Модель системы передачи информации

Основы теории информации Открыть в лаборатории →

Любая система связи — телефон, Wi-Fi, флешка, космический зонд — решает одну задачу: доставить сообщение от источника к получателю быстро, без искажений и, если нужно, тайно. Клод Шеннон в 1948 году описал эту задачу математически, и его схема до сих пор лежит в основе теории информации.

Схема Шеннона

Система передачи информации состоит из пяти звеньев:

Звено	Что делает	В лаборатории
Источник	порождает сообщение — последовательность символов алфавита	класс Source: введённый текст
Кодер	преобразует сообщение в сигнал для канала: сжимает, добавляет избыточность для защиты от помех, шифрует	класс Encoder
Канал	переносит сигнал; в канале с шумом часть символов искажается	моделирование ошибок в кодах Хэмминга и Адамара
Декодер	восстанавливает сообщение: исправляет ошибки, расшифровывает, распаковывает	класс Decoder
Приёмник	получатель сообщения	класс Receiver

Кодер обычно решает три разные задачи, и в теории их принято разделять:

кодирование источника (сжатие) — убрать избыточность, чтобы передавать меньше символов (код Хаффмана, Шеннона–Фано);
канальное (помехоустойчивое) кодирование — добавить контролируемую избыточность, чтобы обнаруживать и исправлять ошибки (код Хэмминга, код Адамара);
шифрование — сделать сообщение непонятным для постороннего, у которого нет ключа (классические шифры, шифр Эль-Гамаля).

Порядок важен: сначала сжимают (у сжатого текста меньше статистических закономерностей, которые помогают криптоаналитику), затем шифруют, и последним — помехоустойчивое кодирование, которое защищает уже готовый к передаче поток бит.

Количество информации

Определение

Количество информации в событии, которое происходит с вероятностью p, равно

I = −log₂ p (бит)

Чем неожиданнее событие, тем больше информации оно несёт. Исход броска монеты (p = 1/2) несёт ровно 1 бит, выпадение конкретной грани кубика — log₂ 6 ≈ 2,58 бита, а достоверное событие (p = 1) — 0 бит. Логарифм выбран потому, что информация независимых событий складывается: −log₂(p·q) = −log₂ p − log₂ q.

Энтропия источника

Определение

Пусть источник выдаёт символы a_1, …, a_N независимо с вероятностями p_1, …, p_N. Энтропия источника — среднее количество информации на символ:

H = −Σ p_i·log₂ p_i

Свойства

H ≥ 0, и H = 0 только если один символ имеет вероятность 1.
H ≤ log₂ N, равенство — только при равновероятных символах.

Доказательство второго свойства. Функция log₂ выпукла вверх, поэтому по неравенству Йенсена Σ p_i·log₂(1/p_i) ≤ log₂(Σ p_i·(1/p_i)) = log₂ N, причём равенство достигается, только когда все 1/p_i равны.

Пример

Слово «абракадабра» из 11 букв: «а» встречается 5 раз, «б» и «р» — по 2, «к» и «д» — по 1. Энтропия

H = −(5/11)·log₂(5/11) − 2·(2/11)·log₂(2/11) − 2·(1/11)·log₂(1/11) ≈ 2,04 бита/символ

Равномерный код для пяти букв требует ⌈log₂ 5⌉ = 3 бита на символ, то есть 33 бита на слово. Теория говорит, что никакой код не опустится ниже ≈ 2,04 бита на символ (≈ 22,4 бита на слово), а код Хаффмана тратит 23 бита — см. пример в статье о коде Хаффмана.

Избыточность

Избыточность показывает, какая доля передаваемых символов «лишняя»:

R = 1 − H / log₂ N

Избыточность естественного языка велика — по оценкам Шеннона, для английского текста она около 50% и выше: многие буквы угадываются по контексту («прив_т»). Это и позволяет сжимать тексты, и делает возможным частотный анализ шифров. Помехоустойчивые коды, наоборот, намеренно добавляют избыточность: у кода Хэмминга (7,4) из 7 бит только 4 несут данные, скорость кода k/n = 4/7.

Две теоремы Шеннона

Теорема о кодировании источника

Для любого однозначно декодируемого кода средняя длина кодового слова L ≥ H. Существует префиксный код с L < H + 1, а при кодировании блоками из m символов — с L < H + 1/m на символ.

Теорема о кодировании для канала с шумом

У каждого канала есть пропускная способность C. Если скорость передачи меньше C, существуют коды, при которых вероятность ошибки декодирования сколь угодно мала; при скорости больше C это невозможно.

Для двоичного симметричного канала, который переворачивает каждый бит с вероятностью q, C = 1 − h(q), где h(q) = −q·log₂ q − (1 − q)·log₂(1 − q). Теорема утверждает существование хороших кодов, но не даёт их построения — поиску таких кодов посвящена вся теория помехоустойчивого кодирования.

В лаборатории

Простейший «кодер» — переворачивание текста: он ничего не сжимает и не защищает, зато наглядно показывает, что кодер и декодер должны быть согласованы — декодер применяет обратное преобразование. Открыть пример →

Вопросы для самопроверки

Сколько информации несёт сообщение «выпало число 3» при броске честного кубика?
Ответ
log₂ 6 ≈ 2,58 бита.
Почему энтропия источника из 8 равновероятных символов равна 3 битам?
Ответ
H = −8·(1/8)·log₂(1/8) = log₂ 8 = 3.
Почему сжатие выполняют до шифрования, а не после?
Ответ
Хороший шифртекст выглядит случайным и почти не сжимается; кроме того, сжатие убирает статистические закономерности открытого текста, которые помогают криптоаналитику.
Что такое скорость кода и чему она равна для кода (15,11)?
Ответ
Доля информационных символов: k/n = 11/15 ≈ 0,73.