信息论第5章 信源编码

第5章信源编码教学内容和要求理解无失真信源编码定理，理解异前置码掌握香农码掌握费诺码掌握赫夫曼码6/23/2024一、无失真信源编码定理与异前置码1、无失真信源编码定理定理N次扩展信源的熵率为H(X)，对扩展信源进行二进制编码，设K为码长，对任意给定的ε

>0，只要码率N足够大时，该编码为无失真编码6/23/2024如果码率无论N多大，该编码也一定失真无失真信源编码定理也叫香农第一定理，定理表明了扩展信源无失真编码的存在性，明确了熵率H(X)是无失真编码的码率下界——香农界6/23/20242、编码效率定义扩展信源无失真编码的编码效率从提高传输效率的角度，码率越接近熵率越好6/23/2024无失真信源编码及编码效率信源的熵率例16/23/2024无失真编码1——等长码码长K=2(bit)6/23/2024二次扩展信源6/23/2024码长K=4(bit)6/23/2024等长码的码率为整数，熵率为小数情况下编码效率不可能提高不等长码的平均码长和码率才可能为小数无失真编码2——一种不等长编码6/23/2024二次扩展信源6/23/20246/23/2024无失真信源不等长编码的结论与问题大概率符号序列编为短码、小概率符号序列编为长码有助于压缩平均码长N次扩展有助于压缩平均码长，随N的增大，可以预见码率可能渐进达到熵率出现无失真译码问题——码长不等，接收端如何从码串中唯一分割出对应于每个符号序列的码字6/23/20243、异前置码单义可译码——接收端能从不等长码串中唯一分割出对应于每个符号序列的码字①即时码——能在对应于每个符号序列的码字结束时译出②延时码——等到对应于下个符号序列的码字出现时才能译出定义6/23/2024码A不是单义可译码——不能从不等长码串中唯一分割出对应于每个符号的码字；码B是延时码——它需等到对应于下个符号的码字开头0才能确定本码字的结束；码C是即时码6/23/2024定义异前置码——任何码字都不是其它码字的前缀码C是异前置码异前置码可以用树图构造码C所对应的二进制码树图0101016/23/2024码树图从树根开始到每片树叶的联枝代表一个码字010101码C——0,10,110,1116/23/2024长度为ki

i=1,2,…,nN的二进制异前置码存在的充分必要条件——Kraft不等式4、Kraft不等式6/23/20245、最优码6/23/20246/23/20246/23/2024二、无失真信源编码①将符号序列aii=1,2,…,nN按概率降序排列②确定第i个码字的码长1、香农码编码步骤6/23/2024③令P(a0)=0，计算第i-1个符号序列的累加概率④将Pa(ai)用二进制表示，取小数点后ki位作为符号序列ai的码字ci

i=1,2,…,nN6/23/2024编香农码并计算编码效率①将符号xii=1,2,3,4按概率降序排列例1②确定第i个码字的码长6/23/2024③令P(x0)=0，计算第i个码字的累加概率6/23/2024④将Pa(xi)用二进制表示，取小数点后ki位作为xi的码字ciPa(x1)=0.0=(0.000000…)2→c1=0Pa(x2)=0.5=(0.100000…)2→c2=10Pa(x3)=0.8=(0.110011…)2→c3=110Pa(x4)=0.95=(0.111100…)2→c4=111106/23/2024xiP(xi)kiPa(xi)cix10.5100x20.320.510x30.1530.8110x40.0550.95111106/23/20246/23/2024分别对信源和二次扩展信源编香农码并计算编码效率(1)信源编码并计算编码效率例26/23/2024Pa(x1)=0.0=(0.000000…)2→c1=0Pa(x2)=0.5=(0.100000…)2→c2=10Pa(x3)=0.8=(0.110011…)2→c3=110Pa(x1)=0+0=0Pa(x2)=0+0.5=0.5Pa(x3)=0.5+0.3=0.8xiP(xi)kiPa(xi)cix10.5100x20.320.510x30.230.81106/23/20246/23/2024(2)二次扩展信源编码并计算编码效率6/23/20246/23/2024Pa(x1x1)=0+0=0Pa(x1x2)=0+0.25=0.25Pa(x2x1)=0.25+0.15=0.4Pa(x1x3)=0.4+0.15=0.55Pa(x3x1)=0.55+0.1=0.65Pa(x2x2)=0.65+0.1=0.75Pa(x2x3)=0.75+0.09=0.84Pa(x3x2)=0.84+0.06=0.9Pa(x3x3)=0.9+0.06=0.966/23/2024Pa(x1x1)=0.0=(0.00)2→c1=00Pa(x1x2)=0.25=(0.010)2→c2=010Pa(x2x1)=0.4=(0.011…)2→c3=011Pa(x1x3)=0.55=(0.1000…)2→c4=1000Pa(x3x1)=0.65=(0.1010…)2→c5=1010Pa(x2x2)=0.75=(0.1100)2→c6=1100Pa(x2x3)=0.84=(0.11010…)2→c7=11010Pa(x3x2)=0.9=(0.11100…)2→c8=11100Pa(x3x3)=0.96=(0.11101…)2→c9=111016/23/2024aiP(ai)kiPa(ai)cix1x10.252000x1x20.1530.25010x2x10.1530.4011x1x30.140.551000x3x10.140.651010x2x20.0940.751100x2x30.0650.8411010x3x20.0650.911100x3x30.0450.96111016/23/20246/23/2024香农码的特点编码过程中先确定码长，后确定码字，保证大概率符号序列编为短码，小概率符号序列编为长码第一个符号序列的累加概率为0，对应码字总是0、00、…形式具有唯一性码率不超过熵率1/N个比特，N越大码率越接近熵率6/23/2024习题，(P166)5.16/23/2024①将符号序列aii=1,2,…,nN按概率降序排列②不改变排列次序条件下分为两组，使每组概率尽可能相等③给每组分配一个二进制码元对每个分组重复②③步骤，直到不可分为止2、费诺码编码步骤分配给符号序列ai的全部码元作为该符号序列的码字cii=1,2,…,nN6/23/2024编费诺码并计算编码效率例1①将符号xii=1,2,3,4按概率降序排列②不改变排列次序条件下第一次分组，使每组概率尽可能相等6/23/2024xiP(xi)分组1分组2分组3cix10.50x20.31x30.15x40.05③给每组分配一个二进制码元对每个分组重复②③步骤6/23/2024第二次分组及分配二进制码元xiP(xi)分组1分组2分组3cix10.50x20.310x30.151x40.056/23/2024第三次分组及分配二进制码元xiP(xi)分组1分组2分组3cix10.500x20.31010x30.1510110x40.0511116/23/20246/23/2024例2分别对信源和二次扩展信源编费诺码并计算编码效率(1)信源编码并计算编码效率第一次分组及分配二进制码元6/23/2024第二次分组及分配二进制码元xiP(xi)分组1分组2cix10.500x20.41010x30.11116/23/20246/23/2024(2)二次扩展信源编码并计算编码效率6/23/2024第二次分组及分配二进制码元第一次分组及分配二进制码元6/23/2024第三次分组及分配二进制码元第四次分组及分配二进制码元6/23/2024第六次分组及分配二进制码元第五次分组及分配二进制码元6/23/2024aiP(ai)分组1分组2分组3分组4分组5分组6cix1x10.250000x1x20.2101x2x10.21010x2x20.1610110x1x30.0510011100x3x10.05111101x2x30.041011110x3x20.0410111110x3x30.0111111116/23/20246/23/2024两种方法进行费诺编码并计算平均码长(1)方法1——大概率分组排在前面例3第一次分组及分配二进制码元6/23/2024第二次分组及分配二进制码元第三次分组及分配二进制码元6/23/2024xiP(xi)分组1分组2分组3cix10.40000x20.2101x30.21010x40.110110x50.111116/23/2024(2)方法2——小概率分组排在前面第一次分组及分配二进制码元第二次分组及分配二进制码元6/23/2024第三次分组及分配二进制码元第四次分组及分配二进制码元6/23/2024xiP(xi)分组1分组2分组3分组4cix10.400x20.21010x30.210110x40.1101110x50.1111116/23/2024采用不同排列方法编出的费诺码，码字和码长可能完全不相同，但平均码长相等——编码效率不会因排列方法而改变6/23/2024费诺码的特点编码过程中先确定码字，后确定码长大概率符号序列分解次数少，编为短码，小概率符号序列分解次数多，编为长码不具有唯一性，但不同费诺码的编码效率相同码率不超过熵率1/N个比特，N越大码率越接近熵率6/23/2024习题，(P166)5.26/23/2024①将符号序列aii=1,2,…,nN按概率降序排列②为概率最小的两个符号序列各自分配一个二进制码元③将概率最小的两个符号序列合并成一个新的符号序列，用两者概率之和作为新符号序列的概率3、赫夫曼码编码步骤重复①②③步骤，直到合并出一个以1为概率的新符号序列6/23/2024编赫夫曼码并计算编码效率①将符号xii=1,2,3,4按概率降序排列例1分配给符号序列ai的全部码元作为该符号序列的码字cii=1,2,…,nN②为概率最小的两个符号序列各自分配一个二进制码元6/23/202410③将概率最小的两个符号合并成一个新的符号，用两者概率之和作为新符号的概率0.2x3，xiP(xi)x10.5x2x3x40.30.150.056/23/2024重复①②③步骤，直到合并出一个以1为概率的新符号xiP(xi)x10.5x2x3，0.30.2100.5x2，xiP(xi)x10.5x2，0.5101x1，6/23/2024cikixiP(xi)x10.5x2x3x40.30.150.050.20.511110000101101111233整个编码过程集中在一起6/23/20246/23/2024例2分别对信源和二次扩展信源编赫夫曼码并计算编码效率(1)信源编码并计算编码效率6/23/2024xiP(xi)x10.5x2x30.40.10.510110ciki010111226/23/2024(2)二次扩展信源编码并计算编码效率6/23/2024aiP(ai)x1x10.25x1x2x2x1x2x20.20.20.16x1x30.05x3x1x2x30.050.04x3x20.04x3x30.010.050.091000110.1100.190.410010.35100.61016/23/20242236255560110001000101110000100011000000001000.050.091000110.1