Что такое неравномерный код? Сформулируйте условие Фано.

Неравномерный код — это код, в котором разные символы могут кодироваться словами разной длины. Например, часто встречающиеся символы можно кодировать короткими кодами, а редкие —…

Неравномерный код — это код, в котором разные символы могут кодироваться словами разной длины.

Например, часто встречающиеся символы можно кодировать короткими кодами, а редкие — длинными. Это позволяет уменьшить среднюю длину сообщения.

Равномерный и неравномерный код

Равномерный код

В равномерном коде все кодовые слова имеют одинаковую длину.

Пример:

A = 00
B = 01
C = 10
D = 11

Каждый символ кодируется двумя битами.

Неравномерный код

В неравномерном коде длины кодовых слов разные.

Пример:

A = 0
B = 10
C = 110
D = 111

Символ A имеет самый короткий код.

Проблема декодирования

Главный вопрос для неравномерного кода: можно ли однозначно разбить поток битов на символы.

Например, если:

A = 0
B = 01

то кодовая строка 01 может начинаться как A, но также может быть кодом B. Такое кодирование неоднозначно.

Условие Фано

Условие Фано формулируется так:

никакое кодовое слово не должно быть началом другого кодового слова.

Иначе говорят: код должен быть префиксным.

Пример кода, который удовлетворяет условию Фано

A = 0
B = 10
C = 110
D = 111

Проверим:

• 0 не является началом 10, 110 или 111;
• 10 не является началом 110 или 111;
• 110 не является началом 111;
• 111 не является началом другого слова.

Значит, код можно декодировать однозначно слева направо.

Пример нарушения условия Фано

A = 0
B = 01
C = 10

Код A равен 0, и он является началом кода B, равного 01. Условие Фано нарушено.

Почему это важно

Если условие Фано выполняется, декодер может читать последовательность битов и сразу понимать, где заканчивается очередной символ. Не нужно ждать дополнительные символы или возвращаться назад.

Это свойство используется в префиксных кодах, например в идее кодирования Хаффмана.

Где применяются неравномерные коды

Неравномерные коды применяются:

• в сжатии данных;
• при передаче сообщений;
• в кодировании символов с учетом частот;
• в теории информации;
• в построении префиксных деревьев.

Вывод

неравномерный код использует кодовые слова разной длины. Чтобы такой код декодировался однозначно, часто требуют выполнение условия Фано: ни одно кодовое слово не является префиксом другого.