Код Шеннона-Фано
Те саме повідомлення можна закодувати різними способами. Оптимально закодованим вважатимемо такий код, при якому на передачу повідомлень витрачається мінімальний час. Якщо на передачу кожного елементарного символу (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. Необхідно буквам первинного алфавіту, які мають більшу ймовірність, надавати короткі кодові слова вторинного алфавіту.
Приклад 2. Закодуємо літери алфавіту з прикладу 1 код Шеннона - Фано.
Всі літери записуються в порядку зменшення їх ймовірностей, потім діляться на рівноймовірні групи, якіпозначаються 0 та 1, потім знову діляться на рівноймовірні групи і т.д. (Див.табл.4.1)
Середня довжина отриманого коду дорівнюватиме
Отже ми отримали оптимальний код. Довжина цього коду збіглася з ентропією. Цей код виявився успішним, оскільки величини ймовірностей точно ділилися на рівноймовірні групи.
Візьмемо 32 дві літери українського алфавіту. Частоти цих букв відомі. В алфавіт включений і пропуск, частота якого становить 0,145. Метод кодування представлений у таблиці 4.2.
Середня довжина цього коду дорівнюватиме, біт/літеру;
Ентропія H = 4.42 біт/літера. Ефективність одержаного коду можна визначити як відношення ентропії до середньої довжини коду. Вона дорівнює 0,994. При значенні рівному одиниці код є оптимальним. Якби ми кодували кодом рівномірної довжини, то ефективність була б значно нижчою.