- Коды бывают равномерные и неравномерные.
- Равномерные коды используют кодовые слова одинаковой длины. Их преимущества — простота кодирования и декодирования, а также гарантия однозначного декодирования.
- Неравномерные коды допускают разную длину кодовых слов, но для однозначного декодирования должно выполняться условие Фано: никакое кодовое слово не должно быть началом другого.
Пример. По каналу связи передаются сообщения, содержащие шесть букв: A, B, C, D, E, F. Используется неравномерный двоичный код, удовлетворяющий условию Фано. Для букв A, B, C заданы кодовые слова: A = 11, B = 101, C = 0. Найдите кодовое слово наименьшей длины для буквы F.
Решение.
- Строим двоичное дерево от корня.
- Буква C (0) блокирует левую ветку.
- Продолжаем строить дерево от правой ветки (11).
- Буква A (11) блокирует правую ветку.
- От левой ветки (10) продолжаем построение:
- Буква B (101) блокирует правую ветку.
- Наименьшая свободная ветка — левая ветка 4-го уровня (1000).
- Оставшиеся буквы D и E кодируются на других свободных ветках.
Ответ. 1000.