Удаление канала

Канал связи, где биты могут быть потеряны без предупреждения.

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

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

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

Пусть — вероятность удаления, . Двоичный канал удаления iid определяется следующим образом: ${\displaystyle p}$ ${\displaystyle 0<p<1}$

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

Емкость

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

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

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

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

Ссылки

1. Митценмахер, Майкл (2009), «Обзор результатов для каналов удаления и связанных каналов синхронизации», Probability Surveys , 6 : 1–33, doi : 10.1214/08-PS141 , MR  2525669.
2. Канория, Яшодхан; Монтанари, Андреа (2013), «Оптимальное кодирование для двоичного канала удаления с малой вероятностью удаления», IEEE Transactions on Information Theory , 59 (10): 6192–6219, doi :10.1109/TIT.2013.2262020, MR  3106824.

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

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