第第 5 章章 信源编码信源编码 5.1 编码的定义编码的定义 5.2 无失真信源编码无失真信源编码 5.3 限失真信源编码定理限失真信源编码定理 5.4 常用信源编码方法简介常用信源编码方法简介 编码编码 通信的实质是传输信息，通信系统的性能指标主通信的实质是传输信息，通信系统的性能指标主 要有有效性、可靠性、安全性等，这些指标正是信息要有有效性、可靠性、安全性等，这些指标正是信息 论研究的对象编码的目的是为了优化通信系统，就论研究的对象编码的目的是为了优化通信系统，就 是使这些指标达到最佳是使这些指标达到最佳 按不同的编码目的，编码分为三类：按不同的编码目的，编码分为三类： 信源编码信源编码 信道编码信道编码 安全编码安全编码/密码密码 信源编码信源编码 信源编码是以提高通信的有效性为目的编码信源编码是以提高通信的有效性为目的编码 通常通过压缩信源的冗余度来实现通常通过压缩信源的冗余度来实现 采用的一般方法是压缩每个信源符号的平均比特采用的一般方法是压缩每个信源符号的平均比特 数或信源的码率同样多的信息用较少的码率来数或信源的码率同样多的信息用较少的码率来 传送，使单位时间内传送的平均信息量增加，从传送，使单位时间内传送的平均信息量增加，从 而提高通信的有效性。
而提高通信的有效性 在不失真或允许失真的条件下，用在不失真或允许失真的条件下，用 尽可能少的符号传送信源信息尽可能少的符号传送信源信息 • 信道编码：信道编码： – 是以提高信息传输的可靠性为目的的编码是以提高信息传输的可靠性为目的的编码 – 通常通过增加信源的冗余度来实现采用的通常通过增加信源的冗余度来实现采用的 一般方法是增大码率一般方法是增大码率/带宽 在信道受干扰的情况下增加信号的抗干在信道受干扰的情况下增加信号的抗干 扰能力，同时又使得信息传输率最大扰能力，同时又使得信息传输率最大 • 密码：密码： –是以提高通信系统的安全性为目的的编码是以提高通信系统的安全性为目的的编码 –通常通过加密和解密来实现通常通过加密和解密来实现 无失真编码无失真编码 无失真信源编码定理无失真信源编码定理 信源编码信源编码 限失真编码限失真编码 限失真信源编码定理限失真信源编码定理 无失真无失真 ( 冗余度压缩编码冗余度压缩编码 ) ：仅对信源的冗余度进行：仅对信源的冗余度进行 压缩，不改变信源的熵无失真编码是可逆的，即当压缩，不改变信源的熵无失真编码是可逆的，即当 信源符号变换成代码后，可从代码无失真地恢复出原信源符号变换成代码后，可从代码无失真地恢复出原 信源符号。
只适用于离散信源信源符号只适用于离散信源 限失真限失真 ( 熵压缩编码熵压缩编码 ) ：在失真受限的情况下进行限：在失真受限的情况下进行限 失真编码在连续信源的情况下，由于信源的信息量失真编码在连续信源的情况下，由于信源的信息量 趋于无限，显然不能用离散符号序列来完成无失真编趋于无限，显然不能用离散符号序列来完成无失真编 码，而只能进行限失真编码码，而只能进行限失真编码 离散信源离散信源 无失真信源编码定理称为第一极限定理无失真信源编码定理称为第一极限定理 离散和连续信道离散和连续信道 信道编码定理称为第二极限定理信道编码定理称为第二极限定理 限失真信源编码定理称为第三极限定理限失真信源编码定理称为第三极限定理 连续信源连续信源 信源编码的主要任务信源编码的主要任务 符号变换：使信源输出符号与信道输入符号匹配符号变换：使信源输出符号与信道输入符号匹配 减少冗余，提高编码效率减少冗余，提高编码效率 针对信源输出符号序列的统计特性，寻找一定的方针对信源输出符号序列的统计特性，寻找一定的方 法把信源输出符号序列变换为最短的码字序列法把信源输出符号序列变换为最短的码字序列 信源编码的基本途径信源编码的基本途径 使序列中的各个符号尽可能地互相独立，即解使序列中的各个符号尽可能地互相独立，即解 除相关性，去冗余；除相关性，去冗余； 使编码中各个符号出现的概率尽可能地相等，使编码中各个符号出现的概率尽可能地相等， 即概率均匀化。
即概率均匀化 本章讨论离散信源编码首先从无失真编码定理本章讨论离散信源编码首先从无失真编码定理 出发，重点讨论以香农码、费诺码和霍夫曼码为出发，重点讨论以香农码、费诺码和霍夫曼码为 代表的最佳无失真码代表的最佳无失真码 5.1 编码的定义编码的定义 信源编码：信源输出符号经信源编码器编码后信源编码：信源输出符号经信源编码器编码后 转换成另外的压缩符号转换成另外的压缩符号 无失真信源编码：可精确无失真地复制信源输无失真信源编码：可精确无失真地复制信源输 出的消息出的消息 编码器的作用编码器的作用 将信源符号集将信源符号集 X 中的符号中的符号 变换成由码变换成由码 符号集符号集 y 中的码元中的码元 组成的长度为组成的长度为 Ki 的一的一 一对应的码字一对应的码字 码字集合叫做代码组码字集合叫做代码组Y；码字；码字 所含码元的个数称所含码元的个数称 为该码字的码长，记为为该码字的码长，记为 Ki 分组码分组码 将信源消息分成若干组，即符号序列，每个符号将信源消息分成若干组，即符号序列，每个符号 序列依照固定码表映射成一个码字，这样的码称序列依照固定码表映射成一个码字，这样的码称 为分组码，有时也叫块码。
只有分组码才有对应为分组码，有时也叫块码只有分组码才有对应 的码表，而非分组码中则不存在码表的码表，而非分组码中则不存在码表 例：例：若将信源若将信源 X 通过二元信道传输，就必须把信源符通过二元信道传输，就必须把信源符 号号ai 变换成由变换成由0 、、 1符号组成的码符号序列，这个符号组成的码符号序列，这个 过程就是信源编码过程就是信源编码 定长码定长码 固定长度的码，码中所固定长度的码，码中所 有码字的长度都相同有码字的长度都相同 变长码变长码 可变长度码，码中的码字可变长度码，码中的码字长短不一长短不一 定长码定长码 变长码变长码 若若 0 、、 01 都是码字，译码时如何分离？都是码字，译码时如何分离？ 分组码分组码 / 块码块码将信源符号集中的每个符号映射成一个将信源符号集中的每个符号映射成一个固固 定的码字定的码字分组码必须具有某些属性，才能保证在接分组码必须具有某些属性，才能保证在接 收端能够迅速可靠地译码收端能够迅速可靠地译码 码的不同属性码的不同属性 码表码表 信源符号信源符号 信源信源 出现概率出现概率 p(ai) 符号符号 ai 码码 1 码码 2 码码 3 码码 4 a 1 1/2 0 0 1 1 a 2 1/4 11 10 10 01 a 3 1/8 00 00 100 001 a 4 1/8 11 01 1000 0001 奇异码奇异码 奇异码和非奇异码奇异码和非奇异码 1 若信源符号和码字是一一对应的，则该码为若信源符号和码字是一一对应的，则该码为非奇异非奇异 码。
反之为奇异码码反之为奇异码 唯一可译码唯一可译码 2 任意有限长的码元序列，只能任意有限长的码元序列，只能 被唯一地分割成一个个码字被唯一地分割成一个个码字 例：例： {0,10,11} 是一种唯一可译码是一种唯一可译码 任意一串有限长码序列，如任意一串有限长码序列，如 100111000 ，只能被分割，只能被分割 成成 10、、0、、11、、10 、、0、、0 任何其他分割法都会产生任何其他分割法都会产生 一些非定义的码字一些非定义的码字 奇异码不是唯一可译码奇异码不是唯一可译码 非唯一可译码非唯一可译码 —码码 2 ，可译成，可译成 a1a1或或a3 非奇异码非奇异码 唯一可译码唯一可译码 —码码 3 ，， 但译码有延时但译码有延时 非即时码非即时码 唯一可译码唯一可译码 即时码即时码 非即时码非即时码 接收端收到一个完整的码字后，不能立即译码，还需接收端收到一个完整的码字后，不能立即译码，还需 等下一个码字开始接收后才能判断是否可以译码等下一个码字开始接收后才能判断是否可以译码 码码 3 即时码即时码 ( 非延长码非延长码 ) ( 异前缀码异前缀码 ) 在译码时无需参考后续的码符号就能立即作出判断，在译码时无需参考后续的码符号就能立即作出判断， 译成对应的信源符号。
译成对应的信源符号 码码 4 任意一个码字都不是其它码字的前缀部分任意一个码字都不是其它码字的前缀部分 码码 1 码码 2 码码 3 码码 4 ai a1 0 0 1 1 a2 11 10 10 01 a3 00 00 100 001 a4 11 01 1000 0001 即时码即时码 奇异码奇异码 非唯一非唯一 可译码可译码非即时码非即时码 用码树来构造码字用码树来构造码字 码树从树根开始向下长出码树从树根开始向下长出 m 个树枝，成为个树枝，成为 m 进进制制 码树，树枝代表码元，树枝与树枝的交点叫做节点码树，树枝代表码元，树枝与树枝的交点叫做节点 经过经过 r 个树枝才能到达的节点称为个树枝才能到达的节点称为 r 阶节点向下不阶节点向下不长长 出树枝的节点称为终端节点或端点出树枝的节点称为终端节点或端点 m 进制码树各节进制码树各节 点点 ( 包括树根包括树根 ) 向下长出的树枝不会超过向下长出的树枝不会超过m，若等于，若等于m称称 为满树为满树 (整树整树) ，否则称为非满树，否则称为非满树 (非整树非整树 ) 码树上任一节点都对应一个码字，组成该码字的码树上任一节点都对应一个码字，组成该码字的 码元就是从树根开始到该节点所经过的树枝码元就是从树根开始到该节点所经过的树枝 ( 码元码元 ) 。
若一个码所有码字均处于终端节点，则该码为即时码若一个码所有码字均处于终端节点，则该码为即时码 满树满树 — 等长码等长码 节数节数 — 码长码长 非满树非满树 — 变长码变长码 树码：若有树码：若有 n 个信源符号，那么在码树上就要选择个信源符号，那么在码树上就要选择 n 个终端节点，用相应的个终端节点，用相应的 m 元基本符号表示这些码字元基本符号表示这些码字 • 任一即时码都可用树图法来表示任一即时码都可用树图法来表示 • 当码字长度给定，即时码不是唯一的当码字长度给定，即时码不是唯一的 该码树从根到终端节点所经路径上，该码树从根到终端节点所经路径上， 每一个中间节点皆为码字，因此码每一个中间节点皆为码字，因此码 3 不是即时码，但它是唯一可译码不是即时码，但它是唯一可译码 唯一可译码存在的充分和必要条件唯一可译码存在的充分和必要条件 各码字的长度各码字的长度 K i 应符合克劳夫特应符合克劳夫特 (Kraft) 不等式：不等式： m ：码元进制数：码元进制数 n ：信源符号数：信源符号数 Ki ：各个码字的长度：各个码字的长度 例：例： 设二进制码树中设二进制码树中 X∈∈( a1, a2, a3, a4)，， K1 =1 ，， K2 =2 ，， K3 =2 ，， K4 =3 。
应用应用 Kraft 不等式，得：不等式，得：不存在满足这种不存在满足这种 K i 的唯一可译码的唯一可译码 要形成满足上述长度要形成满足上述长度的码字，必须在中间的码字，必须在中间 节点放置码字节点放置码字 中间节点中间节点如果将各码字长度改成：如果将各码字长度改成：存在唯一可译码存在唯一可译码 K1 =1 ，， K2 =2 ，， K3 =2 ，， K4 =3 K1 =1 , K2 =2 , K3 =3 , K4 =3 注意注意 Kraft 不等式只是用来说明唯一可译码是不等式只是用来说明唯一可译码是 否否存在存在，并不能作为唯一可译码的判据并不能作为唯一可译码的判据 如码字如码字 {0，，10，，010，，111} 虽然满足虽然满足 Kraft 不等式，不等式， 但它不是唯一可译码但它不是唯一可译码 K1 =1 , K2 =2 , K3 =3 , K4 =3 5.2 无失真信源编码无失真信源编码 要求能够无失真或无差错地译码，同时希望所要求能够无失真或无差错地译码，同时希望所 得编码的平均码长最小得编码的平均码长最小 对信源的对信源的 L 长符号序列进行长符号序列进行 m 进制编码，码长进制编码，码长 KL 只要可用的码字数不少于扩展信源的符号数：只要可用的码字数不少于扩展信源的符号数：就可做到唯一译码就可做到唯一译码 编码输出码编码输出码 字的个数字的个数 KL/L 是平均每个信源符号所需要的码元符号个数是平均每个信源符号所需要的码元符号个数 编码后平均每个信源符号能载荷的最大信息量为：编码后平均每个信源符号能载荷的最大信息量为： 5.2.1 定长编码定理定长编码定理 在定长编码中，在定长编码中， K=KL 是定值，且为唯一可译码。
是定值，且为唯一可译码 编码的目的是寻找编码的目的是寻找最小最小 K 值值 • 若对信源进行定长编码，必须满足若对信源进行定长编码，必须满足: 对于定长唯一可译码，每个信源符号至少需用对于定长唯一可译码，每个信源符号至少需用 （（ log n / log m ）个码符号来变换个码符号来变换 例例: 英文电报符号，英文电报符号， n =27 ，， L =1 ，， m =2( 二元编码二元编码 ) log 2 n K ≥ = log 2 27 ≈ 5 每个英文电报符号至少每个英文电报符号至少 log 2 m 要用要用5位二元符号编码位二元符号编码 • 实际英文电报符号信源，平均每个英文电报符号所实际英文电报符号信源，平均每个英文电报符号所 提供的信息量约等于提供的信息量约等于 1.4 比特，大大小于比特，大大小于 5 比特 • 定长编码后每个码字定长编码后每个码字 (5个二元符号个二元符号)只携带约只携带约1.4比特比特 信息量定长编码的信息传输效率极低信息量定长编码的信息传输效率极低 当考虑信源符号出现的概率及符号间的依赖关系后当考虑信源符号出现的概率及符号间的依赖关系后 （考虑信源的冗余度），在定长编码中每个信源符（考虑信源的冗余度），在定长编码中每个信源符 号平均所需的号平均所需的码长可以减少。
码长可以减少 定长编码定理给出了信源进行定长编码所需码定长编码定理给出了信源进行定长编码所需码 长的长的理论极限值理论极限值 定长编码定理定长编码定理 • 编码器的平均输出信息率编码器的平均输出信息率 • 对于二进制编码，每个信源符号必须对于二进制编码，每个信源符号必须 输出的码长输出的码长 定长编码定理说明：定长编码定理说明： 只要码字所能携带的信息量大于信源序列输出的只要码字所能携带的信息量大于信源序列输出的 信息量，则可以使传输几乎无失真，当然条件是信息量，则可以使传输几乎无失真，当然条件是 L足够大 当当 时，不可能构成无失真的编码，也时，不可能构成无失真的编码，也 就是不可能做一种编码器，能使收端译码时差就是不可能做一种编码器，能使收端译码时差 错概率趋于零错概率趋于零 当当 时，则为临界状态，可能无失真，时，则为临界状态，可能无失真， 也可能有失真也可能有失真 Ø 差错概率差错概率 设差错概率用设差错概率用 Pe 表示，则有：表示，则有：ε 为一正数为一正数 为信源序列的自信息方差为信源序列的自信息方差 当当 均为定值时，只要均为定值时，只要 L 足够大，足够大， Pe可以小可以小 于任一正数于任一正数δ。
即：即：当信源序列长度当信源序列长度 L 满足满足能达到差错率要求：能达到差错率要求： Ø 编码效率编码效率 编码效率总编码效率总 定义编码效率为：定义编码效率为：是小于是小于 1 信源的平均符号熵为信源的平均符号熵为 HL (X) ，采用平均符号码长，采用平均符号码长 为为 K 来编码后所得的效率来编码后所得的效率 最佳编码效率：最佳编码效率：编码定理从理论上阐明了编码效率接近编码定理从理论上阐明了编码效率接近 1 的理想编码的理想编码 器的存在性，它使输出符号的信息率与信源熵之比接器的存在性，它使输出符号的信息率与信源熵之比接 近于近于 1 ，即：，即：若要实现，取无限长若要实现，取无限长 L 的的 信源符号进行统一编码信源符号进行统一编码 例：例： 设离散无记忆信源概率空间为设离散无记忆信源概率空间为 • 信源熵：信源熵： H ( X ) = - ∑ p ( xi ) log p ( xi ) = 2.55 bit / 符号符号 i = 1 对信源符号采用定长二元编码对信源符号采用定长二元编码, 要求编码效率要求编码效率η为为 90 ％％ 若取若取 L ＝＝ 1 ，则，则即每个符号用即每个符号用 2.83bit 进行定长编码，共有进行定长编码，共有 22.83 =7.11 种种 可能，按可能，按 7 种可能性计算，信源符号中就有一种符号种可能性计算，信源符号中就有一种符号 没有对应的码字，取概率最小的没有对应的码字，取概率最小的 a8 ，则，则 Pe=0.04 , 太大太大 • 信源序列的自信息方差：信源序列的自信息方差： 若要求译码错误概率若要求译码错误概率 δ ≤ 10-6 L 应满足：应满足：对于定长编码，即使在编码效率和译码错误概率的要对于定长编码，即使在编码效率和译码错误概率的要 求并不十分苛刻的情况下，就需要求并不十分苛刻的情况下，就需要 10 8 个信源符号一个信源符号一 起进行编码。
这显然是很难实现的起进行编码这显然是很难实现的 5.2.2 变长编码定理变长编码定理 在变长编码中，码长在变长编码中，码长 KL是变化的是变化的 根据信源各个符号的统计特性，如概率大的符号用根据信源各个符号的统计特性，如概率大的符号用 短码，概率小的用较长的码，使得编码后平均码长短码，概率小的用较长的码，使得编码后平均码长 降低，从而提高编码效率统计匹配）降低，从而提高编码效率统计匹配） 编码后码字编码后码字 Y1 , Y 2 , ‥ , Y n 码长分别为码长分别为 K 1 , K 2 , ‥ , K n 码的码的平均长度平均长度为：为：编码后的编码后的信息传输率信息传输率为：为： 对于某一信源和某一码符号集，若有一个唯一可译对于某一信源和某一码符号集，若有一个唯一可译 码，其平均长度小于所有其他唯一可译码的平均长码，其平均长度小于所有其他唯一可译码的平均长 度，则称该码为最佳码（紧致码）度，则称该码为最佳码（紧致码） 单个符号变长编码定理单个符号变长编码定理 若离散无记忆信源的符号熵为若离散无记忆信源的符号熵为 H(X) ，每个信源符号，每个信源符号 用用 m 进制码元进行变长编码，一定存在一种无失真进制码元进行变长编码，一定存在一种无失真 编码方法，其码字平均长度编码方法，其码字平均长度 K 满足下列不等式：满足下列不等式： H ( X ) H ( X ) ≤ K < K < + 1 log m log m 离散平稳无记忆序列变长编码定理离散平稳无记忆序列变长编码定理 对于平均符号熵为对于平均符号熵为 HL(X) 的离散平稳无记忆信的离散平稳无记忆信 源，必存在一种无失真编码方法，使平均信息率源，必存在一种无失真编码方法，使平均信息率R ′ 满足不等式：满足不等式： 其中其中 ε 为任意小正数。
为任意小正数 无失真变长信源编码定理（无失真变长信源编码定理（香农第一定理香农第一定理）） 对于平均符号熵为对于平均符号熵为 HL(X) 的离散平稳无记忆信源（离散的离散平稳无记忆信源（离散 无记忆信源无记忆信源 X 的的 L 次扩展信源次扩展信源对其进行对其进行 m 元编码，必存在一种无失真编码方法，构元编码，必存在一种无失真编码方法，构 成唯一可译码，使信源成唯一可译码，使信源 X 中每个信源符号所需的平均码中每个信源符号所需的平均码 长长 满足：满足： 用变长编码可达到相当高的编码效率，一般所要求用变长编码可达到相当高的编码效率，一般所要求 的符号长度的符号长度 L 可以比定长编码小得多可以比定长编码小得多 • 编码效率的下界编码效率的下界 为了衡量各种编码方法与最佳码的差距，定义码的为了衡量各种编码方法与最佳码的差距，定义码的 剩余度为：剩余度为： 同前例： 设离散无记忆信源概率空间为 • 信源熵： H ( X ) = 2 . 55 bit / 符号 要求编码效率η为 90 ％ 用二进制变长编码， m ＝ 2 例：例： 设离散无记忆信源概率空间为设离散无记忆信源概率空间为 • 信源熵：信源熵： H ( X ) = 1/4 log4 +3/4 log3/4 = 0. 811 bit / 信源符号信源符号 若用二元定长编码若用二元定长编码 (0,1) 来构造一个即时码：来构造一个即时码：• 平均码长：平均码长： 二元码符号二元码符号 / 信源符号信源符号 • 编码效率：编码效率：• 输出的信息传输率：输出的信息传输率： 再对长度再对长度 L 为为 2 的信源序列进行的信源序列进行 变长编码，其即时码如表：变长编码，其即时码如表： • 码字平均长度：码字平均长度： • 单个符号的平均码长单个符号的平均码长• 编码效率编码效率• 输出的信息传输率：输出的信息传输率： R2 ＝＝ 0.961bit/ 二元码符号二元码符号 信源序列的长度增加信源序列的长度增加 : 编码复杂一些，但信息传输率有了提高编码复杂一些，但信息传输率有了提高 变长编码：变长编码： L ＝＝ 2 ，， η2 = 0.961 定长编码：定长编码： 要求编码效率达到要求编码效率达到 96 ％时，允许译码错误概率％时，允许译码错误概率 δ ≤ 10 －－ 5 说明说明 (1) 定长码需要的信源序列长，使码表很大，且总存定长码需要的信源序列长，使码表很大，且总存 在译码差错。
而用变长码编码时，在译码差错而用变长码编码时， L 不需要很大就可不需要很大就可 达到相当高的编码效率，而且可实现无失真编码达到相当高的编码效率，而且可实现无失真编码 (2) 随着信源序列长度的增加，编码的效率越来越接随着信源序列长度的增加，编码的效率越来越接 近于近于 1 编码后的传输率编码后的传输率 R 也越来越接近于无噪无损也越来越接近于无噪无损 二元对称信道的信道容量二元对称信道的信道容量 (1bit/ 二元码符号二元码符号 ) ，达到，达到信信 源与信道的匹配源与信道的匹配 最佳变长编码最佳变长编码 5.2.3 凡是能载荷一定的信息量，且码字的平均长度最凡是能载荷一定的信息量，且码字的平均长度最 短，可分离的变长码的码字集合称为最佳变长码短，可分离的变长码的码字集合称为最佳变长码 编码主要方法有：香农编码、费诺编码、哈夫曼编码主要方法有：香农编码、费诺编码、哈夫曼 编码等 仅哈夫曼编码是真正意义下的最佳编码仅哈夫曼编码是真正意义下的最佳编码 哈夫曼编码效率最高，费诺编码效率次之，香农哈夫曼编码效率最高，费诺编码效率次之，香农 编码效率最低，甚至低于定长编码的效率因此，香编码效率最低，甚至低于定长编码的效率。
因此，香 农编码的实用价值不大，但却有深远的理论意义，因农编码的实用价值不大，但却有深远的理论意义，因 为按香农的方法对信源序列编码，当序列长度趋于无为按香农的方法对信源序列编码，当序列长度趋于无 穷时，平均码长会趋于信源的熵穷时，平均码长会趋于信源的熵 香农（香农（ Shannon ）编码方法）编码方法 1 香农第一定理指出了平均码长与信源之间的关系，同香农第一定理指出了平均码长与信源之间的关系，同 时也指出了可以通过编码使平均码长达到极限值时也指出了可以通过编码使平均码长达到极限值 香农第一定理指出，选择每个码字的长度香农第一定理指出，选择每个码字的长度 K i 满足下满足下 式，就可以得到香农码：式，就可以得到香农码： 二进制香农码的编码步骤二进制香农码的编码步骤 按信源符号的概率从大到小的顺序排队，不妨设：按信源符号的概率从大到小的顺序排队，不妨设： 1 确定满足下列不等式的整数码长确定满足下列不等式的整数码长 K i ：： 2 令令 p ( a0 )=0 ，计算第，计算第 i 个消息的累加概率个消息的累加概率 P i ：： 3 将累加概率将累加概率 Pi 变换成二进制数，并取小数点后变换成二进制数，并取小数点后 Ki 位位 4 作为符号作为符号 ai的编码。
的编码 例：例： 有一单符号离散无记忆信源有一单符号离散无记忆信源 对该信源编二对该信源编二 进制香农码进制香农码 • 香农码的平均码长香农码的平均码长 • 信源熵信源熵 • 编码效率编码效率 为提高编码效率，可把为提高编码效率，可把 x 4 x 5 换成前面的换成前面的节节 点，可减小平均码长点，可减小平均码长 不应先规定码长，而是由码树来规定码不应先规定码长，而是由码树来规定码 字，可得更好的结果字，可得更好的结果 例：例： 设信源共设信源共 7 个符号消息，其概率如表所示：个符号消息，其概率如表所示： 费诺（费诺（ Fano ）编码方法）编码方法 概率匹配概率匹配 2 按信源符号的概率从大到小的顺序排队，不妨设：按信源符号的概率从大到小的顺序排队，不妨设： p ( a 1 ) ≥ p ( a 2 ) ≥ … ≥ p ( a n ) 按编码进制数将概率分组，使每组概率尽可能接按编码进制数将概率分组，使每组概率尽可能接 近或相等。
如编二进制码就分成两组，编近或相等如编二进制码就分成两组，编 m 进制进制 码就分成码就分成 m 组 给每一组分配一位码元给每一组分配一位码元 将每一分组再按同样原则划分，重复步骤将每一分组再按同样原则划分，重复步骤 2 和和 3 ，， 直至概率不再可分为止直至概率不再可分为止 信源符号对应的码字即为费诺码信源符号对应的码字即为费诺码 例：例： 对前例信源进行二进制费诺编码对前例信源进行二进制费诺编码 费诺编码的基本特点费诺编码的基本特点: 1) 费诺编码在构造费诺编码在构造码树码树时，是从树根开始到终端节时，是从树根开始到终端节 点结束；点结束； 2) 由于赋码元时的任意性，因此编出的码字不唯一；由于赋码元时的任意性，因此编出的码字不唯一； 3) 费诺编码虽属于费诺编码虽属于概率匹配概率匹配范畴，但并未严格遵守范畴，但并未严格遵守 匹配规则，有时出现概率小的码长反而小因此匹配规则，有时出现概率小的码长反而小因此 平均码长一般不会最小平均码长一般不会最小 费诺码比较适合于费诺码比较适合于每次分组概率都很接近每次分组概率都很接近的信源，特的信源，特 别是对每次别是对每次分组概率都相等的信源分组概率都相等的信源进行编码时，可达进行编码时，可达 到理想的编码效率。
到理想的编码效率 例：例： 对该信源进行二对该信源进行二 进制费诺编码进制费诺编码 • 平均码长：平均码长：• 编码效率：编码效率： 例：例： 二进制费诺编码二进制费诺编码 信源符号信源符号 概率概率 编码编码 码字码字 码长码长 x 1 0.25 0 0 00 2 x 2 0.25 1 01 2 x 3 0.125 0 100 3 0 x 4 0.125 1 101 3 x 5 0.0625 0 1100 4 1 0 x 6 0.0625 1 1101 4 1 x 7 0.0625 0 1110 4 1 x 8 0.0625 1 1111 4 平均码长平均码长 K = 2 . 75 码元码元 / 符号符号 每次所分两组的每次所分两组的 信源熵信源熵 H ( X ) = 2 . 75 bit / 符号符号 概率恰好相等概率恰好相等 H ( X ) 编码效率编码效率 η = = = 1 K log 2 树图： 哈夫曼（哈夫曼（ Huffman ）编码方法）编码方法 3 将信源符号按概率由大到小顺序排队将信源符号按概率由大到小顺序排队 1 给两个概率最小的符号各分配一个码元，将其概率给两个概率最小的符号各分配一个码元，将其概率 2 相加后合并作为一个新的符号，与剩下的符号一相加后合并作为一个新的符号，与剩下的符号一 起，再重新排队起，再重新排队 给缩减信源中概率最小的两个符号各分配一个码元给缩减信源中概率最小的两个符号各分配一个码元 3 4 重复步骤重复步骤 2 、、 3 直至概率和为直至概率和为 1 从最后一级开始，向前返回得到各个信源符号所对从最后一级开始，向前返回得到各个信源符号所对 5 应的码元序列，即相应的码字。
应的码元序列，即相应的码字 例：例：试对该信源编二进制哈夫曼码试对该信源编二进制哈夫曼码 读取码字的时候，要从后向前读，此读取码字的时候，要从后向前读，此 时编出来的码字是可分离的即时码时编出来的码字是可分离的即时码 平均码长平均码长 信源熵信源熵 H(X) = H (0.2,0.19,0.18,0.17,0.15,0.1,0.01)=2.61 bit/ 符号符号 编码效率编码效率 哈夫曼编码的基本特点哈夫曼编码的基本特点 1) 哈夫曼编码在构造码树时，是从端点开始直到树哈夫曼编码在构造码树时，是从端点开始直到树 根结束；根结束； 2) 哈夫曼编码采用概率匹配方法来决定各码字长度，哈夫曼编码采用概率匹配方法来决定各码字长度， 概率大的符号对应于短码，概率小的符号对应与长概率大的符号对应于短码，概率小的符号对应与长 码，充分利用了短码，从而使平均码长最小；码，充分利用了短码，从而使平均码长最小； 3) 哈夫曼编码时，缩减信源的最后二个码字总是最哈夫曼编码时，缩减信源的最后二个码字总是最 后一位不同，从而保证了哈夫曼码是即时码后一位不同，从而保证了哈夫曼码是即时码 费诺码是从树根开始，把各节点分给某子集，若子费诺码是从树根开始，把各节点分给某子集，若子 集已是单点集，它就是一片树叶而作为码字。
集已是单点集，它就是一片树叶而作为码字 哈夫曼编码是先给每一符号一片树叶，逐步合并成哈夫曼编码是先给每一符号一片树叶，逐步合并成 节点直到树根节点直到树根 哈夫曼的编法并不惟一哈夫曼的编法并不惟一 说明说明 • 每次对概率最小的符号分配每次对概率最小的符号分配 “0” 和和 “1” 码元是码元是任意任意 的，所以可得到不同的码字只要在各次缩减信源的，所以可得到不同的码字只要在各次缩减信源 中保持码元分配的一致性，即能得到可分离码字中保持码元分配的一致性，即能得到可分离码字 • 不同的码元分配，得到的具体码字不同，但码长不同的码元分配，得到的具体码字不同，但码长 K i 不变，平均码长也不变，所以没有本质区别不变，平均码长也不变，所以没有本质区别 • 缩减信源时，若合并后的新符号概率与其他符号概缩减信源时，若合并后的新符号概率与其他符号概 率相等，从编码方法上来说，这几个符号的次序可率相等，从编码方法上来说，这几个符号的次序可 任意排列，编出的码都是正确的，但得到的码字不任意排列，编出的码都是正确的，但得到的码字不 相同，不同的编法得到的码字长度相同，不同的编法得到的码字长度 K i 也不尽相同。
也不尽相同 • 在哈夫曼编码过程中，对缩减信源符号按概率由大在哈夫曼编码过程中，对缩减信源符号按概率由大 到小的顺序重新排列时，应使合并后的新符号尽可到小的顺序重新排列时，应使合并后的新符号尽可 能排在靠前的位置，这样可使合并后的新符号重复能排在靠前的位置，这样可使合并后的新符号重复 编码次数减少，使短码得到充分利用编码次数减少，使短码得到充分利用 m 进制哈夫曼编码进制哈夫曼编码 在编在编 m 进制哈夫曼码时，为了使短码得到充分利用，进制哈夫曼码时，为了使短码得到充分利用， 使平均码长最短，必须使最后一步的缩减信源有使平均码长最短，必须使最后一步的缩减信源有 m 个个 信源符号信源符号 缩减次数缩减次数 每次缩减所减少每次缩减所减少 的信源符号个数的信源符号个数 信源符号数信源符号数 n 应满足：应满足：不满足时：设不满足时：设q个概率为个概率为 0 的信源符号，使的信源符号，使q+n 满足要求满足要求 第一次对最小概率符号分配码元时只取第一次对最小概率符号分配码元时只取 (m-q) 个，分别个，分别 配以配以 0,1,…, m-q-1 ，把这些符号的概率相加作为一个新，把这些符号的概率相加作为一个新 符号的概率，与其它符号一起重新排列。
以后每次取符号的概率，与其它符号一起重新排列以后每次取 m 个符号，分别配以个符号，分别配以 0,1,…, m-1；如此下去，直至所有；如此下去，直至所有 概率相加得概率相加得 1 为止，即得到各符号的为止，即得到各符号的 m 进制码字进制码字 单符号离散无记忆信源，单符号离散无记忆信源， 例例 试对该信源编三进制哈夫曼码试对该信源编三进制哈夫曼码 m =3 ，， n =8 无法满足无法满足 n = s ( m -1) + m s =3 ，， q =1 q + n = s ( m -1) + m 第一次取第一次取 m - q =2 个符号进行编码个符号进行编码 平均码长平均码长 信息传输率信息传输率 编码效率编码效率 • 香农码、费诺码、哈夫曼码都考虑了信源的统计特香农码、费诺码、哈夫曼码都考虑了信源的统计特 性，使经常出现的信源符号对应较短的码字，使平性，使经常出现的信源符号对应较短的码字，使平 均码长缩短，从而实现了对信源的压缩；均码长缩短，从而实现了对信源的压缩； • 香农码有系统的、惟一的编码方法，费诺码和哈夫香农码有系统的、惟一的编码方法，费诺码和哈夫 曼码的编码方法都不惟一；曼码的编码方法都不惟一； • 费诺码比较适合于对分组概率相等或接近的信源编费诺码比较适合于对分组概率相等或接近的信源编 码，费诺码也可以编码，费诺码也可以编 m m 进制码，但进制码，但 m m 越大，信源的越大，信源的符符 号数越多，可能的编码方案就越多，编码过程就越号数越多，可能的编码方案就越多，编码过程就越 复杂，有时短码未必能得到充分利用；复杂，有时短码未必能得到充分利用； • 哈夫曼码对信源的统计特性没有特殊要求，编码效哈夫曼码对信源的统计特性没有特殊要求，编码效 率比较高，对编码设备的要求也比较简单，因此综率比较高，对编码设备的要求也比较简单，因此综 合性能优于香农码和费诺码。
合性能优于香农码和费诺码 5.3 限失真信源编码定理限失真信源编码定理 • 设离散无记忆信源设离散无记忆信源 X 的信息率失真函数为的信息率失真函数为 R (D) ，， – 当信息率当信息率 R ＞＞ R (D) 时，只要信源序列长度时，只要信源序列长度 L 足足 够长，一定存在一种编码方法，其译码失真小够长，一定存在一种编码方法，其译码失真小 于或等于于或等于 D+ε，，ε为任意小的正数；为任意小的正数； – 反之，若反之，若 R＜＜ R (D) ，则无论采用什么样的编码，则无论采用什么样的编码方方 法，其译码失真必大于法，其译码失真必大于 D • 如是二元信源，则对于任意小的如是二元信源，则对于任意小的ε＞＞ 0 ，每一个信，每一个信 源符号的平均码长满足如下公式：源符号的平均码长满足如下公式： 5.4 常用信源编码方法简介常用信源编码方法简介 5.4.1 游程编码游程编码 游程：数字序列中连续出现相同符号的一段游程：数字序列中连续出现相同符号的一段 在二元序列中，连在二元序列中，连 0 段称为段称为 0 游程，连游程，连 1 段称为段称为 1 游程游程 游程长度序列游程长度序列 / 游程序列：用交替出现的游程序列：用交替出现的 “0” 游程游程 和和 “1” 游程长度表示任意二元序列。
游程长度表示任意二元序列 游程变换：是一种一一对应的变换，也是可逆变换游程变换：是一种一一对应的变换，也是可逆变换 游程序列：游程序列： 3113213 二元序列：二元序列： 000101110010001 若已知二元序列以若已知二元序列以 0 起始，从游程序列很容易恢复成起始，从游程序列很容易恢复成 原来的二元序列原来的二元序列 游程变换将二元序列变换成了多元序列；这样游程变换将二元序列变换成了多元序列；这样 就适合于用其他方法，如哈夫曼编码，进一步就适合于用其他方法，如哈夫曼编码，进一步 压缩信源，提高通信效率压缩信源，提高通信效率 • 编码方法：编码方法： – 首先测定首先测定 “0” 游程长度和游程长度和 “1” 游程长度游程长度的概率的概率 分布，即以游程长度为元素，构造一个新的分布，即以游程长度为元素，构造一个新的 信源；信源； – 对新的信源对新的信源 ( 游程序列游程序列 ) 进行哈夫曼编码进行哈夫曼编码 5.4.2 算术编码算术编码 • 算术编码是近十多年来发展迅速的一种无失真信源算术编码是近十多年来发展迅速的一种无失真信源 编码，它与最佳的哈夫曼码相比，理论性能稍加逊编码，它与最佳的哈夫曼码相比，理论性能稍加逊 色，而实际压缩率和编码效率却往往还优于哈夫曼色，而实际压缩率和编码效率却往往还优于哈夫曼 码，且实现简单，故很受工程上的重视。
码，且实现简单，故很受工程上的重视 • 算术编码不同于哈夫曼码，它是非分组算术编码不同于哈夫曼码，它是非分组 ( 非块非块 ) 码它 从全序列出发，考虑符号之间的关系来进行编码从全序列出发，考虑符号之间的关系来进行编码 • 算术编码利用了累积概率的概念算术编码利用了累积概率的概念 • 算术码主要的编码方法是计算输入信源符号序列所算术码主要的编码方法是计算输入信源符号序列所 对应的区间对应的区间。