信息论计算实战：从香农熵、互信息与信道容量到霍夫曼编码、汉明纠错与率失真理论的完整工程链路

信息论不是通信工程师的专利，它是所有"从噪声中提取信号、从冗余中压缩信息、从不确定性中做决策"系统的共同数学底座。本文沿着香农 1948 年的原始脉络，把信息论拆成可运行、可验证的工程零件：先建立熵与互信息这套信息度量的"语言"，再落地信源编码（霍夫曼）、信道容量（香农极限）、信道编码（汉明纠错）、率失真（有损压缩极限）四条主线，最后把每一块映射回 AI/深度学习——你会发现交叉熵损失、VAE 正则、信息瓶颈、量化蒸馏，全都是信息论原语的旧瓶装新酒。

一、信息度量：自信息、香农熵与 KL 散度

信息的单位来自"惊讶程度"。一个必然会发生的事件不携带信息；一个概率极低的事件一旦发生，携带大量信息。香农把单点自信息定义为 I(x) = -log2 P(x)（单位 bit），把整条分布的不确定性总量定义为熵 H(X) = -Σ P(x) log2 P(x)。熵是衡量随机性的标尺：公平硬币 H=1 bit，确定事件 H=0，而越均匀的分布熵越高。

互信息 I(X;Y) 衡量两个变量共享的信息量，等价于"知道 Y 后 X 不确定性减少了多少"。一个极其重要的性质是 I(X;Y) = H(X) - H(X|Y)，且互信息非负、I(X;Y) ≤ min(H(X), H(Y))。KL 散度（相对熵）D_KL(P‖Q) 衡量两个分布的"距离"（不对称），它是信息论与机器学习之间最频繁的桥。下面用纯 Python 把这套度量全部实现并验证。

import math

def log2(x):
    return math.log2(x) if x > 0 else 0.0

def entropy(p):
    """香农熵 H(X) = -Σ p_i log2 p_i"""
    return -sum(log2(pi) * pi for pi in p)

def joint_entropy(pxy):
    """pxy: dict {(x,y): prob}"""
    return -sum(log2(v) * v for v in pxy.values())

def mutual_information(pxy):
    """I(X;Y) = ΣΣ p(x,y) log2 p(x,y)/(p(x)p(y))"""
    px = {}; py = {}
    for (x, y), v in pxy.items():
        px[x] = px.get(x, 0) + v
        py[y] = py.get(y, 0) + v
    mi = 0.0
    for (x, y), v in pxy.items():
        mi += v * log2(v / (px[x] * py[y]))
    return mi

def kl_divergence(p, q):
    """D_KL(P||Q) = Σ p_i log2(p_i/q_i)  (base-2 → bits)"""
    return sum(pi * (log2(pi) - log2(qi)) for pi, qi in zip(p, q) if pi > 0)

# --- 验证 ---
fair = [0.5, 0.5]
print("fair coin H =", round(entropy(fair), 3))   # 1.0

# 独立随机变量 → I=0
pxy_ind = {(0,0):0.25,(0,1):0.25,(1,0):0.25,(1,1):0.25}
print("independent I(X;Y) =", round(mutual_information(pxy_ind), 3))  # 0.0

# 相关变量
pxy_corr = {(0,0):0.4,(0,1):0.1,(1,0):0.1,(1,1):0.4}
mi = mutual_information(pxy_corr)
HX = entropy([0.5,0.5]); HY = entropy([0.5,0.5])
print("correlated I(X;Y) =", round(mi, 3))        # >0 (≈0.279)
print("I <= min(HX,HY)?", mi <= min(HX,HY)+1e-9)  # True

# KL >=0 且不对称
p = [0.5,0.3,0.2]; q = [1/3,1/3,1/3]
print("KL(P||Q) =", round(kl_divergence(p,q),3))  # >0
print("KL(Q||P) =", round(kl_divergence(q,p),3))  # 与上式不同

运行结果完全符合理论预期：公平硬币熵恰为 1.0 bit；独立变量互信息严格为 0；相关变量互信息 ≈0.279 且被 min(H(X),H(Y))=1 牢牢上界约束；KL 散度非负且 D_KL(P‖Q)≠D_KL(Q‖P)，这正是它在变分推断里"前向/反向"两种用法行为截然不同的根源。

二、信源编码：霍夫曼最优前缀码

香农源编码定理告诉我们，无损压缩的平均码长 L 必然满足 H(X) ≤ L < H(X)+1。霍夫曼算法给出一个贪心构造的最优前缀码：每次合并两个概率最小的节点，给左支标 0、右支标 1，直到合成一棵树，从根到叶的路径就是该符号的码字。它保证平均码长最小，且没有任何码字是别的码字的前缀（前缀码），因而解码无歧义。

import heapq, math

def huffman(freqs):
    """freqs: dict symbol->count. 返回 code dict {symbol: bits}"""
    heap = [[w, [sym, ""]] for sym, w in freqs.items()]
    heapq.heapify(heap)
    while len(heap) > 1:
        lo = heapq.heappop(heap); hi = heapq.heappop(heap)
        for pair in lo[1:]: pair[1] = "0" + pair[1]
        for pair in hi[1:]: pair[1] = "1" + pair[1]
        heapq.heappush(heap, [lo[0]+hi[0]] + lo[1:] + hi[1:])
    return {sym: cd for sym, cd in heap[0][1:]}

def encode(text, code):
    return "".join(code[ch] for ch in text)

def decode(bits, code):
    rev = {v:k for k,v in code.items()}
    out=""; cur=""
    for b in bits:
        cur += b
        if cur in rev:
            out += rev[cur]; cur=""
    return out

freqs = {"a":5,"b":9,"c":12,"d":13,"e":16,"f":45}
code = huffman(freqs)
print("codes:", code)
text = "abfacfebfacdeaf"
bits = encode(text, code)
dec = decode(bits, code)
print("roundtrip ok:", dec == text)   # True

total = sum(freqs.values())
H = -sum((w/total)*math.log2(w/total) for w in freqs.values())
avg_len = sum(len(code[s])*w for s,w in freqs.items())/total
print("entropy H =", round(H,3), "avg code len =", round(avg_len,3))
print("H <= avg_len < H+1 ?", H-1e-9 <= avg_len < H+1)   # 香农源编码定理

高频符号 f 拿到最短码字（1 bit），低频符号拿到更长码字，往返编解码完全一致，且平均码长恰好落在 [H, H+1) 区间内——教科书式的香农定理落地。

三、信道与容量：从二元对称信道到香农极限

信道容量 C 是信道每单位时间能可靠传输的最大信息率（bit/符号或 bit/s）。最经典的玩具模型是二元对称信道（BSC）：每位以概率 p 翻转为相反值，其容量为 C = 1 - H2(p)，H2 是二元熵。当 p=0 或 p=1 时信道完美或可逆，容量回到 1；当 p=0.5 信道纯噪声，容量为 0——无论发什么都无法区分。

真实物理信道（加性高斯白噪声，AWGN）遵循香农-哈特莱公式 C = B·log2(1+SNR)：带宽 B 与信噪比 SNR 共同决定极限。它给出了"在任意误码率下可通信"的理论天花板，是所有调制编码、5G/光纤系统的终极裁判。

import math

def binary_symmetric_capacity(p):
    """二元对称信道容量 C = 1 - H2(p)"""
    if p == 0 or p == 1: return 1.0
    return 1.0 + p*math.log2(p) + (1-p)*math.log2(1-p)

def shannon_hartley(B, snr_linear):
    """AWGN 信道容量 C = B log2(1+SNR)"""
    return B*math.log2(1+snr_linear)

print("BSC p=0.1 C =", round(binary_symmetric_capacity(0.1),3))  # ≈0.531
print("BSC p=0.5 C =", round(binary_symmetric_capacity(0.5),3))  # 0.0
print("Shannon 1MHz, SNR=100x C =",
      round(shannon_hartley(1e6,100)/1e6,3), "Mbps")             # ≈6.658
print("C(B,2SNR) > C(B,SNR)?",
      shannon_hartley(1e6,200) > shannon_hartley(1e6,100))        # True

p=0.1 时每符号还能可靠传 0.531 bit；p=0.5 时彻底归零；1 MHz 带宽在 100 倍信噪比下容量约 6.658 Mbps，且容量随 SNR 严格单调——这就是"带宽换 SNR、SNR 换速率"的定量依据。

四、信道编码：汉明码的单比特纠错

容量定义了上限，但要让收发双方在噪声里真正"零差错"通信，必须主动插入冗余——这就是信道编码。汉明 (7,4) 码用 3 个校验位保护 4 个数据位，构成一个能检测并纠正单个比特错误的最小完备码。三个校验位按奇偶方程组生成，接收端重新计算校验和得到"症候群（syndrome）"，症候群的值直接指定位号，翻转即修复。

def hamming74_encode(d):
    """d: 4 bits [d1..d4]. 码字布局 [p1,p2,d1,p3,d2,d3,d4]"""
    d1,d2,d3,d4 = d
    p1 = d1 ^ d2 ^ d4
    p2 = d1 ^ d3 ^ d4
    p3 = d2 ^ d3 ^ d4
    return [p1,p2,d1,p3,d2,d3,d4]

def hamming74_decode(r):
    """r: 7-bit 接收字。纠正单比特错误，返回 (corrected, data, syndrome)"""
    p1,p2,d1,p3,d2,d3,d4 = r
    s1 = p1 ^ d1 ^ d2 ^ d4
    s2 = p2 ^ d1 ^ d3 ^ d4
    s3 = p3 ^ d2 ^ d3 ^ d4
    s = s1 + (s2<<1) + (s3<<2)   # 1..7 指定位号
    if s:
        r[s-1] ^= 1
    p1,p2,d1,p3,d2,d3,d4 = r
    return r, [d1,d2,d3,d4], s

data = [1,0,1,1]
code = hamming74_encode(data)
print("encoded:", code)
recv = code[:]; recv[3] ^= 1          # 注入单比特错误（位置 4 = p3）
corr, dec, syn = hamming74_decode(recv)
print("syndrome:", syn, "decoded:", dec, "match:", dec == data)  # syn=4, True

# 双错误：汉明码无法纠正（会误纠成别的字）
recv2 = code[:]; recv2[0]^=1; recv2[5]^=1
_, dec2, _ = hamming74_decode(recv2)
print("double-error decoded == data?", dec2 == data)  # False：仅能纠正 1 位

综合症精确定位并翻转了被篡改的第 4 位，数据完美还原；而故意注入的双比特错误被正确"拒识"为不可纠正——这直观展示了信道编码的纠错能力上限，也解释了为什么现代存储/通信要用更强的 LDPC 或 BCH 码来处理多比特突发错误。

五、率失真理论：有损压缩的极限

并非所有信息都值得无损保留。率失真理论回答一个反直觉的问题：如果要允许最多 D 的平均失真，最少需要多少 bit/symbol？对高斯信源，率失真函数闭式给出 R(D) = ½ log2(σ²/D)（0）。它随 D 单调下降，在 D=σ²（失真等于方差，等于直接发均值）时归零——这正是 JPEG/MPEG/语音编码"质量换码率"的数学根基。与之同源的 KL 散度在同方差高斯下也有闭式 D_KL = (μ1-μ2)²/(2σ²)，非负性一眼可证。

import math

def gaussian_rate_distortion(sigma2, D):
    """高斯信源率失真 R(D) = 1/2 log2(sigma^2 / D), 0 < D <= sigma^2"""
    if D >= sigma2: return 0.0
    return 0.5*math.log2(sigma2/D)

sig2 = 1.0
print("R(0.5) =", round(gaussian_rate_distortion(sig2,0.5),3))   # 0.5
print("R(0.1) =", round(gaussian_rate_distortion(sig2,0.1),3))   # ≈1.661
print("R at D=sigma^2 ->", gaussian_rate_distortion(sig2, sig2)) # 0.0
print("monotonic decreasing?",
      gaussian_rate_distortion(sig2,0.1) > gaussian_rate_distortion(sig2,0.5))  # True

def kl_gauss(m1, m2, s2):
    return (m1-m2)**2/(2*s2)
print("KL(N(0,1)||N(2,1)) =", round(kl_gauss(0,2,1),3))  # 2.0
print("KL self =", kl_gauss(0,0,1))                       # 0.0：非负性