- Намалювати структурну схему кодера і декодера, що виправляє помилку.
- Визначити код для переданої кодової комбінації 1011.
- Виправити помилку, допущену в четвертому елементі прийнятої кодової комбінації.
Побудова кодів Хеммінга базується на принципі перевірки на парність ваги W (числа одиничних символів) в інформаційній групі кодового блоку. Пояснимо ідею перевірки на парність на прикладі найпростішого коректив-рующего коду, який так і називається кодом з перевіркою на парність ілікодом з перевіркою за паритетом (рівності) .В такому коді до кодовою комбінаціям безізбиточного первинного двоіче-ного k - розрядного коду додається один додатковий розряд (сімволпроверкі на парність, званий перевірочним, або контрольним). Якщо число символів "1" вихідної кодової комбінації парне, то в дополнітельномразряде формують контрольний символ 0, а якщо число символів "1" нечёт-ве, то в додатковому розряді формують символ 1. В результаті общеечісло символів "1" в будь-який передається кодової комбінації завжди буде чётним.Такім чином, правило формування перевірочного символу зводиться донаступного:
r1 = i1 ⊕ i2 ⊕. ⊕ ik,
де i - відповідний інформаційний символ (0 або 1), k - загальна їх чіслоа під операцією "⊕" тут і далі розуміється складання по mod2. Очевидно, що додавання додаткового розряду збільшує загальне число можли-них комбінацій удвічі в порівнянні з числом комбінацій вихідного привчає-ного коду, а умова парності розділяє всі комбінації на дозволені інеразрешённие. Код з перевіркою на парність дозволяє виявляти одначе-ву помилку при прийомі кодової комбінації, так як така помилка нарушаетусловіе парності, переводячи дозволену комбінацію в запрещённую.Крітеріем правильності прийнятої комбінації є рівність нулюрезультата S підсумовування по mod 2 всіх n символів коду, включаючи провероч-ний символ r1. При наявності одиночної помилки S приймає значення 1:
S = r1 ⊕ i1 ⊕ i2 ⊕. ⊕ ik = # 63730; 0 - помилки немає
1444424443 = # 63730; 1 - одноразова помилка. n
Цей код є (k +1, k) - кодом, або (n, n -1) - кодом. Мінімальна рас-стояння коду дорівнює двом (d min = 2), і, отже, ніякі помилки не могутбить виправлені. Простий код з перевіркою на парність може іспользоватьсятолько для виявлення (але не виправлення) одноразових ошібок.Увелічівая число додаткових перевірочних розрядів і формуючи поопределённим правилам перевірочні символи r, рівні 0 або 1, можна усі-лити коригувальні властивості коду так, щоб він дозволяв не тільки вияв-проживати, але і виправляти помилки. На цьому і засноване побудова кодів Хем-мінга.Коди Хемминга. Розглянемо ці коди, що дозволяють виправляти одначе-ву помилку, за допомогою безпосереднього опису. Для кожного числа про-верочних символів r = 3,4,5 ... існує класичний код Хеммінга з марки-ровкой (n, k) = (2r-1, 2r-1 -r). (3.20)
тобто - (7,4), (15,11), (31,26) ...
При інших значеннях числа інформаційних символів k виходять такзвані усічені (укорочені) коди Хеммінга. Так, для міжнародно-го телеграфного коду МТК-2. має 5 інформаційних символів, потре-буется використання коригуючого коду (9,5), що є усіченим отклассіческого коду Хеммінга (15,11), так як число символів в цьому кодеуменьшается (коротшає) на 6. Для прикладу розглянемо класичний кодХеммінга (7,4 ), який можна сформувати і описати за допомогою кодера, представленого на рис.3.2. У найпростішому варіанті при заданих чотирьох (k = 4) інформаційних символах (i1, i2, i3, i4) будемо вважати, що вони згрупує-вани на початку кодового слова, хоча це і не обов'язково. Доповнимо ці ін-формаційні символи три перевірних символами (r = 3), задаючи іхследующімі равенствами перевірки на парність, які визначаються відповід-ветствующим алгоритмами [3,5]:
r1 = i1 ⊕ i2 ⊕ i3;
r2 = i2 ⊕ i3 ⊕ i4;
r3 = i1 ⊕ i2 ⊕ i4,
де знак ⊕ означає складання по модулю 2.
Відповідно до цього алгоритмом визначення значень проверочнихсімволов ri нижче виписані всі можливі 16 кодових слів (7,4) - коду Хем-мінга.
На рис. 3.3 приведена схема декодера для (7,4) - коду Хеммінга, на входкоторого надходить кодове слово
V = (i1 ', i2', i3 ', i4', r1 ', r2', r3 ')
Апостроф означає, що будь-який символ слова може бути спотворений перешкодою вканале передачі.
У декодере в режимі виправлення помилок будується послідовність:
s1 = r1 '⊕ i1' ⊕ i2 '⊕ i3';
s2 = r2 '⊕ i2' ⊕ i3 '⊕ i4';
s3 = r3 '⊕ i1' ⊕ i2 '⊕ i4'. Трёхсімвольная послідовність (s1, s2, s3) називається синдромом.
Термін "синдром" використовується і в медицині, де він позначає сочетаніепрізнаков, характерних для певного захворювання. В даному случаесіндром S = (s1, s2, s3) являє собою поєднання результатів проверкіна парність відповідних символів кодової групи і характеризує визна-поділені конфігурацію помилок (шумовий вектор).
Кодові слова (7,4) - коду Хеммінга.
i1 i2 i3 i4 r1 r2 r3