Канал удаления - Deletion channel

А канал удаления это канал связи модель, используемая в теория кодирования и теория информации. В этой модели передатчик посылает немного (ноль или единица), а получатель либо принимает бит (с вероятностью ${ displaystyle p}$ ) или ничего не получает без уведомления о том, что бит был сброшен (с вероятностью ${ displaystyle 1-p}$ ). Определение вместимость канала удаления - открытая проблема.^[1]^[2]

Канал удаления не следует путать с канал двоичного стирания который гораздо проще анализировать.

Формальное описание

Позволять ${ displaystyle p}$ вероятность удаления, ${ displaystyle 0$ . В iid Канал двоичного удаления определяется следующим образом:

Учитывая входную последовательность ${ displaystyle n}$ биты ${ displaystyle (X_ {i})}$ в качестве входа каждый бит в ${ displaystyle X_ {n}}$ можно удалить с вероятностью ${ displaystyle p}$ . Позиции удаления неизвестны отправителю и получателю. Выходная последовательность ${ displaystyle (Y_ {i})}$ это последовательность ${ displaystyle (X_ {i})}$ которые не были удалены, в правильном порядке и без ошибок.

Вместимость

Нерешенная проблема в информатике:

Какова емкость канала удаления?

(больше нерешенных проблем в информатике)

В вместимость двоичного канала удаления (как аналитическое выражение скорости удаления ${ displaystyle p}$ ) неизвестно. Оно имеет математическое выражение^{[нужна цитата ]}. Известно несколько верхних и нижних границ.

внешние ссылки

Реализация исправления для канала удаления

использованная литература

^ Митценмахер, Майкл (2009), «Обзор результатов для каналов удаления и связанных каналов синхронизации», Вероятностные исследования, 6: 1–33, Дои:10.1214 / 08-ПС141, Г-Н 2525669.
^ Канория, Яшодхан; Монтанари, Андреа (2013), "Оптимальное кодирование для двоичного канала удаления с малой вероятностью удаления", IEEE Transactions по теории информации, 59 (10): 6192–6219, Дои:10.1109 / TIT.2013.2262020, Г-Н 3106824.

[1] Митценмахер, Майкл (2009), «Обзор результатов для каналов удаления и связанных каналов синхронизации», Вероятностные исследования, 6: 1–33, Дои:10.1214 / 08-ПС141, Г-Н 2525669.

[2] Канория, Яшодхан; Монтанари, Андреа (2013), "Оптимальное кодирование для двоичного канала удаления с малой вероятностью удаления", IEEE Transactions по теории информации, 59 (10): 6192–6219, Дои:10.1109 / TIT.2013.2262020, Г-Н 3106824.

[1]

[2]