3. Кодування Хаффмана

Один з перших алгоритмів ефективного кодування інформації був запропонований Д. А. Хаффманом в 1952 році. Ідея алгоритму полягає в наступному: знаючи ймовірності символів у повідомленні, можна описати процедуру побудови кодів змінної довжини, що складаються з цілої кількості бітів. Символам з більшою ймовірністю ставляться у відповідність більш короткі коди. Коди Хаффмана володіють властивістю префіксності(тобто жодне кодове слово не є префіксом іншого), що дозволяє однозначно їх декодувати.

Класичний алгоритм Хаффмана на вході отримує таблицю частот з якими зустрічаються символи у повідомленні. Далі на підставі цієї таблиці будується дерево кодування Хаффмана (Н-дерево).

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

2. Вибираються два вільних вузла дерева з найменшими вагами.

3. Створюється їх батьковий вузол з вагою, рівною їх сумарній вазі.

4. Вузол-батько додається в список вільних вузлів, а два його нащадка видаляються з цього списку.

5. Одній дузі, котра виходить з вузла батька, ставиться у відповідність біт 1, інший - біт 0.

6. Кроки, починаючи з другого, повторюються до тих пір, поки в списку вільних вузлів не залишиться тільки один вільний вузол. Він і буде вважатися коренем дерева.

2. Код Ріда-Малера

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

Коди Ріда - Маллера відносяться до лінійних двійкових кодів, що мають великі кодові відстані і виправляючи завдяки цьому багато помилок. Вони придатні для каналів з малим відношенням сигнал / перешкода(шум). Як правило, ці коди кодуються таким чином, що в результаті виходить нероздільний код. РМ-коди знайшли широке застосування в різних радіоелектронних системах. При цьому використовується однорідна і регулярна структура породжує матриці G, що дозволяє спростити декодування кодів. З цих причин коди Ріда - Малера відіграють важливу роль у кодуванні (коди Ріда - Малера були використані при передачі фотографій Марса космічним кораблем Марінер в 1972р.).

До основних параметрів РМ - кодів відносяться:

а) - довжина кодової послідовності;

б) - кількість інформаційних символів, що входять в кодову послідовність;

в) r = nk - кількість перевірочних символів;

г) - мінімальна кодова відстань;

д) l - порядок коду.

Коди Ріда-Маллера першого порядку задаються породжувальною матрицею G, перший рядок якої складається з одиниць. В якості стовпців інших m рядків використовуються всі двійкові числа довжиною m:

Кодування РМ-кодів здійснюється стандартним чином - шляхом множення вихідного вектора на породжувальну матрицю:

AG = B.

Як правило, РМ-коди декодуются мажоритарним способом (в останні роки для декодування РМ-кодів використовуються процесори швидких перетворень).