Згідно з формулою (3.1) визначаємо абсолютне недовантаження двійкового шестирозрядного повідомлення:

D=(6-5.02)=0.98 біт/повідомлення .

Приклад 3.2. Визначити інформаційну надлишковість повідомлення, характеристики якого наведено в прикладі 3.1.

Розв’язок.

В прикладі 3.1 нами були визначені наступні значення ентропії:

Н_макс= 6 біт/повідомлення;

Н = 5.02 біт/повідомлення.

Згідно формулою (3.2) визначимо інформаційну надлишковість повідомлення:

D=1-5.02/6=0.16 .

Приклад 3.3. Нехай нам необхідно закодувати двійковим кодом для передачі через послідовний канал зв’язку текст “АРАРАТ.”. Кодування слід виконати співставленням комбінації коду кожному символу тексту (кожний символ тексту при цьому розглядається як окреме повідомлення). Метою кодування є максимальна ефективність використання ресурсів систем передачі інформації, тобто мінімізація довжини сформованого коду (в цілому для всього тексту).

Розв’язок.

Текст “АРАРАТ.” складається з чотирьох символів: “А”, “Р”, “Т” та “.”. Це означає, що кількість повідомлень в нашому випадку N=4. Кількість якісних ознак двійкового коду m=2. За аналогією з прикладом 1.2 отримуємо n -значення кількості символів в повідомленні (не враховуючи розподілу імовірностей надходження повідомлень):

n = log_m N = log₂ 4 = 2 .

Таким чином, для кодування чотирьох літер відповідні повідомлення повинні містити по 2 двійкових розряди. Одним з можливих варіантів такого коду може бути наступний: “А” – 00; “Р” – 01; “Т” – 10; “.” – 11. При цьому кодова послідовність, яку слід передати для передачі всього тексту “АРАРАТ.”, буде мати вигляд:

0 0 0 1 0 0 0 1 0 0 1 0 1 1

( А Р А Р А Т .)

Всього наведена кодова послідовність складається з 14 двійкових розрядів, тобто з 7 дворозрядних повідомлень.

Розглянемо інший спосіб кодування. Для цього співставимо літерам тексту кодові комбінації різної довжини, а саме: “А” – 0; “Р” – 10; “Т” – 110; “.” – 111 (при визначенні значень кодових комбінацій було використано один з методів побудови оптимальних нерівномірних кодів, які будуть розглядатися далі). Кодова послідовність, яку слід передати для передачі тексту, при такому способі кодування буде мати вигляд:

0 1 0 0 1 0 0 1 1 0 1 1 1

( А Р А Р А Т . )

Якщо спосіб кодування символів відомий декодуючій стороні, порозрядний аналіз отриманої двійкової кодової послідовності, починаючи з старшого розряду (з ліва на право), дозволяє легко виділити кодові комбінації символів повідомлення. Наприклад, самий старший розряд кодової послідовності дорівнює 0, що відповідає кодовій комбінації символу “А”; наступний (другий) розряд дорівнює 1 і не має аналога серед кодових комбінацій, тому його розглядаємо в сукупності з третім розрядом, що дає нам кодову комбінацію 10 - символ “Р” і т.д.). Таким чином, нами отримано спосіб кодування, який дозволяє легко відновити початковий вигляд закодованого тексту без втрат та потребує передачі лише 13 двійкових розрядів. В наведеному прикладі це дозволяє скоротити довжину кодової послідовності в порівнянні з попереднім варіантом на 7%.

Приклад 3.4. Порівняти показники абсолютного недовантаження та інформаційної надлишковості для рівномірного та нерівномірного способу кодування повідомлення “АРАРАТ.”, наведених в прикладі 3.3.

Розв’язок.

Визначимо імовірності надходження символів повідомлення “АРАРАТ.”. Отримуємо: р_А=3/70.43; р_Р=2/70.29; р_Т=р_.=1/70.14.

Оскільки показник Н не залежить від особливостей вторинного алфавіту (довжини сформованих кодових комбінацій), за умови нерівномірного розподілу імовірностей надходження символів повідомлення “АРАРАТ.” його значення розраховуємо за формулою (2.1):

Н =-(р_А log₂ р_А + р_р log₂ р_Р + р_Т log₂ р_Т + р_. log₂ р_.)=

=-(0.43 log₂ 0.43 + 0.29 log₂ 0.29 + 2*0.14 log₂ 0.14)=

= 0.43*1.23+0.29*1.79+2*0.14*2.82  1.837 біт/символ .

Для розрахунку значення Н_макс з прикладу 3.3 визначимо довжини кодових комбінацій для обох способів кодування. Для кодування рівномірним кодом отримуємо: l_А=l_Р=l_Т=l_.=2. Для кодування нерівномірним кодом отримуємо: l_А=1; l_Р=2; l_Т=l_.=3.

Значення Н_макс розраховуємо згідно з формулою (3.3), яка для нашого прикладу буде мати вигляд:

Н_макс= р_А l_А + р_р l_Р + р_Т l_Т + р_. l_. .

Для кодування рівномірним кодом отримуємо:

Н_макс= 0.43*2+0.29*2+0.14*2+0.14*2 = (0.43+0.29+0.14+0.14)*2 =2 біта/символ .

Для кодування нерівномірним кодом отримуємо:

Н_макс= 0.43*1+0.29*2+0.14*3+0.14*3 = 1.85 біт/символ .

Згідно з формулою (3.1) визначаємо абсолютне недовантаження на символ повідомлення для обох способів кодування:

D_{рівном.} = ( 2 –1.837 )=0.163 біт/символ ;

D_{нерівном.} = ( 1.85 –1.837 )=0.013 біт/символ .

Згідно з формулою (3.2) визначаємо показник надлишковості для обох способів кодування:

D_{рівном.} = ( 2 –1.837 )/2  0.082 ;

D_{нерівном.} = ( 1.85 –1.837 )/1.85  0.007 .

Як видно з проведеного дослідження, використання нерівномірного коду при кодуванні символів повідомлення “АРАРАТ.” замість рівномірного коду дозволяє значною мірою зменшити показники абсолютного недовантаження на символ повідомлення та інформаційної надлишковості.

Приклад 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.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.

Приклад 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.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”, що призводить до можливості неоднозначного декодування повідомлень.