无失真的信源编码

《无失真的信源编码》由会员分享，可在线阅读，更多相关《无失真的信源编码（50页珍藏版）》请在金锄头文库上搜索。

1、第八章第八章 无失真的信源编码无失真的信源编码 8.1 霍夫曼（霍夫曼（Huffman）码）码8.2 费诺费诺(Fano)码码8.3 香农香农-费诺费诺-埃得斯码埃得斯码8.4 游程编码和游程编码和MH编码编码8.6 字典码字典码8.5 算术编码算术编码8.1 霍夫曼（霍夫曼（Huffman）码）码n设离散无记忆信源n二进制香农码的编码步骤如下：n将信源符号按概率从大到小的顺序排列，为方便起见，令 p(x1) p(x2) p(xn)n令p(x0)=0，用pa(xj)，j=i+1表示第i个码字的累加概率，则：n确定满足下列不等式的整数ki ，并令ki为第i个码字的长度nlog2 p(xn)ki

2、log2 p(xn)+1n将pa(xj) 用二进制表示，并取小数点后ki 位作为符号xi的编码。例 有一单符号离散无记忆信源对该信源编二进制香农码。其编码过程如下表所示。8.1 霍夫曼（霍夫曼（Huffman）码）码n计算出给定信源香农码的平均码长n若对上述信源采用等长编码，要做到无失真译码，每个符号至少要用3个比特表示。相比较，香农编码对信源进行了压缩。n由离散无记忆信源熵定义，可计算出：n对上述信源采用香农编码的信息率为n编码效率为信源熵和信息率之比。则n可以看出，编码效率并不是很高。8.1 霍夫曼（霍夫曼（Huffman）码）码第六节第六节 费诺编码费诺编码费诺编码也是一种常见的信源编码

3、方法。编码步骤如下：将概率按从大到小的顺序排列，令p(x1) p(x2) p(xn)按编码进制数将概率分组，使每组概率尽可能接近或相等。如编二进制码就分成两组，编m进制码就分成m组。给每一组分配一位码元。将每一分组再按同样原则划分，重复步骤2和3，直至概率不再可分为止。第六节第六节 费诺编码费诺编码例 设有一单符号离散信源对该信源编二进制费诺码。编码过程如下表。第六节第六节 费诺编码费诺编码该信源的熵为平均码长为编码效率为本例中费诺编码有较高的编码效率。费诺码比较适合于每次分组概率都很接近的信源。特别是对每次分组概率都相等的信源进行编码时，可达到理想的编码效率。第六节第六节 费诺编码费诺编码题

4、中码字还可用码树来表示，如图所示。第七节第七节 霍夫曼编码霍夫曼编码 霍夫曼(Huffman)编码是一种效率比较高的变长无失真信源编码方法。编码步骤二进制哈夫曼编码m进制哈夫曼编码第七节第七节 霍夫曼编码霍夫曼编码编码步骤将信源符号按概率从大到小的顺序排列，令p(x1) p(x2) p(xn)给两个概率最小的信源符号p(xn-1)和p(xn)各分配一个码位“0”和“1”，将这两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，结果得到一个只包含(n1)个信源符号的新信源。称为信源的第一次缩减信源，用S1表示。将缩减信源S1的符号仍按概率从大到小顺序排列，重复步骤2，得到只含

5、(n2)个符号的缩减信源S2。重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符号的概率之和必为1。然后从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字。第七节第七节 霍夫曼编码霍夫曼编码二进制哈夫曼编码例 设单符号离散无记忆信源如下，要求对信源编二进制 霍夫曼码。编码过程如下图（后页）。n在图中读取码字的时候，一定要从后向前读，此时编出来的码字才是可分离的异前置码。若从前向后读取码字，则码字不可分离。第七节第七节 霍夫曼编码霍夫曼编码二进制哈夫曼编码第七节第七节 霍夫曼编码霍夫曼编码二进制哈夫曼编码将上图左右颠倒过来重画一下，即可得到二进制哈夫曼码的码树。信源

6、熵为：平均码长为编码效率为若采用定长编码，码长K=3，则编码效率可见哈夫曼的编码效率提高了12.7%。第七节第七节 霍夫曼编码霍夫曼编码二进制哈夫曼编码第七节第七节 霍夫曼编码霍夫曼编码二进制哈夫曼编码注意：哈夫曼的哈夫曼的编法并不惟一法并不惟一。每次对缩减信源两个概率最小的符号分配“0”和“1”码元是任意的，所以可得到不同的码字。只要在各次缩减信源中保持码元分配的一致性，即能得到可分离码字。不同的码元分配，得到的具体码字不同，但码长ki不变，平均码长 也不变，所以没有本质区别；缩减信源时，若合并后的新符号概率与其他符号概率相等，从编码方法上来说，这几个符号的次序可任意排列，编出的码都是正确的

7、，但得到的码字不相同。不同的编法得到的码字长度ki也不尽相同。例：单符号离散无记忆信源 ，用两种不同的方法对其编二进制哈夫曼码。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方法一：合并后的新符号排在其它相同概率符号的后面。第七节第七节 霍夫曼编码霍夫曼编码二进制哈夫曼编码siliWi概率s1s2s3s4s512344101000001000110.40.20.20.10.1 0.4 0.2 0.2 0.2 0.4 0.4 0.2 0.6 0.40101

8、01 这两种编码哪一种更好呢，我们来计算一下二者的码长。方法二：合并后的新符号排在其它相同概率符号的前面。第七节第七节 霍夫曼编码霍夫曼编码二进制哈夫曼编码两种编码的平均码长是一样的，都是2.2，那一种更好呢，我们可以计算一下平均码长的方差。定义码字长度的方差2：第七节第七节 霍夫曼编码霍夫曼编码二进制哈夫曼编码第七节第七节 霍夫曼编码霍夫曼编码二进制哈夫曼编码n可见：第二种编码方法的码长方差要小许多。意味着第二种编码方法的码长变化较小，比较接近于平均码长。l第一种方法编出的5个码字有4种不同的码长；l第二种方法编出的码长只有两种不同的码长；l显然，第二种编码方法更简单、更容易实现，所以更好。

9、结论结论：在哈夫曼编码过程中，对缩减信源符号按概率由大到小的顺序重新排列时，应使合并后的新符号尽可能排在靠前的位置，这样可使合并后的新符号重复编码次数减少，使短码得到充分利用。第七节第七节 霍夫曼编码霍夫曼编码m进制哈夫曼编码“全树”概念定义：码树图中每个中间节点后续的枝数为m时称为全树；若有些节点的后续枝数不足m，就称为非全树。二进制码不存在非全树的情况，因为后续枝数是一时，这个枝就可以去掉使码字长度缩短。对m进制编码：若所有码字构成全树，可分离的码字数（信源个数）必为 m+k(m1)。k为信源缩减次数。若信源所含的符号数n不能构成m进制全树，必须增加s个不用的码字形成全树。显然s0(i=1

10、,2, ,n)n信源符号的累积分布函数为： 所得累积分布函数为每台级的下界值，则其区间为0,1)左闭右开区间。 F (a1)=0 F (a2)=P (a1) F (a3)=P (a1)+P (a2) n当A=0,1二元信源二元信源时： F (0)= 0，F (1)=P (0)第八节第八节 游程编码、算术编码、冗余编码游程编码、算术编码、冗余编码算算术术编编码码n计算二元无记忆信源序列二元无记忆信源序列的累积分布函数n初始时：在0,1)区间内由F (1)划分成二个子区间0,F (1)和F (1),1)， F (1)= P (0)。n子区间0,F (1)的宽度为A(0)= P (0)，对应于信源符

11、号“0”；n子区间F (1),1)的宽度为A(1)= P (1)，对应于信源符号“1”；n若输入符号序列的第一个符号为s=“0”，落入0,F (1)区间，得累积分布函数F (s=“0”)= F (0)=0； 第八节第八节 游程编码、算术编码、冗余编码游程编码、算术编码、冗余编码算算术术编编码码n输入第二个符号为“1”，s=“01”ns=“01”所对应的区间是在区间0,F (1)中进行分割；n符号序列“00”对应的区间宽度为: A(00)=A(0)P (0)=P (0)P (0)=P (00)；n对应的区间为0,F (s=“01”)。n符号序列“01”对应的区间宽度为 A(01)=A(0)P (

12、1)=P (0)P (1)=P (01)= A(0)A(00)；n对应的区间为F (s=“01”),F (1)。n累积分布函数F (s=“01”)=P (00)= P (0)P (0)第八节第八节 游程编码、算术编码、冗余编码游程编码、算术编码、冗余编码算算术术编编码码第八节第八节 游程编码、算术编码、冗余编码游程编码、算术编码、冗余编码算算术术编编码码 输入第三个符号为“1”：n输入序列可记做s1=“011”（若第三个符号输入为“0”，可记做s0=“010”）；n现在，输入序列s1=“011”对应的区间是对区间F(s),F(1)进行分割；n序列s0=“010”对应的区间宽度为 A(s=“01

13、0”)=A(s=“01”)P(0)=A(s)P(0) 其对应的区间为F(s), F(s)+ A(s)P(0)；n序列s1=“011”对应的区间宽度为 A(s=“011”)=A(s)P(1)=A(s=“01”)A(s=“010”)= A(s )A(s0) 其对应的区间为F(s)+A(s)P(0),F(1)；n符号序列s1=“011”的累积分布函数为F(s1)=F(s)+A(s)P(0)；n若第三个符号输入为“0”，符号序列s0=“010”的区间下界值仍为F(s)，得符号序列s0=“010”的累积分布函数为F(s0)=F(s)。第八节第八节 游程编码、算术编码、冗余编码游程编码、算术编码、冗余编码

14、算算术术编编码码n归纳n当已知前面输入符号序列为s，若接着再输入一个符号“0”，序列s0的累积分布函数为： F(s0)=F(s)n对应区间宽度为： A(s0)=A(s)P(0)n若接着输入的一个符号是“1”，序列的累积分布函数为：F(s1)=F(s)+A(s)P(0)n对应区间宽度为： A(s1)=A(s)P(1)=A(s)A(s0)第八节第八节 游程编码、算术编码、冗余编码游程编码、算术编码、冗余编码算算术术编编码码n符号序列对应的区间宽度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”

15、)=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=“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)。第八节第八节 游程编码、

16、算术编码、冗余编码游程编码、算术编码、冗余编码算算术术编编码码n二元信源符号序列的累积分布函数的递推公式nF(sr)=F(s)+P(s)F(r) (r=0,1) nsr表示已知前面信源符号序列为s，接着再输入符号为rF(0)=0， F(1)=P(0)F(s0)=F(s)F(s1)=F(s)+P(s)F(1)= F(s)+P(s)P(0)nA(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)第八节第八节 游程编码、算术编码、冗余编码游程编码、算术编码、冗余编码算算术术编编码码n举例：已输入二元符号序列为s=“

17、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”)+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)n上述整个分析过程可用图5.6.1描述n式(5.6.1)和(5.6.2)是可递推运算，在实际中，只需两个存储器，把P(s)和F(s)存下来，然后，根据输入符号和式(5.6.1)、(

18、5.6.2)更新两个存储器中的数值。因此在编码过程中，每输入一个符号要进行乘法和加法运算，所以称为算术编码算术编码。第八节第八节 游程编码、算术编码、冗余编码游程编码、算术编码、冗余编码算算术术编编码码第八节第八节 游程编码、算术编码、冗余编码游程编码、算术编码、冗余编码算算术术编编码码 通过关于信源符号序列的累积分布函数的计算，把区间分割成许多小区间，不同的信源符号序列对应不同的区间为F(s),F(s)+P(s) 。可取小区间内的一点来代表这序列。n编码方法：将符号序列的累积分布函数写成二进位的小数，取小数点后k位，若后面有尾数，就进位到第k位，这样得到的一个数C，并使k满足n举例第八节第八

19、节 游程编码、算术编码、冗余编码游程编码、算术编码、冗余编码算算术术编编码码n编码效率n这样选取的数值C，一般根据二进小数截去尾数的影响得 CF(s)Cn而P(s)1/2kn信源符号序列对应区间的上界为 F(s)+P(s)F(s)+1/2kCn可见，数值在区间F(s),F(s)+P(s)内。而信源符号序列对应的不同区间（左封右开）是不重叠的，所以编得的码是即时码。第八节第八节 游程编码、算术编码、冗余编码游程编码、算术编码、冗余编码算算术术编编码码n算术编码的编码效率很高。当信源符号序列很长时，L很大时，平均码长接近信源的熵。第八节第八节 游程编码、算术编码、冗余编码游程编码、算术编码、冗余编

20、码算算术术编编码码译码就是一系列比较过程，每一步比较CF (s)与(s)P (0)。 F (s0)=F (s) F (s1)=F (s)+P (s)P (0)ns为前面已译出的序列串；nP (s)是序列串s对应的宽度；nF (s)是序列串s的累积分布函数，即为s对应区间的下界；nP (s)P (0)是此区间内下一个输入为符号“0”所占的子区间宽度；n若CF (s)P (s)P (0)则译输出符号为“1”。第八节第八节 游程编码、算术编码、冗余编码游程编码、算术编码、冗余编码算算术术编编码码例：设二元无记忆信源S=0,1，其P (0)=1/4，P (1)=3/4。对二元序 列11111100做算

21、术编码。解：P (s=11111100)=P 2(0)P 6(1)=(3/4)6(1/4)2F (sr)=F (s)+P (s)F (r)F (s0)=F (s) F (s1)=F (s)+P (s)F (1)= F (s)+P (s)P (0)F (s)=P (0)+P (1)P (0)+P (1)2P (0)+P (1)3P(0)+P (1)4P (0)+P (1)5P (0) =0.82202=0.110100100111得C0.1101010 得s的码字为1101010。编码效率 第八节第八节 游程编码、算术编码、冗余编码游程编码、算术编码、冗余编码n我们学习了6种信源编码：香农编码香农编码、费诺编码费诺编码、哈夫哈夫曼编码曼编码、游程编码游程编码、算术编码算术编码。n游程编码和算术编码是非分组编码；n游程编码是限失真信源编码。n本章介绍的都是离散信源变长编码。n优点优点：提高编码效率；n缺点缺点：需要大量缓冲设备来存储这些变长码，然后再以恒定的码率进行传送；在传输的过程中如果出现了误码，容易引起错误扩散，所以要求有优质的信道。n有时为了得到较高的编码效率，先采用某种正交变换，解除或减弱信源符号间的相关性，然后再进行信源编码；有时则利用信源符号间的相关性直接编码。信信源源编编码码总总结结