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

Модель канала для канала двоичного стирания, показывающая сопоставление входа канала 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. Маккей (2003), с. 158.
3. Обложка и Томас (1991), с. 189.
4. Обложка и Томас (1991), с. 187.
5. Маккей (2003), с. 15.
6. Митценмахер (2009), с. 2.

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

• Обложка, Томас М.; Томас, Джой А. (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