Нерівномірні ефективні коди - студопедія

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

При побудові нерівномірного коду необхідно забезпечити однозначність декодування. Пояснимо це простим прикладом. Нехай алфавіт джерела містить шість повідомлень, які позначимо А, Б, В, Г, Д, Е, переданих незалежно один від одного з вірогідністю P (А) = 0,4; Р (Б) = 0,3; Р (В) = 0,1; Р (Г) = 0,08; Р (Д) = 0,07; Р (Е) = 0,05. Сума цих ймовірностей, звичайно, дорівнює 1. Зауважимо, що ентропія цього джерела

де i = l. 6-номер повідомлення в алфавіті джерела.

Щоб закодувати ці повідомлення рівномірним двійковим кодом, потрібно затратити на кожне повідомлення три символи. Відповідно до теореми кодування для джерела ці повідомлення можна закодувати двійковими символами так, щоб в середньому на кожне повідомлення витрачати ncp = 2,16 + e двійкових символів, де е - як завгодно мале позитивне число. Спробуємо зробити це, не замислюючись над однозначністю декодування, просто привласнюючи найбільш імовірним символам найбільш короткі блоки, наприклад:

Таким чином, для передачі повідомлень А і В, що мають сумарну ймовірність 0,7, використовують один символ, а для передачі інших повідомлень, що мають сумарну ймовірність 0,3 два символу, так що середнє число символів на повідомлення

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

Її можна відповідно до (1.37) декодувати так:

А А Б Б А Б А А А Б. і т. Д.,

і ще безліччю різних способів.

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

Однак можна побудувати і однозначно Декодовані двійкові коди «без коми». Для цього досить (хоча і не потрібно) будувати код так, щоб він задовольняв так званому «префіксних властивості». Воно полягає в тому, що жодне використовується кодове слово не повинно збігатися з початком ( «префіксом») іншого кодового слова. Це властивість не виконано у коду (1.37), так як, наприклад, слово, відповідне повідомлення А, є початком слова, відповідного повідомлення В і т. Д.

Існують різні алгоритми побудови нерівномірних кодів з префіксним властивістю. Серед них оптимальним, т. Е. Що дозволяє найкраще наблизитися до кордону, яка визначається ентропією, є алгоритм Хафмена. Розглянемо тут більш простий алгоритм Фено, в більшості випадків приводить до тих же результатів.

Алгоритм Фено полягає в наступному. Повідомлення алфавіту джерела, записані в порядку незростаюча ймовірностей, поділяються на дві частини так, щоб сумарні ймовірності повідомлень в кожній з цих частин були по можливості майже однаковими. Повідомленнями першої частини приписується в якості першого символу 0, а повідомленнями другій частині - 1. Потім кожна з цих частин (якщо вона містить більше одного повідомлення) ділиться на дві, по можливості рівноімовірні, частини і в якості другого символу для першої з них береться 0 , а для другої - 1. Цей процес повторюється, поки в кожній з отриманих частин не залишиться по одному повідомленню.

Для прикладу (1.37) на першому етапі розділення в першій частині виявиться одне повідомлення А з ймовірністю 0,4, а в другій частині - інші повідомлення з сумарною ймовірністю 0,6. Якби включити в першу частину два повідомлення (А і Б), то відхилення від равновероятности було б ще більше. Припишемо повідомленням А символ 0, а рештою повідомлень, в якості першого символу -1.

На другому етапі розділимо повідомлення Б, В, Г, Д, Е на дві рівноімовірні частини, включивши в першу частину повідомлення Б, а в другу частину - В, Г, Д, Е. Тут сумарні ймовірності для обох частин однакові - по 0, 3. Припишемо повідомленням Б в якості другого символу 0, а рештою повідомлень - 1. На третьому етапі повідомлення В і Г утворюють одну частину, а повідомлення Д і Е - другу і т. Д. В результаті приходимо до такого коду:

Б -10 Д -1110 (1.40)

Цей код, як можна переконатися, за своєю побудовою володіє префіксним властивістю. Тому, наприклад, послідовність символів (1.39) декодируется однозначно, а саме:

Середнє число символів на одне повідомлення з урахуванням їх ймовірностей дорівнює 2,2, т. Е. Перевищує ентропію (1.36) менше, ніж на 2%. Ще ближче можна було б підійти до ентропії, якщо при складанні коду зіставляти з кодовими словами не поодинокі повідомлення, а послідовності з декількох повідомлень.

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