Код Хеммінгу (7; 4)
Всім привіт! Сьогодні я хочу розповісти вам трохи про код Хеммінга (7; 4). Цей найпростіший код може бути з легкістю застосований будь-якою людиною для передачі повідомлень, що самокоректуються, і сьогодні я хочу вам показати як саме цей код можна легко і просто використовувати.
Структурно слова коду Хеммінга складаються із двох частин. Спочатку йдуть інформаційні 4 біти, потім три біти перевірочних. Позначатимемо інформаційні біти літерами ABCD, перевірочні літерами xyz.
Таким чином слово коду Хеммінга має таку структуру:
Для передачі 4 біт інформації нам потрібно передавати кодове слово з 7 біт! Останні три біти у разі, коли помилки відсутні, не несуть жодної нової інформації, бо вони залежать від перших 4. Однак якщо в кодовому слові з 7 бітів відбулася 1 помилка, то вихідні інформаційні 4 біти все одно можна буде відновити точно! У цьому і полягає головна особливість кодів, що самокоректуються.
Звичайно, використання коду Хеммінга при передачі даних вимагає збільшених ресурсів. Тут є таке важливе поняття як швидкість коду - відношення числа інформаційних біт до загальної кількості біт. У разі коду Хеммінгу швидкість дорівнює 4/7. Тобто, наприклад, щоб передавати інформацію зі швидкістю 1 Мбіт/сек і корекцією помилок за допомогою коду Хеммінга вам знадобиться канал із пропускною здатністю мінімум 7/4=1.75 Мбіт/сек.
Для підрахунку перевірочних біт можна використовувати такі формули:
x = A + B + C mod 2,
y = A + B + D mod 2,
z = A + C + D mod 2,
де n mod 2 означає залишок від розподілу числа n на 2.
Наприклад, якщо інформаційний вектор є ABCD = 1001, кодовий вектор буде ABCDxyz = 1001 100
Замість незрозумілих формул можна використати такузображення:
Тут все дуже просто. Підставляєте замість букв значення відповідних бітів і потім вважаєте значення x, y та z як суму за модулем 2 тих інформаційних біт, які є у відповідному колі.
У наведеному вище прикладі буде:
Набагато цікавішим є питання про виправлення помилок. Очевидно, висновок про відсутність помилок приймач може зробити просто взявши інформаційні біти ABCD, порахувавши їх основі перевірочні біти xyz і порівняти пораховані перевірочні біти з прийнятими. Якщо є помилка, то частина перевірочних бітів не співпаде.
Припустимо, що сталася помилка в перевірочному биті y і було прийнято слово 1001 110
У такому разі два перевірочні біти зійдуться, а один ні. Цього цілком достатньо, щоб зробити висновок, що потрібно виправити біт y (для якого перевірка не зійшлася).
Припустимо, що сталася помилка в одному з інформаційних бітів BCD - наприклад, у биті B.
У такому разі не зійдуться аж два перевірочні біти - x (він дорівнює 1, а "має" дорівнювати 0) і y. Подивившись на кола легко побачимо, що вони перетинаються по бітах B і A. Т.к. не зійшлося дві перевірки, то беремо біт B (розташований на перетині двох перевірок).
Нарешті окремо розглянемо біт A. Якщо в ньому помилка, то у нас не зійдуться всі три перевірки:
Побачивши таке неподобство одразу робимо висновок про те, що помилка в биті A.
Таким чином, можна легко та просто обчислювати локацію помилки та виправляти її. Зауважу, що якщо помилок більше однієї, то описаний вище алгоритм спрацює невірно. Наприклад, припустимо, що відбулися помилки в бітах C і z:
Перевірочні біти y та z зійдуться, а біт x ні. Алгоритм виправить біт х і все. Це цілкомприродне поведінка, т.к. якщо ймовірність помилки p0).
Звичайно, працювати з кольоровими колами зручно людині, але незручно комп'ютеру. У кодів Хеммінга є одна особливість, яка дозволяє їхнє легке декодування на комп'ютері. Отже, розглянемо наступний алгоритм:
Визначимо числа g, b, r як суму всіх чотирьох біт у колах відповідного кольору. Тобто:
g = A + B + C + x mod 2,
b = A + B + D + y mod 2,
r = A+C+D+z mod 2.
Практично кожен із цих біт можна з'ясувати, як суму відповідного перевірочного біта, обчисленого виходячи з прийнятих інформаційних біт, з прийнятим перевірним бітом. Тобто. Наприклад g є сума (A + B + C mod 2) (за цією формулою вважався x за передавача) і прийнятого x. Аналогічно b відповідає y, r відповідає z.
Якщо помилок немає, то gbr = 000 (прийняті перевірочні біти зійшлися з обчисленими з урахуванням інформаційного вектора).
Якщо є 1 помилка, то число gbr є номер (у двійковій запису) помилкового біта у векторі ABCxDyz.
Як приклад розглянемо вже знайомий нам вектор ABCDxyz = 1001 100, у якому сталася помилка у биті x (четвертий біт у векторі ABCxDyz). Порахуємо gbr:
gbr = 100[2] = 4[10]. Помилка в 4 бітах, яким і є x. Таким чином, для декодування та виправлення помилки в кодовому слові довжини 7 потрібно лише обчислити три суми та з отриманого числа нескладною функцією отримати місцезнаходження помилки.