Немає перевірених версій цієї сторінки; ймовірно, її ще не перевіряли на відповідність правилам проекту.

Коди Гемінґа — сімейство лінійних кодів, які забезпечують виявлення та корекцію помилок і узагальнюють код Гемінґ(7,4) винайдений у 1950 році Річардом Гемінґом. Коди Гемінґа забезпечують виявлення двобітних помилок і виправлення однобітних помилок. На відміну від них, біт парності не може виправляти помилок, а може лише виявити непарну кількість помилок у бітах.

Історія

ред.

У середині 1940-х років Річард Гемінґ працював у знаменитих Bell Labs на лічильній машині Bell Model V. Це була електромеханічна машина, що використовує релейні блоки, швидкість яких була дуже низька: один оберт за кілька секунд. Дані вводилися в машину за допомогою перфокарт, і тому в процесі читання часто відбувалися помилки. У робочі дні використовувалися спеціальні коди, щоб виявляти й виправляти знайдені помилки, при цьому оператор дізнавався про помилку за світінням лампочок, виправляв і запускав машину. У вихідні дні, коли не було операторів, при виникненні помилки машина автоматично виходила з програми та запускала іншу.

Гемінґ часто працював у вихідні дні, і все більше і більше дратувався, тому що часто був повинен перезавантажувати свою програму через ненадійність перфокарт. Протягом декількох років він проводив багато часу над побудовою ефективних алгоритмів виправлення помилок. У 1950 році він опублікував спосіб, який сьогодні відомий як код Гемінґа[1].

Коди, що самоконтролюються

ред.

Коди, що самоконтролюються, дають змогу автоматично виявляти найімовірніші помилки під час передачі даних. Для їх побудови досить приписати до кожного слова один додатковий (контрольний) двійковий розряд і вибрати цифру цього розряду так, щоб загальна кількість одиниць в зображенні будь-якого числа була, наприклад, парною. Одиночна помилка в довільному розряді переданого слова (зокрема, можливо, і в контрольному розряді) змінить парність загальної кількості одиниць. Лічильники по модулю 2, що підраховують кількість одиниць, які містяться серед двійкових цифр числа, можуть давати сигнал про наявність помилок.

При цьому, зрозуміло, ми не отримуємо ніяких вказівок про те, в якому саме розряді відбулася помилка, і, отже, не маємо можливості виправити її. Залишаються непоміченими також помилки, які виникають одночасно в двох, в чотирьох або взагалі в парній кількості розрядів. Утім, подвійні, а тим більше чотирикратні помилки вважаються малоймовірними[2].

Коди, що самокоректуються

ред.

Нехай ми маємо множину всіх двійкових слів довжини t. Ці слова передаються по каналу зв'язку, в якому діє джерело завад. Це джерело завад під час передачі двійкового слова довжини t може видавати помилки не більше ніж у р символах. Це означає, що двійкова послідовність, отримана на виході каналу, відрізняється від початкової не більше ніж у р позиціях.

Очевидно, що якщо початкове слово передавати без попереднього кодування, то відновити на виході дійсне повідомлення практично неможливо. Тому виникає завдання побудови за початковим, будь-яким словом a1a2...am його коду b1b2...bl (l > m), що самокоректується і дає змогу за отриманим на виході каналу кодом b'1b'2...b'l однозначно відновити передаваний код b1b2...bl, а отже і початкове повідомлення a1a2...am. Під час передавання коду b1b2...bl по каналу зв'язку код, можливо, спотворився, а отже, на виході каналу буде слово b'1b'2...b'l, яке в загальному випадку відрізняється від b1b2...bl не більше ніж у р позиціях.

Коди, що мають такі властивості, називають стійкими до завад кодами (кодами, що самокоректуються), або кодами, що виправляють p помилок.

Маючи m + k розрядів, стійкий до завад код для p = 1 можна побудувати так.
Присвоїмо кожному з розрядів свій номер – від 1 до m + k; запишемо ці номери у двійковій системі числення. Оскільки 2k > m + k, то кожен номер можна представити, очевидно, k-розрядним двійковим числом.

Нехай усі m + k розрядів коду розбиті на контрольні групи, які частково перекриваються, причому так, що одиниці у двійковому представленні номера розряду указують на його приналежність до певних контрольних груп. Наприклад: розряд № 5 належить до 1-ї і 3-ї контрольних груп, тому що у двійковому представленні його номера 5 =...000101 — 1-й і 3-й розряди містять одиниці.

Серед m + k розрядів коду при цьому є k розрядів, кожен із яких належить тільки до однієї контрольної групи:

  • Розряд № 1: 110 = 0000012 належить тільки до 1-ї контрольної групи.
  • Розряд № 2: 210 = 0000102 належить тільки до 2-ї контрольної групи.
  • Розряд № 4: 410 = 0001002 належить тільки до 3-ї контрольної групи.
  • ...
  • Розряд № 2k-1 належить тільки до k-ї контрольній групі.

Ці k розрядів ми і вважатимемо контрольними. Інші m розрядів, кожен із яких належить принаймні до двох контрольних груп, будуть інформаційними розрядами.

У кожній із k контрольних груп матимемо по одному контрольному розряду. У кожен із контрольних розрядів помістимо таку цифру (0 або 1), щоб загальна кількість одиниць у його контрольній групі була парною.

Наприклад, розглянемо код Гемінґа при m = 7 і k = 4 (табл. 1).

Таблиця 1. Кодування з використанням кодів Гемінґа 0110101
ред.
№ розряду: 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011
Розподіл контрольних і інформаційних розрядів p1 p2 d1 p3 d2 d3 d4 p4 d5 d6 d7
Інформаційне кодове слово 0 1 1 0 1 0 1
L0 1 0 1 0 1 1
L1 0 0 1 0 0 1
L2 0 1 1 0
L3 0 1 0 1
Кодове слово з контрольними розрядами 1 0 0 0 1 1 0 0 1 0 1

Нехай початкове слово (кодове слово без контрольних розрядів) — 01101012.

Позначимо pі — контрольний розряд № і, а di — інформаційний розряд № i, де i = 1, 2, 3, 4...

Припустимо, що під час передавання даного кодового слова 10001100101 відбулася помилка в 11-му символі, так, що було прийнято нове кодове слово 10001100100. Провівши в прийнятому коді перевірку парності всередині контрольних груп, ми виявимо, що кількість одиниць непарна в 1-й, 2-й і 4-й контрольних групах, і парна в 3-й контрольній групі. Це указує, по-перше, на наявність помилки, по-друге, значить, що номер помилково прийнятого символу у двійковому представленні містить одиниці на першій, другій і четвертій позиціях і нуль — на третій позиції, тому помилка тільки одна, і 3-тя контрольна сума виявилася правильною (табл. 2).

Таблиця 2. Перевірка однієї помилки в коді Гемінґа
ред.
№ розряду: 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 Контроль парності в групі Контрольний біт
Розподіл контрольних і інформаційних розрядів p1 p2 d1 p3 d2 d3 d4 p4 d5 d6 d7
Передане кодове слово 1 0 0 0 1 1 0 0 1 0 1
Прийняте кодове слово 1 0 0 0 1 1 0 0 1 0 0
L0 1 0 1 0 1 0 Fail 1
L1 0 0 1 0 0 0 Fail 1
L2 0 1 1 0 Pass 0
L3 0 1 0 0 Fail 1
L3 L2 L1 L0
У двійковому представленні 1 0 1 1
У десятковому представленні 8 2 1 11

З таблиці видно, що помилка відбулася в 11-му символі і її можна виправити.

Побудова коду Гемінґа

ред.

Вважатимемо, що в каналі зв'язку при передачі повідомлення може відбутися не більш ніж одна помилка. Це означає, що якщо початкове повідомлення a1a2...am кодується набором b1b2...bl (l = m + k), то на виході можливі наступні варіанти кода: ́́́́́ . Таким чином, число варіантів рівне l + 1. Це пояснюється тим, що помилка може не відбутися, або вона відбудеться в одному з l розрядів і символ bi заміниться на протилежний. Число додаткових розрядів для побудови коду Геммінга потрібно вибрати так, щоб їх вистачило для кодування перерахованих l + 1 випадків. Отже, необхідно, щоб

2kl + 1 або 2m ≤ 2l / (l + 1).

Тому, знаючи m, l вибираємо як найменше ціле число, що задовольняє умову: 2m ≤ 2l / (l + 1).

Число l називається довжиною коду Гемінґа. Число m — число інформаційних символів. Враховуючи, що l = m + k, можна вибирати не l, а число k, яке називається числом контрольних символів і є найменшим цілим числом, що задовольняє умові: 2kk + m + 1.

Наприклад,

  • якщо m = 4, то l = 7, k = 3
  • якщо m = 9, то l = 13, k = 4

Таким чином, при побудові кода Гемінґа, перше, що потрібно зробити: це по числу t визначити числа k і l.

Нехай для повідомлення а = a1a2...am довжини m необхідно побудувати код Гемінґа. Візьмемо m=9; початкове повідомлення

а=101110111=a1a2a3a4a5a6a7a8a9.

Тоді l = 13, k = 4; код Гемінґа b = b1b2b3b4b5b6b7b8b9b10b11b12b13.

Крок 1. Представимо кожне число і з множини L = {1,2...,l} у вигляді к-розрядного двійкового числа w = Vk-1Vk-2...V1V0. Результати запишемо у вигляді таблиці

w/i 1 2 3 4 5 6 7 8 9 10 11 12 13
V0 1 0 1 0 1 0 1 0 1 0 1 0 1
V1 0 1 1 0 0 1 1 0 0 1 1 0 0
V2 0 0 0 1 1 1 1 0 0 0 0 1 1
V3 0 0 0 0 0 0 0 1 1 1 1 1 1

Крок 2. Розіб’ємо множину L на k підмножин таким чином:
L0 = {і ∈ L0 : V0 = 1}; L0 = {1, 3, 5, 7, 9, 11, 13},
L1 = {і ∈ L1 : V1 = 1}; L1 = {2, 3, 6, 7, 10, 11},
L2 = {і ∈ L2 : V2 = 1}; L2 = {4, 5, 6, 7, 12, 13},
L3 = {і ∈ L3 : V3 = 1}; L3 = {8, 9, 10, 11, 12, 13}.

Крок 3. Перші елементи (їх рівно k) цих множин є степенем числа 2; вони визначають номери контрольних розрядів коду Гемінґа. Решта елементів множини L визначають номери інформаційних розрядів. Отже, в коді Геммінга розряди b1b2b4b8 – контрольні, решта розрядів b3b5b6b7b9b10b11b12b13 – інформаційні.

Крок 4. Формування значень інформаційних символів. Інформаційні символи коду Геммінга формуються природним чином з символів початкового повідомлення a1a2...am . А саме: b3=a1, b5=a2, b6=a3, b7=a4, b9=a5, b10=a6, b11=a7, b12=a8, b13=a9.
Оскільки початкове повідомлення а = 101110111, то b3=1 b5=0, b6=1, b7=1, b9=1, b10=0, b11=1, b12=1, b13=1.

Крок 5. Формування значень контрольних символів.
Після визначення інформаційних символів контрольні символи визначаються таким чином:
b1= ⊕ ∑ bj ; j ∈ L0 ; j ≠ 1
b2= ⊕ ∑ bj ; j ∈ L1 ; j ≠ 2
b4= ⊕ ∑ bj ; j ∈ L2 ; j ≠ 4
b8= ⊕ ∑ bj ; j ∈ L3 ; j ≠ 8.
Тут ⊕ ∑ – сума по модулю два, bj – розряди, що мають номери з відповідної множини Lj. У розглянутому прикладі матимемо:
b1 = b3 ⊕ b5 ⊕ b7 ⊕ b9 ⊕ b11 ⊕ b13 = 1 ⊕ 0 ⊕ 1 ⊕ 1 ⊕ 1 ⊕ 1 = 1
b2 = b3 ⊕ b6 ⊕ b7 ⊕ b10 ⊕ b11 =1 ⊕ 1 ⊕ 1 ⊕ 0 ⊕ 1= 0
b4 = b5 ⊕ b6 ⊕ b7 ⊕ b12 ⊕ b13 = 0 ⊕ 1 ⊕ 1 ⊕ 1 ⊕ 1 = 0
b8 = b9 ⊕ b10 ⊕ b11 ⊕ b12 ⊕ b13 = 1 ⊕ 0 ⊕ 1 ⊕ 1 ⊕ 1 = 0

Крок 6. Остаточно, для повідомлення а = 101110111 код Гемінґа b буде наступним: b=b1b2b3b4b5b6b7b8b9b10b11b12b13 = 1010011010111.
Таким чином можна побудувати код Гемінґа для довільного повідомлення довжиною m.

Виявлення і виправлення помилки в кодах Гемінґа

ред.

Нехай при передачі коду b = b1b2...bl відбулася помилка в розряді з номером t, тобто на виході каналу отримано слово b' = b1b2…bt-1btbt+1…bl.
Представимо t у вигляді к-розрядного двійкового числа: t = Vk-1...V1V0. Покажемо, як за кодом b' знайти розряди Vi числа t.
Розглянемо t' = V'k-1...V'1V'0 де:
V'0= ⊕ ∑b'j ; j ∈ L0 ,
V'1= ⊕ ∑b'j ; j ∈ L1 ,

V'k-1= ⊕ ∑b'j ; j ∈ Lk-1.

Покажемо, що t' = t, тобто V'0= V0 ; V'1=V1 ; … ; V'k-1= Vk-1 .
Розглянемо ситуації:
1. Нехай Vi = 0; це означає, що t ∉ Li = {j ∈ Li : Vi = 1}.
Отже, всі розряди з номерами з Li отримані на виході каналу без спотворення, тобто b't = bt ; t ∈ Li .
2. Нехай Vi = 1, тоді t ∈ Li = {j ∈ Li : Vi = 1}, і деякий розряд з номером з Li отриманий на виході каналу із спотворенням, тобто для деякого q з Li , а для всіх j ∈ Li, j≠q, b'j = bj.
Звідси отримуємо V'i= ⊕ ∑b'j = (⊕ ∑bj) ⊕ 1= 0 ⊕ 1 = 1. Отже, і в цьому випадку Vi=V'i.
Нехай в розглянутому вище прикладі помилка при передачі кодового слова b = b1b2b3b4b5b6b7b8b9b10b11b12b13 = 1010011010111 відбулася в 11 розряді (t = 11). Тобто на виході каналу отримано повідомлення b' = b'1b'2b'3b'4b'5b'6b'7b'8b'9b'10b'11b'12b'13 = 1010011010011.
Для цього кодового повідомлення отримуємо:
V0 = b'1 ⊕ b'3 ⊕ b'5 ⊕ b'7 ⊕ b'9 ⊕ b'11 ⊕ b'13 = 1 ⊕ 1 ⊕ 0 ⊕ 1 ⊕ 1 ⊕ 0 ⊕ 1 = 1
V1 = b'2 ⊕ b'3 ⊕ b'6 ⊕ b'7 ⊕ b'10 ⊕ b'11 =0 ⊕1 ⊕ 1 ⊕ 1 ⊕ 0 ⊕ 0= 1
V2 = b'4 ⊕ b'5 ⊕ b'6 ⊕ b'7 ⊕ b'12 ⊕ b'13 = 0 ⊕ 0 ⊕ 1 ⊕ 1 ⊕ 1 ⊕ 1 = 0
V3 = b'8 ⊕ b'9 ⊕ b'10 ⊕ b'11 ⊕ b'12 ⊕ b'13 = 0 ⊕ 1 ⊕ 0 ⊕ 0 ⊕ 1 ⊕ 1 = 1
Таким чином, двійкове представлення номера розряду, в якому відбулася помилка, є 1011. Але це не що інше, як двійкове представлення числа 11. Отже, помилковий розряд 11.
Для виправлення помилки необхідно біт помилкового розряду змінити протилежним.
Декодування (отримання початкового повідомлення) здійснюється так: після виправлення помилки виписати послідовно зліва направо з коду повідомлення інформаційні символи, тобто a1a2…am = b3b5b6b7b9b10b11b12b13. У нашому прикладі з коду b = 1010011010111 виписуємо а = 101110111. Це і є початкове повідомлення.

Використання

ред.

Код Гемінґа використовується в деяких прикладних програмах в області зберігання даних, особливо в RAID 2; крім того, метод Гемінґа давно застосовується в пам'яті типа ECC і дозволяє «на льоту» виправляти однорозрядні і виявляти дворозрядні помилки.

Джерела

ред.

1. Новиков Ф.А. Дискретная математика для программистов – Питер: СПб, 2004. — 302 с.

2. Конспект лекций по дискретной математике / Ю. И. Галушкина, А. Н. Марьямов. — М.: Айрис-пресс, 2007. — 176 с. — (Высшее образование).

3. Нікольський Ю. В., Пасічник В.В., Щербина Ю.М. Дискретна математика. — К.: Видавнича група BHV, 2007. — 368 с.: іл.

4. Хемминг Р. В. Теория кодирования и теория информации: Пер. с англ. — М.: Радио и связь, 1983. — 176 с., ил.

Примітки

ред.
  1. Richard W. Hamming: Error Detection and Error Correction Codes. The Bell System Technical Journal, Vol. XXIX 2, 1950, Seite 147-160.
  2. Кудряшов Б.Д. Теория информации: Учебник для вузов. – СПб.: Питер, 2009. – 320с.: ил..

Див. також

ред.

Посилання

ред.