信息论与编码理论第6章 无失真信源编码

信息论与编码理论

第6章无失真信源编码6.1编码的基本概念

6.1.1编码器和译码器符号码1码2码3码4码5u1000011u20110110110u3100000001100u411011100011000例对码1，如果S=u2u4u1，则X=0111006.1.2码的分类符号码1码2码3码4码5u1000011u20110110110u3100000001100u411011100011000等长码：所有码子长度相同变长码：码子的长度不同奇异码：至少两个符号的编码相同非奇异码：所有码子均不相同非唯一可译码：译码时会产生歧义唯一可译码：译码时不会产生歧义即时码：不需要知道下一个码子的符号就能译码非即时码：需要知道下一个码子的符号才能译码（码1）（码2、码3、码4、码5）（码3）（码1、码2、码4、码5）（码1、码4）（码5）（码2）（码1、码4、码5）6.1.3N次（阶）扩展码将待编码的符号进行N次扩展例如下面的两个例子，ACD编码成为001011/0001111的形式，均为3阶扩展码。3次扩展符号共有43=64个ABCD00011011ABCD0010011113次扩展符号3次扩展码3次扩展符号3次扩展码AAA000……AAB0001DDB11111101AAC00001DDC111111001……DDD1111111116.2“无失真”的本质无失真信源编码：编码时没有信息丢失，译码器可以精确恢复编码之前的消息。无失真信源编码又叫“无损压缩”无失真信源编码的基本问题是研究如何用最少的比特数去表示离散信源的熵值，也就是如何找出最佳编码方案编码之前的信息量=编码之后的信息量信源的信息量就是信源熵（信源的平均自信息量）6.3定长码1次扩展码有n个信源符号，r个码符号，码长l，则要求n≤rlN次扩展码要求nN≤rl两边同时取对数得到Nlogn≤llogr，因此还可以引入一个概念：编码速率

bit/符号编码速率的含义：平均每个信源符号用多少个二进制码符号表示编码效率：

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

=H(S)/R=log3/2=0.7925AAABACBABBBCCACBCC0000000100100100010101101000100110106.4变长码变长码的几个衡量指标平均码长：每个信源符号平均需用的码元数编码效率：信息传输率：平均每个码元携带的信息量符号u1u2u3u4码子010110111码集{0,1}码元数r=2（二元码）码长1233概率0.50.250.1250.125信源熵平均码长编码效率信息传输率对二元编码，R=η，但是两者的含义并不相同：如果将H(U)理解为平均每个信源符号携带的信息量，则为信息传输率R如果将H(U)理解为理论上的平均码长，则为编码效率η6.2.4变长码的特点能够提高压缩效果使信道复杂化信道要匀速传输但是变长编码使得信源不匀速解决方法：增加缓冲器符号定长码变长码u1000u20110u310110u4111116.4.3唯一可译码和即时码的判别两个不等式克拉夫特（Kraft）不等式：对于码长分别为l1,l2,…,ln的r元码，存在即时码的充要条件是麦克米伦（McMillan）不等式：对于码长分别为l1,l2,…,ln的r元码，存在唯一可译码的充要条件是这说明在码长选择的条件上，即时码与唯一可译码是一致的，唯一可译码并不比即时码有什么更宽松的条件。码1：码2、3：码4、5：符号码1码2码3码4码5u1000011u20110110110u3100000001100u411011100011000奇异码：至少两个符号的编码相同非奇异码：所有码子均不相同非唯一可译码：译码时会产生歧义唯一可译码：译码时不会产生歧义即时码：不需要知道下一个码子的符号就能译码非即时码：需要知道下一个码子的符号才能译码（码3）（码1、码2、码4、码5）（码1、码4）（码5）（码2）（码1、码4、码5）唯一可译码判别准则命题6-1一种码是唯一可译码的充要条件是S1,S2,…中没有一个含有S0中的码字。S0S1S2S3S4S5S6S7abbcdedebaddebcbcdeabbbaddebbbcde即时码的判别准则【命题6-2】

一个唯一可译码成为即时码的充要条件是其中任何一个码字都不是其他码字的前缀。即S1本身就是空集6.4.4无失真信源

编码定理信源编码中非常关心码的平均码长无失真信源编码定理（定理6-4，香农第一定理）就给出了平均码长的取值范围。无失真变长信源编码定理（香农第一定理）。离散无记忆信源U的N次扩展信源UN，其熵为H(UN)，对该信源UN进行r元编码，总可以找到一种编码方法，构成唯一可译码，使信源UN中每个信源符号所需的平均码长满足：或者其中：是N次扩展信源的平均码长X是一个离散无记忆信源则X的N次扩展信源为：其中例如：则离散无记忆信源X的N次扩展信源XN的熵等于信源X的熵的N倍，即H(XN)=NH(X)变长信源编码定理的含义以r=2，N=1为例，则这说明，总可以找到一种唯一可译码，它的平均码长处在信源熵和信源熵加1之间。而且当平均码长小于信源熵的时候，这种编码肯定不是唯一可译码。还说明编码效率

最大是100%该定理并未给出这种唯一可译码的构造方法。6.5霍夫曼码

6.5.1二元霍夫曼码1952年，霍夫曼提出，这是一种最佳码。二元霍夫曼码的编码步骤将信源U的n个符号ui按概率p(ui)从大到小排列将两个概率最小的符号合并成一个新符号，新符号的概率为两个符号概率之和，得到只包含n－1个符号的缩减信源U1把缩减信源U1的符号仍按概率从大到小排列，将其中两个概率最小的符号合并成一个符号，形成n－2个符号的缩减信源U2依次继续，直至信源最后只剩下１个符号为止将每次合并的两个信源符号分别用0和1码符号表示从最后一级缩减信源开始，向前返回，就得出各信源符号所对应的码符号序列，即得各信源符号对应的码字例信源熵：平均码长：编码效率：霍夫曼编码过程例两种霍夫曼码信源熵：平均码长：编码效率：码长方差这两种编码方式的平均码长和编码效率均相同，如何衡量这两种编码方式的好坏呢？码长方差方差小意味着更接近等长码,更易于传输，所以方法(a)要优于方法(b)两个信号均值相同，但方差不同。方差可以作为散度，用来度量信号的分散程度。6.5.2多元霍夫曼码每次把概率最小的r个符号合并成一个新的符号，并分别用0,1,…,(r-1)等码元表示为了使短码得到充分利用，使平均码长最短，必须使最后一步的缩减信源有r个信源符号因此对于r元编码，信源U符号个数n必须满足：n=(r-1)Q+r

即要求方程n=(r-1)Q+r有解，其中Q为未知数，是合并的次数。当此方程没有解时，可以通过人为增加一些概率为0的符号来解决。例三元霍夫曼编码此时：n=5,m=3，因此n=(m-1)Q+m是有解的，解为Q=1平均码长：编码效率：例四元霍夫曼编码此时：n=5,m=4，因此n=(m-1)Q+m是无解的，需要增加2个概率为0的符号平均码长：编码效率：霍夫曼码的最佳性霍夫曼码是最佳码（紧致码）霍夫曼码是即时码：任一码子都不是其他码子的前缀。6.6算术编码20世纪70年代末、80年代初由Rissanen、Pasco和Landon等人发展起来的编码方法算术编码的思想：用信源符号对应的概率区间中的一个点来表示该信源符号。但是算术编码不是对信源符号编码，而是对N次扩展信源（信源符号序列）编码。算术编码适合于小消息信源，即n较小的信源。6.6.1算术编码基本原理

为什么对信源序列编码

（以霍夫曼编码为例）一次扩展二次扩展三次扩展符号abaaabbabbaaaaabababaaabbbabbbabbb概率0.70.30.490.210.210.090.3430.1470.1470.1470.0630.0630.0630.027码子1010100000100110100111000100110101011编码长度11123322334444平均码长10.910.90867编码效率88.1%96.2%96.9%概率区间6.6.2算术编码方法

积累概率的递推公式信源符号积累概率定义为信源序列S的积累概率的递推公式为：F(Sur)=F(S)+p(S)F(ur)p(Sur)=p(S)p(ur)其中F(Sur)：信源序列S添加一个新的信源符号ur后所得到的新序列Sur的积累概率p(Sur)：新序列Sur的概率p(S)：信源序列S的概率F(ur)：

信源符号ur的积累概率p(ur)：信源符号ur的概率算术编码的码长把信源序列S的编码取前L位二进制小数，若后面有尾数就在第L位进位如：计算出的数值为

0.011011，且L=3，则序列S的二进制编码是100算术编码方法）二进制算术编码的计算步骤计算信源符号的积累概率

设S＝（空集），F(

)＝0，p(

)＝1计算序列的积累概率F(Sui)和概率p(Sui)计算码长L

将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的码字，若后面有尾数就在第L位进位信源符号的积累概率：F(0)＝0，F(1)＝0.25序列F(S)p(S)L序列的码字

01F(

1)＝F(

)＋p(

)F(1)＝0＋1×0.25＝(0.01)2p(

1)＝p(

)p(1)＝1×0.75＝(0.11)21

0.010.11F(10)＝F(1)＋p(1)F(0)＝0.01＋0.75×0＝0.01p(10)＝p(1)p(0)＝0.75×0.25＝0.001110

0.010.0011F(101)＝F(10)＋p(10)F(1)＝0.01＋0.0011×0.01＝0.010011p(101)＝p(10)p(1)＝0.0011×0.01＝0.001001101

0.0100110.001001F(1010)＝F(101)＋p(101)F(0)＝0.010011p(1010)＝p(101)p(0)＝0.000010011010

0.0100110.00001001501010例

求S=11111100的算术编码6.6.3算术译码方法（1）求出各个信源符号的概率区间和积累概率，并将码字转换成十进制小数形式；（2）判断十进制小数所在符号区间，翻译出1个符号u；（3）按照公式（6-13）计算出一个新的十进制小数；

（6-13）（4）重复2、3直至全部信源序列被翻译完为止。例值所在区间译得的符号计算过程0.3125[0.25,1]10.08333[0,0.25)00.3333[0.25,1]10.1111[0,0.25)06.7LZW编码信源统计特性未知时的无失真信源编码LZW编码历史1977年，以色列学者兰佩尔(A.lempel)和奇费(J.ziv)提出一种语法解析码，简称LZ编码1978年提出了改进算法，LZ77和LZ781984年，韦尔奇(T.A.Welch)将LZ78算法修改成一种实用的算法，后定名为LZW算法6.7.1LZW基本原理LZW编码算法的基本思想是建立一个编码表(转换表)，韦尔奇称其为串表，该表将输入字符串映射成定长码字输出，通常码长设为12bitLZW编码算法从一个空符号串表开始工作，在产生输出串的同时动态更新串表，这样串表就对应产生压缩信源的特殊性质简单说，LZW算法就是将待编码信源序列进行分割，每一部分编码为一个长度为12bit的0-1串。字符串码字6.7.2LZW编码方法将待编码非空字符串中的所有单个字符存入串表中，并给每个符号赋一个码字值读入第一个输入字符，赋给前缀串变量P读下一个输入字符，赋给扩展串变量S如果S为空，输出P，停止；否则执行步骤5如果PS不在串表中，则将P

对应的码字值输出，将PS存入串表，并分配一个码字值，同时将扩展字符S赋给P

；否则将PS赋给P

；重复步骤3例

XYXYZYXYXYXXXXXXX字符串XYZ码子1231.将待编码非空字符串中的所有单个字符存入串表中，并给每个符号赋一个码字值2.读入第一个输入字符，赋给前缀串