2.1 Двоичное кодирование. Равномерные и неравномерные коды. Декодирование сообщений, записанных с помощью неравномерных кодов. Условие Фано. Построение однозначно декодируемых кодов с помощью дерева

1. Двоичное кодирование

Принцип: Любая информация представляется комбинациями 0 и 1.

Примеры:

2. Равномерные vs Неравномерные коды

Неравномерный код: Частые символы → короткие коды (пример: А=0, Б=10, В=110, Г=111).

3. Условие Фано

Цель: Гарантировать однозначное декодирование.

Правила:

• Прямое условие: Ни одно кодовое слово не совпадает с началом другого.
• Обратное условие: Ни одно кодовое слово не является окончанием другого.

Проверка кода:

4. Дерево кодирования

Принцип: Построение бинарного дерева для префиксного кода.

Пример для А, Б, В, Г:

graph TD
ROOT[ ] -- 0 --> A[А]
ROOT -- 1 --> N1[ ]
N1 -- 0 --> B[Б]
N1 -- 1 --> N2[ ]
N2 -- 0 --> B1[В]
N2 -- 1 --> B2[Г]

Полученные коды:

• А: 0
• Б: 10
• В: 110
• Г: 111

5. Декодирование сообщений

Алгоритм:

1. Читать биты до совпадения с кодовым словом
2. Записать символ и перейти к следующим битам

Пример:

Сообщение: 110100111

Код: А=0, Б=10, В=110, Г=111

• 110 → В (остаток: 100111)
• 10 → Б (остаток: 0111)
• 0 → А (остаток: 111)
• 111 → Г

Результат: ВБАГ

6. Построение оптимального кода

Шаги (метод Хаффмана):

1. Составить таблицу частот
2. Построить дерево (объединять символы с min частотой)
3. Назначить коды: левая ветвь = 0, правая = 1

Пример частот:

Дерево Хаффмана:

graph TD
A[А:40] -->|0| ROOT[100%]
BC[Б+В+Г:60] -->|1| ROOT
B[Б:30] -->|0| BC
C[В+Г:30] -->|1| BC
V[В:20] -->|0| C
G[Г:10] -->|1| C

Коды:

• А: 0
• Б: 10
• В: 110
• Г: 111