Все формулы РФ

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

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

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

Опубликовано: Обновлено:

Кодирование информацииСтраницы с задачами и решениямиЕсть историческая справкаДиагностика условий

Формула

$$C=1-H_2(p),\quad H_2(p)=-p\log_2p-(1-p)\log_2(1-p)$$
Схема Ёмкость двоичного симметричного канала
Ёмкость двоичного симметричного каналаЁмкость двоичного симметричного каналаC=1−H₂(p)000.1250.250.250.50.3750.750.51pбит/использ.

При ошибке 1/2 выход независим от входа и ёмкость равна нулю.

Обозначения

$x$
аргумент, состояние или вектор данных конкретной задачи, единицы исходной модели
$n,k,i,j$
целые индексы узла, шага либо компоненты, безразмерные
$ε / err$
допуск или оценка вычислительной ошибки, если она используется, единицы результата

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

Модель предполагает двоичный симметричный канал с независимым переворотом каждого бита с вероятностью p и равными стоимостями символов. При p=0 или 1 ёмкость равна 1, при p=1/2 — 0; для других каналов эту формулу переносить нельзя.

Ограничения

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

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

Двоичный симметричный канал меняет 0 на 1 и 1 на 0 с одной вероятностью p. При p=0 выход повторяет вход, а при p=1/2 выход статистически не связан с входом.

Двоичная энтропия H₂(p) измеряет неопределённость ошибки. Вычитание из одного бита показывает, какую долю идеальной передачи удаётся сохранить после оптимального кодирования в пределе длинных блоков.

Формула симметрична относительно p и 1−p: если p>1/2, можно инвертировать выходные биты и получить вероятность 1−p. Это полезная проверка, которую часто пропускают.

Ёмкость — не фактическая скорость любого протокола. Реальный код имеет конечную длину, задержку и требования к вероятности ошибки, поэтому рабочая скорость обычно ниже теоретического предела.

Для p=0,1: −0,1log₂0,1≈0,332193 и −0,9log₂0,9≈0,136803; сумма 0,468996. Вычитание из одного даёт 0,531004. При p=0,5 оба члена энтропии по 0,5 и пропускная способность действительно исчезает.

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

  1. Выпишите C=1-H_2(p),\quad H_2(p)=-p\log_2p-(1-p)\log_2(1-p) и отметьте искомую величину; не заменяйте её одноимённым параметром из другой модели.
  2. Подготовьте данные в требуемой форме: проверьте индексы, знак, область аргумента, нормировку либо размерность.
  3. Выполните первое задание по действиям и сохраните промежуточные значения каждого коэффициента, отношения или суммы.
  4. Проверьте результат естественным способом: симметрией, точным частным случаем, невязкой или исходным ограничением.
  5. Разберите второе задание: изменённые данные показывают границу применимости и предупреждают типичную ошибку метода.

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

Клод Шеннон в 1948 году сформулировал понятие пропускной способности как предельную скорость надёжной передачи при заданной модели канала. Двоичный симметричный канал стал каноническим примером: каждый бит независимо меняется с одинаковой вероятностью p. Формула C=1−H₂(p) демонстрирует разницу между просто наличием ошибок и фундаментальным пределом кодирования. Теорема не говорит, что любое короткое сообщение можно передать без ошибок: она утверждает существование длинных кодов при скоростях ниже ёмкости.

Формула следует из теоремы Шеннона о кодировании для канала, опубликованной в 1948 году в Bell System Technical Journal. Двоичный симметричный канал стал учебным примером, потому что его симметрия позволяет записать максимум взаимной информации через одну двоичную энтропию.

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

Формула ёмкости в этом контексте следует из работы Клода Шеннона 1948 года. Историческая атрибуция не отменяет условий модели: симметричность, независимые ошибки и асимптотически длинные блоки существенны для такого вывода. Источник в карточке указан для различения исторического имени, публикации и современной вычислительной формы; эти уровни не следует смешивать.

Пример

При вероятности ошибки p=0,1 энтропия H₂≈0,468996, поэтому C≈0,531004 бита на использование канала. При p=0 ёмкость равна 1, а при p=0,5 — 0. Для p=0,1: −0,1log₂0,1≈0,332193 и −0,9log₂0,9≈0,136803; сумма 0,468996. Вычитание из одного даёт 0,531004. При p=0,5 оба члена энтропии по 0,5 и пропускная способность действительно исчезает. Двоичный симметричный канал меняет 0 на 1 и 1 на 0 с одной вероятностью p. При p=0 выход повторяет вход, а при p=1/2 выход статистически не связан с входом. Двоичная энтропия H₂(p) измеряет неопределённость ошибки. Вычитание из одного бита показывает, какую долю идеальной передачи удаётся сохранить после оптимального кодирования в пределе длинных блоков.

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

Нельзя считать p=1 каналом нулевой ёмкости: инверсия выхода восстанавливает вход, и ёмкость равна одному. Нельзя заменять H₂(p) на p. Не следует путать бит на использование канала с битом в секунду. И нельзя применять выражение к несимметричному каналу без новой оптимизации входа. В разборе «Ёмкость двоичного симметричного канала» проверяют именно обозначения и условия данной записи.

Практика

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

Ёмкость при p=0,25

Условие. Вычислите ёмкость BSC при p=0,25.

Решение. H₂(0,25)=−0,25log₂0,25−0,75log₂0,75≈0,811278; C=1−H₂≈0,188722.

Ответ. C≈0,188722 бита.

Нулевая ёмкость при p=0,5

Условие. Проверьте p=0,5.

Решение. H₂(0,5)=−2·0,5log₂0,5=1, следовательно C=0.

Ответ. C=0.

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

  • https://onlinelibrary.wiley.com/doi/pdf/10.1002/j.1538-7305.1948.tb01338.x
  • https://ocw.mit.edu/courses/6-050j-information-and-entropy-spring-2008/80c7258fd6bc5780797975eabb6fd747_MIT6_050JS08_textbook.pdf

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

Информатика

Дивергенция Кульбака—Лейблера для дискретных распределений

$D_{KL}(P\|Q)=\sum_i p_i\log_2\frac{p_i}{q_i}$

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

Информатика

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

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

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

Информатика

Перекрёстная энтропия дискретного распределения

$H(P,Q)=-\sum_i p_i\log_2q_i$

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