Оптимальне кодування повідомлень (стиск інформації)

Найбільш ефективним методом зменшення надлишковості повідомлень є побудова оптимальних кодів.

Оптимальні коди – це коди з практично нульовою надлишковістю. Оптимальні коди мають мінімальну середню довжину кодових слів L. Верхня та нижня межа L визначаються нерівністю:

Н/log m  L  Н/log m+1

де Н – ентропія первинного алфавіту, m - кількість якісних ознак вторинного алфавіту.

Слід зазначити, що довжини кодових комбінацій оптимального коду за умови різних імовірностей надходження повідомлень, як правило, є різними, тому такі коди називають оптимальними нерівномірними кодами (ОНК).

Одна з методик побудови ОНК була запропонована К. Е. Шенноном та Р. Фано (методика Шеннона-Фано). Побудова ОНК згідно методиці Шеннона-Фано передбачає виконання наступної послідовності дій:

1. всі елементи (літери, повідомлення) розташовуються в порядку зменшення імовірностей;

2. множина впорядкованих елементів поділяється на дві частини таким чином, щоб суми імовірностей повідомлень, які складають кожну підмножину, були приблизно рівними (при цьому елементи кожної підмножини повинні бути розташовані в сформованому переліку послідовно і порядок їх слідування ні в якому разі не змінюється);

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

4. виконання пунктів 2 та 3 повторюється для сформованих на попередньому етапі підмножин (кожна з підмножин, яка складається більше ніж з одного елемента, знов поділяється на дві і т.д.) до отримання N підмножин, кожна з яких складається з одного елемента (N дорівнює числу елементів).

Приклад 4.1. Побудувати за методикою Шеннона-Фано ОНК для передачі повідомлень, що складаються з літер А, Б, В, Г, Д, Е. Імовірності появи літер в повідомленні дорівнюють: р_А=0.25; р_Б=0.2; р_В=0.1; р_Г=0.05; р_Д=0.15; р_Е=0.25.

Розв’язок.

Порядок формування ОНК за методикою Шеннона-Фано відображено в табл.2.3.1 (в табл.2.3.1 підкреслено символи, які додаються до кодових комбінацій на кожному етапі їх формування, а напівжирним шрифтом виділені сформовані кодові комбінації).

Таблиця 4.1.

Етап 1		Етап 2			Етап 3			Етап 4			Етап 5
Літера	рліт	рліт	р	К о д	рліт	р	К о д	рліт	р	К о д	рліт = р	К о д
А	0.25	0.25	0.5	0	0.25	0.25	00
Е	0.25	0.25		0	0.25	0.25	01
Б	0.2	0.2	0.5	1	0.2	0.2	10
Д	0.15	0.15		1	0.15	0.3	11	0.15	0.15	110
В	0.1	0.1		1	0.1		11	0.1	0.15	111	0.1	1110
Г	0.05	0.05		1	0.05		11	0.05		111	0.05	1111

Згідно з методикою на першому етапі впорядковуємо символи в порядку зменшення імовірностей.

На другому етапі впорядковану множину літер {А,Е,Б,Д,В,Г} розбиваємо на дві підмножини з приблизно рівними значеннями сумарних імовірностей. Отримуємо підмножини літер {А,Е} та {Б,Д,В,Г}, сумарні імовірності символів для яких дорівнює 0.5 (р_А+р_Е=р_Б+р_В+р_Д+р_Г=0.5). Елементам першої підмножини (літерам А та Е) в якості першого розряду (він стає старшим) ставимо у відповідність символ 0, а елементам другої підмножини (літерам Б, Д, В та Г) – символ 1.

На третьому етапі обидві отримані множини знов розбиваються на підмножини. Множина {А,Е} розбивається на підмножини {А} та {Е}(р_А=р_Е=0.25); до коду літери А в якості другого розряду додаємо символ 0, а для літери Е - символ 1. Множину {Б,Д,В,Г} ділимо на підмножину {Б} (р_Б=0.2) та підмножину {Д,В,Г} (р_Д+р_В+р_Г=0.3); літері Б в якості другого розряду ставимо у відповідність 0, а літерам В, Г і Д – 1. При цьому слід зазначити, що, хоча розбиття множини {Б,Д,В,Г} на підмножини {Б,Г} і {Д,В} дає однакові сумарні імовірності елементів підгруп (р_Б+р_Г=р_Д+р_В=0.25), таке розбиття неприпустиме, оскільки літери Б і Г в сформованому переліку розташовані не послідовно.

Оскільки перші три отримані множини {А}, {Е} і {Б} складаються з однієї літери кожна, розділити на підмножини їх неможливо (це означає, що коди літер А, Е та Б сформовано). Тому на четвертому етапі за аналогічною методикою на підмножини {Д} та {В,Г} розбивається множина {Д,В,Г}.

На п’ятому етапі множина {В,Г} розбивається на підмножини {В} та {Г}, яким присвоюються значення 0 та 1 відповідно, після чого процес кодування завершується, оскільки підмножини, які складаються більше ніж з одного стану, відсутні.

Таким чином кодові комбінації ОНК для кодування літер повідомлень будуть наступні: А-00; Б-10; В-1110; Г-1111; Д-110; Е-01.

Примітка 4.1. В процесі побудови ОНК можуть виникати ситуації, коли декільком різним символам відповідають однакові імовірності (див. приклад 4.1: символи А та Е). Хоча це не є принциповим, для однозначності умовимось впорядковувати такі символи за алфавітом (для літерних символів) або в порядку зростання значення (для цифрових символів).

Примітка 4.2. Вихідні дані для задач формування ОНК можуть бути надані не лише характерним розподілом імовірностей появи символів (літер; цифр), а й у вигляді послідовності символів або кількістю символів в повідомленні. В таких випадках перед формуванням ОНК слід визначити імовірності входження кожного символу до повідомлення (як відношення кількості входжень певного символу до загальної кількості символів).

Приклад 4.2. Побудувати за методикою Шеннона-Фано ОНК для передачі повідомлення: 1234123121.

Розв’язок.

Перед тим, як приступити до побудови ОНК, визначимо імовірності надходження різних елементів, характерні для наведеного повідомлення. Отримуємо: р₁=4/10; р₂=3/10; р₃=2/10; р₄=1/10. Порядок формування ОНК за методикою Шеннона-Фано відображено в табл.2.3.2.

Таблиця 4.2.

Етап 1		Етап 2			Етап 3			Етап 4
Літера	рліт	рліт	р	К о д	рліт	р	К о д	рліт	р	К о д
1	4/10	4/10	4/10	0
2	3/10	3/10	6/10	1	3/10	3/10	10
3	2/10	2/10		1	2/10	3/10	11	2/10	2/10	110
4	1/10	1/10		1	1/10		11	1/10	1/10	111

Таким чином кодові комбінації ОНК для кодування повідомлення будуть наступні: “1”-0; “2”-10; “3”-110; “4”-111.

Однією з основних переваг методики Шеннона-Фано є простота реалізації, але в ході формування ОНК за цією методикою можуть виникати ситуації, коли існує можливість розподілу множини на дві частини з приблизно рівними сумами імовірностей повідомлень двома способами. Так, наприклад, для імовірностей р₁=0.4 та р₂=р₃=р₄=0.2 множину {1,2,3,4} можна розбити на підмножини {1} (р₁=0.4) та {2,3,4} (р₂+р₃+р₄=0.6) або на підмножини {1,2} (р₁+р₂=0.6) та {3,4} (р₃+р₄=0.4). Оскільки методика Шеннона-Фано не визначає правил розв’язання таких ситуацій, це призводить до виникнення неоднозначності.

Примітка 4.3. В ситуації, коли існує можливість розподілу множини на дві частини з приблизно рівними сумами імовірностей повідомлень двома способами, для усунення неоднозначності домовимось обирати варіант, при якому першій підмножині відповідає менша сумарна імовірність елементів.

Зазначений недолік призвів до розробки Хаффменом вдосконаленої методики побудови ОНК, яка отримала назву методики Шеннона-Фано-Хаффмена або просто методики Хаффмена. Побудова ОНК згідно методики Хаффмена передбачає виконання наступної послідовності дій:

1. всі елементи (літери, повідомлення) розташовуються в порядку зменшення імовірностей (так саме, як і за методикою Шеннона-Фано);

2. останні два елементи впорядкованої множини (цим елементам повинні відповідати найменші значення імовірностей) замінюються допоміжним елементом, значення імовірності для якого визначається як сума імовірностей елементів, що замінюються;

3. всі елементи отриманої множини (після заміни двох елементів одним допоміжним) повторно розташовуються в порядку зменшення імовірностей;

4. виконання пунктів 2 та 3 повторюється до отримання єдиного допоміжного елемента, сумарна імовірність появи якого дорівнює 1.

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

Більш наочним є формування кодових комбінацій на підставі кодового дерева.

Побудова кодового дерева та визначення комбінацій ОНК з його допомогою виконується за наступними правилами:

1. коренева вершина дерева співставляється з останнім отриманим допоміжним елементом (елементом, якому відповідає сумарна імовірність, що дорівнює 1);

2. гілки кодового дерева формуються в послідовності, зворотній проходженню процесу об’єднання елементів. З кореневої вершини дерева відводяться дві гілки, з кінцевими вершинами яких співставляються елементи, об’єднання яких дозволило отримати елемент з сумарною імовірністю 1. При цьому з кінцевою вершиною лівої гілки співставляється елемент, що знаходиться в таблиці у вищому рядку (як правило, це елемент з більшою імовірністю), а з кінцевою вершиною правої гілки - розташований в таблиці в нижньому рядку;

3. процес нарощування гілок продовжується до отримання дерева, кінцевим вершинам якого відповідають елементи вихідного алфавіту;

4. після закінчення побудови кодового дерева виконується співставлення його гілкам символів коду: гілкам, які відгалужуються з вершин вліво, ставиться у відповідність символ 0; гілкам, які відгалужуються з вершин вправо, ставиться у відповідність символ 1;

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

Отриманий за наведеною методикою код буде задовольняти вимозі оптимальності.

Примітка 4.4. Окрім наявності символів з однаковою імовірністю в первинному алфавіті, порядок упорядкування яких було визначено в примітці 4.1, при утворенні допоміжних елементів за методикою Хаффмена їх імовірності можуть дорівнювати імовірностям існуючих елементів. Для однозначності умовимось в процесі упорядкування останній отриманий допоміжний символ ставити в переліку після всіх символів з таким самим значенням імовірності, які існували раніше.

Розглянемо приклад побудови ОНК за методикою Хаффмена.

Приклад 4.3. Побудувати ОНК для передачі повідомлень, що складаються з літер А, В, С, D, Е, F. Імовірності появи літер в повідомленні дорівнюють: р_А=1/2; р_В=1/4; р_С=1/8; р_D=1/16; р_Е=1/32; р_F=1/32.

Розв’язок.

Згідно з методою побудови ОНК за методом Хаффмена впорядковуємо символи за принципом зменшення імовірностей. Отримуємо: А, В, С, D, Е, F (р_А=1/2; р_В=1/4; р_С=1/8; р_D=1/16; р_Е=1/32; р_F=1/32). Впорядковані символи та процес формування допоміжних символів відображено в табл. 4.3 (символи, що об’єднуються в допоміжний символ на кожному етапі, та їх імовірності виділені в табл. 4.3 напівжирним шрифтом).

Таблиця 4.3.

Вихідні дані		Об’єднання символів
		Етап 1		Етап 2		Етап 3		Етап 4		Етап 5
Символ	рсим	Символ	рсим	Символ	рсим	Сим-вол	рсим	Сим-вол	рсим	Символ	рсим
A	1/2	A	1/2	A	1/2	A	1/2	A	1/2	ABCDEF	1
B	1/4	B	1/4	B	1/4	B	1/4	BCDEF	1/2
C	1/8	C	1/8	C	1/8	CDEF	1/4
D	1/16	D	1/16	DEF	1/8
E	1/32	EF	1/16
F	1/32

На першому етапі об’єднуємо два останні символи Е та F в допоміжний символ ЕF, імовірність появи якого умовно приймається рівною р_ЕF=р_Е+р_F=1/32+1/32=1/16. Після упорядкування символів в порядку зменшення імовірностей отримуємо оновлений перелік: А, В, С, D, ЕF (р_А=1/2; р_В=1/4; р_С=1/8; р_D=1/16; р_Е=1/16).

На другому етапі об’єднуємо два останні символи D та ЕF в допоміжний символ DЕF, імовірність появи якого умовно приймається рівною р_DEF=р_D+р_EF=1/16+1/16=1/8.

Процес продовжується аналогічним чином до отримання допоміжного символа ABCDEF з сумарною імовірністю 1.

Виконаємо формування ОНК на підставі кодового дерева.

Згідно з табл. 4.3 визначаємо символ ABCDEF, який має імовірність появи 1 і, відповідно, співставляється кореневій вершині дерева (див. рис. 4.1). З кореневої вершини відводяться дві гілки з кінцевими вершинами A та BCDEF. Лівій гілці ставимо у відповідність значення 0, а правій – значення 1.

Оскільки кінцева вершина лівої гілки дерева відповідає літері А, яка є елементом початкового алфавіту, а не допоміжним символом, побудова цієї гілки завершується.

З вершини допоміжного символу BCDEF відводяться дві гілки з кінцевими вершинами B та CDEF. Лівій гілці ставимо у відповідність значення 0; правій – значення 1.

Додавання гілок до дерева продовжуємо до отримання всіх кінцевих вершин, які відповідають символам, що кодуються. Повністю побудоване кодове дерево наведене на рис. 4.1.

Проаналізуємо кодове дерево для визначення комбінацій ОНК.

Від кореневої вершини до кінцевої вершини А веде одна гілка ABCDEF-А. Їй відповідає значення 0, яке і є кодом символу А.

Від кореневої вершини до кінцевої вершини В веде послідовність з двох гілок ABCDEF-BCDEF-В, яким відповідають значення 1 та 0. Код символу В дорівнює 10.

Подальший аналіз дозволяє отримати кодові комбінації символів, наведені в таблиці 4.4.

Таблиця 4.4.

Символ алфавіту	Імовірність входження символу в повідомлення	Код символу
A	1/2	0
B	1/4	10
C	1/8	110
D	1/16	1110
E	1/32	11110
F	1/32	11111

Проілюструємо спосіб формування ОНК без побудови кодового дерева. Вихідними даними при цьому є відомості табл. 4.3. Процес формування кодових комбінацій ОНК відображено в таблиці 4.5.

Для побудови ОНК розпочинаємо зворотній аналіз виконаних в табл. 4.3 об’єднань. Двом останнім символам (А та ВСDЕF), при об’єднанні яких було отримано символ з імовірністю 1 (АВСDЕF), присвоюються значення коду 0 (символу А) та 1 (символу ВСDЕF).

Раніше (в табл. 4.3) символ ВСDЕF був отриманий об’єднанням символів В та СDЕF. Згідно з вживаною методикою символу В присвоюється значення коду 0 (дописується в молодші розряди до присвоєного на попередньому етапі символу ВСDЕF значення коду 1, тобто код символу прийме значення 10), а символу СDЕF - значення коду 1 (тобто код символу прийме значення 11).

Таблиця 4.5.

Результат		Об’єднання символів
Етап 10		Етап 9		Етап 8		Етап 7		Етап 6
Символ	Код	Символ	Код	Символ	Код	Сим-вол	Код	Символ	Код	Символ
A	0	A	0	A	0	A	0	A	0	ABCDEF
B	10	B	10	B	10	B	10	BCDEF	1
C	110	C	110	C	110	CDEF	11
D	1110	D	1110	DEF	111
E	11110	EF	1111
F	11111

Подальший аналіз дозволяє отримати кодові комбінації символів, наведені в таблиці 4.4.

Примітка 4.5. Побудова ОНК за методикою Хаффмена без використання кодового дерева характеризується меншою наочністю і потребує більшої уваги, що, як показує практика, призводить до збільшення помилок при вирішенні таких задач студентами. З цієї причини рекомендується використовувати при вирішенні завдань для засвоєння матеріалу саме спосіб кодування з використанням кодового дерева.

На завершення наведемо основні ознаки, за якими можливо оцінити правильність побудови ОНК без перевірки всієї послідовності операцій його формування (така перевірка не гарантує, що розглянутий код обов’язково є оптимальним, але дозволяє швидко виявити найбільш типові помилки). Ці ознаки базуються на основних вимогах, яким повинен відповідати ОНК:

• довжина кодових комбінацій ОНК повинна бути пропорційна вміщуваній в повідомленні інформації, тобто в жодному разі повідомленню з меншою імовірністю надходження не може відповідати кодова комбінація меншої довжини;

• ОНК повинен відповідати умові неприводимості, тобто жодна кодова комбінація не повинна бути початком іншої кодової комбінації (це правило забезпечує можливість розрізнення символів в повідомленні).

Приклад 4.4. Без повторної побудови коду перевірити, чи може він використовуватись в якості ОНК для передачі повідомлень, що складаються з літер А, В, С, D. Імовірності появи літер в повідомленні дорівнюють р_А=0.2; р_В=0.15; р_С=0.4; р_D=0.25. Співставлені літерам кодові комбінації мають значення: А=00; В=101; С=01; D=1.

Розв’язок.

Для перевірки коду на відповідність умовам оптимальності упорядкуємо літери та їх кодові комбінації за зменшенням імовірностей надходження. Упорядковані дані представлені в табл.4.6.

Аналіз характеру розподілу імовірностей надходження літер повідомлень в сукупності з аналізом довжин співставлених кодових комбінацій (див. табл.4.6) дозволяє зробити висновок, що запропонований код не може бути використаний як ОНК при наведених умовах, оскільки кодова комбінація літери D при меншій імовірності надходження має меншу довжину, ніж кодова комбінація літери C, що порушує умову пропорційності довжини кодової комбінації кількості вміщуваної інформації.

Таблиця 4.6.

Символ алфавіту	Імовірність входження символу в повідомлення	Код символу
C	0.4	01
D	0.25	1
A	0.2	00
B	0.15	001

Крім того, даний код не може бути ОНК, оскільки кодова комбінація літери А є початком кодової комбінації літери B, що порушує умову неприводимості коду. Внаслідок цього кодові послідовності повідомлень “ВАDC” та “ВBC” будуть мати однаковий вигляд “00100101”, що призводить до можливості неоднозначного декодування повідомлень.

Примітка 4.6. В ряді випадків (наприклад, через неповноту статистичних даних) сумарна імовірність появи символів, які аналізуються, може бути меншою 1. При побудові ОНК за методикою Хаффмена в таких випадках формування допоміжних символів продовжується до отримання одного символа, імовірность появи якого дорівнює сумі імовірностей появи всіх символів вихідного алфавіту (цей символ в подальшому співставляється кореневій вершині кодового дерева). Зазначимо, що кодування за таких умов може впливати на достовірність отриманого результату.