第4章离散无记忆信源无失真编码4.1基本要求通过本章学习，了解信源编码的基本术语和基本概念，掌握码的唯一可译性、码树和Kraft不等式等重要概念、定长无失真编码定理及其思想、变长编码定理（香农第一定理及其思想、三种重要的变长编码方法：霍夫曼编码、费诺编码和香农编码。掌握几种实用的无失真信源编码方法：游程编码、算术编码和基于字典的编码。4.22学习要点4.2.1信源编码的基本术语码元：信道能够传送的符号x称为码元。码元集：所有码元组成的集合X={2"x）称为码元集。信源编码：把信源U输出的符号u,变换成码元序列w,。码字：码元序列w,称为码字。码或码字集：所有码字组成的集合W={w,W2，"wg）称为码或码字集。码长：码字w,所含码元的个数称为该码字的码长，记为l，单位是“码元/符号”或“r进制单位/符号”。定长码：如果所有码字均有相同的码长1，即l,=l，=…=l=1，则称为定长码。变长码：不是所有码字的码长均相同的编码，称为变长码。平均码长I：对码W中所有码字的码长求统计平均，得平均码长T。T-ZP(w,),=ZP(u,),(4.1)码元/符号i=11=1平均码长「小说明平均一个码元所携带的信息量大，信息的允余就小。编码后的信息率：编码后平均一个码元携带的信息量即为编码后的信息率，记为R。H(U)bit/码元(4.2)R= H(X)=A编码效率：定义编码后的实际信息率与编码后的最大信息率之比为编码效率，记为n。。118
118 第 4 章 离散无记忆信源无失真编码 4.1 基本要求 通过本章学习，了解信源编码的基本术语和基本概念，掌握码的唯一可译性、码树和 Kraft 不等式等重要概念、定长无失真编码定理及其思想、变长编码定理（香农第一定理） 及其思想、三种重要的变长编码方法：霍夫曼编码、费诺编码和香农编码。掌握几种实用的 无失真信源编码方法：游程编码、算术编码和基于字典的编码。 4.2 学习要点 4.2.1 信源编码的基本术语 码元：信道能够传送的符号 i x 称为码元。 码元集：所有码元组成的集合 1 2 X {,} r xx x 称为码元集。 信源编码：把信源U 输出的符号ui 变换成码元序列 wi 。 码字：码元序列 wi 称为码字。 码或码字集：所有码字组成的集合 1 2 { , , } W ww w q 称为码或码字集。 码长：码字 wi 所含码元的个数称为该码字的码长，记为 i l ，单位是“码元/符号”或“ r 进 制单位/符号”。 定长码：如果所有码字均有相同的码长l ，即 1 2 q ll ll ，则称为定长码。 变长码：不是所有码字的码长均相同的编码，称为变长码。 平均码长 l ：对码W 中所有码字的码长求统计平均，得平均码长 l 。 1 1 ( ) () q q ii ii i i l Pwl Pu l 码元/符号 （4.1） 平均码长 l 小说明平均一个码元所携带的信息量大，信息的冗余就小。 编码后的信息率：编码后平均一个码元携带的信息量即为编码后的信息率，记为 R 。 ( ) ( ) H U R HX l bit /码元 （4.2） 编码效率：定义编码后的实际信息率与编码后的最大信息率之比为编码效率，记为c
RH(X)H(U)/TH(U)(4.3)n. =TlogrRmaxH max(X)logr码的允余度：。=1-n。。4.2.2信源编码的基本概念4.2.2.1奇异码和非奇异码含有相同码字的码称为奇异码，否则称为非奇异码。4.2.2.2续长码和非续长码任一码字都不是另一码字的续长（加长），这种码称为非续长码：有些码字是在另一些码字后面添加码元（续长）得来的，称为续长码。4.2.2.3即时码码字的最后一个码元出现时，译码器能立即判断一个码字已经结束并译码，这种码称为即时码或立即码。4.2.2.4唯一可译码（UDC，UniquelyDecodableCode）码字组成的任意有限长码字序列可被译成唯一的信源符号序列。4.2.2.5各种码之间的关系奇异码非唯一可译码信源编码非奇异码『定长唯一可译码变长即时码（非续长码）和非即时码（部分续长码）4.2.2.6Kraft不等式对于任一r进制非续长码（或唯一可译码），各码字的码长l，，i=1,2，"，9，必须满足Kraft不等式：rs(4.4)反过来，若上式成立，就一定能构造一个r进制非续长码（或唯一可译码）。4.2.3定长无失真编码定理用r元符号表对离散无记忆信源U的次扩展信源进行定长编码，N长符号序列对应的119
119 max max () () () ( ) log log c R H X HU l HU R H X r lr （4.3） 码的冗余度： 1 c c 。 4.2.2 信源编码的基本概念 4.2.2.1 奇异码和非奇异码 含有相同码字的码称为奇异码，否则称为非奇异码。 4.2.2.2 续长码和非续长码 任一码字都不是另一码字的续长（加长），这种码称为非续长码；有些码字是在另一些 码字后面添加码元（续长）得来的，称为续长码。 4.2.2.3 即时码 码字的最后一个码元出现时，译码器能立即判断一个码字已经结束并译码，这种码称 为即时码或立即码。 4.2.2.4 唯一可译码（UDC，Uniquely Decodable Code） 码字组成的任意有限长码字序列可被译成唯一的信源符号序列。 4.2.2.5 各种码之间的关系 奇异码 非唯一可译码 信源编码 非奇异码 定长 唯一可译码 变长即时码（非续长码）和非即时码（部分续长码） 4.2.2.6 Kraft 不等式 对于任一 r 进制非续长码（或唯一可译码），各码字的码长 i l ，i q 1,2, , ，必须满足 Kraft 不等式： 1 1 i q l i r （4.4） 反过来，若上式成立，就一定能构造一个 r 进制非续长码（或唯一可译码）。 4.2.3 定长无失真编码定理 用 r 元符号表对离散无记忆信源U 的次扩展信源进行定长编码， N 长符号序列对应的
码长为l，若对于任意小的正数6，有不等式>H(U)+(4.5)Nlogr就几乎能做到无失真编码，且随着序列长度N的增大，译码差错率趋于0。反过来，若<H(U)-28(4.6)N-logr就不可能做到无失真编码，且随着N的增大，译码差错率趋于1。4.2.4无失真变长编码定理（香农第一定理）用r元符号表对离散无记忆信源U的N次扩展信源进行变长编码，记N长符号序列对应的平均码长为1w，那么，要做到无失真编码，平均码长必须满足≥H,(U)(4.7)N另一方面，一定存在唯一可译码，其平均码长满足<H,(U)+1(4.8)NN信源无失真变长编码定理是信息理论的重要定理，它给出了信源有效编码的基本界限。信源序列长度N趋于无穷时平均码长的极限：lim/=limk(4.9)=H(U)N→NN→编码效率的极限为H(U)H,(U)2=100%limlim n。= llim(4.10)1N-TlogrN→00N→a4.2.5变长编码方法4.2.5.1霍夫曼编码（Huffman）霍夫曼编码是1952年由霍夫曼提出，是一种非续长码，其平均码长最短，因此是最佳编码。1）二进制霍夫曼编码编码过程如下：（1）将信源符号按概率大小排序；（2）对概率最小的两个符号求其概率之和，同时给两符号分别赋予码元“0”和“1”120
120 码长为 Nl ，若对于任意小的正数 ，有不等式 ( ) log Nl H U N r （4.5） 就几乎能做到无失真编码，且随着序列长度 N 的增大，译码差错率趋于 0。反过来，若 ()2 log Nl H U N r （4.6） 就不可能做到无失真编码，且随着 N 的增大，译码差错率趋于 1。 4.2.4 无失真变长编码定理（香农第一定理） 用 r 元符号表对离散无记忆信源U 的 N 次扩展信源进行变长编码，记 N 长符号序列对 应的平均码长为 Nl ，那么，要做到无失真编码，平均码长必须满足 ( ) N r l H U N （4.7） 另一方面，一定存在唯一可译码，其平均码长满足 1 ( ) N r l H U N N （4.8） 信源无失真变长编码定理是信息理论的重要定理，它给出了信源有效编码的基本界限。 信源序列长度 N 趋于无穷时平均码长的极限： lim lim ( ) N r N N l l HU N （4.9） 编码效率的极限为 ( ) ( ) lim lim lim 100% log r c NN N H U H U lr l （4.10） 4.2.5 变长编码方法 4.2.5.1 霍夫曼编码（Huffman） 霍夫曼编码是 1952 年由霍夫曼提出，是一种非续长码，其平均码长最短，因此是最佳 编码。 1）二进制霍夫曼编码 编码过程如下： （1）将信源符号按概率大小排序； （2）对概率最小的两个符号求其概率之和，同时给两符号分别赋予码元“0”和“1”；
（3）将“概率之和”当作一个新符号的概率，与剩下符号的概率一起，形成一个缩减信源，再重复上述步骤，直到“概率之和”为1为止；（4）按上述步骤实际上构造了一个码树，从树根到端点经过的树枝即为码字。霍夫曼编码构造了一个非续长码，采用概率匹配方法来决定各码字的码长，概率大的符号对应于短码，概率小的符号对应于长码，从而使平均码长最短，但编出的码字并不唯一。2）r进制霍夫曼编码对于r进制霍夫曼编码，信源符号数q应满足(4.11)q=(r-1)o+r其中θ为信源缩减的次数。可通过给信源添加概率为零的符号满足上式。4.2.5.2费诺编码（Fano）费诺编码也是构造一个码树，因此编出的码也是非续长码，但不一定是最佳码。编码步骤如下：（1）将信源符号按概率从大到小排序：（2）将信源符号分成2组，使2组信源符号的概率之和尽量接近，并给2组信源符号分别赋码元“0”和“1”；（3）把各小组的信源符号再细分为2组并赋码元，方法与第一次分组相同：（4）继续分组，直到每一小组只含一个信源符号为止：（5）由此即可构造一个码树，所有终端节点上的码字组成费诺码。费诺编码的平均码长比霍夫曼编码略长，编码效率稍有下降。一般来讲，费诺编码不是平均码长最短意义下的最佳编码，可将其看作准最佳编码。4.2.5.3香农编码香农编码的步骤如下：（1）将信源符号按概率从大到小排序：（2）按下式求第i个信源符号对应的码长l，并取整；(4.12)-log P(u,)≤l,<-log P(u,)+1（3）按下式求第i个信源符号的累加概率P；[P =0(4.13)[P=P(u)i=23,..,qk=l（4）将累加概率P转换成二进制数：121
121 （3）将“概率之和”当作一个新符号的概率，与剩下符号的概率一起，形成一个缩减 信源，再重复上述步骤，直到“概率之和”为 1 为止； （4）按上述步骤实际上构造了一个码树，从树根到端点经过的树枝即为码字。 霍夫曼编码构造了一个非续长码，采用概率匹配方法来决定各码字的码长，概率大的 符号对应于短码，概率小的符号对应于长码，从而使平均码长最短，但编出的码字并不唯一。 2）r 进制霍夫曼编码 对于 r 进制霍夫曼编码，信源符号数 q 应满足 qr r ( 1) （4.11） 其中 为信源缩减的次数。可通过给信源添加概率为零的符号满足上式。 4.2.5.2 费诺编码（Fano） 费诺编码也是构造一个码树，因此编出的码也是非续长码，但不一定是最佳码。编码步 骤如下： （1）将信源符号按概率从大到小排序； （2）将信源符号分成 2 组，使 2 组信源符号的概率之和尽量接近，并给 2 组信源符号 分别赋码元“0”和“1”； （3）把各小组的信源符号再细分为 2 组并赋码元，方法与第一次分组相同； （4）继续分组，直到每一小组只含一个信源符号为止； （5）由此即可构造一个码树，所有终端节点上的码字组成费诺码。 费诺编码的平均码长比霍夫曼编码略长，编码效率稍有下降。一般来讲，费诺编码不是 平均码长最短意义下的最佳编码，可将其看作准最佳编码。 4.2.5.3 香农编码 香农编码的步骤如下： （1）将信源符号按概率从大到小排序； （2）按下式求第i 个信源符号对应的码长 i l ，并取整； log ( ) log ( ) 1 Pu l Pu ii i （4.12） （3）按下式求第i 个信源符号的累加概率 Pi ； 1 1 1 0 ( ) 2,3, , i i k k P P Pu i q （4.13） （4）将累加概率 Pi 转换成二进制数；
（5）取P二进制数小数点后l个二进制数字，作为第i个信源符号的码字。三种方法中，霍夫曼编码效率最高，费诺编码效率次之，香农编码效率最低。香农编码的实用价值不大，但却有很深远的理论意义，同时，也是算术编码的基础。4.2.6几种实用的无失真信源编码4.2.6.1游程编码游程编码主要用于黑、白二值文件的传真。白纸黑字的二值文件采用二元码进行编码，表示背景（白色）时像素为码元“0”，表示内容（黑字）时像素为码元“1”。参照国际标准：一张A4幅面的二值文件，可分1188行，每行1728个像素。重复出现的同类像素的长度称为游程长度（Run-length）。信源符号中重复出现的黑游程和白游程可归一化为统一的编码单元，其单元结构如下：符号码标识码游程长度实际文件的行扫描中，由于文件的二值性，黑、白游程总是交替出现，在第一游程的类型预先规定后，进行游程编码就可省去原单元结构中的“符号码”及“标识码”，仅保留游程长度数据。4.2.6.2MH码MH码是CCITT提出的文件、传真类一维数据压缩编码的国际标准，是由游程编码及霍夫曼编码结合而成的一种改进型霍夫曼码。MH码使用固定编码表进行编码，即在信源与信宿两端，利用预先确定的编码表各自独立进行编码和解码。MH码在编码中对游程长度进行分割，相应将长游程码（游程长度>64）分割为结尾码（终止码）和组合码（形成码）两部分，如表4.1及表4.2所示。表4.1MH码表(一）结尾码RL长度白游程码字RL长度黑游程码字黑游程码字白游程码字0001101013200001101110001101100000110101010001110103300010010000001101011201111134000100110000110100103103510000001010000001101001140113610110001010100001101010051100370011000101100000110101016111000103800010111000011010110122
122 （5）取 Pi 二进制数小数点后 i l 个二进制数字，作为第i 个信源符号的码字。 三种方法中，霍夫曼编码效率最高，费诺编码效率次之，香农编码效率最低。香农编码 的实用价值不大，但却有很深远的理论意义，同时，也是算术编码的基础。 4.2.6 几种实用的无失真信源编码 4.2.6.1 游程编码 游程编码主要用于黑、白二值文件的传真。 白纸黑字的二值文件采用二元码进行编码，表示背景（白色）时像素为码元“0”，表示 内容（黑字）时像素为码元“1”。 参照国际标准：一张 A4 幅面的二值文件，可分 1188 行，每行 1728 个像素。 重复出现的同类像素的长度称为游程长度（Run length) 。 信源符号中重复出现的黑游程和白游程可归一化为统一的编码单元，其单元结构如下： 符号码 标识码 游程长度 实际文件的行扫描中，由于文件的二值性，黑、白游程总是交替出现，在第一游程的类 型预先规定后，进行游程编码就可省去原单元结构中的“符号码”及“标识码”，仅保留游 程长度数据。 4.2.6.2 MH 码 MH 码是 CCITT 提出的文件、传真类一维数据压缩编码的国际标准，是由游程编码及 霍夫曼编码结合而成的一种改进型霍夫曼码。 MH 码使用固定编码表进行编码，即在信源与信宿两端，利用预先确定的编码表各自独 立进行编码和解码。 MH 码在编码中对游程长度进行分割，相应将长游程码（游程长度> 64）分割为结尾码 （终止码）和组合码（形成码）两部分，如表 4.1 及表 4.2 所示。 表 4.1 MH 码表(一) 结尾码 RL 长度 白游程码字 黑游程码字 RL 长度 白游程码字 黑游程码字 0 00110101 0000110111 32 00011011 000001101010 1 000111 010 33 00010010 000001101011 2 0111 11 34 00010011 000011010010 3 1000 10 35 00010100 000011010011 4 1011 011 36 00010101 000011010100 5 1100 0011 37 00010110 000011010101 6 1110 0010 38 00010111 000011010110