第 11 章信源编码 / Source Coding

11.1 基本概念

信源编码（Source Coding） 的核心目标：用尽可能少的比特（bit）表示信源输出的信息，在允许的失真范围内压缩数据冗余。

$$R \geq H(S)$$

其中 $R$ 为编码速率（bits/symbol），$H(S)$ 为信源熵（Entropy）。这是 Shannon 第一定理（信源编码定理）的量化表述——平均码长不可能低于信源熵。

11.1.1 离散信源与连续信源

类型	数学模型	熵的定义
离散信源（Discrete Source）	符号集 $S={s_1, s_2, \dots, s_N}$，概率 ${p_1, p_2, \dots, p_N}$	$H(S)=-\sum_{i=1}^{N} p_i \log_2 p_i$
连续信源（Continuous Source）	概率密度 $f(x)$	$h(X)=-\int_{-\infty}^{+\infty} f(x)\log_2 f(x),dx$（差熵）

实际工程中，连续信源必须先经过采样与量化（Sampling & Quantization） 转化为离散信源，再进行编码。

11.1.2 定长码与变长码

定长码（Fixed-length Code）：每个符号用相同位数表示。简单但效率低，如 ASCII 每字符 7 bit。
变长码（Variable-length Code）：高频符号短码、低频符号长码，平均码长更接近熵。

Kraft 不等式给出了唯一可译码（Uniquely Decodable Code）存在的充要条件：

$$\sum_{i=1}^{N} D^{-l_i} \leq 1$$

其中 $D$ 为码符号集大小（二进制时 $D=2$），$l_i$ 为第 $i$ 个符号的码字长度。

Shannon 信源编码定理：存在唯一可译的变长码，其平均码长 $\bar{L}$ 满足：

$$H(S) \leq \bar{L} < H(S) + 1$$

flowchart LR
    A["信源输出"] --> B["符号概率统计"]
    B --> C{"编码方式选择"}
    C -->|"符号概率分布均匀"| D["定长编码"]
    C -->|"符号概率分布不均匀"| E["变长编码"]
    E --> F["哈夫曼 / 算术编码"]
    D --> G["PCM / 均匀量化"]
    F --> H["压缩后的比特流"]
    G --> H
    style A fill:#1a1a2e,color:#fff
    style B fill:#1a1a2e,color:#fff
    style C fill:#16213e,color:#fff
    style D fill:#1a1a2e,color:#fff
    style E fill:#1a1a2e,color:#fff
    style F fill:#0f3460,color:#fff
    style G fill:#0f3460,color:#fff
    style H fill:#533483,color:#fff

11.2 哈夫曼编码 / Huffman Coding

哈夫曼编码（1952）是一种最优前缀码（Optimal Prefix Code） 的构造算法，保证平均码长最小。

11.2.1 编码步骤

将 $N$ 个符号按概率从大到小排列。
合并概率最小的两个符号为一个新节点，其概率为两者之和。
对合并的分支分别赋予 0 和 1。
重复步骤 2–3，直到只剩一个节点（根节点）。
从根到叶的路径即为该符号的码字。

11.2.2 编码示例

设信源 $S={s_1, s_2, s_3, s_4, s_5}$，概率分别为 $0.4,;0.2,;0.2,;0.1,;0.1$。

符号	概率 $p_i$	码字	码长 $l_i$	$p_i \cdot l_i$
$s_1$	0.4	`0`	1	0.4
$s_2$	0.2	`10`	2	0.4
$s_3$	0.2	`110`	3	0.6
$s_4$	0.1	`1110`	4	0.4
$s_5$	0.1	`1111`	4	0.4

平均码长：

$$\bar{L} = \sum_{i=1}^{5} p_i l_i = 0.4 + 0.4 + 0.6 + 0.4 + 0.4 = 2.2 \text{ bits/symbol}$$

信源熵：

$$H(S) = -\sum_{i=1}^{5} p_i \log_2 p_i \approx 2.122 \text{ bits/symbol}$$

编码效率：

$$\eta = \frac{H(S)}{\bar{L}} = \frac{2.122}{2.2} \approx 96.5%$$

11.2.3 哈夫曼编码伪代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
function HUFFMAN(symbols, probs):
    Q ← min-priority queue of (symbol, prob)
    while |Q| > 1:
        x ← EXTRACT-MIN(Q)   // 最小概率节点
        y ← EXTRACT-MIN(Q)   // 次小概率节点
        z ← new node
        z.left  ← x;  z.right ← y
        z.prob  ← x.prob + y.prob
        INSERT(Q, z)
    root ← EXTRACT-MIN(Q)
    return BUILD_CODE_TABLE(root)

function BUILD_CODE_TABLE(node, prefix=""):
    if node is leaf:
        table[node.symbol] ← prefix
    else:
        BUILD_CODE_TABLE(node.left,  prefix + "0")
        BUILD_CODE_TABLE(node.right, prefix + "1")
    return table

11.2.4 最优性分析

哈夫曼编码满足前缀条件（Prefix Condition）——任何码字都不是另一个码字的前缀，因此无需分隔符即可唯一解码。

其最优性基于贪心策略的交换论证：若存在比哈夫曼更优的前缀码，则可以通过交换使概率最小的符号拥有最长码字，从而导出矛盾。

练习：对信源 $S={a,b,c,d}$，概率分别为 $0.5, 0.25, 0.125, 0.125$，构造哈夫曼码并计算编码效率。（提示：效率应为 100%。）

11.3 算术编码 / Arithmetic Coding

哈夫曼编码为每个符号分配整数长度的码字，当符号概率不是 $2^{-k}$ 的形式时存在效率损失。算术编码（Arithmetic Coding） 用一个 $[0,1)$ 区间内的实数（浮点数）表示整个符号序列，理论上可无限逼近信源熵。

11.3.1 核心思想

将输入符号序列映射到 $[0,1)$ 上的一个子区间，区间长度等于该序列的概率，区间内的任意实数即为编码结果。

$$[\text{Low}, \text{High}) \xrightarrow{\text{符号 } s_i} [\text{Low} + R \cdot C_{\text{low}}(s_i),;; \text{Low} + R \cdot C_{\text{high}}(s_i))$$

其中 $R = \text{High} - \text{Low}$ 为当前区间宽度，$C_{\text{low}}(s_i)$、$C_{\text{high}}(s_i)$ 为符号 $s_i$ 的累积概率上下界。

11.3.2 编码伪代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
function ARITHMETIC_ENCODE(sequence, model):
    Low  ← 0.0
    High ← 1.0
    for symbol in sequence:
        R    ← High - Low
        High ← Low + R × CumHigh(symbol)
        Low  ← Low + R × CumLow(symbol)
    return any value in [Low, High)  // 通常取 Low 的二进制表示

function ARITHMETIC_DECODE(code, model, num_symbols):
    value ← code
    result ← empty list
    for i = 1 to num_symbols:
        R ← High - Low
        scaled ← (value - Low) / R
        symbol ← LOOKUP_CUMULATIVE(scaled)
        result.append(symbol)
        // 缩小区间（同编码步骤）
        High ← Low + R × CumHigh(symbol)
        Low  ← Low + R × CumLow(symbol)
    return result

11.3.3 精度问题与工程实现

纯浮点实现面临两个问题：

有限精度：区间不断缩小，浮点数精度不足导致下溢。
乘法开销：每次迭代需两次乘法。

解决方案：

方法	原理	适用场景
归一化（Renormalization）	当 High < 0.5 或 Low ≥ 0.5 时，输出比特并放大区间	通用
表查找（Table-based）	预计算区间映射表，用整数加法和移位替代乘法	嵌入式/实时系统
QM 编码器	基于概率状态机，纯整数运算	JPEG 标准选项

11.3.4 效率比较

$$\eta_{\text{Huffman}} \geq 1 - p_{\max}$$

$$\eta_{\text{Arithmetic}} \approx 1 - \frac{\epsilon}{n}$$

其中 $p_{\max}$ 为最大符号概率，$n$ 为序列长度，$\epsilon$ 为很小的常数。对于长序列，算术编码的效率优势明显。

JPEG 2000 和 H.264/AVC 的 CABAC 模式均采用算术编码。

11.4 游程编码与 LZW / Run-Length & LZW

11.4.1 游程编码（RLE）

游程编码（Run-Length Encoding, RLE） 将连续重复的符号序列用 (符号, 重复次数) 对表示。

示例：AAAABBBCCDAAA → A4B3C2D1A3（13 字符 → 10 字符）

RLE 实现简单，但仅对高冗余数据（如传真、简单图形）效果显著。

11.4.2 LZW 编码

LZW（Lempel-Ziv-Welch） 编码是一种基于字典（Dictionary） 的自适应编码算法，无需预先传输概率表。

编码步骤

初始化字典为所有单符号条目（如 ASCII 的 256 个字符）。
读入输入序列，维护当前字符串 $W$。
不断读入下一字符 $K$：
- 若 $W+K$ 在字典中：$W \leftarrow W+K$
- 否则：输出 $W$ 的字典索引，将 $W+K$ 加入字典，$W \leftarrow K$
序列结束时，输出 $W$ 的索引。

LZW 编码伪代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
function LZW_ENCODE(input):
    dict ← {所有单字符 → 索引 0..255}
    next_code ← 256
    W ← first character of input
    output ← empty list

    for each K in rest of input:
        if (W + K) in dict:
            W ← W + K
        else:
            output.append(dict[W])
            dict[W + K] ← next_code
            next_code ← next_code + 1
            W ← K

    output.append(dict[W])  // 输出最后一个 W
    return output

解码原理

解码端维护相同的初始字典。收到索引后：

查字典输出对应字符串。
将上一个字符串的首字符拼接至上一个字符串后，作为新字典条目。

这一巧妙设计保证编解码双方字典同步，无需传输字典本身。

编解码示例

输入：ABABABA

步骤	W	K	W+K 在字典？	输出	新字典条目
1	A	B	否	65(A)	256=AB
2	B	A	否	66(B)	257=BA
3	A	B	是(256)	—	—
4	AB	A	否	256(AB)	258=ABA
5	A	B	是(256)	—	—
6	AB	A	是(258)	—	—
结束	ABA	—	—	258(ABA)	—

输出码流：65, 66, 256, 258（4 个索引替代 7 个字符）

flowchart TD
    A["输入符号流"] --> B["初始化字典
（单字符条目）"]
    B --> C["读入字符 K
拼接 W+K"]
    C --> D{"W+K 在字典中？"}
    D -->|是| E["W ← W+K"]
    E --> C
    D -->|否| F["输出 W 的索引"]
    F --> G["W+K 加入字典"]
    G --> H["W ← K"]
    H --> C
    C -->|"序列结束"| I["输出最后 W 的索引"]
    style A fill:#1a1a2e,color:#fff
    style B fill:#16213e,color:#fff
    style C fill:#1a1a2e,color:#fff
    style D fill:#0f3460,color:#fff
    style E fill:#1a1a2e,color:#fff
    style F fill:#533483,color:#fff
    style G fill:#533483,color:#fff
    style H fill:#1a1a2e,color:#fff
    style I fill:#533483,color:#fff

11.5 工程应用

11.5.1 PCM 编码 / Pulse Code Modulation

PCM 是模拟信号数字化的基础方法：

$$\text{模拟信号} \xrightarrow{\text{采样}} \xrightarrow{\text{量化}} \xrightarrow{\text{编码}} \text{PCM 码流}$$

采样率：由 Nyquist 定理决定，$f_s \geq 2f_{\max}$。
量化：均匀量化（线性 PCM）或非均匀量化（$\mu$律/A律）。
编码：每个样值用 $n$ bit 表示，编码速率 $R = n \cdot f_s$。

G.711 标准（电话语音）：采样率 8 kHz，8 bit/样值，速率 64 kbps。采用 A律（欧洲/中国）或 $\mu$律（北美/日本）压扩，对小信号提升信噪比。

11.5.2 图像压缩：JPEG

JPEG（Joint Photographic Experts Group）编码流程：

颜色空间转换：RGB → YCbCr，利用人眼对色度不敏感的特性。
分块 DCT：8×8 像素块做离散余弦变换（Discrete Cosine Transform）。
量化：用量化表除以 DCT 系数（这是有损压缩的关键步骤）。
熵编码：直流系数用 DPCM + 哈夫曼；交流系数用游程编码 + 哈夫曼。

$$F(u,v) = \frac{1}{4} C(u)C(v) \sum_{x=0}^{7}\sum_{y=0}^{7} f(x,y) \cos\frac{(2x+1)u\pi}{16}\cos\frac{(2y+1)v\pi}{16}$$

JPEG 2000 用小波变换（DWT）替代 DCT，熵编码采用算术编码，支持渐进传输和感兴趣区域（ROI）编码。

11.5.3 视频压缩：MPEG 系列

视频压缩利用时间冗余（帧间预测）和空间冗余（帧内编码）：

标准	年代	关键技术	典型应用
MPEG-1	1993	运动补偿 + DCT	VCD
MPEG-2 / H.262	1995	B帧、场/帧编码	DVD、数字电视
MPEG-4 / H.264	2003	CABAC、1/4像素运动估计	Blu-ray、流媒体
H.265 / HEVC	2013	CTU、SAO、并行编码	4K/8K 视频
H.266 / VVC	2020	AI 辅助编码工具	8K、360° 视频

flowchart LR
    A["视频帧"] --> B["运动估计/补偿"]
    B --> C["残差 DCT/变换"]
    C --> D["量化"]
    D --> E["熵编码
CABAC/CAVLC"]
    E --> F["压缩码流"]
    style A fill:#1a1a2e,color:#fff
    style B fill:#16213e,color:#fff
    style C fill:#0f3460,color:#fff
    style D fill:#0f3460,color:#fff
    style E fill:#533483,color:#fff
    style F fill:#533483,color:#fff

11.5.4 音频压缩

MP3（MPEG-1 Layer III）：利用心理声学模型（Psychoacoustic Model），掩蔽效应（Masking Effect）使得不可听见频率分量可被丢弃，典型压缩比 10:1。
AAC（Advanced Audio Coding）：MP3 的继任者，更高编码效率，用于 iTunes、YouTube。
Opus：开源编码器，动态切换 CELT（频域）和 SILK（时域），覆盖语音到音乐全场景。

11.6 小结

三大编码方法对比

特性	哈夫曼编码	算术编码	LZW 字典编码
编码类型	变长前缀码	区间编码	自适应字典
是否需要概率表	是	是	否（自适应）
整数比特约束	是（每个符号整数比特）	否（可分数比特）	是（字典索引）
最优性	符号级最优	序列级渐进最优	通用（渐近最优）
计算复杂度	低	中	低
典型应用	JPEG、Deflate	JPEG 2000、H.264 CABAC	GIF、TIFF、Unix compress
对输入统计的依赖	强	强	弱（自适应）
有损/无损	无损	无损	无损

思考题

证明 Kraft 不等式是前缀码存在的充要条件。
对概率分布 ${0.6, 0.4}$ 的二元信源，哈夫曼编码和算术编码的平均码长分别逼近多少？哪个更优？
LZW 编码中，编解码双方为何能保持字典同步而不需要传输字典？试通过一个 5 字符以上的例子验证。
为什么 JPEG 选用 DCT 而非 DFT 进行变换编码？
若要将一段 48 kHz / 24 bit 的立体声音频无损压缩，你会选择哪种熵编码方案？给出理由。
HEVC 的 CABAC 模块中，上下文模型（Context Model）的初始化依赖哪些参数？这对编码效率有什么影响？

第 11 章 信源编码 / Source Coding#

11.1 基本概念#

11.1.1 离散信源与连续信源#

11.1.2 定长码与变长码#

11.2 哈夫曼编码 / Huffman Coding#

11.2.1 编码步骤#

11.2.2 编码示例#

11.2.3 哈夫曼编码伪代码#

11.2.4 最优性分析#

11.3 算术编码 / Arithmetic Coding#

11.3.1 核心思想#

11.3.2 编码伪代码#

11.3.3 精度问题与工程实现#

11.3.4 效率比较#

11.4 游程编码与 LZW / Run-Length & LZW#

11.4.1 游程编码（RLE）#

11.4.2 LZW 编码#

编码步骤#

LZW 编码伪代码#

解码原理#

编解码示例#

11.5 工程应用#

11.5.1 PCM 编码 / Pulse Code Modulation#

11.5.2 图像压缩：JPEG#

11.5.3 视频压缩：MPEG 系列#

11.5.4 音频压缩#

11.6 小结#

三大编码方法对比#

思考题#