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

Від надмірності повідомлень і кодів, якими вони передаються, залежить максимальна кількість інформації, що може бути пе­редана по каналу за одиницю часу.

Розрізняють два види надмірності: природну та штучну. Пер­шою описується надмірність первинних алфавітів, а другою - вторинних. Природна надмірність поділяється на семантичну та статистичну.

Семантична надмірність випливає з того, що будь-яку дум­ку, яка міститься в повідомленні, можна висловити коротше.

Є багато способів усунення семантичної надмірності: замі­ною деяких типових повідомлень, які зустрічаються досить часто, умовними позначеннями; введенням таблиць, куди за­носяться характерні елементи повідомлення; застосуванням ско­рочень тощо.

Статистична надмірність спричинена нерівномірним розпо­ділом якісних ознак первинного алфавіту та взаємозалежністю їх. Це можна побачити на прикладі англійського алфавіту, що містить 26 літер. Максимальне значення ентропії англійського алфавіту H_mах = 1оg₂ q = lоg₂ 26 = 4,7 біт. Проте у зв'язку з тим, що ймовірність появи літер англійського алфавіту не од­накова, ентропія англійської мови значно менша ніж 4,7 біт і без урахування взаємозалежності між словами становить приб­лизно 2,35 біт.

Якщо ж урахувати дійсну частоту появи літер у текстах, різ­них сполученнях і слів у різних повідомленнях, то інформацію, що передається, можна значно скоротити, стиснути. Коефіцієнт ущільнення інформації визначається виразом

K _ущ = Н/Н _mах,

а надмірність - виразом

R _над = 1 – К _ущ = 1 - Н/Н _mах. (5.3)

Із (5.3) випливає, що для зменшення надмірності повідом­лення необхідно збільшити ентропію первинного алфавіту.

Для англійської мови

R _над

тобто можна відновити зміст англійських текстів, складених з 50 % алфавіту.

До видів статистичної надмірності алфавітів належать такі поняття, як надмірність R _над.зв, зумовлена статистичним зв'яз­ком між елементами повідомлення, та надмірність R _над.р, спри­чинена нерівноймовірним розподілом елементів у повідомленні.

Надмірність R _над.зв вказує на інформаційний резерв повідом­лень із взаємозалежними елементами відносно повідомлень, які мають статистичний зв'язок між елементами:

R _над.зв = 1 - Н/Н ',

де

Тут Н' теж має надмірність через нерівномірний розподіл імовірностей окремих елементів алфавіту.

Надмірність Н _над.рвказує на інформаційний резерв повідом­лень, елементи яких нерівноймовірні:

R _над.р = 1 – Н/Н _mах.

де .

Повна статистична надмірність алфавіту визначається ви­разом

R _над = R _над.зв + R _над.р - R _над.зв R _над.р.

При незначних R _над.зв і R _над.р цей вираз набуває вигляду

R _над = R _над.зв + R _над.р,

тому що зі зменшенням R _над.зв і R _над.р добуток їх прямує до нуля.

Для усунення статистичної надмірності алфавітів викорис­товують оптимальні нерівномірні коди; при цьому статистична надмірність первинного алфавіту значно зменшу­ється завдяки більш раціональній побудові повідомлень у вто­ринному алфавіті.

Так, при передачі десяткових чисел двійковим кодом трьо­ма двійковими розрядами можна передати і цифру 5, і цифру 8, тобто для передачі п'яти та восьми повідомлень треба мати коди однакової довжини.

Довжина комбінації двійкового коду визначається виразом

або

де N - кількість повідомлень, яку необхідно передати; q ₁, q ₂ - відповідно якісні ознаки первинного та вторинного алфавітів. Так, для передачі N = 5 повідомлень двійковим кодом (q = 2)потрібно

двійкових символів.

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

де К - округлене до найближчого цілого значення К _над =

У даному разі

що характеризує недовантаженість коду.

Вираз

(5.4)

можна застосувати для визначення довжини кодів з рівноймовірними та взаємонезалежними елементами. Для двійковою коду (q = 2)цей вираз дійсний тільки тоді, коли ймовірність, появи 0 та 1 однакові. Проте в рівномірних кодах, як правило, нулі зустрічаються частіше, ніж одиниці. Тому надмірність, закладену в природу коду, повністю усунути не можна. Однак надмірність від нерівноймовірності появи елемента та надмірність від округлення зменшуються зі збільшенням довжини ко­дового блока.

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

- відносну коректувальну надмірність коду.

 

Оптимальне кодування

У теорії інформації існує кілька методик побудови оптималь­них з точки зору швидкості передачі інформації безнадмірних кодів.

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

Оптимальним кодуванням називається про­цедура перетворення символів первинного алфавіту q ₁на ко­дові комбінації вторинного алфавіту q ₂,при якій середня дов­жина повідомлення у вторинному алфавіті мінімальна.

Основним завданням оптимального кодуван­ня є досягнення рівності між кількістю інформації І, що вироб­ляється джерелом повідомлень, та обсягом інформації Q на вхо ді приймача повідомлень.

Перша універсальна методика побудови ОНК ґрунтується па методиці Шеннона - Фано і передбачає цю побудову вкодовому алфавіті з кількістю якісних значень q. Згідно з цією методикою виконують такі процедури:

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

2) впорядковані за ймовірностями повідомлення розбивають, по можливості, на q рівноймовірних груп;

3) кожній з груп завжди в одній і тій самій послідовності при­своюють символи алфавіту q (всім повідомленням першої гру­пи - першу якісну ознаку цього алфавіту, всім повідомленням другої групи - другу якісну його ознаку тощо);

4) створені групи розбивають, по можливості, на рівноймовірні підгрупи, кількість яких дорівнює або менша ніж q (якщо після розбивання в групі залишається одне повідомлення, то подальший поділ стає неможливим);

5) кожній з утворених підгруп присвоюють якісні ознаки з алфавіту q за процедурою п.3;

6) розбивання та присвоєння ознак алфавіту q повторюють доти, поки після чергового поділу в утворених підгрупах зали­шиться не більш як одне повідомлення.

Друга універсальна методика побудови ОНКґрунтується на відомій методиці Хаффмена. Згідно з цією методикою викону­ють такі процедури:

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

2) останні N ₀повідомлень (2 ≤ N ₀ ≤ q)об'єднують у нове по­відомлення з імовірністю, що дорівнює сумі ймовірностей об'єд­нуваних повідомлень;

3) утворену множину (N - N ₀ + 1) повідомлень розташову­ють у порядку спадання ймовірностей;

4)об'єднують останні q повідомлень і впорядковують множи­ну повідомлень у порядку спадання ймовірностей. Так діють доти, доки ймовірність чергового об'єднаного повідомлення не дорівнюватиме одиниці;

5) будують кодове дерево, починаючи з кореня, і гілкам цього дерева присвоюють якісні ознаки кодового алфавіту q.

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

Для того щоб перевірити оптимальність коду відносно довжини
кодових комбінацій, визначаємо середню довжину п _серкодової комбіна­ції ОНК. У разі оптимальності ця довжина не повинна перевищувати
довжину рівномірного четвіркового коду, яким можна закодувати 16 по­відомлень, тобто qⁿ = 4² = 16 (n = 2):

Таким чином, утворений код дійсно оптимальний, оскільки n _сер < п.

 

Приклад

Побудувати двійковий ОНК Шеннона — Фано і Хаффмена для восьми пові­домлень джерела з імовірностями Р (х ₁)= 0,3; Р (х₂) = 0,2; Р (х ₃) = 0,15; Р (х ₄)= 0,12; Р (х ₅) = 0,1; Р (х ₆) = 0,08; Р (х ₇) = 0,03; Р (х ₈)= 0,02.

Розв'язання. Користуючись першою універсальною методикою побудови ОНК, будуємо заданий код (табл. 5.2).

 

 

Таблиця 5.2 – Побудова ОНК за першою методикою

 

 

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

n _сер= 2(0,3 + 0,2) + 3(0,15 + 0,12 + 0,1) + 4 · 0,08 + 5(0,03 + 0,02) =

= 1 + 1,11 + 0,32 + 0,25 = 2,68 < 3,

тобто код оптимальний.

Користуючись другою універсальною методикою побудови ОНК будуємо заданий код (табл. 5.3).

 

 

Таблиця 5.3 – Побудова ОНК за другою методикою

 

В таблиці використовуємо суму імовірності повідомлення останніх номерів так:

0,03 + 0,02 = 0,05;

0,12 + 0,1 + 0,08 + 0,05 = 0,13;

0,12 + 0,1 = 0,22; 0,22+ + 0,2 = 0,42;

0,58 + 0,42 = 1.

Будуємо кодове дерево, що має вигляд, зображений на рис. 5.4.

Рисунок 5.4 – Побудова кодового дерева для утвореного коду

 

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

n _сер = 2(0,3 + 0,2) + 3(0,15 + 0,12 + 0,1) + 4 · 0,08 + 5 (0,03 + 0,02) =

= 1 + 1,11 + 0,32 + 0,25 = 2,68 < З,

тобто код оптимальний.

 

 

Кодування повідомлень

 

Повідомлення, що надходять від первісних джерел, як правило, кодуються. Кодування застосовується як для спрощення оброблення повідомлень, так і для підвищення завадостійкості їх передачі по лініях і в каналах зв’язку, де спотворюються сигнали, що спричиняє появу помилок у повідомленнях.

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