Z-канал (теория информации)

Z-канал всегда видит каждый 0 бит сообщения, переданного правильно, и каждый 1 бит, переданный правильно с вероятностью 1– p из-за шума в среде передачи.

В теории кодирования и теории информации Z -канал или двоичный асимметричный канал — это канал связи, используемый для моделирования поведения некоторых систем хранения данных.

Определение

Z-канал — это канал с двоичным входом и двоичным выходом, где каждый 0 бит передается правильно, но каждый 1 бит имеет вероятность p быть переданным неправильно как 0 и вероятность 1– p быть передано правильно как 1. Другими словами, если X и Y — случайные величины, описывающие распределения вероятностей входа и выхода канала соответственно, то пересечения канала характеризуются условными вероятностями :

${\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}}$

Емкость

канала Пропускная способность ${\mathsf {cap}}(\mathbb {Z} )$ Z-канала $\mathbb {Z}$ с вероятностью кроссовера 1 → 0 p , когда входная случайная величина X распределяется по распределению Бернулли с вероятностью $\alpha$ для появления 0 определяется следующим уравнением:

${\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)$

где ${\mathsf {s}}(p)={\frac {{\mathsf {H}}(p)}{1-p}}$ для двоичной функции энтропии ${\mathsf {H}}(\cdot )$.

Эта емкость получается, когда входная переменная X имеет распределение Бернулли с вероятностью $\alpha$ иметь значение 0 и $1-\alpha$ значения 1, где:

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

Для малых p емкость аппроксимируется выражением

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

по сравнению с емкостью $1{-}{\mathsf {H}}(p)$ двоичного симметричного канала с вероятностью пересечения p .

showРасчет

${\mathsf {cap}}(\mathbb {Z} )=\max _{\alpha }\{{\mathsf {H}}(Y)-{\mathsf {H}}(Y\mid X)\}=\max _{\alpha }{\Bigl \{}{\mathsf {H}}(Y)-\sum _{x\in \{0,1\}}{\mathsf {H}}(Y\mid X=x){\mathsf {Prob}}\{X=x\}{\Bigr \}}$ $=\max _{\alpha }\{{\mathsf {H}}((1-\alpha )(1-p))-{\mathsf {H}}(Y\mid X=1){\mathsf {Prob}}\{X=1\}\}$ $=\max _{\alpha }\{{\mathsf {H}}((1-\alpha )(1-p))-(1-\alpha ){\mathsf {H}}(p)\},$ To find the maximum we differentiate ${\frac {d}{d\alpha }}{\mathsf {cap}}(\mathbb {Z} )=-(1-p)\log _{2}\left({\frac {1-(1-\alpha )(1-p)}{(1-\alpha )(1-p)}}\right)+{\mathsf {H}}(p)$ And we see the maximum is attained for $\alpha =1-{\frac {1}{(1-p)(1+2^{{\mathsf {H}}(p)/(1-p)})}},$ yielding the following value of ${\mathsf {cap}}(\mathbb {Z} )$ as a function of p ${\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)\;{\textrm {where}}\;{\mathsf {s}}(p)={\frac {{\mathsf {H}}(p)}{1-p}}.$

Для любого р , $\alpha <0.5$ (т.е. следует передавать больше нулей, чем единиц), поскольку передача единицы вносит шум. Как $p\rightarrow 1$, предельное значение $\alpha$ является ${\frac {1}{e}}$.

Границы размера асимметричного кода, исправляющего ошибки

Определите следующую функцию расстояния ${\mathsf {d}}_{A}(\mathbf {x} ,\mathbf {y} )$ на словах $\mathbf {x} ,\mathbf {y} \in \{0,1\}^{n}$ длины n, передаваемый по Z-каналу

${\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\}.$

Определите сферу $V_{t}(\mathbf {x} )$ радиуса t вокруг слова $\mathbf {x} \in \{0,1\}^{n}$ длины n как набор всех слов, находящихся на расстоянии t или меньше от $\mathbf {x}$, другими словами,

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

Код ​ ${\mathcal {C}}$ длины n называется t -асимметричным корректирующим ошибки, если для любых двух кодовых слов $\mathbf {c} \neq \mathbf {c} '\in \{0,1\}^{n}$, у одного есть $V_{t}(\mathbf {c} )\cap V_{t}(\mathbf {c} ')=\emptyset$. Обозначим через $M(n,t)$ максимальное количество кодовых слов в t -асимметричном коде с исправлением ошибок длины n .

Варшамов на границе .Для n ≥1 и t ≥1,

$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 определяется как

$B_{0}=2,\quad B_{i}=\min _{0\leq j<i}\{B_{j}+A(n{+}t{+}i{-}j{-}1,2t{+}2,t{+}i)\}$ для $i>0$.

Затем $M(n,t)\leq B_{n-2t-1}.$

Ссылки

• Маккей, Дэвид Дж. К. (2003). Теория информации, вывод и алгоритмы обучения . Издательство Кембриджского университета. ISBN  0-521-64298-1 .
• Клёве, Т. (1981). «Коды, исправляющие ошибки для асимметричного канала». Технический отчет 18–09–07–81 . Норвегия: Департамент информатики Бергенского университета.
• Верду, С. (1997). «Пропускная способность канала (73,5)». Справочник по электротехнике (второе изд.). IEEE Press и CRC Press. стр. 1671–1678.
• Таллини, LG; Аль-Басам, С.; Бозе, Б. (2002). О емкости и кодах для Z-канала . Труды Международного симпозиума IEEE по теории информации. Лозанна, Швейцария. п. 422.