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

情報理論において、シャノンの通信路符号化定理（シャノンのつうしんろふごうかていり、）とは、通信路の雑音のレベルがどのように与えられたとしても、その通信路を介して計算上の最大値までほぼエラーのない離散データ（デジタル情報）を送信することが可能であるという定理である。この定理は、1948年にクロード・シャノンによって発表されたが、これはハリー・ナイキストとラルフ・ハートレーの初期の仕事とアイデアに一部基づいていた。シャノンの第一基本定理（情報源符号化定理）に対してシャノンの第二基本定理とも言い、単にシャノンの定理とも言う。
上記の「計算上の最大値」を通信路容量（またはシャノン限界、シャノン容量とも）といい、特定の雑音レベルについて、通信路の理論上の最大情報転送速度である。
概要.
1948年にクロード・シャノンによって定式化されたこの定理は、誤り訂正の可能な最大効率と雑音干渉およびデータ破損のレベルを記述している。 シャノンの定理は、通信と情報記録の両方に幅広く応用されている。この定理は、現代的な情報理論の分野にとって根本的に重要なものである。シャノンは証明の概要を記述しただけで、離散した場合の最初の厳密な証明は、1954年のAmiel Feinsteinによるものである。
シャノンの定理によれば、雑音のある通信路の通信路容量を "C" 、情報の送信レートを "R" と与えたとき、 formula_1 ならば、受信機での誤り率を任意に小さくすることが可能な符号化が存在する。これは、理論的には、限界速度 "C" 未満のいかなる速度でも、ほぼ誤差なく情報を伝送することが可能であることを意味する。
逆も重要である。 formula_2 ならば、任意の小さな誤り率を達成することはできない。全ての符号は、ある正の最小レベルよりも大きい誤り率を有し、このレベルは、レートが増加するにつれて増加する。従って、情報は、通信路容量を超えた速度で通信路を介して確実に伝送されることを保証することはできない。この定理は、速度と容量が等しい稀な状況に対処するものではない。
通信路容量 "C" は、通信路の物理的特性から計算することができる。ガウス雑音を伴う帯域制限された通信路に対しては、シャノン＝ハートレーの定理を用いる。
「メッセージが3回送信され、受信されたメッセージが異なる場合に、3つの中で最良の2つを使用する」などの単純なスキームは、非効率的な誤り訂正法であり、データブロックが誤りなしに通信できることを漸近的に保証することはできない。リード・ソロモン符号、低密度パリティ検査符号(LDPC)、ターボ符号などの高度な技術は、理論的な通信路容量に近づくが、計算上の複雑さを犠牲にしている。今日のデジタルシグナルプロセッサでは、これらの高性能な符号化と計算能力を使用することで、通信路容量に非常に近いところまで到達することが可能になっている。
実際、LDPC符号は、非常に長いブロック長を有する2進AWGNチャネルの場合に、通信路容量の0.0045dB以内に到達することができることが示された。
数学的な記述.
定理 (Shannon, 1948):
証明の概要.
情報理論における他のいくつかの主要な結果と同様に、雑音のある通信路符号化定理の証明は、達成可能性の結果と、対応する逆定理の結果を含む。ここでの場合、これらの2つの構成要素は、雑音のある通信路を介して通信する際に可能なデータレートの集合の有界性を示す役割を果たし、また対応する逆定理は、これらの上下界がタイトであることを示している。
以下の概要は、情報理論の教科書で学習できる様々な証明スタイルのうちの一例に過ぎない。
離散無記憶通信路の達成可能性.
この達成可能性の証明は、(AEP)を利用する証明のスタイルに従う。他のスタイルとして、を用いる情報理論の教科書もある。
どちらのタイプの証明でも、通信路を通じて使用される符号表がランダムに構成されているランダム符号化の論法を使う。これを用いることで解析が簡単になるが、それでもなお、通信路容量以下の任意のデータレートにおいて、誤り率が望むままに小さい符号が存在することを証明できる。
AEP関連の議論により、与えられた通信路について、長さ formula_7 の情報源シンボル系列を formula_8 、長さ formula_7 の通信路出力系列を formula_10 とするとき、同時典型集合(jointly typical set)を以下のように定義できる。
2つの系列 formula_15 と formula_16 が上記で定義した同時典型集合の中にある場合、これらは同時典型(jointly typical)であるという。
ステップ
この枠組みにおける誤り率は、2つの部分に分けられる。
メッセージ1が送信されたときの受信系列と、メッセージiとが同時典型である事象として、次のように事象formula_26を定義する。
定義: formula_27
通信路に関して formula_29 であれば、formula_7 を無限大に持って行くと、誤り率は0に近付くことが分かる。
最終的に、平均的な符号表が「良好」であることが示されたわけだが、性能が平均よりも優れている符号表が存在することは明らかであるため、雑音のある通信路を通じて任意の小さな誤り率で通信するという要求を満たしている。
離散無記憶通信路の弱逆定理.
formula_31個の符号語からなる符号について考える。Wは、この集合から一様的に選んだ符号語の番号であるとする。formula_32 および formula_33 は、それぞれ送出した符号語と受信した符号語であるとする。
これらのステップの結果として、 formula_38 が得られる。
R が C よりも大きい場合、ブロック長 formula_7 を無限大に持って行くと、formula_40 は0より大きな下界を持つことになる。任意に小さな誤り率を得ることができるのは、R が C より小さい場合に限られる。
離散無記憶通信路の強逆定理.
ウォルフォウィッツ(Wolfowitz)が1957年に証明した強逆定理(strong converse theorem)では、任意の有限の正の定数 formula_41 について、
であることを示している。弱逆定理では、formula_7 を無限大に持って行くと、誤り率が0より大きな下界を持つことしか示していないのに対し、強逆定理では誤り率が1に近付くことを示している。このように、formula_44 は、完全に信頼できる通信とまったく信頼できない通信とをはっきりと分ける境界点になっている。
非定常無記憶通信路のための通信路符号化定理.
通信路は無記憶であると仮定しているが、その遷移確率は送信者および受信者において既知の方法で離散時刻 "i" と共に変化する。
通信路容量は、
により与えられる。
最大値は、それぞれの通信路において通信路容量に達する確率分布において得られる。つまり、formula_46 を時刻 "i" の通信路の通信路容量とすると、
formula_47
である。
下極限(formula_48)の部分は、formula_49が収束しない場合に機能する。
証明の概要.
この証明は、通信路符号化定理とほぼ同じ方法で行われる。達成可能性は、それぞれの通信路で通信路容量を得る確率分布に従ってランダムに抽出された各シンボルを用いたランダム符号化を用いて証明される。典型性の議論では、の記事の非定常情報源における典型集合の定義を使用する。