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

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

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

Определение

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

${\displaystyle {\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 составляет , достигается при равномерном распределении (т.е. половина входов должна быть 0, а половина - 1). ^[2] ${\displaystyle 1-P_{e}}$ ${\displaystyle X}$

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

Похожие каналы

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

История

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

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

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

Примечания

1. Маккей (2003), стр. 148.
2. MacKay (2003), стр. 158.
3. Кавер и Томас (1991), стр. 189.
4. Кавер и Томас (1991), стр. 187.
5. Маккей (2003), стр. 15.
6. Митценмахер (2009), стр. 2.

Ссылки

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