Канал двоичного стирания

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

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

Определение [ править ]

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

Вместимость [ править ]

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

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

По симметрии входных значений оптимальное входное распределение составляет . Емкость канала составляет:${\displaystyle X\sim \mathrm {Bernoulli} \left({\frac {1}{2}}\right)}$ ${\displaystyle \operatorname {I} (X;Y)=\operatorname {H} (X)-\operatorname {H} (X|Y)}$ Обратите внимание, что для двоичной функции энтропии (которая имеет значение 1 для входа ),${\displaystyle \operatorname {H} _{\text{b}}}$${\displaystyle {\frac {1}{2}}}$ ${\displaystyle \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}}$ как известно из (и равно) y, если только , что имеет вероятность .${\displaystyle X}$${\displaystyle y=e}$${\displaystyle P_{e}}$ По определению так${\displaystyle \operatorname {H} (X)=\operatorname {H} _{\text{b}}\left({\frac {1}{2}}\right)=1}$ ${\displaystyle \operatorname {I} (X;Y)=1-P_{e}}$.

Если отправитель получает уведомление о стирании бита, он может многократно передавать каждый бит до тех пор, пока он не будет получен правильно, достигнув необходимой емкости . Однако по теореме кодирования канала с шумом пропускная способность может быть получена даже без такой обратной связи. ^[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 году в качестве игрушечного примера. ^{[ необходима цитата ]}

См. Также [ править ]

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

Примечания [ править ]

Ссылки [ править ]

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