Рівномірні і нерівномірні коди

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

До рівномірним кодами відноситься телеграфний код Бодо (Baudot code). Його можна вважати двійковим рівномірним алфавітним кодом. Початковий варіант цього коду розробив Еміль Бодо в 1870 році для свого телеграфу. Код вводився прямо клавіатурою, що складається з п'яти клавіш, натискання або ненажатом клавіші відповідало передачі або непередачі одного біта в пятібітном коді. Наприклад, буква А передавалася як - - + - -. що відповідало натискання середньої клавіші. У двійковому коді це можна записати як 00100. Таким чином, кожна буква записувалася п'ятьма бітами. Отже, кодом Бодо можна було передати 2 +5 = 32 різних символу.

Іншим цікавим прикладом рівномірного коду є код Трісіме, в якому знакам латинського алфавіту ставляться у відповідність кодові слова довжини 3 над алфавітом із 3-х символів:. Цей код представлений в наступній таблиці:

Зрозуміло, що код Трісіме не може кодувати понад 3 3 = 27 символів.

Число букв в алфавіті коду називається підставою коду, а довжина кодових слів рівномірного коду називається порядком коду. Коди з основою 2, як вже говорилося, називаються двійковими. а з підставою 3 - трійковими. і так далі. Так код Бодо має підставу 2, а порядок 5, а у коду Трісіме і підстава, і порядок рівні 3.

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

Типовим прикладом нерівномірного коду є телеграфний код, який прийнято називати азбукою Морзе. На наступній таблиці представлений код азбуки Морзе для українського алфавіту:

• - - • - •

Як бачимо, азбука Морзе складається зі слів над алфавітом із двох символів: точка і тире. Але, строго кажучи, цей код не є двійковим, так як він при кодуванні слів передбачає ще один символ для розділення букв в слові (символ «пауза»). Без цього символу не було б однозначності при декодуванні текстів. Наприклад, код з чотирьох тире можна було б декодувати по-різному: або як код однієї літери Ш, або як код поєднань з двох букв - ММ, ВІД або ТО. Розділяє символ дозволяє однозначно декодувати будь-яку кодову послідовність, отриману кодуванням повідомлень за допомогою азбуки Морзе, але тоді код азбуки Морзе слід вважати потрійним, так як його алфавіт містить три символи.

Американський винахідник телеграфу Семюель Морзе розробив цей код в 1838 році для передачі телеграфних повідомлень у вигляді послідовності електричних сигналів, які передаються від одного телеграфного апарату по дротах до іншого телеграфному апарату. Цей код був придуманий Морзе задовго до наукових досліджень

відносної частоти появи різних букв в текстах, але, тим не менш, Морзе при складанні коду використовував принцип частоти букв. Буквах, використовуваним частіше, їм присвоєні короткі кодові комбінації, рідко використовуваних буквах - довгі. Морзе оцінив відносну частоту букв англійської мови підрахунком літер в осередках друкарською складальної машини. Найбільш часто респонденти користуються послугами букві «Е» (в англійській мові) він привласнив найбільш короткий код «точка». Наступною за кількістю літер букві привласнила код кілька більшої тривалості і так далі.

При складанні азбуки Морзе для букв українського алфавіту облік відносної частоти букв не проводився, і це підвищило його надмірність. Розрахунки надмірності коду Морзе на підставі проведених досліджень частоти появи літер показали, що для букв англійського алфавіту вона становить 19%, для букв українського алфавіту 22%.

Самим знаменитим телеграфним повідомленням є сигнал лиха "SOS" (Save Our Souls - врятуйте наші душі). Ось як він виглядає: «• • • - - - • • •»

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

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

Наведемо більш простий приклад. Нехай S = 1, s2. ..., s7> - безліч повідомлень, кодування яких задається кодовими словами над алфавітом за допомогою функції F:

Цей код нерівномірний (кодові слова різної довжини).

Закодируем послідовність повідомлень: s7 s7. Маємо F (s7 s7) = B = 111111. Але ця послідовність може бути декодована і по-іншому, так як: B = F (s3 s3 s3) = F (s1 s3 s7) = F (s3 s7 s1) = F (s1 s1 s1 s1 s1 s1 s1 s). Як бачимо, способів декодування багато (підрахуйте: скільки їх?). Неоднозначно декодируется і наступна послідовність:

11011011 (а скільки тут способів декодування?). Очевидно, що такий код практично використовувати не можна. А якщо ми змінимо код так, щоб він став рівномірним, наприклад, довизначити функцію F так:

то тепер ніяких проблем з декодуванням не буде.