Одно и то же сообщение можно закодировать различными способами. Оптимально закодированным будем считать такой код, при котором на передачу сообщений затрачивается минимальное время. Если на передачу каждого элементарного символа (0 или 1) тратиться одно и то же время, то оптимальным будет такой код, который будет иметь минимально возможную длину.
Пример 1.
Пусть
имеется случайная величина
X(x1,x2,x3,x4,x5,x6,x7,x8),
имеющая восемь состояний
с распределением вероятностей
Для кодирования алфавита из восьми букв без учета вероятностей равномерным двоичным кодом нам понадобятся три символа:
Это
000, 001, 010, 011, 100, 101, 110, 111
Определив
избыточность L
по формуле L=1-H/H0=1-2,75/3=0,084,
видим, что возможно сокращение длины
кода на
8,4%.
Возникает
вопрос: возможно ли составить код, в котором
на одну букву будет, в среднем приходится
меньше элементарных символов.
Такие
коды существуют. Это коды Шеннона-Фано
и Хаффмана.
Принцип
построения оптимальных кодов:
1.
Каждый элементарный символ должен
переносить максимальное количество
информации, для этого необходимо, чтобы
элементарные символы (0 и 1) в закодированном
тексте встречались в среднем одинаково
часто. Энтропия в этом случае будет
максимальной.
2.
Необходимо буквам первичного алфавита,
имеющим большую вероятность, присваивать
более короткие кодовые слова вторичного
алфавита.
