北工大信息论第五章无失真信源编码

1、信源编码器信源编码器 信源发出的消息符号集信源发出的消息符号集输出的码字集合输出的码字集合C C（代码组）（代码组）qSSSS,.,21qWWWC,.,21 信道的基本符号集合信道的基本符号集合qxxxX,.,21ix 信源符号信源符号Si Si 码码1 1 码码2 2 码码3 3 码码4 4 S S1 1 00 0 0 0 00 0 0 0 S S2 2 01 01 11 1001 01 11 10 S S3 3 10 001 00 00 10 001 00 00 S S4 4 11 111 11 10 11 111 11 10)()()()(43214321spspspspssssPSNN

2、CSCS码信源)11,01(),(21CSSS一个分组码若对任意有限的整数一个分组码若对任意有限的整数N,N,其其N N次扩展码均为非奇异码，次扩展码均为非奇异码，则称为唯一可译码。则称为唯一可译码。 或每个信源符号序列映射成一个固定的码字，并且代码组中每或每个信源符号序列映射成一个固定的码字，并且代码组中每个码字只能唯一地被译成所对应的信源符号序列。个码字只能唯一地被译成所对应的信源符号序列。)1111,1101,0111,0101(),(221221112CSSSSSSSSS无需考虑后续的码符号即可从码符号序列中译出码字，这样无需考虑后续的码符号即可从码符号序列中译出码字，这样的唯一可译码

3、称为即时码，又称非延时码。的唯一可译码称为即时码，又称非延时码。树根树根一阶节点一阶节点二阶节点二阶节点 三阶节点三阶节点( (终端节点终端节点) )A00011010111001000111110101100011010001 为码字的长度lqrNl,rqNlqrNllog/logrqNLloglog由52log/32loglog/logrqNlqrNl)()()(2121qqNpppPS进行长度为进行长度为 的的定长编码，定长编码，rxxxX,21NS对对用码元集用码元集设离散无记忆信源设离散无记忆信源)()()(2121qqSpSpSpSSSPS的熵为的熵为H(S)H(S)，其，其N N

4、次扩展次扩展对于对于, 0, 0只要满足只要满足)(logSHrNl( (正定理正定理) )则当则当N N足够大时，几乎可实现无失真信源编码，此时译码差错足够大时，几乎可实现无失真信源编码，此时译码差错小于小于。反之，若反之，若2)(logSHrNl则当则当N N足够大时，译码错误概率趋于足够大时，译码错误概率趋于1(1(编码误差任意大编码误差任意大) )（逆定理）（逆定理）l信源为信源为symbolbitXH/5)( symbolbitXH/4 . 1)(1log)(次扩展代码组的熵次扩展信源的熵lNrlSNH)(log, 1)()(SHrNlSHSH此时最佳编码时，2iSIDN 2221

5、SHSIDNiiSID为自信息的方差为自信息的方差如果为最佳编码，如果为最佳编码，则则414321SSPS96. 0510求求信源序列的长度信源序列的长度。允许错误概率允许错误概率7222212222222222221013. 4)1 ()()(4715. 0)()(log )(2)()( )()(2)()( )()(2)()( )()(2)()()()()(/811. 0)(NSHSIDNSHppSHSHSIESIESHSHSIESHSIESHSIESHSISHSIESHSIESIDSHiiiiiiiiiiiii则根据符号比特解：第三节第三节 离散无记忆信源的变长编码离散无记忆信源的变长编码

6、 设信源符号集为设信源符号集为),(21qSSSS不等式）kraftrqili(11其分别对应码长为其分别对应码长为l1 1, ,l2 2, ,lq q，则即时码存在的充要条件是：则即时码存在的充要条件是：),(21qwwwW对信源进行编码，相应的码字集为对信源进行编码，相应的码字集为),(21rxxxX码符号集为码符号集为不等式）McMillanrqili(11 在满足在满足kraftkraft不等式的条件下，唯一可译码存在的充要条不等式的条件下，唯一可译码存在的充要条件是：件是： 设设S S0 0为原始码字的集合。再构造一系列集合为原始码字的集合。再构造一系列集合S S1 1,S,S2 2

7、, ,Sn。构造构造S S1 1,S,S2 2, , S Sn n的方法：的方法： 1 1、首先考察、首先考察S S0 0中所有的码字。若码字中所有的码字。若码字W Wj j是码字是码字W Wi i的前缀，的前缀，即即W Wi i = W = Wj jA A，则将后缀，则将后缀A A列为列为S S1 1中的元素，中的元素，S S1 1就是由所有具有就是由所有具有这种性质的这种性质的A A构成的集合。构成的集合。 2 2、当、当n1n1，则将，则将S S0 0于于S Sn-1n-1比较，看是否比较，看是否S S0 0中的码字是中的码字是S Sn-1n-1的前的前缀，如果是，则取后缀为缀，如果是，

8、则取后缀为S Sn n中元素，且看中元素，且看S Sn-1n-1中码字是否为中码字是否为S S0 0中码字的前缀，如果是，则取后缀为中码字的前缀，如果是，则取后缀为S Sn n中元素，如此构成集中元素，如此构成集合合S Sn n。 S0 S1 S2 S3 S4 S5 S6 S7 S8 S0 S1 S2 S3 S4 S5 S6 S7 S8 a d eb de b a d eb de b ad ad d eb 0 d eb 0 c bb cde bcde c bb cde bcde ad ad abb abb bad bad deb deb bbcde bbcde,7654321aaaaaaa,b

9、bcdedebbadabbadca信源符号码元/)(1qiiilspl平均每个码元载荷的信息量平均每个码元载荷的信息量 = = 信道的信息传输率信道的信息传输率R R码符号比特/)(lSHR 秒比特信道的信息传输速率/)(tlSHRt = = 信道中平均每个符号所能传送的信息量信道中平均每个符号所能传送的信息量 l 对于某一信源和某一码元集，若有一种唯一可译码，其平对于某一信源和某一码元集，若有一种唯一可译码，其平均长度均长度 小于所有其他的唯一可译码，则称此码为最佳码小于所有其他的唯一可译码，则称此码为最佳码( (紧致紧致码码) )。NrSHNLrSHN1log)(log)(则总可以找到一种

10、编码方法构成唯一可译码，使信源则总可以找到一种编码方法构成唯一可译码，使信源S S中的每中的每个信源符号所需的码字与平均长度满足个信源符号所需的码字与平均长度满足 有一离散无记忆信源有一离散无记忆信源S=SS=Si i(i=1,2,(i=1,2,q),q)，输出符号为，输出符号为q q个，其个，其熵为熵为H(S)H(S)，它的，它的N N次扩展信源次扩展信源),.,2 , 1(NiNqiS)()(SNHSHNNS其熵其熵, ,若用若用r r个码元对个码元对信源进行编码信源进行编码其中，其中， 为为 中每个信源符号序列中每个信源符号序列 编码所对应的码字的平编码所对应的码字的平均码长。均码长。N

11、LNSiNqiiiiiNpL1,)(所对应的码字的长度为所对应的平均码长中每个信源符号离散无记忆信源iNSSNL:NLN)(log)(SHrSHr变长编码定理说明：变长编码定理说明：若编码的平均码长小于信源的熵则唯一可译码不存在。同时指出：要做到无失真的信源编码，变换每个信源符号平均所需要最少的r进制码符号数，就是原始信源的熵值（以r为底的）；如果编码的平均码长小于原始信源的熵值，则唯一可译码不存在，此时，译码必然带来失真。 )(SHrrRlog当平均码长为时，编码后的信道的信息传输率此时有： 比特/符号信道的信息传输率R=无损信道的信道容量C 可知此时：R达到最大值，实现信源与信道的统计匹配

12、。 变长编码定理还表明变长编码定理还表明：在无失真信源编码中，采用扩展信源的手段，虽然可以减少每一个信源符号所需要的平均码符号数，使编码的有效性提高，但无论如何扩展，其有效性是有限度的，其极限值即是信源的熵值。rlSHlSHrlog)()(码的剩余度码的剩余度=1-=1-有一离散无记忆信源有一离散无记忆信源 , ,414321SSPSsymbolbitSH/811. 0)(1, 021SS21/1)(iiillSpl信源符号码元则811. 0)()(2lSHlSHr编码效率码元信道信息传输率/811. 0)(bitlSHR解解: :(1) (1) 161163163169221221112 S

13、SSSSSSSPS111110100用树图构造即时码为信源序列码元 /332116271611631631692l信源符号码元 /32/272/2 ll961. 0811. 0)(3227lSHr编码效率码元信道信息传输率/961. 0)(bitlSHR 为了编成唯一可译码，首先计算第为了编成唯一可译码，首先计算第i i个消息的累加概率个消息的累加概率11)(iKKiSpp 1)(log)(logiiiSplSp 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

14、 11100. 090. 01011. 070. 00110. 040. 0000. 004321pppp信源符号码符号编码的平均码长/40.2)(41iiilSpl码符号比特信道的信息传输率/796.0)(lSHR796.0log)(rlSH编码效率用用0 0，1 1码符号分别代表概率最小的两个信源符号，并将这两码符号分别代表概率最小的两个信源符号，并将这两个概率最小的信源符号合并成一个，从而得到只包含个概率最小的信源符号合并成一个，从而得到只包含q-1q-1个符个符号的新信源号的新信源S S1 1, ,称为缩减信号源。称为缩减信号源。编码对其进行二元HuffmanSSSSSPS1 . 01

15、 . 02 . 02 . 04 . 054321信源符号信源符号S Si i 概率概率p(p(Si) ) 编码过程编码过程 码字码字W Wi i 码长码长li i S1 S2 S3 S1 0.4 S2 0.2 S3 0.2 S4 0.1 S5 1010100151/2 . 2)(iiilSpl信源符号码元则平均码长0A01001110100000100011信源符号比特/123. 2)(log)()(51iiiSpSpSH码符号比特信道的信息传输率/965. 0)(lSHR965. 0)(lSHr编码效率 码字码字W Wi i 码长码长l i S1 0.4

16、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 301010101A00111000101101010011965. 0/2 . 2编码效率信源符号码元平均码长l比第一种好。由此可见，第二种质量差现在讲的哈夫曼码的方差先前讲的哈夫曼码的方16. 036. 1)()(22211222LLqiiiLllSpliE结论：结论：同，用码方差表示：而他们的质量不完全相和编码效率码长两种编码有相同的平均l r r元哈夫曼码可由二元哈夫曼码的编码方法推广得到。只元哈夫曼码可由二元

17、哈夫曼码的编码方法推广得到。只是编码过程中构成缩减信源时，每次将是编码过程中构成缩减信源时，每次将r r个概率最小的符号合个概率最小的符号合并，并分别用并，并分别用0 0，1 1，r-1r-1码元表示。码元表示。 为了充分利用短码，使哈夫曼码的平均码长最短，必须为了充分利用短码，使哈夫曼码的平均码长最短，必须是最后一个缩减信源有是最后一个缩减信源有r r个信源符号。因此，对于个信源符号。因此，对于r r元哈夫曼码，元哈夫曼码，信源信源S S的符号个数的符号个数q q必须满足必须满足为非负整数表示信源缩减的次数，其中rrq) 1( 如果信源如果信源S S的符号个数的符号个数q q不满足上式，则增

18、补一些概率不满足上式，则增补一些概率为为0 0的信源符号。的信源符号。：有一离散无记忆信源有一离散无记忆信源025. 0025. 005. 02 . 03 . 04 . 0654321SSSSSSPS码元集码元集X=(0,1,2)X=(0,1,2)，对对S S进行进行3 3元哈夫曼编码元哈夫曼编码。0)(72323) 1(77SpSqqrrrq则增补信源符号信源符号 概率概率 编码过程编码过程 码字码字W Wi i 码长码长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

19、.05 0.05 12 2 S5 0.025 0.05 110 3 S6 0.025 111 3 S7 0 112 321021021061/35. 1)(iiilSpl信源符号码元其平均码长霍夫曼编码的特点：霍夫曼编码的特点： 1）由于霍夫曼编码总是以最小概率相加的方法来缩减参与皮埃对的概率个数，因此概率越小，对缩减的贡献越大，其对应消息的码字也越长。2）最小概率相加的方法使得编码不具有唯一性，尤其是碰到存在几个消息符号有着相同概率的情况，将会有多种路径选择，即既具有多种可能的代码组集合。3）尽管对同一信源存在着多种结果的霍夫曼编码，但它们的平均码长几乎都是相等的，因为每一种路径选择都是使用

20、最小概率相加的方法，其实质都是遵循最佳编码的原则，因此霍夫曼编码是最佳编码。 霍夫曼编码存在的问题霍夫曼编码存在的问题： 1）霍夫曼编码要求信源消息概率已知或可估计。由于初始信源不可能总是统计好了概率，为此编码之前必须先估算信源的统计特性。在信源具有记忆性能并用霍夫曼编码来表示信源的扩展输出时，概率的估计很耗费时间。2）霍夫曼编码是建立在编码器和译码器都知道码树结构的基础上的，如果信源消息数目变大，则树型结构的大小和算法的复杂性会呈指数规律增加。 例例5-105-10：待编码的字符序列为：abaaaabaabaaabbbbbbbabbbbbaababaababa.,试用Lemple-Ziv方法

21、给出编码结果。 编码结果0a0b1a3b4a4b2b7b1b8b5b11b地址123456789101112码段内容abaaaabaabaaabbbbbbbabbbbbaababaababa由此可知：Lemple-Ziv编码利用了已编码信息进行当前的编码，编码结果是等长码，编码过程就是建立码地址和将待编码消息序列分段的过程，所有的码段内容都是不同的。 ：若有一信源：若有一信源：每秒钟发出每秒钟发出2.662.66个信源符号，将此信源的输出符号送入某一个二个信源符号，将此信源的输出符号送入某一个二元信道中进行传输（假设信道是无噪无损的），而信道每秒钟只元信道中进行传输（假设信道是无噪无损的），而

22、信道每秒钟只传递传递2 2个二元符号。个二元符号。2 .08 .0)(21sssps 04. 016. 016. 064. 0)(2212211122sssssssssps信源符号二元符号符号序列二元符号/78. 0/56. 12ll008. 0032. 0032. 0032. 0128. 0128. 0128. 0512. 0)(22212221211222112121111133sssssssssssssssssssssssssps1 000 001 010 01100 01101 01110 01111信源符号二元符号符号序列二元符号/728. 0/184. 23ll一一. .游程编码游

23、程编码1.1.游程编码的基本原理游程编码的基本原理 游程编码是哈夫曼编码的一种改进和应用，主要用于黑白二游程编码是哈夫曼编码的一种改进和应用，主要用于黑白二值文件的传真。值文件的传真。 表示背景（白色）时像素为码元表示背景（白色）时像素为码元“0 0”，表示内容（黑字），表示内容（黑字）像素为码元像素为码元“1 1”。 对大量出现的连对大量出现的连“0 0”或连或连“1 1”（黑或白）像素序列在传（黑或白）像素序列在传输时，可通过像素类别（黑、白像素）加重复次数的方式来加输时，可通过像素类别（黑、白像素）加重复次数的方式来加以表示，由此思路构成的一种编码方式即是以表示，由此思路构成的一种编码方

24、式即是。重复出现的同类像素的长度称为重复出现的同类像素的长度称为。规定第一个游程为白游程。规定第一个游程为白游程。 第五节第五节 实用的信源编码方法实用的信源编码方法 MH MH码是国际电话电报咨询委员会提出的文件、传真类一维数据压缩码是国际电话电报咨询委员会提出的文件、传真类一维数据压缩编码的国际标准，是由游程编码和哈夫曼编码相结合而成的一种改进型编码的国际标准，是由游程编码和哈夫曼编码相结合而成的一种改进型哈夫曼码哈夫曼码. .其具体编码规则为：其具体编码规则为： 游程长度在游程长度在0 06363之间时，码字直接由相应的终止码表示。之间时，码字直接由相应的终止码表示。 游程长度在游程长度

25、在646417281728之间时，码字由一个形成（组合之间时，码字由一个形成（组合) )码加上一个终止码码加上一个终止码构成。构成。 每行必须以白游程开始，以一个同步码每行必须以白游程开始，以一个同步码EOLEOL结束，且每页文件也必须以同结束，且每页文件也必须以同步码步码EOLEOL开始（用以清洗系统，防止误差扩散）。开始（用以清洗系统，防止误差扩散）。 每行游程总和必须为每行游程总和必须为17281728个像素，否则该行出现错误。个像素，否则该行出现错误。 为了达成同步操作，每行编码的传输时间最短为为了达成同步操作，每行编码的传输时间最短为20ms20ms，最长为，最长为5s5s；不足；不

26、足20ms20ms的行，需的行，需EOLEOL码之前填入足够的码之前填入足够的“0 0”码元。码元。 连续连续6 6个个EOLEOL表示文件页传输的结束。表示文件页传输的结束。按编码规则，一页文件传真编码的最终格式如图所示。按编码规则，一页文件传真编码的最终格式如图所示。 页首填充码页尾tTtTTTEOLEOLEOLEOL6个EOL数据数据数据数据数据其中，其中，EOLEOL是行同步码，其码字为是行同步码，其码字为00000000000010000000000001，在正常的，在正常的游程编码数据中不可能出现连游程编码数据中不可能出现连1111个个0 0，故，故EOLEOL能够在出现突发能够在

27、出现突发差错时，重新建立行同步，控制差错不扩散到下一行，同时差错时，重新建立行同步，控制差错不扩散到下一行，同时每一页结束时，转回控制（每一页结束时，转回控制（RTCRTC）由）由6 6个个EOLEOL组成。组成。若传真文件某行的扫描像素序列如表所示，现用码若传真文件某行的扫描像素序列如表所示，现用码进行编码。进行编码。白游程白游程黑游黑游程程白游程白游程黑游程黑游程白游程白游程黑游程黑游程 码是一种改进码，与前面介绍的哈夫曼码存在的两点差码是一种改进码，与前面介绍的哈夫曼码存在的两点差异：异： 码的编码表是由各类文件的平均统计特性指标得到的，码的编码表是由各类文件的平均统计特性指标得到的，并且固定不变，因而多数情况下，码并非紧致码（最佳码）。并且固定不变，因而多数情况下，码并非紧致码（最佳码）。 游程的码字由形成码和终止码组成，可使码字大大缩短。游程的码字由形成码和终止码组成，可使码字大大缩短。具体编码过程如下：具体编码过程如下： 从信源符号全序列出发，将各信源序列依累积概率分布从信源符