《信源编码ppt课件》由会员分享，可在线阅读，更多相关《信源编码ppt课件（61页珍藏版）》请在金锄头文库上搜索。
1、HUST - Basis for Information Theory信源编码（主要内容）信源编码（主要内容）o信源编码定理vv信源编码概念信源编码概念信源编码概念信源编码概念vv香农第一定理（变长编码）香农第一定理（变长编码）香农第一定理（变长编码）香农第一定理（变长编码）vv香农第三定理香农第三定理香农第三定理香农第三定理o信源编码方法n n离散信源编码离散信源编码离散信源编码离散信源编码n n连续信源编码连续信源编码连续信源编码连续信源编码* * * *n n相关信源编码相关信源编码相关信源编码相关信源编码* * * *n n变换编码变换编码变换编码变换编码* * * *1HUST -
2、Basis for Information Theoryo特点：特点：n在符号序列长度L不很大时，能达到较高的编码效率。n n完全无失真完全无失真完全无失真完全无失真o要求：要求：n变长码要满足唯一可译码条件，则它必须是非非奇异码奇异码，而且任意有限长L次扩展码也应该是非非奇异码奇异码。n为了能够即时译码，变长码还必须是即时码即时码。变长编码变长编码2HUST - Basis for Information Theory1 1、克拉夫特不等式、克拉夫特不等式o信源符号数、码符号数信源符号数、码符号数和码字长度码字长度之间应满足什么条件，才能构成即时码？即时码？3HUST - Basis for
3、 Information Theory2 2、麦克米伦不等式、麦克米伦不等式o将克拉夫特不等式推广到唯一可译码唯一可译码的情况o定理定理 在前一定理所给定的条件下，唯一可译码存在存在的充要条件的充要条件是4HUST - Basis for Information Theory说明说明o如果码字长度码字长度和码符号数码符号数满足克拉夫特（或麦克米伦）不等式，则一定可以构造出即时码（或唯一可译码），否则不能构造出即时码（或唯一可译码）。o但是该定理并不能作为判断一种码是否为即并不能作为判断一种码是否为即时码（或唯一可译码）的依据时码（或唯一可译码）的依据。n例如：码中，有两个码字长度相同，则这两个
4、码字无论是否相同，都可能使不等式成立。但是，两个码字相同时显然不可能是唯一可译码。5HUST - Basis for Information Theory3 3、平均码长、平均码长o定义定义 设信源 o编码后的码字分别为W1 ，W2，Wn，相应的码长分别为k1，k2，kn。因为是唯一可译码，信源符号xi和码字Wi一一对应，则平均平均码长码长为6HUST - Basis for Information Theory4 4、信息传输率与信息传输速率、信息传输率与信息传输速率7HUST - Basis for Information Theory变长无失真信源编码定理变长无失真信源编码定理o即香农第
5、一定理香农第一定理o定理定理 设离散无记忆信源为8HUST - Basis for Information Theory变长无失真信源编码定理（续）变长无失真信源编码定理（续）9HUST - Basis for Information Theory变长无失真信源编码定理理解变长无失真信源编码定理理解10HUST - Basis for Information Theory推广到普通信源推广到普通信源o变长无失真信源编码定理可以推广到平稳遍历的有记忆信源，一般离散信源或马尔可夫信源，有 其中，H为有记忆信源的极限熵o定长编码作为变长编码的特例，可统一到香农第一定理之中。11HUST - Basi
6、s for Information Theory变长编码的编码信息率变长编码的编码信息率Ro定义变长编码的编码信息率为 它表示编码后平均每个信源符号能载荷的最大信息量。o香农第一定理可表述为：香农第一定理可表述为：n若H(X)RH(X)+，就存在唯一可译的变长编码。n若RH(X)，则不存在唯一可译的变长编码。不能实现无失真的信源编码。12HUST - Basis for Information Theory信息传输率信息传输率Ro从信道角度看，信道的信息传输率信息传输率13HUST - Basis for Information Theory编码效率和剩余度编码效率和剩余度定义码的剩余度为 1
7、4HUST - Basis for Information Theory变长变长编码举例编码举例15HUST - Basis for Information Theory变长变长编码举例编码举例续续16HUST - Basis for Information Theory变长变长编码举例编码举例续续17HUST - Basis for Information Theory变长变长编码举例编码举例续续o用同样方法可进一步对信源X的三次和四次扩展信源进行编码，并求出其编码效率为：n n 1 1=0.811=0.811比特比特/ /二元码符号二元码符号n n 2 2=0.961=0.961比特比特/
8、 /二元码符号二元码符号n3=0.985比特/二元码符号n4=0.991比特/二元码符号o对于同一信源，要求编码效率都达到96，比较n变长码只需对二次扩展信源（L = 2）进行编码；n而等长码则要求L大于4.13X107 .o变长码编码效率更高，L不需很大就可以达到比较高的编码效率，而且可实现无失真编码。18HUST - Basis for Information Theory小结小结o介绍了变长码基本特征和平均码长的概念；o通过克拉夫特不等式和麦克米伦不等式，给出了构成即时码和唯一可译码时，信源符号数和码字长度之间应满足的条件；o讨论了香农第一定理：变长编码定理；19HUST - Basis
9、 for Information Theory信源编码（主要内容）信源编码（主要内容）o信源编码定理vv信源编码概念信源编码概念信源编码概念信源编码概念vv香农第一定理香农第一定理香农第一定理香农第一定理vv香农第三定理香农第三定理香农第三定理香农第三定理o信源编码方法n n离散信源编码离散信源编码离散信源编码离散信源编码n n连续信源编码连续信源编码连续信源编码连续信源编码* * * *n n相关信源编码相关信源编码相关信源编码相关信源编码* * * *n n变换编码变换编码变换编码变换编码* * * *20HUST - Basis for Information Theory限失真信源编码
10、定理限失真信源编码定理 21HUST - Basis for Information Theory对信源编码定理的统一理解对信源编码定理的统一理解o定长信源无失真编码定理o变长信源无失真编码定理（香农第一定理）o保真度准则下的信源编码定理（香农第三定理）o从编码信息率的角度，当时，则信源编码无失真或失真可控。22HUST - Basis for Information Theory信源编码（主要内容）信源编码（主要内容）o信源编码定理vv信源编码概念信源编码概念信源编码概念信源编码概念vv香农第一定理香农第一定理香农第一定理香农第一定理vv香农第三定理香农第三定理香农第三定理香农第三定理o信源
11、编码方法n n离散信源编码离散信源编码离散信源编码离散信源编码n n连续信源编码连续信源编码连续信源编码连续信源编码n n相关信源编码相关信源编码相关信源编码相关信源编码n n变换编码变换编码变换编码变换编码23HUST - Basis for Information Theory 常见的方法：o香农编码o费诺编码o霍夫曼编码o游程编码o冗余位编码变长码的编码方法变长码的编码方法24HUST - Basis for Information Theory1、香农编码、香农编码25HUST - Basis for Information Theory香农编码举例香农编码举例26HUST - Bas
12、is for Information Theory香农编码举例（续）香农编码举例（续）27HUST - Basis for Information Theory香农编码举例（续）香农编码举例（续）o由上表可以看出，一共有5个三位的代码组，各代码组之间至少有一位数字不相同，故是唯一可译码。还可以判断出，这7个代码组都属于即时码。o平均码长、信息传输率、编码信息率和编码效率28HUST - Basis for Information Theory2、霍夫曼编码、霍夫曼编码-方法方法29HUST - Basis for Information Theory霍夫曼编码举例霍夫曼编码举例30HUST -
13、 Basis for Information Theory霍夫曼编码举例（续）霍夫曼编码举例（续）o该霍夫曼码的平均码长o从编码表可以看出，霍夫曼是即时码，从右图的码树中也可以清楚看出。31HUST - Basis for Information Theory霍夫曼编码并不唯一霍夫曼编码并不唯一霍夫曼编码方法非唯一，原因：o每次对信源缩减时，赋予信源最后两个概率最小的符号，用0和1是可以任意的；o对信源进行缩减时，两个概率最小的符号合并后的概率与其它信源符号的概率相同时，这两者在缩减信源中进行概率排序时，其位置放置次序可以任意。32HUST - Basis for Information Th
14、eory另一种霍夫曼编码另一种霍夫曼编码o合并后的概率与其它信源符号的概率相同时，改变这两者在缩减信源中的排序，可以得到另一种霍夫曼编码。33HUST - Basis for Information Theory另一种霍夫曼编码（续）另一种霍夫曼编码（续）o该霍夫曼码的平均码长o编码效率与前一种霍夫曼码的效率相同。o但后一种编码的码长方差 o方差比第一种方法小，即码长变化小，简单，易实现。故在霍夫曼编码过程中，对缩减信源符号以概率重新排列时，应使合并符号尽量靠对缩减信源符号以概率重新排列时，应使合并符号尽量靠前，可使合并符号重复编码次数减少，使短码得到充分利用。前，可使合并符号重复编码次数减少
15、，使短码得到充分利用。34HUST - Basis for Information Theoryr元霍夫曼码元霍夫曼码o二进制霍夫曼码的编码方法可以很容易推广到r进制的情况。只是编码过程中构成缩减信源时，每次都是将r个概率最小的符号合并，并分别用0, 1, , (r-1)码符号表示。o例例 设有离散无记忆信源 码符号集X(0,1,2)，试构造一种三进制霍夫曼码。35HUST - Basis for Information Theoryr元霍夫曼码元霍夫曼码举例举例o编码过程见下表，其中信源s9是增补的，令其概率为零.36HUST - Basis for Information Theory r
16、元霍夫曼码元霍夫曼码举例举例（续续）r3元霍夫曼编码37HUST - Basis for Information Theory霍夫曼编码总结霍夫曼编码总结o霍夫曼编码是用概率匹配方法进行的信源编码，它有两个明显特点：o1、编码方法保证了概率大的符号对应于短、编码方法保证了概率大的符号对应于短码，概率小的符号对应于长码，充分利用了码，概率小的符号对应于长码，充分利用了短码；短码；o2、每次缩减信源的最后二个码字总是最后、每次缩减信源的最后二个码字总是最后一位不同，从而保证了霍夫曼码是即时码。一位不同，从而保证了霍夫曼码是即时码。38HUST - Basis for Information The
17、ory3、费诺编码、费诺编码39HUST - Basis for Information Theory费诺编费诺编码码举例举例40HUST - Basis for Information Theory费诺编费诺编码码举例举例（续续）41HUST - Basis for Information Theory4、游程编码与游程变换、游程编码与游程变换o前面三种方法针对无记忆信源，对于有记忆信源的编码效率不高，一般采用其它编码。如：游程编码。o二元序列：000101110010001n“0”游程、“1”游程；游程长度L(0)、L(1) o多元序列/游程长度序列：31132131oo游程变换游程变换游
18、程变换游程变换规定游程序列从“0”开始，是可逆变换。它减弱了二元序列的相关性。对变换后的多元序列可采用其它编码方法，比如：哈夫曼编码。o多元序列也可以变换成游程序列，但是需要增加标志位，可能会抵消压缩编码得到的好处，意义不大。42HUST - Basis for Information Theory游程序列的概率特性游程序列的概率特性o若二元序列的概率特性已知，可计算出游程序列的概率特性。o假设二元序列为独立序列，则n0游程长度概率游程长度概率：pL(0)= p0 L(0)-1 p1 ;n0游程长度的熵游程长度的熵：HL(0)=H(p0 )/ p1 ; n0游程序列的平均长度游程序列的平均长度
19、：l0=EL(0)=1/ p1npL(1)= p1 L(1)-1 p0 ; HL(1)=H(p0 )/ p0 ; l1=EL(1)=1/ p0op0和p1分别为二元序列中 “0”和“1”的概率nH(X) = HL(0)+ HL(1) / (l0+l1) = H(p0 ) = H(p1 )43HUST - Basis for Information Theory0/ 1游程长度的概率：游程长度的概率：pL(0)、 pL(1)44HUST - Basis for Information Theory平均游程长度：平均游程长度：EL(0)、 EL(1)45HUST - Basis for Infor
20、mation Theory0/ 1游程长度的熵：游程长度的熵：HL(0)/ HL(1)46HUST - Basis for Information Theory原二元序列的熵原二元序列的熵H(X)o0游程序列的熵与1游程序列的熵之和除以它们的平均游程长度之和。nH(X) = HL(0)+ HL(1) / (l0+l1) = H(p0 ) /p1 + H(p0 ) /p0 / (1/ p1 +1/ p0 ) = H(p0 ) = H(p1 ) o游程变换后符号熵没有变。游程变换后符号熵没有变。o当0游程和1游程的编码效率都很高时，采用游程编码的效率也会高。47HUST - Basis for I
21、nformation Theory相关性二元序列的游程变换相关性二元序列的游程变换o若原二元序列是二阶马氏链，由它变换而来的游程序列将也是独立序列。n0游程：10X； 1游程：01Xo对于高阶马氏链，若阶数大于2，经变换的游程序列将不再是独立序列。n如三阶马氏链：Y10X一阶马氏链n一般k阶马氏链，由之变换而来的游程序列将为k-2阶马氏链。o通过游程变换可有效的解除或减弱二元序列的相关性，再对游程长度进行编码可达到较高的编码效率。48HUST - Basis for Information Theory游程长度与码字之间的游程长度与码字之间的 码表码表o取适当值n，游程长度为1, 2, , 2
22、n-1, 2n，所有大于2n者，都按2n处理。o所有长度大于等于2n的游程，只有一个码字C，需要按右表进一步区分。o当游程长度大于或等于2n+1时，需要两个或两个以上的C 。概率小，码字长。o0游程和1游程应分别编码，建立各自的码字和码表。码字可重复， C必须不同。如： C0 或 C1游程长度 2nC之后为一个n位的自然码（ C0 或 C1）2nC00002n+1C00012n+1 -1C11112n+1 C0000 C00002n+2 -1C0000 C111149HUST - Basis for Information Theory冗余位编码（冗余位编码（Lynch-Davission）o
23、冗余位：冗余位：信源序列中不携带信息的符号，除了符号数目或所占时长外，可不必传送。n语音中的话语间歇、图像的单一背景部分。o去掉部分冗余信息可以提高通信效率。o设有多元信源序列：x 为信息位；y 冗余位nx1 , x2 ,xm1 ,y,y,y, xm1+1 , xm1+2 , xm2 ,y,y, 可用下面两个序列来代替：n冗余位序列冗余位序列：111,100,000111,111000n信息位序列信息位序列：x1 , x2 ,xm1 , xm1+1 , xm1+2 , xm2 , 50HUST - Basis for Information Theory冗余位编码思路冗余位编码思路o多元信源序
24、列分解分解：一个二元序列和一个缩短了的多元序列。o对两个序列分别编码，有效压缩信源对两个序列分别编码，有效压缩信源n如：对二元序列进行游程编码；对多元序列直接采用哈夫曼编码。o要求同时传送两个序列，才能在接收端实时恢复出原来的多元信源序列。n实际应用有困难，通常采用分帧传送的方式采用分帧传送的方式。51HUST - Basis for Information Theory分帧传送冗余位序列：分帧传送冗余位序列：L-D编码编码o在冗余位序列中取N个符号作为一帧，编成一个码字码字，其后就把本帧中的信息位按序排列，再取下一帧作同样处理。在接收端根据这些码字和信息序列进行译码。o每个码字码字中含有：信
25、息位的数量Q和位置信息T52HUST - Basis for Information TheoryL-D编码的译码过程编码的译码过程o收端收到Q和T后，如下译码：53HUST - Basis for Information Theory编码编码Q和和ToQ可以取0到N的各种值，共N+1种，故54HUST - Basis for Information Theory例：对一冗余位序列编例：对一冗余位序列编L-D码码o一冗余位序列：001 100000001 10000，N=15o这里Q=2，n1=3，n2=11，则55HUST - Basis for Information TheoryQ=2和
26、T=47的译码过程的译码过程o收端收到Q=2和T=47后，如下译码：56HUST - Basis for Information TheoryQ=2和T=47的译码过程的译码过程-续续57HUST - Basis for Information Theory对例题的说明对例题的说明o当Q为0或N时，相当于全0或全1序列，此时T值为0，在编码时只需编Q值，对于N=15，得0000或1111oL-D编码与哈夫曼码不同，不需要已知概率特性。也就是编成的码字与概率特性无关，而与一帧内的信息位的数目有关，即码字长度与Q有关。58HUST - Basis for Information Theory码字长
27、度与码字长度与Q的关系的关系 Q0 1 2 3 4 5 6 715 14 13 12 11 10 9 8Log(15 Q)0 3.91 6.71 8.83 10.4 11.8 12.3 12.9T的码字长度0 4 7 9 11 12 13 13码字总长度4 8 11 13 15 16 17 17压缩率r0.27 0.53 0.73 0.87 1 1.07 1.13 1.13o概率未知，无法计算熵，也无法计算编码效率，一般只能用压缩率来表达编码增益。o当Q接近N/2时，L-D编码是无效的；当Q接近0或N时，可得很小的压缩率，N很大时更有效。59HUST - Basis for Informati
28、on Theory编码方法小结编码方法小结o介绍了几种变长码的编码方法：n香农编码、哈夫曼编码和费诺编码n游程编码和冗余位编码o变长码的缺点：n1.高概率符号和低概率符号出现的不均匀与信源符号恒速输出高概率符号和低概率符号出现的不均匀与信源符号恒速输出的矛盾的矛盾。信道可能无信息可送，或信息溢出而丢失。（需要很需要很大的缓存大的缓存）n2.差错的扩散。差错的扩散。因为它采用异前置码来分解码字，一旦传送中出现误码，则某个码字的前置部分可能成为另一个码字，因而错译为另一个符号。（需要采用差错控制需要采用差错控制）60HUST - Basis for Information Theory本章小结本章小结o介绍了变长码基本特征和平均码长的概念；o通过克拉夫特不等式和麦克米伦不等式，给出了为构成唯一可译码，信源符号数和码字长度之间应满足的条件；o给出了一种唯一可译码的判别准则；o讨论了香农第一定理：变长编码定理；o学习了几种变长码的编码方法，包括：香农编码、费诺编码和霍夫曼编码。61
