Канал двоичного стирания - Binary erasure channel

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

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

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

Определение

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

${displaystyle {egin{aligned}operatorname {Pr} [Y=0|X=0]&=1-P_{e}operatorname {Pr} [Y=0|X=1]&=0operatorname {Pr} [Y=1|X=0]&=0operatorname {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}}}$

Емкость

В пропускная способность канала БЭК ${displaystyle 1-P_{e}}$, достигнутая с равномерным распределением для ${displaystyle X}$ (т.е. половина входов должна быть 0, а половина - 1).^[2]

Доказательство[2]

Благодаря симметрии входных значений оптимальное входное распределение ${displaystyle Xsim mathrm {Bernoulli} left({frac {1}{2}}ight)}$. Емкость канала составляет: ${displaystyle operatorname {I} (X;Y)=operatorname {H} (X)-operatorname {H} (Y|X)}$ Обратите внимание, что для бинарная функция энтропии ${displaystyle operatorname {H} _{ ext{b}}}$ (который имеет значение 1 для ввода ${displaystyle {frac {1}{2}}}$), ${displaystyle operatorname {H} (Y|X)=sum _{y}P(y)operatorname {H} (X|y)=P_{e}operatorname {H} _{ ext{b}}left({frac {1}{2}}ight)=P_{e}}$ в качестве ${displaystyle X}$ известен из (и равен) y, если ${displaystyle y=e}$, имеющая вероятность ${displaystyle P_{e}}$. По определению ${displaystyle operatorname {H} (X)=operatorname {H} _{ ext{b}}left({frac {1}{2}}ight)=1}$, так ${displaystyle operatorname {I} (X;Y)=1-P_{e}}$.

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

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

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

История

BEC был представлен Питер Элиас Массачусетского технологического института в 1955 году в качестве игрушечного примера.^{[нужна цитата ]}

Смотрите также

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

Примечания

1. Маккей (2003), п. 148.
2. Маккей (2003), п. 158.
3. Обложка и Томас (1991), п. 189. Ошибка sfnp: цель отсутствует: CITEREFCoverThomas1991 (помощь)
4. Обложка и Томас (1991), п. 187. Ошибка sfnp: цель отсутствует: CITEREFCoverThomas1991 (помощь)
5. Маккей (2003), п. 15.
6. Митценмахер (2009), п. 2.

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

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