Код Хеммінга: ідея побудови
Код Хеммінга є одним із найважливіших класів лінійних кодів, що знайшли широке застосування на практиці, і має простий і зручний для технічної реалізації алгоритм виявлення й виправлення одиничної помилки.
Нехай необхідно виправити одиничну помилку бінарного коду. Такий код складається з nі інформаційних символів і nк контрольних (надлишкових) символів. Усього символів у коді:
| n = nі + nк | (4.1) |
При передаванні коду може бути спотворено будь-який інформаційний символ. Однак можливий і такий варіант, коли жоден із символів не буде перекручений, тобто якщо всього n символів, то за допомогою контрольних символів, що входять у це число, повинна бути створена така кількість комбінацій 
, щоб просто розрізнити n + 1 варіант.
Тому nк повинне задовольняти нерівність:
| 2nk ³ n + 1 | (4.2) |
Тоді, згідно (4.1):
| 2n = 2nk+ni = 2nk × 2ni | (4.3) |
Використовуючи (4.2), запишемо:
2n ³ (n + 1) × 2nk,
де 2n – повне число комбінацій коду.
Звідси число інформаційних символів коду, що виявляє і коригує одиничну помилку, буде дорівнювати:
Для обчислення основних параметрів коду Хеммінга задається кількість або інформаційних символів, або інформаційних комбінацій N = 2ni.
За допомогою формул обчислюють n і nк. Співвідношення між n, nі і nк для коду Хеммінга представлені в табл. 4.1.
Знаючи основні параметри коригувального коду, визначають робочі і контрольні сигнали. Практика показує, що номери контрольних символів зручно вибирати за законом 2i, де i = 0, 1, 2, 3, ... – натуральний ряд чисел. Номери контрольних символів у цьому випадку дорівнюють відповідно 1, 2, 4, 16, 32... Потім вираховують значення контрольних коефіцієнтів (0 або 1), керуючись наступним правилом: сума одиниць на перевірочних позиціях повинна бути парної. Якщо ця сума парна, то значення контрольного коефіцієнту буде дорівнювати нулю, чи одиниці - у протилежному випадку.
Таблиця 4.1 – Співвідношення між кількістю інформаційних і контрольних символів у коді Хеммінга
| n | nі | nk | n | nі | nk |
Таблиця 4.2 – Номери перевірочних позицій коду Хеммінга
| № перевірки | Перевірочні позиції (П) | № контрольного символу |
| 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, … | ||
| 2, 3, 6, 7, 10, 11, 14, 15, 18, 19, 22, 24, ... | ||
| 4, 5, 6, 7, 12, 13, 14, 15, 20, 21, 22, 23, ... | ||
| 8, 9, 10, 11, 12, 13, 14, 15, 24, 25, 26, 27, 28, 29, 30, 31, 40, 41, 42, ... | ||
| 16, 17, 18, 19, 20, 21, … |
Побудова коду Хеммінга
Розглянемо правила побудови коду Хеммінга на прикладі.
Приклад 4.1.Побудувати макет коду Хеммінга й розрахувати значення коригувальних розрядів для кодової комбінації (nі=4) 0101.
Розв‘язок:Згідно табл. 4.1 мінімальне число контрольних символів nк = 3, при цьому n = 7. Контрольні коефіцієнти будуть розташовані на позиціях 1, 2, 4. Складемо макет коригувального коду і запишемо його в другий стовпчик табл. 2.3. Користуючись табл. 4.2, визначимо значення коефіцієнтів K1, K2 і K3.
Перша перевірка: сума П1+П3+П5+П7 повинна бути парної, а сума K1+0+1+1 буде парної при K1 = 0.
Друга перевірка: сума П2+П3+П6+П7 повинна бути парної, а сума K2+0+0+1 буде парної при K2 = 1.
Третя перевірка: сума П4+П5+П6+П7 повинна бути парної, а сума K3+1+0+1 буде парної при K3 = 0.
Остаточне значення шуканої комбінації коригувального коду записуємо в третій стовпчик таблиця 4.3.
Таблиця 4.3
| Позиція символів коригувального коду | Кодове слово | |
| без значень контрольних коефіцієнтів | зі значеннями контрольних коефіцієнтів | |
| К1 | ||
| К2 | ||
| К3 | ||