跳轉到

1.3 Shannon 的論文（1948）#

導言：一篇文章建立一門科學#

1948 年 7 月與 10 月，Bell 實驗室的 Claude Elwood Shannon（1916–2001）在《Bell System Technical Journal》分兩部分發表《A Mathematical Theory of Communication》。這篇論文後來於 1949 年與 Warren Weaver 合集成書，改名為《The Mathematical Theory of Communication》——加一個定冠詞，宣告這是唯一的理論。

論文做了一件前人從未做到的事：把「通訊」從工程技藝提升為數學理論。它定義了資訊、證明了壓縮的極限、證明了可靠通訊的極限，並指出壓縮與除錯可以完全分開做。今日所有數位系統——手機、網際網路、衛星、儲存媒體——都是這篇論文的工程實現。

Shannon 的問題架構#

Shannon 開宗明義把通訊系統抽象為五個元素：

關鍵的抽象躍進有三：

  1. 語義與工程分離：通訊的工程問題與訊息「意義」無關，只與「從有限集合中選取一個」的統計性質有關。這使理論成為可能。
  2. 信源是隨機過程：文字、語音、影像都是隨機過程的樣本路徑，於是機率論成為自然語言。
  3. 雜訊是統計的：通道不確定，但雜訊有統計規律，可用通道模型描述（第 4 章）。

核心成果一：信源編碼定理#

Shannon 定義熵（第 3 章詳述）：

\[ H(X) = -\sum_{x \in \mathcal{X}} p(x) \log_2 p(x) \]

並證明無失真信源編碼定理：任何無損壓縮的平均碼長不能低於熵：

\[ \bar{L} \ge H(X) \]

且存在編碼方式使 \(\bar{L}\) 任意接近 \(H(X)\) 。熵是壓縮的極限——不多不少。

例題：熵作為壓縮下界#

信源符號 \(\{a, b, c, d\}\) ，機率 \(\{1/2, 1/4, 1/8, 1/8\}\) 。熵為

\[ H = \tfrac12 \cdot 1 + \tfrac14 \cdot 2 + \tfrac18 \cdot 3 + \tfrac18 \cdot 3 = 0.5 + 0.5 + 0.375 + 0.375 = 1.75 \text{ bits} \]

固定長度編碼需 \(2\) bits/符號。Huffman 編碼（5.2 節）可達到 \(\{0, 10, 110, 111\}\) ，平均碼長 \(1.75\) bits，正好等於熵。而任何編碼都無法低於 \(1.75\) ——Shannon 定理保證了這一點。

核心成果二：通道編碼定理#

Shannon 定義離散無記憶通道的容量：

\[ C = \max_{p(x)} I(X;Y) \]

其中 \(I(X;Y)\) 是互資訊（3.3 節），衡量輸入 \(X\) 對輸出 \(Y\) 所能提供的資訊。通道編碼定理宣稱：

只要傳輸率 \(R < C\) ，就存在編碼方式使錯誤率隨碼長增加而趨近於零；若 \(R > C\) ，錯誤率必有嚴格正的下界。

這個結果在當時看似違反直覺：雜訊會破壞資訊，怎麼可能「任意可靠」？Shannon 的答案是隨機編碼：不追求單一精巧的碼，而是證明「隨機挑一個碼，平均而言表現良好」。這個證明技術（random coding argument）至今仍是資訊理論的標配（4.3 節詳述證明思想）。

例題：二元對稱通道的容量#

二元對稱通道（BSC）：每個位元以機率 \(p\) 翻轉。可算出（4.1 節詳推）

\[ C = 1 - H_2(p) \quad \text{bits/use}, \qquad H_2(p) = -p\log_2 p - (1-p)\log_2 (1-p) \]

代入 \(p = 0.11\) ： \(H_2(0.11) \approx 0.500\) ，故 \(C \approx 0.499\) bits/use。意即：即使每十個位元錯一個，仍能以接近每個通道使用 \(0.5\) 位元的速率零錯誤通訊——只要用夠長的碼。這就是編碼理論（第 6–7、10 章）要追趕的極限。

核心成果三：分離定理與高斯容量#

Shannon 指出信源編碼與通道編碼可分開設計：先把信源壓到熵 \(H\) ，再為通道設計碼使率 \(R < C\) 。只要 \(H < C\) ，整體系統可任意可靠。這個「分離」大幅簡化系統設計，是模組化通訊架構的理論根據。

對帶限 \(W\) Hz、雜訊功率 \(N\) 、訊號功率 \(P\) 的加性高斯白雜訊（AWGN）通道，Shannon 給出著名公式：

\[ C = W \log_2\!\left(1 + \frac{P}{N}\right) \quad \text{bits/s} \]

例題：電話線的容量極限#

帶限 \(W = 3000\) Hz、訊雜比 \(P/N = 1000\) （30 dB）：

\[ C = 3000 \log_2(1 + 1000) \approx 3000 \times 9.97 \approx 29900 \text{ bits/s} \]

這解釋了為什麼撥接數據機的速率在 1990 年代末止步於 33.6 kbps（下行 56 kbps 靠壓縮與不同通道假設才突破）——它們已逼近香農極限，物理法則不允許更快。4.2 節將深入此公式的推導與意涵。

歷史前因後果#

誰、何時、為什麼#

Shannon 1936 年自 Michigan 大學畢業，1940 年在 MIT 以《A Symbolic Analysis of Relay and Switching Circuits》獲碩士（把布林代數應用於電路設計，創立數位電路理論）與博士（應用數學，涉及代數理論遺傳學）。二戰期間他在 Bell 實驗室從事密碼分析，與英國圖靈有交流。密碼學工作迫使他用機率與熵思考「秘密量」，1945 年的機密報告《A Mathematical Theory of Cryptography》（後公開為《Communication Theory of Secrecy Systems》，1949）已包含熵的語言。

戰後，他把密碼學中發展的工具反轉過來：密碼學要「隱藏資訊」，通訊理論要「傳遞資訊」，兩者共用同一數學骨架。十年的私人思考（友人回憶他在辦公室深夜工作、玩雜耍與獨輪車）最終凝結成 1948 論文。

解決了什麼問題#

  1. 效率極限：Morse 依頻率編碼的直覺（1.1 節）有了理論極限 \(H\) 與系統性方法（Huffman、算術編碼，第 5 章）。
  2. 可靠度極限：Hartley 的「可靠電平數」（1.2 節）推廣到統計雜訊， \(C\) 成為任何通道的速度極限。
  3. 系統設計：分離定理讓壓縮器與除錯碼可獨立研發，帶動整個產業的模組化。
  4. 密碼學基礎：完美保密性的定義與 one-time pad 的證明（9.3 節）。

引發什麼新問題#

  1. Shannon 的證明是存在性的：他知道好碼存在，卻沒給出可實作的碼。尋找「接近香農極限」的可實作碼，花了五十餘年——Turbo 碼（1993，10.1 節）與 LDPC 碼（10.2 節）才終於抵達。
  2. 信源是隨機過程的假設對語音影像不夠精緻，催生了率失真理論（8.2 節）與感知編碼。
  3. 網路中多個信源、多個通道同時存在——網路資訊理論（10.3 節）至今仍有很多未解問題。
  4. 「資訊」能否量化生物、語言、經濟系統？——資訊理論的跨領域擴張（10.3 節）。

與其他領域的關聯#

統計力學#

Shannon 自己承認，熵的名稱來自馮諾伊曼的建議：「沒有人真的懂熵，你在辯論中永遠佔上風。」Boltzmann–Gibbs 統計力學的熵 \(S = -k \sum p_i \ln p_i\) 與 Shannon 熵形式完全相同（差一個常數與單位）。兩者的深層聯繫——最大熵原理、自由能類比——在 3.1 節與 10.3 節繼續發展。

機率論#

Shannon 熵的極限定理（漸近等分性質 AEP）本質上是大數法則的資訊版（2.1、3.1 節），這條線通向現代資訊理論中的「典型序列」方法。

線性代數與代數#

通道編碼定理說好碼存在，但好的線性碼如何建構？這條線通向有限體（9.1 節）、循環碼（7.1 節）與 Reed–Solomon 碼（7.2 節）。

圖論#

隨機編碼的對偶觀念——隨機圖——後來在 LDPC 碼的 Tanner 圖分析（9.2、10.2 節）中大放異彩。

論文的結構地圖#

論文章節 主題 對應本書
1–3 離散無雜訊信源、熵 第 2、3 章
4 無失真編碼定理 第 5 章
5–7 雜訊通道、容量、編碼定理 第 4 章
8–9 幾何表示、上界技巧 第 4.3、6 章
10–15 連續信源、高斯通道 第 4.2、8 章
16–24 連續通道、率失真預告 第 8 章

小結與思考題#

Shannon 1948 論文的三大定理——信源編碼、通道編碼、（隱含的）分離——界定了之後七十五年資訊與通訊理論的疆界。本書接下來的九章，基本上就是沿著這篇論文的骨架，把每個抽象的「存在」變成可觸摸的「工程」。

思考題

  1. 計算 \(p = \{0.5, 0.25, 0.125, 0.125\}\) 的熵，並設計一個平均碼長 \(1.75\) 的前綴碼驗證它達到極限。
  2. 若 BSC 的錯誤率 \(p = 0.5\) ，容量為何？這在物理上意味著什麼？（提示：輸出與輸入完全無關。）
  3. Shannon 為什麼刻意把「語義」排除在理論之外？若要為「意義」建立理論，會遇到什麼困難？這個問題至今仍是語義通訊（semantic communication）研究的核心。
  4. 用 AWGN 公式估算： \(W = 1\) MHz、SNR = 0 dB（ \(P/N = 1\) ）的容量是多少 bits/s？

第一章到此，我們從 1837 的電報走到了 1948 的數學。第二章開始，我們將補上理論的地基：機率。

深入探討：1948 論文的細讀與時代語境#

一、論文的寫作風格與「可讀性的戰略」#

Shannon 的 1948 論文有一個常被忽略的特點：幾乎不用測度論、極少引用機率論文獻。這不是數學修養不足（Shannon 的博士論文涉及代數），而是刻意選擇：

  • 他以「隨機過程的直觀描述 + 基本極限（大數法則）」行文，讓電機工程師能讀。
  • 嚴格化的工作留給了數學家們（Khinchin 1957、Wolfowitz 1957、Gallager 1968）在之後十年完成。

結果是奇特的：論文的核心定理（信源編碼、通道編碼）的完整證明在原文中是綱要式的，但定理陳述之精確、構造之清晰，使後人只需補細節而無需改結構。證明可以後補，問題的提出不能——這是 Shannon 之所以為 Shannon 的原因。

二、熵的名稱之謎與馮諾伊曼的建議#

關於「entropy」一名的來源，流傳最廣的版本出自 Shannon 自己的回憶：馮諾伊曼建議用這個詞，理由有二——「統計力學中已有人用它，而你不知道該叫什麼」；以及「沒有人真的懂熵，你在辯論中永遠佔上風」。這段軼事的文獻可靠性有爭議（Tribus 1971 的轉述），但反映了兩個事實：

  1. Shannon 函數 \(-\sum p \log p\) 與 Boltzmann–Gibbs 熵 \(-k\sum p \ln p\) 形式相同（3.1 節詳述），同名是合理的。
  2. Shannon 原文曾用「uncertainty」「communication rate」等詞，最後定名 entropy 確實借了物理學的威望。

歷史學家（如 Segal、Verdú 1998 的回顧）認為：Shannon 的熵是從公理推導出來的，與統計力學的獨立殊途同歸；兩者的深層聯繫（最大熵原理、Jaynes 1957）是後來者建成的橋樑，不是 Shannon 原始論文的內容。

三、三大定理的精確陳述（現代形式）#

為本書後續章節立下精確的靶子，我們把 1948 論文的兩大定理以現代術語重述（證明分別在 4.3、5.1 節完成）：

定理（無失真信源編碼）：設 \(\{X_i\}\) 為 i.i.d.、分佈 \(p\) 、熵 \(H\) 。對任意 \(R > H\) 與 \(\epsilon > 0\) ，存在 \(n_0\) ，對 \(n > n_0\) 存在編碼映射 \(\mathrm{enc}: \mathcal{X}^n \to \{0,1\}^{\lceil nR \rceil}\) 與解碼映射使 \(P(\text{解碼錯誤}) < \epsilon\) 。反方向： \(R < H\) 時任何編碼的錯誤率 \(\to 1\) 。

定理（通道編碼）：設離散無記憶通道容量 \(C\) 。對任意 \(R < C\) 與 \(\epsilon > 0\) ，存在 \(n_0\) 與 \((n, 2^{nR})\) 碼使錯誤率 \(< \epsilon\) ； \(R > C\) 時錯誤率有正下界（強逆定理）。

注意兩個定理的對偶結構：都是「存在 \(n_0\) 、存在編碼、錯誤趨零」加「反向不可能」。這種「可達 + 逆」的雙面陳述成為資訊理論所有定理的模板（5.3 節 LZ 定理、8.2 節率失真定理、10.3 節網路定理全部如此）。

四、1948 的四項方法論發明#

除了定理本身，論文貢獻了四項至今通用的證明與建模技術：

  1. 隨機編碼（random coding）：證明「隨機挑碼平均好 ⇒ 存在好碼」。解決了「好碼難找」與「單個碼難證」的雙重困難。4.3 節詳述；10.2 節 LDPC 的「隨機稀疏圖」是它的可解碼化版本。
  2. 典型序列（typical sequences）：用大數法則把序列空間切成「典型/非典型」，一切編碼定理的直接法證明都在典型集上進行（3.1 節 AEP）。
  3. 分離設計（separation）：信源編碼與通道編碼可獨立最佳化，只要 \(H < C\) 。這個模組化讓壓縮器與調變解調器成為兩個獨立產業（4.3 節末討論其非普遍性——有限碼長與多用戶下分離可次優）。
  4. 上界技術（converse）：Fano 式論證 + 資料處理不等式的雛形，宣告「不可能」與「可能」同樣是定理。

五、同時代的競爭理論：為什麼是 Shannon 勝出#

1948 年前後，「資訊」的度量並非只有 Shannon 一家：

提出者 年代 核心觀念 為何未成主流
Hartley 1928 \(\log M\) （等可能） 無機率、無極限定理
Wiener 1948 資訊 = 熵差（濾波/預測語境） 面向控制與預測，無編碼定理
Fisher 1922–25 Fisher 資訊（統計估計） 面向參數估計，非訊息傳輸
Kolmogorov 1965 演算法複雜度 \(K(x)\) 不可計算，作理論基準

Shannon 的獨特組合是：機率建模（Wiener 也懂）+ 對數度量（Hartley 先有）+ 兩大極限定理（只有他有）+ 工程問題的精確翻譯。定理使他的度量「有用」——它給出可達與不可達的硬界；其他度量最多是描述性的。這是「度量必須伴隨定理」的深刻教訓。

六、一個可手工驗證的微型編碼實驗#

把 1948 的信源編碼定理做成一個完整可驗的例子。信源 \(p = \{a: 0.6, b: 0.3, c: 0.1\}\) ：

熵： $$ H = -0.6\log_2 0.6 - 0.3\log_2 0.3 - 0.1\log_2 0.1 = 0.442 + 0.521 + 0.332 = 1.295 \text{ bits} $$

Huffman（5.2 節演算法）：合併 \(c(0.1)+b(0.3) = 0.4\) ；再合併 \(0.4 + 0.6\) 。碼： \(a \to 0\) （長 1）、 \(b \to 10\) （長 2）、 \(c \to 11\) （長 2）。平均碼長：

\[ \bar L = 0.6(1) + 0.3(2) + 0.1(2) = 1.4 \text{ bits} \]

與熵的差距： \(1.4 - 1.295 = 0.105\) bits/符號（約 8%）。

塊狀改善：一次編 2 個符號（ \(M = 9\) 種組合），Huffman 平均碼長約 \(2 \times 1.31\) （接近 \(2H = 2.59\) ）——每符號攤薄到約 1.31 bits，差距縮到 1.2%。這驗證了 5.1 節的定理： \(\bar L < H + 1/n\) （塊長 \(n\) 時）。用一個手算例子走完「熵 → 極限 → 演算法 → 改善」的完整迴路，是理解 1948 定理實際意義的最短路徑。

七、1948 論文的目錄精讀指南#

對想讀原文的讀者，給出章節對應與閱讀建議（本書章節在右）：

論文章節 內容 難點 對應本書
1 離散無雜訊信源 無 2.1–2.2
2 離散信源與熵 公理與極限 3.1
3 序列的熵率 平穩過程 3.2
4 無雜訊編碼定理 首個極限定理 5.1
5 通道與容量 定義 4.1
6 錯誤對率的影響（曖昧度） 條件熵應用 3.2、4.1
7 離散通道編碼定理 隨機編碼首秀 4.3
8–9 幾何表示與上界 高維球 4.3
10–13 連續信源與取樣 連續熵 8.1–8.2
14–16 高斯通道與容量 水填充前身 4.2
17–24 連續通道細節與率失真預告 技術性強 8.2

建議第一次只讀 1–7 章與 15 章（高斯容量），其餘按本書進度回補。原文在 Bell 系統期刊可自由取得，Mathematical Theory of Communication 書版含 Weaver 的科普導讀。

八、補充思考題#

  1. 用第六節的方法對 \(p = \{0.7, 0.2, 0.1\}\) 完整走一遍：算熵、建 Huffman、算塊長 2 的改善。
  2. 論證：若 Shannon 只證出「可達性」而無「逆定理」，工程實踐會有何不同？（提示：人們會在超極限區浪費資源，因為不知道那是物理禁區。）
  3. 對比 Shannon 與 Wiener 的「資訊」定義，各舉一個只有對方理論才能回答的問題。