Оптимално кодиране
Едно и също съобщение може да бъде кодирано по различни начини. Оптимално кодиран код е този, при който се изразходва минимално време за предаване на съобщение. Ако предаването на всеки елементарен знак (0 или 1) отнема едно и също време, тогава оптималният код ще бъде този, който ще има минималната възможна дължина.
Нека има случайна променлива X (x 1, x 2, x 3, x 4, x 5, x 6, x 7, x 8), имаща осем състояния с вероятностно разпределение
За да кодираме азбука от осем букви, без да отчитаме вероятностите с единен двоичен код, имаме нужда от три знака:
Това е 000, 001, 010, 011, 100, 101, 110, 111
За да отговорите дали този код е добър или не, трябва да го сравните с оптималната стойност, тоест да определите ентропията
След като определихме излишъкаLпо формулатаL =1- H / H 0=1 - 2.75/3=0.084,виждаме, че е възможно да се намали дължината на кода с 8.4%.
Възниква въпросът: възможно ли е да се състави код, в който да има средно по-малко елементарни символи на буква.
Такива кодове съществуват. Това са кодовете на Шанън-Фано и Хъфман.
Принципът на конструиране на оптимални кодове:
1. Всеки елементарен знак трябва да носи максимално количество информация, за това е необходимо елементарните знаци (0 и 1) в кодирания текст да се срещат средно еднакво често. Ентропията в този случай ще бъде максимална.
2. Необходимо е на буквите от първичната азбука, които имат по-голяма вероятност, да бъдат присвоени по-кратки кодови думи от вторичната азбука.