信息论第四章

1、信息论第四章第1页，共78页，2022年，5月20日，1点23分，星期一信源编码：以提高通信有效性为目的的编码。通常通过压缩信源的冗余度来实现。采用的一般方法是压缩每个信源符号的平均比特数或信源的码率。即同样多的信息用较少的码率传送，使单位时间内传送的平均信息量增加，从而提高通信的有效性。信道编码：是以提高信息传输的可靠性为目的的编码。通常通过增加信源的冗余度来实现。采用的一般方法是增大码率/带宽。与信源编码正好相反。密码：是以提高通信系统的安全性为目的的编码。通常通过加密和解密来实现。从信息论的观点出发，“加密”可视为增熵的过程，“解密”可视为减熵的过程。第一节 引言第2页，共78页，202

2、2年，5月20日，1点23分，星期一信源编码理论是信息论的一个重要分支，其理论基础是信源编码的两个定理。无失真信源编码定理：是离散信源/数字信号编码的基础；限失真信源编码定理：是连续信源/模拟信号编码的基础。信源编码的分类：离散信源编码、连续信源编码和相关信源编码三类。离散信源编码：独立信源编码，可做到无失真编码；连续信源编码：独立信源编码，只能做到限失真信源编码；相关信源编码：非独立信源编码。第一节 引言第3页，共78页，2022年，5月20日，1点23分，星期一第二节 码的分类 编码器可以看作这样一个系统，它的输入端为原始信源S，其符号集为 ；而信道所能传输的符号集为 编码器的功能是用符号

3、集X中的元素，将原始信源的符号 变换为相应的码字符号 ，所以编码器输出端的符号集为 称为码字， 为码字 的码元个数，称为码字 的码字长度，简称码长。 编码器第4页，共78页，2022年，5月20日，1点23分，星期一1、二元码： 码符号集X=0,1，如果要将信源通过二元信道传输，必须将信源编成二元码，这也是最常用的一种码。2、等长码： 若一组码中所有码字的长度都相同，称为等长码。3、变长码： 若一组码中所有码字的长度各不相同，称为变长码。4、非奇异码： 若一组码中所有码字都不相同，称为非奇异码。第二节 码的分类第5页，共78页，2022年，5月20日，1点23分，星期一5、奇异码： 若一组码中

4、有相同的码字，称为奇异码。6、码的N次扩展： 若码 ， 码 则称码B为码C的N次扩展码。7、唯一可译码： 若码的任意一串有限长的码符号序列只能被唯一的译成所对应的信源符号序列，则称此码为唯一可译码。 第二节 码的分类第6页，共78页，2022年，5月20日，1点23分，星期一例：如果有四个信源符号s1，s2，s3，s4，采用二元编码，l=2，则可以编成s1=00，s2=01，s3=10，s4=11。第三节 等长信源编码定理如果我们要对信源的N次扩展信源进行编码，也必须满足 ， 两边取对数得：表示平均每个信源符号所需的码符号个数。若对信源进行等长编码，则必须满足其中，l是码长，r是码符号集中的码

5、元数，q信源符号个数。第7页，共78页，2022年，5月20日，1点23分，星期一第二节 等长码例：对英文电报得32个符号进行二元编码，根据上述关系： 我们继续讨论上面得例子，我们已经知道英文的极限熵是1.4bit,远小于5bit，也就是说，5个二元码符号只携带1.4bit的信息量，实际上，5个二元符号最多可以携带5bit信息量。我们可以做到让平均码长缩短，提高信息传输率第8页，共78页，2022年，5月20日，1点23分，星期一第二节 等长码 我们举例说明： 设信源而其依赖关系为：第9页，共78页，2022年，5月20日，1点23分，星期一第二节 等长码若不考虑符号间的依赖关系，可得码长l2

6、若考虑符号间的依赖关系，则对此信源作二次扩展 可见，由于符号间依赖关系的存在，扩展后许多符号出现的概率为0，此信源只有4个字符，可得码长 ，但平均每个信源符号所需码符号为第10页，共78页，2022年，5月20日，1点23分，星期一第二节 等长码 我们仍以英文电报为例，在考虑了英文字母间的相关性之后，我们对信源作N次扩展，在扩展后形成的信源（也就是句子）中，有些句子是有意义的，而有些句子是没有意义的，我们可以只对有意义的句子编码，而对那些没有意义的句子不进行编码，这样就可以缩短每个信源符号所需的码长。 等长信源编码定理给出了进行等长信源编码所需码长的极限值。第11页，共78页，2022年，5月

7、20日，1点23分，星期一定理4.3（等长信源编码定理） 一个熵为H(S)的离散无记忆信源，若对其N次扩展信源进行等长r元编码，码长为l，对于任意 大于0，只要满足当N无穷大时，则可以实现几乎无失真编码，反之，若：则不可能实现无失真编码，当N趋向于无穷大是，译码错误率接近于1。第三节 等长信源编码定理第12页，共78页，2022年，5月20日，1点23分，星期一定理4.3的条件式可写成：左边表示长为 的码符号所能载荷的最大信息量，而右边代表长为N的序列平均携带的信息量。因此，只要码字传输的信息量大于信源序列携带的信息量，总可以实现无失真编码 。 第三节 等长信源编码定理定理4.3的条件式也可写

8、成：令： 称之为编码信息率。可见，编码信息率大于信源的熵，才能实现无失真编码。第13页，共78页，2022年，5月20日，1点23分，星期一最佳编码效率为：第三节 等长信源编码定理为了衡量编码效果，引进称为编码效率。第14页，共78页，2022年，5月20日，1点23分，星期一例：设离散无记忆信源：若采用等长二元编码，要求编码效率 ，允许错误率，则：也就是长度要达到4130万以上。第三节 等长信源编码定理第15页，共78页，2022年，5月20日，1点23分，星期一1、唯一可译变长码与及时码信源符号出现概率码1码2码3码4s1s2s3s41/21/41/81/80110011010000111

9、010010001010010001第四节 变长信源编码定理第16页，共78页，2022年，5月20日，1点23分，星期一第五节 变长码 码1是一个奇异码，不是唯一可译码；码2也不是唯一可译码，因为收到一串序列是，无法唯一译出对应的原符号序列，如0100，即可译作s4s3s1,也可译作s4s1s3,s1s2s3或s1s2s1s1；码3和码4都是唯一可译的。 但码3和码4也不太一样，码4称作逗点码，只要收到1，就可以立即作出译码；而码3不同，当受到一个或几个码是，必须参考后面的码才能作出判断。 定义，在唯一可译码中，有一类码，它在译码是无须参考后面的码字就可以作出判断，这种码称为即时码。第17页

10、，共78页，2022年，5月20日，1点23分，星期一定义：如果一个码组中的任一个码字都不是另一个码字的续长，或者说，任何一个码字后加上若干码元后都不是码组中另一个码字，则称为即时码。 所有的码非奇异码唯一可译码即时码第四节 变长信源编码定理第18页，共78页，2022年，5月20日，1点23分，星期一2、即时码的树图构造法我们可以用树图的形式构造即时码，如01001111010010001码4的树图10110000101001000码3的树图第四节 变长信源编码定理树根码字的起点树枝数码的数节点数码字的一部分节数码长端点码字满树等长码非满树变长码第19页，共78页，2022年，5月20日，1

11、点23分，星期一 在每个节点上都有r个分枝的树称为整树，否则称为非整树。 即时码的树图还可以用来译码第四节 变长信源编码定理第20页，共78页，2022年，5月20日，1点23分，星期一3、克拉夫特（Kraft）不等式定理4.4 对于码符号为 的任意即时码，所对应的码长为 ，则必定满足： 反之，若码长满足上式，则一定存在这样的即时码 。 可以根据即时码的树图构造法来证明。 后来，B.McMillan证明了对于唯一可译码也必须满足上面的不等式，第四节 变长信源编码定理第21页，共78页，2022年，5月20日，1点23分，星期一定理4.6 若存在一个码长为 唯一可译码，则一定存在一个同样长度的即

12、时码。 这说明，其他唯一可译码在码长方面并不比即时码占优。所以在讨论唯一可译码时，只需要讨论即时码就可以了。第四节 变长信源编码定理第22页，共78页，2022年，5月20日，1点23分，星期一设信源编码后的码字为：码长为：则这个码的平均长度为：平均每个码元携带的信息量即编码后的信息传输率为：若有一个唯一可译码，它的平均码长小于其他唯一可译码的长度，则称此码为紧致码或最佳码，无失真信源编码的基本问题就是寻找紧致码。第四节 变长信源编码定理第23页，共78页，2022年，5月20日，1点23分，星期一定理4.8 无失真变长信源编码定理（香农第一定理）离散无记忆信源S的N次扩展信源 ，其熵为 ，并

13、且编码器的码元符号集为A： 对信源 进行编码，总可以找到一种编码方法，构成单义可译码，使信源S中每个符号si所需要的平均码长满足 当 则得：第四节 变长信源编码定理第24页，共78页，2022年，5月20日，1点23分，星期一 这个定理是香农信息论中非常重要得一个定理，它指出，要做到无失真得信源编码，信源每个符号所需要的平均码元数就是信源的熵值，如果小于这个值，则唯一可译码不存在，可见，熵是无失真信源编码的极限值。定理还指出，通过对扩展信源进行编码，当N趋向于无穷时，平均码长可以趋进该极限值。 还可以证明，如果我们不确切知道信源的概率分布，我们用估计的概率分布去进行编码时，平均码长会加长，但是

14、如果估计的偏差不大的话，平均码长也不会增加太多（定理4.9的内容）。 第四节 变长信源编码定理第25页，共78页，2022年，5月20日，1点23分，星期一由得：就是编码后每个信源符号所携带的平均信息量第一定理可以表述如下：若 就存在唯一可译变长码，若 则不存在唯一可译变长码。第四节 变长信源编码定理定义：若从信道角度讲，信道的信息传输率因为：所以当平均码长达到极限值时，编码后信道的信息传输率为：第26页，共78页，2022年，5月20日，1点23分，星期一无噪信道编码定理 若信道的信息传输率R不大于信道容量C，总能对信源的输出进行适当的编码，使的在无噪无损信道上能无差错的以最大信息传输率C传

15、输信息，若R小于C，则无差错传输是不可能的。第四节 变长信源编码定理 编码效率：码的剩余度：在二元无噪无损信道中：在二元无噪无损信道中信息传输率：第27页，共78页，2022年，5月20日，1点23分，星期一例：其熵为：H(S)=0.811我们令s1=0，s2=1，这时平均码长 ，编码的效率为 。第四节 变长信源编码定理二次扩展信源进行编码：即时码s1s19/160s1s23/1610s2s13/16110s2s21/16111第28页，共78页，2022年，5月20日，1点23分，星期一第五节 香农编码设离散无记忆信源二进制香农码的编码步骤如下：将信源符号按概率从大到小的顺序排列，为方便起见

16、，令 p(x1) p(x2) p(xn)令p(x0)=0，用pa(xj)，j=i+1表示第i个码字的累加概率，则：确定满足下列不等式的整数ki ，并令ki为第i个码字的长度log2 p(xn)ki log2 p(xn)+1将pa(xj) 用二进制表示，并取小数点后ki 位作为符号xi的编码。第29页，共78页，2022年，5月20日，1点23分，星期一第五节 香农编码例 有一单符号离散无记忆信源对该信源编二进制香农码。其编码过程如下表所示。第30页，共78页，2022年，5月20日，1点23分，星期一第五节 香农编码计算出给定信源香农码的平均码长若对上述信源采用等长编码，要做到无失真译码，每个

17、符号至少要用3个比特表示。相比较，香农编码对信源进行了压缩。由离散无记忆信源熵定义，可计算出：对上述信源采用香农编码的信息率为编码效率为信源熵和信息率之比。则可以看出，编码效率并不是很高。第31页，共78页，2022年，5月20日，1点23分，星期一第六节 费诺编码费诺编码也是一种常见的信源编码方法。编码步骤如下：将概率按从大到小的顺序排列，令p(x1) p(x2) p(xn)按编码进制数将概率分组，使每组概率尽可能接近或相等。如编二进制码就分成两组，编m进制码就分成m组。给每一组分配一位码元。将每一分组再按同样原则划分，重复步骤2和3，直至概率不再可分为止。第32页，共78页，2022年，5

18、月20日，1点23分，星期一第六节 费诺编码例 设有一单符号离散信源对该信源编二进制费诺码。编码过程如下表。第33页，共78页，2022年，5月20日，1点23分，星期一第六节 费诺编码该信源的熵为平均码长为编码效率为本例中费诺编码有较高的编码效率。费诺码比较适合于每次分组概率都很接近的信源。特别是对每次分组概率都相等的信源进行编码时，可达到理想的编码效率。第34页，共78页，2022年，5月20日，1点23分，星期一第六节 费诺编码题中码字还可用码树来表示，如图所示。第35页，共78页，2022年，5月20日，1点23分，星期一第七节 霍夫曼编码 霍夫曼(Huffman)编码是一种效率比较高

19、的变长无失真信源编码方法。编码步骤二进制哈夫曼编码m进制哈夫曼编码第36页，共78页，2022年，5月20日，1点23分，星期一第七节 霍夫曼编码编码步骤将信源符号按概率从大到小的顺序排列，令p(x1) p(x2) p(xn)给两个概率最小的信源符号p(xn-1)和p(xn)各分配一个码位“0”和“1”，将这两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，结果得到一个只包含(n1)个信源符号的新信源。称为信源的第一次缩减信源，用S1表示。将缩减信源S1的符号仍按概率从大到小顺序排列，重复步骤2，得到只含(n2)个符号的缩减信源S2。重复上述步骤，直至缩减信源只剩两个符号

20、为止，此时所剩两个符号的概率之和必为1。然后从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字。第37页，共78页，2022年，5月20日，1点23分，星期一第七节 霍夫曼编码二进制哈夫曼编码例 设单符号离散无记忆信源如下，要求对信源编二进制 霍夫曼码。编码过程如下图（后页）。在图中读取码字的时候，一定要从后向前读，此时编出来的码字才是可分离的异前置码。若从前向后读取码字，则码字不可分离。第38页，共78页，2022年，5月20日，1点23分，星期一第七节 霍夫曼编码二进制哈夫曼编码第39页，共78页，2022年，5月20日，1点23分，星期一第七节 霍夫曼编码二进制哈夫

21、曼编码将上图左右颠倒过来重画一下，即可得到二进制哈夫曼码的码树。第40页，共78页，2022年，5月20日，1点23分，星期一信源熵为：平均码长为编码效率为若采用定长编码，码长K=3，则编码效率可见哈夫曼的编码效率提高了12.7%。第七节 霍夫曼编码二进制哈夫曼编码第41页，共78页，2022年，5月20日，1点23分，星期一第七节 霍夫曼编码二进制哈夫曼编码注意：哈夫曼的编法并不惟一。每次对缩减信源两个概率最小的符号分配“0”和“1”码元是任意的，所以可得到不同的码字。只要在各次缩减信源中保持码元分配的一致性，即能得到可分离码字。不同的码元分配，得到的具体码字不同，但码长ki不变，平均码长

22、也不变，所以没有本质区别；缩减信源时，若合并后的新符号概率与其他符号概率相等，从编码方法上来说，这几个符号的次序可任意排列，编出的码都是正确的，但得到的码字不相同。不同的编法得到的码字长度ki也不尽相同。第42页，共78页，2022年，5月20日，1点23分，星期一例：单符号离散无记忆信源 ，用两种不同的方法对其编二进制哈夫曼码。siliWi概率s1s2s3s4s512344101000001000110.40.20.20.10.1 0.4 0.2 0.2 0.2 0.4 0.4 0.2 0.6 0.4010101方法一：合并后的新符号排在其它相同概率符号的后面。第七节 霍夫曼编码二进制哈夫曼

23、编码第43页，共78页，2022年，5月20日，1点23分，星期一siliWi概率s1s2s3s4s512344101000001000110.40.20.20.10.1 0.4 0.2 0.2 0.2 0.4 0.4 0.2 0.6 0.4010101 这两种编码哪一种更好呢，我们来计算一下二者的码长。方法二：合并后的新符号排在其它相同概率符号的前面。第七节 霍夫曼编码二进制哈夫曼编码第44页，共78页，2022年，5月20日，1点23分，星期一两种编码的平均码长是一样的，都是2.2，那一种更好呢，我们可以计算一下平均码长的方差。定义码字长度的方差2：第七节 霍夫曼编码二进制哈夫曼编码第45

24、页，共78页，2022年，5月20日，1点23分，星期一第七节 霍夫曼编码二进制哈夫曼编码可见：第二种编码方法的码长方差要小许多。意味着第二种编码方法的码长变化较小，比较接近于平均码长。第一种方法编出的5个码字有4种不同的码长；第二种方法编出的码长只有两种不同的码长；显然，第二种编码方法更简单、更容易实现，所以更好。结论：在哈夫曼编码过程中，对缩减信源符号按概率由大到小的顺序重新排列时，应使合并后的新符号尽可能排在靠前的位置，这样可使合并后的新符号重复编码次数减少，使短码得到充分利用。第46页，共78页，2022年，5月20日，1点23分，星期一第七节 霍夫曼编码m进制哈夫曼编码“全树”概念定

25、义：码树图中每个中间节点后续的枝数为m时称为全树；若有些节点的后续枝数不足m，就称为非全树。二进制码不存在非全树的情况，因为后续枝数是一时，这个枝就可以去掉使码字长度缩短。对m进制编码：若所有码字构成全树，可分离的码字数（信源个数）必为 m+k(m1)。k为信源缩减次数。若信源所含的符号数n不能构成m进制全树，必须增加s个不用的码字形成全树。显然s0(i=1,2, ,n)信源符号的累积分布函数为： 所得累积分布函数为每台级的下界值，则其区间为0,1)左闭右开区间。 F (a1)=0 F (a2)=P (a1) F (a3)=P (a1)+P (a2) 当A=0,1二元信源时： F (0)= 0

26、，F (1)=P (0)第62页，共78页，2022年，5月20日，1点23分，星期一第八节 游程编码、算术编码、冗余编码算术编码计算二元无记忆信源序列的累积分布函数初始时：在0,1)区间内由F (1)划分成二个子区间0,F (1)和F (1),1)， F (1)= P (0)。子区间0,F (1)的宽度为A(0)= P (0)，对应于信源符号“0”；子区间F (1),1)的宽度为A(1)= P (1)，对应于信源符号“1”；若输入符号序列的第一个符号为s=“0”，落入0,F (1)区间，得累积分布函数F (s=“0”)= F (0)=0； 第63页，共78页，2022年，5月20日，1点23

27、分，星期一第八节 游程编码、算术编码、冗余编码算术编码输入第二个符号为“1”，s=“01”s=“01”所对应的区间是在区间0,F (1)中进行分割；符号序列“00”对应的区间宽度为: A(00)=A(0)P (0)=P (0)P (0)=P (00)；对应的区间为0,F (s=“01”)。符号序列“01”对应的区间宽度为 A(01)=A(0)P (1)=P (0)P (1)=P (01)= A(0)A(00)；对应的区间为F (s=“01”),F (1)。累积分布函数F (s=“01”)=P (00)= P (0)P (0)第64页，共78页，2022年，5月20日，1点23分，星期一第八节

28、游程编码、算术编码、冗余编码算术编码第65页，共78页，2022年，5月20日，1点23分，星期一第八节 游程编码、算术编码、冗余编码算术编码 输入第三个符号为“1”：输入序列可记做s1=“011”（若第三个符号输入为“0”，可记做s0=“010”）；现在，输入序列s1=“011”对应的区间是对区间F(s),F(1)进行分割；序列s0=“010”对应的区间宽度为 A(s=“010”)=A(s=“01”)P(0)=A(s)P(0) 其对应的区间为F(s), F(s)+ A(s)P(0)；序列s1=“011”对应的区间宽度为 A(s=“011”)=A(s)P(1)=A(s=“01”)A(s=“01

29、0”)= A(s )A(s0) 其对应的区间为F(s)+A(s)P(0),F(1)；符号序列s1=“011”的累积分布函数为F(s1)=F(s)+A(s)P(0)；若第三个符号输入为“0”，符号序列s0=“010”的区间下界值仍为F(s)，得符号序列s0=“010”的累积分布函数为F(s0)=F(s)。第66页，共78页，2022年，5月20日，1点23分，星期一第八节 游程编码、算术编码、冗余编码算术编码归纳当已知前面输入符号序列为s，若接着再输入一个符号“0”，序列s0的累积分布函数为： F(s0)=F(s)对应区间宽度为： A(s0)=A(s)P(0)若接着输入的一个符号是“1”，序列的

30、累积分布函数为：F(s1)=F(s)+A(s)P(0)对应区间宽度为： A(s1)=A(s)P(1)=A(s)A(s0)第67页，共78页，2022年，5月20日，1点23分，星期一第八节 游程编码、算术编码、冗余编码算术编码符号序列对应的区间宽度A(s=“0”)=P(0)A(s=“1”)=1A(s=“0”)=P(1)A(s=“00”)=P(00)=A(0)P(0)=P(0)P(0)A(s=“01”)=A(s=“0”)A(s=“00”)=P(01)=A(0)P(1)=P(0)P(1)A(s=“10”)=P(10)=A(1)P(0)=P(1)P(0)A(s=“11”)=A(s=“1”)A(s=“

31、10”)=P(11)= A(s=“1”)P(1)=P(1)P(1)A(s=“010”)=A(s=“01”)P(0)=P(01)P(0)P(010)A(s=“011”)=A(s=“01”)-A(s=“010”)=A(s=“01”)P(1)=P(01)P(1)=P(011) 信源符号序列s所对应区间的宽度等于符号序列s的概率P(s)。第68页，共78页，2022年，5月20日，1点23分，星期一第八节 游程编码、算术编码、冗余编码算术编码二元信源符号序列的累积分布函数的递推公式F(sr)=F(s)+P(s)F(r) (r=0,1) sr表示已知前面信源符号序列为s，接着再输入符号为rF(0)=0，

32、 F(1)=P(0)F(s0)=F(s)F(s1)=F(s)+P(s)F(1)= F(s)+P(s)P(0)A(sr)=P(sr)=P(s)P(r) (r=0,1) A(s0)=P(s0)=P(s)P(0) A(s1)=P(s1)=P(s)P(1)第69页，共78页，2022年，5月20日，1点23分，星期一第八节 游程编码、算术编码、冗余编码算术编码举例：已输入二元符号序列为s=“011”，接着再输入符号为“1”，得序列累积分布函数为： F(s1)=F(0111)=F(s=“011”)+P(011)P(0) =F(s=“01”)+P(01)P(0)+P(011)P(0) =F(s=“0”)+

33、P(0)P(0) +P(01)P(0)+P(011)P(0) =0+P(00)+P(010)+P(0110) 对应的区间宽度为 A(s1)=P(s=“011”)P(1)=P(011)P(1)=P(0111)上述整个分析过程可用图5.6.1描述式(5.6.1)和(5.6.2)是可递推运算，在实际中，只需两个存储器，把P(s)和F(s)存下来，然后，根据输入符号和式(5.6.1)、(5.6.2)更新两个存储器中的数值。因此在编码过程中，每输入一个符号要进行乘法和加法运算，所以称为算术编码。第70页，共78页，2022年，5月20日，1点23分，星期一第八节 游程编码、算术编码、冗余编码算术编码第71页，共78页，2022年，5月20日，1点23分，星期一第八节 游程编码、算术编码、冗余编码算术编码 通过关于信源符号序列的累积分布函数的计算，把区间分割成许多小区间，不同的信源符号序列对应不同的区间为F(s),F(s)+P(s) 。可取小区间内的一点来代表这序列。编码方法：将符号序列的累积分布函数写成二进位的小数，取小数点后k位，若后面有尾数，就进位到第k位，这样得到的一个数C，并使k满足举例第72页，共78页，2022年，5月20日，1点23分，星期一第八节 游程编码、算术编码、冗余编码算术编码编码效率这样选取的数值C，一般根据二进小数