信息论与编码(清华出版社)第5章信源编码-Qtech

1本节内容编码的定义无失真信源编码定长编码定理变长编码定理2第5章信源编码

编码分为信源编码和信道编码，其中信源编码又分为无失真和限失真。一般称无失真信源编码定理为第一极限定理；信道编码定理（包括离散和连续信道）称为第二极限定理；限失真信源编码定理称为第三极限定理。

3第5章信源编码由于信源符号之间存在分布不均匀和相关性，使得信源存在冗余度，信源编码的主要任务就是减少冗余，提高编码效率。

4第5章信源编码信源编码的基本途径有两个：使序列中的各个符号尽可能地互相独立，即解除相关性；使编码中各个符号出现的概率尽可能地相等，即概率均匀化。5第5章信源编码信源编码的基础是信息论中的两个编码定理：无失真编码定理限失真编码定理

无失真编码只适用于离散信源

对于连续信源，只能在失真受限制的情况下进行限失真编码

6第5章信源编码本章讨论离散信源编码，首先从无失真编码定理出发，重点讨论以香农码、费诺码和霍夫曼码为代表的最佳无失真码。然后介绍限失真编码定理。最后简单介绍一些其它常用的信源编码方法。75.1编码的定义

信源编码器信道码表图5-1信源编码器示意图85.1编码的定义信源编码是指信源输出符号经信源编码器编码后转换成另外的压缩符号；无失真信源编码：可精确无失真地复制信源输出地消息。95.1编码的定义将信源消息分成若干组，即符号序列xi，

xi＝(xi1xi2…xil…xiL)，

xilA={a1，a2，…，ai，…，an}每个符号序列xi依照固定码表映射成一个码字yi，

yi＝(yi1yi2…yil…yiL)，

yilB={b1，b2，…，bi，…，bm}这样的码称为分组码，有时也叫块码。只有分组码才有对应的码表，而非分组码中则不存在码表。

105.1编码的定义如图5-1所示，如果信源输出符号序列长度L＝1，信源符号集A(a1，a2，…，an)；信源概率空间为若将信源X通过二元信道传输，就必须把信源符号ai变换成由0，1符号组成的码符号序列，这个过程就是信源编码。115.1编码的定义码可分为两类：一、固定长度的码，码中所有码字的长度都相同，如表5-1中的码1就是定长码二、可变长度码，码中的码字长短不一，如表中码2就是变长码。

125.1编码的定义不同的码符号序列，如表5-1所示。

表5-1变长码与定长码信源符号ai信源符号出现概率p(ai)码表码1码2a1p(a1)000a2p(a2)0101a3p(a3)10001a4p(a4)11111135.1编码的定义（1）奇异码和非奇异码

若信源符号和码字是一一对应的，则该码为非奇异码。反之为奇异码。如表5-2中的码1是奇异码，码2是非奇异码。

145.1编码的定义表5-2码的不同属性信源符号ai符号出现概率p(ai)码1码2码3码4a11/20011a21/411101001a31/80000100001a41/8110110000001155.1编码的定义（2）唯一可译码

任意有限长的码元序列，只能被唯一地分割成一个个的码字，便称为唯一可译码。如，{0,10,11}是唯一可译码。165.1编码的定义唯一可译码中又分为非即时码和即时码：非即时码：如果接收端收到一个完整的码字后，不能立即译码，还需等下一个码字开始接收后才能判断是否可以译码，这样的码叫做非即时码。175.1编码的定义即时码：只要收到符号就表示该码字已完整，可以立即译码。即时码又称为非延长码，任意一个码字都不是其它码字的前缀部分，亦叫做异前缀码。185.1编码的定义码奇异码非分组码分组码非奇异码非唯一可译码非即时码即时码(非延长码)唯一可译码195.1编码的定义通常可用码树来表示各码字的构成

01

01

01

01010101

0101010101010101二进码树205.1编码的定义012012012012012012三进制码树215.1编码的定义唯一可译码存在的充分和必要条件各码字的长度Ki应符合克劳夫特不等式：

n：信源符号数；m:进制数。

225.1编码的定义例：设二进制码树中X(a1，a2，a3，a4)，K1＝1，K2＝2，K3＝2，K4＝3，应用上述判断定理：

因此不存在满足这种Ki的唯一可译码。

235.1编码的定义a1=1

01

01

01a2=01a3=001a4=000{1，01，001，000}

惟一可译码；{1，01，101，000}

不是惟一可译码；均满足克劳夫特不等式245.1编码的定义克劳夫特不等式只是用来说明唯一可译码是否存在，并不能作为唯一可译码的判据。255.2无失真信源编码

信源输出X＝(X1X2…Xl…XL)，Xl

{a1，a2，…，ai，…，an}编码为Y＝(Y1Y2…Yk…YkL)，Yk

{b1，b2，…，bj，…，bm}。要求能够无失真或无差错地译码，同时传送Y时所需要的信息率最小

265.2无失真信源编码Yk平均每个符号的最大信息量为logmKL长码字的最大信息量为KLlogm则传送一个信源符号需要的信息率平均为

275.2无失真信源编码所谓信息率最小，就是找到一种编码方式使最小。无失真信源编码定理研究的内容:最小信息率为多少时，才能得到无失真的译码？若小于这个信息率是否还能无失真地译码？285.2无失真信源编码无失真的信源编码定理定长编码定理变长编码定理295.2无失真信源编码定长编码定理

K是定值，且惟一可译码。30惟一可译码的判断方法首先，观察是否是非奇异码。其次，计算是否满克劳夫特不等式将码画成一棵树图，观察是否满足即时码的树图的构造，若满足则是惟一可译码。计算出分组码中所有可能的尾随后缀集合F，观察F中有没有包含任一码字，若无则为惟一可译码；若有则一定不是惟一可译码。31定长编码定理由L个符号组成的、每个符号的熵为HL(X)的无记忆平稳信源符号序列X1X2…Xl…XL，可用KL个符号Y1，Y2，…，Yk，…，（每个符号有m种可能值）进行定长编码。对任意

>0，

>0，只要 则当L足够大时，必可使译码差错小于

；反之，当时，译码差错一定是有限值，而L足够大时，译码几乎必定出错。

325.2无失真信源编码定长编码定理说明，码字所能携带的信息量大于信源序列输出的信息量，则可以使传输几乎无失真，当然条件是L足够大。

335.2无失真信源编码反之，当时，不可能构成无失真的编码，也就是不可能做一种编码器，能使收端译码时差错概率趋于零。时，则为临界状态，可能无失真，也可能有失真。345.2无失真信源编码式中为自信息方差，

为一正数。当和均为定值时，只要L足够大，Pe可以小于任一正数

。即，

355.2无失真信源编码当信源序列长度L满足时，能达到差错率要求：

365.2无失真信源编码在连续信源的情况下，由于信源的信息量趋于无限，显然不能用离散符号序列Y来完成无失真编码，而只能进行限失真编码。375.2无失真信源编码定义

为编码效率，即信源的平均符号熵为H(X)，采用平均符号码长为来编码，所得的效率。编码效率总是小于1，且最佳编码效率为

385.2无失真信源编码编码定理从理论上阐明了编码效率接近1的理想编码器的存在性，它使输出符号的信息率与信源熵之比接近于1，即

L取无限长395.2无失真信源编码例

设离散无记忆信源概率空间为比特/符号

405.2无失真信源编码对信源符号采用定长二元编码，要求编码效率为90％，若取L＝1，则可算出 ＝2.5590%=2.83比特/符号每个符号用2.83比特进行定长编码，共有

种可能性。那么，信源符号中就有一种符号无对应码字。即使发生概率最小的a8,其Pe＝0.04太大！415.2无失真信源编码若要求译码错误概率

需要同时对100M个信源符号一起编码！425.2无失真信源编码变长编码定理在变长编码中，码长K是变化的根据信源各个符号的统计特性，如概率大的符号用短码，概率小的用较长的码，使得编码后平均码长降低，从而提高编码效率。（统计匹配）435.2无失真信源编码单个符号变长编码定理：若离散无记忆信源的符号熵为H(X)，每个信源符号用m进制码元进行变长编码，一定存在一种无失真编码方法，其码字平均长度满足下列不等式445.2无失真信源编码

离散平稳无记忆序列变长编码定理：对于平均符号熵为HL(X)的离散平稳无记忆信源，必存在一种无失真编码方法，使平均信息率满足不等式其中

为任意小正数。455.2无失真信源编码用变长编码来达到相当高的编码效率，一般所要求的符号长度L可以比定长编码小得多。465.2无失真信源编码编码效率总是小于1，可以用它来衡量各种编码方法的优劣。为了衡量各种编码方法与最佳码的差距，定义码的剩余度为

475.2无失真信源编码例 设离散无记忆信源的概率空间为485.2无失真信源编码若用二元定长编码(0，1)来构造一个即时码：。平均码长＝1二元码符号/信源符号495.2无失真信源编码编码效率为输出的信息效率为R＝0.811比特/二元码符号505.2无失真信源编码长度为2的信源序列进行变长编码（编码方法后面介绍），其即时码如下表aip(ai)即时码a1a19/160a1a23/1610a2a13/16110a2a21/16111515.2无失真信源编码二元码符号/信源序列二元码符号/信源符号525.2无失真信源编码编码效率信息效率R2＝0.961比特/二元码符号535.2无失真信源编码信源序列长度增加：L＝3时R3＝0.985比特/二元码符号

L＝4时R4＝0.991比特/二元码符号

545.2无失真信源编码若采用定长二元码编码，要求编码效率达到96％时，允许译码错误概率

55L求解的解释：根据式(5-2-7)求得：将其代入式（5-2-6），得到：56575.2无失真信源编码最佳变长编码

凡是能载荷一定的信息量，且码字的平均长度最短，可分离的变长码的码字集合称为最佳变长码。

585.2无失真信源编码能获得最佳码的编码方法主要有：香农（Shannon）费诺（Fano）哈夫曼（Huffman）等

595.2无失真信源编码香农（Shannon）编码1.将信源消息符号按其出现的概率大小依次排列2.确定满足下列不等式的整数码长Ki。605.2无失真信源编码为了编成唯一可译码，计算第i个消息的累加概率将累加概率Pi变换成二进制数。取Pi二进数的小数点后Ki位即为该消息符号的二进制码字。615.2无失真信源编码例设信源共7个符号消息，其概率和累加概率如下表所示。

625.2无失真信源编码信源消息符号ai符号概率(ai)累加概率Pi-logp(ai)码字长度Ki码字a10.2002.323000a20.190.22.393001a30.180.392.473011a40.170.572.563100a50.150.742.743101a60.100.893.3241110a70.010.996.6471111110635.2无失真信源编码以i=4为例，645.2无失真信源编码码元/符号比特/码元

655.2无失真信源编码费诺编码方法费诺编码属于概率匹配编码(1)将信源消息符号按其出现的概率大小依次排列：(2)将依次排列的信源符号按概率值分为两大组，使两个组的概率之和近于相同，并对各组赋予一个二进制码元“0”和“1”。665.2无失真信源编码(3)将每一大组的信源符号进一步再分成两组，使划分后的两个组的概率之和近于相同，并又赋予两个组一个二进制符号“0”和“1”。(4)如此重复，直至每个组只剩下一个信源符号为止。(5)信源符号所对应的码字即为费诺码。675.2无失真信源编码例对以下信源进行费诺编码。

消息符号ai各个消息概率p(ai)第一次分组第二次分组第三次分组第四次分组二元码字码长Kia10.2000002a20.19100103a30.1810113a40.1710102a50.15101103a60.101011104a70.01111114685.2无失真信源编码

码元/符号

bit/符号

695.2无失真信源编码

哈夫曼编码方法(1)将信源消息符号按其出现的概率大小依次排列，(2)取两个概率最小的字母分别配以0和1两个码元，并将这两个概率相加作为一个新字母的概率，与未分配的二进符号的字母重新排队。705.2无失真信源编码(3)对重排后的两个概率最小符号重复步骤(2)的过程。(4)不断继续上述过程，直到最后两个符号配以0和1为止。(5)从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码字。715.2无失真信源编码例对以下信源进行哈夫曼编码

信源符号ai概率p(ai)码字Wi码长Kia10.20102a20.19112a30.180003a40.170013a50.150103a60.1001104a70.0101114725.2无失真信源编码0.20 0.200.260.350.390.611.00.190.190.200.260.350.390.180.180.190.200.260.170.170.180.190.150.150.170.100.110.01010101010101735.2无失真信源编码

码元/符号

bit/符号

745.2无失真信源编码哈夫曼编码方法得到的码并非唯一的每次对信源缩减时，赋予信源最后两个概率最小的符号，用0和1是可以任意的，所以可以得到不同的哈夫曼码，但不会影响码字的长度。755.2无失真信源编码对信源进行缩减时，两个概率最小的符号合并后的概率与其它信源符号的概率相同时，这两者在缩减信源中进行概率排序，其位置放置次序是可以任意的，故会得到不同的哈夫曼码。此时将影响码字的长度，一般将合并的概率放在上面，这样可获得较小的码方差。765.2无失真信源编码例设有离散无记忆信源775.2无失真信源编码信源符号ai概率p(ai)码字Wi1码长Ki1码字Wi2码长K’i2a10.411002a20.2012102a30.20003112a40.1001040103a50.1001140113

其有两种哈夫曼编码方法：785.2无失真信源编码0.40.40.40.61.00.20.20.40.40.20.20.20.10.20.10.40.40.40.61.00.20.20.40.40.20.20.20.10.20.10101010101010101795.2无失真信源编码

码元/符号

805.2无失真信源编码815.2无失真信源编码

进行哈夫曼编码时，为得到码方差最小的码，应使合并的信源符号位于缩减信源序列尽可能高的位置上，以减少再次合并的次数，充分利用短码。

825.2无失真信源编码哈夫曼码是用概率匹配方法进行信源编码。哈夫曼码的编码方法保证了概率大的符号对应于短码，概率小的符号对应于长码，充分利用了短码；缩减信源的最后二个码字总是最后一位不同，从而保证了哈夫曼码是即时码。835.3限失真信源编码定理

信息率失真函数给出了失真小于D时所必须具有的最小信息率R(D)；只要信息率大于R(D)，一定可以找到一种编码，使译码后的失真小于D。845.3限失真信源编码定理限失真信源编码定理：设离散无记忆信源X的信息率失真函数R(D)，则当信息率R>R(D)，只要信源序列长度L足够长，一定存在一种编码方法，其译码失真小于或等于D＋

，

为任意小的正数。反之，若R<R(D)，则无论采用什么样的编码方法，其译码失真必大于D。855.3限失真信源编码定理如果是二元信源，对于任意小的

，每一个信源符号的平均码长满足如下公式

865.3限失真信源编码定理在失真限度内使信息率任意接近R(D)的编码方法存在。然而，要使信息率小于R(D)，平均失真一定会超过失真限度D。对于连续平稳无记忆信源，无法进行无失真编码，在限失真情况下，有与上述定理一样的编码定理。875.3限失真信源编码定理限失真信源编码定理只能说明最佳编码是存在的，而具体构造编码方法却一无所知。因而就不能象无损编码那样从证明过程中引出概率匹配的编码方法。一般只能从优化的思路去求最佳编码。迄今尚无合适的可实现的编码方法可接近R(D)这个界。885.4常用信源编码方法简介游程编码在二元序列中，连0段称为0游程连1段称为1游程000101110010001可变换成下列游程序列：3113213895.4常用信源编码方法简介若已知二元序列以0起始，从游程序列很容易恢复成原来的二元序列；游程序列是多元序列，各长度可按霍夫曼编码或其它方法处理以达到压缩码率的目的。905.4常用信源编码方法简介多元序列也存在相应的游程序列；多元序列变换成游程序列再进行压缩编码没有多大意义；游程编码只适用于二元序列，对于多元信源，一般不能直接利用游程编码。915.4常用信源编码方法简介冗余位编码，——游程编码在多元信源的应用925.4常用信源编码方法简介如下多元序列x1，x2，…，xm1，y，y，…，y，xm1+1，xm1+2，…x

m2，y，y，…X为信息位，取值于m元符号集；y为冗余位，可全为0，无需传送在接收端也可恢复。此多元序列可以用下面序列表示：

111，…，100，…，000111，…，111000x1，x2，…，xm1，x

m1+1，x

m1+2…x

m2，…1表示信息位，0表示冗余位935.4常用信源编码方法简介算术编码非分组码的编码方法之一——算术码94算术编码研究的目的和意义各种媒体信息（图像，动态视频等）数据量非常之大。例如：一幅640x480分辨率的24位真彩色图像的数据量约力900kb；一个100Mb的硬盘只能存储约l00幅静止图像画面。数据量不仅超出了计算机的存储和处理能力，更是当前通信信道的传输速率所不及的。为了存储、处理和传输多媒体数据，必须进行压缩。语音的数据量较小，且基本压缩方法己经成熟；目前的数据压缩研究主要集中于图像和视频信号的压缩方面。图像压缩技术、视频技术与网络技术相结合的应用前景十分可观。研究算术编码以更好的利用它是非常必要的。算术编码作为一种高效的数据编码方法在文本，图像，音频等压缩中有广泛的应用。95算术编码研究的目的和意义根据解码后数据与原始数据是否完全一致进行分类，数据压缩方法一般分为两类：①无损压缩，即解码图像与原始图像严格相同，压缩比大约在2：1－5：1之间，如霍夫曼编码，算术编码等；②有损编码，即还原图像与原始图像存在一定的误差，但视觉效果一般可以接受，压缩比可以从几倍到上百倍，如：PCM编码，预测编码、变换编码等。算术编码作为一种高效的数据编码方法在文本，图像，音频：等压缩中有广泛的应用。它是一种到目前为止编码效率最高的统计熵编码方法,它比著名的Huffman编码效率提高10％左右。96算术编码的原理根据信源可能发现的不同符号序列的概率，把[0，1]区间划分为互不重叠的子区间，子区间的宽度恰好是各符号序列的概率；信源发出的不同符号序列将与各子区间一一对应；每个子区间内的任意一个实数都可以用来表示对应的符号序列，这个数就是该符号序列所对应的码字。975.4常用信源编码方法简介把区间[0，1)分割成许多小区间，每个小区间的长度等于各序列的概率pr，小区间内的任一点可用来代表这序列;

0(P1)P2P3P4P5……1

……p1

p2p3p4985.4常用信源编码方法简介0(P1)P2P3P4P5……1

……p1

p2p3p4

代表大于或等于的最小整数。把累积概率P(S)写成二进位的小数，取其前L位;如果有尾数，就进位到第L位，这样得到一个数C；

995.4常用信源编码方法简介例如P(S)＝0.10110001，p(S)=1/17，则L＝5（？）， 得C＝0.10111这个C就可作为S的码字编码效率很高，当序列很长时，可达到概率匹配。平均代码长度接近S的熵值。可以唯一地译码

1005.4常用信源编码方法简介采用累积概率P(S)表示码字C(S)，符号概率p(S)表示状态区间A(S)S：符号序列；pr:某一区间的概率；

0(P1)P2P3P4P5……1

……p1

p2p3p41015.4常用信源编码方法简介符号符号概率pi符号累积概率Pja0.100(1/2)0.000b0.010(1/4)0.100c0.001(1/8)0.110d0.001(1/8)0.111例有四个符号a，b，c，d构成简单序列S＝abda，各符号及其对应概率如下表，算术编解码过程如下：1025.4常用信源编码方法简介设起始状态为空序列

，则A(

)＝1，C(

)＝0（定义）。1035.4常用信源编码方法简介1045.4常用信源编码方法简介C(abda)即为编码后的码字0101111055.4常用信源编码方法简介A(

)A(a)abcdA(a,b)abcdabcdA(a,b,d)C(

)0(Pa)pa

PbpbPcpcPdpd1C(0)C(a,b,d)C(a,b)算术编码过程1065.4常用信源编码方法简介译码（逆过程）C(abda)=0.010111<0.1

[0,0.1]

第一个符号为a

放大至[0,1](×pa-1)：C(abda)×21＝0.10111

[0.1,0.110]

第二个符号为b

去掉累积概率Pb：0.10111-0.1=0.001111075.4常用信源编码方法简介放大至[0,1](×pb-1)：

0.00111×22=0.111

[0.111,1]

第三个符号为d

去掉累积概率Pd：0.111-0.111=0

放大至[0,1](×pd-1)：0×24＝0

[0,0.1]第四个符号为a108算术编码译码步骤先将码字变成小数形式判断所得值落在所划分的哪个区域内减去所对应的累积概率除以相应的符号概率1095.4常用信源编码方法简介算术编码从性能上看具有许多优点，特别是由于所需的参数很少，不象哈夫曼编码那样需要一个很大的码表，常设计成自适应算术编码来针对一些信源概率未知或非平稳情况。1105.4常用信源编码方法简介但是在实际实现时还有一些问题，如计算复杂性、计算的精度以及存储量等，随着这些问题的逐渐解决，算术编码正在进入实用阶段，但要扩大应用范围或进一步提高性能，降低造价，还需进一步改进。作业P115:5-3；5-5；5-11.111112算术编码过程算术编码在图像数据压缩标准（如JPEG，JBIG）中扮演了重要的角色。在算术编码中，消息用0到1之间的实数进行编码，算术编码用到两个基本的参数：符号的概率和它的编码间隔。信源符号的概率决定压缩编码的效率，也决定编码过程中信源符号的间隔，而这些间隔包含在0到1之间。编码过程中的间隔决定了符号压缩后的输出。113算术编码过程编码编码时首先输入的符号是c，找到它的编码范围是[0.5,0.7)。由于消息中第二个符号a的编码范围是[0,0.1)，因此它的间隔就取[0.5,0.7)的第一个十分之一作新间隔[0.5,0.52)。假设信源符号为{a,b,c,d}，这些符号的概率分别为:p(a)=0.1,p(b)=0.4,p(c)=0.2,p(d)=0.3。如果消息序列的输入:cadacdb。

114算术编码过程1c[0.5,0.7)符号的间隔范围[0.5,0.7)

2a[0.5,0.52)[0.5,0.7)间隔的第一个1/10

3d[0.514,0.52)[0.5,0.