префіксние коди

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

Якщо код префіксний, то, Новомосковський прийняту послідовність поспіль з початку до кінця, можна встановити, де закінчується одне кодове слово і починається наступне. Наприклад, якщо код префіксний і в послідовності зустрівся код 110, то, очевидно, в коді не повинно міститися слів (1), (11). Закодовано префіксним кодом з а1 = (00), а 2 = (01), а3 = (101), а4 = (100). На рис. 1 представлений граф (кодове дерево) префіксного коду з сообщеніема1 = (0), а 2 = (1), а3 = (11), а4 = (111). З рис. 1 випливає, що якщо властивість префікса не виконується, то деякі проміжні вершини дерева можуть відповідати кодовою словами.

Мал. Кодове слово непрефіксного коду

Прикладами префіксних кодів є коди Шеннона-Фано і Хаффмана. Код Шеннона-Фано

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

Мал. Кодова дерево коду Шеннона - Фано

Методика Шеннона - Фано не завжди призводить до однозначного построе-нию коду, оскільки при розбитті на частини можна зробити більше за веро-ятность як верхню, так і нижню частини. Крім того, методика не забезпе-чує відшукання оптимального безлічі кодових слів для кодування даного безлічі повідомлень. (Під оптимальністю мається на увазі те, що ніяке інше однозначно декодіруемой безліч кодових слів не має меншу середню довжину кодового слова, ніж заданий безліч.) Запропонована Хаффманом конструктивна методика вільна від відзначений-них недоліків.

код Хаффмана

Букви алфавіту повідомлень виписують в основний стовпець таблиці кодування в порядку убування ймовірностей. Дві останні літери об'єднують в одну допоміжну букву, якої приписують сумарну ймовірність. Імовірність букв, які не брали участі в об'єднанні, і отримана сумарна ймовірність слова розташовуються в порядку убування ймовірностей в додатковому стовпці, а дві останні об'єднують. Процес триває до тих пір, поки не отримаємо єдину допоміжну букву з ймовірністю, яка дорівнює одиниці.

Для знаходження кодової комбінації необхідно простежити шлях переходу знака по рядках і стовпцях таблиці. Це найбільш наочно можна здійснити по кодовому дереву. З точки, відпо-відної ймовірності 1, направляються дві гілки, причому гілки з більшою ймовірністю присвоюємо символ 1, а з меншою - 0. Таке послідовник-ве розгалуження триває до тих пір, поки не дійдемо до ймовірності каж-дой літери. Рухаючись по кодовому дереву зверху вниз, можна записати для кожного повідомлення відповідні йому кодові комбінації.

Мал. Кодова дерево коду Хаффмана