Теория информации

1.3.4. Оптимальное кодирование Оптимальные коды применяются в тех случаях, когда символы алфавита встречаются в сообщениях с различной вероятностью. В этом случае применение оптимальных кодов позволяет минимизировать избыточность кода, а, следовательно, сократить время передачи сообщений. Одно и то же сообщение можно закодировать различными способами. Определение. Оптимально закодированным будем считать такой код, при котором на передачу сообщений затрачивается минимальное время. Если на передачу каждого элементарного символа (0 или 1) тратиться одно и то же время, то оптимальным будет такой код, который будет иметь минимально возможную длину. Пример 1.21. Пусть имеется случайная величина: X(x 1 ,x 2 ,x 3 ,x 4 ,x 5 ,x 6 ,x 7 ,x 8 ), имеющая восемь состояний с распределением вероятностей: P 1 4 1 4 1 8 1 8 1 16 1 16 1 16 1 16 , , , , , , ,      . Для кодирования алфавита из восьми букв без учета вероятностей равномерным двоичным кодом нам понадобятся три символа: 38 log   р k . Это: 000, 001, 010, 011, 100, 101, 110, 111. Чтобы ответить, хорош этот код или нет, необходимо сравнить его с оптимальным значением, то есть определить энтропию: 75 .2 16 1 log 16 1 4 8 1 log 8 1 2 4 1 log 4 1 2 log 8 1          i i i p p H Определив избыточность L по формуле: L = 1 - H / H 0 = 1  2,75 / 3 = 0,084, видим, что возможно сокращение длины кода на 8,4%. Возникает вопрос: возможно ли составить код, в котором на одну букву будет, в среднем приходится меньше элементарных символов.