5.5 Коди з виявленням і виправленням помилок
До найбільш поширених кодів з виявленням та виправленням помилок відносять код Хемінга, циклічні та рекурентні коди. Розглянемо їх більш детально.
5.5.1 Код Хемінга
Код Хемінга відноситься до систематичних кодів, в яких з п символів, які утворюють комбінацію, n0 символів є інформаційними, а останні k = п - п0 с надлишковими (контрольними), призначеними для перевірки (контрольні символи у вcix комбінаціях займають однакові позиції). Коди Xeмінга дозволяють виправити вci одиничні помилки (при кодовій відстані d=3) i визначити вci подвійні помилки (при d=4), але не виправляти їх.
Зв'язок між кількістю інформаційних та контрольних символів в коді Хемінга знаходять на основі таких міркувань. При передачі комбінації по каналу з шумами може бути спотворений довільний з п символів коду, або комбінація може бути передана без спотворень. Таким чином може бути п + 1 вapiaнтів спотворення (включаючи передачу без спотворення). Використовуючи контрольні символи, необхідно перевірити вci п+1 варіантів. За допомогою контрольних символів k можна описати 2k подій. Для цього повинна бути використана умова:
.
В таблиці 5.3 подана залежність між k i n0, яка отримана з цієї невірності, де k - число контрольних символів в коді Хемінга, n0 - інформаційних символів.
Таблиця 5.3 – Розміщення контрольних символів в комбінаціях коду Хемінга
В коді Хемінга контрольні символи розташовують на місцях, кратних степеню числа 2, тобто на позиціях 1, 2, 4, 8 i т. п. Інформаційні символи розташовують на місцях, що залишилися. Наприклад, для семиелементної закодованої комбінації можна записати
.
Символи коду Хемінга, які обведені прямокутниками, є контрольними, останні – інформаційні, де а3 – старший (четвертий) розряд вихідної кодової комбінації двійкового коду, який необхідно кодувати, а7 – молодший (перший) розряд. Після розташування на відповідних місцях кодової комбінації контрольних i інформаційних символів в коді Хемінга складають спеціальні перевірні рівняння, які використовують для визначення наявності спотворень i їx виправлення. 3 перевірних рівнянь i отримують контрольні символи при кодуванні вихідної кодової комбінації двійкового коду. Для визначення контрольних символів необхідно використати такий алгоритм.
1. Bci символи коду Хемінга з номерами розрядів розташовують в порядку збільшення номерів i під ними записують номери розрядів в двійковому коді
а1 а 2 а3 а4 а5 а6 а7
0001 0010 0011 0100 0101 0110 0111
2. Перше перевірне рівняння складають як суму за mod 2 вcix розрядів, в номерах яких в молодшому розряді 20 стоїть одиниця: 
.
Друге перевірне рівняння складають як суму за mod 2 вcix розрядів, в номерах яких стоїть одиниця на другому місці відповідного двійкового еквівалента (2І): 
.
Третє перевірне рівняння складають як суму за mod 2 всіх розрядів, в номерах яких стоїть одиниця на третьому місці (22): 
.
Аналогічно утворюються i інші перевірні суми (при більшій кількості інформаційних i контрольних символів, відповідно).
Як видно з наведених рівнянь, в кожну перевірну суму входить тільки один невизначений контрольний символ kі (а1, а2, а4, відповідно), а вci інші інформаційні символи відомі
Bci перевірні рівняння за умовою Хемінга повинні дорівнювати 0 при підсумовуванні за mod 2. 3 цієї умови i знаходять контрольні символи.
Наприклад, необхідно передати інформаційну кодову комбінацію:
а1 а2 а3 а4
1 1 0 0
з числом розрядів n 0 = 4.
З формули 2k ?n +1 = n0+k +1 визначимо, що k =3. Запишемо перевірні суми:
;
;
.
Підставимо у рівняння значення відомих інформаційних символів. З умови piвності нулю вcix перевірних сум визначаємо відповідно контрольні символи. З першого рівняння а0 = 0, з другого а1 = 1, з третього а4 = 1.
Відповідно буде передана така комбінація:
яка є комбінацією коду Хемінга.
Алгоритм декодування коду Хемінга
На приймальному пристрої комбінація коду Хемінга декодується -визначається наявність спотворення прийнятої кодової комбінації i, якщо один символ комбінації спотворений, він автоматично спочатку визначається, а потім виправляється. Визначення i виправлення спотвореного символу здійснюється на основі перевірних рівнянь. При правильному прийомі всі суми повинні дорівнювати нулю. В разі спотворення двійкове число, яке є результатом цих сум (синдром помилки), переводять в десяткове число, яке вказує номер спотвореного символу, який в подальшому виправляється шляхом інвертування.
Наприклад, при прийомі закодованої вище неспотвореної кодової комбінації Хемінга:
значення вcix символів комбінації підставляють на відповідні місця у перевірних сумах:
;
;
.
Ознака правильно прийнятої комбінації – рівність нулю вcix сум.
Припустимо, що шостий символ кодової комбінації спотворений, тобто замість комбінації 0111100 буде прийнята:
а1 а 2 а 3 а 4 а6 а7 а8
0 1 1 1 1 1 0
Підставимо значення прийнятих символів у перевірні рівняння.
Одержимо: ;
;
.
Переведемо двійкове число (синдром) 
в десяткове. Одержимо десяткове число 6, яке i вказує на номер спотвореного символу.
Кодер коду Хемінга
На основі наведених вище правил будується кодер коду Хемінга (рис. 5.15). Bін автоматично визначає значення контрольних cимвoлiв коду при відомих інформаційних, які складаються з безнадлишкових комбінацій звичайного двійкового коду.
Рисунок 5.15 – Кодер коду Хемінга
На входи cyматорів за mod 2 Ul, U2, U3 подаються інформаційні символи відповідно до перевірних сум. На вході суматорів одержуються контрольні символи а1, а2, а4. Інформаційні i контрольні символи розташовуються в необхідному порядку i через шину виводяться для подальшого перетворення.
Декодер коду Хемінга
Декодер коду Хемінга (рис. 5.16) аналізує прийняту кодову комбінацію i в разі спотворення будь-якого одного символу (інформаційного чи контрольного) автоматично виправляє спотворений символ.
Вхідна комбінації коду Хемінга надходить на суматори за mod 2 U1-U3 відповідно до контрольних сум. На виходах суматорів утворюється результат контрольних сум S1-S3. При правильному прийомі суми SI, S2, S3 повинні дорівнювати нулю.
В разі спотворення одного символу на виходах елементів U1-U3 з'явиться двійкова кодова комбінація (синдром помилки), яка декодується декодером U4. На одному з виходів декодера з'являється рівень логічної одиниці, який відповідає номеру спотвореного символу.
Рисунок 5.16 – Декодер коду Хемінга для семиелементної комбінації
На суматори за mod 2 U5-U8 надходять відповідні сигнали з входів а3, а5, а6, а7 (інформаційні символи) i відповідний вихід декодера.
При правильному прийомі на виходах 1-7 декодера - логічні нулі i на виходах суматорів U5-U8 з'являться інформаційні символи а3, а5 , а6 , а7 без змін.
В разі спотворення одного з символів, наприклад, третього, на третьому виході декодера з'явиться рівень логічної одиниці i на виході суматора за mod2 U5 спотворений символ автоматично інвертується, перетворюючись у правильний.
