第五章信源编码总结与习题

信源编码：以提高通信有效性为目的的编码。通常通过压缩信源的冗余度来实现。采用的一般方法是压缩每个信源符号的平均比特数或信源的码率。即同样多的信息用较少的码率传送，使单位时间内传送的平均信息量增加，从而提高通信的有效性。信道编码：是以提高信息传输的可靠性为目的的编码。通常通过增加信源的冗余度来实现。采用的一般方法是增大码率/带宽。与信源编码正好相反。密码：是以提高通信系统的安全性为目的的编码。通常通过加密和解密来实现。从信息论的观点出发，“加密”可视为增熵的过程，“解密”可视为减熵的过程。第五章总结1/31/20231香农编码设离散无记忆信源二进制香农码的编码步骤如下：将信源符号按概率从大到小的顺序排列，为方便起见，令p(x1)≥p(x2)≥…≥p(xn)令p(x0)=0，用pa(xj)，j=i+1表示第i个码字的累加概率，则1/31/20232香农编码确定满足下列不等式的整数ki

，并令ki为第i个码字的长度－log2

p(xi)≤ki<1－log2

p(xi)将pa(xj)用二进制表示，并取小数点后ki

位作为符号xi的编码。1/31/20233费诺编码费诺编码也是一种常见的信源编码方法。编码步骤如下：将概率按从大到小的顺序排列，令p(x1)≥p(x2)≥…≥p(xn)按编码进制数将概率分组，使每组概率尽可能接近或相等。如编二进制码就分成两组，编m进制码就分成m组。给每一组分配一位码元。将每一分组再按同样原则划分，重复步骤2和3，直至概率不再可分为止。1/31/20234将信源符号按概率从大到小的顺序排列，令p(x1)≥p(x2)≥…≥p(xn)给两个概率最小的信源符号p(xn-1)和p(xn)各分配一个码位“0”和“1”，将这两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，结果得到一个只包含(n－1)个信源符号的新信源。称为信源的第一次缩减信源，用S1表示。将缩减信源S1的符号仍按概率从大到小顺序排列，重复步骤2，得到只含(n－2)个符号的缩减信源S2。重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符号的概率之和必为1。然后从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字。二元哈夫曼编码1/31/20235在编m进制哈夫曼码时为了使平均码长最短，必须使最后一步缩减信源有m个信源符号。非全树时，有s个码字不用：第一次对最小概率符号分配码元时就只取(m－s)个，分别配以0,1,…,m－s－1，把这些符号的概率相加作为一个新符号的概率，与其它符号一起重新排列。以后每次就可以取m个符号，分别配以0,1,…,m－1；…；如此下去，直至所有概率相加得1为止，即得到各符号的m进制码字。M元哈夫曼编码1/31/20236香农码、费诺码、哈夫曼码都考虑了信源的统计特性，使经常出现的信源符号对应较短的码字，使信源的平均码长缩短，从而实现了对信源的压缩；香农码有系统的、惟一的编码方法，但在很多情况下编码效率不是很高；费诺码和哈夫曼码的编码方法都不惟一；费诺码比较适合于对分组概率相等或接近的信源编码，费诺码也可以编m进制码，但m越大，信源的符号数越多，可能的编码方案就越多，编码过程就越复杂，有时短码未必能得到充分利用；哈夫曼码对信源的统计特性没有特殊要求，编码效率比较高，对编码设备的要求也比较简单，因此综合性能优于香农码和费诺码。1/31/20237适合有记忆信源游程变换减弱了原序列符号间的相关性。游程变换将二元序列变换成了多元序列；这样就适合于用其他方法，如哈夫曼编码，进一步压缩信源，提高通信效率。编码方法：首先测定“0”游程长度和“1”游程长度的概率分布，即以游程长度为元素，构造一个新的信源；对新的信源（游程序列）进行哈夫曼编码。多元序列也可以变换成游程序列，如m元序列可有m种游程。但是变换成游程序列时，需要增加标志位才能区分游程序列中的“长度”是m种游程中的哪一个的长度，否则，变换就不可逆。这样，增加的标志位可能会抵消压缩编码得到的好处。所以，对多元序列进行游程变换的意义不大。二元游程编码1/31/20238通过关于信源符号序列的累积分布函数的计算，把区间分割成许多小区间，不同的信源符号序列对应不同的区间为[F(s),F(s)+P(s))。可取小区间内的一点来代表这序列。编码方法：将符号序列的累积分布函数写成二进位的小数，取小数点后k位，若后面有尾数，就进位到第k位，这样得到的一个数C，并使k满足举例算术编码1/31/20239译码就是一系列比较过程，每一步比较C－F(s)与P(s)P(0)。

F(s0)=F(s)F(s1)=F(s)+P(s)P(0)s为前面已译出的序列串；P(s)是序列串s对应的宽度；F(s)是序列串s的累积分布函数，即为s对应区间的下界；P(s)P(0)是此区间内下一个输入为符号“0”所占的子区间宽度；若C－F(s)<P(s)P(0)则译输出符号为“0”；若C－F(s)>P(s)P(0)则译输出符号为“1”。算术编码译码1/31/202310L－D编码方法是一种分帧传送的方式；编码方法在冗余位序列中取N个符号作为一帧，编成一个码字，码字中含有信息位的数量和位置信息，在接收端依据这些信息进行译码；每个码字传送两个数：Q和T，由下式计算L-D编码1/31/202311Q的位数：T的位数：总位数：L-D编码1/31/202312寻找某一值K若再找某一值LL-D译码1/31/202313Lempel-Ziv算法独立于信源的统计特性，是一种变长到定长的编码方案。任何信源输出序列能唯一分解为可变长度的码组，这些码组是用等长的码字进行编码的。Lempel-Ziv算法及其各种变形使用消息自身迭代性地构造一个变长码字的分析序列，这些不同长度的码字构成一个码字典，编码过程就是在码字典中寻找与编码序列中下一段码相匹配的码。当找到匹配时，编码按照以下思路进行：

(1)如果因为接收器已存有这个码段，因此那么无需重发，只需要辨认地址以重新取回该码段；LZ编码1/31/202314

(2)如果没有找到匹配码段，则根据码段序列的参考位置，向序列添加下一个码元，以构造码字典的新码字。(3)编码开始时，使用一个空码字典，所以第一个码字是与先前码字无关的。(4)在一种码字典结构中，递归地形成地址的游程序列和该地址上的字符段。编码后的码字总是由两部分组成：字典地址和本码段需要添加的消息。由此可见，Lempel-Ziv编码方法充分利用了已编码消息的信息。LZ编码1/31/202315本章介绍的都是离散信源变长编码。优点：提高编码效率；缺点：需要大量缓冲设备来存储这些变长码，然后再以恒定的码率进行传送；在传输的过程中如果出现了误码，容易引起错误扩散，所以要求有优质的信道。有时为了得到较高的编码效率，先采用某种正交变换，解除或减弱信源符号间的相关性，然后再进行信源编码；有时则利用信源符号间的相关性直接编码。编码总结1/31/202316习题11/31/2023171/31/202318习题21/31/202319习题31/31/2023201/31/202321m=3,取k=2,因为m+k*(m-1)=3+2*2=7,所以一开始可取3个概率最小的符号:可以用建立Huffman树的方法1/31/2023221/31/202323习题41/31/2023241/31/2023251/31/2023261/31/2023271/31/202328习题51/31/202329习题51/31/2023301/31/2023311/31/2023321/31/2023331/31/2023341/31/202335习题65.6有二元平稳马氏链，已知，，求它的符号熵。用三个符号合成一个来编二进制哈夫曼码，求新符号的平均码字长度和编码效率。

提示:只考虑二元一阶平稳马氏链,状态图01再利用全概率公式和归1性求p(0)和p(1),然后求出熵H(X).1/31/202336第三步,求出扩展信源的分布:第四步,求出Huffman编码,再求编码效率.1/31/202337习题75.7对题5.6的信源进行游程编码。若“0”游程长度的截止值为16，“1”游程长度的截止值为8，求编码效率。提示:用P143最后一行求出“0”游程长度的概率分布、用P144第一行求出“1”游程长度的概率分布，以及相应的熵；然后求如下信源（换为游程）的Huffman编码：利用P145公式(5.1.24)求编码效率。1/31/202338习题85.8选择帧长=63(1)对001000000000000000000000000000000100000000000000000000000000000编L-D码；(2)对100001000010110000000001001000010100100000000111000001000000001编L-D码，再译码；(3)对0000000000000000