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

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

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

概要

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

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

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

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

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

数学的な記述

定理 (Shannon, 1948)^[3]:

1. 任意の無記憶通信路について、通信路容量

C = \sup_{p_{X}} I (X; Y)

^[4]

は次の特性を持つ。任意の正数

ϵ

および

R < C

について、

N

が充分に大きい場合、ブロックエラーの最大確率が

ϵ

以下となるような、長さ

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}) = - [p_{b} \log_{2} p_{b} + (1 - p_{b}) \log_{2} (1 - p_{b})]

である。

3. 任意の

p_{b}

について、

R (p_{b})

より大きいレートは達成できない。

証明の概要

情報理論における他のいくつかの主要な結果と同様に、雑音のある通信路符号化定理の証明は、達成可能性の結果と、対応する逆定理の結果を含む。ここでの場合、これらの2つの構成要素は、雑音のある通信路を介して通信する際に可能なデータレートの集合の有界性を示す役割を果たし、また対応する逆定理は、これらの上下界がタイトであることを示している。

以下の概要は、情報理論の教科書で学習できる様々な証明スタイルのうちの一例に過ぎない。

離散無記憶通信路の達成可能性

この達成可能性の証明は、テンプレート:仮リンク(AEP)を利用する証明のスタイルに従う。他のスタイルとして、テンプレート:仮リンクを用いる情報理論の教科書もある。

どちらのタイプの証明でも、通信路を通じて使用される符号表がランダムに構成されているランダム符号化の論法を使う。これを用いることで解析が簡単になるが、それでもなお、通信路容量以下の任意のデータレートにおいて、誤り率が望むままに小さい符号が存在することを証明できる。

AEP関連の議論により、与えられた通信路について、長さ $n$ の情報源シンボル系列を $X_{1}^{n}$ 、長さ $n$ の通信路出力系列を $Y_{1}^{n}$ とするとき、同時典型集合(jointly typical set)を以下のように定義できる。

A_{ε}^{(n)} = {(x^{n}, y^{n}) \in 𝒳^{n} \times 𝒴^{n}

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

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

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

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

ステップ

ランダム符号化の論法では、確率分布 $Q$ から長さ $n$ の符号語を $2^{n R}$ 個ランダムに生成する。
この符号は送信者と受信者に公開される。また、両者は通信路が使用している遷移行列 $p (y | x)$ を知っているものと仮定する。
メッセージ W は、符号語の集合上の一様分布に従って選択される。その一様分布は、 $P r (W = w) = 2^{- n R}, w = 1, 2, \dots, 2^{n R}$ である。
メッセージ W は、通信路を通じて送信される。
受信者は、 $P (y^{n} | x^{n} (w)) = \prod_{i = 1}^{n} p (y_{i} | x_{i} (w))$ に従って系列を受信する。
これらの符号語を通信路を通じて送信すると、 $Y_{1}^{n}$ が受信され、Y に同時典型な符号語が丁度1個だけ存在するのであれば、何らかの情報源系列に復号される。同時典型な符号語が存在しない、あるいは2つ以上存在する場合は、誤りが宣言される。さらに、復号された符号語が元の符号語と一致しない場合にも誤りが発生する。これを典型集合復号(typical set decoding)という。

この枠組みにおける誤り率は、2つの部分に分けられる。

受信系列Yに対して同時典型な系列Xが存在しない場合、誤りが発生する可能性がある。
正しくない系列Xが受信系列Yと同時典型である場合、誤りが発生する可能性がある。

符号の構成がランダムであることから、符号全体で平均した平均誤り率は、送信されたメッセージ番号に依存しないと仮定できる。従って、一般性を失うことなく、 $W = 1$ と仮定して良い。
同時AEPから、 $n$ を大きくすると、同時典型な X が存在しない確率は0に近付く。この誤り率は、上界として $ε$ に限定できる。
また、同時AEPから、ある特定の $X_{1}^{n} (i)$ とメッセージ $W = 1$ から得られた $Y_{1}^{n}$ とが同時典型である確率は $\leq 2^{- n (I (X; Y) - 3 ε)}$ である。

メッセージ1が送信されたときの受信系列と、メッセージiとが同時典型である事象として、次のように事象 $E_{i}$ を定義する。

定義: $E_{i} = {(X_{1}^{n} (i), Y_{1}^{n}) \in A_{ε}^{(n)}}, i = 1, 2, \dots, 2^{n R}$

\begin{matrix} P (error) & = P (error | W = 1) \leq P (E_{1}^{c}) + \sum_{i = 2}^{2^{n R}} P (E_{i}) \\ \leq P (E_{1}^{c}) + (2^{n R} - 1) 2^{- n (I (X; Y) - 3 ε)} \\ \leq ε + 2^{- n (I (X; Y) - R - 3 ε)} . \end{matrix}

通信路に関して $R < I (X; Y)$ であれば、 $n$ を無限大に持って行くと、誤り率は0に近付くことが分かる。

最終的に、平均的な符号表が「良好」であることが示されたわけだが、性能が平均よりも優れている符号表が存在することは明らかであるため、雑音のある通信路を通じて任意の小さな誤り率で通信するという要求を満たしている。

離散無記憶通信路の弱逆定理

$2^{n R}$ 個の符号語からなる符号について考える。 $W$ は、この集合から一様的に選んだ符号語の番号であるとする。 $X^{n}$ および $Y^{n}$ は、それぞれ送出した符号語と受信した符号語であるとする。

$n R = H (W) = H (W | Y^{n}) + I (W; Y^{n})$ （エントロピーと相互情報量に関する恒等式を用いて）
$\leq H (W | Y^{n}) + I (X^{n} (W); Y^{n})$ （Xは $W$ の関数であるため）
$\leq 1 + P_{e}^{(n)} n R + I (X^{n} (W); Y^{n})$ （ファノの不等式を用いて）
$\leq 1 + P_{e}^{(n)} n R + n C$ （通信路容量は、相互情報量を最大化したものであることから）

これらのステップの結果として、 $P_{e}^{(n)} \geq 1 - \frac{1}{n R} - \frac{C}{R}$ が得られる。 R が C よりも大きい場合、ブロック長 $n$ を無限大に持って行くと、 $P_{e}^{(n)}$ は0より大きな下界を持つことになる。任意に小さな誤り率を得ることができるのは、R が C より小さい場合に限られる。

離散無記憶通信路の強逆定理

ウォルフォウィッツ(Wolfowitz)が1957年に証明^[5]した強逆定理(strong converse theorem)では、任意の有限の正の定数 $A$ について、

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

であることを示している。弱逆定理では、 $n$ を無限大に持って行くと、誤り率が0より大きな下界を持つことしか示していないのに対し、強逆定理では誤り率が1に近付くことを示している。このように、 $C$ は、完全に信頼できる通信とまったく信頼できない通信とをはっきりと分ける境界点になっている。

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

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

通信路容量は、

C = \lim \inf \max_{p^{(} X_{1}), p^{(} X_{2}), . . .} \frac{1}{n} \sum_{i = 1}^{n} I (X_{i}; Y_{i})

により与えられる。

最大値は、それぞれの通信路において通信路容量に達する確率分布において得られる。つまり、 $C_{i}$ を時刻 i の通信路の通信路容量とすると、 $C = \lim \inf \frac{1}{n} \sum_{i = 1}^{n} C_{i}$ である。

下極限( $\lim \inf$ )の部分は、 $\frac{1}{n} \sum_{i = 1}^{n} C_{i}$ が収束しない場合に機能する。

証明の概要

この証明は、通信路符号化定理とほぼ同じ方法で行われる。達成可能性は、それぞれの通信路で通信路容量を得る確率分布に従ってランダムに抽出された各シンボルを用いたランダム符号化を用いて証明される。典型性の議論では、テンプレート:仮リンクの記事の非定常情報源における典型集合の定義を使用する。

脚注

テンプレート:Reflist

出典

テンプレート:仮リンク, Thomas J. A., Elements of Information Theory, John Wiley & Sons, 1991. テンプレート:ISBN2
Fano, R. M., Transmission of information; a statistical theory of communications, MIT Press, 1961. テンプレート:ISBN2
Feinstein, Amiel, "A New basic theorem of information theory", IEEE Transactions on Information Theory, 4(4): 2-22, 1954.
テンプレート:仮リンク, Information Theory, Inference, and Learning Algorithms, Cambridge University Press, 2003. テンプレート:ISBN2 [free online]
Shannon, C. E., A Mathematical Theory of Communication Urbana, IL: University of Illinois Press, 1949 (reprinted 1998).
テンプレート:仮リンク, "The coding of messages subject to chance errors", Illinois J. Math., 1: 591–606, 1957.

外部リンク

↑ テンプレート:Cite report
↑ 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
↑ MacKay (2003), p. 162; cf Gallager (1968), ch.5; Cover and Thomas (1991), p. 198; Shannon (1948) thm. 11
↑ ここで、"sup"関数は上限を表す。
↑ Robert Gallager. Information Theory and Reliable Communication. New York: John Wiley & Sons, 1968. テンプレート:ISBN2

[1] テンプレート:Cite report

[2] 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

[3] MacKay (2003), p. 162; cf Gallager (1968), ch.5; Cover and Thomas (1991), p. 198; Shannon (1948) thm. 11

[4] ここで、"sup"関数は上限を表す。

[5] Robert Gallager. Information Theory and Reliable Communication. New York: John Wiley & Sons, 1968. テンプレート:ISBN2

[1]

[2]

[3]

[4]

[5]

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

目次

概要

数学的な記述

証明の概要

離散無記憶通信路の達成可能性

離散無記憶通信路の弱逆定理

離散無記憶通信路の強逆定理

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

証明の概要

関連項目

脚注

出典

外部リンク

ナビゲーションメニュー

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

概要

数学的な記述

証明の概要

離散無記憶通信路の達成可能性

離散無記憶通信路の弱逆定理

離散無記憶通信路の強逆定理

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

証明の概要

関連項目

脚注

出典

外部リンク

ナビゲーション メニュー

検索

ナビゲーションメニュー