信息论5.2-2信源编码

1、信源编码徐伟业电子信息工程教研室25.2无失真信源编码最佳码的定义凡是能载荷一定的信息量，且码字的平均长度最短，可分离的变长码的码字集合都可称为最佳码最佳编码思想将概率大的信息符号编以短的码字，概率小的符号编以长的码字，使得平均码字长度最短最佳码的编码主要方法香农（Shannon）、费诺（Fano）、哈夫曼（Huffman）编码35.2无失真信源编码香农编码Shanon编码算法是一种简单的按概率编码的方法，对于一个离散无记忆信源，如果其某一符号ai的先验概率为p(ai)，则就取其码长为45.2无失真信源编码香农编码（1）将信源消息符号按其出现的概率大小依次排列（2）确定满足下列不等式的整数码长

2、Ki55.2无失真信源编码香农编码（3）为了编成唯一可译码，计算第i个消息的累加概率（4）将累加概率Pi变换成二进制数（乘2取整，顺序排列）（5）取Pi二进数的小数点后Ki位即为该消息符号的二进制码字65.2无失真信源编码例 设信源共7个符号消息，其概率和累加概率如下表所示信源消息符号ai符号概率(ai)累加概率Pi-log p(ai)码字长度Ki码字a10.2002.323000a20.190.22.393001a30.180.392.473011a40.170.572.563100a50.150.742.743101a60.100.893.3241110a70.010.996.647111

3、111075.2无失真信源编码码元/符号比特/码元 85.2无失真信源编码费诺编码（1）将信源消息符号按其出现的概率大小依次排列（2）将依次排列的信源符号按概率值分为两大组，使两个组的概率之和近于相同，并对各组赋予一个二进制码元“0”和“1”95.2无失真信源编码费诺编码（3）将每一大组的信源符号进一步再分成两组，使划分后的两个组的概率之和近于相同，并又赋予两个组一个二进制符号“0”和“1”（4）如此重复，直至每个组只剩下一个信源符号为止（5）信源符号所对应的码字即为费诺码105.2无失真信源编码消息符号ai各个消息概率 p(ai)第一次分组第二次分组第三次分组第四次分组二元码字码长Kia10

4、.2000002a20.19100103a30.1810113a40.1710102a50.15101103a60.101011104a70.01111114115.2无失真信源编码 码元/符号 bit/符号 125.2无失真信源编码费诺编码的基本特点费诺编码在构造码树时，是从树根开始到终端节点结束由于赋码元时的任意性，因此编出的码字不是唯一的费诺编码虽属于概率匹配范畴，但并未严格遵守匹配规则，有时出现概率小的码长反而小。因此平均码长一般不会最小费诺码比较适合于每次分组概率都很接近的信源。特别是对每次分组概率都相等的信源进行编码时，可达到理想的编码效率135.2无失真信源编码20110.25a

5、24111110.0625a841110010.0625a741101010.0625a6411000.0625a5310110.125a43100000.125a3200010.25a1码长Ki二元码字第四次分组第三次分组第二次分组第一次分组各个消息概率 p(ai)消息符号ai001145.2无失真信源编码 码元/符号 bit/符号 bit/符号 155.2无失真信源编码哈夫曼编码（1）将信源消息符号按其出现的概率大小依次排列（2）取两个概率最小的字母分别配以0和1两个码元，并将这两个概率相加作为一个新字母的概率，与未分配的二进符号的字母重新排队165.2无失真信源编码哈夫曼编码（3）对重排

6、后的两个概率最小符号重复步骤(2)的过程（4）不断继续上述过程，直到最后两个符号配以0和1为止（5）从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码字175.2无失真信源编码哈夫曼编码信源符号ai概率p(ai)码字Wi码长Kia10.20102a20.19112a30.180003a40.170013a50.150103a60.1001104a70.0101114185.2无失真信源编码哈夫曼编码0.20 0.20 0.26 0.35 0.39 0.61 1.00.19 0.19 0.20 0.26 0.35 0.390.18 0.18 0.19 0.20 0.260.17

7、 0.17 0.18 0.190.15 0.15 0.170.10 0.110.01010101010101195.2无失真信源编码 码元/符号 bit/符号 哈夫曼编码效率最高，费诺编码效率次之，香农编码效率最低205.2无失真信源编码哈夫曼编码方法得到的码并非唯一（1）每次对信源缩减时，赋予信源最后两个概率最小的符号，用0和1是可以任意的。（不影响码长）（2）缩减信源时，对等概符号排序位置的放置次序是可以任意的。（影响码长） 一般将合并的概率放在上面，这样可获得较小的码方差215.2无失真信源编码哈夫曼编码例 设有离散无记忆信源5.2无失真信源编码0.4 0.4 0.4 0.6 1.0 0

8、.2 0.2 0.4 0.40.2 0.2 0.20.1 0.2 0.10.4 0.4 0.4 0.6 1.0 0.2 0.2 0.4 0.40.2 0.2 0.20.1 0.20.10101010101010101235.2无失真信源编码信源符号ai概率p(ai)码字Wi1码长Ki1码字Wi2码长Ki2a10.411002a20.2012102a30.20003112a40.1001040103a50.1001140113245.2无失真信源编码255.2无失真信源编码265.2无失真信源编码哈夫曼编码的特点:（1）采用概率匹配方法，充分利用短码，效率很高。（2）所构造的码是即时码。275.

9、2无失真信源编码m进制哈夫曼编码二进制霍夫曼码的编码方法可以很容易推广到m进制的情况。编码过程中构成缩减信源时，每次都是将m个概率最小的符号合并，并分别用0，1，m-1码符号表示即可为了充分利用短码，使哈夫曼编码的平均码长最短，必须使最后一步缩减的信源有m个信源符号，因此，对于m进制编码，信源符号数n，必须满足 n=(m-1)+m285.2无失真信源编码m进制哈夫曼编码 例：对如下单符号离散无记忆信源编三进制哈夫曼码这里：m=3，n=8令=3，m+(m1)=9，则 t=9n=98=1所以,需要增加一个虚假符号，或第一次取m-t=2个符号进行编码295.2无失真信源编码m进制哈夫曼编码其中，表示

10、缩减次数，（m-1）表示每次缩减减少的信源符号数对于二进制编码，n=+2，只要n2，存在整数0对于m进制编码，n为正整数，不一定存在整数使等式成立，此时用虚设方法，增补t个概率为0的符号xn+1,xn+2, ,xn+t,使下式成立 n+t=(m-1)+m305.2无失真信源编码315.2无失真信源编码325.2无失真信源编码变长编码的存储问题：变长编码的平均码字长度比定长码短。但对于信源某一个符号而言，有时可能会比定长码长。所以编码简单化的代价是要有大量的存储设备来缓冲码字长度的差异。存储时主要问题：溢出或取空，这也就是码方差小的码质量好的原因。5.2无失真信源编码解决方法：由信源速率与信道速率进行换算得到：在溢出率和取空率都小于0.001时，存储容量与单位时间内的信源符号数关系为C为存储容