任意に変化するチャネル

AVCの容量は、特定のパラメータによって変化する可能性があります。

${\displaystyle \textstyle R}$が決定論的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 }$そして$\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}$はAVCの容量を表し、${\displaystyle \textstyle c}$。

ご覧のとおり、唯一有用な状況は、AVC の容量が以下よりも大きい場合です。${\displaystyle \textstyle 0}$なぜなら、そうすればチャネルは保証された量のデータを送信できるからである。${\displaystyle \textstyle \leq c}$エラーなしで。そこで、次の定理から始めます。${\displaystyle \textstyle c}$AVCでは正であり、後述の定理によって範囲が絞り込まれる。${\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}}}$は、​${\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}}}$。

定理１：${\displaystyle \textstyle c>0}$AVCが対称でない場合のみ。${\displaystyle \textstyle c>0}$、 それから${\displaystyle \displaystyle c=\max _{P}I(P)}$。

対称性に関する第１部の証明：もし私たちが証明できるならば${\displaystyle \textstyle I(P)}$AVCが対称でない場合、は正であり、次に証明する。${\displaystyle \textstyle c=\max _{P}I(P)}$そうすれば、定理1を証明できるだろう。${\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)}$

これで確率分布が得られました${\displaystyle \textstyle Y_{r}}$それは独立している${\displaystyle \textstyle X_{r}}$したがって、対称AVCの定義は次のように書き換えることができます。 ${\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)}$先に計算したように、AVCは確かに対称です。${\displaystyle \textstyle I(P)}$に等しい${\displaystyle \textstyle 0}$。 したがって、${\displaystyle \textstyle I(P)}$AVCが対称でない場合にのみ正の値をとることができます。

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

次の定理では、入力制約および／または状態制約を持つ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 }$州による制限。

仮定する${\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)}$（1つの変数について）${\displaystyle \textstyle x_{i}}$入力制約の有用性は正式には説明されていません。${\displaystyle \textstyle \Gamma }$状態制約${\displaystyle \textstyle \Lambda }$これらの式に基づいて計算されます。

入力制約および/または状態制約のある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 }$最大レートは依然としてAVCの容量とみなされ、現在は次のように表されます。${\displaystyle \textstyle c(\Gamma ,\Lambda )}$。

補題 1: 任意のコードは次のようになります。${\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に存在する。

定理2：正の${\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 }$、そして与えられたAVC。

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

次の定理は、ランダム化コードを用いた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 )}$と非常によく似ている${\displaystyle \textstyle I(P)}$前述の方程式${\displaystyle \displaystyle I(P,\zeta )=\min _{Y_{r}}I(X_{r}\land Y_{r})}$しかし、pmfは${\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の証明：完全な証明については、下記に参照されている論文「ランダム符号化における特定のチャネルクラスの容量」を参照してください。