Код Хеммінга: ідея побудови

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

Нехай необхідно виправити одиничну помилку бінарного коду. Такий код складається з n_і інформаційних символів і n_к контрольних (надлишкових) символів. Усього символів у коді:

n = n_і + n_к

(4.1)

При передаванні коду може бути спотворено будь-який інформаційний символ. Однак можливий і такий варіант, коли жоден із символів не буде перекручений, тобто якщо всього n символів, то за допомогою контрольних символів, що входять у це число, повинна бути створена така кількість комбінацій , щоб просто розрізнити n + 1 варіант.

Тому n_к повинне задовольняти нерівність:

2ⁿ^k ³ n + 1

(4.2)

Тоді, згідно (4.1):

2ⁿ = 2ⁿ^k⁺ⁿⁱ = 2ⁿ^k × 2ⁿⁱ

(4.3)

Використовуючи (4.2), запишемо:

2ⁿ ³ (n + 1) × 2ⁿ^k,

де 2ⁿ – повне число комбінацій коду.

Звідси число інформаційних символів коду, що виявляє і коригує одиничну помилку, буде дорівнювати:

Для обчислення основних параметрів коду Хеммінга задається кількість або інформаційних символів, або інформаційних комбінацій N = 2ⁿⁱ.

За допомогою формул обчислюють n і n_к. Співвідношення між n, n_і і n_к для коду Хеммінга представлені в табл. 4.1.

Знаючи основні параметри коригувального коду, визначають робочі і контрольні сигнали. Практика показує, що номери контрольних символів зручно вибирати за законом 2ⁱ, де i = 0, 1, 2, 3,... – натуральний ряд чисел. Номери контрольних символів у цьому випадку дорівнюють відповідно 1, 2, 4, 16, 32... Потім вираховують значення контрольних коефіцієнтів (0 або 1), керуючись наступним правилом: сума одиниць на перевірочних позиціях повинна бути парної. Якщо ця сума парна, то значення контрольного коефіцієнту буде дорівнювати нулю, чи одиниці - у протилежному випадку.

Таблиця 4.1 – Співвідношення між кількістю інформаційних і контрольних символів у коді Хеммінга

n	n_і	n_k	n	n_і	n_k

Таблиця 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

Позиція символів коригувального коду	Кодове слово
без значень контрольних коефіцієнтів	зі значеннями контрольних коефіцієнтів
	К₁
	К₂

	К₃