信息传输基础009

1、第五章 无失真信源编码5.5 实用的编码技术保存在计算机的存储介质（磁盘、光盘等）中的文本、数值、图片、声音、影像等信息，统称为计算机文件对于计算机文件一般都不允许在压缩过程中丢失信息，也就是说对于这类文件的压缩必须是“透明”的利用消息或消息序列出现概率的分布特性，使概率和码字长度匹配，叫做统计编码或概率匹配编码，统称为熵编码。对离散无记忆平稳信源，必须： 准确得到字符概率 ； 对各字符的编码长度都达到它的自信息量。iP aIf Youth，throughout all history， had a champion to stand up for it； to show a doubting

2、 world that a child can think；and， possibly， do it practically； you wouldnt constantly run across folks today who claim that a child dont know anything. - Gadsby by E.V.Wright, 1939. 无需为解压缩预先保存任何信息，整个编码是在压缩和解压缩过程中动态创建的，而且自适应编码由于其符号频率是根据信息内容的变化动态得到的，更符合符号的局部分布规律，因此在压缩效果上比静态模型好许多。自适应模型将自适应模型与霍夫曼编码结合起来

3、的问题是重建霍夫曼树是一个非常昂贵的过程。为了让自适应方案高效，有必要在每一个字符出现之后调整霍夫曼编码。直到霍夫曼编码第一次开发的 20 年之后，执行自适应霍夫曼自适应霍夫曼编码编码的算法都没有发布。即使在现在，最好的自适应霍自适应霍夫曼编码夫曼编码算法仍然相当耗时间和金钱。5.5.1 游程编码游程长度(RL: Run Length,简称游程或游长)： 由字符(或信号采样值)构成的数据流中各字符重复出现而形成的字符串的长度。用二进制码字给出形成串的字符、串的长度及串的位置等信息，以此来恢复出原来的数据流。是在控制论中对于二值图像而言是一种编码方法，对连续的黑、白像素数(游程)以不同的码字进行

4、编码。 游程长度编码(RLC)：基本的RLC压缩方法：最初出现在 IBM 3780 BYSYNC (Binary Synchronous Communication)通信协议中。基本的RLC数据结构：符号码标识码游程长度数 据 流基本的RLC的数据结构游程编码的压缩效能平均重复长度重复出现10次的压缩比重复出现20次的压缩比重复出现30次的压缩比重复出现40次的压缩比重复出现50次的压缩比41.0101.0201.0311.0421.05351.0201.0421.0641.0731.11161.0311.0641.0991.1361.17671.0421.0871.1361.1901.250

5、81.0531.1111.1761.2501.33391.0641.1361.2201.3161.429101.0751.1631.2661.3841.538基本的游程编码压缩比二值图像的编码过程 先对图像进行统计分别得出白长为 i 的 概率 PiW 和黑长为 i 的概率 PiB， 然后根据霍夫曼原则按RL出现概率来分 配码字。二值图像的RLC实为霍夫曼码的具体应用修正霍夫曼编码MH编码规则: RL=063， 用一个相应的结尾码表示 ; RL=641728，用一个组合基干码加一个补充结尾码； RL(白)=128, 补充结尾码为0(白)=00110101, 其编码为: 10010 | 00110

6、101 RL(白)=129, 补充结尾码为1(白)=000111, 其编码为: 10010 | 000111 规定每行都从白游程开始，若实际扫描由黑开始，则 需在行首加零长度白游程；每行结束要加同步码EOL。算术编码的基本原理设一个信源，它有两个符号a和b，出现的概率分别是p和1p，设有一个基准区域0，1，对它进行划分，以便与信源输出序列相对应。abp1aabap1p+p(1-p)bbabaabap2bbab图A 符号序列与区域划分示意例ab0.81aaba0.810.96bbabaaba0.64bbabaaabab0.810.960.64bbaaba0.5120.7680.9920.928b

7、bbbaaabbaab设一个信源，它有两个符号a和b，出现的概率分别是0.8和0.2，有3个符号输出时，符号序列与区域划分的对应关系。图B 3符号输出时的 符号序列与区域划分示意编码字符串 aabaa对应的区域为0.512，0.59392)该区域的二进制表示0.1000001，0.1001100 )二进制数0.1001输出编码 1001对于这个信源：对于这个信源：H（X）=0.7219Huffman编码:算术编码:%19.72%24.90平均码长 R=0.8平均码长 R=1相比Huffman编码，算术编码的编码效率有明显提高。对于长序列，理论上算术编码可以达到信源的熵。多元符号编码定理输入符号

8、串 s 取自符号集 ， mmppprrrS,2121s 后跟 ri (riS)扩展成符号串 sri ,空串记做 , 只有一个符号 ri 的序列就是 ri 。 码字刷新： F(sri) = F(s)+P(s)F(ri) 区间刷新： p(sri) = p(s)p(ri)其中:11)()(ikkispsP是符号的累积概率。初始条件为C( )=0, A( )=1和P( )=0, p( )=1 。符号串每一步新扩展的码字 C(sai) 都是由原符号串的码字 C(s) 与新区宽度 A(sai) 的算术相加而得。“算术码算术码”的由来的由来例例设某信源取自符号集 S=a,b,c,d,e,! , 各符号概率和

9、初始区间如表。字符概率累积概率区间范围a0.200,0.2)b0.10.20.2,0.3)c0.10.30.3,0.4)d0.30.40.4,0.7)e0.20.70.7,0.9)!0.10.90.9,1.0)设待编码的字符串为单词“dead”，编码器和解码器都知道区间初值为0,1。6元信源的算术编码过程C(sai),C(sai) +A(sai)A(sai)初始值0, 1)1.0编完 d 后0.4, 0.7)0.3编完 e 后0.61, 0.67)0.06编完 a 后0.61, 0.622)0.012编完 d 后0.6148, 0.6184)0.0036编完 ! 后0.61804, 0.618

10、4)0.00036编码过程如图所示编码端无需发送最后的区间范围 0.61804, 0.6184) 实际上只要发送其间的某一个值即可, 如0.6181 。解码端收到0.6181，得知区间范围为0.4, 0.7) ，立即解得第一个字符为d，此后解码区间由初始0,1)变为0.4, 0.7)。得到这一范围后，再对所有字符按照公式计算,并与最终的区间范围0.61, 0.67) 相比较,得出第二个字符为e。依此类推，解码器就唯一地解出字符串“dead！”。解码过程算术编码过程:依据字符的发生概率对码区间的分割过程(即子区间宽度与正编码字符发生概率相乘的过程)。算术解码过程:只需知道最终编码区间中的某一个值

11、就可以解码。算术编码每次递推都要做乘法，而且必须在一个信源符号的处理周期内完成，有时难以实时，为此采用了查表等许多近似计算来代替乘法。小结： 二进制编码二进制编码编码对象是二元序列编码对象是二元序列:符号概率较小者为p(L)=2-Q形式, 以右移Q位代替乘2-Q;符号概率较大者为p(H)=1-2-Q形式, 以移位和相减代替;从而算术编码的迭代公式在具体实现时的计算格式为： 码字刷新： C= C+P(ai)A 区间刷新： A= p(ai)A 有限长寄存器C实现C(s): 存在进位问题, 采用插入“填充位”解决, 对编码效 率略有影响; 有限长寄存器A来实现A(s)。实际中只能用令 S=H,L,并

12、设 p(L)=2-Q, p(H)=1-2-Q, 则P(H)=0, P(L)=1-2-Q 。 对子区间宽度A(s)做迭代运算: A(sL)=A(s)2-Q(s) (右移Q位) A(sH)=A(s)- A(sL) (X 表示X的小数点后取q位) 对码字C(s)做迭代运算： C(sH)=C(s) C(sL)=C(s)+A(sH)有限精度、不做乘法且假设Q(s)已经估计出的二进制算术编码的具体步骤如下: 初始化： , ;00.000qC 个10.111qA 个 如果A(sx)0.100, 则A、C重复左移，直到A 0.100为止(即保持A(s)的小数点后的第1位总是“1”); 如果紧靠C的小数点前有连

13、续v个“1”,则紧靠小数点前插 入1个“0”(填充位); 按上述步骤对字符串中所有字符进行迭代运算,直到最 后一个字符输出C(s)代码。参数q与Q的选择直接关系到编码器精度。例对字符串“01000101”来说，H符号是“0”，L符号“1”：取q=4，v=3和Qmax=3，并假定由某个编码模型提供的Q(s)值为(2,1,2,2,3,1,1,2),对其进行算术编码。已编码的字符串编码符号x有限精度附加操作Q(s)A(s)C(s)A(s 1)A(s 0)C (sx)空020.11110.00000.00110.11000.00000011左移1位10.1100 0.11000.00000.11000

14、.01100.01100.011001020.11000.11000.00110.10010.110001001000左移1位20.10010.11100.11001.10000.00100.01110.11000100030.11101.10000.00010.11011.1000010000100011左移1位10.11010.11001.100011.11100.01100.01111.1111010001010001001000100左移1位,填充进位10.11000.110011.1110111.11001110.11000.01100.011011.1110010001001000

15、1011左移2位20.11000.11001110.1100111101.01000.00110.10011111.0101字符串 s =“01000101” 可由最终子区间0.11110101, 0.11111)表示, 编码端传送码字“1111011” 即可，码长7位。算术编码最鲜明的特点： 效率高对于大部分黑白文件传真数据：对一个具体序列:平均编码效率约为98.5%看其概率分布是否集中2-Q附近, 在p= 2-Q处, 编码效率为100%, 实际应用中的关键问题就是要选择合适的概率模型, 使大部分条件概率接近于2-Q。基于字典的压缩方法将长度不同的符号串(短语)编码成一个个新单词, 用其形成

16、一本短语词典的索引。若单词的码长短于它所替代的短语，就实现了数据的无损压缩，而且该短语字典都是自适应生成的。LZ编码的基本原理1977 年，以色列人 Jacob Ziv 和 Abraham Lempel 发表了论文“顺序数据压缩的一个通用算法”(A Universal Alogrithem for Sequential Data Compression)。1978 年，他们发表了该论文的续篇“通过可变比率编码的独立序列的压缩”(Compression of Individual Sequences via Variable-Rate Coding)。在这两篇论文中提出的两个压缩技术被称为LZ7

17、7LZ77和LZ78LZ78。简单地说LZ码思路完全不同于从Shannon到Huffman到算术压缩的传统思路，人们将基于这一思路的编码方法称作“字典”式编码。LZ码字典式编码不但在压缩效果上大大超过字典式编码不但在压缩效果上大大超过了了Huffman编码，编码，而且易于实现，其压而且易于实现，其压缩和解压缩的速度也异常惊人缩和解压缩的速度也异常惊人。LZ编码一例英文字母和符号串编码成12位码字的压缩字符串表。符号串符号串码字码字A1AB2AN3AND4AD5Z6D7DO8DO空空9空空10空空空空11空空空空空空12空空空空空空空空13空空空空空空空空空空14空空空空空空空空空空空空1501

18、60017000180000190000120$4095LZ码的特点 能有效地利用字符出现频率冗余度、字 符重复性和高使用率模式冗余度，但通 常不能有效地利用位置冗余度； 算法是自适应的，无需有关输入数据统 计量的先验信息，运算时间正比于消息 的长度； 对每一消息的起始端的压缩效果很差， 对整段消息压缩得更好。 如果信源非均匀且冗余度特性随消息而 变动，那么消息长度远大于算法实现的 自适应范围，压缩效率就会降低。现代汉语词典中的实例LZ77的编码原理从当前压缩位置开始，考察未编码的数据，并试图在滑动窗口中找出从当前压缩位置开始，考察未编码的数据，并试图在滑动窗口中找出最长的匹配字符串，如果找到

19、，则进行步骤最长的匹配字符串，如果找到，则进行步骤2，否则进行步骤，否则进行步骤3。输出三元符号组输出三元符号组(off,len,c)。其中。其中off为窗口中匹配字符串相对窗口边界为窗口中匹配字符串相对窗口边界的偏移，的偏移，len为可匹配的长度，为可匹配的长度，c为下一个字符。然后将窗口向后滑动为下一个字符。然后将窗口向后滑动len+1个字符，继续步骤个字符，继续步骤1。输出三元符号组输出三元符号组(0,0,c)。其中。其中c为下一个字符。然后将窗口向后滑动为下一个字符。然后将窗口向后滑动len+1个字符，继续步骤个字符，继续步骤1。1984年，Terry Welch发表了名为“高性能数据

20、压缩技术”(A Technique for High-Performance Data Compression)的论文，实现了LZ78算法的一个变种 LZW。LZW保留了保留了LZ码的自适应性能，码的自适应性能，压压缩比也大致相同，其显著特点是逻辑缩比也大致相同，其显著特点是逻辑简单、硬件实现廉价、运算速度快简单、硬件实现廉价、运算速度快。LZW编码LZW算法将输入字串映射成定长(通常为12位)的码字,其串表具有“前缀性”:表中任何一个字符串的前缀字符也在表中。若由某个字符串和某个单字符K 所组成的字符串K 在表中，则 也在表中。 K 叫做前缀串的扩展字符。LZW算法描述初始化：将所有的单字符

21、串放入串表 读第一个输入字符 前缀串 Step：读入下一个输入字符K If 没有这样的K(输入已穷尽): 码字() 输出; 结束。 If K 已存在于串表中: K ; repeat Step.else K不在串表中: 码字() 输出; K 串表; K ; repeat Step.例对一个最简单的3字母字符串“ababcbababaaaaaaa”作LZW编码。字串表另一种形式a 1a 1b 2b 2c 3c 3ab 41b 4ba 52a 5abc 64c 6cb 73b 7bab 85b 8baba 98a 9aa 101a 10aaa 1110a 11aaaa 1211a 12输入符号 a

22、b ab c ba bab a aa aaa a输出符号 1 2 4 3 5 8 1 10 11 1加进表中 5 7 9 11 的新字串 4 6 8 10 12LZW算法对各种类型的计算机文件都有压缩效果:数据类型压缩比英语课文1.8Cobol文件(8位ASCII码)26倍浮 点 数 据1.0格式化的科学数据2.12.1系统登录数据2.6程序源代码2.3目标代码1.5LZW对不同数据类型的压缩结果对不同数据类型的压缩结果LZW编码待压缩的信息为DAD DADA DADDY DADO.待压缩的信息为DAD DADA DADDY DADO.待压缩的信息为DAD DADA DADDY DADO.4

23、信道及信道容量信道是指信息传输的通道，包括空间传输和时间传输。关于信道的主要问题信道的建模信道传输信息的能力在有噪信道中能不能实现可靠传输？ 4.1 信道的分类4.2 离散单符号信道的数学模型 4.2.1 离散单符号信道的数学模型 信道的输入、输出都取值于离散符号集，且都用一个随机变量来表示的信道就是离散单符号信道。条件概率 P(y/x) 描述了输入信号和输出信号之间统计依赖关系。反映了信道的统计特性。信道矩阵设离散单符号信道的输入随机变量为 ，其所有可能的取值为且 输出随机变量为Y，其所有可能的输出值为yj， 由于信道中存在干扰，因此输入符号在传输中会产生错误，这种信道干扰对传输的影响可用传

24、输概率Xix1,2, ,ir1,2, ,jsjip y xjijip y xP Yy Xx11211112222212ssrrrsrp y xp y xp y xxp y xp y xp y xxPxp y xp y xp y x二元对称信道多元信道前向概率后向概率4.2.2 信道容量的概率定义：定义： 消息在信道的传输过程中，单位时间内所传输的信息量，消息在信道的传输过程中，单位时间内所传输的信息量，称为消息在信道中的称为消息在信道中的，简称为，简称为，通常用，通常用R表示。表示。 当信息量单位用比特、时间单位为码元或符号当信息量单位用比特、时间单位为码元或符号或符号序列等所占用的时间时，信

25、息传输速率或符号序列等所占用的时间时，信息传输速率的量纲为比特的量纲为比特/码元（或比特码元（或比特/符号、比特符号、比特/符号符号序列等），通常用序列等），通常用R表示；表示； 当信息量单位用比特、时间单位为秒时，信息当信息量单位用比特、时间单位为秒时，信息传输速率的量纲为传输速率的量纲为 bit/s 或或bps（bit per second），），通常用通常用Rt表示。表示。 4.2.2 信道容量的概率噪声的存在，使得传输中的错误不可避免，但是只要传输速率低于某一个值，理论上在噪声背景下进行可靠传输(错误概率可低于任意给定值)仍然是可能的平均互信息是接收到输出符号集Y后所获得的关于输入符号

26、集X的信息量。 称为信道疑义度。而平均互信息称为信道的信息传输率。信息传输速率信道容量：进行可靠传输的最高速率 H X Y;/RI X YH XH X Y比特 符号1;tRI X Yt max;p xCI X Y二元对称信道的信道容量4.2.3 几种特殊信道的信道容量具有扩展性能的无损信道具有归并性能的无噪信道具有一一对应关系的无噪无损信道1 具有扩展性能的无噪信道 此信道的举例如右图所示。此信道的举例如右图所示。 nm，输入，输入X的符号集个的符号集个数小于输出数小于输出Y的符号集个的符号集个数。其信道矩阵如下：数。其信道矩阵如下：)/()/(00000000)/()/()/(0000000

27、0)/()/()/(3837262524131211xypxypxypxypxypxypxypxyp 虽然信道矩阵中的元素不全是虽然信道矩阵中的元素不全是“1”或或“0”，但由于每列中，但由于每列中只有一个非零元素：只有一个非零元素： 已知已知Y后，后，X不再有任何不确定度，损失熵不再有任何不确定度，损失熵 H(X/Y)=0， I(X;Y)= H(X) -H(X/Y)= H(X) 。 例如，输出端收到例如，输出端收到y2后可以确定输入端发送的是后可以确定输入端发送的是x1，收到，收到y7后可以确后可以确定输入端发送的是定输入端发送的是x3，等等。，等等。 接收到符号接收到符号Y后，对发送的符号

28、后，对发送的符号X是完全确定的，损失熵为是完全确定的，损失熵为零，但噪声熵不为零。这类信道被称为有噪无损信道。零，但噪声熵不为零。这类信道被称为有噪无损信道。 若信道的传递矩阵中每一列有一个也仅有一个非零元素时，若信道的传递矩阵中每一列有一个也仅有一个非零元素时，该信道一定是有噪无损信道，其平均互信息等于信源熵。该信道一定是有噪无损信道，其平均互信息等于信源熵。即信道容量为即信道容量为 与一一对应信道不同的是，此时输入端符号熵小于输出端与一一对应信道不同的是，此时输入端符号熵小于输出端符号熵，符号熵， H(X) m，输入，输入X的符号集个数大于输出的符号集个数大于输出Y的符号集个数。其的符号集个数。其信道矩阵如下：信道矩阵如下：100010010001001 信道矩阵中的元素非信道矩阵中的元素非“0”即即 “1” ，每行仅有一个非零元，每行仅有一个非零元素，但每列的非零元素个数大于素，但每列的非零元素个数大于1： 已知某一个已知某一个xi后，对应的后，对应的yj完全确定，信道噪声熵完全确定，信道噪声熵H(Y/X)=0。 但是收到某一个但是收到某一个yj后，对应的后，对应的xi不完全确定，信