Код Хеммінга

Завадостійке кодування. Двійкові та узагальнені завадостійкі коди

Теорія інформації та кодування – 2

Вступ

Лекція № 1.3 − “Завадостійке кодування. Двійкові та узагальнені завадостійкі коди”. В лекції будуть розглянуті наступні учбові питання:

1. Код Хеммінга. 3

2. Циклічні коди. 9

3. Узагальнені завадостійкі коди. Контрольне додавання. 12

4. Узагальнені завадостійкі коди. Лишково - матричні коди. 13

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

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

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

В цій таблиці невизначені спочатку при кодуванні значення контрольних символів помічені зірочкою (*). Нагадаємо, що при використанні коду Хеммінга для передачі семирозрядних повідомлень потрібно 4 надлишкових символи
(k ³ log₂ (n + 1), k ³ 4), тобто слід використовувати код (11, 7).

Розглянемо історично перший, алгоритм із використанням k послідовних кроків (перевірок), кожна із яких забезпечує обчислення суми по модулю 2 груп символів, номери яких вибираються за певними правилами.

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

Примітка 1: У кожний з контрольних розрядів при побудові коду Хеммінга заноситься таке значення, щоб загальне число одиниць в його контрольній сумі із урахуванням контрольного було парним. Тобто, для (n, m) − коду Хеммінга перевірочні символи визначаються із перевірочних рівнянь:

де − перевірочні символи.

При перевірці наявності спотворень за тими ж правилами, що розглянуті вище, розраховуються так звані елементи синдрому спотворень S_i. Але при розрахунку елементів синдрому спотворень використовуються і сформовані раніше перевірочні елементи. Тобто, елементи синдрому визначаються з виразів (синдромних рівнянь):

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

Приклад 1. Хай передається семизначна двійкова послідовність 1110011. Як уже визначено вище, кількість перевірочних символів k = 4 та, відповідно, загальна довжина коду n = 11 (див. табл. 1). Тоді позиції контрольних біт та позиції, що перевіряються, у відповідних перевірках надано в (табл. 2).

Таблиця 2. Формування контрольних груп

Отже, значення контрольних біт визначимо із системи перевірочних рівнянь:

Отже контрольна сума та значення відповідних контрольних символів дорівнюють 1110, а таблиця 1 набуде вигляду (табл. 3):

Нехай при передаванні спотворень символів не відбулося. Тоді система синдромних рівнянь набуде вигляду:

Отже контрольна сума та значення відповідних символів синдрому дорівнюють 0000, що свідчить про відсутність спотворень.

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

Тоді система синдромних рівнянь для першого випадку набуде вигляду:

Отже контрольна сума та значення відповідних символів синдрому дорівнюють 0111, що свідчить про наявність спотворення у біті із номером 7.

Система синдромних рівнянь для другого випадку набуде вигляду:

Отже контрольна сума та значення відповідних символів синдрому дорівнюють 0101, що свідчить про наявність спотворення у біті із номером 5.

Таким чином, застосування коду Хеммінга дозволило виявити як наявність так і місце спотворення.

Оскільки у двійковому коді символи можуть мати значення 0 чи 1, то у другому алгоритмі операція кодування (а в подальшому і декодування) перетворюється на додавання кодів позицій ненульових біт. Контрольне додавання здійснюється шляхом виконання операції порозрядного додавання по модулю 2 над кодами номерів ненульових бітів. У випадку послідовності за таблицею 1 – це коди біт із номерами: 11, 10, 9, 5 і 3.

Обчислимо контрольну суму (табл. 5):

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

Порівнюючи значення біт, одержаних за цим алгоритмом та обрахованих раніше за табл. 3, упевнюємося в їх ідентичності.

Для перевірки правильності формування контрольних символів здійснимо декодування, для чого, згідно із уже визначеним алгоритмом, знову знайдемо суму кодів номерів ненульових бітів, включаючи контрольні (табл. 7), и одержимо нуль, що свідчить про відсутність спотворень:

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

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

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