1、信息论基础与编码 无失真信源编码ch05article信息论基础与编码 无失真信源编码Contents1 无失真信源编码基本概念 12 定长无失真信源编码 23 渐进等同分割性 54 定长无失真信源编码定理 65 变长无失真编码 85.1 Kraft 不等式 85.2 唯一可译码判决准则 . . . . . . . . . . . . . . . . . . . . . . . . . 96 变长无失真信源编码定理 107 无失真信源编码技术 117.1 Huffman 编码 127.2 Shannon 编码 127.3 Shannon-Fano-Elias 编码 127.4 Fano 编码
2、127.5 Huffman 编码的几个问题 137.6 算数编码 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147.7 游程编码 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157.8 通用编码 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157.9 几种编码方案的性能对比 . . . . . . . . . . . . . . . . . .
3、 . . . . . 221 无失真信源编码基本概念 对于信源来说有两个基本问题：如何计算信源输出的信息量；如何有效地 表示信源输出，即在不失真或允许一定失真的条件下，如何用尽可能少的 符号来表示信源，以便提高信息传输的效率。 编码实质上是对信源的原始符号按照一定的数学规则进行的一种变换。信源编码器C : W1, WS : s1, s2, . . . , sq X : x1, x2, . . . , xr Figure 1: 信源编码器模型2, . . . , Wq 将信源符号集合中的 si（或者长为 N 的信源符号序列）变换成由 xj 组成 的长度为 li 的一一对应的码符号序列 Wi。 编
4、码的一些基本概念 这种码符号序列 Wi 称为码字；长度 li 称为码字长度，简称码长；全 体码字的集合 C 称为码。 若码符号集合为 X = 0, 1，则所得的码字都是二元序列，称为二元 码 或二进制码。 若一个码中所有码字的码长都相等，则称为等长码；否则为变长码。 若一个码中无重复码字，则称为非奇异码；否则为奇异码。 若码符号集合中每个码符号所占的传输时间都相同，则所得的码称 为同价码。 若任意一串有限长的码符号序列只能被唯一地译为对应的信源符号 序列，则称此码为唯一可译码。 若某个唯一可译码在译码时无需参考后续的码符号就能立即作出判 断，将码符号序列译成相应的信源符号序列。则称此码为即时码
5、；否 则为 非即时码。即时码又称为逗点码、非延长码。2 定长无失真信源编码 对一个信源进行定长编码时每个信源符号所需要的二进制码符号个数（码 长）将由信源符号的个数唯一决定：L H0(X) = log2 X Definition 1. X 的原始编码容量定义为：H0(X) = log2 X (1) 当信源符号个数正好是 2 的幂次时，可以得到整数 L = H0(X)； 否则 L = H0(X)。此时实际码长略大于信源的最大熵，效率不高，可以 通过对信源进行扩展的方法来提高编码效率。 另一种提高编码效率的手段为近似无失真编码。 无失真编码可分为严格无失真和近似无失真两种情况。 严格无失真编码是一
6、个信源符号到码字的一一映射；而近似无失真则会将 一些不同的信源符号映射为相同的码字，因此一旦信源真的产生了这些被 混淆的信源符号，就会产生一次译码失败。我们通常用 来表示信源产生 被混淆的符号的概率。当 足够小时，这种近似无失真的编码方法在实际 生产中也就可以近似认为是无失真的了。Example 2. 给定一 8 符号信源： X a b c d e f g h (2)44 416P (X) = 1 1 1 31 164 641 164 64当要求 = 0 时对此信源进行二进制等长编码，每个信源符号需要 3 个二进制 码符号，即 L = 3bit.我们注意到 Prs a, b, c, d = 1
7、5/16，因此如果我们愿意承受 1/16 的译 码失败概率的话，就可以将信源的后 4 个符号忽略，只对前 4 个符号编码，此 时 L = 2bit，信源得到了有效的压缩。 为此，我们定义两个新的概念：Definition 3 (最小 充分子集). X 为包含元素个数最少的、满足下述条件的、X 的子集：Prx X 1 (3)Definition 4 (基本编码容量). X 的基本编码容量为：H (X) = log2 X (4)Example 5. 图2显示了上例中基本编码容量与 的关系：Figure 2: 基本编码容量与 的关系 IExample 6. 考虑抛掷一枚偏畸硬币 N 次得到的结果序列
8、 x = (x1, x2, . . . , xN ),其中 xn 0, 1，概率分布为 p0 = 0.9。令 r(x) 为序列 x 中 1 的个数，则p(x) = pN r(x)r(x)0 p1 (5)为 了 计 算 H (X) 我 们 必 须 先 确 定 相 应 的 X . 显 然 最 小 充 分 子 集 将 包 含 r(x) = 0, 1, 2 . . . 直到 rmax() 1 的所有序列和 r(x) = rmax() 的部分序列。下 图给出了 N = 4 和 10 以及 N = 10, 210, 410, 610, 810, 1010 时的基本编码容量 和 的关系Figure 3: 基
9、本编码容量和 的关系 IIFigure 4: 基本编码容量和 的关系 III 由前面的三幅图可以看出，当 N 较小时 H (X) 的取值严重依赖于 , 而当 N 足够大时，H (X) 基本与 无关，且其值逼近 N H(X).3 渐进等同分割性 设 x = x1x2 . . . xN 是离散无记忆信源输出的一个特定序列，则对 0, 0，总可以找到一个整数 N0，使得当 N N0 时，有： H Pr (X) log p(x) 1 (6) N 对于离散无记忆信源， log p(x)/N = IN 。即长度为 N 的符号序列中平 均每个符号的自信息量。 其中 和 的关系可以由弱大数定理得到：2 = I
10、N 2(7) 我们将满足上述条件的序列集合称为典型列集合T。 典型列集合具有下述性质： Prx T 1 若 x T，则2N H(X)+ p(x) 2N H(X) (8) 当 N 足够大时典型列中元素的数目满足：(1 )2N H(X) T 2N H(X)+ (9) 典型列集合中每个序列出现的概率近似相等，且总和趋向于 1。 个别非典型列出现的概率不一定比典型列出现的概率小；虽然非典型列总 概率小，但非典型列的数目不一定少。Example 7. 典型列示例“偏畸硬币抛掷” 投掷一枚偏畸硬币，出现正面的概率为 p，则进行 N 次投掷，平均有 N p次出现正面、N (1 p) 次出现反面，所以每个典型
11、列出现的概率趋于 pN p (1 p)N (1p)。当 p pN p (1 p)N (1p)。设 p = 0.1, N = 100，(1 p)N = 2.656 105，pN p (1 p)N (1p) = 7.618 1015，H(X) = 0.469bit/symbol，T = 246.9，XN = 2100，所以典型列仅占 246.9/2100 = 253.1，而绝大多数是非典型列。 下图是从上例的 X100 中随机抽取出来的 15 个序列，最后两行是概率最大 和最小的两个序列，最右边的一列是序列概率的对数，请将其与信源的熵 进行比较。 稍后的几副小图分别显示了当 N = 100 和 N
12、 = 1000 时包含 r 个 1 的序列 的个数 n(r)、包含 r 个 1 的序列的概率 p(x)、概率的对数以及包含 r 个 1 的所有序列的总概率 n(r)p(x).Figure 5: 典型列示例Figure 6: n(r) 和 p(x) 曲线 图中的虚横线对应 N H(X)，T 对应典型列集合。 最后这一幅图显示了将所有 N 长序列按概率由小到大排列和典型列的 示例。4 定长无失真信源编码定理Theorem 8. 设熵率为 H(S) 的离散无记忆信源产生的信源符号序列被分为长 为 N 的源符号组，并用长为 L 的码符号组进行编码，码符号表的大小为 r，则 0 和 0，当 N 足够大，
13、并且 L 满足：L log r/N H(S) + ，则源 符号组没有自己特定码符号组的概率可以小于 。Figure 7: log p(x) 和 n(r)p(x) 曲线Figure 8: 典型列全貌 对于恒稳遍历信源可以得到类似的结果。 改写上述定理的条件：L log r N H(S)，即只要 L 个码符号所能传 输的最大信息量大于 N 长信源符号序列所携带的信息量，就可以实现几 乎无失真编码。Definition 9. R = L log r/N 为编码速率； = H(S)/R 为编码效率。 根据上述定理，最佳编码效率为： = H(S)/(H(S) + )。 为允许的编码错误概率上限。 因此在
14、已知自信息方差和信源熵的条件下，信源符号序列长度 N 与最佳 编码效率和允许编码错误概率之间的关系为：N DI(si) 2/H2 (S) (1 )2 定长编码在实际应用中存在两个问题： 编译码同步的问题； 如何均衡分组长度、编译码复杂性、编译码延时和差错概率之间的 关系。5 变长无失真编码 当使用等概的码符号序列对信源符号序列进行定长编码时，为了使编码有 效，信源符号序列的长度必须很大才行。这在实际应用中很难实现。为了 解决这一难题，可以采用可变长度的码符号序列去适应不同概率的信源符 号（序列）。 最典型的变长编码的例子就是电报中使用的 Morse 码：Table 1: Morse 电码AB
15、C D E F G H I JK L M N O P Q R ST U V W X Y Z 上表给出了 Morse 码的一部分。 Morse 码实际上是一个三元码，具有点、划和间隔三种符号。划所对应的 时间长度是点所对应的时间长度的三倍。在一个字母中点和划之间的时间 间隔是一个时间单位，在字母之间是三个时间单位，而在单词之间是七个 时间单位。5.1 Kraft 不等式 在唯一可译码中，即时码显然要比非即时码要好。下面的 Kraft 定理给出 了即时码存在的充要条件。Theorem 10 (Kraft 不等式). 设含有 q 个信源符号的信源要用 r 个符号的 码符号表进行变长编码，则当且仅当各
16、码字的长度 l1, l2, . . . , lq 满足 Kraft 不等式时才存在即时码。q rli 1 (10)i=1 同样，唯一可译码存在的充要条件由下述定理给出：Theorem 11 (McMillan 不等式). 唯一可译码存在的充要条件为：q rli 1 (11)i=1 上述两个定理都是存在性定理。 即时码的一种简单的构造方法是树图法，既用一棵码树来表示一个码。 码树最上面的节点称为根节点，每个节点伸出来的树枝的数目不大于码符 号的个数。树枝的另一头为子节点。没有子节点的节点称为 叶子节点，其 它的节点称为中间节点。 每个中间节点（包括根节点）都有 r 个子节点的树称为整树，某个节点
17、到 根节点所经过的树枝数称为此节点的深度，所有叶子节点的深度都相同的 整树称为完全树。 若将一棵完全树的叶子节点都安排为码字，那么就会得到一个等长码。 若所有的码字都安排在叶子节点上，则相应的变长码为即时码。5.2 唯一可译码判决准则 非奇异的等长码一定是唯一可译码。 如果一个变长码不满足 Kraft 不等式，则它一定不是唯一可译码。 但是满足 Kraft 不等式的变长码不一定是唯一可译码。为此，A.A. Sardinas和 G.W.Patterson 于 1957 年提出下述算法用于判断码 C 的唯一可译性。 此算法的原理如下图所示：A1A2A3. . . . . .Am1AmB1B2B3.
18、 . . . . .Bn1Bn 其中 Ai, Bi 都是码字。由上图可知，当且仅当某个有限长的码符号序列能 译成两种不同的码字序列时，此码不是唯一可译码，此时 B1 一定是 A1 的 前缀，而 A1 的尾随后缀一定是另一码字 B2 的前缀；而 B2 的尾随后缀又 是其它码字的前缀。最后，码符号序列的尾部一定是一个码字。 设 C 为码字集合，按以下步骤构造此码的尾随后缀集合 F ：1. 考查 C 中所有的码字，若 Wi 是 Wj 的前缀，则将相应的后缀作为一 个尾随后缀码放入集合 F 1 中；2. 考查 C 和 F i 两个集合，若 Wk C 是 Wj F i 的前缀或 Wk F i 是 Wj
19、C 的前缀，则将相应的后缀作为尾随后缀码放入集合 F i+1 中，i = 1, 2, . . .；3. F = F i 即为码 C 的尾随后缀集合；i4. 若 F 中出现了 C 中的元素，则算法终止，返回假（C 不是唯一可译 码）；否则若 F 中没有出现新的元素，则返回真。Example 12. 设有码 C 为 a, c, ad, abb, bad, deb, bbcde，请判断是否为唯一可 译码。解：按照上述算法构造右表所示的尾随后缀集 F 5 中的第一个元素正好是 C中的码字，因此 C 不是唯一可译码。CF 1F 2F 3F 4F 5adebdebadcbbcdebcdeadabbbadd
20、ebbbcdeExample 13. 设有码 C 为 0, 01, 11，请判断是否为唯一可译码。6 变长无失真信源编码定理 由上一节讨论可知，对于已知信源 S 可以用码符号 X 进行变长编码，而 且对同一信源可以得到多种即时码。究竟哪一种最好呢？Definition 14. 码的平均码长定义为码长的数学期望：qL = p(si)li (12)i=1其单位为r 进制码符号/信源符号。Definition 15. 码长的方差：q2li2 = p(si) (li L)(13)i=1Definition 16. 编码后平均每个码符号所携带的信息量称为编码后信道的信息传 输率：R = H(X) = H
21、(S)L(14)Definition 17. 对于某一信源来说，若存在一个唯一可译码，其平均码长 L 小于 所有其他唯一可译码的平均码长，则该码称为紧致码，或最佳码。Theorem 18. 离散信源 S 的熵为 H(S)，用 r 个码符号对其进行编码，则总可以 找到一种编码方法构成唯一可译码，使其平均码长满足：H(S) log r + 1 L H(S) (15)log r 根据 Kraft 定理我们知道只要满足 Kraft 不等式，就一定能够通过树图法构 造一个即时码。现在的问题是找到具有最小平均码长的即时码。 上述问题可等效为在满足 rli 1 的条件下寻找一组最佳的 l1, l2, . .
22、 . , lq ， 使得 L = pili 达到极小值。 应用 Lagrange 乘数法可求出：l = logpi。又因为所有的码长都应该是整数，所以有： logri l (16)N log rDefinition 20. 对信源 S 进行无失真编码所得到的平均码长为 L，则 L Hr (S)， 定义为编码效率， 1.Definition 21. 定义 = Hr (S)LHr (S)(17)为码的剩余度。 = 1 = 1 (18)L7 无失真信源编码技术 Huffman 编码 Shannon 编码 Shannon-Fano-Elias 编码 Fano 编码 算数编码 游程编码 通用编码Algo
23、rithm 1 Huffman Algorithm.1: procedure Huffman(si, pi)2: if q = 2 then3: 返回 s0 1 0, s1 1 14: else5: 降序排序 pi6: 缩减信源：创建一个符号 s 以取代 sq2, sq1，其概率为 p = pq2 +pq17: 递归调用 Huffman 以得到 s0, . . . , sq3, s 的编码：w0, . . . , wq3, w，相应的概率分布为 p0, . . . , pq3, p8: 返回编码：s0 1 w0, . . ., sq3 1 wq3, sq2 1 w0, sq1 1 w19: e
24、nd if10: end procedure7.1 Huffman 编码7.2 Shannon 编码1. 将信源符号按其概率降序排序2. 计算 logr pi 得到相应的码长 lii13. 计算第 i 个信源符号的累加概率：Pi = pkk=14. 将累加概率变为 r 进制小数5. 取小数点后 li 位作为码字输出7.3 Shannon-Fano-Elias 编码1. 计算 logr pi + 1 得到相应的码长 li i122. 计算第 i 个信源符号的修正累加概率：P i = pk + 1 pi3. 将累加概率变为 r 进制小数4. 取小数点后 li 位作为码字输出7.4 Fano 编码1
25、. 将信源符号按其概率降序排序k=1 2. 求取 k，使得 pi k i=1qi=k+1 pi 取得最小值，即在位置 k 将信源符号分为 两个子集，其概率和最为接近3. 为两个子集分别分配码符号 0 和 14. 对两个子集递归7.5 Huffman 编码的几个问题 加权码字的 Huffman 编码：Huffman 算法可以用于任意的 pi 0 的集合， 而不要求 pi = 1。在这种情况下，Huffman 编码可以得到最小的加权码i长和 wili 而不是平均码长。i 信源编码和 “20 问游戏”：假设我们需要设计一个最有效的问题序列用以 在一组对象中找到某个特定的对象。我们应该如何去设计这个问
26、题序列？ 假定对任何问题的回答都只可能是 Yes/No。首先，一个问题序列和一个对对象的编码是等效的。每个问题仅仅依赖于 前一个问题的答案，而答案的序列唯一地确定一个对象，并且每个对象都 对应一个不同的答案序列。如果我们将 Yes/No 分别对应 0 和 1，则相 应的解答过程就构成了一棵二叉树，每个码字对应一个对象，平均码长对 应问题的平均数目。通过对对象进行二进制 Huffman 编码，我们可以解决上述问题。 Huffman 编码和 “分片” 问题：在 “20 问游戏” 中 Huffman 编码相当于下列 形式的任意问题：X A 吗？其中 A 1, 2, . . . , q现在我们进一步限
27、制：对象集合已经排好序，并且问题只能是 “X a 吗？ ” 这种形式。则 Huffman 编码无法解决这种问题。而上述的 Fano 编码算法 正好是一个 “分片” 算法。p Huffman 编码和 Shannon 编码：针对某些特定的分布，采用 log 1 作为i码长将比 Huffman 编码方案差很多。Example 22. 考虑拥有两个信源符号的信源，其概率分布为：(0.9999, 0.0001)。采 用 Shannon 编码算法将为第二个信源符号选择 14 作为码长，而 Huffman 编码算 法对两个信源符号都使用 1bit 进行编码。p 对一个最佳码来说，是否每个信源符号对应的码长都小于 log 1 ？答案i是否定的。Example 23. 考虑这样一个信源：( 1 , 1 , 1 ,
