# Теорема Шеннона о шуме: как передавать данные без ошибок при постоянной скорости?

Источник: https://www.youtube.com/watch?v=kWsJ_JDuFaI
Канал: MIT OpenCourseWare
Опубликовано: 17.12.2025

---

В лекции 18 курса MIT «Алгоритмический аспект теории информации» рассматривается одна из фундаментальных работ Клода Шеннона — вторая теорема Шеннона (теорема о кодировании для каналов с шумом). В отличие от сжатия данных, где целью является минимизация объема информации, здесь фокус смещается на надежность передачи данных в условиях помех.

## 📡 Проблема передачи данных через шумный канал
[[JUMP:00:11]]

Традиционно информация передается по каналам, которые подвержены внешним воздействиям. В цифровой среде простейшей моделью такого процесса является двоичный симметричный канал (BSC — binary symmetric channel) [00:52]. Его работа описывается параметром $P$ — вероятностью инверсии (флипа) каждого отдельного бита. С вероятностью $P$ бит меняется на противоположный (0 на 1 или наоборот), а с вероятностью $1-P$ проходит без изменений [01:18].

Ключевая сложность заключается в том, что получатель не знает, в каких именно позициях произошли ошибки. Если представить $P = 1/3$, то каждый третий бит сообщения в среднем будет ошибочным [01:43]. Задача теории кодирования состоит в том, чтобы найти такие методы избыточного кодирования, которые позволят восстановить исходное сообщение с высокой точностью.

## 🔁 Ограниченность кодов повторения
[[JUMP:03:09]]

Первым и наиболее очевидным решением проблемы ошибок являются коды повторения (repetition codes). Суть метода проста: каждый бит сообщения повторяется $t$ раз [03:22]. Например, вместо «1» передается «111...1», а вместо «0» — «000...0». Декодирование на приемной стороне происходит методом мажоритарного голосования (majority vote): если в блоке из $t$ полученных символов больше единиц, считается, что была передана единица [06:01].

Однако коды повторения крайне неэффективны с точки зрения скорости передачи (rate). Скорость кода определяется как отношение длины исходного сообщения $K$ к длине переданной последовательности $N$ [10:12]. По словам лектора:

*   При использовании кодов повторения для достижения вероятности ошибки, стремящейся к нулю, необходимо увеличивать число повторений пропорционально логарифму длины сообщения ($\log K$) [04:58].
*   Это приводит к тому, что при стремлении длины сообщения к бесконечности скорость передачи данных стремится к нулю [11:13].

Главный вопрос лекции: можно ли передавать информацию надежно (с исчезающе малой вероятностью ошибки), сохраняя при этом постоянную, не нулевую скорость передачи? [11:54].

## 🧪 Теорема Шеннона и понятие пропускной способности
[[JUMP:18:35]]

Клод Шеннон доказал поразительный результат: для любого шумного канала существует критическое значение, называемое пропускной способностью (capacity) [21:19]. 

Для двоичного симметричного канала пропускная способность вычисляется по формуле $1 - H(P)$, где $H(P)$ — функция двоичной энтропии [19:05]. Теорема Шеннона утверждает:

1.  Если скорость передачи $R$ меньше пропускной способности ($R < 1 - H(P)$), то существует схема кодирования, при которой вероятность ошибки стремится к нулю при увеличении длины блока [19:32].
2.  Если скорость $R$ превышает этот предел, вероятность ошибки неизбежно стремится к единице (надежная передача невозможна) [19:05].

Интуитивно это понятно на примере $P = 1/2$. В этом случае энтропия $H(1/2) = 1$, а пропускная способность $1 - 1 = 0$ [24:01]. Это логично: если канал инвертирует биты с вероятностью 50%, на выходе получается случайный шум, не несущий никакой информации об источнике [24:28].

## 🎲 Вероятностный метод: случайный код как решение
[[JUMP:26:44]]

Доказательство возможности надежной передачи при постоянной скорости базируется не на поиске конкретного «идеального» алгоритма, а на вероятностном методе. Лектор подчеркивает ироничность ситуации: «Чтобы доказать теорему, мы берем кодирование как случайную функцию — и это всё» [27:10].

Схема доказательства состоит в следующем:

*   Создается «кодовая книга» (code book), состоящая из случайных последовательностей для каждого возможного сообщения [28:18].
*   Для декодирования используется концепция «колец» (rings) вокруг кодовых слов. Кольцо — это множество всех векторов, находящихся на определенном расстоянии Хэмминга от исходного кода, соответствующем ожидаемому количеству ошибок $NP$ [30:08].
*   Ключевая лемма гласит: при $R < 1 - H(P)$ с высокой вероятностью принятый сигнал попадет в «кольцо» правильного кодового слова и не попадет ни в одно другое [33:48].

Лектор объясняет появление энтропии через комбинаторику: количество векторов в «кольце» описывается биномиальными коэффициентами, аппроксимация которых через формулу Стирлинга напрямую приводит к функции энтропии в экспоненте [41:03].

## 🛠 От теории к практике: линейные коды
[[JUMP:1:09:03]]

Несмотря на математическое изящество, метод случайного кодирования Шеннона неприменим на практике. Для кодовой книги со случайными значениями потребовалось бы экспоненциальное количество памяти для хранения всех пар «сообщение-код» [1:10:08].

В качестве решения этой проблемы анонсируются следующие темы курса:

*   **Линейные коды:** Вместо хранения всей книги используется матрица. Процесс кодирования превращается в умножение вектора сообщения на матрицу, что гораздо эффективнее [1:10:21].
*   **Адверсариальное кодирование:** Переход от модели случайного шума к модели «умного противника», который может намеренно выбирать, какие биты исказить в рамках заданного бюджета ошибок [1:11:27].