4.4 信源编码与率失真理论

前几节的熵与散度都是描述性的量。本节讨论它们的一个操作含义：压缩的极限。一个数据源产生的符号序列，在允许无损恢复的前提下，最少需要多少比特表示每个符号。这个问题的答案由熵给出，而且这个极限是可以逼近的，构造方法也已经成熟（Huffman 编码、算术编码、字典编码）。

本节分两条线索。第一条是无损压缩：先建立编码的语言（码字、前缀码、唯一可译码），给出码长必须满足的 Kraft 不等式，再证明信源编码定理（香农第一定理）给出的界 $H(X)\le \overline{L}<H(X)+1$，最后讨论三种实际算法与它们逼近极限的方式。第二条是有损压缩：允许恢复有误差时，最优的压缩率由率失真函数（rate-distortion function）给出，它等于在给定失真水平下互信息的最小值。这一节的内容把 4.1 节的典型性理论转化为可操作的结论，也为 4.5 节的信道容量提供对照：压缩关心把信源压到多小，传输关心在噪声下能传多快，两个问题分别由熵与互信息定价。

4.4.1 无损压缩的问题设定

编码与码字

信源编码（source coding）把信源符号映射为二进制串。设信源取值于 $\mathcal{X}$，编码器为每个符号 $x$ 指定一个码字 $c(x)\in \{0,1{\}}^{\ast }$，码字的长度为 $l(x)$。对一段长度为 $n$ 的序列，编码器逐个符号编码后拼接（逐符号编码），总长度为 $\sum _{i}l(x_i)$。平均码长（average code length）为

$$\overline{L}=\sum _{x\in \mathcal{X}}p(x)l(x)$$

压缩的目标是在保证可恢复的前提下最小化 $\overline{L}$。

唯一可译与前缀码

可恢复性有两个层次。唯一可译码（uniquely decodable code）要求任意两条不同的符号序列编码后也不相同，因此接收端总能还原原始序列。前缀码（prefix code，也称即时码）要求任何一个码字都不是另一个码字的前缀，接收端可以在读到完整码字时立刻译码，不需要缓冲。

两类码的关系是包含：前缀码一定是唯一可译码，反之不然。前缀码的便利在于译码过程是流式的，实现简单，因此在实践中占主导。存在唯一可译但非前缀的码，其平均长度可以更短，但译码需要等待整个序列，实用价值有限。

4.4.2 Kraft 不等式

陈述

给定一组正整数码长 $l_1,\dots ,l_m$（$m=|\mathcal{X}|$），存在前缀码以这些长度为码长的充要条件是

$$\sum _{i=1}^m{2}^{-l_i}\le 1$$

这就是 Kraft 不等式。它的含义是：把码字空间看作一棵二叉树的叶节点，深度为 $l_i$ 的叶节点占据 $2^{-l_i}$ 的长度配额，全部叶子占用的配额之和不能超过 $1$。

证明思路

必要性用树结构论证。深度为 $l$ 的码字在二叉树中占据一个包含 $2^{l_{max}-l}$ 个最深叶子的子树，两个不同码字对应的子树不能相交（否则一个是另一个的前缀）。把所有子树的大小按 $2^{-l_i}$ 归一化后相加不超过 $1$，即得不等式。

充分性的构造用贪心：把码长按升序排列，依次为每个码字分配最左侧的可用叶子。由于总配额不超过 $1$，每一步都能找到可用位置，构造出的码满足前缀条件。

Kraft 不等式的作用是把设计前缀码的问题简化为选择码长的问题：只要码长满足不等式，就一定存在对应的前缀码，无需关心具体码字如何分配。这一简化是信源编码定理证明的关键一步。

4.4.3 信源编码定理

定理的内容

信源编码定理（source coding theorem，香农第一定理）断言：对离散无记忆信源，任何唯一可译码的平均码长满足

$$\overline{L}\ge H(X)$$

且存在前缀码使

$$\overline{L}<H(X)+1$$

下界部分说明熵是压缩的极限，无论算法多复杂都无法突破；上界部分说明这个极限可以在 $1$ 比特的余量内达到。把 $n$ 个符号作为一个块编码，余量按比例缩小，因此块编码（block coding）可以任意接近 $H(X)$：

$$H(X)\le \frac{{\overline{L}}_n}{n}<H(X)+\frac{1}{n}$$

下界的证明

用 Kraft 不等式配合一个不等式即可。由 Kraft 不等式 $\sum _x{2}^{-l(x)}\le 1$，两边取对数无关，改用如下推导：

$$\overline{L}-H(X)=\sum _{x}p(x)l(x)+\sum _{x}p(x)\log p(x)=\sum _{x}p(x)\log \frac{p(x)}{2^{-l(x)}}$$

把 $2^{-l(x)}/\sum _{x^{\prime }}{2}^{-l(x^{\prime })}$ 视为一个概率分布 $q(x)$，上式等于 $D_{\mathrm{KL}}(p\parallel q)$，由 KL 散度的非负性得到 $\overline{L}\ge H(X)$。等号成立当且仅当 $p(x)=2^{-l(x)}$ 对所有 $x$ 成立，即各符号的概率恰好是 $2$ 的负整数次幂。

上界的证明

取码长 $l(x)=\lceil -\log p(x)\rceil$，即向上取整到最近的整数。此时

$$-\log p(x)\le l(x)<-\log p(x)+1$$

两边按 $p(x)$ 加权平均，中间项是 $\overline{L}$，左端是 $H(X)$，右端是 $H(X)+1$，合起来即

$$H(X)\le \overline{L}<H(X)+1$$

还需验证这组码长满足 Kraft 不等式：

$$\sum _x{2}^{-l(x)}\le \sum _x{2}^{\log p(x)}=\sum _{x}p(x)=1$$

其中用到 $2^{-l(x)}\le 2^{\log p(x)}=p(x)$（由 $l(x)\ge -\log p(x)$ 得到）。因此存在前缀码达到这一码长组合，取整带来的最多 $1$ 比特损失是这一构造的代价。

达到极限的途径

上界中的 $1$ 比特是多符号逐次编码的固定开销。两条路径可以缩小它。第一条是块编码：把 $k$ 个符号拼成一个大符号，符号表大小变为 $|\mathcal{X}{|}^k$，固定开销仍为 $1$ 比特，但分摊到 $k$ 个符号上变为 $1/k$。第二条是算术编码（4.4.4 节），它不做逐符号取整，直接把整个序列映射到一个区间，平均码长可以接近熵率而不含 $1$ 比特损失。

import numpy as np

def huffman_code_lengths(probs):
    """构造 Huffman 编码并返回各符号的码长与平均码长"""
    probs = np.asarray(probs, dtype=float)
    nodes = [(p, [i]) for i, p in enumerate(probs)]
    lengths = np.zeros(len(probs), dtype=int)
    while len(nodes) > 1:
        nodes.sort(key=lambda t: t[0])
        (p1, s1), (p2, s2) = nodes[0], nodes[1]
        for i in s1 + s2:
            lengths[i] += 1
        nodes = nodes[2:] + [(p1 + p2, s1 + s2)]
    return lengths

def entropy(p):
    p = np.asarray(p, dtype=float)
    p = p[p > 0]
    return float(-np.sum(p * np.log2(p)))

probs = np.array([0.4, 0.2, 0.15, 0.1, 0.08, 0.05, 0.02])
L = huffman_code_lengths(probs)
avg = float(np.dot(probs, L))
H = entropy(probs)

print(f"各符号码长 = {L}")
print(f"平均码长   = {avg:.4f} 比特/符号")
print(f"熵         = {H:.4f} 比特/符号")
print(f"冗余       = {avg - H:.4f} 比特/符号（应小于 1）")

4.4.4 三种实用的编码方法

Huffman 编码

Huffman 编码（Huffman coding）构造最优前缀码，步骤是反复合并概率最小的两个符号：建立叶节点，每次取出概率最小的两个节点合并为父节点（概率相加），重复到只剩一个根节点，再自上而下分配比特。

它的最优性可以证明：对任意其他前缀码，Huffman 码的平均码长不大于它。证明用交换论证：最优前缀码中概率最小的两个符号必然对应最深的一层且互为兄弟（否则把更深的码字与它们交换可以缩短平均码长），因此可以把这两个符号合并后递归处理，与构造过程一致。

Huffman 编码的局限有三条。第一，它要求知道信源的概率分布，且分布变化后需要重新构造码表。第二，逐符号编码存在 4.4.3 节分析的 $1$ 比特内开销，接近熵率需要块编码，而块编码的码表大小随块长指数增长。第三，它无法利用符号之间的依赖（有记忆信源），需要先用模型去除相关性。

算术编码

算术编码（arithmetic coding）把整个符号序列映射到 $[0,1)$ 内的一个区间。初始区间为 $[0,1)$，每读入一个符号，按该符号在信源分布中的累积概率把当前区间划分为若干子区间，取对应子区间作为新区间。序列处理完后，用一个二进制小数指向最终区间内的任意点，该小数的长度由区间宽度决定：

$$\text{码长}\approx -{\log }_2(\text{区间宽度})=\sum _t-{\log }_{2}p(x_t)$$

区间宽度正是序列概率的乘积，因此码长直接等于序列的自信息。把所有可能序列的概率乘起来看，平均码长收敛到熵率，不含逐符号取整的损失。

算术编码的两个工程要点。第一，区间需要以有限精度表示，实践中用整数区间与重归一化操作避免下溢出；第二，需要一个终止符号或显式给出序列长度，接收端才能确定何时停止。与 Huffman 相比，算术编码的优势在概率分布不均匀时更明显，它也是现代压缩工具（文本、图像、视频编码）中的核心组件。

import numpy as np

def arithmetic_encode_length(seq, probs):
    """按算术编码的区间收缩计算所需比特数（不实现整数化）"""
    low, high = 0.0, 1.0
    cum = np.concatenate([[0.0], np.cumsum(probs)])
    for s in seq:
        width = high - low
        high = low + width * cum[s + 1]
        low = low + width * cum[s]
    width = high - low
    return -np.log2(width), width

probs = np.array([0.7, 0.2, 0.1])
rng = np.random.default_rng(9)

for n in [10, 100, 1000]:
    seq = rng.choice(len(probs), size=n, p=probs)
    bits, width = arithmetic_encode_length(seq, probs)
    self_info = -np.sum(np.log2(probs[seq]))
    print(f"n = {n:4d}：算术编码所需比特 = {bits:.3f}，序列自信息 = {self_info:.3f}，"
          f"每符号 = {bits / n:.4f}（熵 = {-(probs * np.log2(probs)).sum():.4f}）")
# 每符号比特数随 n 增大收敛到熵，没有逐符号取整的固定开销

字典编码

前两种方法依赖已知的概率分布。字典编码（dictionary coding）不需要分布，通过记录重复出现的子串来压缩，适用于有长距离重复的数据（文本、日志、程序代码）。

LZ77 维护一个滑动窗口，对每个位置寻找窗口内最长的匹配串，用（距离，长度，下一个字符）三元组表示。LZ78 维护一个动态增长的短语字典，把新出现的短语加入字典并输出（短语编号，下一个字符）。两者构成的家族（包括其改进版本 LZW、DEFLATE 使用的 LZ77 变体）是通用压缩工具的基础，gzip、zip、png 都使用这一系算法。

字典编码的压缩率不直接由熵给出，因为它利用的是序列内部的结构而不是符号频率。当序列来自有限状态的源（如文本）时，压缩率渐近趋于源的条件熵率（4.1 节），这解释了为什么长文本上的压缩比更高。它的自适应特性使分布未知时也能工作，代价是对短序列或高熵数据几乎没有压缩效果。

4.4.5 微分熵与连续信源

定义与性质差异

连续随机变量的微分熵（differential entropy）定义为

$$h(X)=-\int f(x)\log f(x)dx$$

它与离散熵有三个重要差别。第一，微分熵可以为负：均匀分布 $U(0,a)$（$a<1$）的微分熵为 $\log a<0$。第二，它依赖坐标的单位：改变量纲（例如把米换成厘米）会使微分熵增加 $\log 100$，因此单独报告微分熵的数值没有绝对意义，只有两个微分熵之差（如互信息）才有单位无关的含义。第三，离散熵的上界是 $\log |\mathcal{X}|$，而微分熵在支撑无界时无上界。

连续情形下可操作的量是互信息与 KL 散度，它们由两个微分熵之差定义，单位依赖被抵消：

$$I(X;Y)=h(X)-h(X\mid Y),D_{\mathrm{KL}}(f\parallel g)=\int f\log \frac{f}{g}$$

最大微分熵与熵功率不等式

给定方差约束的最大微分熵分布是正态分布：

$$h(X)\le \frac{1}{2}\log \left(2\pi e{\sigma }^2\right)$$

这一结论与 4.3 节的最大熵推导一致，是正态分布在给定方差下引入假设最少的另一种表述。它在信道容量推导中反复使用。

熵功率不等式（entropy power inequality）给出独立随机变量之和的微分熵下界：

$$e^{2h(X+Y)}\ge e^{2h(X)}+e^{2h(Y)}$$

对独立的 $X$ 与 $Y$ 成立。定义熵功率为 $N(X)=\frac{1}{2\pi e}{e}^{2h(X)}$，不等式变为 $N(X+Y)\ge N(X)+N(Y)$，形式与方差的相加规则相同。这一结果说明：在给定的熵水平下，高斯分布使和的熵最小，因此高斯是最不利的情形，这使它在最坏情形分析中成为标准参照。

4.4.6 率失真理论

问题设定

无损压缩要求完全恢复原始数据，实际中往往允许一定误差。率失真理论（rate-distortion theory）处理允许误差时的压缩极限。引入失真度量（distortion measure）$d(x,\hat{x})\ge 0$ 衡量原始符号 $x$ 与重建符号 $\hat{x}$ 的差异，常用的是汉明失真（不同则为 $1$）与平方误差失真。对逐符号失真的期望值

$$D=E[d(X,\hat{X})]$$

限制不超过给定水平，寻找所需的最小信息率。

率失真函数

率失真函数（rate-distortion function）定义为在失真不超过 $D$ 的条件下，$X$ 与重建 $\hat{X}$ 之间互信息的最小值：

$$R(D)=\underset{p(\hat{x}\mid x):E[d(X,\hat{X})]\le D}{min}I(X;\hat{X})$$

互信息在这里的角色是信息率的度量：编码器把 $X$ 压缩成携带 $I(X;\hat{X})$ 比特的描述，解码器据此重建 $\hat{X}$。函数有以下性质。

单调不增：允许的失真越大，所需的信息率越小。

凸性：$R(D)$ 是凸函数，因此率失真的权衡边界是凸的，不存在用更多失真换取更少信息率的局部最优陷阱。

在 $D=0$ 处等于熵：无损压缩是零失真压缩，因此 $R(0)=H(X)$，与信源编码定理一致。

香农下界与可达性：$R(D)$ 是任何编码方案的率的下界，同时存在编码方案可以任意接近它。达到下界的方式仍然是块编码：把长序列作为一个整体处理，用典型性理论证明存在满足失真约束的码本，其大小约为 $2^{nR(D)}$。

高斯信源的率失真函数

设 $X\sim N(0,{\sigma }^2)$，失真为平方误差，则

$$R(D)=\{\begin{array}{ll}\frac{1}{2}\log \frac{{\sigma }^2}{D},& 0\le D\le {\sigma }^2\\ 0,& D>{\sigma }^2\end{array}$$

以比特为单位时前面的系数为 $\frac{1}{2}$。这条曲线的含义是：把均方误差压到 $D$ 需要每符号 $\frac{1}{2}\log \frac{{\sigma }^2}{D}$ 比特；失真降到方差以下没有收益，因为此时可以完全不传输而用零重建（失真为 ${\sigma }^2$）。

推导思路用最大微分熵与反向信道论证：给定失真约束，重建误差 $X-\hat{X}$ 的方差不超过 $D$，而由 $I(X;\hat{X})=h(X)-h(X\mid \hat{X})$ 与 $h(X\mid \hat{X})\le \frac{1}{2}\log (2\pi eD)$ 得到下界；高斯情形下等号可以取到，因此下界可达。

import numpy as np

# 伯努利信源在汉明失真下的率失真函数
def rate_distortion_bernoulli(p, n_grid=200):
    """计算 R(D)，D 从 0 到 min(p, 1-p)"""
    D_max = min(p, 1 - p)
    Ds = np.linspace(1e-6, D_max, n_grid)
    Rs = []
    for D in Ds:
        # 最优测试信道：以概率 alpha 翻转，选择使 I 最小的 alpha
        from scipy import optimize

        def mutual(alpha):
            # 信道：P(hat != x) = alpha
            # 联合分布
            q = np.array([[p * (1 - alpha), p * alpha],
                          [(1 - p) * alpha, (1 - p) * (1 - alpha)]])
            px = q.sum(axis=1, keepdims=True)
            py = q.sum(axis=0, keepdims=True)
            with np.errstate(divide="ignore", invalid="ignore"):
                terms = np.where(q > 0, q * np.log2(np.where(q > 0, q / (px * py), 1.0)), 0.0)
            return float(terms.sum())

        # 失真 D = alpha
        val = mutual(D)
        Rs.append(val)
    return Ds, np.array(Rs)

def entropy(p):
    ps = np.array([p, 1 - p])
    ps = ps[ps > 0]
    return float(-np.sum(ps * np.log2(ps)))

p = 0.3
Ds, Rs = rate_distortion_bernoulli(p)
print(f"伯努利信源 p = {p}，熵 H(X) = {entropy(p):.4f} 比特")
print(f"D = 0.000001 处 R ≈ {Rs[0]:.4f}（应接近 H(X)）")
print(f"D = {Ds[-1]:.4f}（= min(p,1-p)）处 R ≈ {Rs[-1]:.4f}（应接近 0）")
for D in [0.05, 0.1, 0.2]:
    idx = np.argmin(np.abs(Ds - D))
    print(f"  D = {D:.2f}：R = {Rs[idx]:.4f} 比特/符号")
# R(D) 单调递减且在 D = 0 处等于熵，与理论一致

# 高斯信源的率失真函数
sigma2 = 4.0
for D in [0.5, 1.0, 2.0, 4.0]:
    R = 0.5 * np.log2(sigma2 / D) if D < sigma2 else 0.0
    print(f"高斯信源 sigma^2 = {sigma2}，D = {D}：R = {max(R, 0):.4f} 比特")

4.4.7 本节小结

压缩的两个极限

本节给出压缩的两条极限。无损压缩的极限是熵：Kraft 不等式把前缀码的设计归结为码长的选择，信源编码定理由此得到下界 $H(X)$ 与上界 $H(X)+1$，两者的差距是多符号逐次编码的固定开销，块编码可以按比例缩小它。等号成立的条件是各符号概率恰为 $2$ 的负整数次幂，这一条件在实际数据中很少满足，因此通常存在一个正的冗余。三种实用方法各有侧重：Huffman 编码在已知分布时达到最优前缀码；算术编码把整个序列映射到区间，码长等于序列自信息，可以逼近熵率；字典编码不依赖分布，利用序列中的重复结构，在有记忆信源上压缩比更高。连续情形下微分熵可以为负且依赖量纲，可操作的量是互信息与 KL 散度；正态分布在给定方差下最大化微分熵，熵功率不等式说明和的熵以高斯为最小。有损压缩的极限由率失真函数给出，它是给定失真约束下互信息的最小值，是凸的单调递减函数，在零失真处等于熵；高斯信源的率失真函数有闭式表达 $\frac{1}{2}\log \frac{{\sigma }^2}{D}$，这条曲线说明了为降低均方误差需要付出的信息率。

压缩关心的是把一个信源的信息压到多少比特。与之对称的问题是：经过一条有噪声的信道，最多能可靠地传输多少信息。这一问题的答案由信道容量给出，它是输入与输出之间互信息的最大值，可靠传输的可行性同样由典型性理论保证。下一节讨论信道容量与编码定理，并给出高斯信道、并行信道与多用户情形的具体结论。

练习题

第 1 题 概念推导

设信源取值于 $\{a,b,c\}$，概率分别为 $0.5$、$0.25$、$0.25$。构造一组码长使平均码长等于熵，并说明此时码长满足什么条件；再证明该码长组合满足 Kraft 不等式。

参考答案

构造：信源的熵为

$$H(X)=-0.5\log 0.5-2\times 0.25\log 0.25=0.5+1.0=1.5\text{ 比特}$$

取码长为 $a\to 1$、$b\to 2$、$c\to 2$，则平均码长为

$$\overline{L}=0.5\times 1+0.25\times 2+0.25\times 2=1.5\text{ 比特}=H(X)$$

此时 $\overline{L}=H(X)$，达到下界。

达到等号的条件：由下界证明中的 KL 散度为零的条件，需要 $p(x)=2^{-l(x)}$ 对所有 $x$ 成立。验证：$2^{-1}=0.5=p(a)$，$2^{-2}=0.25=p(b)=p(c)$，条件成立。这说明只有当所有概率都是 $2$ 的负整数次幂时，逐符号前缀码才能达到熵。

Kraft 不等式验证：

$$\sum _x{2}^{-l(x)}=2^{-1}+2^{-2}+2^{-2}=0.5+0.25+0.25=1$$

恰好等于 $1$，说明这组码长用满了全部码字配额，对应的前缀码是完整的二叉树（例如 $a\to 0$、$b\to 10$、$c\to 11$）。若把 $b$ 的码长设为 $3$，则 $\sum 2^{-l}=0.5+0.125+0.25=0.875<1$，仍满足不等式，但平均码长变为 $1.75$ 比特，冗余为 $0.25$ 比特。

第 2 题 计算推理

某文本文件包含 $5$ 个字符，出现频率如下表。求该信源的熵；用 Huffman 编码构造前缀码并给出平均码长与冗余；若改用固定长度编码（每个字符 $3$ 比特），说明两者的差距来源。

字符	A	B	C	D	E
频率	0.35	0.25	0.2	0.15	0.05

参考答案

熵：

$$H(X)=-(0.35\log 0.35+0.25\log 0.25+0.2\log 0.2+0.15\log 0.15+0.05\log 0.05)$$

逐项计算：$0.35{\log }_{2}0.35=-0.5301$，$0.25{\log }_{2}0.25=-0.5$，$0.2{\log }_{2}0.2=-0.4644$，$0.15{\log }_{2}0.15=-0.4105$，$0.05{\log }_{2}0.05=-0.2161$。求和取负得 $H(X)=2.1211$ 比特/符号。

Huffman 构造：合并最小的两个（E: 0.05 与 D: 0.15）得到 0.2；此时概率集合为 $\{0.35,0.25,0.2,0.2\}$，合并两个 0.2 得到 0.4；集合变为 $\{0.35,0.4,0.25\}$，合并 0.25 与 0.35 得到 0.6；最后合并 0.6 与 0.4 得到 1.0。

一种可行的码长分配（自顶向下）：A: 2，B: 2，C: 2，D: 3，E: 3。验证 Kraft：$3\times 2^{-2}+2\times 2^{-3}=1$，成立。

平均码长：

$$\overline{L}=0.35\times 2+0.25\times 2+0.2\times 2+0.15\times 3+0.05\times 3=1.6+0.45+0.15=2.2\text{ 比特}$$

冗余为 $2.2-2.1211=0.0789$ 比特/符号。

与固定长度编码的差距：固定长度编码每符号 $3$ 比特（$\lceil {\log }_{2}5\rceil =3$），比 Huffman 多 $0.8$ 比特。差距有两个来源：一是固定长度忽略了字符频率的差异，把出现频率相差七倍的字符编码为同样长度；二是 5 个字符需要 3 比特，其中 $2^3-5=3$ 个码字被浪费，Kraft 配额没有被用满。若把 $k$ 个字符作为一个块用固定长度编码，块内可容纳的码字数变为 $5^k$，浪费的相对比例下降，平均每符号的码长趋近 ${\log }_{2}5=2.3219$，但仍高于熵，因为固定长度无法利用频率差异。

第 3 题 代码验证

实现 Huffman 编码与算术编码，在一个偏斜分布上比较两者的平均码长；再用长序列验证算术编码的每符号码长收敛到熵，并说明 Huffman 编码在多符号块上如何缩小差距。

参考答案

import numpy as np

def huffman_lengths(probs):
    probs = list(probs)
    nodes = [(p, [i]) for i, p in enumerate(probs)]
    lengths = [0] * len(probs)
    while len(nodes) > 1:
        nodes.sort(key=lambda t: t[0])
        (p1, s1), (p2, s2) = nodes[0], nodes[1]
        for i in s1 + s2:
            lengths[i] += 1
        nodes = nodes[2:] + [(p1 + p2, s1 + s2)]
    return np.array(lengths)

def entropy(p):
    p = np.asarray(p, dtype=float)
    p = p[p > 0]
    return float(-np.sum(p * np.log2(p)))

def arithmetic_bits(seq, probs):
    low, high = 0.0, 1.0
    cum = np.concatenate([[0.0], np.cumsum(probs)])
    for s in seq:
        w = high - low
        high = low + w * cum[s + 1]
        low = low + w * cum[s]
    return -np.log2(high - low)

probs = np.array([0.8, 0.15, 0.05])
H = entropy(probs)
L = huffman_lengths(probs)
print(f"熵 = {H:.4f}，Huffman 平均码长 = {np.dot(probs, L):.4f}，冗余 = {np.dot(probs, L) - H:.4f}")

rng = np.random.default_rng(17)
for n in [10, 100, 1000, 10_000]:
    seq = rng.choice(len(probs), size=n, p=probs)
    print(f"n = {n:6d}：算术编码每符号 = {arithmetic_bits(seq, probs) / n:.4f} 比特（熵 = {H:.4f}）")

# Huffman 的块编码：把两个符号拼成一个新符号
joint = np.outer(probs, probs).flatten()
L2 = huffman_lengths(joint)
print(f"\n块长 2 的 Huffman 平均码长/符号 = {np.dot(joint, L2) / 2:.4f}")
joint4 = np.outer(np.outer(probs, probs).flatten(), np.outer(probs, probs).flatten()).flatten()
L4 = huffman_lengths(joint4)
print(f"块长 4 的 Huffman 平均码长/符号 = {np.dot(joint4, L4) / 4:.4f}")

输出显示三点。第一，单符号 Huffman 的冗余约 $0.1$ 到 $0.3$ 比特，来自概率不是 $2$ 的负整数次幂。第二，算术编码的每符号码长随序列增长单调收敛到熵，没有固定开销。第三，块长从 $1$ 增加到 $4$ 时 Huffman 的平均码长逐步下降并接近熵，验证了块编码可以缩小 $1$ 比特内开销的结论；代价是码表大小按指数增长（块长 $4$ 时符号表有 $3^4=81$ 项），这也是算术编码取代块 Huffman 的原因。

第 4 题 综合应用

某团队要在带宽受限的链路上传输传感器的时间序列数据，采样率为每秒 $1000$ 个样本，样本近似服从标准差为 $0.5$ 的高斯分布（均值为零）。他们希望重建的均方误差不超过 $0.01$。请计算所需的比特率；说明若允许误差增大到 $0.04$，比特率能降低多少；并讨论实际系统的压缩率通常低于理论上限的三个原因。

参考答案

所需比特率：由高斯信源的率失真函数，${\sigma }^2=0.25$，

$$R(D)=\frac{1}{2}{\log }_2\frac{{\sigma }^2}{D}=\frac{1}{2}{\log }_2\frac{0.25}{0.01}=\frac{1}{2}{\log }_{2}25\approx 2.322\text{ 比特/样本}$$

乘以采样率：$2.322\times 1000\approx 2322$ 比特/秒。

放宽误差的影响：$D=0.04$ 时

$$R=\frac{1}{2}{\log }_2\frac{0.25}{0.04}=\frac{1}{2}{\log }_{2}6.25\approx 1.322\text{ 比特/样本}$$

比特率降为约 $1322$ 比特/秒，相对下降约 $43\mathrm{\%}$。这一对比说明率失真曲线在低失真区非常陡：把误差从 $0.01$ 放宽到 $0.04$（四倍）只需付出约 $1$ 比特的代价，而在更低失真处同样的比特增量能换到的误差改善有限。

实际压缩率低于理论上限的三个原因：第一，率失真函数假设以很长的块编码并且能构造任意复杂的码本，实际编码器的块长与码本复杂度受限，存在编码冗余。第二，理论上限基于理想的失真度量与已知分布，实际数据的分布需要在线估计，估计误差会转化为额外的比特；时间序列如果存在样本间相关，理想做法是先做预测再对残差编码，如果没有利用相关性，比特率会明显偏高。第三，实际系统还要考虑抗噪与延迟：在不可靠链路上需要加入纠错冗余（下一节的信道编码），端到端延迟要求限制了块长。三条因素叠加，实际可达的压缩率通常只有理论上限的 $70\mathrm{\%}$ 到 $90\mathrm{\%}$，报告指标时应当同时给出理论下界与实际实现值，并说明差距的来源。

常见错误

错误 1 · 声称压缩率可以低于熵

原因：信源编码定理给出的下界是严格的，任何唯一可译码的平均码长都不小于熵。看到某个工具把文件压到比估计的熵更小，通常是熵的估计有误（把有记忆的数据当作无记忆处理，或分布估计偏差），而不是突破了极限。对有记忆信源，正确的下界是熵率而不是单符号熵，后者可能远大于前者。

解决：估计熵之前先检查符号之间是否存在依赖。做法是对比 $n$ 元条件熵随 $n$ 的变化，选择已经收敛的值作为熵率估计。报告压缩比时说明所用的信源模型，避免把模型误差当作超越极限。

错误 2 · 在短序列上使用算术编码而不考虑终止开销

原因：算术编码的码长等于序列的负对数概率，理论上没有固定开销，但实现上需要额外的比特来标记序列结束（终止符号或长度信息）。短序列上这部分开销占比很小；若把理论值直接与实际字节数比较，会误判实现有缺陷。

解决：把终止开销单独度量并报告。对短序列（长度小于几十个符号），逐符号的 Huffman 或直接发送原始数据可能更划算，选择方案时按实际长度评估。诊断方式是在多个序列长度上比较实际比特数减去自信息和这一差值是否稳定。

错误 3 · 把微分熵当作可比较的绝对量

原因：微分熵依赖坐标的单位，换量纲会引入常数偏移，且取值可以为负。直接把两个不同数据源的微分熵数值拿来比较，结论没有意义。

解决：比较时使用互信息、KL 散度或条件微分熵之差，这些量在换单位时相互抵消。报告微分熵时注明单位与坐标定义；在涉及连续信道的推导中，微分熵通常以之差的形式出现，这一点可以避免误用。

错误 4 · 用率失真函数当作实际系统的设计目标而忽略其假设

原因：率失真函数的下界在块长趋于无穷、码本可任意复杂、信源分布已知且平稳的假设下取得。实际系统受延迟、复杂度与平稳性限制，把理论下界当作设计目标会导致系统无法实现，也会误判现有实现的效率。

解决：把率失真函数作为参照基准而非目标。计算理论下界与实际实现的比值，用它评估改进空间；同时考虑延迟与复杂度约束下的实际可达区域（率失真复杂度函数的思路）。若信源非平稳，还需要按时间段分别估计率失真曲线，或用在线自适应方法跟踪分布变化。