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

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

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

Определение

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

${displaystyle {egin{aligned}operatorname {Pr} [Y=0|X=0]&=1operatorname {Pr} [Y=0|X=1]&=poperatorname {Pr} [Y=1|X=0]&=0operatorname {Pr} [Y=1|X=1]&=1-pend{aligned}}}$

Емкость

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

${displaystyle {mathsf {cap}}(mathbb {Z} )={mathsf {H}}left({frac {1}{1+2^{{mathsf {s}}(p)}}}ight)-{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)}ight)}$

куда ${displaystyle {mathsf {s}}(p)={frac {{mathsf {H}}(p)}{1-p}}}$ для бинарная функция энтропии ${displaystyle {mathsf {H}}(cdot )}$.

Эта емкость получается, когда входная переменная Икс имеет Распределение Бернулли с вероятностью ${displaystyle alpha }$ имеющий значение 1 и ${displaystyle 1-alpha }$ значения 0, где:

${displaystyle alpha ={frac {1}{(1-p)(1+2^{{mathsf {H}}(p)/(1-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}}(Ymid X)}=max _{alpha }{Bigl {}{mathsf {H}}(Y)-sum _{xin {0,1}}{mathsf {H}}(Ymid X=x){mathsf {Prob}}{X=x}{Bigr }}}$ ${displaystyle =max _{alpha }{{mathsf {H}}((1-alpha )(1-p))-{mathsf {H}}(Ymid X=1){mathsf {Prob}}{X=1}}}$ ${displaystyle =max _{alpha }{{mathsf {H}}((1-alpha )(1-p))-(1-alpha ){mathsf {H}}(p)},}$ Чтобы найти максимум, мы дифференцируем ${displaystyle {frac {d}{dalpha }}{mathsf {cap}}(mathbb {Z} )=-(1-p)log _{2}left({frac {1-(1-alpha )(1-p)}{(1-alpha )(1-p)}}ight)+{mathsf {H}}(p)}$ И мы видим, что максимум достигается за ${displaystyle alpha =1-{frac {1}{(1-p)(1+2^{{mathsf {H}}(p)/(1-p)})}},}$ что дает следующее значение ${displaystyle {mathsf {cap}}(mathbb {Z} )}$ как функция п ${displaystyle {mathsf {cap}}(mathbb {Z} )={mathsf {H}}left({frac {1}{1+2^{{mathsf {s}}(p)}}}ight)-{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)}ight);{ extrm {where}};{mathsf {s}}(p)={frac {{mathsf {H}}(p)}{1-p}}.}$

Для любого п, ${displaystyle alpha <0.5}$ (т.е. должно быть передано больше 0, чем 1), потому что передача 1 вносит шум. В качестве ${displaystyle pightarrow 1}$, предельное значение ${displaystyle alpha }$ является ${displaystyle {frac {1}{e}}}$.^[2]

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

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

${displaystyle {mathsf {d}}_{A}(mathbf {x} ,mathbf {y} ){stackrel {vartriangle }{=}}max left{{ig |}{imid x_{i}=0,y_{i}=1}{ig |},{ig |}{imid x_{i}=1,y_{i}=0}{ig |}ight}.}$

Определите сферу ${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}.}$

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

Варшамовский рубеж.За п≥1 и т≥1,

${displaystyle M(n,t)leq {frac {2^{n+1}}{sum _{j=0}^{t}{left({inom {lfloor n/2floor }{j}}+{inom {lceil n/2ceil }{j}}ight)}}}.}$

Постоянный вес^{[требуется разъяснение ]} привязанный к коду.За п> 2т ≥ 2, пусть последовательность B₀, B₁, ..., B_п-2т-1 быть определенным как

${displaystyle B_{0}=2,quad B_{i}=min _{0leq 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}.}$

Примечания

1. Маккей (2003), п. 148.
2. Маккей (2003), п. 159.

Рекомендации

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