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

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

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

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

Формула

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

Схема Две ветви поляризации

Синяя верхняя кривая — первый битовый канал, красная нижняя — второй. Диагональ показывает исходную вероятность.

Обозначения

$ε$: вероятность стирания в каждом исходном канале, доля
$ε₋$: вероятность стирания первого битового канала, доля
$ε₊$: вероятность стирания второго битового канала при известном первом бите, доля

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

Оба физических использования описываются одинаковыми двоичными каналами с видимой меткой стирания. Стирания независимы, а подмен битов нет. Передаётся пара (u₁⊕u₂, u₂). Второй синтезированный канал определён для декодера, которому известно истинное u₁.

Ограничения

Вероятность ε₊ описывает потерю информации о втором бите при известном первом. Ошибка при фактическом декодировании u₁ может повлиять на решение по u₂. При коррелированных потерях произведение ε² заменяется совместной вероятностью двух стираний. Для канала с подменой битов эти выражения неприменимы.

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

Чтобы узнать первый бит u₁ без сведений о u₂, нужны оба выхода: u₁=(u₁⊕u₂)⊕u₂. Если сохранился только один выход, он либо сообщает u₂, либо сообщает сумму по модулю два. Каждому значению первого бита всё ещё соответствует возможное значение второго.

Если оба канала пропускают свои биты, первый бит известен. Это происходит с вероятностью (1−ε)². Следовательно, его стирание происходит с вероятностью 1−(1−ε)²=2ε−ε². На графике эта ветвь лежит выше диагонали при 0<ε<1.

При восстановлении второго бита истинное значение первого уже известно по определению второго битового канала. Если получен u₂, вычисления не нужны. Если сохранилась только сумма u₁⊕u₂, из неё и u₁ можно восстановить u₂. Лишь двойное стирание лишает декодер обеих возможностей, поэтому вероятность равна ε².

Среднее арифметическое двух вероятностей остаётся равным ε. Через формулу ёмкости это означает, что сумма ёмкостей сохраняется. При повторении преобразования часть битовых позиций становится всё надёжнее. Именно различия между позициями позволяют выделять места для информационных битов и фиксировать значения на других позициях.

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

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

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

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

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

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

Схема объединения и расщепления битовых каналов, из которой получаются две вероятности, предложена Эрдалом Арыканом. Равенства здесь относятся к частному случаю независимых каналов со стиранием, разобранному в его работе о полярных кодах.

Пример

В двух независимых использованиях двоичного канала вероятность стирания символа равна 0,3. Найдём вероятности стирания двух битовых каналов после одного шага поляризации. Первый бит доступен только при двух успешных приёмах. Поэтому ε₋=1−0,7²=0,51. Второй бит при известном первом теряется только при двух стираниях. Получаем ε₊=0,3²=0,09. Проверка: (0,51+0,09)/2=0,30. Обе величины являются безразмерными вероятностями и соответствуют 51 % и 9 %. Средняя вероятность сохранилась, хотя первый битовый канал стал менее надёжным, а второй более надёжным.

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

Менять ветви местами. Первому биту нужны два выхода, второму при известном первом достаточно одного. Подставлять вероятность сохранения бита вместо ε. Тогда кривые показывают другие величины и теряют смысл. Считать события независимыми при общей причине потерь. При пакетном стирании обоих символов вероятность совместной потери может быть существенно выше произведения.

Практика

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

Симметричная исходная точка

Условие. У исходного канала ε=0,5. Найдите обе новые вероятности стирания.

Решение. Первый канал: 1−(1−0,5)²=0,75. Второй канал: 0,5²=0,25. Среднее равно 0,5.

Ответ. ε₋=0,75 и ε₊=0,25.

Ёмкости после одного шага

Условие. Вероятность стирания исходного канала равна 0,2. Найдите сумму ёмкостей двух новых каналов.

Решение. Вероятности стирания равны 1−0,8²=0,36 и 0,2²=0,04. Ёмкости равны 0,64 и 0,96 бита на использование. Их сумма равна 1,60 бита за пару использований.

Ответ. Суммарная ёмкость составляет 1,60 бита за пару использований.

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

https://arxiv.org/pdf/0807.3917
https://mathvoices.ams.org/featurecolumn/2020/06/01/fc-2020-06/

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

Информатика

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

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

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

Информатика

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

$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|Y)\le h_2(P_e)+P_e\log_2(|\mathcal X|-1)$

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