《信息理论与编码》课程教学课件（讲稿）第4章 离散无记忆信源无失真编码 4.6 几种实用的无失真信源编码

G4.6几种实用的无失真信源编码4.6.1游程编码4.5介绍的几种无失真信源编码，主要适用于多元信源和无记忆信源。当信源给定时，可以证明霍夫曼码（huffman）是最佳码。当信源有记忆时，特别是二元相关信源，必须对其N次扩展信源编码才能提高编码效率。由于扩展信源符号数剧增，使编译码设备复杂。2014/6/30信应理论身维口

2014/6/30 1 2014/6/30 信息理论与编码 1 4.6.1 游程编码 4.5介绍的几种无失真信源编码，主要 适用于多元信源和无记忆信源。 当信源给定时，可以证明霍夫曼码（ huffman）是最佳码。 当信源有记忆时，特别是二元相关信源 ，必须对其N次扩展信源编码才能提高编码 效率。由于扩展信源符号数剧增，使编译码 设备复杂。 4.6 几种实用的无失真信源编码

C4.6几种实用的无失真信源编码游程编码是一种针对相关信源的有效编码方法，已在图文传真、图像通信等实际通信工程中得到应用。实际工程技术中常常将游程编码与其它编码方法结合，以获得更好的压缩效果。如MH编码。游程（Run Length）：信源输出的符号序列中，连续重复出现的字符串。2014/6/30信应理论身维口

2014/6/30 2 2014/6/30 信息理论与编码 2 游程编码是一种针对相关信源的有效编 码方法，已在图文传真、图像通信等实际通 信工程中得到应用。 实际工程技术中常常将游程编码与其它 编码方法结合，以获得更好的压缩效果。如 MH编码。 游程（Run Length）：信源输出的符号序列 中，连续重复出现的字符串。 4.6 几种实用的无失真信源编码

CG4.6几种实用的无失真信源编码例：若信源的字符序列为BBBBBBBBBBXXXXXXXXXAAAAAAUUUUUUUUUUUUU游程编码需要表示的要素：符号和游程长度，此外还需要用来区分以上两者的标识符，如用#作为标识符。游程编码格式：符号码标识码游程长度B#10X#9A#6U#13字符数量由38个减少为14个。游程编码可以缩短数据2014/6/30信应理论身维理

2014/6/30 3 2014/6/30 信息理论与编码 3 例：若信源的字符序列为 游程编码需要表示的要素： 符号和游程长度，此外还需要用来区分以 上两者的标识符，如用#作为标识符。 游程编码格式: 字符数量由38个减少为14个。游程编码 可以缩短数据。 4.6 几种实用的无失真信源编码 BBBBBBBBBB XXXXXXXXXAAAAAA UUUUUUUUUU UUU B#10 X #9A#6U #13 符号码 标识码 游程长度

G4.6几种实用的无失真信源编码对于二元信源，输出只有“0”和“1”两个符号。例：序列00010011111100000001..由于只有两种信源符号，若规定序列从“0”游程开始，则可以省掉标识符。编码后：31267：（自然数）一般传输信道为二元信道，假设max[L(O),L(1)]=7，则变换后输出码字序列:011 001 010 110 111...2014/6/30信应理论导维口

2014/6/30 4 2014/6/30 信息理论与编码 4 对于二元信源，输出只有“0”和“1” 两个符号。 例：序列00010011111100000001. 由于只有两种信源符号，若规定序列从 “0”游程开始，则可以省掉标识符。 编码后：31267.（自然数） 一般传输信道为二元信道，假设 max[L(0),L(1)]=7，则变换后输出码字序列： 011 001 010 110 111. 4.6 几种实用的无失真信源编码

C4.6几种实用的无失真信源编码对游程序列还可采用变长编码，如huffman编码，这样可以进一步压缩信源。首先测定“0”游程长度和“1”游程长度的概率分布，以游程长度为元素，构造一个新的多元信源，然后再对其进行huffman编码。“0”游程长度和“1”游程长度应分别编码，建立各自的码字和码表。（MH编码)2014/6/30信应理论身维口

2014/6/30 5 2014/6/30 信息理论与编码 5 对游程序列还可采用变长编码，如 huffman编码，这样可以进一步压缩信源。 首先测定“0”游程长度和“1”游程 长度的概率分布，以游程长度为元素，构造 一个新的多元信源，然后再对其进行 huffman编码。 “0”游程长度和“1”游程长度应分 别编码，建立各自的码字和码表。（MH编 码） 4.6 几种实用的无失真信源编码

C4.6几种实用的无失真信源编码理论上游程长度从0至无穷大，实际中建立一个一一对应的码表很困难。一般来讲，很长的游程出现的概率很小，当游程趋近于无穷时，出现的概率趋近于0。实际应用中，对长游程不严格按照huffman编码进行，而采用截断处理。将大于一定长度的游程统一用定长码编码。2014/6/30信应理论身维口

2014/6/30 6 2014/6/30 信息理论与编码 6 理论上游程长度从0至无穷大，实际中 建立一个一一对应的码表很困难。 一般来讲，很长的游程出现的概率很 小，当游程趋近于无穷时，出现的概率趋近 于0。 实际应用中，对长游程不严格按照 huffman编码进行，而采用截断处理。将大 于一定长度的游程统一用定长码编码。 4.6 几种实用的无失真信源编码

G4.6几种实用的无失真信源编码截断处理的方法：（1）选取一个适当的n值，将游程长度定为1,2，.，2n-1，2n。对于游程大于2n的，都要游程为2n的码字来处理。（2）将2n个游程按概率大小进行huffman编码，设游程为2n 的码字为C。（3）对大于2n以上的游程编码。2014/6/30信应理论导维旧

2014/6/30 7 2014/6/30 信息理论与编码 7 截断处理的方法： （1）选取一个适当的n值，将游程长度定为 1,2，.，2 n -1，2 n 。对于游程大于 2 n 的， 都要游程为2 n 的码字来处理。 （2）将2 n 个游程按概率大小进行huffman编 码，设游程为2 n 的码字为C。 （3） 对大于2 n 以上的游程编码。 4.6 几种实用的无失真信源编码

G4.6几种实用的无失真信源编码例：游程在2n~2n+1 之间，用码字CA构成编码。A是n位自然码，用于区分不同游程长度。C00...00游程为 2n，码字n位C00...01游程为2n+1，码字n位游程为2n+1-1，码字C11...11n位2014/6/30信应理论身维口

2014/6/30 8 2014/6/30 信息理论与编码 8 例：游程在2 n ~2n+1 之间，用码字CA构成编码。 A是n位自然码，用于区分不同游程长度。 游程为 2 n，码字 游程为 2 n+1，码字 . 游程为2 n+1 -1，码字 4.6 几种实用的无失真信源编码 00.00 n C 位 00.01 n C 位 11.11 n C 位

T4.6几种实用的无失真信源编码游程在2n+1~2n+2 之间，用码字CA CA构成编码。游程为2n+1，码字C00...00C00...00n位n位游程为2n+2-1，码字C00...00C11...11n位n位依次类推，得到所有游程长度的唯一码字。2014/6/30信应理论身维口

2014/6/30 9 2014/6/30 信息理论与编码 9 游程在2 n+1 ~2n+2 之间，用码字CA CA构成编码。 游程为 2 n+1，码字 游程为 2 n+2 -1，码字 . 依次类推，得到所有游程长度的唯一码字。 4.6 几种实用的无失真信源编码 00.00 00.00 n n C C 位 位 00.00 11.11 n n C C 位 位

C4.6几种实用的无失真信源编码游程编码主要用于黑、白二值文件的传真游程编码常常和其它编码方法混合使用。如黑白图文传真，游程编码和huffman结合，其中背景像素（白色）用码元“0”；内容像素（黑字）用码元“1”。彩色静止图像压缩国际标准JPEG，采用游程编码、DCT和huffman的结合。2014/6/30信应理论导维口

2014/6/30 10 2014/6/30 信息理论与编码 10 游程编码主要用于黑、白二值文件的传真。 游程编码常常和其它编码方法混合使用。 如黑白图文传真，游程编码和huffman结合， 其中背景像素（白色）用码元“0”； 内容像素（黑字）用码元“1”。 彩色静止图像压缩国际标准JPEG，采用游程 编码、DCT和huffman的结合。 4.6 几种实用的无失真信源编码