Оптимальне кодування
Те саме повідомлення можна закодувати різними способами. Оптимально закодованим вважатимемо такий код, при якому на передачу повідомлень витрачається мінімальний час. Якщо на передачу кожного елементарного символу (0 або 1) витрачається той самий час, то оптимальним буде такий код, який матиме мінімально можливу довжину.
Нехай є випадкова величина X (x1, x2, x3, x4, x5, x6, x7, x8), що має вісім станів з розподілом ймовірностей
Для кодування алфавіту з восьми букв без урахування ймовірностей рівномірним двійковим кодом нам знадобляться три символи:
Це 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. Необхідно буквам первинного алфавіту, які мають більшу ймовірність, надавати короткі кодові слова вторинного алфавіту.