雑音のある通信路の符号化定理

情報理論における雑音通信路符号化定理（シャノンの定理、シャノンの限界とも呼ばれる）は、通信路の雑音汚染の程度に関係なく、計算可能な最大速度まで離散データ（デジタル情報）をほぼエラーなしで通信することが（理論上）可能であることを証明しています。この結果は、1948年にクロード・シャノンによって発表され、ハリー・ナイキストとラルフ・ハートリーの以前の研究とアイデアに部分的に基づいています。

通信チャネルのシャノン限界またはシャノン容量とは、リンクが特定のノイズ レベルに対してランダムなデータ伝送エラーの影響を受ける場合に、チャネルを介して理論上転送できるエラーのないデータの最大速度を指します。これはシャノン(1948) によって初めて説明され、その後すぐにシャノンとウォーレン ウィーバーによる「通信の数学的理論」(1949) という本で出版されました。これが現代の情報理論の分野の基礎となりました。

1948 年にクロード シャノンが提唱したこの定理は、エラー訂正方法の最大効率とノイズ干渉およびデータ破損のレベルとの関係を説明しています。シャノンの定理は、通信とデータ ストレージの両方で幅広く応用されています。この定理は、現代の情報理論の分野にとって基礎的な重要性を持っています。シャノンは証明の概要のみを示しました。離散的なケースの最初の厳密な証明は、(Feinstein 1954) で示されています。

シャノンの定理は、チャネル容量 Cのノイズの多いチャネルと、レートRで送信される情報が与えられた場合、受信側でのエラーの確率を任意に小さくできるコードが存在するかどうかを述べています。これは、理論的には、制限レートC未満の任意のレートで、ほぼエラーなしで情報を送信できることを意味します。 ${\displaystyle R<C}$

逆もまた重要です。 の場合、任意の小さなエラー確率は達成できません。すべてのコードには、特定の正の最小レベルを超えるエラー確率があり、このレベルはレートが増加するにつれて増加します。したがって、チャネル容量を超えるレートでは、チャネルを介して情報が確実に送信されることは保証されません。定理は、レートと容量が等しいまれな状況には対処していません。 ${\displaystyle R>C}$

チャネル容量はチャネルの物理的特性から計算できます。ガウスノイズを伴う帯域制限チャネルの場合は、シャノン・ハートレーの定理を使用します。 ${\displaystyle C}$

「メッセージを 3 回送信し、コピーが異なる場合は 3 件中 2 件の投票方式を使用する」などの単純な方式は、非効率的なエラー訂正方法であり、データ ブロックがエラーなしで通信できることを漸近的に保証することはできません。リード ソロモン コードや、より最近では 低密度パリティ チェック(LDPC) コードやターボ コードなどの高度な技術は、理論的なシャノン限界に非常に近づいていますが、計算の複雑さが高くなります。これらの非常に効率的なコードと、今日のデジタル信号プロセッサの計算能力を使用すると、シャノン限界に非常に近づくことができます。実際、LDPC コードは、シャノン限界の 0.0045 dB 以内に到達できることが示されています (ブロック長が非常に長いバイナリ加法性白色ガウス雑音(AWGN) チャネルの場合)。 ^[1]

通信システムの基本的な数学モデルは次のとおりです。

${\displaystyle {\xrightarrow[{\text{Message}}]{W}}{\begin{array}{|c| }\hline {\text{Encoder}}\\f_{n}\\\hline \end{array}}{\xrightarrow[{\mathrm {Encoded \atop sequence} }]{X^{n}}}{\begin{array}{|c| }\hline {\text{Channel}}\\p(y|x)\\\hline \end{array}}{\xrightarrow[{\mathrm {Received \atop sequence} }]{Y^{n}}}{\begin{array}{|c| }\hline {\text{Decoder}}\\g_{n}\\\hline \end{array}}{\xrightarrow[{\mathrm {Estimated \atop message} }]{\hat {W}}}}$

メッセージW は、 エンコードおよびデコード機能を使用して、ノイズの多いチャネルを介して送信されます。エンコーダーは、W を長さnのチャネル シンボルの事前定義されたシーケンスにマッピングします。最も基本的なモデルでは、チャネルはこれらのシンボルのそれぞれを他のシンボルとは独立して歪ませます。チャネルの出力 (受信シーケンス) はデコーダーに送られ、デコーダーはシーケンスをメッセージの推定値にマッピングします。この設定では、エラーの確率は次のように定義されます。

${\displaystyle P_{e}={\text{Pr}}\left\{{\hat {W}}\neq W\right\}.}$

定理(シャノン、1948):

1. 離散無記憶通信路の通信路容量は相互情報 量によって次のように定義される。${\displaystyle I(X;Y)}$

${\displaystyle \ C=\sup _{p_{X}}I(X;Y)}$^[2]

には次の特性があります。 および に対して、十分に大きい に対して、長さおよびレートのコードと、ブロック誤りの最大確率が となるような復号化アルゴリズムが存在します。${\displaystyle \epsilon >0}$${\displaystyle R<C}$${\displaystyle N}$${\displaystyle N}$${\displaystyle \geq R}$${\displaystyle \leq \epsilon }$

2. ビットエラーの確率が許容できる場合、最大速度が達成可能であり、ここで${\displaystyle p_{b}}$${\displaystyle R(p_{b})}$

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

そして、2進エントロピー関数${\displaystyle H_{2}(p_{b})}$

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

3. いずれの についても、 を超えるレートは達成できません。${\displaystyle p_{b}}$${\displaystyle R(p_{b})}$

(MacKay (2003)、p. 162; Gallager (1968)、ch.5を参照; Cover and Thomas (1991)、p. 198; Shannon (1948) thm. 11)

情報理論における他のいくつかの主要な結果と同様に、ノイズのあるチャネル符号化定理の証明には、達成可能性の結果とそれに対応する逆の結果が含まれます。この 2 つの要素は、この場合、ノイズのあるチャネルを介して通信できる可能な速度のセットを制限する役割を果たし、それに対応することは、これらの制限が厳密な制限であることを示す役割を果たします。

以下のアウトラインは、情報理論のテキストで学習できるさまざまなスタイルのうちの 1 つにすぎません。

この達成可能性の証明は、漸近等分割特性(AEP)を使用する証明のスタイルに従います。別のスタイルは、誤差指数を使用する情報理論のテキストで見つけることができます。

どちらのタイプの証明も、チャネル全体で使用されるコードブックがランダムに構築されるランダム コーディング引数を使用します。これにより、分析が簡単になり、チャネル容量を下回る任意のデータ レートで望ましい低いエラー確率を満たすコードの存在が証明されます。

AEP関連の議論により、チャネル、長さのソースシンボルの文字列、および長さのチャネル出力の文字列が与えられた場合、次のように 共同典型セットを定義できます。${\displaystyle n}$${\displaystyle X_{1}^{n}}$${\displaystyle n}$${\displaystyle Y_{1}^{n}}$

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

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

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

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

2 つのシーケンスとが、上で定義した共同典型セット内にある場合、それら は共同典型であると言います。${\displaystyle {X_{1}^{n}}}$${\displaystyle Y_{1}^{n}}$

手順

1. ランダム コーディングの議論のスタイルでは、確率分布 Q から長さ n のコードワードをランダムに生成します。${\displaystyle 2^{nR}}$
2. このコードは送信者と受信者に公開されます。また、使用されているチャネルの遷移行列もわかっているものと想定されます。${\displaystyle p(y|x)}$
3. メッセージ W は、コードワードのセット上の均一分布に従って選択されます。つまり、 です。${\displaystyle Pr(W=w)=2^{-nR},w=1,2,\dots ,2^{nR}}$
4. メッセージ W がチャネルを介して送信されます。
5. 受信側は、以下のシーケンスを受信する。${\displaystyle P(y^{n}|x^{n}(w))=\prod _{i=1}^{n}p(y_{i}|x_{i}(w))}$
6. これらのコードワードをチャネル経由で送信すると、 を受信し、 Y と共同典型的なコードワードが 1 つだけ存在する場合は、何らかのソース シーケンスにデコードします。共同典型的なコードワードがない場合、または複数ある場合は、エラーが宣言されます。デコードされたコードワードが元のコードワードと一致しない場合にもエラーが発生します。これは、典型セット デコードと呼ばれます。${\displaystyle Y_{1}^{n}}$

この方式のエラー確率は 2 つの部分に分かれています。

1. まず、受信したYシーケンスに対して共通の典型的なXシーケンスが見つからない場合、エラーが発生する可能性があります。
2. 2 番目に、誤った X シーケンスが受信した Y シーケンスと共同で典型的な場合、エラーが発生する可能性があります。

• コード構成のランダム性により、すべてのコードにわたって平均されたエラーの平均確率は、送信されたインデックスに依存しないと想定できます。したがって、一般性を失うことなく、W = 1 と想定できます。
• 共同 AEP から、共同典型的な X が存在しない確率は、n が大きくなるにつれて 0 に近づくことがわかります。このエラー確率は で制限できます。${\displaystyle \varepsilon }$
• また、結合 AEP から、特定のとW = 1から得られるが結合して典型的である確率は であることがわかります。${\displaystyle X_{1}^{n}(i)}$${\displaystyle Y_{1}^{n}}$${\displaystyle \leq 2^{-n(I(X;Y)-3\varepsilon )}}$

定義する：${\displaystyle E_{i}=\{(X_{1}^{n}(i),Y_{1}^{n})\in A_{\varepsilon }^{(n)}\},i=1,2,\dots ,2^{nR}}$

メッセージ i がメッセージ 1 が送信されたときに受信されたシーケンスと共同で典型的であるというイベントとして。

${\displaystyle {\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}}}$

が無限大に近づくにつれて、チャネルのエラー確率は 0 になる ことがわかります。${\displaystyle n}$${\displaystyle R<I(X;Y)}$

最後に、平均的なコードブックが「良好」であることが示されていることから、平均よりもパフォーマンスが優れているコードブックが存在することがわかり、ノイズの多いチャネルを介して通信する際にエラー確率を任意に低く抑えるという要件を満たします。

コードワードのコードを想定します。W をインデックスとしてこのセット上に一様に描画します。およびをそれぞれ送信コードワードと受信コードワードとします。 ${\displaystyle 2^{nR}}$${\displaystyle X^{n}}$${\displaystyle Y^{n}}$

1. ${\displaystyle nR=H(W)=H(W|Y^{n})+I(W;Y^{n})}$エントロピーと相互情報量を含むアイデンティティを使用する
2. ${\displaystyle \leq H(W|Y^{n})+I(X^{n}(W);Y^{n})}$XはWの関数なので
3. ${\displaystyle \leq 1+P_{e}^{(n)}nR+I(X^{n}(W);Y^{n})}$ファノの不等式を利用して
4. ${\displaystyle \leq 1+P_{e}^{(n)}nR+nC}$容量が相互情報量によって最大化されるという事実によって。

これらの手順の結果は、 です。ブロックの長さが無限大になると、R が C より大きい場合、 は 0 から制限されます。 R が C より小さい場合にのみ、任意の低いエラー率を得ることができます。 ${\displaystyle P_{e}^{(n)}\geq 1-{\frac {1}{nR}}-{\frac {C}{R}}}$${\displaystyle n}$${\displaystyle P_{e}^{(n)}}$

1957年にウォルフォウィッツによって証明された強い逆定理^[3]は、

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

有限の正の定数 に対して となります。弱い逆は が無限大に近づくにつれてエラー確率がゼロから制限されることを述べていますが、強い逆はエラーが 1 に近づくことを述べています。したがって、 は完全に信頼できる通信とまったく信頼できない通信との間の明確な境界です。 ${\displaystyle A}$${\displaystyle n}$${\displaystyle C}$

チャネルはメモリがないと仮定しますが、その遷移確率は時間とともに変化し、送信側と受信側でその変化がわかります。

チャネル容量は次のように表される。

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

最大値は、各チャネルの容量達成分布で達成されます。つまり、 i番目のチャネルの容量 です。 ${\displaystyle C=\lim \inf {\frac {1}{n}}\sum _{i=1}^{n}C_{i}}$${\displaystyle C_{i}}$

証明は、チャネル符号化定理の証明とほぼ同じ方法で行われます。達成可能性は、特定のチャネルの容量達成分布から各シンボルをランダムに選択するランダム符号化から得られます。典型性に関する議論では、漸近的等分割特性の記事で定義されている非定常ソースの典型セットの定義を使用します。

lim infの専門性は、収束しない 場合に関係してきます。${\displaystyle {\frac {1}{n}}\sum _{i=1}^{n}C_{i}}$

• 漸近等分配特性(AEP)
• ファノの不等式
• レート歪み理論
• シャノンの情報源符号化定理
• シャノン・ハートレーの定理
• ターボコード

• Aazhang, B. (2004). 「Shannon のノイズの多いチャネル符号化定理」(PDF) .接続.
• Cover, TM ; Thomas, JA (1991).情報理論の要素. Wiley. ISBN 0-471-06259-6。
• ファノ、RM（1961）。情報の伝達：コミュニケーションの統計理論。MITプレス。ISBN 0-262-06001-9。
• ファインスタイン、アミエル（1954年9月）。「情報理論の新しい基本定理」。IRE情報理論専門家グループの取引。4 （ 4）：2-22。Bibcode ：1955PhDT......12F。doi ： 10.1109/TIT.1954.1057459。hdl ： 1721.1 /4798。
• Lundheim, Lars (2002). 「ShannonとShannonの公式について」(PDF) . Telektronik . 98 (1): 20–29.

• MacKay, David JC (2003)。情報理論、推論、学習アルゴリズム。ケンブリッジ大学出版局。ISBN 0-521-64298-1。 [無料オンライン]
• シャノン、CE (1948)。「通信の数学的理論」。ベルシステム技術ジャーナル。27 (3): 379–423。doi :10.1002/j.1538-7305.1948.tb01338.x 。
• シャノン、CE（1998）[1948]。コミュニケーションの数学的理論。イリノイ大学出版局。
• Wolfowitz, J. (1957). 「偶然の誤りの影響を受けるメッセージのコーディング」. Illinois J. Math . 1 (4): 591–606. doi : 10.1215/ijm/1255380682 .