Источник → Канал: двухэтапное кодирование
Глава 10 Hamming начинается с модели коммуникации Шеннона, которая применяется к каждой системе, передающей информацию: телефонные вызовы, радио, жесткие диски, репликация ДНК, память компьютера.
Двухэтапная архитектура
Этап 1: кодирование источника (сжатие). Преобразовать исходное сообщение в компактное представление. Цель: удалить избыточность, присущую источнику. Код Морзе делает это: частые буквы получают короткие коды, редкие буквы получают длинные.
Этап 2: кодирование канала (защита от ошибок). Добавить контролируемую избыточность, адаптированную к характеристикам шума канала. Шумная телефонная линия нуждается в большей избыточности, чем оптоволоконный кабель. Два этапа развязаны: оптимизировать каждый независимо для его собственной задачи.
Общий интерфейс между двумя этапами — стандартный битовый поток — означает, что любой источник может сочетаться с любым каналом. Эта модульность является ключным архитектурным прозрением Шеннона.
Хранение как коммуникация. Hamming отмечает, что отправка сообщения через пространство (передача) и отправка его через время (хранение) используют одну и ту же модель. Резервный диск — это шумный канал во времени.
Роль шума
Модель Шеннона делает радикальное предположение: шум неизбежен. Каждый канал, каждый носитель данных, каждая коммутационная цепь вводит некоторую вероятность ошибки. Вопрос не 'как мы устраняем шум?' а 'как мы восстанавливаем исходное сообщение несмотря на шум?'
Это контрастирует с классической физикой, где шум входит как запоздалая мысль (принцип неопределенности). Шеннон рассматривает шум как фундаментальное условие — вся теория строится на нем.
На данный момент глава 10 сосредоточена на случае без шума: кодирование источника без ошибок. Задача кодирования канала (исправление ошибок) ждет в более поздних главах.
Когда вы можете декодировать уникально?
Чтобы код переменной длины был полезен, получатель должен однозначно декодировать поток битов. Hamming иллюстрирует это 4-символьным кодом, который не проходит этот тест, а затем вводит исправление: коды без префиксов.
Условие отсутствия префикса
Код является без префиксов (или мгновенным), если ни одно кодовое слово не является префиксом другого кодового слова. Получив битовый поток, вы знаете, что символ закончился в тот момент, когда вы достигаете листа в дереве декодирования — предварительный просмотр не требуется.
Пример кода без префиксов для {s1, s2, s3, s4}: s1 = 0, s2 = 10, s3 = 110, s4 = 111.
Проверка: 0 не является префиксом 10, 110 или 111. 10 не является префиксом 110 или 111 (10, за которым следуют дополнительные биты, дает 100... или 101..., ни один из которых не начинается с 110 или 111). Код квалифицируется.
Процедура декодирования: следите за деревом, ветвитесь на каждый входящий бит, выдавайте символ, когда вы попадаете на лист, вернитесь к корню.
Неравенство Крафта
Для любого бинарного кода без префиксов с длинами кодовых слов l_1, l_2, ..., l_n:
Σ 2^(−l_i) ≤ 1
Равенство выполняется, когда код полный (листья покрывают полное бинарное дерево без пробелов). Это необходимое условие: ни один код без префиксов не может его нарушить. Наоборот, для любого набора длин, удовлетворяющих неравенству Крафта, существует код без префиксов.
Применение неравенства Крафта
Учитывая длины кодов, проверьте Крафта: Σ 2^(−l_i) ≤ 1.
Для {s1=0, s2=10, s3=110, s4=111}: длины 1, 2, 3, 3.
Σ = 2^(−1) + 2^(−2) + 2^(−3) + 2^(−3) = 1/2 + 1/4 + 1/8 + 1/8 = 1. ✓
Энтропия Шеннона
Средняя длина кода кода переменной длины: L = Σ p_i · l_i, где p_i — вероятность символа s_i, а l_i — длина его кода.
Как коротко может быть L? Ответ Шеннона: не ниже энтропии источника.
Энтропия Шеннона: H = −Σ p_i · log₂(p_i) (единицы: биты/символ)
Энтропия измеряет среднюю информацию на символ. Высокая энтропия означает, что символы примерно одинаково вероятны (максимальная непредсказуемость). Низкая энтропия означает, что некоторые символы доминируют (высокая предсказуемость, более сжимаемо).
Теорема о кодировании без помех
Для любого кода без префиксов H(источник) ≤ L ≤ H(источник) + 1.
Ни один код не может превзойти энтропию. Кодирование Хаффмана (следующая глава) достигает верхней границы: L < H + 1. Для блоковых кодов над n символами граница сужается: H ≤ L/n < H + 1/n.
Энтропия также является теоретическим пределом сжатия: вы не можете сжать источник ниже H битов на символ без потери информации.
Вычисление энтропии
Пример: 4 символа с вероятностями p = [1/2, 1/4, 1/8, 1/8].
H = −(1/2)·log₂(1/2) − (1/4)·log₂(1/4) − (1/8)·log₂(1/8) − (1/8)·log₂(1/8)
= (1/2)·1 + (1/4)·2 + (1/8)·3 + (1/8)·3
= 0,5 + 0,5 + 0,375 + 0,375 = 1,75 битов/символ
И код Хаффмана {0, 10, 110, 111} достигает L = 1,75 = H точно.
Почему энтропия — это нижняя граница
Нижняя граница теоремы о кодировании без помех — это не просто формула — она отражает что-то глубокое об информации: вы не можете сжать то, что уже максимально непредсказуемо.
Когда все символы одинаково вероятны (равномерное распределение), энтропия H = log₂(n) для n символов. Блоковый код длины log₂(n) битов достигает ровно H. Ни один код не может сделать лучше.
Когда один символ доминирует (скажем, p(A) = 0,99, p(B) = 0,01), H мал — близко к 0. Код переменной длины может назначить A очень короткий код, кодируя поток очень эффективно.
Практический вывод: большие выигрыши в сжатии существуют только когда вероятности символов существенно различаются. Если источник уже 'равномерен' (выглядит случайным), кодирование Хаффмана ничего не дает.