4. Статистичне кодування

У зв'язку з тим, що при кодуванні нерівноймовірних повідомлень рівномірні коди мають велику надмірність, було запропоновано використовувати нерівномірні коди, тривалість кодових комбінацій яких була б погоджена з імовірністю випадання різних букв. Таке кодування називається статистичним.

Нерівномірний код при статистичному кодуванні вибирають так, щоб більш ймовірні букви передавалися за допомогою більш коротких комбінацій коду, менш ймовірні - за допомогою більш довгих. У результаті зменшується середня довжина кодової групи в порівнянні з випадком рівномірного кодування. Приклад нерівномірного префіксного коду подано в таблиці 3.3.

Таблиця 3.3 – Приклад нерівномірного префіксного коду

Буква	Імовірність Рi	Кодове дерево	Код	ni	ni × Pi
А Б У Г Д Е Ж З	0.6 0.2 0.1 0.04 0.025 0.015 0.01 0.01		1 01 001 0001 00001 000001 0000001 00000001	1 2 3 4 5 6 7 8	0.6 0.4 0.3 0.16 0.125 0.08 0.07 0.08

Середнє число символів для такого коду складе

а надмірність коду

тобто на порядок менше, ніж при рівномірному кодуванні.

5. Код Шеннона-Фано

Іншим найпростішим способом статистичного кодування є кодування по методу Шеннона-Фано. Кодування відповідно до цього алгоритму виробляється так:

– спочатку всі букви з алфавіту повідомлення записують у порядку зменшення їхніх імовірностей;

– потім усю сукупність букв розбивають на дві приблизно рівні по сумі імовірностей групи; одній з них (у групі може бути будь-яке число символів, у тому числі – один) привласнюють символ “1”, іншої - “0”;

– кожну з цих груп знову розбивають (якщо це можливо) на дві частин і кожній з частин привласнюють “1” і “0” і т.д.

Процедура кодування по методу Шеннона-Фано подана в таблиці 3.4.

Таблиця 3.4 – Процедура кодування по методу Шеннона-Фано

Буква	Р(хi )	I	II	III	IV	V	Код	ni  Pi
А	0.6	1					1	0.6
Б	0.2	0	1	1			011	0.6
В	0.1			0			010	0.3
Г	0.04		0	1			001	0.12
Д	0.025			0	1		0001	0.1
Е	0.015				0		00001	0.075
Ж	0.01					1	000001	0.06
З	0.01					0	000000	0.06

Для отриманого в такий спосіб коду середнє число двійкових символів, що приходяться на одну букву, дорівнює

,

Надмірність коду складе

Тобто також істотно меншу величину, ніж для рівномірного коду.

2. Завдання

1. Побудувати оптимальний нерівномірний код Шеннона–Фано для передачі M повідомлень за допомогою коду з алфавітом q, якщо повідомлення над виході з джерела з’являються з ймовірностями p(x_i). За допомогою першої універсальної методики. Використати варіанти завдань наведені в таблиці 1.1.

2. Побудувати кодове дерево для отриманого коду.

3. Виконати завдання 1 використовуючи другу універсальну методику.

4. Побудувати кодове дерево для отриманого коду.

5. Провести порівняльний аналіз та оцінку одержаних результатів.

6. Модифікувати програму розроблену в лабораторній роботі №1, додавши можливість побудови коду Шеннона–Фано для україномовних текстів. В програмі передбачити наступні функції:

• можливість роботи з символами однієї з кириличних кодових таблиць (cyrilic windows, koi8ru, або ін..);

• можливість вводу та копіювання текстового блоку;

• відображення загальної кількості символів у текстовому блоці;

• розмір текстового блоку повинен бути не менше 2000 символів;

• при обчисленні ентропії враховувати символи знаків пунктуації (коми, крапки, тире та ін..);

• відображення імовірностей появи символів у текстовому блоці;

• відображення обчисленого значення ентропії;

• відображення таблиці покрокової побудови коду Шеннона-Фано.

• відображення таблиці побудованого коду.

• відображення інформації про розробника (курс, група, прізвище та ініціали);

• виконання без застосування середовища програмування використаного для створення програми.

7. Оформити звіт.