核心概念#
安德魯·維特比（Andrew Viterbi）發明了現代數字通信中最常用的維特比算法，並與雅各布共同創辦了高通公司（Qualcomm），制定了 CDMA 的 3G 移動通信標準，是對我們生活影響最大的科學家之一。
維特比算法#
- 維特比算法是一個特殊但應用最廣的動態規劃算法，針對篩笛網絡（Lattice）的有向圖最短路徑問題
- 以拼音轉漢字為例：輸入拼音序列 $y_1, y_2, …, y_N$，要找到最可能的漢字序列 $x_1, x_2, …, x_N$，使得 $P(x_1,…,x_N|y_1,…,y_N)$ 最大
- 每個拼音對應多個漢字（如 “zhong” 對應「中」「種」等），展開後形成篩笛網絡，路徑數量呈指數級爆炸（10 個字的句子組合數約 $13^{10} \approx 5 \times 10^{14}$）
算法三大基礎：
- 概率最大的路徑（最短路徑）經過某個節點時，該段子路徑一定也是起點到該節點的最短路徑
- 從起點到終點的最短路徑必定經過第 $i$ 時刻的某個狀態，只要記錄到每個狀態的最短路徑即可
- 從狀態 $i$ 進入狀態 $i+1$ 時，只需考慮前一個狀態的 $k$ 個節點的最短路徑
算法步驟：
- 第一步：計算起點 $S$ 到第一個狀態所有節點的距離
- 第二步（關鍵）：對第二個狀態的每個節點 $x_{2i}$，計算 $d(S, x_{2i}) = \min_{j} [d(S, x_{1j}) + d(x_{1j}, x_{2i})]$
- 逐步推進直到最後一個狀態，得到全局最短路徑
維特比算法的複雜度為 $O(N \cdot D^2)$，其中 $N$ 是網格長度，$D$ 是最大寬度。更重要的是，它與長度成正比，可以按流（Stream）方式實時進行解碼，這是數學漂亮的地方。
CDMA 技術——3G 移動通信的基礎#
- 海蒂·拉瑪爾（Hedy Lamarr）——被譽為史上最美麗的科學家，主業是演員，副業發明了跳頻通信技術（CDMA 的前身），1941 年獲美國專利
- 跳頻技術即擴頻傳輸（Spread-Spectrum Transmission），通信信號在較寬頻帶上傳輸，三大好處：
- 抗干擾能力極強
- 信號難以被截獲
- 頻帶利用更充分（相比固定頻率的 FDMA 和 TDMA）
- CDMA（碼分多址）：每個發送者有不同的密碼，接收者通過密碼過濾留下對應信號，因此多用戶可同時使用同一頻帶
- 維特比放棄算法專利，與雅各布創辦 Linkabit 公司將算法做成芯片，後創辦高通公司推動 CDMA 商用
- 高通制定了 CDMA1、CDMA2000、WCDMA 等 3G 標準，2007 年維特比獲美國國家科學獎
維特比不僅提供了關鍵性的發明，還解決了所有配套技術以保障效益最大化。他是極少數能將技術成功轉化為商業的科學家。
本章小結#
維特比既是偉大的科學家又是成功的企業家，他不僅發明了關鍵算法並放棄專利推廣之，還將 CDMA 技術從學術推向商業應用，從頭到尾完成了一次革命。