第 12 章 信道编码基础 / Channel Coding

12.1 为什么需要信道编码

实际信道中，噪声、衰落和干扰会导致接收比特发生错误。信道编码 (Channel Coding) 的核心思想：在发送端人为地引入冗余 (redundancy)，使接收端能够检测 (detect) 甚至纠正 (correct) 传输错误。

衡量编码效果的关键指标：

• 编码增益 (Coding Gain)：在相同误比特率 (BER, Bit Error Rate) 下，编码系统比未编码系统所节省的 $E_b/N_0$（dB）。
• 码率 (Code Rate)：$R_c = k/n$，其中 $k$ 为信息比特数，$n$ 为编码后比特数。$R_c < 1$ 意味着引入了 $n - k$ 位冗余。

$$\text{编码增益 (dB)} = \left(\frac{E_b}{N_0}\right){\text{未编码}} - \left(\frac{E_b}{N_0}\right){\text{编码}} \quad \text{(在相同 BER 下)}$$

根据功能分类：

flowchart LR
    A["信息比特 k"] --> B["信道编码器
Encoder"]
    B --> C["编码比特 n"]
    C --> D["调制 & 信道"]
    D --> E["接收信号"]
    E --> F["信道译码器
Decoder"]
    F --> G["估计比特 k̂"]
    style A fill:#1a1a2e,color:#fff
    style B fill:#16213e,color:#fff
    style C fill:#0f3460,color:#fff
    style D fill:#533483,color:#fff
    style E fill:#0f3460,color:#fff
    style F fill:#16213e,color:#fff
    style G fill:#1a1a2e,color:#fff

Shannon 信道编码定理指出：只要码率 $R_c$ 小于信道容量 $C$，就存在一种编码方案可以使误码率任意小：

$$C = B \log_2\left(1 + \frac{S}{N}\right) \quad \text{[bit/s]}$$

信道编码的全部工程探索，本质上就是在逼近 Shannon 极限的路上不断前进。

12.2 线性分组码 (Linear Block Codes)

12.2.1 基本定义

一个 $(n, k)$ 线性分组码将 $k$ 位信息映射为 $n$ 位码字 ($n > k$)，所有码字构成 $\mathbb{F}_2^n$ 的一个 $k$ 维线性子空间。

生成矩阵 (Generator Matrix) $\mathbf{G}$：$k \times n$ 矩阵，编码操作为：

$$\mathbf{c} = \mathbf{m} \cdot \mathbf{G}$$

其中 $\mathbf{m} \in \mathbb{F}_2^k$ 为信息向量，$\mathbf{c} \in \mathbb{F}_2^n$ 为码字。

系统码 (Systematic Code)：生成矩阵具有 $\mathbf{G} = [\mathbf{I}_k \mid \mathbf{P}]$ 的形式，码字前 $k$ 位就是原始信息，后 $n-k$ 位为校验位。

校验矩阵 (Parity-Check Matrix) $\mathbf{H}$：$(n-k) \times n$ 矩阵，满足：

$$\mathbf{G} \cdot \mathbf{H}^T = \mathbf{0}_{k \times (n-k)}$$

对接收向量 $\mathbf{r} = \mathbf{c} + \mathbf{e}$（$\mathbf{e}$ 为错误图样），校验矩阵可用于检错：

$$\mathbf{r} \cdot \mathbf{H}^T = (\mathbf{c} + \mathbf{e}) \cdot \mathbf{H}^T = \mathbf{e} \cdot \mathbf{H}^T = \mathbf{s}$$

$\mathbf{s}$ 称为伴随式 (Syndrome)。若 $\mathbf{s} = \mathbf{0}$，认为无错误；否则根据 $\mathbf{s}$ 纠错。

12.2.2 Hamming 码 (7, 4)

Hamming (7, 4) 码是最经典的线性分组码示例：$k = 4$ 位信息，$n = 7$ 位码字，$r = 3$ 位校验，最小距离 $d_{\min} = 3$，可纠正 1 位错误。

生成矩阵（系统形式）：

$$\mathbf{G} = \begin{bmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{bmatrix}$$

校验矩阵：

$$\mathbf{H} = \begin{bmatrix} 1 & 1 & 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 & 1 \end{bmatrix}$$

12.2.3 伴随式译码 (Syndrome Decoding)

flowchart TD
    R["接收向量 r"] --> S["计算伴随式
s = r·Hᵀ"]
    S --> Z{"s = 0?"}
    Z -->|是| OK["无错误
输出 r"]
    Z -->|否| L["查表：s → 错误图样 e"]
    L --> C["纠正：
ĉ = r + e"]
    C --> OUT["输出 ĉ"]
    style R fill:#1a1a2e,color:#fff
    style S fill:#16213e,color:#fff
    style Z fill:#533483,color:#fff
    style OK fill:#1b4332,color:#fff
    style L fill:#0f3460,color:#fff
    style C fill:#16213e,color:#fff
    style OUT fill:#1a1a2e,color:#fff

伴随式译码伪代码：

1
2
3
4
5
6
7
8

function SYNDROME_DECODE(r, H, syndrome_table):
    s = r × Hᵀ                    // 计算伴随式
    if s == 0:
        return r                   // 无错误
    e = syndrome_table.lookup(s)   // 查表得到最可能错误图样
    ĉ = r ⊕ e                     // 异或纠正
    return ĉ
end function

对于 Hamming (7, 4) 码，伴随式恰好对应错误位置的二进制表示，译码极其简洁。

12.2.4 纠错能力

最小汉明距离 (Minimum Hamming Distance) $d_{\min}$ 决定了码的纠检错能力：

$$\text{检测 } t_d \text{ 个错误：} \quad d_{\min} \geq t_d + 1$$ $$\text{纠正 } t_c \text{ 个错误：} \quad d_{\min} \geq 2t_c + 1$$

12.3 循环码 (Cyclic Codes)

循环码是线性分组码的重要子类，具有循环移位不变性：若 $(c_0, c_1, \ldots, c_{n-1})$ 是码字，则 $(c_{n-1}, c_0, \ldots, c_{n-2})$ 也是码字。

多项式表示

码字 $\mathbf{c} = (c_0, c_1, \ldots, c_{n-1})$ 用多项式表示为：

$$c(x) = c_0 + c_1 x + c_2 x^2 + \cdots + c_{n-1} x^{n-1}$$

循环码由生成多项式 (Generator Polynomial) $g(x)$ 唯一确定，$g(x)$ 是 $x^n + 1$ 的因式。

编码过程（系统码形式）：

1. 计算 $x^{n-k} \cdot m(x)$
2. 求 $x^{n-k} \cdot m(x) \bmod g(x) = r(x)$（余数）
3. 码字 $c(x) = x^{n-k} \cdot m(x) + r(x)$

1
2
3
4
5
6
7

function CYCLIC_ENCODE(m_bits, g_poly):
    // m_bits: k位信息, g_poly: 生成多项式系数
    shifted = m_bits << (n - k)        // 左移 n-k 位
    remainder = POLY_DIV(shifted, g_poly)  // 多项式取余
    codeword = shifted | remainder      // 拼接
    return codeword
end function

CRC (Cyclic Redundancy Check) 是循环码在检错领域的典型应用：CRC-32 广泛用于以太网帧校验。

12.4 卷积码 (Convolutional Codes)

12.4.1 编码器结构

与分组码不同，卷积码的编码输出不仅取决于当前输入，还与之前的输入有关——具有记忆性。一个 $(n, k, K)$ 卷积码的参数：

• $k$：每次输入的比特数
• $n$：每次输出的比特数
• $K$：约束长度 (Constraint Length)，编码器记忆级数
• 码率：$R_c = k/n$

最简单的 $(2, 1, 3)$ 卷积码编码器示例：2 级移位寄存器，两个生成多项式 $g_1 = (1,1,1)$，$g_2 = (1,0,1)$。

$$c_t^{(1)} = u_t \oplus u_{t-1} \oplus u_{t-2}$$ $$c_t^{(2)} = u_t \oplus u_{t-2}$$

12.4.2 状态图与网格图

编码器的状态由寄存器内容决定。$(2, 1, 3)$ 码有 $2^{K-1} = 4$ 个状态 ($S_0$ ~ $S_3$)。

stateDiagram-v2
    S0 --> S0: 输入0/输出00
    S0 --> S2: 输入1/输出11
    S1 --> S0: 输入0/输出10
    S1 --> S2: 输入1/输出01
    S2 --> S1: 输入0/输出01
    S2 --> S3: 输入1/输出10
    S3 --> S1: 输入0/输出11
    S3 --> S3: 输入1/输出00

将状态图按时间展开即得到网格图 (Trellis Diagram)，这是 Viterbi 译码的基础。

12.4.3 Viterbi 算法

Viterbi 算法是一种最大似然 (ML, Maximum Likelihood) 序列估计算法，基于动态规划在网格图上寻找与接收序列汉明距离最小的路径。

核心思想：在每个时刻，对每个状态只保留幸存路径 (Survivor Path)——到达该状态中度量最优的路径。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

function VITERBI(received_seq, trellis):
    // 初始化
    for each state s:
        path_metric[s] = ∞
    path_metric[S0] = 0
    
    // 递推
    for t = 1 to T:
        for each state s:
            for each incoming transition (s_prev → s):
                branch = BRANCH_METRIC(received_seq[t], transition_output)
                candidate = path_metric[s_prev] + branch
                if candidate < new_metric[s]:
                    new_metric[s] = candidate
                    survivor[t][s] = s_prev
        path_metric = new_metric
    
    // 回溯
    s_best = argmin_s(path_metric[s])
    return TRACEBACK(survivor, s_best, T)
end function

Viterbi 算法复杂度为 $O(n \cdot 2^{K-1} \cdot T)$，约束长度 $K$ 通常取 7~9，在工程中广泛应用。

12.5 工程应用

12.5.1 Reed-Solomon 码

RS 码是一种基于有限域 $\mathbb{F}_{2^m}$ 的非二进制 BCH 码，以符号 (symbol) 为单位进行纠错。

• 一个 RS$(n, k)$ 码：$n$ 个符号中有 $k$ 个信息符号
• 纠错能力：$t = (n - k) / 2$ 个符号错误
• 关键优势：对付突发错误 (Burst Error) 极其有效

典型应用：

12.5.2 Turbo 码

Turbo 码由 Berrou 等人于 1993 年提出，是首个逼近 Shannon 极限（距极限仅 0.5 dB）的实用编码方案。

核心结构： 两个递归系统卷积码 (RSC, Recursive Systematic Convolutional) 编码器通过交织器 (Interleaver) 并行级联。

flowchart LR
    U["信息序列 u"] --> ENC1["RSC 编码器 1"]
    U --> INT["交织器
Interleaver"]
    INT --> ENC2["RSC 编码器 2"]
    U --> MUX["复用 & 打孔
MUX & Puncture"]
    ENC1 --> MUX
    ENC2 --> MUX
    MUX --> TX["发送"]
    style U fill:#1a1a2e,color:#fff
    style ENC1 fill:#16213e,color:#fff
    style INT fill:#533483,color:#fff
    style ENC2 fill:#16213e,color:#fff
    style MUX fill:#0f3460,color:#fff
    style TX fill:#1a1a2e,color:#fff

迭代译码 (Iterative Decoding) 是 Turbo 码的灵魂：两个 SISO（Soft-Input Soft-Output）译码器交替工作，相互传递外信息 (Extrinsic Information)，多次迭代后收敛。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

function TURBO_DECODE(received, max_iter):
    L_ext = 0                          // 初始化外信息
    for iter = 1 to max_iter:
        // 译码器 1
        L1 = SISO_DECODER(received_sys, received_p1, L_ext)
        L_ext_new = L1 - L_ext - L_channel
        
        // 交织后送入译码器 2
        L_ext_int = INTERLEAVE(L_ext_new)
        L2 = SISO_DECODER(received_sys_int, received_p2, L_ext_int)
        L_ext = DEINTERLEAVE(L2 - L_ext_int - L_channel_int)
        
        // 检查收敛（可选）
        if CONVERGED(L_ext):
            break
    end for
    return HARD_DECISION(L2)
end function

LTE 中的 Turbo 码参数：

• 码率通过打孔 (Puncturing) 支持 $R_c \in {1/3, 1/2, 2/3, 3/4, \ldots}$
• 交织器采用 QPP (Quadratic Permutation Polynomial) 多项式
• 最多 8 次迭代
• 用于数据信道 (PDSCH/PUSCH)，控制信道使用 Tail-Biting 卷积码

12.5.3 5G NR：LDPC 码与 Polar 码

5G NR 标准中，Turbo 码被取代：

• 数据信道 (eMBB)：LDPC 码 (Low-Density Parity-Check Code)——更灵活，支持更高吞吐量
• 控制信道：Polar 码——首个被理论证明达到信道容量的码

12.6 小结与对比

各类编码对比

编码方案演进路线

1
2
3
4

Hamming (1950) → BCH/RS (1960) → 卷积码+Viterbi (1967)
    → Turbo (1993, +0.5dB to Shannon)
    → LDPC (重新发现, WiFi 6/5G NR)
    → Polar (2009, 理论可达 Shannon, 5G NR)

关键术语回顾

• 编码增益 (Coding Gain)：编码带来的 SNR 节省
• 最小距离 $d_{\min}$：决定纠检错能力
• 伴随式 (Syndrome)：用于线性码的检错定位
• Viterbi 算法：卷积码的 ML 译码
• 迭代译码 (Iterative Decoding)：Turbo/LDPC 码的核心
• 交织 (Interleaving)：将突发错误打散为随机错误

思考题

1. 一个 $(n, k) = (15, 11)$ 的 Hamming 码，其校验位有多少位？最小汉明距离是多少？能纠正几位错误？
2. 如果将 Hamming (7, 4) 码的校验矩阵 $\mathbf{H}$ 增加一行全 1 向量，得到的是什么码？其 $d_{\min}$ 和纠错能力如何变化？
3. 卷积码与分组码的本质区别是什么？为什么说卷积码具有"记忆性"？
4. Viterbi 算法中，如果路径度量采用欧氏距离而非汉明距离，需要对接收信号做什么前提假设？
5. Turbo 码的迭代译码为什么能大幅提升性能？“外信息"在迭代中扮演了什么角色？
6. 为什么 RS 码对突发错误特别有效？如果信道既有随机错误又有突发错误，应如何组合使用编码方案？
7. 5G NR 为什么选择 LDPC 码替代 Turbo 码作为数据信道编码？从吞吐量和灵活性的角度分析。
8. 如果要在深空通信（极低 SNR、长延迟、不允许重传）中选择一种编码方案，你会如何设计级联编码系统？