雜訊通道編碼定理

在資訊理論裡，有噪信道編碼定理指出，儘管雜訊會干擾通訊信道，但還是有可能在訊息傳輸速率小於信道容量的前提下，以任意低的錯誤概率傳送數據訊息。這個令人驚訝的結果，有時候被稱為訊息原理基本定理，也叫做向農-哈特利定理或向農定理，是由克勞德·艾爾伍德·向農於1948年首次提出。

通訊信道的信道容量或向農限制是指在指定的噪音標準下，信道理論上的最大傳輸率。

總述

根據向農1948年的陳述，本定理描述了在不同級別的噪音干擾和數據損壞情況下，錯誤監測和糾正可能達到的最高效率。定理沒有指出如何構造錯誤監測的模型，只是告訴大家有可能達到的最佳效果。向農定理可以廣泛應用在通訊和數據存儲領域。本定理是現代資訊理論的基礎理論。向農只是提出了證明的大概提綱。1954年，艾米爾·范斯坦第一個提出了嚴密的論證。

向農定理假設一個有噪音的信道，信道容量為C，訊息以速度R傳送，如果

$R<C\,$

那麼就存在一種編碼技術使接收端收到的錯誤達到任意小的數值。這意味著理論上，有可能無錯誤地傳送訊息直到達到速度限制C。

反過來同樣重要。如果

$R>C\,$

那麼想達到任意小的錯誤率是不可能實現的。因此，在傳送速度超過信道容量的時候，可靠傳輸訊息是不能被保證的。定理並沒有指出在什麼特殊情況下速度和容量相等。

簡單的流程如「重複發送數據3遍，用一個投票系統在數據不一樣的時候選擇3個裡面相同的那兩個的值」是低效的錯誤糾正的方式，不能保證數據塊能完全沒有錯誤地傳送。先進一些的技術如里德-所羅門碼編碼技術和更現代一些的Turbo碼、低密度奇偶檢查碼等編碼技術更逼近向農限制，但是計算複雜度很高。

數學描述

定理（向農，1948年）：

1.一個離散無記憶信道的信道容量

$C=\max _{P_{X}}\,I(X;Y)$

具有以下特點：任給ε > 0, R < C，存在著長度為N，訊息傳輸速率小於等於R的編碼和相應解碼算法，使得最大可能傳輸錯誤率≤ ε。

2.如果允許誤碼率p_b，那麼存在一種編碼方式，使得訊息傳輸速率速度可以提高到R(p_b)，其中

$R(p_{b})={\frac {C}{1-H_{2}(p_{b})}}.$

而$H_{2}(p_{b})$是一個二元熵函數，定義為

$H_{2}(p_{b})=-\left[p_{b}\log {p_{b}}+(1-p_{b})\log({1-p_{b}})\right]$

3.給定$p_{b}$，不存在速度大於R(p_b)的編碼方式，使得最大可能傳輸錯誤率小於$p_{b}$。（MacKay (2003), p. 162; cf Gallager (1968), ch.5; Cover and Thomas (1991), p. 198; Shannon (1948) thm. 11）

證明框架

和資訊理論的其它主要結果一樣，噪音信道編碼定理包括一個可以實現的結果和相應的相反的結果。這兩個組成部分中間有一個界線。在本案例中，可以通過有噪音的信道的可能速度的集合和相應邊界顯示出這是一個緊密邊界。

下面的證明框架只是已有的許多種不同證明方法中的一種而已。

離散無記憶信道的可實現性

下面這個可實現性的證明是使用漸近等同分割特性（Asymptotic equipartition property - AEP）方法。另一種資訊理論常用證明方法是錯誤列舉法（Error Exponent）。

兩種證明方法都使用隨機編碼參數來構造信道。這樣的目的是減少計算的複雜度，同時仍舊可以證明在速度低於信道容量的時候，存在誤碼率在可接受範圍甚至是接近於理想的無失真的編碼方式。

採用AEP相關的參數，一個指定的信道，長度為n的源字符串$X_{1}^{n}$，和長度為n的信道輸出的字符串$Y_{1}^{n}$，我們可以定義一個以下匹配序列集合：

$A_{\varepsilon }^{(n)}=\{(x^{n},y^{n})\in {\mathcal {X}}^{n}\times {\mathcal {Y}}^{n}$

$2^{-n(H(X)+\varepsilon )}\leq p(X_{1}^{n})\leq 2^{-n(H(X)-\varepsilon )}$

$2^{-n(H(Y)+\varepsilon )}\leq p(Y_{1}^{n})\leq 2^{-n(H(Y)-\varepsilon )}$

${2^{-n(H(X,Y)+\varepsilon )}}\leq p(X_{1}^{n},Y_{1}^{n})\leq 2^{-n(H(X,Y)-\varepsilon )}\}$

我們可以說兩個序列${X_{1}^{n}}$和$Y_{1}^{n}$是匹配序列，如果它們是基於上述定義的匹配序列集合。

步驟

1. 在隨機編碼參數的方法上，我們可能的範圍Q裡面隨機產生$2^{nR}$長度為n的編碼串。
2. 這個編碼和發送端與接收端有關。同樣假設雙方知道傳輸信道使用的傳輸矩陣$p(y|x)$。
3. 在同樣的範圍里選擇消息W，因此，$\operatorname {Pr} (W=w)=2^{-nR},w=1,2,...,2^{nR}$。
4. 消息W通過信道傳送。
5. 接收端收到了一個基於$P(y^{n}|x^{n}(w))=\prod _{i=1}^{n}p(y_{i}|x_{i}(w))$的序列。
6. 將這些編碼串通過信道發送，我們收到了$Y_{1}^{n}$，如果在編碼表里存在和Y匹配的一個序列，該序列並被解碼成為源編碼序列，如果沒有找到，就報告一個錯誤。如果解碼出的序列和原來的序列不一樣，同樣報告一個錯誤。

這個流程產生的錯誤可以分成兩個部分：

1. 沒有找到和接收到的Y序列相匹配（或在允許的誤碼率條件下）的X序列。
2. 接收到的Y序列解碼成一個錯誤的X序列。

• 考慮到構造碼時的隨機性，我們可以假設平均的錯誤的產生率和碼發送的序列沒有關係。因此，我們假設W = 1。

• 從匹配AEP方法考慮，我們知道隨著n的逐漸增加，沒有對應的X的可能性慢慢降為0。我們可以用$\epsilon$來標記這個錯誤的可能性。

• 同樣從匹配AEP方法考慮，我們知道一個指定的$X_{1}^{n(i)}$和$Y_{1}^{n}$，作為W = 1的結果是匹配序列的可能性為$\leq 2^{-n(I(X;Y)-3\epsilon )}$。

定義：$E_{i}=\{(X_{1}^{n}(i),Y_{1}^{n})\in A_{\epsilon }^{(n)}\},i=1,2,...,2^{nR}$

作為消息1發送出去，消息i作為匹配的消息接收到的結果。

${\begin{aligned}P({\text{error}})&{}=P({\text{error}}|W=1)\leq P(E_{1}^{c})+\sum _{i=2}^{2^{nR}}P(E_{i})\\&{}\leq P(E_{1}^{c})+(2^{nR}-1)2^{-n(I(X;Y)-3\varepsilon )}\\&{}\leq \varepsilon +2^{-n(I(X;Y)-R-3\varepsilon )}.\end{aligned}}$

我們可以發現如果信道$R<I(X;Y)$，n變為無窮大，錯誤的可能性將降為0。

最後，假設平均的編碼方式是「好」的話，我們知道存在一個編碼方式的效率比平均的值要好，因此可以滿足我們在有噪音的信道低誤碼率的要求。

弱逆離散無記憶信道

假設一種編碼有$2^{nR}$個編碼詞語。W假設為在這個集合上的一個索引。設$X^{n}$和$Y^{n}$分別為編碼詞和接收到的詞。

1. $nR=H(W)=H(W|Y^{n})+I(W;Y^{n})\;$使用同樣的熵和同樣的訊息
2. $\leq H(W|Y^{n})+I(X^{n}(W);Y^{n})$X是W的一個函數
3. $\leq 1+P_{e}^{(n)}nR+I(X^{n}(W);Y^{n})$使用Fano不等式
4. $\leq 1+P_{e}^{(n)}nR+nC$信道容量設為最大化

這些步驟的結果是$P_{e}^{(n)}\geq 1-{\frac {1}{nR}}-{\frac {C}{R}}$。當塊的長度變為無窮大，如果R比C大，我們得到$P_{e}^{(n)}$不可能降到0。只有在R比C小的情況下，我們可以得到任意低的誤碼率。

強逆離散無記憶信道

強逆定理證明由Wolfowitz於1957年提出。，證明歸結於證明如下不等式，

$P_{e}\geq 1-{\frac {4A}{n(R-C)^{2}}}-e^{-n(R-C)}$

其中$A$為有限的正常數。當$n$變為無窮大的時候，弱逆定理證明錯誤的可能性不可能變成0，而強逆定理證明了錯誤以指數方式趨向於1。因此，$C$是可靠連接和不可靠連接的臨界點。

時變無記憶信道的信道編碼定理

我們假設信道是無記憶的，但是隨著時間的變化，傳輸的可靠性是變化的。發送端和接收端一樣工作正常。這樣信道容量如下

$C=\liminf \max _{p^{X_{1}},p^{X_{2}},...}{\frac {1}{n}}\sum _{i=1}^{n}I(X_{i};Y_{i})$。

針對每個不同的信道，計算出取得該信道容量似的分布，以求得上式中的最大值，這樣 $C=\liminf {\frac {1}{n}}\sum _{i=1}^{n}C_{i}$ ，信道i的容量為$C_{i}$。

簡略證明

證明方法和上面信道編碼定理幾乎一樣。在指定的信道裡面，每一個符號的選擇是隨機的，編碼方式也是隨機的，採用漸近等同分割特性（AEP）方法來定義變化的無記憶信道的參數集。

當${\frac {1}{n}}\sum _{i=1}^{n}C_{i}$不收斂時，下極限開始起作用。

參考文獻

來源

• 克勞德·艾爾伍德·向農：《通訊的數學理論 （頁面存檔備份，存於網際網路檔案館）》Urbana, IL:University of Illinois Press, 1949（reprinted 1998）。
• 艾米爾·范斯坦：《資訊理論的一個新的基礎定理》IEEE Transactions on Information Theory, 4(4):2-22, 1954.
• 羅卜特·梵谷：《訊息傳輸，通訊的一個統計理論》Cambridge, Mass., M.I.T. Press, 1961. ISBN 0-262-06001-9
• 雅各布·Wolfowitz：《面對誤碼的訊息編碼》Illinois J. Math., vol. 1, pp. 591-606, 1957.
• David J. C. MacKay.《資訊理論推理，算法演繹》Cambridge: Cambridge University Press, 2003. ISBN 0-521-64298-1
• Thomas Cover, Joy Thomas，《資訊理論要素》。New York, NY:John Wiley & Sons, Inc., 1991. ISBN 0-471-06259-6

外部連結

• 向農定律 （頁面存檔備份，存於網際網路檔案館）
• 在線書：資訊理論推理，算法演繹 （頁面存檔備份，存於網際網路檔案館），by David MacKay - 介紹關於向農定理的一些基本知識，包括兩種證明方式，也介紹了現在流行的編碼方式。

參見

• 通訊、信道、信道容量、向農極限
• 資訊理論、克勞德·向農