信息论与编码07-最佳信源编码.ppt

1、9/7/2020,1/31,电信学院 汪汉新,第五章信源编码,1. 香农编码 2. 费诺编码 3. 哈夫曼编码,9/7/2020,2/31,电信学院 汪汉新,本章节教学内容、基本要求、重点与难点,1. 教学内容： 信源编码的概念。 三种最佳的信源编码。 2. 教学基本要求： 掌握香农编码。 掌握费诺编码。 掌握哈夫曼编码。 3. 重点与难点： 信息率，平均码长和编码效率的计算。 多进制哈夫曼编码。,9/7/2020,3/31,电信学院 汪汉新,引言,香农编码定理虽然指出了理想编码器的存在性,但是并没有给出实用码的结构及构造方法； 编码理论正是为了解决这一问题而发展起来的科学理论； 编码的目的是

2、为了优化通信系统，使通信系统的性能指标有效性、可靠性、安全性和经济性达到最佳；,9/7/2020,4/31,电信学院 汪汉新,按不同的编码目的，编码分为三类：信源编码、信道编码和安全编码（加密编码）。 信源编码：提高信息传输的有效性。通常通过压缩信息的冗余度来实现。 信道编码：提高信息传输的可靠性。通常通过增加信息的冗余度来实现。与信源编码正好相反。 加密编码：提高通信系统的安全性。通常通过加密和解密来实现。从信息论的观点出发，“加密”可视为增熵的过程，“解密”可视为减熵的过程。,9/7/2020,5/31,电信学院 汪汉新,信源编码,信源编码理论是信息论的一个重要分支，其理论基础是信源编码的

3、两个定理。 香农第一定理（无失真信源编码定理）：是离散信源/数字信号编码的基础； 香农第三定理（限失真信源编码定理）：是连续信源/模拟信号编码的基础。 信源编码的分类： 离散信源编码：可做到无失真编码； 连续信源编码：只能做到限失真信源编码；,9/7/2020,6/31,电信学院 汪汉新,无失真信源编码定理： 定长编码定理：一个熵为H(X)的离散无记忆信源X1X2XlXL，对信源长为L的符号序列进行定长编码，设码字是从m个信源符号集内选取K个码元组成Y1Y2YkYK。对于任意0，0只要满足 (K/L)log2mH(X)+ 则当L足够大时，必可使译码差错小于，即译码错误概率能为任意小。 变长编码

4、定理：(K/L)log2mH(X)+，其中K为平均码长。 限失真信源编码定理：对于给定的失真D，总可以找到一种信源编码方法，只要传输速率R大于R(D)，就可以在平均失真任意接近D的条件下实现波形重建。 说明1：R(D)称为率失真函数，它是单调非增函数，速率越高，平均失真越小。 说明2：为了保证在一定速率下的失真，必需采用信源编码，因而会引入编码延时。,编码理论,9/7/2020,7/31,电信学院 汪汉新,香农编码,设离散无记忆信源 二进制香农码的编码步骤如下(4步)： 将信源符号按概率从大到小的顺序排列 p(x1) p(x2) p(xn) 令p(x0)=0，用pa(xj)，j=i+1表示第i

5、个码字的累加概率 确定满足下列不等式的整数ki ，并令ki为第i个码字的长度 log2 p(xn)ki1 log2 p(xn) 将pa(xj) 用二进制表示，并取小数点后ki 位作为符号xi的编码。,9/7/2020,8/31,电信学院 汪汉新,例有一单符号离散无记忆信源 对该信源编二进制香农码。其编码过程如表所示。,9/7/2020,9/31,电信学院 汪汉新,香农码的平均码长 若对上述信源采用等长编码，要做到无失真译码，每个符号至少要用3个比特表示。相比较，香农编码对信源的等长编码而言有0.3比特/符号的压缩。,由离散无记忆信源熵定义，可计算出： 对上述信源采用香农编码的信息率为 编码效率

6、为信源熵和信息率之比。则 可以看出，编码效率并不是很高。,9/7/2020,10/31,电信学院 汪汉新,费诺编码,费诺编码也是一种常见的信源编码方法。编码步骤如下： 将概率按从大到小的顺序排列，令 p(x1) p(x2) p(xn) 按编码进制数将概率分组，使每组概率尽可能接近或相等。如编二进制码就分成两组，编m进制码就分成m组。 给每一组分配一位码元。 将每一分组再按同样原则划分，重复步骤2和3，直至概率不再可分为止。,9/7/2020,11/31,电信学院 汪汉新,例 与香农编码一样的单符号离散信源 对该信源编二进制费诺码。编码过程如表。,9/7/2020,12/31,电信学院 汪汉新,

7、上述码字还可用码树来表示，如图所示。,9/7/2020,13/31,电信学院 汪汉新,该信源的熵为 平均码长为 编码效率为 费诺编码有较高的编码效率。费诺码比较适合于每次分组概率都很接近的信源。特别是对每次分组概率都相等的信源进行编码时，可达到理想的编码效率。,9/7/2020,14/31,电信学院 汪汉新,例 有一单符号离散无记忆信源 对该信源编二进制费诺码，编码过程如表。,9/7/2020,15/31,电信学院 汪汉新,码树图如图 信源熵为 H(X)=2.75(比特/符号) 平均码长为 信息率 编码效率为=100%。因为每次所分两组的概率恰好相等。,9/7/2020,16/31,电信学院

8、汪汉新,5.4.1 编码步骤,哈夫曼(Huffman)编码是一种效率比较高的变长无失真信源编码方法。 将信源符号按概率从大到小的顺序排列，令 p(x1) p(x2) p(xn) 给两个概率最小的信源符号p(xn-1)和p(xn)各分配一个码位“0”和“1”，将这两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，结果得到一个只包含(n1)个信源符号的新信源。称为信源的第一次缩减信源，用S1表示。 将缩减信源S1的符号仍按概率从大到小顺序排列，重复步骤2，得到只含(n2)个符号的缩减信源S2。 重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符号的概率之和必为1。然后

9、从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字。,哈夫曼编码,9/7/2020,17/31,电信学院 汪汉新,例 设单符号离散无记忆信源如下，要求对信源编二进制哈夫曼码。,9/7/2020,18/31,电信学院 汪汉新,将上图左右颠倒过来重画一下，即可得到二进制哈夫曼码的码树，如图所示。,9/7/2020,19/31,电信学院 汪汉新,信源熵为 平均码长为 编码效率为 若采用定长编码，码长K=3，则编码效率 可见哈夫曼的编码效率提高了12.7%。,9/7/2020,20/31,电信学院 汪汉新,注意：哈夫曼的编码并不惟一。 每次对缩减信源两个概率最小的符号分配“0”和

10、“1”码元是任意的，所以可得到不同的码字。只要在各次缩减信源中保持码元分配的一致性，即能得到可分离码字。 不同的码元分配，得到的具体码字不同，但码长ki不变，平均码长 也不变，所以没有本质区别； 缩减信源时，若合并后的新符号概率与其他符号概率相等，从编码方法上来说，这几个符号的次序可任意排列，编出的码都是正确的，但得到的码字不相同。不同的编法得到的码字长度ki也不尽相同。,9/7/2020,21/31,电信学院 汪汉新,举例说明上述问题 例: 单符号离散无记忆信源 方法一：合并后的新符号排在其它相同概率符号的后面。,9/7/2020,22/31,电信学院 汪汉新,9/7/2020,23/31,

11、电信学院 汪汉新,方法二：合并后的新符号排在其它相同概率符号的前面。,9/7/2020,24/31,电信学院 汪汉新,9/7/2020,25/31,电信学院 汪汉新,单符号信源编二进制哈夫曼码，编码效率主要决定于信源熵和平均码长之比。对相同的信源编码，其熵是一样的，采用不同的编法，得到的平均码长可能不同。平均码长越短，编码效率就越高。 编法一的平均码长为 编法二的平均码长为 可见 ，本例两种编法的平均码长相同，所以编码效率相同。,9/7/2020,26/31,电信学院 汪汉新,讨论：哪种方法更好？ 定义码字长度的方差2：长度ki与平均码长 之差的平方的数学期望，即 编法一码字长度方差： 编法二

12、码字长度方差：,可见：编法二的码长方差要小许多。意味着第二种编码方法的码长变化较小，比较接近于平均码长。 编法一的5个码字有4种不同的码长；而编法二的码字只有2种不同的码长；显然，编法二的方法更简单、更容易实现，所以更好。 结论：在哈夫曼编码过程中，对缩减信源符号按概率由大到小的顺序重新排列时，应使合并后的新符号尽可能排在靠前的位置，这样可使合并后的新符号重复编码次数减少，使短码得到充分利用。,9/7/2020,27/31,电信学院 汪汉新,“全树”概念 定义：码树图中每个中间节点后续的枝数为m时称为全树；若有些节点的后续枝数不足m，就称为非全树。 二进制码不存在非全树的情况，因为后续枝数是一

13、时，这个枝就可以去掉使码字长度缩短。 对m进制编码：若所有码字构成全树，可分离的码字数（信源个数）必为 m+k(m1)。k为信源缩减次数。 若信源所含的符号数n不能构成m进制全树，必须增加s个不用的码字形成全树。显然sm1，若s=m1，意味着某个中间节点之后只有一个分枝，为了节约码长，这一分枝可以省略。,m进制哈夫曼编码,9/7/2020,28/31,电信学院 汪汉新,例：对前面的单符号离散无记忆信源编三进制哈夫曼码。 这里：m=3，n=8 令k=3，m+k(m1)=9，则 s=9n=98=1 所以第一次取ms=2个符号进行编码。,9/7/2020,29/31,电信学院 汪汉新,9/7/2020,30/31,电信学院 汪汉新,平均码长为 信息率为 编码效率为 可见：哈夫曼的编码