Методика Хаффмана

Другою універсальною є методика Хаффмана і зводиться до процедури побудови кодового дерева. Ця процедура також включає 6 кроків.

1. N символів первинного алфавіту сортуються в порядку спадання ймовірностей.

2. останні n₀ символів, які вибираються з умови 2≤n₀≤m, де m кількість якісних ознак коду(для двійкового коду n₀ = 2). Об’єднують n₀ символів в деякий новий символ з ймовірністю, яка дорівнює сумі об’єднаних символів.

3. останні символи, із врахуванням утвореного символу на кроці 2, знову об’єднують і отримують новий допоміжний символ дотримуючись правил: на всіх етапах побудови кодового дерева, крім першого та останнього, додаткові символи об’єднують n=m, а на останньому 1 ≤n≤m, і в додатковий символ об’єднують тільки символи з найменшими ймовірностями.

4. процедура об’єднання продовжується до тих пір, поки ймовірність утвореного символу стане «1».

5. гілкам дерева, що виходять, прискорення та вузлів n-якісних ознак кодового алфавіту присвоюються в одному напрямку.

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

Оптимальні нерівномірні коди (онк)

Побудовані за даними, універсальними або подібними методиками, коди з нерівномірними розподілами символів, які мають мінімальну середню довжину кодового слова називаються оптимальними нерівномірними кодами (ОНК).

Рівномірні коди можуть бути оптимальними лише за умови використання їх для передачі повідомлень з рівномірним розподілом символів первинного алфавіту. При цьому кількість символів первинного алфавіту повинна бути рівною цілому степеню кількості якісних ознак вторинного алфавіту. Для двійкових кодів – це цілому степеню двійки. Максимально ефективними будуть ОНК для яких :

l_cep = H

Для двійкових кодів повинна забезпечуватись наступна умова:

При цьому довжина коду l_i –го у вторинному алфавіті повинна задовольняти наступну рівність.

l_i = -log₂ p_i = log₂(1/p_i)

Ефективність ОНК оцінюють з використанням коефіцієнта статистичного стиснення, яке характеризує зменшення кількості двійкових знаків на символ повідомлення у випадку застосування ОНК у порівнянні із застосуванням методів нестатистичного кодування.

Цей коефіцієнт визначається із наступного співвідношення.

K_cc = H_max/l_cep = log₂N/()

Коефіцієнт за наступним виразом вказує ефективність використання статистичної надлишковості:

K_cc = H/l_cep

Ентропію обчислюють в залежності від випадків:

1. нерівномірних і взаємозалежних – за ф-ю Шенона;

2. нерівномірних і взаємозалежних символів – за формулою повної умовної ентропії

Завадостійке кодування

Завадостійкими називаються коди, які володіють властивістю знаходити та виправляти помилки, які виникають у процесі передачі чи обробки інформації. На даний час розроблено десятки кодів, які теоретично можуть знаходити і виправляти довільну кількість помилок. Загалом усі коди в тій чи іншій мірі володіють коригуючою здатністю, за винятком ОНК, коди Бодо та Морзе. Так як ОНК має нульову надлишковість, а два інших – близьку до нульової.

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

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

В нероздільних визначення правильно прийнятого символу відбувається за кількісним співставленням певних якісних ознак переданих та прийнятих повідомлень. До таких кодів відносяться ОНК, стохастичні коди, код Клодкіна, код Грея, коди з постійною вагою, кореляційні коди.