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

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

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

Определение [ править ]

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

${\ displaystyle {\ begin {align} \ operatorname {Pr} [Y = 0 | X = 0] & = 1 \\\ operatorname {Pr} [Y = 0 | X = 1] & = p \\\ operatorname { Pr} [Y = 1 | X = 0] & = 0 \\\ имя оператора {Pr} [Y = 1 | X = 1] & = 1-p \ end {выровнено}}}$

Емкость [ править ]

Пропускная способность канала от Z-канала с кроссовером 1 → 0 вероятность р , когда входной случайная величина Х распределена в соответствии с распределением Бернулли с вероятностью для появления 0, задается следующим уравнением:${\ 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)}$

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

Расчет [2]

${\displaystyle {\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 \}}}$ ${\displaystyle =\max _{\alpha }\{{\mathsf {H}}((1-\alpha )(1-p))-{\mathsf {H}}(Y\mid X=1){\mathsf {Prob}}\{X=1\}\}}$ ${\displaystyle =\max _{\alpha }\{{\mathsf {H}}((1-\alpha )(1-p))-(1-\alpha ){\mathsf {H}}(p)\},}$ Чтобы найти максимум, мы дифференцируем ${\displaystyle {\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)}$ И мы видим, что максимум достигается за ${\displaystyle \alpha =1-{\frac {1}{(1-p)(1+2^{{\mathsf {H}}(p)/(1-p)})}},}$ давая следующее значение в зависимости от p${\displaystyle {\mathsf {cap}}(\mathbb {Z} )}$ ${\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)\;{\textrm {where}}\;{\mathsf {s}}(p)={\frac {{\mathsf {H}}(p)}{1-p}}.}$

Для любого р , (т.е. больше 0s должны быть переданы , чем 1s) , так как ПРЕПРОВОЖДАЮЩЕЕ 1 вносит шум. As , предельное значение равно . ^[2]${\displaystyle \alpha <0.5}$${\displaystyle p\rightarrow 1}$${\displaystyle \alpha }$${\displaystyle {\frac {1}{e}}}$

Ограничения на размер кода с исправлением асимметричных ошибок [ править ]

Определите следующую функцию расстояния для слов длины n, передаваемых по Z-каналу${\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\}.}$

Определите сферу радиуса t вокруг слова длины n как набор всех слов на расстоянии 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\}.}$

Код длины п называется т -asymmetric-коррекции ошибок , если для любых двух кодовых слов , один есть . Обозначим максимальное количество кодовых слов в t- асимметричном коде с исправлением ошибок длины n .${\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}.}$

Заметки [ править ]

Ссылки [ править ]

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