Теоретичні положення

В елементах пам’яті, виготовлюваних у вигляді напвіпровідникових ВІС, а також в процесорах підвищеної надійності використовується оперативний апаратний контроль за допомогою кодів Хемінга. Даний кодом виявляє і виправляє одноразові помилки. Кожній з 2ⁿ-1 ненульових комбінацій n-розрядного числа відповідає комбінація з n+k бітів. Значення перевірних бітів отримуються в результаті додавання за модулем 2 значень бітів у деяких визначених інформаційних розрядах, Із загальної кількості 2^n-k-1 можливих помилок код Хеммінга може виявити та виправити 2^k-1 помилок. Припустімо, що треба передати або обробити 15 різних послідовностей з одиниць та нулів. Без кодування для цього достатньо чотирьох інформаційних бітів (n=4). Потрібну кількість додаткових перевірних бітів k обчислюють з формули 2^k-1 =n+k. Звідки визначають кількість перевірних розрядів та кількість одноразових помилок, які можуть бути виявлені та виправлені. У цьому випадку кількість додаткових розрядів k = 3, а кількість одноразових помилок – 2^k-1 = 7.

Контрольні біти k_i розташовують у послідовності інформаційних бітів u_j на позиціях із номерами 2^i-1 (табл. 1.).

Таблиця 1. Послідовність контрольних та інформаційних бітів у коді Хеммінга

Значення перевірних бітів k_i обчислюється додаванням за модулем 2 значень бітів, у двійковому виразі номерів яких наявна одиниця в i-му розряді.

Для обчислення значення k₁ потрібно додати за модулем 2 значення бітів із непарними номерами. Це біти на позиціях з номерами 3, 5, 7, 9, 11, 13, 15:

.

Для визначення k₂ треба додати за модулем 2 біти, у двійковому виразі

номерів яких наявна одиниця у другому розряді, тобто 3, 6, 7, 10, 11, 14, 15:

Контрольний біт k₃ визначається додаванням за модулем 2 бітів, у двійковому виразі номерів яких наявна одиниця у третьому розряді, тобто 5, 6, 7, 12, 13, 14, 15:

.

Аналогічно визначається k₄ через біти з номерами: 9,10,11,12,13,14,15:

Визначення та виправлення помилок здійснюється k перевірками. При кожній перевірці додаються за модулем 2 біти послідовності інформаційних та контрольних бітів, двійкові номери яких мають одиницю в першому, другому, третьому і так далі розрядах. Якщо під час передавання не було збою, то результати перевірок дорівнюють нулю. Якщо збій відбувся, то хоча б одна перевірка не дорівнює нулю. У цьому випадку треба сформувати двійковий код з результатів перевірок, який вкаже на розряд, де відбувся збій. Молодший розряд коду результату перевірок формує перша перевірка, старший - остання. Інверсія біта в розряді з одержаним номером виправить помилку.

Приклад. Сформувати код Хеммінга, що виявляє і виправляє одноразову помилку у послідовності:

Для формування коду Хеммінга необхідно к = 3 контрольні біти, які мають займати позиції з номерами 1, 2 і 4.

Послідовність з контрольними символами має вигляд:

Значення контрольних бітів визначимо як:

Отже, послідовність, закодована за кодом Хеммінга, буде такою: 1100001. Нехай після передачі відбувся збій в одному розряді і прийнята послідовність 1110001.

Перша та друга перевірки дадуть значення 0, а третя - 1:

1.

2.

3.

Код 101, який створюють результати перевірок, вказує, що відбувся збій у п’ятому розряді. Якщо проінвертувати п’ятий розряд, то одержимо виправлену послідовність 1100001.

Лістинг 1. Приклад програми, яка реалізує код Хемінга для передачі повідомлення довжиною 7 бітів та розшифрування отриманого повідомлення кількістю 11 бітів: