Сутність та принципи оптимального кодування

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

1. Сутність та принципи оптимального кодування.

2. Метод Шеннона–Фано.

3. Метод Хаффмена.

4. Метод Лемпеля–Зіва.Частотно–компактні коди.(самостійно)

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

Кодування, при якому досягається мінімальна середня довжина кодового слова, називається оптимальним.

Основні властивості оптимальних кодів:

1. Мінімальна середня довжина кодового слова оптимального коду забезпечується в тому випадку, коли надмірність кожного кодового слова зведена до мінімуму (в ідеальному випадку до нуля).

2. Кодові слова оптимального коду повинні будуватися з рівноймовірних і незалежних символів.

Принципи побудови оптимальних кодів:

1. Вибір кожного кодового слова необхідно робити так, щоб кількість інформації, міститься в ньому була максимальною.

2. Літерам первинного алфавіту, які мають велику імовірність, присвоюються коротші кодові слова у вторинному алфавіті. (Символи, за допомогою яких записано передане повідомлення, складають первинний алфавіт, а символи, за допомогою яких повідомлення трансформується в код, – вторинний алфавіт).

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

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

1) різні символи первинного алфавіту, з якого складені повідомлення, повинні мати різні кодові комбінації – вимога очевидна оскільки при однакових кодових позначеннях різних букв алфавіту можна буде їх декодувати однозначно;

2) код повинен бути побудований так, щоб можна було чітко відокремити початок і кінець букв первинного алфавіту. Вимогу можна виконати наступним чином:

- введенням в код додаткового розділового знака (символу) – паузи, що значно подовжує коди, а, отже, і час передачі повідомлення;

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

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

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

У разі рівноймовірного і незалежного алфавіту його ентропія Н дорівнює:

,

де N– число неповторюваних повідомлень;

m–основа коду;

n– довжина кодової комбінації.

З цього виразу випливає, що

,

тобто довжина кодової комбінації являє собою відношення ентропій первинного та вторинного алфавітів.

Резерв скорочення n можна шукати за рахунок зменшення чисельника, а також за рахунок збільшення знаменника.

Ентропіяхарактеризує первинний алфавіт і є незалежною інформаційною характеристикою. Для даного алфавіту та даних станів елементів системи ентропія– величина незмінна. Тому всі перетворення для поліпшення інформаційних характеристик системи передачі інформації виробляються у вторинному алфавіті. Середня довжина кодової комбінації у вторинному алфавіті ні за яких умов не може бути менше ентропії кодованого алфавіту. При правильному кодуванні ці величини будуть відрізнятися один від одного не більше, ніж на 1 одиницю.

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

Розглянемо питання побудови кодів з мінімальною надлишковістю, які застосовуються при економному кодуванні повідомлень. Метою кодування при цьому є мінімізація середньої довжини кодової комбінації на елемент повідомлення.

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

де N- кількість комбінацій;

Р_i – імовірність i–ї комбінації.

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