5.7 Класифікація (двійкових) кодів

За кількістю дозволених кодових комбінацій коди поділяють на ненадлишкові (коли ) й надлишкові (коли < ) . Тут – кількість дозволених кодових комбінацій (тих, що застосовані для кодування символів повідомлень).

5.7.1. Ненадлишкові коди

В ненадлишкових кодах дозволені всі можливі кодові комбінації N₀, що можуть бути складені з n двійкових розрядів (біт), тобто загальна кількість кодових комбінацій дорівнює числу поєднань з двох кодових символів по n штук (N₀=2ⁿ). Тому будь-яке перекручування через перешкоди одного з кодових символів в кодовому слові викликає помилку, тому, що кодове слово перетворюється в деяке інше допустиме кодове слово. Таким чином приймач прийме повідомлення з помилкою. Тобто ненадлишкові коди не дозволяють виявляти помилки.

Ненадлишкові коди бувають рівномірні і нерівномірні.

В рівномірних кодах усі кодові комбінації мають однакову довжину і тому при передачі повідомлень не потрібно відокремлювати одну кодову комбінацію від іншої.

Прикладом рівномірного коду є телеграфний код, за допомогою якого передають 32 символи кириліці. Код має основу m=2, загальна кількість кодових слів N₀=2⁵=32_, довжина кодового слова n=log32=log2⁵=5 біт.

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

В комп’ютерних мережах використовується восьмирозрядний двійковий код (n=8 біт, N₀=2⁸=256). Однак вже відчутна нестача кодових слів для кодування символів у 8‑розрядних ЕОМ.

Виникає проблема кодування символів національних алфавітів. Двохсот п’ятдесяти шести символів недостатньо для того, щоб закодувати усі необхідні символи повідомлень. У зв’язку з цим, кодами деяких основних символів кодуються додаткові символи національних алфавітів, а при розкодуванні утворюються неоднозначності. Ця проблема особливо яскраво виявляється при прийомі повідомлень із Інтернету.

Для розв’язання проблеми впроваджується 16-бітовий код, спроможний закодувати N₀=2¹⁶=65536 символів.

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

Наприклад, для передачі десяткових цифр потрібний 4-бітовий рівномірний код: 0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001. Але ентропія десяткової цифри не 4 біта, а

біта.

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

Як приклад нерівномірного коду розглянемо код Хаффмена для кодування десяткових цифр

0~000 2~010 4~100 6~1100(0110) 8~1110(1000)

1~001 3~011 5~101 7~1101(0111) 9~1111(1001).

У середньому для запису кодом Хаффмена однієї десяткової цифри потрібно

біта.

Це майже дорівнює ентропії десяткової цифри 3,32 біта.

Чому не 3,32 біта? Тому що нерівномірні коди мають бути префіксними, коли жодна кодова комбінація не є початком іншої, що дозволяє зчитувати повідомлення, записані без відокремлень одне від одного, за допомогою спеціального алгоритму.

Алгоритм розпізнавання змісту повідомлень, закодованих кодом Хаффмена: виділяють два старших біта; якщо це «11» – то це тетрада (в кодовому слові 4 біта), інакше – це тріада. В такому вигляді повідомлення передаються каналами зв’язку. Після передачі повідомлення вже на приймачі в тріадах доповнюють 0-й старший біт, а тетради спеціальним чином також перетворюють у двійковий код.

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