信息论第讲算术编码与编码.ppt

《信息论第讲算术编码与编码.ppt》由会员分享，可在线阅读，更多相关《信息论第讲算术编码与编码.ppt（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、信息论第讲算术编码与编码现在学习的是第1页，共28页算术编码算术编码前面所讨论的无失真编码，都是建立在信源符号与码字一一对应的基前面所讨论的无失真编码，都是建立在信源符号与码字一一对应的基础上，这种编码方法通常称为础上，这种编码方法通常称为块码或分组码块码或分组码，此时信源符号一般是，此时信源符号一般是多多元元的。的。如果要对二元序列进行编码，则需采用合并信源符号方法，把二元序如果要对二元序列进行编码，则需采用合并信源符号方法，把二元序列转换成多值符号，转换时二元符号之间的相关性不予考虑，转换后列转换成多值符号，转换时二元符号之间的相关性不予考虑，转换后这些多值符号之间的相关性也不予考虑。这就

2、使信源编码的匹配原则这些多值符号之间的相关性也不予考虑。这就使信源编码的匹配原则不能充分满足，编码效率一般不高。不能充分满足，编码效率一般不高。为了克服这种局限性，需要跳出分组码范畴，为了克服这种局限性，需要跳出分组码范畴，从整个符号序列出发，采从整个符号序列出发，采用递推形式进行编码用递推形式进行编码。现在学习的是第2页，共28页 从整个符号序列出发，根据各信源序列的概率将信源序列映射到从整个符号序列出发，根据各信源序列的概率将信源序列映射到0,1) 区间上，然后选取区间内的一点（也就是一个二进区间上，然后选取区间内的一点（也就是一个二进制的小数）来表示信源序列。制的小数）来表示信源序列。算

3、术编码基本思想算术编码基本思想 设信源字母表为设信源字母表为a1, a2,概率概率p(a1)=0.6, p(a2)=0.4，将将0,1按概率比例分为区间按概率比例分为区间0,0.6,0.6,l。p(a1)p(a2)0 0.6 10 0.36 0.6 0.84 1p(a1a1)p(a1a2)p(a2a1)p(a2a2)随着序列的长度不断增加随着序列的长度不断增加,C所在区间的长度就越短所在区间的长度就越短,精精确地确定确地确定C的位置需要码长的位置需要码长也不断增加也不断增加现在学习的是第3页，共28页 设信源符号集设信源符号集A=a1,a2,an, 其相应概率分布为其相应概率分布为pi, pi

4、 0 (i=1,2, ,n), 定义信源符号的定义信源符号的为为 P1= 0; P2= p1 ; P3= p1+p2 ; 11riirpP累积概率累积概率r=1,2, ,npr = Pr+1 - Pr) 1 , 0rPP1p1P2P3P41p2p30现在学习的是第4页，共28页 当当A=0,1二元信源时，二元信源时，P1=P(0)= 0 ; P2 = P(1)= p0P(0)P(1)01p0p1二元序列的累积概率引例引例设有二元序列设有二元序列S=011，求，求S的累积概率的累积概率P(S)=p(000)+ p(001)+ p(010)现在学习的是第5页，共28页若若S后面接后面接0P(S0)

5、=p(0000)+ p(0001)+ p(0010)+p(0011)+ p(0100)+ p(0101) =p(000)+ p(001)+ p(010) =P(S)若若S后面接后面接1P(S1)=p(0000)+ p(0001)+ p(0010)+p(0011)+ p(0100)+ p(0101)+ p(0110) =P(S)+ p(0110) =P(S)+p(S) p0二元序列的累积概率P(0)=0,P(1)=p0 P(Sar)=P(S) + p(S) PrS0=0110S1=0111 p(Sar)=p(S) p(ar) p(Sar)=p(S) p(ar) P(Sar)=P(S) + p(S

6、) Pr现在学习的是第6页，共28页P(0)0P(1)1p0设符号序列设符号序列S = 011p1P(0)P(1)p(00)=p(0)P(1)P(01)p(01)P(01)P(1)P(011)p(010)=p(01)P(1)p(011)二元序列的累积概率 P(Sar)=P(S)+p(S)Pr现在学习的是第7页，共28页累积概率递推公式累积概率递推公式一般多元信源序列的累积概率递推公式一般多元信源序列的累积概率递推公式rrPSpSPaSPP)()(),(0)()()(),(),(1)(rrrapSpaSpaSAp序列的概率序列的概率(所对应区间的宽度所对应区间的宽度)递推公式递推公式SrrPSp

7、SPaSPP/)()(),(0)()/()(),(),(1)(SapSpaSpaSAprrr现在学习的是第8页，共28页实际中实际中,求序列累积概率只需两个存储器求序列累积概率只需两个存储器,起始时可令起始时可令: A() =1, P() = 0 每输入一个符号每输入一个符号,存储器存储器P和和A 就按照上式更新一次就按照上式更新一次,直至符号输入完毕直至符号输入完毕,这时存储器这时存储器P的内容即为该序列的累积概率。的内容即为该序列的累积概率。 0)()()(),(PPSpSPaSPrr，1)()()(),(),(papSpaSpaSArrr，累积概率递推公式累积概率递推公式累积概率递推计算

8、累积概率递推计算注意：计算过程中注意：计算过程中,每输入一个符号只要进行乘法和加每输入一个符号只要进行乘法和加法运算。法运算。现在学习的是第9页，共28页 通过信源符号序列累积概率计算通过信源符号序列累积概率计算,把区间分割成许多小把区间分割成许多小区间区间,不同的信源符号序列对应不同的区间为不同的信源符号序列对应不同的区间为P(S), P(S) + p(S) ，可取小区间内的一点来代表这序列。，可取小区间内的一点来代表这序列。 将符号序列的将符号序列的写成二进位小数，取小数点后写成二进位小数，取小数点后L位位,若后面有尾数若后面有尾数,就进位到第就进位到第L位，即位，即)(1logSpL算术

9、编码算术编码若若P(S) = 0.10110001，L=3 则则C = 0.110LLSP.0)(现在学习的是第10页，共28页算术编码的唯一可译性算术编码的唯一可译性由码由码C的形成方法，的形成方法，)(SPC )(1logSpL又又可知可知可知可知LSp 2)()()(SpSPLSP2)(C由此可见由此可见C必在必在)()(),(SpSPSP)()(),(SpSPSPCLSPC2)(,因而唯一可译。因而唯一可译。)(1logSpL对于长序列，对于长序列，p(S)必然很小，必然很小，L与概率倒数对数几乎相等，也与概率倒数对数几乎相等，也就是说取整造成的差别很小，因而平均码长将接近于信源熵就是

10、说取整造成的差别很小，因而平均码长将接近于信源熵H(S)现在学习的是第11页，共28页7)(1logSpL设二元无记忆信源设二元无记忆信源S=0,1,p(0)=1/4,p(1)=3/4。S=11111100，对其做算术编码。，对其做算术编码。P(S) = p(00000000) + p(00000001) + p(00000010) + + p(11111011) = 1- p(11111111)- p(11111110)- p(11111101) - p(11111100) = 1- p(111111) = 1-(3/4)6= 0.110100100111从而得从而得C = 0.110101

11、0，S的码字为的码字为1101010解：解：p(S) = p2(0)p6(1) = (1/4)2 (3/4)6例例 题题1101001%7 .928/7811. 0现在学习的是第12页，共28页+=p(1)=3/4=(0.11)2p(11)=(3/4)2=(0.1001)2+=p(0)=(1/4)=2-2p(S)p(0)p(S)右移2位现在学习的是第13页，共28页1log14( )npu设无记忆信源设无记忆信源U=a1,a2,a3,a4，其概率分布依次为，其概率分布依次为 0.5,0.25,0.125,0.125，对信源序列，对信源序列做算术编码。做算术编码。解：解：例例 题题21 1341

12、21a a a a a a a au42214( )(0.5) (0.25) (0.125)2Pu现在学习的是第14页，共28页序号uip(ui)P(ui)l(ui)C0空1001a21/41/220.102a11/81/230.1003a11/161/240.10004a31/12835/6470.10001105a41/1024567/1024100.10001101116a11/2048567/1024110.100011011107a21/81922269/4096130.10001101110108a11/163842269/4096140.10001101110100算术编码递推过

13、程算术编码递推过程 a1, a2, a3 , a40.5,0.25,0.125,0.12521 134121a a a a a a a aurrPSpSPaSP)()(),(1( )0P a 2( ) 1/2P a3( )3/4P a 4( )7/8P a现在学习的是第15页，共28页由算术编码递推表得由算术编码递推表得C = 0. 1000110111010000 ，从而从而U的码字为的码字为10001101110100 RUH)(1.75100%14/8( )0.5log0.50.25log0.252 0.125log0.1251.75H U ( )logH UnD现在学习的是第16页，共

14、28页P(0)0P(1)1p(0)译码输出序列译码输出序列 011p(1)P(0)P(1)p(00)P(01)p(01)P(01)P(1)P(011)p(010)p(011)算术译码算术译码CCC( )CP ( ) (0)Ap现在学习的是第17页，共28页对二元算术码而言，其译码过程是一系列比较过程：对二元算术码而言，其译码过程是一系列比较过程：每一步比较每一步比较 与与 ，这里，这里 为前面已译出的为前面已译出的序列串，序列串， 是序列串是序列串 对应的宽度，对应的宽度， 是序列是序列 的累的累积概率值，即为积概率值，即为 对应区间的下界限，对应区间的下界限， 是此区间是此区间内下一个输入为

15、符号内下一个输入为符号“0”所占的子区间宽度。所占的子区间宽度。译码规则为：译码规则为： 若若 ，则译输出符号为，则译输出符号为“0”； 若若 ，则译输出符号为，则译输出符号为“1”。( )CP ( ) (0)Ap( )A ( )P ( ) (0)Ap( )CP ( ) (0)Ap( )CP ( ) (0)Ap算术编码的译码算术编码的译码现在学习的是第18页，共28页算术编码的编码效率很高，当信源符号序列很长时，算术编码的编码效率很高，当信源符号序列很长时，L很大很大时，平均码长接近信源熵。时，平均码长接近信源熵。从性能上来看，算术编码具有许多优点，它所需的参从性能上来看，算术编码具有许多优点

16、，它所需的参数较少、编码效率高、编译码简单，不象哈夫曼码那数较少、编码效率高、编译码简单，不象哈夫曼码那样需要一个很大的码表。样需要一个很大的码表。算术编码在图像数据压缩标准（如算术编码在图像数据压缩标准（如JPEG）中得到广泛的）中得到广泛的应用。应用。算术编码的优点算术编码的优点现在学习的是第19页，共28页算术编码要注意的一些问题算术编码要注意的一些问题 计算精度计算精度 随着递推过程的延续，随着递推过程的延续，P(u)和和F(u)的小数位数也将逐的小数位数也将逐步增加，若不能随时输出和加以截断，运算器将步增加，若不能随时输出和加以截断，运算器将难以容纳。但有所截断必然降低精度，而精度不

17、难以容纳。但有所截断必然降低精度，而精度不够会影响译码的正确性。够会影响译码的正确性。存储器容量存储器容量 编成的码字编成的码字S的长度也是随序列的长度也是随序列u的长度增加而不断的长度增加而不断增长。若不及时输出，存储量将非常大。但若输出过增长。若不及时输出，存储量将非常大。但若输出过早，运算过程中可能还需调整已经输出的部分，那就早，运算过程中可能还需调整已经输出的部分，那就来不及了。来不及了。现在学习的是第20页，共28页 计算复杂性计算复杂性 每次递归运算都有乘法，每次递归运算都有乘法， P(ak)小数位数影响计算小数位数影响计算复杂度。在算术编码中使用的概率复杂度。在算术编码中使用的概

18、率P(ak)不一定完全不一定完全等于真实的概率分布，只要设定的分布近似于真等于真实的概率分布，只要设定的分布近似于真实分布就很有效。实分布就很有效。 自适应算术编码自适应算术编码 在实际应用中，可以在编码过程中根据输入的信源序在实际应用中，可以在编码过程中根据输入的信源序列自适应估计信源的分布，因此可以对任意概率分布列自适应估计信源的分布，因此可以对任意概率分布的信源（包含有记忆）进行编码。的信源（包含有记忆）进行编码。 上述问题现已解决，算术编码已进入实用。上述问题现已解决，算术编码已进入实用。现在学习的是第21页，共28页两位以色列研究者两位以色列研究者J. Ziv和和A. Lempel独

19、辟蹊径，完全脱离独辟蹊径，完全脱离Huffman及算术编码的设计思路，创造出了一系列比及算术编码的设计思路，创造出了一系列比Huffman编码更有效，比算术编码更快捷的通用压缩算法编码更有效，比算术编码更快捷的通用压缩算法LZ算法。算法。LZ编码编码对于统计特性确知的平稳信源，已有对于统计特性确知的平稳信源，已有Huffman编码和算术编码编码和算术编码高效编码方法，其平均码长可逼近信源的平均符号熵，而且实现高效编码方法，其平均码长可逼近信源的平均符号熵，而且实现困难不算太大，所以已进入实用。困难不算太大，所以已进入实用。要确知信源的统计特性相当困难。通用编码指在信源统计特性要确知信源的统计特

20、性相当困难。通用编码指在信源统计特性不知时，对信源进行编码，而且编码效率很高。不知时，对信源进行编码，而且编码效率很高。现在学习的是第22页，共28页Ziv和和Lempel于于1977年提出了年提出了LZ77算法。算法。1978年，二人又提年，二人又提出了改进算法，后被命名为出了改进算法，后被命名为LZ78。1984年，年，T. A. Welch提出提出了了LZ78算法的一个变种，即算法的一个变种，即LZW算法。算法。1990年后，年后，T. C. Bell等人又陆续提出了许多等人又陆续提出了许多LZ系列算法的变体或改进版本系列算法的变体或改进版本。LZ系列算法用一种巧妙的方式将字典技术应用于

21、通用数据系列算法用一种巧妙的方式将字典技术应用于通用数据压缩领域，而且，可以从理论上证明压缩领域，而且，可以从理论上证明LZ 系列算法同样可系列算法同样可以逼近信息熵的极限以逼近信息熵的极限.下面我们主要介绍下面我们主要介绍LZ78算法。算法。现在学习的是第23页，共28页12 ,KAa aa设输入信源符号序列为设输入信源符号序列为尽可能取最少个相连的信源符号，并保证各段都不相同。尽可能取最少个相连的信源符号，并保证各段都不相同。Luuuu,21iu，其中，其中编码时将此序列分成不同的段。编码时将此序列分成不同的段。分段规则：分段规则：设序列分段结果为设序列分段结果为.,321cyyyy若若i

22、j ，则必有，则必有rijayy LZ78码码LZ78编码算法是一种分段编码。编码算法是一种分段编码。由分段规则可见，字典中每一段都是前面某一段后加一个由分段规则可见，字典中每一段都是前面某一段后加一个符号。符号。现在学习的是第24页，共28页开始时，先取一个符号作为第一段，然后再继续分段。若出现有开始时，先取一个符号作为第一段，然后再继续分段。若出现有与前面相同符号时，就再取紧跟后面的一个符号一起组成一个段与前面相同符号时，就再取紧跟后面的一个符号一起组成一个段，以使与前面的段不同。，以使与前面的段不同。这些分段构成字典。这些分段构成字典。当字典达到一定大小后，再分段时就应查看有否与字典中的

23、短语相当字典达到一定大小后，再分段时就应查看有否与字典中的短语相同，若有重复就添加符号后再查看，直至与字典中短语不同为止。同，若有重复就添加符号后再查看，直至与字典中短语不同为止。由分段规则可见，字典中每一段都是前面某一段后加一个符号。由分段规则可见，字典中每一段都是前面某一段后加一个符号。则编码的码字由段号加后面一个符号组成。则编码的码字由段号加后面一个符号组成。 或者说编码码字可用两个数段号或者说编码码字可用两个数段号i 和符号序号和符号序号r 组成。组成。现在学习的是第25页，共28页 段号段号i 和符号序号和符号序号r 的表示的表示 由于由于ri，则，则 所以，对所以，对Nj编码所需的

24、比特数为编码所需的比特数为 由上式可见，各段所需的比特数是不同的，是由上式可见，各段所需的比特数是不同的，是随随j的增加而增多。的增加而增多。1,jijrK NKirKjlog(1)logjjlNKj 现在学习的是第27页，共28页设设U=a1, a2, a3, a4，信源序列为，信源序列为1213242431 14a a a a a a a a a a a a 按照分段规则，可以分为按照分段规则，可以分为1213242431 14,a a a a a a a a a a a a段号短语irNjlj编码1a10002002a201130013a1a3126401104a2a42311410115a2a4a342185100106a1a11045？001007a40335？00011符号编码表符号编码表 a1a2a3a4012300011011例例 题题28/12n 现在学习的是第28页，共28页