В теории кодирования и теории информации канал двоичного стирания ( BEC ) является моделью канала связи . Передатчик отправляет бит (ноль или единицу), а приемник либо принимает бит правильно, либо с некоторой вероятностью получает сообщение о том, что бит не был получен («стерт»).
Определение
Канал двоичного стирания с вероятностью стирания — это канал с двоичным входом, троичным выходом и вероятностью стирания . То есть пусть будет переданная случайная величина с алфавитом . Пусть – полученная переменная с алфавитом , где – символ стирания. Тогда канал характеризуется условными вероятностями : [1]
Емкость
Пропускная способность канала BEC достигается при равномерном распределении (т. е. половина входов должна быть 0, а половина — 1). [2]
Если отправитель уведомлен о стирании бита, он может повторно передавать каждый бит до тех пор, пока он не будет правильно получен, достигнув емкости . Однако по теореме о кодировании зашумленного канала пропускную способность можно получить и без такой обратной связи. [3]
Связанные каналы
Если биты переворачиваются, а не стираются, канал представляет собой двоичный симметричный канал (BSC), пропускная способность которого (для функции двоичной энтропии ) меньше емкости BEC для . [4] [5] Если биты стираются, но получатель не уведомляется (т.е. не получает выходной сигнал ), то канал является каналом удаления , и его пропускная способность является открытой проблемой. [6]
История
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