シャノンの通信路符号化定理

情報理論における重要な定理の一つに、シャノンの通信路符号化定理があります。これは、雑音（ノイズ）が存在する通信路においても、ある条件を満たせば、理論上の最大値までエラーをほぼゼロに抑えてデジタル情報を伝送できるという画期的な定理です。1948年にクロード・シャノンによって発表され、情報理論の基礎を築きました。

定理の概要

シャノンの通信路符号化定理は、通信路の雑音がどの程度大きくても、一定の条件を満たせば、情報伝送をほぼ完全に近く正確に行えることを示しています。この「一定の条件」とは、情報伝送の速度が「通信路容量」と呼ばれる理論上の最大情報伝送速度を下回るというものです。通信路容量は、通信路の物理的な特性と雑音のレベルによって決定されます。

この定理は、単に情報伝送の可能性を示すだけでなく、誤り訂正の限界と効率についても述べています。つまり、どれだけ効率的に誤りを訂正できるか、どの程度の雑音ならデータ破損を防げるか、といった問題を理論的に扱うことができます。シャノンの定理は、現代の情報理論において、通信技術だけでなく、データ記録などの分野でも広く応用されています。

定理の証明は、1954年にアミエル・ファインスタインによって厳密に行われました。この証明は、シャノンが示した概要を詳細に記述したもので、情報理論の基礎をさらに強固なものとしました。

通信路容量と情報伝送レート

定理の核となるのは、通信路容量 (C) と情報伝送レート (R) の関係です。定理によれば、もし情報伝送レート R が通信路容量 C より小さい (R < C) ならば、受信側での誤り率を任意に小さくすることが可能な符号化方法が存在します。これは、理論的には、通信路容量 C 未満のあらゆる速度で、ほぼ誤りなく情報を伝送できることを意味します。

逆に、情報伝送レート R が通信路容量 C より大きい (R > C) 場合、誤り率を任意に小さくすることはできません。必ず、ある程度の誤りが発生し、その誤り率は情報伝送レートが上がるほど大きくなります。つまり、通信路容量を超える速度で情報を伝送しても、確実に情報を送ることは保証されないのです。

実用的な符号化技術

単純な誤り訂正方法、例えばメッセージを3回送信して多数決を取るような方法では、非効率的であり、理論的な限界には到底及びません。しかし、リード・ソロモン符号、低密度パリティ検査符号（LDPC）、ターボ符号などの高度な符号化技術を用いることで、理論的な通信路容量に非常に近い効率で情報伝送が可能になります。これらの技術は、計算量を犠牲にするものの、現代のデジタル信号処理技術と組み合わせることで、通信路の限界を最大限に活用できます。

特に、LDPC符号は、ある条件下では通信路容量の0.0045dB以内という、極めて高い効率を達成できることが示されています。

数学的な記述

シャノンの通信路符号化定理は、数学的には以下のように表現できます。

1. 達成可能性: 任意の無記憶通信路に対して、通信路容量 C は以下の式で定義されます。

C = sup [p(x)] I(X;Y)

ここで、I(X;Y) は X と Y の相互情報量を表し、sup [p(x)] は入力分布 p(x) について相互情報量を最大化することを意味します。

任意の小さな正数 ε と R < C を満たすレート R に対して、十分大きい N に対して、ブロックエラーの最大確率が ε 以下となるような、長さ N、レート R の符号と復号アルゴリズムが存在します。

2. 達成可能なレート: ビットの誤り率 pb が許容可能な場合、以下のレート R(pb) までが達成可能です。

R(pb) = C / (1 - H2(pb))

ここで、H2(pb) は二値エントロピー関数であり、

H2(pb) = -[pb log2(pb) + (1 - pb) log2(1 - pb)]

3. 達成不可能なレート: R(pb) より大きいレートは、任意のpbに対して達成できません。

証明の概要

定理の証明は、達成可能性の結果と、それに対応する逆定理の結果を含みます。これらの結果により、雑音のある通信路を通じて通信する際に可能なデータレートの上限と下限が示されます。

達成可能性の証明

達成可能性は、ランダム符号化という手法を用いて証明されます。これは、通信路で使用される符号表をランダムに生成し、その性能を平均化することで、誤り率を小さく抑えられる符号が存在することを示すものです。

具体的な証明では、漸近的等分配性(AEP)という概念を用います。AEPとは、長い系列のデータは、その確率分布に従って典型的な集合に属する確率が非常に高くなるという性質です。この性質を用いることで、誤りが発生する確率を詳細に解析することができます。

弱逆定理の証明

逆定理は、達成可能なデータレートに上限があることを示すもので、以下のステップで示されます。

1. エントロピーと相互情報量の関係式を利用します。
2. ファノの不等式を利用し、誤り率を考慮に入れます。
3. 通信路容量は相互情報量の最大値であるという性質を利用します。

これらのステップにより、R > C の場合、誤り率は一定の値以上になることが証明されます。

強逆定理の証明

強逆定理は、R > C の場合に誤り率が1に近づくことを示しており、弱逆定理よりも強い結果となります。

非定常無記憶通信路への拡張

通信路が時間とともに変化する場合（非定常）、通信路容量は以下のように定義されます。

C = lim inf max [p(X1),p(X2),...] (1/n) Σ [i=1 to n] I(Xi;Yi)

この場合でも、それぞれの通信路で通信路容量を得る確率分布に従って符号化することで、達成可能性を証明できます。

結論

シャノンの通信路符号化定理は、情報理論において非常に重要な位置を占める定理であり、デジタル通信技術の根幹をなしています。この定理によって、雑音のある環境でも、情報を確実かつ効率的に伝送するための理論的な基盤が確立されました。

シャノンの通信路符号化定理