任意に変化するチャネル

任意可変チャネル（AVC ）は、符号化理論で使用される通信チャネルモデルであり、Blackwell、Breiman、およびThomasianによって初めて導入されました。この特定のチャネルには、時間の経過とともに変化する未知のパラメータがあり、これらの変化は、コードワードの送信中に均一なパターンを持たない場合があります。このチャネルの使用は、確率行列を使用して記述できます。ここで、は入力アルファベット、は出力アルファベット、は、送信された入力が受信出力につながる、指定された状態セットでの確率です。セット内の状態は、時間単位ごとに任意に変化できます。このチャネルは、チャネルの性質全体が既知であるShannonの2値対称チャネル（BSC）の代替として、実際のネットワークチャネルの状況により現実的になるように開発されました。 ${\displaystyle \textstyle n}$ ${\displaystyle \textstyle W^{n}:X^{n}\times }$ ${\displaystyle \textstyle S^{n}\rightarrow Y^{n}}$ ${\displaystyle \textstyle X}$ ${\displaystyle \textstyle Y}$ ${\displaystyle \textstyle W^{n}(y|x,s)}$ ${\displaystyle \textstyle S}$ ${\displaystyle \textstyle x=(x_{1},\ldots ,x_{n})}$ ${\displaystyle \textstyle y=(y_{1},\ldots ,y_{n})}$ ${\displaystyle \textstyle s_{i}}$ ${\displaystyle \textstyle S}$ ${\displaystyle \textstyle i}$

能力と関連する証明

決定論的AVCの容量

AVC の容量は特定のパラメータに応じて異なります。

${\displaystyle \textstyle R}$ は、決定論的AVC符号で達成可能なレートであるとは、それが より大きい場合、および任意の正の、 、および非常に大きな長さのブロック符号が存在し、次の式を満たす場合です。および。ここでは における最大値であり、は状態シーケンス の平均エラー確率です。最大レートはAVCの容量を表し、 と表されます。 ${\displaystyle \textstyle 0}$ ${\displaystyle \textstyle \varepsilon }$ ${\displaystyle \textstyle \delta }$ ${\displaystyle \textstyle n}$ ${\displaystyle \textstyle n}$ ${\displaystyle \textstyle {\frac {1}{n}}\log N>R-\delta }$ ${\displaystyle \displaystyle \max _{s\in S^{n}}{\bar {e}}(s)\leq \varepsilon }$ ${\displaystyle \textstyle N}$ ${\displaystyle \textstyle Y}$ ${\displaystyle \textstyle {\bar {e}}(s)}$ ${\displaystyle \textstyle s}$ ${\displaystyle \textstyle R}$ ${\displaystyle \textstyle c}$

ご覧のとおり、 AVCの容量が より大きい場合にのみ有用な状況となります。なぜなら、その場合、チャネルは保証された量のデータをエラーなく送信できるからです。そこで、 AVCにおいて が正であるときを示す定理から始め、その後に議論する定理によって、さまざまな状況におけるの範囲を絞り込んでいきます。 ${\displaystyle \textstyle 0}$ ${\displaystyle \textstyle \leq c}$ ${\displaystyle \textstyle c}$ ${\displaystyle \textstyle c}$

定理 1 を述べる前に、いくつかの定義について説明する必要があります。

• AVC は、任意の に対して、、、がチャネル関数である場合に対称です。${\displaystyle \displaystyle \sum _{s\in S}W(y|x,s)U(s|x')=\sum _{s\in S}W(y|x',s)U(s|x)}$ ${\displaystyle \textstyle (x,x',y,s)}$ ${\displaystyle \textstyle x,x'\in X}$ ${\displaystyle \textstyle y\in Y}$ ${\displaystyle \textstyle U(s|x)}$ ${\displaystyle \textstyle U:X\rightarrow S}$
• ${\displaystyle \textstyle X_{r}}$ 、、およびはすべて、それぞれ、、およびセット内のランダム変数です。${\displaystyle \textstyle S_{r}}$ ${\displaystyle \textstyle Y_{r}}$ ${\displaystyle \textstyle X}$ ${\displaystyle \textstyle S}$ ${\displaystyle \textstyle Y}$
• ${\displaystyle \textstyle P_{X_{r}}(x)}$ は、ランダム変数 が に等しい確率に等しい。${\displaystyle \textstyle X_{r}}$ ${\displaystyle \textstyle x}$
• ${\displaystyle \textstyle P_{S_{r}}(s)}$ は、ランダム変数 が に等しい確率に等しい。${\displaystyle \textstyle S_{r}}$ ${\displaystyle \textstyle s}$
• ${\displaystyle \textstyle P_{X_{r}S_{r}Y_{r}}}$ は、、、の組み合わせた確率質量関数(pmf)です。 は正式には と定義されます。${\displaystyle \textstyle P_{X_{r}}(x)}$ ${\displaystyle \textstyle P_{S_{r}}(s)}$ ${\displaystyle \textstyle W(y|x,s)}$ ${\displaystyle \textstyle P_{X_{r}S_{r}Y_{r}}}$ ${\displaystyle \textstyle P_{X_{r}S_{r}Y_{r}}(x,s,y)=P_{X_{r}}(x)P_{S_{r}}(s)W(y|x,s)}$
• ${\displaystyle \textstyle H(X_{r})}$ は のエントロピーです。${\displaystyle \textstyle X_{r}}$
• ${\displaystyle \textstyle H(X_{r}|Y_{r})}$ 等しい可能性のあるすべての値に基づいて、特定の値になる平均確率に等しくなります。${\displaystyle \textstyle X_{r}}$ ${\displaystyle \textstyle Y_{r}}$
• ${\displaystyle \textstyle I(X_{r}\land Y_{r})}$ はとの相互情報量であり、 に等しい。${\displaystyle \textstyle X_{r}}$ ${\displaystyle \textstyle Y_{r}}$ ${\displaystyle \textstyle H(X_{r})-H(X_{r}|Y_{r})}$
• ${\displaystyle \displaystyle I(P)=\min _{Y_{r}}I(X_{r}\land Y_{r})}$ ここで、最小値は、、、が の形式で分布するすべてのランダム変数に対してになります。${\displaystyle \textstyle Y_{r}}$ ${\displaystyle \textstyle X_{r}}$ ${\displaystyle \textstyle S_{r}}$ ${\displaystyle \textstyle Y_{r}}$ ${\displaystyle \textstyle P_{X_{r}S_{r}Y_{r}}}$

定理1: AVCが対称でない場合、かつその場合に限ります。 の場合、 となります。 ${\displaystyle \textstyle c>0}$ ${\displaystyle \textstyle c>0}$ ${\displaystyle \displaystyle c=\max _{P}I(P)}$

対称性の第1部の証明： AVCが対称でない場合に が正であることを証明し、 が正であることを証明できれば、定理1を証明できます。が に等しいと仮定します。 の定義から、 と は、に対して独立した確率変数となります。これは、どちらの確率変数の エントロピーも、もう一方の確率変数の値に依存しないことを意味するためです。 という式を用いて（ を覚えておいて）、次の式を得ます。 ${\displaystyle \textstyle I(P)}$ ${\displaystyle \textstyle c=\max _{P}I(P)}$ ${\displaystyle \textstyle I(P)}$ ${\displaystyle \textstyle 0}$ ${\displaystyle \textstyle I(P)}$ ${\displaystyle \textstyle X_{r}}$ ${\displaystyle \textstyle Y_{r}}$ ${\displaystyle \textstyle S_{r}}$ ${\displaystyle \textstyle P_{X_{r}S_{r}Y_{r}}}$ ${\displaystyle \textstyle P_{X_{r}}=P}$

${\displaystyle \displaystyle P_{Y_{r}}(y)=\sum _{x\in X}\sum _{s\in S}P(x)P_{S_{r}}(s)W(y|x,s)}$

${\displaystyle \textstyle \equiv (}$ とは独立確率変数なので、${\displaystyle \textstyle X_{r}}$ ${\displaystyle \textstyle Y_{r}}$ ${\displaystyle \textstyle W(y|x,s)=W'(y|s)}$ ${\displaystyle \textstyle W')}$

${\displaystyle \displaystyle P_{Y_{r}}(y)=\sum _{x\in X}\sum _{s\in S}P(x)P_{S_{r}}(s)W'(y|s)}$

${\displaystyle \textstyle \equiv (}$ 今だけに依存しているから${\displaystyle \textstyle P(x)}$ ${\displaystyle \textstyle x}$ ${\displaystyle \textstyle )}$

${\displaystyle \displaystyle P_{Y_{r}}(y)=\sum _{s\in S}P_{S_{r}}(s)W'(y|s)\left[\sum _{x\in X}P(x)\right]}$

${\displaystyle \textstyle \equiv (}$ なぜなら${\displaystyle \displaystyle \sum _{x\in X}P(x)=1)}$

${\displaystyle \displaystyle P_{Y_{r}}(y)=\sum _{s\in S}P_{S_{r}}(s)W'(y|s)}$

これで、 に依存しない における確率分布が得られます。対称AVCの定義は次のように書き直すことができます。 と はどちらも に基づく関数であるため、とのみに基づく関数に置き換えられました。ご覧のとおり、両辺は先ほど計算した に等しいため、が に等しい場合、AVCは確かに対称です。したがって、 が正になるのは、AVCが対称でない場合のみです。 ${\displaystyle \textstyle Y_{r}}$ ${\displaystyle \textstyle X_{r}}$ ${\displaystyle \displaystyle \sum _{s\in S}W'(y|s)P_{S_{r}}(s)=\sum _{s\in S}W'(y|s)P_{S_{r}}(s)}$ ${\displaystyle \textstyle U(s|x)}$ ${\displaystyle \textstyle W(y|x,s)}$ ${\displaystyle \textstyle x}$ ${\displaystyle \textstyle s}$ ${\displaystyle \textstyle y}$ ${\displaystyle \textstyle P_{Y_{r}}(y)}$ ${\displaystyle \textstyle I(P)}$ ${\displaystyle \textstyle 0}$ ${\displaystyle \textstyle I(P)}$

容量の第 2 部の証明: 完全な証明については、以下で参照されている論文「任意に変化するチャネルの容量の再考: 正値、制約」を参照してください。

入力と状態の制約を持つAVCの容量

次の定理は、入力制約および／または状態制約を持つAVCの容量について扱います。これらの制約は、AVCにおける伝送とエラーの可能性の非常に大きな範囲を縮小するのに役立ち、AVCの挙動を理解しやすくなります。

定理2に進む前に、いくつかの定義と補題を定義する必要があります。

このような AVC には次のものが存在します。

-およびという式に基づく入力制約。${\displaystyle \textstyle \Gamma }$ ${\displaystyle \displaystyle g(x)={\frac {1}{n}}\sum _{i=1}^{n}g(x_{i})}$ ${\displaystyle \textstyle x\in X}$ ${\displaystyle \textstyle x=(x_{1},\dots ,x_{n})}$

- 状態制約、式 （および）に基づく。${\displaystyle \textstyle \Lambda }$ ${\displaystyle \displaystyle l(s)={\frac {1}{n}}\sum _{i=1}^{n}l(s_{i})}$ ${\displaystyle \textstyle s\in X}$ ${\displaystyle \textstyle s=(s_{1},\dots ,s_{n})}$

-${\displaystyle \displaystyle \Lambda _{0}(P)=\min \sum _{x\in X,s\in S}P(x)l(s)}$

-は前述の方程式と非常によく似ていますが、方程式内の任意の状態またはは状態制約に従う必要があります。${\displaystyle \textstyle I(P,\Lambda )}$ ${\displaystyle \textstyle I(P)}$ ${\displaystyle \displaystyle I(P,\Lambda )=\min _{Y_{r}}I(X_{r}\land Y_{r})}$ ${\displaystyle \textstyle s}$ ${\displaystyle \textstyle S_{r}}$ ${\displaystyle \textstyle l(s)\leq \Lambda }$

は上の与えられた非負値関数であり、は 上の与えられた非負値関数であり、両方の最小値は であると仮定します。この主題に関して私が読んだ文献では、と（1つの変数 、に対して）の正確な定義は正式には示されていません。入力制約と状態制約の有用性は、これらの式に基づいています。 ${\displaystyle \textstyle g(x)}$ ${\displaystyle \textstyle X}$ ${\displaystyle \textstyle l(s)}$ ${\displaystyle \textstyle S}$ ${\displaystyle \textstyle 0}$ ${\displaystyle \textstyle g(x)}$ ${\displaystyle \textstyle l(s)}$ ${\displaystyle \textstyle x_{i}}$ ${\displaystyle \textstyle \Gamma }$ ${\displaystyle \textstyle \Lambda }$

入力制約および／または状態制約を持つAVCの場合、レートは を満たす形式のコードワードに制限され、状態はを満たすすべての状態に制限されます。最大レートは引き続きAVCの容量とみなされ、 と表記されます。 ${\displaystyle \textstyle R}$ ${\displaystyle \textstyle x_{1},\dots ,x_{N}}$ ${\displaystyle \textstyle g(x_{i})\leq \Gamma }$ ${\displaystyle \textstyle s}$ ${\displaystyle \textstyle l(s)\leq \Lambda }$ ${\displaystyle \textstyle c(\Gamma ,\Lambda )}$

補題1： がより大きいコードは「良い」コードとはみなされません。なぜなら、そのようなコードは最大平均誤り確率が （はの最大値）以上になるからです。これは良い最大平均誤り確率とは言えません。なぜなら、 はかなり大きくに近く、式の他の部分は の2乗でより大きくなるように設定されているため非常に小さくなるからです。したがって、誤りのないコードワードを受信する可能性は非常に低くなります。これが、定理2に条件が存在する理由です。 ${\displaystyle \textstyle \Lambda }$ ${\displaystyle \textstyle \Lambda _{0}(P)}$ ${\displaystyle \textstyle {\frac {N-1}{2N}}-{\frac {1}{n}}{\frac {l_{max}^{2}}{n(\Lambda -\Lambda _{0}(P))^{2}}}}$ ${\displaystyle \textstyle l_{max}}$ ${\displaystyle \textstyle l(s)}$ ${\displaystyle \textstyle {\frac {N-1}{2N}}}$ ${\displaystyle \textstyle {\frac {1}{2}}}$ ${\displaystyle \textstyle (\Lambda -\Lambda _{0}(P))}$ ${\displaystyle \textstyle \Lambda }$ ${\displaystyle \textstyle \Lambda _{0}(P)}$ ${\displaystyle \textstyle \Lambda _{0}(P)}$

定理 2:任意のブロック長に対して、任意に小さい、、、が与えられ、条件およびを伴う任意の型に対して、 、および の場合、型 のコードワードを持つコードが存在し、これは次の式を満たします: 、、、および 。ただし、正であり、、、および指定された AVC のみに依存します。 ${\displaystyle \textstyle \Lambda }$ ${\displaystyle \textstyle \alpha >0}$ ${\displaystyle \textstyle \beta >0}$ ${\displaystyle \textstyle \delta >0}$ ${\displaystyle \textstyle n\geq n_{0}}$ ${\displaystyle \textstyle P}$ ${\displaystyle \textstyle \Lambda _{0}(P)\geq \Lambda +\alpha }$ ${\displaystyle \displaystyle \min _{x\in X}P(x)\geq \beta }$ ${\displaystyle \textstyle P_{X_{r}}=P}$ ${\displaystyle \textstyle x_{1},\dots ,x_{N}}$ ${\displaystyle \textstyle P}$ ${\displaystyle \textstyle {\frac {1}{n}}\log N>I(P,\Lambda )-\delta }$ ${\displaystyle \displaystyle \max _{l(s)\leq \Lambda }{\bar {e}}(s)\leq \exp(-n\gamma )}$ ${\displaystyle \textstyle n_{0}}$ ${\displaystyle \textstyle \gamma }$ ${\displaystyle \textstyle \alpha }$ ${\displaystyle \textstyle \beta }$ ${\displaystyle \textstyle \delta }$

定理 2 の証明: 完全な証明については、下記の論文「任意に変化するチャネルの容量の再考: 正値、制約」を参照してください。

ランダム化AVCの容量

次の定理は、ランダム化 コードを持つAVCに関するものです。このようなAVCでは、コードは長さnのブロックコード族の値を持つランダム変数であり、これらのコードはコードワードの実際の値に依存/依拠することはできません。これらのコードは、そのランダム性のため、どのチャネルでも同じ最大および平均誤り確率を持ちます。これらのタイプのコードは、AVCの特定の特性をより明確にするのにも役立ちます。

定理 3 に進む前に、まずいくつかの重要な用語を定義する必要があります。

${\displaystyle \displaystyle W_{\zeta }(y|x)=\sum _{s\in S}W(y|x,s)P_{S_{r}}(s)}$
${\displaystyle \textstyle I(P,\zeta )}$ は、前述の方程式と非常によく似ていますが、ここでは方程式にpmfが追加され、 の最小値がの新しい形式に基づきます。 ここで、 は に置き換えられます。${\displaystyle \textstyle I(P)}$ ${\displaystyle \displaystyle I(P,\zeta )=\min _{Y_{r}}I(X_{r}\land Y_{r})}$ ${\displaystyle \textstyle P_{S_{r}}(s)}$ ${\displaystyle \textstyle I(P,\zeta )}$ ${\displaystyle \textstyle P_{X_{r}S_{r}Y_{r}}}$ ${\displaystyle \textstyle W_{\zeta }(y|x)}$ ${\displaystyle \textstyle W(y|x,s)}$

定理3: AVCのランダム化コードの容量はです。 ${\displaystyle \displaystyle c=max_{P}I(P,\zeta )}$

定理 3 の証明: 完全な証明については、下記の論文「ランダム コーディングにおける特定のチャネル クラスの容量」を参照してください。

参照

• バイナリ対称チャネル
• バイナリ消去チャネル
• Zチャネル（情報理論）
• チャネルモデル
• 情報理論
• 符号理論

参考文献

• アールスウェーデ、ルドルフ、ブリノフスキー、ウラジミール、「古典-量子任意可変チャネルの古典容量」、https://ieeexplore.ieee.org/document/4069128
• ブラックウェル、デイビッド、ブレイマン、レオ、トーマス、AJ、「ランダムコーディングにおける特定のチャネルクラスの容量」、https://www.jstor.org/stable/2237566
• Csiszar, I. および Narayan, P.、「制約された入力と状態を持つ任意に変化するチャネル」、https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=2598&isnumber=154
• Csiszar, I. および Narayan, P.、「任意に変化するチャネルのクラスの容量と復号規則」、https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=32153&isnumber=139
• Csiszar, I. および Narayan, P.、「任意に変化するチャネルの容量の再考：正値性、制約」、https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=2627&isnumber=155
• Lapidoth, A. および Narayan, P.、「チャネルの不確実性下における信頼性の高い通信」、https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=720535&isnumber=15554