Завдання 1. Задано 8 повідомлень та ймовірності їх появи. Побудувати код Шеннона-Фано та код Хаффмана. Виконати порівняння характеристик щодо ефективності кодування.

, , , , , ,

, .

Код Шеннона-Фано:

Для побудови коду Шеннона-Фано всі повідомлення записуються в порядку спадання їх ймовірностей.

		Поділ повідомлення на підгрупи				Код
	0.27	1	1			11	2	0.54
	0.23	1	0			10	2	0.46
	0.14	0	1	1		011	3	0.42
	0.12	0	1	0		010	3	0.36
	0.07	0	0	1	1	0011	4	0.28
	0.06	0	0	1	0	0010	4	0.24
	0.06	0	0	0	1	0001	4	0.24
	0.05	0	0	0	0	0000	4	0.20

Записані таким чином повідомлення розбиваються на дві по можливості рівноймовірні підгрупи. Всім повідомленням першої підгрупи присвоюють 1 в якості кодового символу, а всім повідомленням другої підгрупи – 0. Аналогічне ділення на підгрупи робиться до тих пір, доки в кожну підгрупу не попаде одне повідомлення. Знайдений код по Шеннону-Фано дуже близький до оптимального. Щоб це перевірити, знайдемо ентропію цих повідомлень:

.

Визначимо середню довжину кодового слова:

.

Знайдемо середне число нулів:

.

Знайдемо середне число одиниць:

.

Перевірка: .

Ймовірність появи нулів: .

Ймовірність появи одиниць: .

Перевірка: .

Так як , то говорять, що поява символів є рівноймовірна, а тому отриманий код є близьким до оптимального.

Код Хаффмана:

		Об’єднання повідомлень																					Код
	0.27			0.27			0.27			0.27			0.27			0.46			0.54	1		1	10
	0.23			0.23			0.23			0.23			0.27			0.27	1		0.46	0			00
	0.14			0.14			0.14			0.23			0.23	1		0.27	0						111
	0.12			0.12			0.13			0.14	1		0.23	0									011
	0.07			0.11			0.12	1		0.13	0												1101
	0.06			0.07	1		0.11	0															1100
	0.06	1		0.06	0																		0101
	0.05	0																					0100

Для того, щоб отримати код Хаффмана, дві найменші ймовірності об’єднуються дужкою і одній з них присвоюється символ 1, іншій – 0. Потім ці ймовірності додаються, результат записується в проміжку між найближчими йому ймовірностями. Процес об’єднання повідомлень для найменших ймовірностей продовжується до тих пір, поки сумарна ймовірність повідмлення не стане рівною 1. Код для кожного повідомлення будується при записі двійкового числа справа-наліво шляхом обходу по лініях вверх-направо, починаючи з ймовірності повідомлення, для якого будується код.

Жоден з отриманих кодів не співпав з початком довшого коду. Тобто знайдені коди є префіксними.

.

Визначимо середню довжину кодового слова:

.

Знайдемо середне число нулів:

.

Знайдемо середне число одиниць:

.

Перевірка: .

Ймовірність появи нулів: .

Ймовірність появи одиниць: .

Перевірка: .

Так як , то говорять, що поява символів є рівноймовірна, а тому отриманий код є близьким до оптимального.

Висновок: для заданих ймовірностей середня довжина кодового слова для методів кодування Шеннона-Фано та Хаффмана однакова: . Тому можна сказати, що обидва коди однаково оптимальні.

Завдання 2. Згрупувати по два і по три повідомлення в групі. Побудувати код Хаффмана. Виконати порівняльну характеристику щодо ефективності коду, швидкості передачі та похибки коду. Значення ймовірностей наступні: , .