Код Хеммінга

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

Оптимальним називається (n, m) - код, який забезпечує мінімальну імовірність помилкового декодування серед всіх інших кодів з тими ж n і m.

Найвідоміші з кодів, що самоконтролюються і самокоректуються, – коди Хеммінга. Побудовані вони стосовно двійкової системи числення.

Код Хеммінга є блочним кодом, який дозволяє виявити і виправити помилково переданий біт в межах переданого блоку. Звичайно код Хеммінга характеризується двома цілими числами, наприклад, (11,7). Такий запис говорить, що при передачі 7-бітного коду використовується 4 контрольних біта (7 + 4 = 11).

Коди Хеммінга призначені або для виправлення одиночних спотворень, або для виправлення одиночних і виявлення без виправлення подвійних спотворень (при збільшенні надмірності), і мають, зрозуміло, більшу надмірність, ніж коди з перевіркою на парність. У такому коді n-значне число має m інформаційних і k контрольних символів.

Певною особливістю коду є система нумерації його символів: вони нумеруються від 1 до . Одразу зауважимо, що згідно із загальними умовами, вагові коефіцієнти контрольних розрядів дорівнюють їх номерам у базовому кодовому слові і мають значення , і = 0, 1, 2, …, k. Отже в базовому кодовому слові контрольні символи розташовуються серед інформаційних.

При цьому приймається наступна нумерація біт (знаків коду): всі біти кодової комбінації одержують номери, починаючи з 1, справа наліво (варто нагадати, що в двійковій системі числення біти нумеруються з 0 справа наліво); контрольними (перевірочними) є біти з номерами 1, 2, 4, 8 і т.д. – всі інші є інформаційними. При цьому при формуванні коду Хеммінга для наочності при кодуванні чи декодуванні інформаційні та контрольні символи зручно представляти записаними в деякий шаблон, наприклад, для восьмизначної двійкової послідовності 10110110:

чи записаними в таблицю, наприклад таку, яка наведена нижче (табл. 1) для восьмизначної двійкової послідовності 01110011:

В цій таблиці невизначені спочатку значення контрольних символів помічені зірочкою (*).

Приклад застосування цього алгоритму розглянемо на прикладі передачі коду літери s = 0x073 = 1110011. При використанні коду Хеммінга для передачі семисимвольних повідомлень потрібно 4 надлишкових символи k ³ log₂ (n + 1), k ³ 4, тобто слід використовувати код (11,7). Таблиця для формування контрольних символів такого має вигляд (табл. 2):

Як і раніше, символами * позначені чотири позиції, де повинні розміщуватися біти контрольної ознаки.

Загальний вираз для формування контрольної ознаки у цих кодах набуває вигляду:

(mod Р),

де , додавання здійснюється порозрядно за модулем Р = 2, а вагові коефіцієнти , тобто дорівнюють номеру відповідного символу. Для формування контрольних символів здійснюється контрольне додавання шляхом виконання операції порозрядного додавання по модулю 2 кодів номерів ненульових бітів (пропускається множення на нуль). У цьому випадку це 11, 10, 9, 5 і 3.

Обчислимо контрольну суму:

Таким чином, приймач одержить код (табл. 5):

Для перевірки правильності формування контрольних символів підсумуємо знову коди номерів ненульових бітів (табл. 6) и одержимо нуль:

Ну а тепер розглянемо два випадки помилок в одному з біт посилки, наприклад в біті 7 (1 замість 0) і в біті 5 (0 замість 1). Підсумуємо коди позицій ненульових біт ще раз (таблиця 7):

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

Існує і модифікація алгоритмів кодування – декодування цього коду. При кодуванні формуються k контрольних символів, кожний з яких є ознакою парності для певної групи інформаційних знаків базового кодового слова. З цією метою здійснюється k групових перевірок на парність із залученням відповідних інформаційних символів і формується певне число – контрольна ознака U = u₁, u₂, u₃,… u_k.

Для (n, m) − коду Хеммінга перевірочні символи визначаються із перевірочних рівнянь:

При декодуванні здійснюється k групових перевірок на парність із залученням відповідних інформаційних та контрольних символів і формується певне число – синдром спотворень S. В результаті кожної перевірки у відповідний символ синдрому спотворень S_і записується 0, якщо перевірка була успішною, або 1, якщо була знайдена непарність.При перевірці наявності спотворень за тими ж правилами, що розглянуті вище, розраховуються так звані елементи синдрому спотворень S_i. Але при розрахунку елементів синдрому спотворень використовуються і сформовані раніше перевірочні елементи. Тобто, елементи синдрому визначаються з виразів (синдромних рівнянь):

Групи для перевірки утворюються таким чином, що в регістрі спотворень після закінчення перевірки виходить k - символьний синдром спотворень S, що показує номер позиції помилкового двійкового символу. Зміна цього символу – виправлення спотворень.

Приклад 2. Розглянемо семизначний код Хеммінга для зображення чисел від 0 до 9 (табл. 2).

Таблиця 2. Семизначний код Хеммінга

Хай переданий код числа 6 у вигляді “0 1 1 0 0 1 1”, а прийняли у вигляді “0 1 0 0 0 1 1”. Перевірочні групи:

Вміст синдрому спотворень “101”, значить помилка в п’ятій позиції.

Перевірочні рівняння використовуються для побудови кодера, а синдромні − декодера коду Хеммінга.