信息理论基础 第五章 无失真信源编码

1、第五章 无失真信源编码本章需要掌握的内容：编码的目的离散无记忆信源的定长编码离散无记忆信源的变长编码定理变长编码的Huffman编码方法信源信道信宿信源编码信道编码信源译码信道译码信源信道信宿一.信源编码第一节 信源编码和码的类型信源编码无失真信源编码限失真信源编码1.信源编码的概念编码：将携带信息的一种符号序列按照一定规则映射成另一种符号序列的变换。信源编码:根据信源的统计特性对信源发出的信息进行编码。3.编码器的数学模型信源编码器 信源发出的消息符号集输出的码字集合C（代码组） 信道的基本符号集合其中： 称为码元,或码符号2.信源编码目的 压缩信源剩余度，提高传输消息的有效性，把消息变成适

2、合信道传输的信号。Wi称为码字，如果码字由N个码元组成，则码长为N 2.二元码：3.定长码：8.非同价码：信道的基本符号集中码元个数为2 每个码元所占的传输时间不完全相同7.同价码：每个码元所占的传输时间相同6.奇异码：码中码字至少有两个相同5.非奇异码：码中所有的码字都不相同4.变长码：码中的码字长短不一码中所有码字的长度都相同二.码的类型1.分组码：将信源符号集中的每个信源组符号映射成一个固定的码字 例5-1：设有二元信道的信源编码器，其概率空间编码后的结果：信源符号Si 码1 码2 码3 码4 S1 00 0 0 0 S2 01 01 11 10 S3 10 001 00 00 S4 1

3、1 111 11 10定长码非奇异码非奇异码变长码变长码奇异码9.N次扩展码（类似N次扩展信源）举例：10.唯一可译码： 每个信源符号序列映射成一个固定的码字，并且代码组中每个码字只能唯一地被译成所对应的信源符号序列。11.即时码： 无需考虑后续的码符号即可从码符号序列中译出码字，这样的唯一可译码称为即时码，又称非延时码。*唯一可译码要成为即时码的条件： 其中任一码字都不是其他码字的前缀即时码可用树图构造：树根一阶节点二阶节点 三阶节点(终端节点)A00011010111001000111110101100011010001(1)树图的最顶部的节点称为树根，树枝的尽头称为节点;(2)每个节点的

4、分支数等于码元数，且各分支分别对应一个固定的码元，各分支伸出方向所对应的码元是统一的，如图向左伸出为0，向右伸出为1。 (3)各码字分布在码树的终端节点(即不再分支的节点)。 (4)节点一旦被分配码字，后边的枝便去掉，否则为非即时码。 有一离散无记忆信源输出为N长符号序列，信道基本符号r个，信源输出符号个数为q，则存在唯一可译码的充要条件为： 第二节 离散无记忆信源的定长编码一.离散无记忆信源的唯一可译码存在条件结论:当码长为l的码元序列的个数不小于信源输出的N长序列的个数时,才存在唯一可译码. 每个信源输出的符号序列经编码后的码字的码长至少为 ,如果小于 ,则唯一可译码不存在.平均每个信源符

5、号至少用 个码元来表示 例5-2： 英文电报有32个符号(26个字母加上6个字符),请问对信源符号进行二进制编码，要想有唯一可译码，码长至少为多少？解： r = 2, q = 32, N = 1，要想有唯一可译码，则二.定长编码定理进行长度为 的定长编码，对用码元集设离散无记忆信源的熵为H(S)，其N次扩展对于只要满足(正定理)则当N足够大时，几乎可实现无失真信源编码，此时译码差错小于。反之，若则当N足够大时，译码错误概率趋于1(编码误差任意大)（逆定理）信源为例5-3：仍以英文电报为例，当认为各符号是等概分布时的熵为 ，但是考虑相关性后英文信源的极限熵为 那么对它们进行码长为2的定长编码时，

6、各自所需的最少码符号是多少？哪种情况的信息传输率高？ 解：等概时所需的最少码符号5个，而考虑相关性时需要的最少码符号是1.4个。由此可见后一种的信息传输率高 三. 编码效率当允许错误概率小于时，信源符号序列的长度N：为自信息的方差如果为最佳编码，则例5-4：设离散无记忆信源求信源序列的长度。对S采取等长二元编码，要求编码效率允许错误概率一.变长编码的概念 概念：通过编码后的代码组中的每个码字的码长不尽相等。 要实现无失真信源编码，变长码必须是唯一可译码第三节 离散无记忆信源的变长编码提问：信源符号数和码字长度之间应该满足什么条件才能构成唯一可译码呢和即时码？要想即时译码，唯一可译码必须是即时码

7、二.克拉夫特不等式和麦克米伦不等式 设信源符号集为其分别对应码长为l1,l2,lq，则即时码存在的充要条件是：对信源进行编码，相应的码字集为码符号集为1.Kraft不等式2.McMillan不等式 在满足kraft不等式的条件下，唯一可译码存在的充要条件是： 设S0为原始码字的集合。再构造一系列集合S1,S2,Sn。构造S1,S2, Sn的方法： 1、首先考察S0中所有的码字。若码字Wj是码字Wi的前缀，即Wi = WjA，则将后缀A列为S1中的元素，S1就是由所有具有这种性质的A构成的集合。 2、当n1，则将S0于Sn-1比较，看是否S0中的码字是Sn-1的前缀，如果是，则取后缀为Sn中元素

8、，且看Sn-1中码字是否为S0中码字的前缀，如果是，则取后缀为Sn中元素，如此构成集合Sn。三.唯一可译码判断准则准则：一种码为唯一可译码的充要条件是S1,S2,中没有一个含有S0中的码字。 S0 S1 S2 S3 S4 S5 S6 S7 S8 a d eb de b ad d eb 0 c bb cde bcde ad abb bad deb bbcde结论：当N7时，Sn为空集，而在S5中包含S0中的码字，故而S0不是唯一可译码。例5-5：设消息集合中共有7个消息，分别为被编码成对应的码字，判断是否是唯一可译码。1.平均码长四.变长编码定理表示编码时，平均每个信源符号需用的码元个数。提问:

9、 平均每个码元载荷的信息量(码率)与信道的信息传输率R有什么关系?平均每个码元载荷的信息量 = 信道的信息传输率R 信源编码目的： 提高信道信息传输率R，充分利用信道信道的信息传输率R= 信道中平均每个符号所能传送的信息量2.最佳码 对于某一信源和某一码元集，若有一种唯一可译码，其平均长度 小于所有其他的唯一可译码，则称此码为最佳码(紧致码)。请问:从提高无失真信源编码的有效性角度出发，当然希望平均码长越小越好，但是是否可以无限地小？有没有限度？ 则总可以找到一种编码方法构成唯一可译码，使信源S中的每个信源符号所需的码字与平均长度满足 有一离散无记忆信源S=Si(i=1,2,q)，输出符号为q

10、个，其熵为H(S)，它的N次扩展信源其熵,若用r个码元对信源进行编码3.变长无失真信源编码定理(香农第一定理)其中， 为 中每个信源符号序列 编码所对应的码字的平均码长。 对离散信源进行适当变换，使变化后的码符号信源(作为信道的输入信源)尽可能等概分布，使每个码符号平均含的信息量最大，从而使信道的信息传输率R达到信道容量C，实现信源与信道的统计匹配。香农第一定理是香农信息论的主要定理之一： 若信息传输率R不大于信道容量C，总能对信源的输出进行适当的编码，使得在信道上能够无差错地以最大信息率C传输信息。要使信息传输率R大于C而无差错地传输信息量是不可能的。无失真信源编码的实质是： 4.编码效率和

11、码的剩余度 码的剩余度=1-编码效率: 衡量各种码的优劣码的剩余度: 衡量编码与最佳码的差距例5-6:有一离散无记忆信源 ,求对原始信源和二次扩展信源用0，1码元集进行编码后的信息传输率以及编码效率. 解:(1) 用0，1对之进行编码，有 (2)二次扩展信源为：第四节 变长编码的编码方法一.莫尔斯(Morse)编码 二.香农编码1.具体步骤: 将信源发出的q个消息符号按其概率的逆减次序排列计算第i个消息的二进制码字的码长li,并取整为了编成唯一可译码，首先计算第i个消息的累加概率根据码长li, 对的结果取小数点后li位数作为第i个消息的码字将累加概率Pi变成二进制数利用例5-7： 消息序号Si

12、 概率p(Si) logp(Si) 码长Li 累加概率pi 二进制码 S1 0.40 1.32 2 0 00 S2 0.30 1.74 2 0.40 01 S3 0.20 2.32 3 0.70 101 S4 0.10 3.32 4 0.90 1110 用0，1码符号分别代表概率最小的两个信源符号，并将这两个概率最小的信源符号合并成一个，从而得到只包含q-1个符号的新信源S1,称为缩减信号源。三.二元Huffman编码1.编码步骤将信源发出的q个信源按其概率依次从大到小排列把缩减信源S1的符号按概率从大到小排列，再将其最后两个概率最小的符号合并成一个符号，并分别用0和1码元表示，这样形成q-2

13、个符号的新信源S2。依此类推，直至信源只剩两个符号为止，并分别用“0”和“1”表示。从最后一级缩减信源开始，向前返回，得出各信源符号所对应的码符号序列，即相应码字。例5-8信源符号Si 概率p(Si) 编码过程 码字Wi 码长li S1 S2 S3 S1 0.4 S2 0.2 S3 0.2 S4 0.1 S5 0.10.40.20.40.60.210101001编码过程： 101 2000 30010 40011 4用树图检验是否为即时码0A01001110100000100011(1)每次对信号缩减时，赋予最后两个概率最小的符号 用“0”和“1”是可任意的。(2)对信源进行缩减时两个概率最小

14、的符号合并后的概率与其他符号概率相同时，可任意排序。经哈夫曼编码方法得到的码并非是唯一的,造成非唯一的原因： 码字Wi 码长l i S1 0.4 0.4 0.4 0.6 00 2 S2 0.2 0.2 0.4 0.4 10 2 S3 0.2 0.2 0.2 11 2 S4 0.1 0.2 010 3 S5 0.1 011 301010101例题5-8：A00111000101101010011即时码由此可见：结论：当进行哈夫曼编码时，为了得到质量好的码，应使合并的信源符号位于缩减信源序列尽可能高的位置，这样可充分利用短码。 r元哈夫曼码可由二元哈夫曼码的编码方法推广得到。只是编码过程中构成缩减

15、信源时，每次将r个概率最小的符号合并，并分别用0，1，r-1码元表示。 为了充分利用短码，使哈夫曼码的平均码长最短，必须是最后一个缩减信源有r个信源符号。因此，对于r元哈夫曼码，信源S的符号个数q必须满足 如果信源S的符号个数q不满足上式，则增补一些概率为0的信源符号。四.r元哈夫曼码例5-9：有一离散无记忆信源码元集X=(0,1,2)，对S进行3元哈夫曼编码。解：信源符号 概率 编码过程 码字Wi 码长li Si p(Si) S1 S2 Wi li S1 0.4 0.4 0.4 0 1 S2 0.3 0.3 0.3 2 1 S3 0.2 0.2 0.3 10 2 S4 0.05 0.05 1

16、2 2 S5 0.025 0.05 110 3 S6 0.025 111 3 S7 0 112 3210210210例5-10：某气象员报告气象状态，有四种可能的消息：晴、云、雨和雾。若每个消息是等概率分布的，那么发送每个消息最少所需的二元脉冲数是多少？又若四个消息出现的概率分别为1/4、1/8、1/8和1/2，问在此情况下消息所需的二元脉冲数是多少？如何编码？解: 当消息等概分布，对这四个消息进行二元脉冲无失真信源编码必须满足：所以l=2,得每个消息最少所需的二元脉冲数为2。 当消息不等概分布时，采用二元哈夫曼编码，可以用最少的二元脉冲来发送. 则当不等概时，平均每个消息至少用1.75个二元

17、脉冲来发送。编码：信源消息 编码过程 码字 码长雾 1/2 1/2 1/2 0 1晴 1/4 1/4 1/2 10 2云 1/8 1/4 110 3雨 1/8 111 3平均码长：例5-11：若有一信源：每秒钟发出2.66个信源符号，将此信源的输出符号送入某一个二元信道中进行传输（假设信道是无噪无损的），而信道每秒钟只传递2个二元符号。试问信源不通过编码能否直接与信道连接？若通过适当编码能否在此信道中进行无失真传输？若能连接，试说明如何编码并说明原因。每秒发2.66个信源符号，所以信源输出的信息速率为： Rt=2.66*H(S)=1.924比特/秒该信道是二元无噪无损信道，所以此信道的最大信息

18、传输率（信道容量） C=1比特/符号信道每秒只传送2个二元符号，所以信道的最大信息传输速率： Ct=2*C=2比特/秒 RtCt根据无失真信源编码定理，因为Rt2二元符号/秒所以必须考虑3次扩展信源，并对之编码.考虑3次扩展信源，并对之编码，得：二元哈夫码： 1 000 001 010 01100 01101 01110 01111平均码长：送入信道的传输速率为 0.728*2.66=1.9365二元符号/秒2二元符号/秒这时可在信道中进行无失真传输。例5-12: 一个由字母ABCD组成的字，对于传输的每个字母用两个二进制符号编码，以00表示A，01表示B，10表示C，11表示D，二进制比特间

19、隔为0.5ms，若每个字母出现概率分别为p(A)=1/8, p(B)=1/4, p(C)=1/4, p(D)=1/8,计算每秒传输的平均信息量。解：平均每个字母携带的信息量为由二进制间隔为0.5ms可得：符号速率为则每秒传输的平均信息量为1.75*R=1750bps一.游程编码1.游程编码的基本原理 游程编码是哈夫曼编码的一种改进和应用，主要用于黑白二值文件的传真。 表示背景（白色）时像素为码元“0”，表示内容（黑字）像素为码元“1”。 对大量出现的连“0”或连“1”（黑或白）像素序列在传输时，可通过像素类别（黑、白像素）加重复次数的方式来加以表示，由此思路构成的一种编码方式即是游程编码（RL

20、C）。重复出现的同类像素的长度称为游程长度（RunLength）。规定第一个游程为白游程。 第五节 几种实用的无失真信源编码方法 MH码是国际电话电报咨询委员会提出的文件、传真类一维数据压缩编码的国际标准，是由游程编码和哈夫曼编码相结合而成的一种改进型哈夫曼码.2.MH码以及应用其具体编码规则为： 游程长度在063之间时，码字直接由相应的终止码表示。 游程长度在641728之间时，码字由一个组合码加上一个终止码构成。 每行必须以白游程开始，以一个同步码EOL结束，且每页文件也必须以同步码EOL开始（用以清洗系统，防止误差扩散）。 每行游程总和必须为1728个像素，否则该行出现错误。 为了达成同

21、步操作，每行编码的传输时间最短为20ms，最长为5s；不足20ms的行，需EOL码之前填入足够的“0”码元。 连续6个EOL表示文件页传输的结束。按编码规则，一页文件传真编码的最终格式如图所示。 页首填充码页尾tTtTTTEOLEOLEOLEOL6个EOL数据数据数据数据数据其中，EOL是行同步码，其码字为0000000000001，在正常的游程编码数据中不可能出现连11个0，故EOL能够在出现突发差错时，重新建立行同步，控制差错不扩散到下一行，同时每一页结束时，转回控制（RTC）由6个EOL组成。例5-13:若传真文件某行的扫描像素序列如表所示，现用码进行编码。白游程黑游程白游程黑游程白游程

22、黑游程 码是一种改进码，与前面介绍的哈夫曼码存在的两点差异： 码的编码表是由各类文件的平均统计特性指标得到的，并且固定不变，因而多数情况下，码并非紧致码（最佳码）。 游程的码字由形成码和终止码组成，可使码字大大缩短。二.算术编码 具体编码过程如下： 从信源符号全序列出发，将各信源序列依累积概率分布函数的大小映射到,区间,将,区间分成许多互不重叠的小区间。此时每个符号序列均有一个小区间与之对应，因而可在小区间内取点来代表该符号序列。编码的码长与信源序列的概率成反比，即取码长l为p()表示信源符号序列的概率，符号表示取大于或等于该值的最小整数. 为了保证码字的唯一性，应在信源符号序列累积概率分布函数值的对应区间内取一点来表示。将此点