Information-theoretical limit on transmission rate in a communication channel
電気工学 、 コンピュータサイエンス 、 情報理論 における チャネル容量とは、 通信チャネルを介して 情報を 確実に送信できる 理論上の最大速度です 。
雑音下通信路符号化定理 によれば、与えられた通信 路 の通信路容量は 、任意の小さな誤り確率で達成できる 最高の情報速度（単位時間あたりの 情報量）である。 [1] [2]
1948年にクロード・E・シャノン によって提唱された 情報理論は 、チャネル容量の概念を定義し、それを計算するための数学モデルを提供しています。重要な結論は、上で定義したチャネル容量は、チャネルの入力と出力間の 相互情報量 の最大値によって与えられ、その最大化は入力分布に関して行われるというものです。 [3]
チャネル容量の概念は、チャネル容量によって約束された限界に非常に近いパフォーマンスを実現する
新しい エラー訂正コーディング メカニズムの登場により、現代の有線および無線通信システムの開発の中心となっています。
通信システムの基本的な数学モデルは次のとおりです。
→ Message W Encoder f n → E n c o d e d s e q u e n c e X n Channel p ( y | x ) → R e c e i v e d s e q u e n c e Y n Decoder g n → E s t i m a t e d m e s s a g e W ^ {\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 {\displaystyle W} 送信されるメッセージです。 X {\displaystyle X} は、アルファベット 順に並べられたチャネル入力シンボル（シンボル のシーケンス ）です 。 X n {\displaystyle X^{n}} n {\displaystyle n} X {\displaystyle {\mathcal {X}}} Y {\displaystyle Y} は、アルファベット順に並べられた チャネル出力シンボル（シンボル のシーケンス）です 。 Y n {\displaystyle Y^{n}} n {\displaystyle n} Y {\displaystyle {\mathcal {Y}}} W ^ {\displaystyle {\hat {W}}} 送信されたメッセージの推定値です。 f n {\displaystyle f_{n}} 長さのブロックのエンコード関数です 。 n {\displaystyle n} p ( y | x ) = p Y | X ( y | x ) {\displaystyle p(y|x)=p_{Y|X}(y|x)} は条件付き確率分布 でモデル化されたノイズのあるチャネルであり 、 g n {\displaystyle g_{n}} は長さ のブロックのデコード関数です 。 n {\displaystyle n} と を 確率変数としてモデル化する。さらに、 を与えられたの 条件付き確率分布 関数 とする。これは通信路に固有の固定された性質である。すると、 周辺分布 の選択は、 恒等式により 結合分布を 完全に決定する。 X {\displaystyle X} Y {\displaystyle Y} p Y | X ( y | x ) {\displaystyle p_{Y|X}(y|x)} Y {\displaystyle Y} X {\displaystyle X} p X ( x ) {\displaystyle p_{X}(x)} p X , Y ( x , y ) {\displaystyle p_{X,Y}(x,y)}
p X , Y ( x , y ) = p Y | X ( y | x ) p X ( x ) {\displaystyle \ p_{X,Y}(x,y)=p_{Y|X}(y|x)\,p_{X}(x)} これにより 相互情報量 が誘導される。 通信路容量 は次のように定義される
。 I ( X ; Y ) {\displaystyle I(X;Y)}
C = sup p X ( x ) I ( X ; Y ) {\displaystyle \ C=\sup _{p_{X}(x)}I(X;Y)\,} ここで、 の 最高値 は、 のすべての可能な選択肢に対して取られます 。 p X ( x ) {\displaystyle p_{X}(x)}
チャネル容量の加法性 チャネル容量は独立チャネルごとに加算される。 [4] これは、2つの独立チャネルを組み合わせて使用しても、それらを独立して使用した場合と同じ理論容量が得られることを意味する。より正式には、 2 つの独立チャネルを上記のようにモデル化し、 入力アルファベット と出力アルファベットを持つものとする 。 についても同様である 。積チャネルを次 のように
定義する。 p 1 {\displaystyle p_{1}} p 2 {\displaystyle p_{2}} p 1 {\displaystyle p_{1}} X 1 {\displaystyle {\mathcal {X}}_{1}} Y 1 {\displaystyle {\mathcal {Y}}_{1}} p 2 {\displaystyle p_{2}} p 1 × p 2 {\displaystyle p_{1}\times p_{2}} ∀ ( x 1 , x 2 ) ∈ ( X 1 , X 2 ) , ( y 1 , y 2 ) ∈ ( Y 1 , Y 2 ) , ( p 1 × p 2 ) ( ( y 1 , y 2 ) | ( x 1 , x 2 ) ) = p 1 ( y 1 | x 1 ) p 2 ( y 2 | x 2 ) {\displaystyle \forall (x_{1},x_{2})\in ({\mathcal {X}}_{1},{\mathcal {X}}_{2}),\;(y_{1},y_{2})\in ({\mathcal {Y}}_{1},{\mathcal {Y}}_{2}),\;(p_{1}\times p_{2})((y_{1},y_{2})|(x_{1},x_{2}))=p_{1}(y_{1}|x_{1})p_{2}(y_{2}|x_{2})}
この定理は次のように述べています。 C ( p 1 × p 2 ) = C ( p 1 ) + C ( p 2 ) {\displaystyle C(p_{1}\times p_{2})=C(p_{1})+C(p_{2})}
証拠 まず、 であることを示します 。 C ( p 1 × p 2 ) ≥ C ( p 1 ) + C ( p 2 ) {\displaystyle C(p_{1}\times p_{2})\geq C(p_{1})+C(p_{2})}
と を 2つの独立した確率変数とする。 をチャネル を通した の出力に対応する確率変数とし 、 を を通した に対応する確率変数とする 。 X 1 {\displaystyle X_{1}} X 2 {\displaystyle X_{2}} Y 1 {\displaystyle Y_{1}} X 1 {\displaystyle X_{1}} p 1 {\displaystyle p_{1}} Y 2 {\displaystyle Y_{2}} X 2 {\displaystyle X_{2}} p 2 {\displaystyle p_{2}}
定義によります 。 C ( p 1 × p 2 ) = sup p X 1 , X 2 ( I ( X 1 , X 2 : Y 1 , Y 2 ) ) {\displaystyle C(p_{1}\times p_{2})=\sup _{p_{X_{1},X_{2}}}(I(X_{1},X_{2}:Y_{1},Y_{2}))}
と は独立であり、 と も 同様である ため 、 は とは 独立です。 相互情報量 の次の性質を適用できます 。 X 1 {\displaystyle X_{1}} X 2 {\displaystyle X_{2}} p 1 {\displaystyle p_{1}} p 2 {\displaystyle p_{2}} ( X 1 , Y 1 ) {\displaystyle (X_{1},Y_{1})} ( X 2 , Y 2 ) {\displaystyle (X_{2},Y_{2})} I ( X 1 , X 2 : Y 1 , Y 2 ) = I ( X 1 : Y 1 ) + I ( X 2 : Y 2 ) {\displaystyle I(X_{1},X_{2}:Y_{1},Y_{2})=I(X_{1}:Y_{1})+I(X_{2}:Y_{2})}
今のところ、 となる 分布を見つけるだけで十分です 。実際、 および、 および を実現する および の 2つの確率分布が あれば十分です。 p X 1 , X 2 {\displaystyle p_{X_{1},X_{2}}} I ( X 1 , X 2 : Y 1 , Y 2 ) ≥ I ( X 1 : Y 1 ) + I ( X 2 : Y 2 ) {\displaystyle I(X_{1},X_{2}:Y_{1},Y_{2})\geq I(X_{1}:Y_{1})+I(X_{2}:Y_{2})} π 1 {\displaystyle \pi _{1}} π 2 {\displaystyle \pi _{2}} X 1 {\displaystyle X_{1}} X 2 {\displaystyle X_{2}} C ( p 1 ) {\displaystyle C(p_{1})} C ( p 2 ) {\displaystyle C(p_{2})}
C ( p 1 × p 2 ) ≥ I ( X 1 , X 2 : Y 1 , Y 2 ) = I ( X 1 : Y 1 ) + I ( X 2 : Y 2 ) = C ( p 1 ) + C ( p 2 ) {\displaystyle C(p_{1}\times p_{2})\geq I(X_{1},X_{2}:Y_{1},Y_{2})=I(X_{1}:Y_{1})+I(X_{2}:Y_{2})=C(p_{1})+C(p_{2})} すなわち。 C ( p 1 × p 2 ) ≥ C ( p 1 ) + C ( p 2 ) {\displaystyle C(p_{1}\times p_{2})\geq C(p_{1})+C(p_{2})}
それでは、次のことを示しましょう 。 C ( p 1 × p 2 ) ≤ C ( p 1 ) + C ( p 2 ) {\displaystyle C(p_{1}\times p_{2})\leq C(p_{1})+C(p_{2})}
をチャネル の分布 と 定義し 、対応する出力とし ます 。 を のアルファベット 、を とします 。 同様に とです。 π 12 {\displaystyle \pi _{12}} p 1 × p 2 {\displaystyle p_{1}\times p_{2}} ( X 1 , X 2 ) {\displaystyle (X_{1},X_{2})} ( Y 1 , Y 2 ) {\displaystyle (Y_{1},Y_{2})} X 1 {\displaystyle {\mathcal {X}}_{1}} X 1 {\displaystyle X_{1}} Y 1 {\displaystyle {\mathcal {Y}}_{1}} Y 1 {\displaystyle Y_{1}} X 2 {\displaystyle {\mathcal {X}}_{2}} Y 2 {\displaystyle {\mathcal {Y}}_{2}}
相互情報量の定義によれば、
I ( X 1 , X 2 : Y 1 , Y 2 ) = H ( Y 1 , Y 2 ) − H ( Y 1 , Y 2 | X 1 , X 2 ) ≤ H ( Y 1 ) + H ( Y 2 ) − H ( Y 1 , Y 2 | X 1 , X 2 ) {\displaystyle {\begin{aligned}I(X_{1},X_{2}:Y_{1},Y_{2})&=H(Y_{1},Y_{2})-H(Y_{1},Y_{2}|X_{1},X_{2})\\&\leq H(Y_{1})+H(Y_{2})-H(Y_{1},Y_{2}|X_{1},X_{2})\end{aligned}}}
エントロピー の最後の項を書き直してみましょう 。
H ( Y 1 , Y 2 | X 1 , X 2 ) = ∑ ( x 1 , x 2 ) ∈ X 1 × X 2 P ( X 1 , X 2 = x 1 , x 2 ) H ( Y 1 , Y 2 | X 1 , X 2 = x 1 , x 2 ) {\displaystyle H(Y_{1},Y_{2}|X_{1},X_{2})=\sum _{(x_{1},x_{2})\in {\mathcal {X}}_{1}\times {\mathcal {X}}_{2}}\mathbb {P} (X_{1},X_{2}=x_{1},x_{2})H(Y_{1},Y_{2}|X_{1},X_{2}=x_{1},x_{2})}
積チャネルの定義により、 。与えられたペア に対して 、次のように書き直すことができます 。 P ( Y 1 , Y 2 = y 1 , y 2 | X 1 , X 2 = x 1 , x 2 ) = P ( Y 1 = y 1 | X 1 = x 1 ) P ( Y 2 = y 2 | X 2 = x 2 ) {\displaystyle \mathbb {P} (Y_{1},Y_{2}=y_{1},y_{2}|X_{1},X_{2}=x_{1},x_{2})=\mathbb {P} (Y_{1}=y_{1}|X_{1}=x_{1})\mathbb {P} (Y_{2}=y_{2}|X_{2}=x_{2})} ( x 1 , x 2 ) {\displaystyle (x_{1},x_{2})} H ( Y 1 , Y 2 | X 1 , X 2 = x 1 , x 2 ) {\displaystyle H(Y_{1},Y_{2}|X_{1},X_{2}=x_{1},x_{2})}
H ( Y 1 , Y 2 | X 1 , X 2 = x 1 , x 2 ) = ∑ ( y 1 , y 2 ) ∈ Y 1 × Y 2 P ( Y 1 , Y 2 = y 1 , y 2 | X 1 , X 2 = x 1 , x 2 ) log ( P ( Y 1 , Y 2 = y 1 , y 2 | X 1 , X 2 = x 1 , x 2 ) ) = ∑ ( y 1 , y 2 ) ∈ Y 1 × Y 2 P ( Y 1 , Y 2 = y 1 , y 2 | X 1 , X 2 = x 1 , x 2 ) [ log ( P ( Y 1 = y 1 | X 1 = x 1 ) ) + log ( P ( Y 2 = y 2 | X 2 = x 2 ) ) ] = H ( Y 1 | X 1 = x 1 ) + H ( Y 2 | X 2 = x 2 ) {\displaystyle {\begin{aligned}H(Y_{1},Y_{2}|X_{1},X_{2}=x_{1},x_{2})&=\sum _{(y_{1},y_{2})\in {\mathcal {Y}}_{1}\times {\mathcal {Y}}_{2}}\mathbb {P} (Y_{1},Y_{2}=y_{1},y_{2}|X_{1},X_{2}=x_{1},x_{2})\log(\mathbb {P} (Y_{1},Y_{2}=y_{1},y_{2}|X_{1},X_{2}=x_{1},x_{2}))\\&=\sum _{(y_{1},y_{2})\in {\mathcal {Y}}_{1}\times {\mathcal {Y}}_{2}}\mathbb {P} (Y_{1},Y_{2}=y_{1},y_{2}|X_{1},X_{2}=x_{1},x_{2})[\log(\mathbb {P} (Y_{1}=y_{1}|X_{1}=x_{1}))+\log(\mathbb {P} (Y_{2}=y_{2}|X_{2}=x_{2}))]\\&=H(Y_{1}|X_{1}=x_{1})+H(Y_{2}|X_{2}=x_{2})\end{aligned}}}
この等式を すべてにわたって合計すると が得られます 。 ( x 1 , x 2 ) {\displaystyle (x_{1},x_{2})} H ( Y 1 , Y 2 | X 1 , X 2 ) = H ( Y 1 | X 1 ) + H ( Y 2 | X 2 ) {\displaystyle H(Y_{1},Y_{2}|X_{1},X_{2})=H(Y_{1}|X_{1})+H(Y_{2}|X_{2})}
相互情報量の上限を与えることができます。
I ( X 1 , X 2 : Y 1 , Y 2 ) ≤ H ( Y 1 ) + H ( Y 2 ) − H ( Y 1 | X 1 ) − H ( Y 2 | X 2 ) = I ( X 1 : Y 1 ) + I ( X 2 : Y 2 ) {\displaystyle {\begin{aligned}I(X_{1},X_{2}:Y_{1},Y_{2})&\leq H(Y_{1})+H(Y_{2})-H(Y_{1}|X_{1})-H(Y_{2}|X_{2})\\&=I(X_{1}:Y_{1})+I(X_{2}:Y_{2})\end{aligned}}}
この関係は最高値でも維持される。したがって
C ( p 1 × p 2 ) ≤ C ( p 1 ) + C ( p 2 ) {\displaystyle C(p_{1}\times p_{2})\leq C(p_{1})+C(p_{2})} 証明した2つの不等式を組み合わせると、定理の結果が得られます。
C ( p 1 × p 2 ) = C ( p 1 ) + C ( p 2 ) {\displaystyle C(p_{1}\times p_{2})=C(p_{1})+C(p_{2})}
グラフのシャノン容量 Gが 無向グラフ である 場合 、グラフの頂点をシンボルとする通信路を定義するために用いることができ、2つの符号語は、それぞれの位置におけるシンボルが等しいか隣接している場合、互いに混同される可能性がある。このような通信路のシャノン容量を求める計算量は未知数であるが、別の重要なグラフ不変量である ロヴァース数 によって上限が定められる。 [5]
ノイズチャネル符号化定理 雑音 下通信路符号化定理は 、誤り確率 ε > 0 かつ 通信路容量 C未満の伝送 速度 Rに対して、十分に大きなブロック長に対して、誤り確率が ε 未満となるような、伝送速度 R でデータを伝送する符号化・復号化方式が存在することを述べています 。また、通信路容量を超える伝送速度の場合、ブロック長が無限大になるほど、受信側での誤り確率は0.5に減少します。
アプリケーション例 チャネル容量の概念を B Hzの 帯域幅 と 信号対雑音比 S/Nを持つ 加法性白色ガウス雑音 （AWGN）チャネルに適用したものが シャノン・ハートレーの定理 である 。
C = B log 2 ( 1 + S N ) {\displaystyle C=B\log _{2}\left(1+{\frac {S}{N}}\right)\ } Cは、 対数を 2を底とする 場合には ビット/秒、 自然対数 を用いる場合には ナット /秒 で測定されます（ B は ヘルツ単位 ）。信号電力 S とノイズ電力 N は、線形 電力単位 （ワットやボルト 2など）で表されます。S /N比は dB で表されることが多い ため 、変換が必要になる場合があります。例えば、信号対雑音比30dBは線形電力比に相当します 。 10 30 / 10 = 10 3 = 1000 {\displaystyle 10^{30/10}=10^{3}=1000}
チャネル容量の推定 チャネル容量を決定するには、容量達成分布を見つけ 、 相互情報量 を評価する必要があります。研究は主に、特定の電力制約とノイズ分布の下での加法性ノイズチャネルの研究に焦点を当ててきました。これは、他のほとんどのシナリオでは解析的な手法が実行不可能であるためです。そのため、 文献では
、入力サポートの調査 [6] 、緩和 [7] 、容量の上限 [8]などの代替アプローチが提案されています。 p X ( x ) {\displaystyle p_{X}(x)} I ( X ; Y ) {\displaystyle I(X;Y)}
離散無記憶通信路の容量は、 Blahut-Arimoto アルゴリズム を使用して計算できます。
深層学習は チャネル容量の推定に用いることができる。実際、任意の離散時間連続無記憶ベクトルチャネルのチャネル容量と容量達成分布は、 生成的敵対ネットワーク に着想を得た協調フレームワークであるCORTICAL [9] を用いて得ることができる。CORTICALは2つの協調ネットワークから構成される。1つは容量達成入力分布からサンプルを採取することを学習する生成器であり、もう1つはペアになっているチャネルとペアになっていないチャネルの入出力サンプルと推定値を区別することを学習する識別器である 。 I ( X ; Y ) {\displaystyle I(X;Y)}
無線通信におけるチャネル容量 このセクション [10] では、単一アンテナのポイントツーポイントシナリオに焦点を当てています。複数アンテナシステムにおけるチャネル容量については、 MIMO に関する記事を参照してください。
帯域制限AWGNチャネル 電力制限領域と帯域幅制限領域におけるAWGNチャネル容量。ここで、 B と C は 他の値に比例してスケーリングできます。 P ¯ N 0 = 1 {\displaystyle {\frac {\bar {P}}{N_{0}}}=1} 平均受信電力が [W]、総帯域幅が ヘルツ、雑音 電力スペクトル密度 が [W/Hz]の場合、AWGNチャネル容量は P ¯ {\displaystyle {\bar {P}}} W {\displaystyle W} N 0 {\displaystyle N_{0}}
C AWGN = W log 2 ( 1 + P ¯ N 0 W ) {\displaystyle C_{\text{AWGN}}=W\log _{2}\left(1+{\frac {\bar {P}}{N_{0}W}}\right)} [ビット/秒], ここで 、受信信号対雑音比（SNR）である。この結果は シャノン・ハートレーの定理 として知られている。 [11] P ¯ N 0 W {\displaystyle {\frac {\bar {P}}{N_{0}W}}}
SNRが大きい場合（SNR ≫ 0 dB）、容量は 電力に対して対数的、帯域幅に対してほぼ線形的になります。これは 帯域幅制限領域 と呼ばれます。 C ≈ W log 2 P ¯ N 0 W {\displaystyle C\approx W\log _{2}{\frac {\bar {P}}{N_{0}W}}}
SNRが小さい場合（SNR ≪ 0 dB）、容量は 電力に対して線形ですが、帯域幅には依存しません。これは 電力制限領域 と呼ばれます。 C ≈ P ¯ N 0 ln 2 {\displaystyle C\approx {\frac {\bar {P}}{N_{0}\ln 2}}}
帯域幅制限方式と電力制限方式を図に示します。
周波数選択性AWGNチャネル 周波数選択 チャネルの容量 は、いわゆる ウォーターフィリング 電力割り当てによって与えられ、
C N c = ∑ n = 0 N c − 1 log 2 ( 1 + P n ∗ | h ¯ n | 2 N 0 ) , {\displaystyle C_{N_{c}}=\sum _{n=0}^{N_{c}-1}\log _{2}\left(1+{\frac {P_{n}^{*}|{\bar {h}}_{n}|^{2}}{N_{0}}}\right),} ここで 、 はサブチャネル のゲインであり 、 は 電力制約を満たすように選択されます。 P n ∗ = max { ( 1 λ − N 0 | h ¯ n | 2 ) , 0 } {\displaystyle P_{n}^{*}=\max \left\{\left({\frac {1}{\lambda }}-{\frac {N_{0}}{|{\bar {h}}_{n}|^{2}}}\right),0\right\}} | h ¯ n | 2 {\displaystyle |{\bar {h}}_{n}|^{2}} n {\displaystyle n} λ {\displaystyle \lambda }
低速フェージングチャネル コヒーレンス時間が遅延要件よりも大きい 低速フェージングチャネル では、チャネルがサポートする信頼性の高い通信の最大速度 は、送信機には未知 のランダムチャネルゲイン に依存するため 、明確な容量は存在しません。送信機が [ビット/秒/Hz]の速度でデータを符号化する場合、復号誤り確率を任意に小さくすることができない確率がゼロではありません。 log 2 ( 1 + | h | 2 S N R ) {\displaystyle \log _{2}(1+|h|^{2}SNR)} | h | 2 {\displaystyle |h|^{2}} R {\displaystyle R}
p o u t = P ( log ( 1 + | h | 2 S N R ) < R ) {\displaystyle p_{out}=\mathbb {P} (\log(1+|h|^{2}SNR)<R)} 、 この場合、システムはアウトテージ状態にあると言われます。チャネルがディープフェード状態にある確率がゼロでない場合、厳密にはスローフェージングチャネルの容量はゼロです。しかし、 アウトテージ確率が 未満となるような の最大値を決定することは可能です 。この値は -アウトテージ容量と呼ばれます 。 R {\displaystyle R} p o u t {\displaystyle p_{out}} ϵ {\displaystyle \epsilon } ϵ {\displaystyle \epsilon }
高速フェージングチャネル 高速フェージングチャネル では 、遅延要件がコヒーレンス時間よりも大きく、符号語長が多数のコヒーレンス期間にまたがるため、多数のコヒーレンス時間間隔にわたって符号化することにより、多数の独立したチャネルフェージングを平均化することができます。したがって、 [ビット/秒/Hz]の信頼性の高い通信速度を実現することが可能であり、この値を高速フェージングチャネルの容量と呼ぶことは意味があります。 E ( log 2 ( 1 + | h | 2 S N R ) ) {\displaystyle \mathbb {E} (\log _{2}(1+|h|^{2}SNR))}
フィードバック容量 フィードバック容量とは、受信側が送信側にチャネル出力をフィードバックする ポイントツーポイント 通信チャネルにおいて、単位時間あたりに確実に 情報 を伝送できる最大の速度です。フィードバックを組み込んだ通信システムの情報理論的分析は、フィードバックがない場合よりも複雑で困難です。おそらくこれが、 CEシャノンが 1973年にイスラエルのアシュケロンで開催されたIEEE国際情報理論シンポジウムで行った最初のシャノン講演のテーマとしてフィードバックを選んだ理由でしょう。
フィードバック容量は、 チャネル入力とチャネル出力間の 有向情報量の最大値によって特徴付けられる。ここで、最大化は、出力が与えられた場合の入力の因果的条件付けに関して行われる。 有向情報量は、1990年に James Massey [12] によって造語され 、フィードバック容量の上限であることが示された。メモリレスチャネルの場合、Shannon [13] は、フィードバックによって容量が増加することはなく、フィードバック容量は入力と出力間の 相互情報量 によって特徴付けられるチャネル容量と一致することを示した。フィードバック容量は、トラップドアチャネル [14] やイジングチャネル [15] などのいくつかの例に対してのみ、閉形式の表現として知られている。 [ 16]他のいくつかのチャネルでは、連続しない1の入力制約を持つバイナリ消去チャネル [17] などの定数サイズの最適化問題によって特徴付けられる。NOST チャネル [18]
通信システムの基本的な数学モデルは次のとおりです。
フィードバックによるコミュニケーション 各要素の正式な定義は次のとおりです (非フィードバック容量に関する唯一の違いはエンコーダの定義です)。
W {\displaystyle W} 送信されるメッセージはアルファベット順 です 。 W {\displaystyle {\mathcal {W}}} X {\displaystyle X} は、アルファベット 順に並べられたチャネル入力シンボル（シンボル のシーケンス ）です 。 X n {\displaystyle X^{n}} n {\displaystyle n} X {\displaystyle {\mathcal {X}}} Y {\displaystyle Y} は、アルファベット順に並べられた チャネル出力シンボル（シンボル のシーケンス）です 。 Y n {\displaystyle Y^{n}} n {\displaystyle n} Y {\displaystyle {\mathcal {Y}}} W ^ {\displaystyle {\hat {W}}} 送信されたメッセージの推定値です。 f i : W × Y i − 1 → X {\displaystyle f_{i}:{\mathcal {W}}\times {\mathcal {Y}}^{i-1}\to {\mathcal {X}}} は、長さ のブロックに対する、 時刻 でのエンコード関数です 。 i {\displaystyle i} n {\displaystyle n} p ( y i | x i , y i − 1 ) = p Y i | X i , Y i − 1 ( y i | x i , y i − 1 ) {\displaystyle p(y_{i}|x^{i},y^{i-1})=p_{Y_{i}|X^{i},Y^{i-1}}(y_{i}|x^{i},y^{i-1})} は時刻 におけるノイズのある通信路であり、 条件付き確率分布 によってモデル化される 。 i {\displaystyle i} w ^ : Y n → W {\displaystyle {\hat {w}}:{\mathcal {Y}}^{n}\to {\mathcal {W}}} は長さ のブロックのデコード関数です 。 n {\displaystyle n} つまり、各時点 に対して、 前の出力のフィードバックが存在し 、エンコーダは以前のすべての出力 にアクセスできます 。 コードとは、 の符号化と復号化のマッピングのペアであり 、一様分布します。 の誤り率の平均確率 が のときにゼロに近づくよう な コード列が存在する場合、 レートは 達成可能 と言われます 。 i {\displaystyle i} Y i − 1 {\displaystyle Y_{i-1}} Y i − 1 {\displaystyle Y^{i-1}} ( 2 n R , n ) {\displaystyle (2^{nR},n)} W = [ 1 , 2 , … , 2 n R ] {\displaystyle {\mathcal {W}}=[1,2,\dots ,2^{nR}]} W {\displaystyle W} R {\displaystyle R} ( 2 n R , n ) {\displaystyle (2^{nR},n)} P e ( n ) ≜ Pr ( W ^ ≠ W ) {\displaystyle P_{e}^{(n)}\triangleq \Pr({\hat {W}}\neq W)} n → ∞ {\displaystyle n\to \infty }
フィードバック 容量 は で表され 、達成可能なすべてのレートの最大値として定義されます。 C feedback {\displaystyle C_{\text{feedback}}}
フィードバック容量に関する主な結果 と を 確率変数としてモデル化する。因果条件付けは 与えられたチャネルを記述する。因果条件付き分布の選択は 、因果条件付けの連鎖律 [19] により 結合分布 を決定し 、それによって 有向情報 分布が誘導される。 X {\displaystyle X} Y {\displaystyle Y} P ( y n | | x n ) ≜ ∏ i = 1 n P ( y i | y i − 1 , x i ) {\displaystyle P(y^{n}||x^{n})\triangleq \prod _{i=1}^{n}P(y_{i}|y^{i-1},x^{i})} P ( x n | | y n − 1 ) ≜ ∏ i = 1 n P ( x i | x i − 1 , y i − 1 ) {\displaystyle P(x^{n}||y^{n-1})\triangleq \prod _{i=1}^{n}P(x_{i}|x^{i-1},y^{i-1})} p X n , Y n ( x n , y n ) {\displaystyle p_{X^{n},Y^{n}}(x^{n},y^{n})} P ( y n , x n ) = P ( y n | | x n ) P ( x n | | y n − 1 ) {\displaystyle P(y^{n},x^{n})=P(y^{n}||x^{n})P(x^{n}||y^{n-1})} I ( X N → Y N ) = E [ log P ( Y N | | X N ) P ( Y N ) ] {\displaystyle I(X^{N}\rightarrow Y^{N})=\mathbf {E} \left[\log {\frac {P(Y^{N}||X^{N})}{P(Y^{N})}}\right]}
フィードバック 容量 は次のように与えられる。
C feedback = lim n → ∞ 1 n sup P X n | | Y n − 1 I ( X n → Y n ) {\displaystyle \ C_{\text{feedback}}=\lim _{n\to \infty }{\frac {1}{n}}\sup _{P_{X^{n}||Y^{n-1}}}I(X^{n}\to Y^{n})\,} 、 ここで、 の 最高値 は、 のすべての可能な選択肢に対して取られます 。 P X n | | Y n − 1 ( x n | | y n − 1 ) {\displaystyle P_{X^{n}||Y^{n-1}}(x^{n}||y^{n-1})}
ガウスフィードバック容量 ガウスノイズが色付きの場合、チャネルはメモリを持ちます。例えば、 自己回帰モデルの ノイズ過程（ ここで はIID過程）における単純なケースを考えてみましょう。 z i = z i − 1 + w i {\displaystyle z_{i}=z_{i-1}+w_{i}} w i ∼ N ( 0 , 1 ) {\displaystyle w_{i}\sim N(0,1)}
解決手法 フィードバック容量は一般的なケースでは解決が困難です。 チャネルが離散的である場合、
制御理論や マルコフ決定過程に関連するいくつかの手法があります。
参照
高度なコミュニケーショントピック
外部リンク 「チャネルの伝送速度」、 数学百科事典 、 EMSプレス 、2001 [1994] チャネル入力にさまざまな制約があるAWGNチャネル容量（インタラクティブなデモンストレーション）
参考文献 ^ Saleem Bhatti. 「チャネル容量」。 修士課程データ通信ネットワークと分散システムD51「基礎通信とネットワーク」の講義ノート 。2007年8月21日時点のオリジナルよりアーカイブ。 ^ ジム・レサーフ「信号はノイズのように見える！」 情報と測定、第2版 。 ^ Thomas M. Cover, Joy A. Thomas (2006). 情報理論の要素. John Wiley & Sons, New York. ISBN 9781118585771 。 ^ Cover, Thomas M.; Thomas, Joy A. (2006). 「第7章 チャネル容量」. 『情報理論の要素 』 （第2版）. Wiley-Interscience. pp. 206– 207. ISBN 978-0-471-24195-9 。 ^ Lovász、László (1979)、「グラフのシャノン容量について」、 IEEE 情報理論トランザクション 、IT-25 (1): 1–7 、 doi :10.1109/tit.1979.1055985 。 ^ スミス、ジョエル・G. (1971). 「振幅と分散に制約されたスカラーガウス通信路の情報容量」 . 情報制御 . 18 (3): 203– 219. doi :10.1016/S0019-9958(71)90346-9. ^ Huang, J.; Meyn, SP (2005). 「チャネル符号化における最適分布の特性評価と計算」. IEEE Transactions on Information Theory . 51 (7): 2336– 2351. doi :10.1109/TIT.2005.850108. ISSN 0018-9448. S2CID 2560689. ^ McKellips, AL (2004). 「ピーク制限離散時間通信路の容量に関する単純かつ厳密な境界」. 国際情報理論シンポジウム, 2004. ISIT 2004. Proceedings . IEEE. p. 348. doi :10.1109/ISIT.2004.1365385. ISBN 978-0-7803-8280-0 . S2CID 41462226。 ^ Letizia, Nunzio A.; Tonello, Andrea M.; Poor, H. Vincent (2023). 「協調チャネル容量学習」. IEEE Communications Letters . 27 (8): 1984– 1988. arXiv : 2305.13493 . doi :10.1109/LCOMM.2023.3282307. ISSN 1089-7798. ^ David Tse, Pramod Viswanath (2005), 『無線通信の基礎』, Cambridge University Press, UK, ISBN 9780521845274 ^ 電気工学ハンドブック. 研究教育協会. 1996年. D-149ページ. ISBN 9780878919819 。 ^ Massey, James (1990年11月). 「因果関係、フィードバック、そして指向性情報」 (PDF) . Proc. 1990 Int. Symp. On Information Theory and Its Applications (ISITA-90), Waikiki, HI. : 303– 305. ^ シャノン、C.（1956年9月）「ノイズの多い通信路のゼロ誤り容量」 IEEE Transactions on Information Theory . 2 (3): 8– 19. doi :10.1109/TIT.1956.1056798. ^ Permuter, Haim; Cuff, Paul; Van Roy, Benjamin; Weissman, Tsachy (2008年7月). 「フィードバックを伴うトラップドアチャネルの容量」 (PDF) . IEEE Trans. Inf. Theory . 54 (7): 3150– 3165. arXiv : cs/0610047 . doi :10.1109/TIT.2008.924681. S2CID 1265. ^ Elishco, Ohad; Permuter, Haim (2014年9月). 「フィードバック付きイジング通信路の容量と符号化」. IEEE Transactions on Information Theory . 60 (9): 5138– 5149. arXiv : 1205.4674 . doi :10.1109/TIT.2014.2331951. S2CID 9761759. ^ Aharoni, Ziv; Sabag, Oron; Permuter, Haim H. (2022年9月). 「強化学習による大規模アルファベットを持つイジングチャネルのフィードバック容量」. IEEE Transactions on Information Theory . 68 (9): 5637– 5656. doi :10.1109/TIT.2022.3168729. S2CID 248306743. ^ Sabag, Oron; Permuter, Haim H.; Kashyap, Navin (2016). 「非連続1入力制約を持つバイナリ消去通信路のフィードバック容量」 IEEE Transactions on Information Theory . 62 (1): 8– 22. doi :10.1109/TIT.2015.2495239. ^ シェムエル, エリ; サバグ, オロン; パーミューター, ハイム H. (2022). 「ノイズ出力のフィードバック容量は状態（NOST）チャネルである」. IEEE Transactions on Information Theory . 68 (8): 5044– 5059. arXiv : 2107.07164 . doi :10.1109/TIT.2022.3165538. ^ Permuter, Haim Henry; Weissman, Tsachy; Goldsmith, Andrea J. (2009年2月). 「時間不変の決定論的フィードバックを備えた有限状態チャネル」. IEEE Transactions on Information Theory . 55 (2): 644– 662. arXiv : cs/0608070 . doi :10.1109/TIT.2008.2009849. S2CID 13178.
![{\displaystyle {\xrightarrow[{\text{メッセージ}}]{W}}{\begin{array}{|c|}\hline {\text{エンコーダ}}\\f_{n}\\\hline \end{array}}{\xrightarrow[{\mathrm {エンコードされた \atop シーケンス} }]{X^{n}}}{\begin{array}{|c|}\hline {\text{チャネル}}\\p(y|x)\\\hline \end{array}}{\xrightarrow[{\mathrm {受信された \atop シーケンス} }]{Y^{n}}}{\begin{array}{|c|}\hline {\text{デコーダー}}\\g_{n}\\\hline \end{array}}{\xrightarrow[{\mathrm {推定された \atop メッセージ} }]{\hat {W}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/39d63076666d80bf3b6140eadf87155187e371a2 "チャネルモデル")
![{\displaystyle {\begin{aligned}H(Y_{1},Y_{2}|X_{1},X_{2}=x_{1},x_{2})&=\sum _{(y_{1},y_{2})\in {\mathcal {Y}}_{1}\times {\mathcal {Y}}_{2}}\mathbb {P} (Y_{1},Y_{2}=y_{1},y_{2}|X_{1},X_{2}=x_{1},x_{2})\log(\mathbb {P} (Y_{1},Y_{2}=y_{1},y_{2}|X_{1},X_{2}=x_{1},x_{2}))\\&=\sum _{(y_{1},y_{2})\in {\mathcal {Y}}_{1}\times {\mathcal {Y}}_{2}}\mathbb {P} (Y_{1},Y_{2}=y_{1},y_{2}|X_{1},X_{2}=x_{1},x_{2})[\log(\mathbb {P} (Y_{1}=y_{1}|X_{1}=x_{1}))+\log(\mathbb {P} (Y_{2}=y_{2}|X_{2}=x_{2}))]\\&=H(Y_{1}|X_{1}=x_{1})+H(Y_{2}|X_{2}=x_{2})\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/733594496825a6d2bf9543f0df96fe19033e9c58)
![{\displaystyle {\mathcal {W}}=[1,2,\dots ,2^{nR}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8165bbe91b46c99cc81c985199b5716f42fecb48)
![{\displaystyle I(X^{N}\rightarrow Y^{N})=\mathbf {E} \left[\log {\frac {P(Y^{N}||X^{N})}{P(Y^{N})}}\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a80fd8f7886755bdf075cf0837f6649b3f1c526a)
