信息论基础与编码 — 无失真信源编码

Contents

1 无失真信源编码基本概念

1 2 5 6

2 定长无失真信源编码

3 渐进等同分割性

4 定长无失真信源编码定理

5 变长无失真编码 8 5.1 Kraft 不等式 ................................................................................................. 8 5.2 唯一可译码判决准则 . . . . . . . . . . . . . . . . . . . . . . . . . 9

6 变长无失真信源编码定理

10

7 无失真信源编码技术 11 7.1 Huffman 编码 ............................................................................................. 12 7.2 Shannon 编码 .............................................................................................. 12 7.3 Shannon-Fano-Elias 编码 ........................................................................... 12 7.4 Fano 编码 .................................................................................................... 12 7.5 Huffman 编码的几个问题 ......................................................................... 13 7.6 算数编码 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 7.7 游程编码 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 7.8 通用编码 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 7.9 几种编码方案的性能对比 . . . . . . . . . . . . . . . . . . . . . . . 22

1 无失真信源编码基本概念

? 对于信源来说有两个基本问题：如何计算信源输出的信息量；如何有效地 表示信源输出，即在不失真或允许一定失真的条件下，如何用尽可能少的 符号来表示信源，以便提高信息传输的效率。

? 编码实质上是对信源的原始符号按照一定的数学规则进行的一种变换。

1

S : {s1, s2, . . . , sq } ?

信源编码器 2, . . . , Wq } C : {W1, W ??X : {x1, x2, . . . , xr }

Figure 1: 信源编码器模型

? 将信源符号集合中的 si（或者长为 N 的信源符号序列）变换成由 xj 组成 的长度为 li 的一一对应的码符号序列 Wi。 ? 编码的一些基本概念

– 这种码符号序列 Wi 称为码字；长度 li 称为码字长度，简称码长；全 体码字的集合 C 称为码。 – 若码符号集合为 X = {0, 1}，则所得的码字都是二元序列，称为二元 码 或二进制码。 – 若一个码中所有码字的码长都相等，则称为等长码；否则为变长码。 – 若一个码中无重复码字，则称为非奇异码；否则为奇异码。

– 若码符号集合中每个码符号所占的传输时间都相同，则所得的码称 为同价码。 – 若任意一串有限长的码符号序列只能被唯一地译为对应的信源符号 序列，则称此码为唯一可译码。 – 若某个唯一可译码在译码时无需参考后续的码符号就能立即作出判 断，将码符号序列译成相应的信源符号序列。则称此码为即时码；否 则为 非即时码。即时码又称为逗点码、非延长码。

2 定长无失真信源编码

? 对一个信源进行定长编码时每个信源符号所需要的二进制码符号个数（码 长）将由信源符号的个数唯一决定：L ≥ H0(X) = log2 ∥X ∥ Definition 1. X 的原始编码容量定义为：

H0(X) = log2 ∥X ∥ ? 当信源符号个数正好是 2 的幂次时，可以得到整数 L = H0(X)；

(1)

? 否则 L = ?H0(X)?。此时实际码长略大于信源的最大熵，效率不高，可以 通过对信源进行扩展的方法来提高编码效率。 ? 另一种提高编码效率的手段为近似无失真编码。 ? 无失真编码可分为严格无失真和近似无失真两种情况。

2

? 严格无失真编码是一个信源符号到码字的一一映射；而近似无失真则会将 一些不同的信源符号映射为相同的码字，因此一旦信源真的产生了这些被 混淆的信源符号，就会产生一次译码失败。我们通常用 δ 来表示信源产生 被混淆的符号的概率。当 δ 足够小时，这种近似无失真的编码方法在实际 生产中也就可以近似认为是无失真的了。

Example 2. 给定一 8 符号信源：

[a b c d [ ]

X = 1 1 1 3

P (X) 4 4 4 16

e 1 64 f 1 64

g 1 64 ] h 1 64

(2)

当要求 δ = 0 时对此信源进行二进制等长编码，每个信源符号需要 3 个二进制 码符号，即 L = 3bit.

我们注意到 Pr{s ∈ {a, b, c, d}} = 15/16，因此如果我们愿意承受 1/16 的译 码失败概率的话，就可以将信源的后 4 个符号忽略，只对前 4 个符号编码，此 时 L = 2bit，信源得到了有效的压缩。

? 为此，我们定义两个新的概念：

Definition 3 (最小 δ 充分子集). Xδ 为包含元素个数最少的、满足下述条件的、 X 的子集：

Pr{x ∈ Xδ } ≥ 1 ? δ (3) Definition 4 (基本编码容量). X 的基本编码容量为：

Hδ (X) = log2 ∥Xδ ∥ Example 5. 图2显示了上例中基本编码容量与 δ 的关系：

(4)

Figure 2: 基本编码容量与 δ 的关系 I

3