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

Від надмірності повідомлень і кодів, якими вони передаються, залежить максимальна кількість інформації, що може бути пе­редана по канапу за одиницю часу. Якщо повідомлення пере­даються алфавітом q, то максимальну кількість інформації на один елемент (символ, знак) повідомлення Η = logq можна діс­тати лише в разі його рівноймовірних і незалежних елементів. Реальні коди, які використовуються для кодування повідомлень, майже ніколи не задовольняють цю умову, тому що інфор­маційне навантаження кожного елемента їх, як правило, менше від того, яке вони могли б забезпечувати. Це свідчить про те, що повідомлення мають інформаційну надмірність.

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

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

Так, повідомлення: «До вечора наступного дня передати ін­формацію не зможемо у зв'язку з пошкодженням ліній, що з'єд­нують пункт збирання інформації з периферійними абонентськи­ми пунктами» без значної втрати цінності інформації можна було б сформулювати коротше: «Передача інформації затри­мується до вечора наступного дня у зв'язку з пошкодженням абонентських ліній», тобто перше повідомлення має семантичну надмірність відносно другого.

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

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

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

К_уш=Н/Н_max,

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

R_над=1- К_уш=1- Н/Н_max (3.5)

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

R_над=1- ,

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

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

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

R_{над зв}=1- Н/Н'

де Н= - ,

Н'= -

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

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

R_{над р} =1- Н/Н_max,

де Н_max =logq·

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

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

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

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

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

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

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

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

n≥ або n≥ ,

де Ν –кількість повідомлень, яку необхідно передати; q₁, q₂ – відповідно якісні ознаки первинного та вторинного алфавітів.

Так, для передачі N = 5 повідомлень двійковим кодом (q = 2) потрібно

n≥

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

R_{над окр}=

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

У даному випадку

,

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

Вираз

(5.6)

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

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

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

Поиск по сайту: