В лекции 18 курса MIT «Алгоритмический аспект теории информации» рассматривается одна из фундаментальных работ Клода Шеннона — вторая теорема Шеннона (теорема о кодировании для каналов с шумом). В отличие от сжатия данных, где целью является минимизация объема информации, здесь фокус смещается на надежность передачи данных в условиях помех.
📡 Проблема передачи данных через шумный канал 0:11
Традиционно информация передается по каналам, которые подвержены внешним воздействиям. В цифровой среде простейшей моделью такого процесса является двоичный симметричный канал (BSC — binary symmetric channel) . Его работа описывается параметром $P$ — вероятностью инверсии (флипа) каждого отдельного бита. С вероятностью $P$ бит меняется на противоположный (0 на 1 или наоборот), а с вероятностью $1-P$ проходит без изменений .
Ключевая сложность заключается в том, что получатель не знает, в каких именно позициях произошли ошибки. Если представить $P = 1/3$, то каждый третий бит сообщения в среднем будет ошибочным . Задача теории кодирования состоит в том, чтобы найти такие методы избыточного кодирования, которые позволят восстановить исходное сообщение с высокой точностью.
🔁 Ограниченность кодов повторения 3:09
Первым и наиболее очевидным решением проблемы ошибок являются коды повторения (repetition codes). Суть метода проста: каждый бит сообщения повторяется $t$ раз . Например, вместо «1» передается «111...1», а вместо «0» — «000...0». Декодирование на приемной стороне происходит методом мажоритарного голосования (majority vote): если в блоке из $t$ полученных символов больше единиц, считается, что была передана единица .
Однако коды повторения крайне неэффективны с точки зрения скорости передачи (rate). Скорость кода определяется как отношение длины исходного сообщения $K$ к длине переданной последовательности $N$ . По словам лектора:
- При использовании кодов повторения для достижения вероятности ошибки, стремящейся к нулю, необходимо увеличивать число повторений пропорционально логарифму длины сообщения ($\log K$) .
- Это приводит к тому, что при стремлении длины сообщения к бесконечности скорость передачи данных стремится к нулю .
Главный вопрос лекции: можно ли передавать информацию надежно (с исчезающе малой вероятностью ошибки), сохраняя при этом постоянную, не нулевую скорость передачи? .
🧪 Теорема Шеннона и понятие пропускной способности 18:35
Клод Шеннон доказал поразительный результат: для любого шумного канала существует критическое значение, называемое пропускной способностью (capacity) .
Для двоичного симметричного канала пропускная способность вычисляется по формуле $1 - H(P)$, где $H(P)$ — функция двоичной энтропии . Теорема Шеннона утверждает:
- Если скорость передачи $R$ меньше пропускной способности ($R < 1 - H(P)$), то существует схема кодирования, при которой вероятность ошибки стремится к нулю при увеличении длины блока .
- Если скорость $R$ превышает этот предел, вероятность ошибки неизбежно стремится к единице (надежная передача невозможна) .
Интуитивно это понятно на примере $P = 1/2$. В этом случае энтропия $H(1/2) = 1$, а пропускная способность $1 - 1 = 0$ . Это логично: если канал инвертирует биты с вероятностью 50%, на выходе получается случайный шум, не несущий никакой информации об источнике .
🎲 Вероятностный метод: случайный код как решение 26:44
Доказательство возможности надежной передачи при постоянной скорости базируется не на поиске конкретного «идеального» алгоритма, а на вероятностном методе. Лектор подчеркивает ироничность ситуации: «Чтобы доказать теорему, мы берем кодирование как случайную функцию — и это всё» .
Схема доказательства состоит в следующем:
- Создается «кодовая книга» (code book), состоящая из случайных последовательностей для каждого возможного сообщения .
- Для декодирования используется концепция «колец» (rings) вокруг кодовых слов. Кольцо — это множество всех векторов, находящихся на определенном расстоянии Хэмминга от исходного кода, соответствующем ожидаемому количеству ошибок $NP$ .
- Ключевая лемма гласит: при $R < 1 - H(P)$ с высокой вероятностью принятый сигнал попадет в «кольцо» правильного кодового слова и не попадет ни в одно другое .
Лектор объясняет появление энтропии через комбинаторику: количество векторов в «кольце» описывается биномиальными коэффициентами, аппроксимация которых через формулу Стирлинга напрямую приводит к функции энтропии в экспоненте .
🛠 От теории к практике: линейные коды 1:09:03
Несмотря на математическое изящество, метод случайного кодирования Шеннона неприменим на практике. Для кодовой книги со случайными значениями потребовалось бы экспоненциальное количество памяти для хранения всех пар «сообщение-код» .
В качестве решения этой проблемы анонсируются следующие темы курса:
- Линейные коды: Вместо хранения всей книги используется матрица. Процесс кодирования превращается в умножение вектора сообщения на матрицу, что гораздо эффективнее .
- Адверсариальное кодирование: Переход от модели случайного шума к модели «умного противника», который может намеренно выбирать, какие биты исказить в рамках заданного бюджета ошибок .
