1. 引言：兩個看似違背直覺的「資訊復活」工程奇蹟

在現代數位文明的底層，有兩個每天都在發生、卻在直覺上近乎魔法的工程奇蹟：

奇蹟一：跨越240億公里的航海家1號與2號（Voyager 1 & 2）深空通訊

1977年發射的航海家1號與2號（Voyager 1 & 2）先後飛掠木星、土星、天王星與海王星，如今已飛出太陽圈進入距離地球超過240億公里的星際空間。 令人震撼的物理事實是：航海家號上的無線電發射機功率僅有$23\text{ W}$（瓦特）——還不如家用冰箱裡的一顆小燈泡。當這束微弱的電磁波跨越數十億公里的深空到達地球上NASA深空網路（DSN）的70公尺口徑巨型拋物面天線時，接收到的訊號功率已衰減至驚人的$10^{-16}\text{ W}$（$0.1\text{ 阿瓦}$）以下！

這一功率完全淹沒在宇宙背景輻射與接收機內部電子熱運動產生的熱雜訊（Thermal Noise）海洋之中。如果直接發送未編碼的原始像素位元（$0$ 和 $1$），成千上萬的位元會在途中隨機翻轉（$0 \leftrightarrow 1$），傳回地球的影像只會是一片雪花雜訊。然而，航海家號卻傳回了木星大紅斑、土星光環與海王星深邃藍大氣的零誤差高解析度彩色影像。

奇蹟二：被咖啡漬污染或被Logo遮擋30%面積的 QR Code

另一個奇蹟發生在你的手機鏡頭前。無論是餐廳桌角被咖啡漬染黑了一塊的 QR Code，還是中心高達30%的黑白模組被企業品牌Logo直接覆蓋的 QR Code，當你用手機相機對準它的瞬間，不到$10\text{ 毫秒}$，手機就能以零位元誤差（Zero Bit Errors）完美還原出完整的網址或支付憑證。

  flowchart TD
    subgraph Voyager["深空遙測通訊（航海家1號與2號）"]
        V1["行星影像原始資料 k 位元"] --> V2["串接編碼（外碼RS碼 + 內碼摺積碼/LDPC碼）"]
        V2 --> V3["23瓦發射 → 跨越數十億公里（接收功率 10⁻¹⁶ W）"]
        V3 --> V4["加性高斯白雜訊（AWGN）導致大量位元翻轉"]
        V4 --> V5["軟判決維特比/置信傳播 + RS代數解碼"]
        V5 --> V6["零誤差還原高解析度行星彩色影像"]
    end
    subgraph QR["日常 QR Code 高速掃描"]
        Q1["網址或支付資料 k 位元組"] --> Q2["GF(2⁸) 里德-所羅門編碼（n 位元組）"]
        Q2 --> Q3["咖啡污漬或企業Logo遮擋損毀30%面積"]
        Q3 --> Q4["伴隨式計算 + Berlekamp-Massey / 歐幾里得演算法"]
        Q4 --> Q5["錢氏搜尋定位錯誤 + Forney公式計算差值（10毫秒）"]
        Q5 --> Q6["100% 精確重構原始位元組資料"]
    end

為什麼淹沒在熱雜訊中的星際電波和缺失了近三分之一面積的條碼，能夠在不需要重傳的情況下100%精確復原？答案正是克勞德·夏農（Claude Shannon）的資訊理論與錯誤更正碼（Error-Correcting Codes, ECC）的數學科學。

2. 克勞德·夏農的1948年革命與「有噪通道編碼定理」

2.1 樸素重複碼（Repetition Code）的困境

2.2 夏農第二定理與夏農極限（Shannon Limit $-1.59\,\text{dB}$）

1948年，克勞德·夏農在《通訊的數學理論》（A Mathematical Theory of Communication）中證明了震撼世界的有噪通道編碼定理（Noisy-Channel Coding Theorem）：

【定理：夏農有噪通道編碼定理】 每一個無記憶有噪通道都存在一個由其雜訊統計特性唯一決定的正常數——通道容量（Channel Capacity） $C$：

• 對於翻轉機率為 $p$ 的二元對稱通道（BSC），最大化互資訊 $I(X;Y) = H(Y) - H(Y\mid X)$ 可得： $$C_{\text{BSC}}(p) = 1 - H_2(p) = 1 + p\log_2 p + (1-p)\log_2(1-p) \quad [\text{bits / channel use}]$$
• 對於頻寬為 $B$、訊號功率為 $S$、高斯白雜訊功率為 $N = N_0 B$ 的加性高斯白雜訊（AWGN）通道，夏農-哈特利定理給出： $$C_{\text{AWGN}} = B \log_2\!\left(1 + \frac{S}{N}\right) = B \log_2\!\left(1 + \frac{S}{N_0 B}\right) \quad [\text{bits / s}]$$

只要資訊傳輸速率嚴格小於通道容量（$R < C$），無論 $R$ 多麼接近 $C$，當碼長 $n \to \infty$ 時，必定存在速率為 $R$ 的區塊碼使得解碼錯誤機率任意接近於零（$P_e \to 0$）！

3. 理查·漢明的1950年幾何突破：漢明距離與 $[7, 4, 3]$ 完美碼

3.1 超立方體 $\mathbb{F}_2^n$ 上的漢明距離與球堆積界（Sphere-Packing Bound）

設編碼集合 $\mathcal{C} \subset \mathbb{F}_q^n$ 的最小漢明距離為 $d_{\min} = \min_{\mathbf{u} \neq \mathbf{v}} d_H(\mathbf{u}, \mathbf{v})$。利用三角不等式與以各碼字為中心、半徑為 $t$ 的不相交漢明球（Disjoint Hamming Spheres），可以直接證明：

1. 偵錯能力：最多可偵測 $d_{\min} - 1$ 個位元錯誤；
2. 抹除更正能力（Erasure Correction，已知損壞位置）：最多可恢復 $e = d_{\min} - 1$ 個抹除符號；
3. 隨機更正能力（Error Correction，未知損壞位置）：最多可更正 $t = \lfloor(d_{\min} - 1)/2\rfloor$ 個任意位置的錯誤。 當 $t$ 個未知位置錯誤與 $e$ 個已知位置抹除同時發生時，充要條件及漢明球堆積界（Hamming Sphere-Packing Bound）為： $$\mathbf{d_{\min} \ge 2t + e + 1}, \qquad |\mathcal{C}| \cdot \sum_{i=0}^{t} \binom{n}{i} (q-1)^i \le q^n$$

3.2 漢明 $(7,4)$ 碼的生成矩陣 $\mathbf{G}$、同位元檢查矩陣 $\mathbf{H}$ 與伴隨式解碼

若第 $j$ 位發生單位元翻轉，則 $\mathbf{s} = \mathbf{H}\mathbf{e}_j^T$ 恰好等於 $\mathbf{H}$ 的第 $j$ 行——伴隨式 $\mathbf{s}$ 的二進位數值直接輸出了出錯位元的座標索引 $(1 \dots 7)$！這一機制至今仍在所有伺服器級 ECC 記憶體（SECDED DRAM）中以奈秒級硬體電路即時運行。

4. 里德與所羅門的1960年傑作：伽羅瓦體 $\mathbb{F}_{2^m}$ 上的里德-所羅門（RS）碼

4.1 伽羅瓦體 $\text{GF}(2^8)$ 與抗突發錯誤（Burst Errors）的秘密

漢明碼只能更正零星的單位元翻轉，而光碟刮痕、QR Code 污漬或深空通訊衰落往往會造成連續數十位元同時損毀的突發錯誤（Burst Errors）。 1960年，歐文·里德（Irving Reed）與古斯塔夫·所羅門（Gustave Solomon）提出了在伽羅瓦體（有限體） $\mathbb{F}_{2^m}$ 上構造的里德-所羅門碼（Reed-Solomon Codes）。

在 $\text{GF}(2^8)$ 中，每 $8$ 個連續位元（1位元組）被打包為一個體符號（Symbol）：加減法就是逐位元互斥或（XOR），乘除法則透過本原元 $\alpha$ 的冪次指數加減（模255）完成。即使一個位元組內部的8個位元全部被咖啡漬毀壞，在 $\text{GF}(2^8)$ 看來也僅僅是1個符號發生了錯誤！

4.2 多項式插值唯一性與達到 Singleton 界的 MDS 性質

在 $\mathbb{F}_q$ 中選取 $n$ 個互不相同的求值點 $(\alpha_1, \dots, \alpha_n)$，發送求值向量 $\mathbf{c} = \bigl(P(\alpha_1), P(\alpha_2), \dots, P(\alpha_n)\bigr)$。

根據有限體上的代數學基本定理：

• 次數 $< k$ 的非零多項式最多只有 $k-1$ 個根。因此，任意兩個不同的訊息多項式 $P(x) \neq Q(x)$ 最多只能在 $k-1$ 個求值點上相等，在其餘至少 $n - (k-1) = n - k + 1$ 個點上必然不同！
• 於是，任何 $[n, k]$ 里德-所羅門碼都以嚴格等號達到理論上限 Singleton 界（最大距離可分碼，MDS Code）： $$\mathbf{d_{\min} = n - k + 1 \implies 2t + e \le n - k}$$

這意味著：增加 $n-k$ 個冗餘同位元組，就能完美恢復任意 $e = n - k$ 個已知位置的抹除（用於 RAID-6 雙碟容錯與雲端儲存抹除編碼），或者完美更正任意 $t = \lfloor(n-k)/2\rfloor$ 個未知位置的位元組錯誤（用於 QR Code 的 L/M/Q/H 四級糾錯，H級允許高達30%面積損毀，以及航海家號 $[255, 223]$ 外碼）！在循環碼實現中，利用生成多項式 $g(x) = \prod_{i=1}^{2t}(x - \alpha^i)$ 編碼，接收端計算伴隨式 $S_j = y(\alpha^j)$，透過 Berlekamp-Massey 演算法或擴展歐幾里得演算法求解關鍵方程 $\Lambda(x)S(x) \equiv \Omega(x) \pmod{x^{2t}}$ 得到錯誤位置多項式 $\Lambda(x) = \prod_{l=1}^\nu (1 - X_l x)$，再經由錢氏搜尋（Chien Search）與 Forney 公式即可在幾毫秒內精準算出所有錯誤位元組的位置與數值。

5. 逼近夏農極限：LDPC碼（1962）、Turbo碼（1993）與極化碼 Polar Codes（2009）

為了跨越硬判決代數解碼與夏農極限之間的最後 $3\,\text{dB}$ 鴻溝，現代通訊迎來了兩大終極武器：

1. 羅伯特·加拉格爾（Robert Gallager, 1962）的低密度同位元檢查碼（LDPC Codes）：採用極度稀疏的檢查矩陣 $\mathbf{H}$ 構造二分坦納圖（Tanner Graph），利用接收訊號的連續軟判決對數似然比 $L(c_i) = \ln\frac{P(c_i=0|y_i)}{P(c_i=1|y_i)}$ 在變數節點與檢查節點之間進行迭代置信傳播（Belief Propagation / 和積演算法 Sum-Product）。經密度演化最佳化的非規則LDPC碼已逼近夏農極限僅差 $0.0045\,\text{dB}$，成為 5G NR 資料通道、Wi-Fi 6/7 與現代 3D NAND SSD 固態硬碟的核心標準。
2. 埃達爾·阿里坎（Erdal Arıkan, 2009）的極化碼（Polar Codes）：利用克羅內克積核矩陣 $\mathbf{G}_N = \mathbf{B}_N \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix}^{\otimes m}$ 對 $N = 2^m$ 個獨立通道實施遞迴通道極化（Channel Polarization）。當 $N \to \infty$ 時，比例恰為 $C = I(W)$ 的合成子通道容量趨向於 $1$（完全無噪），其餘 $1 - C$ 的子通道容量趨向於 $0$（純雜訊）。只需在容量趨近 $1$ 的子通道發送資訊位元、將容量趨近 $0$ 的子通道固定為已知的凍結位元（Frozen Bits $0$），配合連續消除列表解碼（CA-SCL），即可在 $O(N \log N)$ 複雜度下在數學上首次嚴格證明達到夏農容量 $C$，並被確立為 5G NR 控制通道國際標準。

  flowchart TD
    subgraph ModernECC["現代逼近夏農極限的兩大編碼範式"]
        L1["LDPC碼（稀疏二分 Tanner 圖）"] --> L2["變數節點與檢查節點交換軟判決 LLR"]
        L2 --> L3["和積置信傳播（Sum-Product BP）逼近夏農極限 0.0045 dB"]
        P1["Polar碼（克羅內克積 G_N = B_N F^{⊗m}）"] --> P2["通道極化：子通道分裂為 W⁻（退化）與 W⁺（增強）"]
        P2 --> P3["比例 C 趨向容量 1（承載資訊），比例 1-C 趨向容量 0（凍結位元）"]
    end

主流錯誤更正碼體系全景對比表

6. Python 完整實戰驗證：漢明 $(7,4)$ 碼與伽羅瓦體 $\text{GF}(2^8)$ 里德-所羅門解碼器

下面的 Python 程式碼實現了漢明 $(7,4)$ 伴隨式解碼器，以及基於 QR Code 標準有限體 $\text{GF}(2^8)$（不可約多項式 0x11D）的里德-所羅門編碼與 Welch-Berlekamp 代數糾錯解碼：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

from typing import List

def hamming74_demo() -> None:
    G = [[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]]
    H = [[1,1,0,1,1,0,0], [1,0,1,1,0,1,0], [0,1,1,1,0,0,1]]
    msg = [1, 0, 1, 1]
    c = [sum(msg[i] * G[i][j] for i in range(4)) % 2 for j in range(7)]
    y = c.copy()
    y[2] ^= 1
    s = [sum(H[r][col] * y[col] for col in range(7)) % 2 for r in range(3)]
    err_idx = next(col for col in range(7) if [H[r][col] for r in range(3)] == s)
    y[err_idx] ^= 1
    print(f"[Hamming (7,4)] Syndrome={s} -> Flipped idx={err_idx}, Recovered={y[:4] == msg}")

class GF256:
    def __init__(self, poly: int = 0x11D) -> None:
        self.exp, self.log = [0] * 512, [0] * 256
        v = 1
        for i in range(255):
            self.exp[i] = self.exp[i + 255] = v
            self.log[v] = i
            v <<= 1
            if v & 0x100:
                v ^= poly

    def mul(self, a: int, b: int) -> int:
        return 0 if (a == 0 or b == 0) else self.exp[self.log[a] + self.log[b]]

    def inv(self, a: int) -> int:
        return self.exp[255 - self.log[a]]

    def power(self, a: int, p: int) -> int:
        return 1 if p == 0 else (0 if a == 0 else self.exp[(self.log[a] * p) % 255])

    def eval_poly(self, coeffs: List[int], x: int) -> int:
        res = 0
        for c in reversed(coeffs):
            res = self.mul(res, x) ^ c
        return res

    def solve(self, A: List[List[int]], b: List[int]) -> List[int]:
        n = len(b)
        M = [row[:] + [b[i]] for i, row in enumerate(A)]
        for col in range(n):
            piv = next(r for r in range(col, n) if M[r][col] != 0)
            M[col], M[piv] = M[piv], M[col]
            inv_p = self.inv(M[col][col])
            for j in range(col, n + 1):
                M[col][j] = self.mul(M[col][j], inv_p)
            for r in range(n):
                if r != col and M[r][col] != 0:
                    f = M[r][col]
                    for j in range(col, n + 1):
                        M[r][j] ^= self.mul(f, M[col][j])
        return [M[i][n] for i in range(n)]

def rs_demo() -> None:
    gf = GF256()
    text = "VOYAGER-1"
    k, t = len(text), 3
    n = k + 2 * t
    pts = [gf.exp[i] for i in range(n)]
    cw = [gf.eval_poly([ord(c) for c in text], x) for x in pts]
    rx = cw.copy()
    rx[1] ^= 0xFF; rx[6] ^= 0xA5; rx[13] ^= 0x3C
    A = [[gf.power(pts[i], d) for d in range(k + t)] + [gf.mul(rx[i], gf.power(pts[i], d)) for d in range(t)] for i in range(n)]
    b = [gf.mul(rx[i], gf.power(pts[i], t)) for i in range(n)]
    sol = gf.solve(A, b)
    E = sol[k + t:] + [1]
    err_pos = [i for i, x in enumerate(pts) if gf.eval_poly(E, x) == 0]
    valid = [(pts[i], rx[i]) for i in range(n) if i not in err_pos][:k]
    rec = gf.solve([[gf.power(x, d) for d in range(k)] for x, _ in valid], [y for _, y in valid])
    print(f"[RS(15,9) over GF(2^8)] Located Errors={err_pos}, Recovered='{''.join(chr(c) for c in rec)}'")

if __name__ == "__main__":
    hamming74_demo()
    rs_demo()

7. 結語

從克勞德·夏農在1948年揭示通道容量 $C$ 與 $-1.59\,\text{dB}$ 夏農極限，到漢明在超立方體上建立伴隨式幾何，再到里德與所羅門利用伽羅瓦體 $\mathbb{F}_{2^m}$ 上的多項式插值實現 MDS 突發糾錯，直至加拉格爾的 LDPC 置信傳播與阿里坎的通道極化最終觸及夏農極限——正是這座橫跨代數、幾何與機率論的數學豐碑，使得人類能夠在充滿熱雜訊與熵增的物理宇宙中，構建起毫釐不差的數位文明。