湖南大学信息论与纠错编码

第四讲离散信源无失真编码--变长编码方法香农编码法（Shannon）---编码效率低，具有理论意义费诺编码法（Fano）---可以，但不能确保找到最佳编码霍夫曼编码法（Huffman）---平均码长最短，编码效率最高几种常用编码方法：1.Shannon编码法Shannon第一定理虽然没有直接给出构造唯一可译码的方法；在证明定理3.3上界时，已经给出了唯一可译码编码方法：选择每个码字的长度使之满足不等式:注意这里采用二进制编码，D=2.这种编码方法称为Shannon编码方法。log()log()1mmmpxnpx(3-30)1loglogHXHXnDD回顾定理3.3---即变长编码定理（定理3.4）的特例L=1下限:H(X)/logD上限:1+H(X)/logD1logHXnD如果：也可以找到唯一可译码，但是难以保证紧致码，难以保证传输效率。=logHXnD如果：平均码长取下界，则能得到紧致码，对信源消息的概率分布有特殊要求注意以下两点回顾：定理3.3上界的证明1,mtmmPxtD不一定为整数•把概率写成指数形式•用这种方式构造码，则码长满足：=,11,mmmmmmmmmmntttnttntt是整数不是整数(3-28)loglogmmPxtDlog()log()1mmmpxnpx(3-30)1231m1(1)M()()()...()(2)log()1,2,...,(3)-log()log()1log()(4),m()(5)MmmmmmmmiiipxpxpxpxpxmMpxnpxnpxPPsP设信源发出个消息，将其按照概率递减排列：计算出各消息的值，；根据（330）计算每个码长（注意为整数则取等号）；为了编成唯一可译码首先计算第个消息的累加概率将累加概率()(6).mmnnm为小数变成二进制小数；根据码长，取小数点后位数作为第个消息的代码组(码字)Shannon编码步骤[举例]Shannon编码，以s5为例[举例]Shannon编码，以s5为例55512345151255alog(s)=-log(0.15)2.74=bssss()0.20.190.18+0.170.74c0.74=d3iipnxPPsnx10、计算，取整数3作为码字的码长、计算消息，，，的累加概率:、把换乘二进制小数（0.74）（0.1011110）；、取小数点后位（即位）101作为的码字可以求得平均码长和编码效率：平均码长：3.14编码效率：2.61===0.8313.141logHXnD由表可以看出,一共有5个三位的代码组,各代码组之间至少有一位数字不相同,故是唯一可译码。同时可以看出，这7个代码组即时码。Shannon编码方法的核心思想:码字的长度满足则可找到唯一可译码。至于采用什么方法找一种唯一可译码，则无关紧要。log(s)1()mmnp，注意取整Shannon编码小结例子中的Shannon编码是不是最佳码？？？先回忆一下:“树码一定是即时码,唯一可译码”那么能否利用树码来寻找满足条件的唯一可译码呢？（码树结构图）在三级节点上找出5个终端节点;(码长为3的5个)在四级节点上找出1个终节点;(码长为4的1个)在七级节点上找出1个终端节点(码长为7的1个)“从树根到每一个终端节点所走的路径不相同”从码树可以看出，这不是一个紧凑码树(树码的各个分支都延伸到最后一级端点。)也就是说按照Shannon编码方法编出来的码可以使不超过上界，但并不一定能使码长最短，即编出来的不一定是最佳码。2.Fano编码方法Fano编码依据----Shannon第一定理：回顾：Shannon第一定理的物理意义：信源等概分布时，能得到最大传输率；信源编码时，应使编码后的码集中各码字尽可能等概分布，若将该码集看成一个新的信源，此时新信源所含信息量最大。Fano编码步骤Fano编码不是最佳的编码方法。Fano码的编码程序如下：1.首先,将信源符号以概率递减的次序排列；2.将排列好的信源符号划分成两大组,使每组的概率和近于相同,并各赋于二元码符号“0”和“1”；3.将每一个大组的信源符号再分成两组，使同一个组的两个小组的概率和近于相同，并分别赋于一个二元码符号；4.依次下去，直至每个小组只剩下一个信源符号为止；5.逐次分解得到的码元排列即信源符号所对应码字。Fano编码计算Fano编码的编码效率71HX=()20.20.1730.190.18+0.1540.10.010.18+0.152.742.61===0.9352.741logmmmnnPxHXnD信源熵：2.61平均码长:编码效率：Fano编码效率略高于Shannon编码逐次分解中，各码元取“0”或“1”是任意的，但码长要一致Fano编码的核心思想：“一分为二”Fano编码方法实际上是构造码树的一种方法，即时码；Fano编码方法考虑了信源的统计特性，使大概率的信源符号对应短码，小概率的信源符号对应长码。Fano编码方法不一定能使短码得到充分利用。当信源符号多，一些符号概率分布很接近，分两大组的组合方法就会很多。可能某种分大组的结果，会出现后面小组“概率和”相差较远，因而平均码长增加。Fano编码方法同样适用于D进制编码，只需每次分成D组即可。17[Fano编码]单符号离散无记忆信源对该信源编二进制费诺码,编码过程如表:二进制费诺编码信源符号概率编码码字码长x10.2500002x20.251012x30.1251001003x40.12511013x50.062510011004x60.0625111014x70.06251011104x80.062511111412345678,,,,,()1/41/41/81/81/161/161/161/16XxxxxxxxxPX18信源熵为H(X)=2.75(比特/符号)平均码长为•编码效率为η=1•之所以如此,因为每次所分两组的概率恰好相等。(0.250.25)20.12230.0625442.75(/)K比特符号费诺码比较适合于每次分组概率都很接近的信源；特别是对每次分组概率都相等的信源进行编码时,可达到理想的编码效率。3.霍夫曼(Huffman)编码1952年Huffman提出了对统计独立信源达到最小平均码长的编码方法，也即最佳码。最佳性可从理论上证明。这种码具有即时性和唯一可译性。该编码是常见的一种统计编码。对给定的数据流，计算其每个字节的出现频率。根据频率表，运用哈夫曼算法可确定分配各字符的最小位数，然后给出一个最优的编码。和出现概率相关，广泛用于IT领域（1）将信源符号按概率递减顺序排列；（2）把二个最小的概率加起来，作为新符号的概率；（3）重复步骤1,2,（注意新符号概率和原来符号概率进行递减排列，如概率相等，新符号概率往上排，），直到概率和达到1为止；（4）在每次合并消息时，将被合并的消息赋以1和0或0和1（会造成编码不唯一，但不会影响码长）；（5）寻找从每一信源符号到概率为1处的路径，记录下路径上的1和0；（6）对每一符号写出“1”、“0”序列（从码树的根到终节点，即从最后一步开始得到码字）。Huffman编码过程如下：[举例]Huffman编码概率之和往上排（1）将信源符号按概率递减顺序排列；（2）把二个最小的概率加起来，作为新符号的概率；（3）重复步骤1,2,（注意新符号概率和原来符号概率进行递减排列），直到概率和达到1为止；若概率相等，也可以把新符号排在下面（4）在每次合并消息时，将被合并的消息赋以1和0或0和1，（通常概率大的取1）；（5）寻找从每一信源符号到概率为1处的路径，记录下路径上的1和0；（6）对每一符号写出“1”、“0”序列（从码树的根到终节点）。Huffman编码另一种方式：[举例]Huffman编码：另一方式：概率之和往下排（若概率之和和原概率相等时）平均码长等长码：平均码长=每个码字码长1()MmmmnnPC码字长度码字Cm出现概率码长的概率加权平均两种方式的区别与优劣：考察平均码长和码长的均方差511521()20.830.22.2()10.420.230.240.22.2mmmmmmnnPCnnPC222122222222.20.832.20.20.1612.20.422.20.232.20.242.20.21.36EnnEnn平均码长相等第一种方式均方差较小，只有两种码长，更接近于等长编码两种方式的区别：考察平均码长和码长的均方差方差较小的编码方法较好为使得码方差较小，概率之和往上排，这样可以减少合并次数，则可充分利用短码缩减信源时，最后两个码字总是最后一位不同，因此是即时码27[例]设单符号离散无记忆信源如下,要求对信源编二进制哈夫曼码。编码过程如下表01.010.015.017.018.019.020.0)(7654321xxxxxxxxpX信源符号xi符号概率p(xi)编码过程x10.20x20.19x30.18x40.17x50.15x60.10x70.01010.200.190.180.170.150.11010.260.200.190.180.17010.350.260.200.19010.390.350.26010.610.3901码字101100000101001100111在图中读取码字的时候,要从后向前读,此时编出来的码字是可分离的即时码。28•熵61.201.0log01.010.0log10.015.0log15.017.0log17.018.0log18.019.0log19.02.0log2.0)(XH平均码长为72.2401.0410.0315.0317.0318.0219.022.0)(71iiiKxpK•编码效率()()2.6196%2.72HXHXRKHuffman编码小结原则：合并的信源符号位于缩减信源序列尽可能高的位置上，这样可以充分利用短码。特点：(1)概率大的符号对应于短码,概率小的符号对应于长码,充分利用短码。(2)Huffman码是紧致即时码。每次缩减信源的最后二个码字总是最后一位不同。核心思想：“合二为一”3种变长编码方法对比香农码、费诺码、哈夫曼码都考虑了信源的统计特性,使经常出现的信源符号对应较短的码字,使信源的平均码长缩短,从而实现了对信源的压缩；香农码有系统的、惟一的编码方法,但在很多情况下编码效率不是很高；费诺码和哈夫曼码的编码方法都不惟一；费诺码比较适合于对分组概率相等或接近的信源编码；哈夫曼码对信源的统计特性没有特殊要求,编码效率比较高,对编码设备的要求也比较简单,因此综合性能优于香农码和费诺码。变长编码小结1.统计编码，获得与信源分布在统计意义上的匹配；2.Huffman编码具有较高的编码效率;3.码字码长不同，需要大量存储设备来缓冲码字长度的差异，也是码字码长方差小则更好的原因4.存在取空和溢出的问题，连续发送短码---取空，连续发送长码---溢出.解决的办法是设置一定容量的缓冲寄存器.5.变长码适合有限长的信息传输，因为有差错扩散问题；6.解决方法是将长信息分段传输，或增加纠错位。课后学习---限失真信源编码1.无失真编码目的是压缩信源冗余度，避免携带信息能力的浪费；2.很多场合，信源可以有在允许范围内的失真，---限失真编码，比如游程编码等方法。