3. Приклад виконання завдання

Побудувати оптимальний нерівномірний код (ОНК) Шеннона–Фано для передачі 13 повідомлень за допомогою коду з алфавітом 4, якщо повідомлення над виході з джерела з’являються з ймовірностями 0.25, 0.1, 0.05, 0.02, 0.03, 0.05, 0.11, 0.04, 0.01, 0,15, 0.01, 0,08, 0.1.

Розв’язання:

Використовуємо першу універсальну методику побудови ОНК. Згідно неї необхідно виконати ряд процедур:

1)Розташуємо множину повідомлень у порядку спадання ймовірностей.

2)Визначаємо квант поділу 1/q=1/4=0.25.

3)Впорядковані за ймовірністю розбиваємо , по можливості, на 4 рівно ймовірні групи: ;;;;

4)За результатами першого поділу груп як перший символ кодових комбінацій присвоюємо послідовно якісні ознаки алфавіту q згідно з 3-ю процедурою першої універсальної методики побудови ОНК.

5)Утворені групи ,крім першої, розбиваємо на підгрупи. Друга та третя групи мають до 4-х повідомлень, тому як другий символ кодових комбінацій їм присвоюємо відповідно три та чотири якісні ознаки алфавіту q.

6)Четверта група має 7 повідомлень, тому розбиваємо її на рівно ймовірні підгрупи. Квант поділу 0,25:4=0,0625. Поділ присвоєння ознак виконуємо доти, поки після чергового поділу в утворених підгрупах залишиться не більше як одне повідомлення.

Отриманий код наведено в таблиці 3.5.

Таблиця 3.5 – Оптимальний нерівномірний код Шеннона–Фано

Номер повідомлення	Ймовірність повідомлення	Кодова комбінація ОНК
1	0,25	0
2	0,15	10
3	0,11	11
4	0,1	20
5	0,1	21
6	0,08	22
7	0,05	300
8	0,05	301
9	0,04	310
10	0,03	311
11	0,02	312
12	0,01	3130
13	0,01	3131

Побудуэмо кодове дерево (рисунок 3.4).

Рисунок 3.4 – Кодове дерево побудоване за першою універсальною методикою

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

1. Множину з М = 13 повідомлень розташовуємо в порядку спадання ймовірностей.

2. Оскільки q = 4, об’єднуємо останні 4 повідомлення й утворюємо нове умовне повідомлення з ймовірністю, що дорівнює сумі ймовірностей об’єднаних повідомлень.

3. Утворену множену з 13-4=11 повідомлень розташовуємо в порядку спадання ймовірностей.

4. Знову об’єднуємо останні 4 повідомлення та впорядковуємо множину повідомлень у порядку спадання ймовірностей. Цю процедуру повторюємо, поки сумарна ймовірність не досягне одиниці.

5. Будуємо кодове дерево (рисунок 3.5). Його гілкам присвоюємо якісні ознаки кодового алфавіту.

Рисунок 3.5 – Кодове дерево побудоване за другою універсальною методикою

6. Кодові комбінації ОНК заносимо до таблиці 3.6. Вони визначаються послідовністю якісних ознак, які зустрічаються на шляху від кореня до певної вершини кодового дерева.

Таблиця 3.6 – Побудова коду Шеннона-Фано за другою універсальною методикою

Номер повідомлення	Ймовірність повідомлення	Ймовірності повідомлень при об’єднаннях				Кодова комбінація ОНК
		перш ому	другому	третьому	четвертому
1	0,25	0,25	0,25	0,39	1	1
2	0,15	0,15	0,21	0,25		2
3	0,11	0,11	0,15	0,21		00
4	0,1	0,1	0,11	0,15		01
5	0,1	0,1	0,1			02
6	0,08	0,08	0,1			03
7	0,05	0,07	0,08			21
8	0,05	0,05				22
9	0,04	0,05				23
10	0,03	0,04				200
11	0,02					201
12	0,01					202
13	0,01					203

Тема: Побудова оптимального коду алфавіту. Оптимальний код Хаффмана.

Мета роботи: Опрацювання процедури кодування по методу Хаффмана.