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

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

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

n = nі + nк (4.1)

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

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

2nk ³ n + 1 (4.2)

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

2n = 2nk+ni = 2nk × 2ni (4.3)

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

2n ³ (n + 1) × 2nk,

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

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

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

Для обчислення основних параметрів коду Хеммінга задається кількість або інформаційних символів, або інформаційних комбінацій 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

Наши рекомендации