Zチャネル（情報理論）

符号理論と情報理論において、Z チャネルまたはバイナリ非対称チャネルは、一部のデータ ストレージ システムの動作をモデル化するために使用される 通信チャネルです。

Zチャネルは、バイナリ入力とバイナリ出力を持つチャネルであり、各0ビットは正しく送信されますが、各1ビットは0として誤って送信される確率pと、1として正しく送信される確率1- pを持ちます。言い換えると、XとYがそれぞれチャネルの入力と出力の確率分布を記述するランダム変数である場合、チャネルのクロスオーバーは条件付き確率によって特徴付けられます。^[1]

${\displaystyle {\begin{aligned}\operatorname {Pr} [Y=0|X=0]&=1\\\operatorname {Pr} [Y=0|X=1]&=p\\\operatorname {Pr} [Y=1|X=0]&=0\\\operatorname {Pr} [Y=1|X=1]&=1-p\end{aligned}}}$

入力ランダム変数X が0 の発生 確率を持つベルヌーイ分布に従って分布している場合、クロスオーバー 1 → 0 確率pを持つZ チャネルのチャネル容量は次の式で与えられます。 ${\displaystyle {\mathsf {cap}}(\mathbb {Z} )}$${\displaystyle \mathbb {Z} }$${\displaystyle \alpha}$

${\displaystyle {\mathsf {cap}}(\mathbb {Z} )={\mathsf {H}}\left({\frac {1}{1+2^{{\mathsf {s}}(p)}}}\right)-{\frac {{\mathsf {s}}(p)}{1+2^{{\mathsf {s}}(p)}}}=\log _{2}(1{+}2^{-{\mathsf {s}}(p)})=\log _{2}\left(1+(1-p)p^{p/(1-p)}\right)}$

ここで、バイナリエントロピー関数です。 ${\displaystyle {\mathsf {s}}(p)={\frac {{\mathsf {H}}(p)}{1-p}}}$ ${\displaystyle {\mathsf {H}}(\cdot )}$

この容量は、入力変数X が、値 0​​ と値 1 の確率を持つベルヌーイ分布に従う場合に得られます。 ${\displaystyle \alpha}$${\displaystyle 1-\alpha }$

${\displaystyle \alpha =1-{\frac {1}{(1-p)(1+2^{{\mathsf {H}}(p)/(1-p)})}},}$

pが小さい場合、容量は次のように近似される。

${\displaystyle {\mathsf {cap}}(\mathbb {Z} )\approx 1-0.5{\mathsf {H}}(p)}$

交差確率pを持つバイナリ対称チャネルの容量と比較します。 ${\displaystyle 1{-}{\mathsf {H}}(p)}$

任意のpに対して、（つまり、 1 よりも 0 を多く送信する必要があります） 1 を送信するとノイズが発生するためです。 であるため、 の極限値はです。^[2]${\displaystyle \alpha <0.5}$${\displaystyle p\rightarrow 1}$${\displaystyle \alpha }$${\displaystyle {\frac {1}{e}}}$

Zチャネルを介して送信される 長さnのワードに次の距離関数を定義する。${\displaystyle {\mathsf {d}}_{A}(\mathbf {x} ,\mathbf {y} )}$${\displaystyle \mathbf {x} ,\mathbf {y} \in \{0,1\}^{n}}$

${\displaystyle {\mathsf {d}}_{A}(\mathbf {x} ,\mathbf {y} ){\stackrel {\vartriangle }{=}}\max \left\{{\big |}\{i\mid x_{i}=0,y_{i}=1\}{\big |},{\big |}\{i\mid x_{i}=1,y_{i}=0\}{\big |}\right\}.}$

長さnの単語の周りの半径tの球面を、そこから距離t以内にあるすべての単語の集合として定義します。言い換えると、 ${\displaystyle V_{t}(\mathbf {x} )}$${\displaystyle \mathbf {x} \in \{0,1\}^{n}}$${\displaystyle \mathbf {x} }$

${\displaystyle V_{t}(\mathbf {x} )=\{\mathbf {y} \in \{0,1\}^{n}\mid {\mathsf {d}}_{A}(\mathbf {x} ,\mathbf {y} )\leq t\}.}$

長さnのコードは 、任意の 2 つのコードワードに対して が成り立つ場合、t非対称エラー訂正コードであると言われます。長さnのt非対称エラー訂正コードの最大コードワード数を で表します。 ${\displaystyle {\mathcal {C}}}$${\displaystyle \mathbf {c} \neq \mathbf {c} '\in \{0,1\}^{n}}$${\displaystyle V_{t}(\mathbf {c} )\cap V_{t}(\mathbf {c} ')=\emptyset }$${\displaystyle M(n,t)}$

ヴァルシャモフ境界。n ≥ 1 かつt ≥ 1の場合、

${\displaystyle M(n,t)\leq {\frac {2^{n+1}}{\sum _{j=0}^{t}{\left({\binom {\lfloor n/2\rfloor }{j}}+{\binom {\lceil n/2\rceil }{j}}\right)}}}.}$

定数重み^{[説明が必要]}コード境界。n > 2t ≥ 2の場合、シーケンスB ₀、B ₁、...、B _n-2t-1を次のように定義します。

${\displaystyle B_{0}=2,\quad B_{i}=\min _{0\leq j<i}\{B_{j}+A(n{+}t{+}i{-}j{-}1,2t{+}2,t{+}i)\}}$のために。${\displaystyle i>0}$

それから${\displaystyle M(n,t)\leq B_{n-2t-1}.}$

• MacKay, David JC (2003)。情報理論、推論、学習アルゴリズム。ケンブリッジ大学出版局。ISBN 0-521-64298-1。
• Kløve, T. (1981). 「非対称チャネルのエラー訂正コード」.技術レポート 18–09–07–81 . ノルウェー: ベルゲン大学情報学部.
• Verdú, S. (1997). 「チャネル容量 (73.5)」.電気工学ハンドブック(第 2 版). IEEE Press および CRC Press. pp.  1671– 1678.
• Tallini, LG; Al-Bassam, S.; Bose, B. (2002). Z チャネルの容量とコードについて。IEEE 国際情報理論シンポジウムの議事録。ローザンヌ、スイス。p. 422。