差错控制编码第6章无失真信源编码.ppt

《差错控制编码第6章无失真信源编码.ppt》由会员分享，可在线阅读，更多相关《差错控制编码第6章无失真信源编码.ppt（45页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、信息论与编码理论第6章 无失真信源编码6.1 编码的基本概念6.1.1 编码器和译码器符号码1码2码3码4码5u1000011u20110110110u3100000001100u411011100011000例例对码对码1，如果，如果S=u2u4u1，则，则X=0111006.1.2 码的分类符号码1码2码3码4码5u1000011u20110110110u3100000001100u411011100011000等长码：所有码子长度相同等长码：所有码子长度相同变长码：码子的长度不同变长码：码子的长度不同奇异码奇异码非奇异码非奇异码非惟一可译码非惟一可译码惟一可译码惟一可译码即时码即时码非即

2、时码非即时码（码（码1 1）（码（码2 2、码、码3 3、码、码4 4、码、码5 5）（码（码3 3）（码（码1 1、2 2、4 4、5 5）（码（码1 1、4 4）（码（码5 5）（码（码3 3）（码（码1 1、4 4、5 5）6.1.3 N次（阶）扩展码n将待编码的符号进行将待编码的符号进行N次扩展次扩展n例如下面的两个例子，例如下面的两个例子，ACD编码成为编码成为001011/0001111的形式，均为的形式，均为3阶扩展码。阶扩展码。n3次扩展符号共有次扩展符号共有43=64个个ABCD00011011ABCD0010011113次 扩展符号 3次 扩展码字 3次 扩展符号 3次 扩

3、展码字AAA000AAB0001DDB11111101AAC00001DDC111111001DDD1111111116.2 “无失真”的含义n无失真信源编码：编码时没有信息丢失，译码器可以精确恢复编码之前的消息。n无失真信源编码又叫“无损压缩”n无失真信源编码的基本问题是研究如何用最少的比特数最少的比特数去表示离散信源的熵值信源的熵值，也就是如何找出最佳编码方案最佳编码方案编码之前的信息量编码之前的信息量 =编码之后的信息量编码之后的信息量信源的信息量就是信源熵（信源的平均自信息量）信源的信息量就是信源熵（信源的平均自信息量）6.3 定长码定长码 若对若对离散单符号信源离散单符号信源U进行进

4、行定长编码定长编码，则则U存在惟一可译定长码时，必须满足存在惟一可译定长码时，必须满足 nrl 其中，其中，n是信源是信源S的的符号个数符号个数，l是定长码的是定长码的码长码长，r是码符号集中的是码符号集中的码元数码元数。【例例】在在P87的表的表中中U=u1,u2,u3,u4，可以看，可以看出出n=4。由于由于XA=0,1，其中码符号集的，其中码符号集的码元数码元数r=2。根据根据nrl，则则 llog24 故故 l26.3 定长码定长码1.若对若对单符号信源单符号信源单符号信源单符号信源S S的的的的N N次扩展源次扩展源次扩展源次扩展源S SN N进行进行定长编码定长编码定长编码定长编码

5、，则必须满，则必须满足足 nNrl 其中，其中，n是信源是信源U的符号个数，的符号个数，nN是是UN的符号个数的符号个数，l是定长码的码长，是定长码的码长，r是码符号集中的码元数。是码符号集中的码元数。2.对对上上式两边取对数，得式两边取对数，得可可见见，对对于于定定长长惟惟一一可可译译码码，平平均均每每个个信信源源符符号所需要的码元个数号所需要的码元个数至少为至少为至少为至少为loglogr rn n个个个个。平均每个信源符号所需要的码符号个数。平均每个信源符号所需要的码符号个数。二元信源二元信源N次扩展源的次扩展源的定长编码定长编码对于对于二元信源二元信源(r=2)的的N次扩展源次扩展源：

6、【含含义义】对对于于二二元元定定长长惟惟一一可可译译码码，每每个个信信源源符符号号至至少少需需要要用用logq个个二二元符号来变换。元符号来变换。【例例】1.英文电报有英文电报有32个符号个符号(26个英文字母加个英文字母加上上6个标点个标点)，即，即q=32。2.若若r=2、N=1(即对信源即对信源S进行单符号二元进行单符号二元编码编码)，得：，得：3.这就是说，为了实现无失真信源编码，这就是说，为了实现无失真信源编码，每个英文电报符号每个英文电报符号至少要用至少要用5 5位二元码位二元码符号编码符号编码。n概念：编码速率 bit/符号n编码速率的含义：平均每个信源符号用多少个二进制码符号表

7、示n编码效率：=H(U)/R，其中H(U)是扩展之前信源的熵。n编码效率的含义：每个信源符号带有的信息量（即理论上平均每个信源符号用多少个二进制码表示）除以实际上用的码符号的个数，即效率n例如：S=A,B,C,分别编码为00,01,10，等概率出现，N=2,SN=AA,CC，对SN进行二元编码，则r=2，编码方式如下，则l=4。n那么，SN的编码速率为R=(4log2)/2=2nSN的编码效率为=H(S)/R=log3/2=0.7925AAABACBABBBCCACBCC0000000100100100010101101000100110106.4 变长码变长码一、变长一、变长码编码的原理码编

8、码的原理1.在变长码编码中，码长在变长码编码中，码长li是变化的。是变化的。根据信源各个符号的统计特性，根据信源各个符号的统计特性，概概率大的符号用短码率大的符号用短码，概率小的用较概率小的用较长的码长的码，使得，使得编码后平均码长降低编码后平均码长降低，从而从而提高编码效率提高编码效率。6.4 变长码n变长码的几个衡量指标变长码的几个衡量指标平均码长：每个信源符号平均码长：每个信源符号平均需用的码元数平均需用的码元数编码效率：编码效率：信息传输率：平均每个信息传输率：平均每个码元携带的信息量码元携带的信息量6.4.2 变长码的特点n能够提高压缩效果n使信道复杂化6.4.3 惟一可译码和即时码

9、的判别n克拉夫特（克拉夫特（Kraft）不等式：对于码长分别为）不等式：对于码长分别为l1,l2,ln的的r元码，存在即时码的充要条件是元码，存在即时码的充要条件是n麦克米伦（麦克米伦（McMillan）不等式：对于码长分别为）不等式：对于码长分别为l1,l2,ln的的r元码，存在惟一可译码的充要条件是元码，存在惟一可译码的充要条件是n说明在码长选择条件上，即时码与惟一可译码一致。说明在码长选择条件上，即时码与惟一可译码一致。n码1：n码2、3：n码4、5：符号码1码2码3码4码5u1000011u20110110110u3100000001100u411011100011000奇异码：至少两

10、个符号的编码相同奇异码：至少两个符号的编码相同非奇异码：非奇异码：所有码子均不相同所有码子均不相同非惟一可译码：译码时会产生歧义非惟一可译码：译码时会产生歧义惟一可译码：惟一可译码：译码时不会产生歧义译码时不会产生歧义即时码：即时码：不需要知道下一个码子的符号就能译码不需要知道下一个码子的符号就能译码非即时码：非即时码：需要知道下一个码子的符号才能译码需要知道下一个码子的符号才能译码（码（码3 3）（码（码1 1、码、码2 2、码、码4 4、码、码5 5）（码（码1 1、码、码4 4）（码（码5 5）（码（码2 2）（码（码1 1、码、码4 4、码、码5 5）唯一可译码判别准则n命题6-1 一

11、种码是唯一可译码的充要条件是S1,S2,中没有一个含有S0中的码字。S0S1S2S3S4S5S6S7abbcdedebaddebcbcdeabbbaddebbbcde即时码的判别准则n【命题6-2】一个惟一可译码成为即时码的充要条件是其中任何一个码字都不是其他码字的前缀。6.4.4 无失真信源编码定理n无失真信源编码定理（定理无失真信源编码定理（定理6-4）就给出了平均）就给出了平均码长的取值范围。码长的取值范围。n无失真变长信源编码定理（香农第一定理）。信源UN中每个信源符号所需的平均码长满足：n或者离散无记忆信源离散无记忆信源X的的N次扩展信源次扩展信源XN的熵等于信的熵等于信源源X的熵的

12、的熵的N倍，即倍，即H(XN)=NH(X)变长信源编码定理的含义n以以r=2为例，则为例，则n说明，总可以找到一种惟一可译码，它的平均码说明，总可以找到一种惟一可译码，它的平均码长处在信源熵和信源熵加长处在信源熵和信源熵加1之间。之间。n当平均码长小于信源熵的时候，这种编码肯定不当平均码长小于信源熵的时候，这种编码肯定不是惟一可译码。是惟一可译码。n说明编码效率说明编码效率 最大是最大是100%n该定理并未给出这种惟一可译码的构造方法。该定理并未给出这种惟一可译码的构造方法。6.5 霍夫曼码6.5.1 二元霍夫曼码二元霍夫曼码的编码步骤1.将信源将信源U的的n个符号个符号ui按概率按概率p(u

13、i)从大到小排列从大到小排列2.将将两个概率最小的符号两个概率最小的符号合并成一个新符号，新符号的合并成一个新符号，新符号的概率为两个符号概率之和，得到只包含概率为两个符号概率之和，得到只包含n1个符号的个符号的缩减信源缩减信源U13.把把缩减信源缩减信源U1的符号仍按概率从大到小排列，将其中的符号仍按概率从大到小排列，将其中两个概率最小的符号合并成一个符号，形成两个概率最小的符号合并成一个符号，形成n2个符个符号的号的缩减信源缩减信源U24.依次继续，直至信源最后依次继续，直至信源最后只剩下个符号只剩下个符号为止为止5.将每次合并的将每次合并的两个信源符号两个信源符号分别用分别用0和和1码符

14、号表示码符号表示6.从从最后一级缩减信源最后一级缩减信源开始，向前返回，就得出各信源开始，向前返回，就得出各信源符号所对应的符号所对应的码符号序列码符号序列，即得各信源符号对应的码，即得各信源符号对应的码字字 例n信源熵：信源熵：n平均码长：平均码长：n编码效率：编码效率：霍夫曼编码过程例两种霍夫曼码n信源熵：信源熵：n平均码长：平均码长：n编码效率：编码效率：码长方差n这两种编码方式的平均码长和编码效率均相同，如何衡量这两种编码方式的好坏呢？n码长方差码长方差方差小意味着更接近等长码,更易于传输，所以方法(a)要优于方法(b)6.5.2 多元霍夫曼码n每次把概率最小的r个符号合并成一个新的符

15、号，并分别用0,1,(r-1)等码元表示n为了使短码得到充分利用，使平均码长最短，必须使最后一步的缩减信源有r个信源符号n因此对于r元编码，信源U符号个数n必须满足：n=(r-1)Q+rn 即要求方程n=(r-1)Q+r有解，其中Q为未知数。n当此方程没有解时，可以通过人为增加一些概率为0的符号来解决。例n三元霍夫曼编码n此时：n=5,m=3，因此n=(m-1)Q+m是有解的，解为Q=1n平均码长：n编码效率：例n四元霍夫曼编码n此时：n=5,m=4，因此n=(m-1)Q+m是无解的，需要增加2个概率为0的符号n平均码长：n编码效率：霍夫曼码的最佳性n霍夫曼码是最佳码（紧致码）n霍夫曼码是即时

16、码：任一码字都不是其他码字的前缀。6.6 算术编码n20世纪70年代末、80年代初由Rissanen、Pasco和Landon等人发展起来的编码方法n算术编码的思想：用信源符号对应的概率区间中的一个点来表示概率区间中的一个点来表示该信源符号该信源符号。n但是算术编码不是对信源符号编码，而是对N次扩展信源（信源符信源符号序列号序列）编码。n算术编码适合于小消息信源，即n较小的信源。6.6.1 算术编码基本原理为什么对信源序列编码（以霍夫曼编码为例）一次扩展二次扩展三次扩展符号abaaabbabbaaaaabababaaabbbabbbabbb概率0.70.30.490.210.210.090.3

17、430.1470.1470.1470.0630.0630.0630.027码子1010100000100110100111000100110101011编码长度11123322334444平均码长10.910.90867编码效率88.1%96.2%96.9%概率区间6.6.2 算术编码方法积累概率的递推公式n信源符号信源符号积累概率积累概率定义为定义为n信源序列信源序列S的积累概率的的积累概率的递推公式递推公式为：为：F(Sur)=F(S)+p(S)F(ur)p(Sur)=p(S)p(ur)n其中F(Sur)信源序列信源序列S添加一个新的信源符号添加一个新的信源符号ur后所得后所得到的新序列到

18、的新序列Sur的积累概率的积累概率p(S)信源序列信源序列S的概率的概率F(ur)信源符号信源符号ur的积累概率的积累概率p(Sur)信源序列信源序列S添加一个新的信源符号添加一个新的信源符号ur后所得后所得到的新序列到的新序列Sur的概率的概率p(ur)信源符号信源符号ur的概率的概率算术编码的码长n把信源序列把信源序列S的编码的编码取取前前L位二进制小数位二进制小数，若若后面有尾数就在第后面有尾数就在第L位进位位进位n如：计算出的数值为如：计算出的数值为 0.011011，且，且L=3，则，则序列序列S的二进制编码是的二进制编码是100算术编码方法）n二进制算术编码的计算步骤1.计算信源计

19、算信源符号的积累概率符号的积累概率 2.设设S（空集）（空集），F()0，p()13.计算计算序列的积累概率序列的积累概率F(Sui)和和概率概率p(Sui)4.计算计算码长码长L 5.将将F(S)写成写成二进制数二进制数的形式，取其小数点后的形式，取其小数点后前前L位位作为序列作为序列S的码字，若后面有尾数就的码字，若后面有尾数就在第在第L位位进位进位例求信源序列S=1010的算术编码1.计算信源符号的积累概率2.设S（空集），F()0，p()13.计算序列的积累概率F(Sui)和概率p(Sui)4.计算码长L 5.将F(S)写成二进制数的形式，取其小数点后前L位作为序列S的码字，若后面有尾

20、数就在第L位进位信源符号的积累概率：F(0)0，F(1)0.25序列 F(S)p(S)L 序列的码字 0 1F(1)F()p()F(1)010.25(0.01)2p(1)p()p(1)10.75(0.11)21 0.01 0.11F(10)F(1)p(1)F(0)0.010.7500.01p(10)p(1)p(0)0.750.250.001110 0.01 0.0011F(101)F(10)p(10)F(1)0.010.00110.010.010011p(101)p(10)p(1)0.00110.010.001001101 0.010011 0.001001F(1010)F(101)p(101

21、)F(0)0.010011p(1010)p(101)p(0)0.000010011010 0.010011 0.00001001 5 01010例求求S=11111100的算术编码的算术编码6.6.3 算术译码方法n（1）求出各个信源符号的概率区间和积累概率，并将码字转换成十进制小数形式；n（2）判断十进制小数所在符号区间，翻译出1个符号u；n（3）按照公式（6-13）计算出一个新的十进制小数；n （6-13）n（4）重复2、3直至全部信源序列被翻译完为止。例值所在区间译得的符号计算过程0.31250.25,110.083330,0.25)00.33330.25,110.11110,0.25)

22、06.7 LZW编码n信源统计特性未知时的无失真信源编码nLZW编码历史1977年，以色列学者年，以色列学者兰佩尔兰佩尔(A.lempel)和和奇费奇费(J.ziv)提出一种语法解析码，简称提出一种语法解析码，简称LZ编码编码1978年提出了改进算法，年提出了改进算法，LZ77和和LZ781984年，年，韦尔奇韦尔奇(T.A.Welch)将将LZ78算法修改算法修改成一种实用的算法，后定名为成一种实用的算法，后定名为LZW算法算法6.7.1 LZW基本原理基本原理nLZW编码算法的基本思想是建立一个编码算法的基本思想是建立一个编码表编码表(转换转换表表)，韦尔奇称其为，韦尔奇称其为串表串表，该

23、表将输入字符串映射，该表将输入字符串映射成成定长码字定长码字输出，通常码长设为输出，通常码长设为12bitnLZW编码算法从一个编码算法从一个空符号串表空符号串表开始工作，在产开始工作，在产生输出串的同时生输出串的同时动态更新串表动态更新串表，这样串表就对应，这样串表就对应产生压缩信源的特殊性质产生压缩信源的特殊性质n简单说，简单说，LZW算法就是将待编码信源序列进行分算法就是将待编码信源序列进行分割，每一部分编码为一个长度为割，每一部分编码为一个长度为12bit的的0-1串。串。字符串码子6.7.2 LZW编码方法编码方法1.将待编码非空字符串中的将待编码非空字符串中的所有单个字符所有单个字

24、符存入串存入串表中，并给每个符号赋一个码字值表中，并给每个符号赋一个码字值2.读入第一个输入字符，赋给读入第一个输入字符，赋给前缀串变量前缀串变量P3.读下一个输入字符，赋给读下一个输入字符，赋给扩展串变量扩展串变量S4.如果如果S为空，为空，输出输出P，停止，停止；否则执行；否则执行步骤步骤55.如果如果PS不在串表不在串表中，则将中，则将P 对应的码字值输出，对应的码字值输出，将将PS存入串表，并分配一个码字值，同时将扩存入串表，并分配一个码字值，同时将扩展字符展字符S赋给赋给P；否则；否则将将PS赋给赋给P；6.重复重复步骤步骤3例 XYXYZYXYXYXXXXXXX字符串XYZ码子12

25、31.将待编码非空字符串中的所有单个字符存入串表中，并给每个符号赋一个码字值2.读入第一个输入字符，赋给前缀串变量P3.读下一个输入字符，赋给扩展串变量S4.如果S为空，输出P，停止；否则执行步骤55.如果PS不在串表中，则将P 对应的码字值输出，将PS存入串表，并分配一个码字值，同时将扩展字符S赋给P；否则将PS赋给P；6.重复步骤3P=X S=Y1字符串XYZXY码子1234P=Y S=X2字符串XYZXYYX码子12345P=X S=Y字符串XYZXYYXXYZ码子123456P=XY S=ZP=Z S=Y字符串XYZXYYXXYZZY码子123456734字符串XYZXYYXXYZZY

26、码子1234567YXYYXYXXXXXXXXXX891011121 2 4 3 5 8 1 10 11 1P=Y S=X字符串XYZXYYXXYZZYYXY码子123456785P=YX S=Y000000000001 000000000010 000000000100000000000011 000000000101 000000001000000000000001 000000001010 0000000010110000000000016.8 本章小结n理论部分讲了编码器和译码器、码的分类、无失真的本质，以及定长码和变长码的衡量指标、特点等，变长码部分还讲了无失真信源编码定理，即香农第一定理。n方法部分讲了霍夫曼编码、算术编码、LZW编码三种编码方法。