Информатика / Кодирование информации

Пропускная способность двоичного канала со стиранием

Пропускная способность двоичного канала со стиранием равна доле нестёртых символов. Она задаёт предельную скорость надёжной передачи в битах на одно использование канала.

Опубликовано: 5 ноября 2026 г.Обновлено: 5 ноября 2026 г.

Формула

C_{\mathrm{BEC}}=1-\varepsilon

Схема Ёмкость и вероятность стирания

Точка на прямой соответствует примеру при ε=0,25.

Обозначения

$C_BEC$: пропускная способность, бит на использование
$ε$: вероятность стирания каждого входного бита, доля от 0 до 1
X, Y: вход из множества {0, 1} и выход из множества {0, 1, ?}, символы

Условия применения

Двоичный входной символ либо принимается без изменения, либо заменяется специальной меткой. Вероятность стирания одинакова для нуля и единицы, а переходы при разных использованиях канала независимы при заданных входах. Входное распределение при расчёте ёмкости можно выбирать свободно.

Ограничения

Формула относится к асимптотической пропускной способности канала без памяти. Она не предсказывает вероятность ошибки для короткого блока. Если приёмник не знает, в каких позициях возникло искажение, или канал стирает нули и единицы с разной вероятностью, описанная модель переходов неприменима.

Подробное объяснение

Пусть на выходе канала виден знак вопроса, если бит стёрт. Этот знак отделяет два случая. Когда получено 0 или 1, исходный бит восстановлен однозначно. Когда видна метка стирания, оба исходных значения остаются возможными.

Если стирание одинаково вероятно для обоих входов, его наблюдение не меняет априорных вероятностей нуля и единицы. Поэтому при стирании неопределённость о входе равна его исходной энтропии H(X). При остальных выходах она равна нулю. Усреднение даёт H(X|Y)=εH(X).

Взаимная информация за одно использование равна H(X)−H(X|Y), то есть (1−ε)H(X). Двоичная энтропия достигает одного бита при равных вероятностях входных символов. Отсюда получается прямая на графике. Увеличение вероятности стирания на 0,1 уменьшает ёмкость на 0,1 бита на использование.

У реальной схемы с кодированием полезная скорость определяется числом информационных битов и числом отправленных символов, включая избыточные. Канальная теорема описывает возможность приблизиться к ёмкости с убывающей ошибкой при росте длины блока для скоростей строго ниже предела. Один короткий блок при той же скорости может потерять больше символов, чем средняя доля стираний.

Как пользоваться формулой

Проверьте, выдаёт ли приёмник отдельную метку для пропавшего символа и сохраняет ли его позицию в блоке.
Убедитесь, что вероятность стирания одинакова для нуля и единицы, а последовательные переходы описываются моделью без памяти.
Переведите вероятность стирания в долю единицы и вычтите её из единицы, чтобы получить предел в битах на использование.
Найдите фактическую скорость кода как отношение информационных битов к переданным символам и сравните её с пределом.

Историческая справка

В работе Клода Шеннона 1948 года задача связи с шумом была сформулирована через статистическую зависимость между отправленными и принятыми символами. Это дало способ отделить предел надёжной передачи от характеристик отдельного устройства или выбранного кода. Для модели со стиранием особенно наглядно видно, какая доля неопределённости остаётся после наблюдения канала.

В статье Эрдала Арыкана, вышедшей в IEEE Transactions on Information Theory в 2009 году, канал со стиранием служит примером поляризации. Два синтезированных канала в базовом шаге также описываются стираниями, но один имеет большую вероятность стирания, а другой меньшую. Это позволяет проследить перераспределение исходной ёмкости при построении полярных кодов.

Историческая линия формулы

Общий способ вычисления пропускной способности связан с теорией связи Шеннона. Равенство для двоичного канала со стиранием получается из неё для конкретной матрицы переходов. Работа Арыкана относится к последующему применению модели для построения кодов.

Пример

Приёмник получает двоичные символы без подмен, но для четверти позиций видит только специальную метку. Оценим предел для кода, отправляющего 800 символов на блок. Дано ε=0,25. Тогда C=1−0,25=0,75 бита на использование. Предельная скорость соответствует 800·0,75=600 информационным битам при таком числе отправленных символов. Если код несёт 560 информационных битов, его скорость равна 560/800=0,70 бита на использование и лежит ниже предела. Проверка единиц: число использований, умноженное на биты за использование, даёт биты. Число 600 выражает масштаб предела, а не гарантированное число восстановленных битов в конкретном блоке.

Частая ошибка

Считать стирание заменой бита на ноль. Ноль является допустимым входом, поэтому нужна отдельная метка, иначе изменится модель. Подставлять 25 вместо 0,25. Вероятность в формуле выражается долей единицы. Считать предельную скорость гарантией успешного декодирования каждого блока. Для конечной длины оцените вероятность ошибки отдельно, с учётом кода и правила декодирования.

Практика

Задачи с решением

Проверка скорости кода

Условие. Вероятность стирания равна 0,18. Код передаёт 144 информационных бита за 180 использований канала. Сравните скорость с ёмкостью.

Решение. C=1−0,18=0,82 бита на использование. R=144/180=0,80 бита на использование. Разность C−R=0,02 бита на использование.

Ответ. Скорость ниже предела на 0,02 бита на использование.

Допустимая вероятность стирания

Условие. Для скорости 0,65 бита на использование требуется строго положительный запас по ёмкости. Какое условие на ε надо выполнить?

Решение. Требование 1−ε>0,65 даёт ε<0,35. При ε=0,35 скорость равна пределу и запас равен нулю.

Ответ. Вероятность стирания должна быть меньше 35 %.

Дополнительные источники

https://www.nokia.com/bell-labs/publications-and-media/publications/a-mathematical-theory-of-communication/
https://ocw.mit.edu/courses/6-441-information-theory-spring-2010/8a41ad57fef4487df71ea164635e1248_MIT6_441S10_lec08.pdf
https://arxiv.org/abs/0807.3917

Связанные формулы

Информатика

Поляризация двоичного канала со стиранием

$\varepsilon_{-}=2\varepsilon-\varepsilon^2,\qquad \varepsilon_{+}=\varepsilon^2$

Один шаг поляризации преобразует два независимых двоичных канала со стиранием в два битовых канала с разной надёжностью. У одного вероятность стирания растёт, у другого падает.

Информатика

Ёмкость двоичного симметричного канала

$C=1-H_2(p),\quad H_2(p)=-p\log_2p-(1-p)\log_2(1-p)$

Ёмкость двоичного симметричного канала даёт не только вычислительную запись, но и правило, какие данные определяют результат и как проверить его численно. Формула применяется к строго указанной модели; ниже разобраны предпосылки, два решённых задания и границы корректной интерпретации.

Информатика

Взаимная информация двух дискретных величин

$I(X;Y)=\sum_{x,y}p(x,y)\log_2\frac{p(x,y)}{p(x)p(y)}$

Взаимная информация двух дискретных величин даёт не только вычислительную запись, но и правило, какие данные определяют результат и как проверить его численно. Формула применяется к строго указанной модели; ниже разобраны предпосылки, два решённых задания и границы корректной интерпретации.

Информатика

Энтропия Шеннона: средняя информация дискретного источника

$H(X)=-\sum_{i=1}^{m}p_i\log_2p_i$

Энтропия Шеннона измеряет среднюю неопределённость исхода по его вероятностям. При двоичном логарифме результат выражают в битах на символ; редкие и частые символы вносят разный вклад.

Информатика

Неравенство Фано: связь ошибки и условной энтропии

$H(X|Y)\le h_2(P_e)+P_e\log_2(|\mathcal X|-1)$

Неравенство Фано сверху оценивает условную энтропию дискретного X через вероятность ошибки декодера X-hat=g(Y). Оно формализует: если X почти удаётся восстановить из наблюдения Y, неопределённость H(X|Y) не может быть большой.