无失真的信源编码

无失真的信源编码第一页，共五十页，编辑于2023年，星期三8.1霍夫曼（Huffman）码设离散无记忆信源二进制香农码的编码步骤如下：将信源符号按概率从大到小的顺序排列，为方便起见，令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的编码。第二页，共五十页，编辑于2023年，星期三例有一单符号离散无记忆信源对该信源编二进制香农码。其编码过程如下表所示。8.1霍夫曼（Huffman）码第三页，共五十页，编辑于2023年，星期三计算出给定信源香农码的平均码长若对上述信源采用等长编码，要做到无失真译码，每个符号至少要用3个比特表示。相比较，香农编码对信源进行了压缩。由离散无记忆信源熵定义，可计算出：对上述信源采用香农编码的信息率为编码效率为信源熵和信息率之比。则可以看出，编码效率并不是很高。8.1霍夫曼（Huffman）码第四页，共五十页，编辑于2023年，星期三第六节费诺编码费诺编码也是一种常见的信源编码方法。编码步骤如下：将概率按从大到小的顺序排列，令p(x1)≥p(x2)≥…≥p(xn)按编码进制数将概率分组，使每组概率尽可能接近或相等。如编二进制码就分成两组，编m进制码就分成m组。给每一组分配一位码元。将每一分组再按同样原则划分，重复步骤2和3，直至概率不再可分为止。第五页，共五十页，编辑于2023年，星期三第六节费诺编码例设有一单符号离散信源对该信源编二进制费诺码。编码过程如下表。第六页，共五十页，编辑于2023年，星期三第六节费诺编码该信源的熵为平均码长为编码效率为本例中费诺编码有较高的编码效率。费诺码比较适合于每次分组概率都很接近的信源。特别是对每次分组概率都相等的信源进行编码时，可达到理想的编码效率。第七页，共五十页，编辑于2023年，星期三第六节费诺编码题中码字还可用码树来表示，如图所示。第八页，共五十页，编辑于2023年，星期三第七节霍夫曼编码

霍夫曼(Huffman)编码是一种效率比较高的变长无失真信源编码方法。编码步骤二进制哈夫曼编码m进制哈夫曼编码第九页，共五十页，编辑于2023年，星期三第七节霍夫曼编码——编码步骤将信源符号按概率从大到小的顺序排列，令p(x1)≥p(x2)≥…≥p(xn)给两个概率最小的信源符号p(xn-1)和p(xn)各分配一个码位“0”和“1”，将这两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，结果得到一个只包含(n－1)个信源符号的新信源。称为信源的第一次缩减信源，用S1表示。将缩减信源S1的符号仍按概率从大到小顺序排列，重复步骤2，得到只含(n－2)个符号的缩减信源S2。重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符号的概率之和必为1。然后从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字。第十页，共五十页，编辑于2023年，星期三第七节霍夫曼编码——二进制哈夫曼编码例设单符号离散无记忆信源如下，要求对信源编二进制霍夫曼码。编码过程如下图（后页）。在图中读取码字的时候，一定要从后向前读，此时编出来的码字才是可分离的异前置码。若从前向后读取码字，则码字不可分离。第十一页，共五十页，编辑于2023年，星期三第七节霍夫曼编码——二进制哈夫曼编码第十二页，共五十页，编辑于2023年，星期三第七节霍夫曼编码——二进制哈夫曼编码将上图左右颠倒过来重画一下，即可得到二进制哈夫曼码的码树。第十三页，共五十页，编辑于2023年，星期三信源熵为：平均码长为编码效率为若采用定长编码，码长K=3，则编码效率可见哈夫曼的编码效率提高了12.7%。第七节霍夫曼编码——二进制哈夫曼编码第十四页，共五十页，编辑于2023年，星期三第七节霍夫曼编码——二进制哈夫曼编码注意：哈夫曼的编法并不惟一。每次对缩减信源两个概率最小的符号分配“0”和“1”码元是任意的，所以可得到不同的码字。只要在各次缩减信源中保持码元分配的一致性，即能得到可分离码字。不同的码元分配，得到的具体码字不同，但码长ki不变，平均码长也不变，所以没有本质区别；缩减信源时，若合并后的新符号概率与其他符号概率相等，从编码方法上来说，这几个符号的次序可任意排列，编出的码都是正确的，但得到的码字不相同。不同的编法得到的码字长度ki也不尽相同。第十五页，共五十页，编辑于2023年，星期三例：单符号离散无记忆信源，用两种不同的方法对其编二进制哈夫曼码。siliWi概率s1s2s3s4s512344101000001000110.40.20.20.10.10.40.20.20.20.40.40.20.60.4010101方法一：合并后的新符号排在其它相同概率符号的后面。第七节霍夫曼编码——二进制哈夫曼编码第十六页，共五十页，编辑于2023年，星期三siliWi概率s1s2s3s4s512344101000001000110.40.20.20.10.10.40.20.20.20.40.40.20.60.4010101

这两种编码哪一种更好呢，我们来计算一下二者的码长。方法二：合并后的新符号排在其它相同概率符号的前面。第七节霍夫曼编码——二进制哈夫曼编码第十七页，共五十页，编辑于2023年，星期三两种编码的平均码长是一样的，都是2.2，那一种更好呢，我们可以计算一下平均码长的方差。定义码字长度的方差σ2：第七节霍夫曼编码——二进制哈夫曼编码第十八页，共五十页，编辑于2023年，星期三第七节霍夫曼编码——二进制哈夫曼编码可见：第二种编码方法的码长方差要小许多。意味着第二种编码方法的码长变化较小，比较接近于平均码长。第一种方法编出的5个码字有4种不同的码长；第二种方法编出的码长只有两种不同的码长；显然，第二种编码方法更简单、更容易实现，所以更好。结论：在哈夫曼编码过程中，对缩减信源符号按概率由大到小的顺序重新排列时，应使合并后的新符号尽可能排在靠前的位置，这样可使合并后的新符号重复编码次数减少，使短码得到充分利用。第十九页，共五十页，编辑于2023年，星期三第七节霍夫曼编码——m进制哈夫曼编码“全树”概念定义：码树图中每个中间节点后续的枝数为m时称为全树；若有些节点的后续枝数不足m，就称为非全树。二进制码不存在非全树的情况，因为后续枝数是一时，这个枝就可以去掉使码字长度缩短。对m进制编码：若所有码字构成全树，可分离的码字数（信源个数）必为m+k(m－1)。k为信源缩减次数。若信源所含的符号数n不能构成m进制全树，必须增加s个不用的码字形成全树。显然s<m－1，若s=m－1，意味着某个中间节点之后只有一个分枝，为了节约码长，这一分枝可以省略。第二十页，共五十页，编辑于2023年，星期三第七节霍夫曼编码——m进制哈夫曼编码在编m进制哈夫曼码时为了使平均码长最短，必须使最后一步缩减信源有m个信源符号。非全树时，有s个码字不用：第一次对最小概率符号分配码元时就只取(m－s)个，分别配以0,1,…,m－s－1，把这些符号的概率相加作为一个新符号的概率，与其它符号一起重新排列。以后每次就可以取m个符号，分别配以0,1,…,m－1；…；如此下去，直至所有概率相加得1为止，即得到各符号的m进制码字。第二十一页，共五十页，编辑于2023年，星期三第七节霍夫曼编码——m进制哈夫曼编码例：对如下单符号离散无记忆信源(例5.4.1)编三进制哈夫曼码。这里：m=3，n=8令k=3，m+k(m－1)=9，则s=9－n=9－8=1所以第一次取m－s=2个符号进行编码。第二十二页，共五十页，编辑于2023年，星期三第七节霍夫曼编码——m进制哈夫曼编码第二十三页，共五十页，编辑于2023年，星期三第七节霍夫曼编码——m进制哈夫曼编码平均码长为：信息率为：编码效率为：可见：哈夫曼的编码效率相当高，对编码器的要求也简单得多。第二十四页，共五十页，编辑于2023年，星期三一些结论香农码、费诺码、哈夫曼码都考虑了信源的统计特性，使经常出现的信源符号对应较短的码字，使信源的平均码长缩短，从而实现了对信源的压缩；香农码有系统的、惟一的编码方法，但在很多情况下编码效率不是很高；费诺码和哈夫曼码的编码方法都不惟一；费诺码比较适合于对分组概率相等或接近的信源编码；哈夫曼码对信源的统计特性没有特殊要求，编码效率比较高，对编码设备的要求也比较简单，因此综合性能优于香农码和费诺码。第二十五页，共五十页，编辑于2023年，星期三第八节游程编码、算术编码香农编码、费诺编码、哈夫曼编码主要是针对无记忆信源。当信源有记忆时上述编码效率不高；游程编码对相关信源编码更有效；香农编码、费诺编码、哈夫曼编码属于无失真信源编码；游程编码属于限失真信源编码。第二十六页，共五十页，编辑于2023年，星期三第八节游程编码、算术编码、冗余编码游程：数字序列中连续出现相同符号的一段。二元序列的游程：只有“0”和“1”两种符号。连“0”这一段称为“0”游程，它的长度称为游程长度L(0)；连“1”这一段称为“1”游程，它的游程长度用L(1)表示。游程编码①二元独立序列游程长度概率若规定二元序列总是从“0”开始。对于随机序列，游程长度是随机的其取值可为1,2,3,…，直至无穷。游程长度序列/游程序列：用交替出现的“0”游程和“1”游程长度表示任意二元序列。游程变换：是一种一一对应的变换，也是可逆变换。例如：二元序列：000101110010001…，可变换成如下游程序列：31132131第二十七页，共五十页，编辑于2023年，星期三第八节游程编码、算术编码、冗余编码游程变换减弱了原序列符号间的相关性。游程变换将二元序列变换成了多元序列；这样就适合于用其他方法，如哈夫曼编码，进一步压缩信源，提高通信效率。编码方法：首先测定“0”游程长度和“1”游程长度的概率分布，即以游程长度为元素，构造一个新的信源；对新的信源（游程序列）进行哈夫曼编码。游程编码第二十八页，共五十页，编辑于2023年，星期三第八节游程编码、算术编码、冗余编码②二元独立序列游程长度的熵若二元序列的概率特性已知，由于二元序列与游程变换序列的一一对应性，可计算出游程序列的概率特性。令“0”和“1”的概率分别为p0和p1，则“0”游程长度L(0)的概率为

p[L(0)]=p0L(0)－1p1

式中L(0)=1,2,…,在计算p[L(0)]时必然已有“0”出现，否则就不是“0”游程，若下一个符号是“1”，则游程长度为1，其概率是p1=1－p0；若下一个符号为“0”、再下一个符号为“1”，则游程长度为2，其概率将为p0p1

；依此类推。游程编码第二十九页，共五十页，编辑于2023年，星期三第八节游程编码、算术编码、冗余编码游程编码游程长度至少是1，理论上，游程长度可以是无穷，但很长的游程实际出现的概率非常小。同理可得“1”游程长度L(1)的概率为：P[L(1)]=p1L(1)-1p0“0”游程长度的熵：第三十页，共五十页，编辑于2023年，星期三第八节游程编码、算术编码、冗余编码③二元独立序列的平均游程长度“0”游程序列的平均游程长度同理可得“1”游程长度的熵和平均游程长度游程编码第三十一页，共五十页，编辑于2023年，星期三第八节游程编码、算术编码、冗余编码游程编码④二元独立序列的熵“0”游程序列的熵与“1”游程长度的熵之和除以它们的平均游程长度之和，即为对应原二元序列的熵H(X)游程变换后符号熵没有变。因为游程变换是一一对应的可逆变换，所以变换后熵值不变。第三十二页，共五十页，编辑于2023年，星期三第八节游程编码、算术编码、冗余编码游程变换有较好的去相关效果，因而对游程序列进行哈夫曼编码可获得较高的编码效率。假设“0”游程长度的哈夫曼编码效率为η0，“1”游程长度的哈夫曼编码效率为η1，由编码效率的定义和式(5.4.9)可得对应二元序列的编码效率（信源熵和信息率之比为编码效率η=H(X)/R）当“0”游程和“1”游程的编码效率都很高时，采用游程编码的效率也很高，至少不会低于较小的那个效率。要想编码效率尽可能高，应尽可能提高熵值较大的游程编码效率。游程编码第三十三页，共五十页，编辑于2023年，星期三第八节游程编码、算术编码、冗余编码算术编码算术编码不同于哈夫曼码，它是非分组（非块）码。它从全序列出发，考虑符号之间的关系来进行编码。算术编码利用了累积概率的概念。算术码主要的编码方法是计算输入信源符号序列所对应的区间。因为在编码过程中，每输入一个符号要进行乘法和加法运算，所以称此编码方法为算术编码。二元序列的算术编码可用于黑白图像的编码，例如传真。第三十四页，共五十页，编辑于2023年，星期三第八节游程编码、算术编码、冗余编码算术编码设信源符号集A={a1,a2,…,an}，其相应概率分布为P(ai)，

P(ai)>0(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，F(1)=P(0)第三十五页，共五十页，编辑于2023年，星期三第八节游程编码、算术编码、冗余编码算术编码计算二元无记忆信源序列的累积分布函数初始时：在[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；

第三十六页，共五十页，编辑于2023年，星期三第八节游程编码、算术编码、冗余编码算术编码输入第二个符号为“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)第三十七页，共五十页，编辑于2023年，星期三第八节游程编码、算术编码、冗余编码算术编码第三十八页，共五十页，编辑于2023年，星期三第八节游程编码、算术编码、冗余编码算术编码

输入第三个符号为“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=“010”)=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)。第三十九页，共五十页，编辑于2023年，星期三第八节游程编码、算术编码、冗余编码算术编码归纳当已知前面输入符号序列为s，若接着再输入一个符号“0”，序列s0的累积分布函数为：F(s0)=F(s)对应区间宽度为：A(s0)=A(s)P(0)若接着输入的一个符号是“1”，序列的累积分布函数为：F(s1)=F(s)+A(s)P(0)对应区间宽度为：A(s1)=A(s)P(1)=A(s)－A(s0)第四十页，共五十页，编辑于2023年，星期三第八节游程编码、算术编码、冗余编码算术编码符号序列对应的区间宽度A(s=“0”)=P(0)A(s=“1”)=1－A(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=“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)。第四十一页，共五十页，编辑于2023年，星期三第八节游程编码、算术编码、冗余编码算术编码二元信源符号序列的累积分布函数的递推公式F(sr)=F(s)+P(s)F(r)(r=0,1)

sr表示已知前面信源符号序列为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)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)第四十二页，共五十页，编辑于2023年，星期三第八节游程编码、算术编码、冗余编码算术编码举例：已输入二元符号序列为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”)+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)更新两个存储器中的数值。因此在编码过程中，每输入一个符号要进行乘法和加法运算，所以称为算术编码。第四十三页，共五十页，编辑于2023年，星期三第八节游程编码、算术编码、冗余编码算术编码第四十四页，共五十页，编辑于2023年，星期三第八节游程编码、算术编码、冗余编码算术编码

通过关于信源符号序列的累积分布函数的计算，把区间分割成许多小区间，不同的信源符号序列对应不同的区间为[F(s),F(s)+P(s))。可取小区间内的一点来代表这序列。编码方法：将符号序列的累积分布函数写成二进位的小数，取小数点后k位，若后面有尾数，就进位到第k位，这样得到的一个数C，并使k满足举例第四十五页，共五十页，编辑于2023年，星期三第八节游程编码、算术编码、冗余编码算术编码编码效率这样选取的数值C，一般根据二进小数截去尾数的影响得

C－F(s)<1/2k，当在l以后没有尾数时C=F(s)。

F(s)+1/2k>C而P(s)≥1/2k信源符号序列对应区间的上界为F(s)+P(s)≥F(s)+1/2k>C可见，数值在区间[F(s),F(s)+P(s))内。而信源符号序列对应的不同区间（左封右开）是不重叠的，所以编得的码是即时码。第四十六页，共五十页，编辑于2023年，星期三第八节游程编码、算术编码、冗余编码算术编码算术编码的编码效率很高。当信源符号序列很长时，L很大时，平均码长接近