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

出典: フリー百科事典『ウィキペディア(Wikipedia)』
Jump to navigation Jump to search

情報理論において、シャノンの通信路符号化定理(シャノンのつうしんろふごうかていり、英語: noisy-channel coding theorem)とは、通信路の雑音のレベルがどのように与えられたとしても、その通信路を介して計算上の最大値までほぼエラーのない離散データ(デジタル情報)を送信することが可能であるという定理である。この定理は、1948年にクロード・シャノンによって発表されたが、これはハリー・ナイキストラルフ・ハートレーの初期の仕事とアイデアに一部基づいていた。シャノンの第一基本定理(情報源符号化定理)に対してシャノンの第二基本定理とも言い、単にシャノンの定理とも言う。

上記の「計算上の最大値」を通信路容量(またはシャノン限界、シャノン容量とも)といい、特定の雑音レベルについて、通信路の理論上の最大情報転送速度英語版である。

概要[編集]

1948年にクロード・シャノンによって定式化されたこの定理は、誤り訂正の可能な最大効率と雑音干渉およびデータ破損のレベルを記述している。 シャノンの定理は、通信と情報記録の両方に幅広く応用されている。この定理は、現代的な情報理論の分野にとって根本的に重要なものである。シャノンは証明の概要を記述しただけで、離散した場合の最初の厳密な証明は、1954年のAmiel Feinsteinによるものである。

シャノンの定理によれば、雑音のある通信路の通信路容量C 、情報の送信レートを R と与えたとき、 ならば、受信機での誤り率英語版を任意に小さくすることが可能な符号化が存在する。これは、理論的には、限界速度 C 未満のいかなる速度でも、ほぼ誤差なく情報を伝送することが可能であることを意味する。

逆も重要である。 ならば、任意の小さな誤り率を達成することはできない。全ての符号は、ある正の最小レベルよりも大きい誤り率を有し、このレベルは、レートが増加するにつれて増加する。従って、情報は、通信路容量を超えた速度で通信路を介して確実に伝送されることを保証することはできない。この定理は、速度と容量が等しい稀な状況に対処するものではない。

通信路容量 C は、通信路の物理的特性から計算することができる。ガウス雑音を伴う帯域制限された通信路に対しては、シャノン=ハートレーの定理を用いる。

「メッセージが3回送信され、受信されたメッセージが異なる場合に、3つの中で最良の2つを使用する」などの単純なスキームは、非効率的な誤り訂正法であり、データブロックが誤りなしに通信できることを漸近的に保証することはできない。リード・ソロモン符号低密度パリティ検査符号(LDPC)、ターボ符号などの高度な技術は、理論的な通信路容量に近づくが、計算上の複雑さを犠牲にしている。今日のデジタルシグナルプロセッサでは、これらの高性能な符号化と計算能力を使用することで、通信路容量に非常に近いところまで到達することが可能になっている。 実際、LDPC符号は、非常に長いブロック長を有する2進AWGNチャネルの場合に、通信路容量の0.0045dB以内に到達することができることが示された[1]

数学的な記述[編集]

Comm Channel.svg

定理 (Shannon, 1948)[2]:

1. 任意の無記憶通信路について、通信路容量
[3]
は次の特性を持つ。任意の ε > 0 および R < C について、N が充分に大きい場合、ブロックエラーの最大確率が ≤ ε となるような、長さ N 、レート ≥ R の符号と復号アルゴリズムが存在する。
2. ビットの誤り率 pb が許容可能である場合、 R(pb) までのレートが達成可能である。ここで、
であり、 二値エントロピー関数で、
である。
3. 任意の pb について、 R(pb) より大きいレートは達成できない。

証明の概要[編集]

情報理論における他のいくつかの主要な結果と同様に、雑音のある通信路符号化定理の証明は、達成可能な結果と、一致する逆の結果を含む。この場合、これらの2つの成分は、ノイズの多い通信路を介して通信できる可能なレートのセットに結びつき、これらの境界が狭い境界であることを示すために役立つ。

以下の概要は、情報理論の教科書による学習で利用できる多くの異なるスタイルのうちの1つのセットである。

離散無記憶通信路の達成可能性[編集]

この達成可能性の証明は、漸近的等分配性英語版(AEP)を利用する証明のスタイルに従う。誤り指数英語版を用いた情報理論の教科書では、別のスタイルが使用されている。

どちらのタイプの証明でも、通信路全体で使用される符号一覧表がランダムに構成されているランダムな符号化引数を使用する。これは、通信路容量以下の任意のデータレートで所望の低い誤り率を満足する符号の存在を証明しながら、解析をより簡単にするのに役立つ。

AEPに関連する引数として、与えられた通信路について、長さ の情報源の文字列を 、長さ の出力の文字列を としたとき、同時典型集合(jointly typical set)を以下のように定義できる。

2つの系列 が上記で定義した同時典型集合の中にある場合、これらは同時典型(jointly typical)であるという。

段階

  1. ランダムな符号化引数のスタイルでは、確率分布 Q からの長さ n符号語英語版 個ランダムに生成する。
  2. この符号は送信者と受信者に公開される。また、両者は通信路が使用している遷移行列 を知っているものと仮定する。
  3. メッセージ W は、符号語の集合上の一様分布 に従って選択される。
  4. メッセージ W は、通信路を介して送信される。
  5. 受信機は、 に従う系列を受信する。
  6. これらの符号語を通信路に送信すると、 が受信され、Y に同時典型な1つだけの符号語が存在する場合、情報源系列に復号される。同時典型な符号語が存在しない場合、または2つ以上存在する場合は、誤りが宣言される。復号された符号語が元の符号語と一致しない場合にも誤りが発生する。これを典型集合復号(typical set decoding)という。

このスキームの誤り率は、以下の2つの部分に分割される。

  1. 受信されたY系列に対して同時典型のX系列が見つからない場合、誤りが発生する可能性がある。
  2. 誤ったX系列が受信されたY系列と同時典型である場合、誤りが発生する可能性がある。
  • 符号構成のランダム性によって、全ての符号にわたって平均化された平均誤り率は、送信されたインデックスに依存しないと仮定することができる。従って、一般性を失うことなく、 W = 1 と仮定することができる。
  • 同時AEPから、n が大きくなるにつれて同時典型な X が存在しない確率は0になる。この誤り率は に拘束される。
  • また、同時AEPから、W = 1 としたときの特定の が同時典型である確率は である。

定義:

(メッセージiが、メッセージ1を送信したときに受信された系列と同時典型的であるイベントとして)

通信路の ならば、 が無限大に近づくにつれて、誤り率は0に近づく。

最後に、平均符号一覧表が「良好」であると仮定すると、性能が平均より優れている符号一覧表が存在することがわかっており、雑音の多い通信路全体で通信する任意の低い誤り確率の必要性を満たす。

離散無記憶通信路の弱逆[編集]

個の符号語からなる符号を仮定する。W をこの集合の上に一様に索引として描く。 それぞれ符号語と受信された符号語とする。

  1. は、エントロピー相互情報量を含むidentityとして使用する。
  2. (WはXの関数であるため)
  3. ファノの不等式を使用して)
  4. (容量が相互情報量を最大化するという事実によって)

上記の結果、 となる。 R が C よりも大きい場合、ブロック長 が無限大に近づくにつれ、 は0から離れ有界である。R が C より小さい場合、任意の低いレートか、誤りしか得られない。

離散無記憶通信路の強逆[編集]

ウォルフォウィッツ(Wolfowitz)が1957年に証明[4]した強逆定理(strong converse theorem)によれば、任意の有限の正の定数 について、

である。弱逆状態では、 が無限になるにつれて誤り率がゼロから離れるように制限されているが、強逆は誤り率が1になることを示す。従って、 は完全に信頼できる通信と完全に信頼できない通信の間の鋭い閾値である。

非定常無記憶通信路のための通信路符号化定理[編集]

通信路は無記憶であると仮定しているが、その遷移確率は送信機および受信機において既知の方法で時間と共に変化する。

通信路容量が

で与えられたとする。

最大値は、それぞれの通信路の分配を達成する容量で達成される。その値は、 である。ここで、i 番目の通信路の通信路容量である。

証明の概要[編集]

この証明は、通信路符号化定理とほぼ同じ方法で実行される。達成可能性は、その特定の通信路のための容量を達成する能力から無作為に選択された各シンボルを用いたランダム符号化に続く。典型的な引数は、漸近的等分配性英語版の記事で定義る非定常情報源の典型集合の定義を使用する。

The technicality of lim inf comes into play when does not converge.

関連項目[編集]

脚注[編集]

  1. ^ Sae-Young Chung, G. David Forney, Jr., Thomas J. Richardson, and Rüdiger Urbanke, "On the Design of Low-Density Parity-Check Codes within 0.0045 dB of the Shannon Limit", IEEE Communications Letters, 5: 58-60, Feb. 2001. ISSN 1089-7798
  2. ^ MacKay (2003), p. 162; cf Gallager (1968), ch.5; Cover and Thomas (1991), p. 198; Shannon (1948) thm. 11
  3. ^ ここで、"sup"関数は上限を表す。
  4. ^ Robert Gallager. Information Theory and Reliable Communication. New York: John Wiley & Sons, 1968. 0-471-29048-3

出典[編集]

外部リンク[編集]