Двоичный канал стирания

«Канал Erasure» перенаправляется сюда. Другой метод см. в разделе Канал стирания пакетов .

Модель канала для канала двоичного стирания, показывающая сопоставление входа канала X с выходом канала Y (с известным символом стирания ? ). Вероятность стирания равна $p_{e}$

В теории кодирования и теории информации канал двоичного стирания ( BEC ) является моделью канала связи . Передатчик отправляет бит (ноль или единицу), а приемник либо принимает бит правильно, либо с некоторой вероятностью. $P_{e}$ получает сообщение о том, что бит не получен («стерт»).

Определение

Двоичный канал стирания с вероятностью стирания $P_{e}$ это канал с двоичным входом, троичным выходом и вероятностью стирания $P_{e}$. То есть пусть $X$ быть переданной случайной величиной с алфавитом $\{0,1\}$. Позволять $Y$ быть полученной переменной с алфавитом $\{0,1,{\text{e}}\}$, где ${\text{e}}$ является символом стирания. Тогда канал характеризуется условными вероятностями :

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

Емкость

Пропускная способность канала BEC равна $1-P_{e}$, достигаемый при равномерном распределении для $X$ (т.е. половина входных данных должна быть 0, а половина — 1).

showДоказательство

By symmetry of the input values, the optimal input distribution is $X\sim \mathrm {Bernoulli} \left({\frac {1}{2}}\right)$. The channel capacity is: $\operatorname {I} (X;Y)=\operatorname {H} (X)-\operatorname {H} (X|Y)$ Observe that, for the binary entropy function $\operatorname {H} _{\text{b}}$ (which has value 1 for input ${\frac {1}{2}}$), $\operatorname {H} (X|Y)=\sum _{y}P(y)\operatorname {H} (X|y)=P_{e}\operatorname {H} _{\text{b}}\left({\frac {1}{2}}\right)=P_{e}$ as $X$ is known from (and equal to) y unless $y=e$, which has probability $P_{e}$. By definition $\operatorname {H} (X)=\operatorname {H} _{\text{b}}\left({\frac {1}{2}}\right)=1$, so $\operatorname {I} (X;Y)=1-P_{e}$.

Если отправитель уведомлен о стирании бита, он может повторно передавать каждый бит до тех пор, пока он не будет правильно получен, достигая пропускной способности. $1-P_{e}$. Однако по теореме о кодировании зашумленного канала пропускная способность $1-P_{e}$ можно получить даже без такой обратной связи.

Связанные каналы

Если биты переворачиваются, а не стираются, канал является двоичным симметричным каналом (BSC), пропускная способность которого $1-\operatorname {H} _{\text{b}}(P_{e})$ (для двоичной функции энтропии $\operatorname {H} _{\text{b}}$), что меньше емкости БЭК для $0<P_{e}<1/2$. Если биты стираются, но получатель не уведомляется (т. е. не получает выходной сигнал) $e$) то канал является каналом удаления , и его пропускная способность является открытой проблемой.

История

BEC был представлен Питером Элиасом из Массачусетского технологического института в 1955 году в качестве игрушечного примера.

См. также

• Код стирания
• Канал стирания пакетов

Ссылки

• Обложка, Томас М.; Томас, Джой А. (1991). Элементы теории информации . Хобокен, Нью-Джерси: Уайли. ISBN  978-0-471-24195-9 .
• Маккей, Дэвид Дж. К. (2003). Теория информации, вывод и алгоритмы обучения . Издательство Кембриджского университета. ISBN  0-521-64298-1 .
• Митценмахер, Майкл (2009), «Обзор результатов для каналов удаления и связанных с ними каналов синхронизации», Probability Surveys , 6 : 1–33, doi : 10.1214/08-PS141 , MR   2525669