《信息论与编码》复习.ppt

设离散无记忆信源有八种等概率符号，输出长度N=1，H（X）=3bits设离散无记忆信源概率空间为：比特/符号*变长编码在变长编码中，码长L是变化的，根据信源各个符号的统计特性，如概率大的符号用短码，概率小的用长码，使得编码后平均码长降低，从而提高编码效率。*码字的平均长度最短的变长码的码字集合称为最佳变长码。变长码的编码方法主要有：香农（Shannon）码法诺（Fano）码哈夫曼（Huffman）码（最佳变长码）最佳变长编码*Fano编码方法编码对象：离散信源概率集合编码方法（对二元系统）按概率递减的方式将消息及其概率排列起来；将消息分成概率尽可能相同的两个子集，两个子集分别冠以码元符号“1”和“0”。将每个子集再划分为概率尽可能相等的两个子集，并分别冠以11，10和01，00，依此类推，直到子集只包括一个消息为止。*例1将下列消息按二元Fano方法编码：*X2x5x1x6x3x4x7x80.250.250.1250.1250.06250.06250.06250.06250100011011110111100101110011011110111100011001011100110111101111消息概率编码码字*编码后可以计算得到：*Huffman编码方法Huffman编码是一种可变长编码方式，是由美国数学家DavidHuffman创立的，是二叉树的一种特殊转化形式。编码的原理：将使用次数多的代码转换成长度较短的代码，而使用次数少的可以使用较长的编码，并且保持编码的唯一解码性。*Huffman编码方法编码对象：离散信源概率集合*编码方法（对二元系统）将N个信源符号按概率递增（或递减）方式排列起来；用“0”，“1”码符号分别表示概率最小的两个信源符号，并将这两个概率最小的信源符号合并成一个符号，从而得到只包含N-1个符号的新信源，称为S信源的缩减信源S1；*将缩减信源S1的符号仍按概率大小以递减次序排列，再将其最后两个概率最小的符号合并成一个符号，并分别用0，1码符号表示，这样又形成了N-2个符号的缩减信源S2；依次继续下去，直到信源最后只剩下两个符号为止，将这最后两个符号分别用0，1码符号表示，然后从最后一级缩减信源开始，向前返回，就得出各信源符号所对应的码符号序列，即得出对应的码字。*例1将下列消息按二元Huffman方法编码：*X10.20x20.19x30.18x40.17x50.15x60.10x70.01SS1100.11100.26S2100.35100.39100.61101.00S3S4S5111001101000100010000*编码后可以计算得到：*Huffman编码的特点Huffman编码方法得到的编码不是唯一的；每次对信源缩减时，赋予信源最后两个概率最小的符号，用0和1可以是任意的，但这不会影响码字的长度；对信源进行缩减时，若两个概率最小的符号合并后概率与其他信源符号的概率相同时，这两者在缩减信源中进行概率排序，其位置次序可以是任意的；*Huffman编码方法保证了概率大的符号对应于短码，概率小的符号对应于长码，充分利用了短码；Huffman编码方法缩减信源的最后两个码字总是最后一位不同，从而保证了编码结果是即时码；*码方差码方差定义δ2=E[(ni-L)2]=∑p(xi)(ni-L)2对信源进行压缩时，若两个概率最小的符号合并后的概率与其他信源符号的概率相同时，这两者在压缩信源中进行概率排序，其位置次序可以是任意的，这种情况将影响码字的长度；在进行编码时，为了得到码方差最小的码，应使合并的信源符号位于压缩信源序列尽可能高的位置上，以减少再次合并的次数，充分利用短码；*码方差例子设离散无记忆信源如下，分别按如下两种方式编码，分析哪种编码更好。*Huffman编码1*Huffman编码2*编码1、2的分析比较这两种编码的平均码长和编码效率相同，分别为：L=2.2；η=0.965但它们的码方差不同。对于方法1，δ2=1.36，对于方法2，δ2=0.1