信源编码一离散信源无失真编码.pptVIP

DMS的等长编码取ε=0.01。找L0使得即L0=252435。当L≥252435时总有P{(U1U2…UL)=(u1u2…uL)|-0.01≤IL-H(U)≤0.01}≥0.99。另一方面，当事件(u1u2…uL)中a1的个数为k，a2的个数为L-k时，DMS的等长编码事件(u1u2…uL)属于典型序列集TU(L,0.01)；当且仅当0.01≤IL-H(U)≤0.01；当且仅当单击此处可添加副标题设L=252435。此时=692.61096；0=1326.8690。当事件(u1u2…u252435)中a1的个数不超出闭区间[693，1326]内时，(u1u2…u252435)∈TU(252435,0.01)；否则(u1u2…u252435)不属于TU(252435,0.01)。(u1u2…u252435)∈TU(252435,0.01)的概率不小于0.99；(u1u2…u252435)∈TU(252435,0.01)的个数为DMS的等长编码单击此处可添加副标题对L=252435，对应地取整数N=[R0L]=126217。则N/LR0，这就是说2元编码的实际编码速率小于编码设备的编码速率。2元编码的编码方法：将TU(252435,0.01)中的事件用不同的126217长码字表示；将TU(252435,0.01)外的事件用同一个126217长码字表示，该码字已经用于表示了TU(252435,0.01)中的一个事件。由于|TU(252435,0.01)|≤212012.66172126217，码字足够用。2元编码的译码方法：将码字译为它所表示的TU(252435,0.01)中的事件(u1u2…u252435)。于是，译码错误的概率为P((u1u2…u252435)不属于TU(252435,0.01))≤ε=0.01。DMS的等长编码3.3DMS的不等长编码不等长编码的优越性总体上减少码字的长度。不等长编码的特殊问题唯一可译性，或者叫做可识别性。对于一个码，如果存在一种译码方法，使任意若干个码字所组成的字母串只能唯一地被翻译成这几个码字所对应的事件序列。这个码就被称为是唯一可译的。解决方案：适当地编码，使得每个码字都具有识别标记。（注解：一个唯一可译的、码字长度不超过N的D元码，其码字个数小于D(DN-1)/(D-1)个。这是因为两个码字c(1)和c(2)连接成的字母串c(1)c(2)不能是码字）DMS的不等长编码平均码长希望平均码长小。解决方案：概率大的事件用短码字。ONE不等长编码面临问题同步问题01划分唯一性02译码延迟03缓存问题04几个定义唯一可译码字头或前缀树码，满树，非满树，全树逗点码，无逗点码：若①事件与码字一一对应；②每个码字的开头部分都是一个相同的字母串；③这个字母串仅仅出现在码字的开头，不出现在码字的其它部位，也不出现在两个码字的结合部。则称这个字母串为逗号，称此码为逗点码。（逗点码显然是唯一可译的，识别码字的方法为：见到逗号就识别为一个码字的开始。）异字头码或异前缀码：①若事件与码字一一对应；②每个码字都不是另一个码字的开头部分（字头）。则称此码为异字头码。（异字头码也是唯一可译的，识别码字的方法为：见到一个码字就识别为一个码字。）树码构造异字头码123456logo例子信源字母集概率码A码B码C码Da1a2a3a40.50.250.1250.125001100100110101101110010110111例观察表。码A不是唯一可译的。码B不是唯一可译的。码C是唯一可译的，识别码字的方法为：见“0”或“111”就是一个码字的结束。实际上，码C是异字头码。码D是唯一可译的，识别码字的方法为：见“0”就是一个码字的开始。实际上，码D是逗点码，其中“0”是逗号。码C不是逗点码。码D不是异字头码。码C的平均码长比码D的平均码长小：码C的平均码长为1×0.5+2×0.25+3×0.125+3×0.125=1.75；码D的平均码长为1×0.5+2×0.25+3×0.125+4×0.125=1.875。异字头码的第一种构造方法：Shannon-Fano编码法（D元编码，字母表为{0,1,…,D-1}）（1）将源随机变量的事件按概率从大到小排成一行。（2）将此行切分为D段，分别赋予标号“0”到“D-1”，称为1级标号。（3）将每个非空段再切分为D段，分别赋予标号“0”到“D-1”，称为2级标号。（4）将每个非空段再切分为