信息论与编码第5章

1、第5章信源编码编码分为信源编码和信道编码，其中信源编码又分为无失真和限失真。一般称u无失真信源编码定理为第一极限定理；u信道编码定理（包括离散和连续信道）称为第二极限定理；u限失真信源编码定理称为第三极限定理。1信息论基础B第5章信源编码由于信源符号之间存在分布不均匀和相关性，使得信源存在冗余度，信源编码的主要任务就是减少冗余，提高编码效率。2信息论基础B第5章信源编码信源编码的基本途径有两个：n 使序列中的各个符号尽可能地互相除相关性；，即解n 使编码中各个符号出现的概率尽可能地相等，即概率均匀化。3信息论基础B第5章信源编码信源编码的基础是信息论中的两个编码定理：n 无失真编码定理n 限失

2、真编码定理 无失真编码只适用于离散信源 对于连续信源，只能在失真受限制的情况下进行限失真编码4信息论基础B5.1编码的定义图5-1信源编码器示意图5信息论基础B码表信道编码器信源5.1编码的定义信源编码是指信源输出符号经信源编码器编码后转换成另外的压缩符号无失真信源编码：可精确无失真地地消息信源输出6信息论基础B5.1编码的定义将信源消息分成若干组，即符号序列xi，xi(xi1xi2xilxiL)， xilÎA=a1，a2，ai，an每个符号序列xi依照固定码表yi(yi1yi2yilyiL)，成一个码字yi，yilÎB=b1，b2，bi，bm这样的码称为分组码，有时也叫块

3、码。只有分组码才有对应的码表，而组码中则不存在码表。7信息论基础B5.1编码的定义如图5-1所示，如果信源输出符号序列长度L1，信源符号集A(a1，a2，an)信源概率空间为é X ù = éùa1a2p(a2 )LLanêP úêúp(a)p(a)ëûëû1n若将信源X通过二元信道传输，就必须把信源符号ai变换成由0，1符号组成的码符号序列，这个过程就是信源编码8信息论基础B5.1编码的定义不同的码符号序列，如表5-1所示。表5-1变长码与定长码9信息论基础B信源符号ai信

4、源符号出现概率p(ai)码表码1码2a1 a2 a3a4p(a1)p(a2)p(a3)p(a4)000110110010011115.1编码的定义组码奇异码码非唯一可译码非奇异码非即时码分组码唯一可译码即时码(非延长码)10信息论基础B5.1编码的定义表5-2码的不同属性11信息论基础B信源符号ai符号出现概率p(ai)码1码2码3码4a11/20011a21/411101001a31/80000100001a41/81101100000015.1编码的定义通常可用码树来表示各码字的010101010101010101 010101 01 0101二进制码树12信息论基础B5.1编码的定义01

5、2012012012012012三进制码树13信息论基础B5.1编码的定义唯一可译码存在的充分和必要条件各码字的长度Ki 应符合克劳夫特不等式：nå mKii=1£ 114信息论基础B5.1编码的定义例：设二进制码树中X(a1， a2 ，Îa3 ， a4)，K1定1，K22，K32，K43，应用上述理：49å=-K-+=ii=1因此不存在满足这种Ki的唯一可译码。15信息论基础B5.1编码的定义1，01，001，000惟一可译码；1，01，101，000不是惟一可译码； 均满足克劳夫特不等式01a1=101a2=01014å2- Kii=1=

6、2-1 + 2-2 + 2-3 + 2-3 = 1a4=000a3=01116信息论基础B5.2信源输出无失真信源编码X(X1X2XlXL)，XlÎa1，a2，ai，an编码为Y(Y1Y2Yk YkL)， YkÎb1，b2，bj，bm。要求能够无失真或无差错地译码，同时传送Y 时所需要的信息率最小17信息论基础B5.2无失真信源编码无失真的信源编码定理n 定长编码定理n 变长编码定理18信息论基础B5.2无失真信源编码由L个符号组成的、每个符号的熵为HL(X)的无记忆平稳信源符号序列X1X2XlXL，可用KL个符号Y1， Y2，Yk，（每个符号有m种可能值）进行定长编码。对

7、任意e>0，d>0，只要则当L足够大时，必可使译码差错小于d；反之，当 KL(X) + e 时，译码差错一log m ³ HLL定是有限值，而L足够大时，译码几乎必定出错KLlog m £ H (X) - 2eLL19信息论基础B5.2无失真信源编码定长编码定理说明，KL log m > LHL (X) = H (X)码字所能携带的信息量大于信源序列输出的信息量，则可以使传输几乎无失真，当然条件是L足够大。20信息论基础B5.2无失真信源编码反之，当 K < HL (X)时，不可能无失真的编码，也就是不可能做一种编码器，能使收端译码时差错概率趋于零。

8、K = HL (X) 时，则为临界状态，可能无失真，也可能有失真。21信息论基础B5.2无失真信源编码s 2 (X)£PeLe 2式中s2 ()2为自信息方差e为一正数。当s 2 ( X ) 和 e 2 均为定值时，只要L足够大，Pe可以小于任一正数d。即，s 2 (X) £ dLe 222信息论基础B5.2无失真信源编码s 2 (X) 时，e 2d当信源序列长度L满足L ³s 2 (X)Le 2能达到差错率要求Pe £23信息论基础B5.2无失真信源编码在连续信源的情况下，由于信源的信息量趋于无限，显然不能用离散符号序列Y来完成无失真编码，而只能进行限

9、失真编码。24信息论基础B5.2无失真信源编码h = HL (X)定义K为编码效率，即信源的平均符号熵为H(X)，采用平均符号码长为K来编码，所得的效率。编码效率总是小于1，且最佳编码效率为HL (X)HL (X) + eh =,e > 025信息论基础B5.2无失真信源编码编码定理从理论上阐明了编码效率接近1的理想编码器的存在性，它使输出符号的信息率与信源熵之比接近于1，即HL (X)® 1KLlog mLL取无限长26信息论基础B5.2无失真信源编码例设离散无记忆信源概率空间为é X ùé a1ùa20.18a30.1a40.1a50

10、.07a60.06a70.05a8ê P úê0.40.04úëûëû8H ( X ) = -å pii=1= 2.55比特/符号log pi27信息论基础B5.2无失真信源编码对信源符号采用定长二元编码，要求编码效率90，若取L1，则可算出为2.55 ¸ 90%=2.8比特/符号KPe0.04太大28信息论基础B5.2无失真信源编码H ( X )hÞ e = 0.28= 0.90,H ( X ) + e8åi=1s( X ) = DI (x ) =- H ( X )2= 7

11、.82(bit)222p (log p )iiid£ 106若要求译码错误概率s 2 ( X )e 2d7.82L ³=0.282 ´10-6= 9.8 ´10» 107829信息论基础B5.2无失真信源编码变长编码定理在变长编码中，码长K是变化的根据信源各个符号的统计特性，如概率大的符号用短码，概率小的用较长的码，使得编码后平均码长降低，从而提高编码效率。（统计匹配）30信息论基础B5.2无失真信源编码单个符号变长编码定理：若离散无记忆信源的符号熵为H(X)，每个信源符号用m进制码元进行变长编码，一定存在一种无失真编码方法，其码字平均长度满足

12、下列不等式H ( X ) £ K < H ( X ) + 1log mlog m31信息论基础B5.2无失真信源编码离散平稳无记忆序列变长编码定理：对于平均符号熵为HL(X)的离散平稳无记忆信源，必存在一种无失真编码方法，使平均信息率满足不等式HL (X) £ K < HL (X) + e其中e为任意小正数。32信息论基础B5.2无失真信源编码编码效率总是小于1，可以用它来衡量各种编码方法的优劣。为了衡量各种编码方法与最佳码的差距，定义码的剩余度为HL ( X )= 1 - HL ( X )g= 1 - h = 1 -KLKlog mL33信息论基础B5.2无失

13、真信源编码例设离散无记忆信源的概率空间为éa1a2 ù1 ú4 úûé X ùê P ú = ê 3êë 4ëû34信息论基础B5.2无失真信源编码H ( X ) = 1 log 4 + 3 log 4 = 0.811bit / 符号443若用二元定长编码(0，1)来构造一个即® 0,a2® 1。时码：a1平均码长 K 1二元码符号/信源符号35信息论基础B5.2无失真信源编码编码效率为h = H ( X ) = 0.811K输出的信息

14、效率为R0.811比特/二元码符号36信息论基础B5.2无失真信源编码长度为2的信源序列进行变长编码（编码方法后面介绍），其即时码如下表37信息论基础Baip(ai)即时码a1a19/160a1a23/1610a2a13/16110a2a21/161115.2无失真信源编码933K2 =´1´ 2´´1616二元码符号/信源序列K = K2= 27二元码符号/信源符号23238信息论基础B5.2无失真信源编码编码效率= 32 ´ 0.811 = 0.961h227信息效率R20.961比特/二元码符号39信息论基础B5.2无失真信源编码h3 =

15、 0.985L3R30.985比特/二元码符号h4 = 0.991L4R40.991比特/二元码符号40信息论基础B5.2无失真信源编码定长二元码编码，要求编码效率达到96时d £ 105，译码错误概率2s 2 ( X ) = å pi (log pi )2 -H ( X )2i=1= 0.4715(bit)2(0.96)20.4715L ³(0.811)2·0.0424.13 ´10´105741信息论基础B5.2无失真信源编码能获得最佳码的编码方法主要有：n 香农（Shannon）n 费诺（Fano）n 哈夫曼（Huffman）等

16、42信息论基础B5.2无失真信源编码香农（Shannon）编码将信源消息符号按其出现的概率大小依次np1 ³ p2³ L ³ pn排列确定满足下列不等式的整数码长Ki。nlog2 (pi ) £ Ki< - log2 (pi ) + 143信息论基础B5.2无失真信源编码为了编成唯一可译码，计算第i个消息的累加3.i-1Pi= å p(ak )概率k =1将累加概率Pi变换成二进制数。取Pi二进数的小数点后Ki位即为该消息符号的二进制码字。4.5.44信息论基础B5.2无失真信源编码设信源共7个符号消息，其概率和累加概率如下表所示。例45

17、信息论基础B5.2无失真信源编码信息论基础B信源消息符号ai符号概率(ai)累加概率Pi-log p(ai)码字长度Ki码字a10.2002.323000a20.190.22.393001a30.180.392.473011a40.170.572.563100a50.150.742.743101a60.100.893.3241110a0.010.996.64711111107465.2无失真信源编码7K = å p(ai )Kii=1= 3.14码元/符号R = H ( X ) = 2.61 = 0.831比元3.14K47信息论基础B5.2无失真信源编码费诺编码方法费诺编码属于概率

18、匹配编码(1)将信源消息符号按其出现的概率大小依次³ p2³ L ³ pn排列：p1。(2)将依次排列的信源符号按概率值分为两大组，使两个组的概率之和近于相同，并对各组赋予一个二进制码元“0”和“1”。48信息论基础B5.2无失真信源编码(3) 将每一大组的信源符号进一步再分成两组，使划分后的两个组的概率之和近于相同，并又赋予两个组一个二进制符号“0”和“1”。(4) 如此重复，直至每个组只剩下一个信源符号为止。(5) 信源符号所对应的码字即为费诺码。49信息论基础B5.2无失真信源编码例对以下信源进行费诺编码。消息符号ai各 个 消息 概 率p(ai)第一次分组

19、第二次分组第三次分组第四次分组二元码字码长Kia10.2000002a20.1913a30.a40.1710102a50.15101103a60.101011104信息论a7基础B0.01111114505.2无失真信源编码7K = å p(ai )Kii=1= 2.74码元/符号R = H ( X ) = 2.61 = 0.953bit/符号2.74K51信息论基础B5.2无失真信源编码哈夫曼编码方法(1)将信源消息符号按其出现的概率大小依次排p1 ³ p2³ L ³ pn列，(2)取两个概率最小的字母分别配以0和1两个码元，并将这两个概率相加作为一个

20、新字母的概率，与未分配的二进符号的字母重新排队。52信息论基础B5.2无失真信源编码(3) 对重排后的两个概率最小符号重复步骤(2)的过程。(4) 不断继续上述过程，直到最后两个符号配以0和1为止。(5) 从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码字。53信息论基础B5.2无失真信源编码例对以下信源进行哈夫曼编码信源符号ai概率p(ai)码字Wi码长Kia10.20102a20.19112a30.180003a40.170013a50.150103a60.1001104信息论基础Ba70.0101114545.2无失真信源编码0.200.190.180.170.150

21、.1000.200.190.180.170.260.200.190.180.350.260.200.190.390.350 0.261 0.6100.390 1.01 1 00.150.110.171 01 0.011 55信息论基础B5.2无失真信源编码7K = å p(ai )Kii=1= 2.72码元/符号R = H ( X ) = 2.61 = 0.96bit/符号2.72K56信息论基础B5.2无失真信源编码哈夫曼编码方法得到的码并非唯一的n 每次对信源缩减时，赋予信源最后两个概率最小的符号，用0和1是可以任意的，所以可以得到不同的哈夫曼码，但影响码字的长度。57信息论基础

22、B5.2无失真信源编码n 对信源进行缩减时，两个概率最小的符号合并后的概率与其它信源符号的概率相同时， 这两者在缩减信源中进行概率排序，其位置放置次序是可以任意的，故会得到不同的哈夫曼码。此时将影响码字的长度，一般将合并的概率放在上面，这样可获得较小的码方差。58信息论基础B5.2无失真信源编码例设有离散无记忆信源P = é a1ùa20.2a30.2a40.1a5Xê0.40.1úëû59信息论基础B5.2无失真信源编码60信息论基础B信源符号ai概率p(ai)码字Wi1码长Ki1码字Wi2码长Ki2a10.411002a20.20

23、12102a30.20003112a40.1001040103a50.10011401135.2无失真信源编码0.40.20.20.40.20.20.40.40.20.60.41 001 01 00.10.10.21 01 0.40.20.20.1 00.40.20.20.20.40.40.20.60.41.001 01 01 0.1 1 61信息论基础B5.2无失真信源编码7K = å p(ai )Kii=1= 2.2码元/符号h = H ( X ) = 0.965K62信息论基础B5.2无失真信源编码= E(K )2 = åqi=1s-p(ai )(ki -2l2kiK

24、 )s= 1.362l1s= 0.162l 263信息论基础B5.2无失真信源编码进行哈夫曼编码时，为得到码方差最小的码，应使合并的信源符号位于缩减信源序列尽可能高的位置上，以减少再次合并的次数，充分利用短码。64信息论基础B5.2无失真信源编码哈夫曼码是用概率匹配方法进行信源编码。n 哈夫曼码的编码方法保证了概率大的符号对应于短码，概率小的符号对应于长码，充分利用了短码；n 缩减信源的最后二个码字总是最后一位不同，从而保证了哈夫曼码是即时码。65信息论基础B5.3限失真信源编码定理信息率失真函数给出了失真小于D时所必须具有的最小信息率R(D)；只要信息率大于R(D)，一定可以找到一种编码，

25、使译码后的失真小于D。66信息论基础B5.3限失真信源编码定理限失真信源编码定理：设离散无记忆信源X的信息率失真函数R(D)，则当信息率R>R(D)，只要信源序列长度L足够长， 一定存在一种编码方法，其译码失真小于或等于De，e为任意小的正数。反之，若R<R(D)，则无论采用什么样的编码方法，其译码失真必大于D。67信息论基础B5.3限失真信源编码定理如果是二元信源，对于任意小的e，每一个信源符号的平均码长满足如下公式R(D) £ K < R(D) + e68信息论基础B5.3限失真信源编码定理在失真限度内使信息率任意接近R(D)的编码方法存在。然而，要使信息率小于

26、R(D)，平均失真一定会超过失真限度D。对于连续平稳无记忆信源，无法进行无失真编码，在限失真情况下，有与上述定理一样的编码定理。69信息论基础B5.3限失真信源编码定理限失真信源编码定理只能说明最佳编码是存在的，而具体构造编码方法却一无所知。因而就不能象无损编码那样从证明过程中引出概率匹配的编码方法。一般只能从优化的思路去求最佳编码。实际上迄今尚无合适的可实现的编码方法可接近R(D)这个界。70信息论基础B5.4常用信源编码方法简介n 算术编码组码的编码方法之一算术码71信息论基础B5.4常用信源编码方法简介符号概率与积累概率的递推关系P(S, r) = P(S) + p(S)Pr , r =

27、 0,1ìP(S,0) = P(S )íP(S,1) = P(S ) + p(S )Pî072信息论基础B5.4常用信源编码方法简介采用累积概率P(S)表示码字C(S)，符号概率p(S)表示状态区间A(S)ìC(Sr) = C(S ) + A(S )PríA(Sr) = A(S ) pîr73信息论基础B5.4常用信源编码方法简介P(S)把区间0，1)分割成许多小区间，每个小区间的长度等于各序列的概率p(S)，小区间内的任一点可用来代表这序列0(P1)P2P3P4P51p1p2p3p474信息论基础B5.4常用信源编码方法简介0(P1

28、)P2P3P4P51p1p2p3p4L = élogù1êp(S ) úêúé ù 代表大于或等于的最小整数。把积累概率P(S)写成二进位的小数，取其前L位; 如果有尾数，就进位到第L位，这样得到一个数C75信息论基础B5.4例如P(S)0.10110001，p(S)=1/17，则L5， 得C0.10111这个C就可作为S的码字编码效率很高，当序列很长时，可达到概率匹配。平均代码长度接近S的熵值。可以唯一地译码常用信源编码方法简介76信息论基础B5.4例常用信源编码方法简介有四个符号a，b，c，d简单序列Sabda

29、，各符号及其对应概率如下表，算术编过程如下：77信息论基础B符号符号概率pi符号累积概率Pja0.100(1/2)0.000b0.010(1/4)0.100c0.001(1/8)0.110d0.001(1/8)0.1115.4常用信源编码方法简介设起始状态为空序列j，则1，C(j)0。ìC(ja) = C(j ) + A(j )Pa= 0 + 1 ´ 0 = 0í A(ja) = A(j ) p= 1 ´ 0.1 = 0.1îaìC(ab) = C(a) + A(a)Pb= 0 + 0.1 ´ 0.1 = 0.01í A(ab) = A(a) p= 0.1 ´ 0.01 = 0.001îb78信息论基础B5.4常用信源编码方法简介ìC(abd )