Кодування символьної інформації - MT1402 Теоретичні основи інформатики

Алфавітне нерівномірне двійкове кодування сигналами рівної тривалості. Префіксні коди

Як випливає з назви, у способах кодування, що належать до цієї групи, знаки первинного алфавіту (наприклад, українська) кодуються комбінаціями символів двійкового алфавіту (тобто 0 і 1), причому, довжина кодів і, відповідно, тривалість передачі окремого коду, можуть відрізнятися. Тривалості елементарних сигналів у своїй однакові %%(τ_0 = τ_1 = τ)%%. Очевидно, для передачі інформації, яка в середньому припадає на знак первинного алфавіту, потрібен час %%K(A,2) \cdot τ%%.

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

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

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

Як вона може бути декодована? Якби код був рівномірним, приймальний пристрій просто відраховував задане (фіксоване) числоелементарних сигналів (наприклад, 5, як у коді Бодо) та інтерпретувало їх відповідно до кодової таблиці. При використанні нерівномірного кодування можливі два підходи до забезпечення помітності кодів. Перший полягає у використанні спеціальної комбінації елементарних сигналів, що інтерпретується декодером як роздільник знаків. Другий – у застосуванні префіксних кодів. Розглянемо докладніше кожен із підходів.

Нерівномірний код із роздільником

Умовимося, що роздільником окремих кодів букв буде послідовність 00 (ознака кінця знака), а роздільником слів-слів - 000 (ознака кінця слова - пробіл). Досить очевидними виявляються такі правила побудови кодів:

код ознаки кінця знака може бути включений до коду літери, оскільки не існує окремо (тобто коду всіх букв будуть закінчуватися 00);
коди букв не повинні містити двох і більше нулів поспіль у середині (інакше вони сприйматимуться як кінець знака);
код літери (крім пропуску) завжди повинен починатися з 1;
роздільнику слів (000) завжди передує ознака кінця знака; при цьому реалізується послідовність 00000 (тобто якщо в кінці коду зустрічається комбінація . 000 або . 0000, вони не сприймаються як роздільник слів); отже, коди літер можуть закінчуватися на 0 чи 00 (до кінця кінця знака).

Відповідно до перерахованих правил побудуємо кодову табл. 3.1 для букв українського алфавіту, ґрунтуючись на наведених раніше (табл. 2.1.) ймовірностях появи окремих букв.

Тепер можна знайти середню довжину коду (r,2) для даного способу кодування:

Оскільки для української мови, %%I_1(r) = 4,356 біт%%, надмірність цього коду згідно (3.5) становить:

це означає, щопри даному способі кодування передаватиметься приблизно на 14% більше інформації, ніж містить вихідне повідомлення. Аналогічні обчислення для англійської мови дають значення %%К(e,2) = 4,716%%, що при %%I_1(e) = 4,036%% біт призводять до надмірності коду %%Q(e,2) = 0,168%%.