Коди Гемінга

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Коди Хеммінга – лінійні коди, які забезпечують виявлення та корекцію помилок. Використовуються при передачі та зберіганні даних. Особливістю даного коду є використання кількох бітів контролю парності. Коди Хеммінга забезпечують виявлення двох помилок і виправлення однієї помилки.

Історія[ред.ред. код]

У середині 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), то на виході можливі наступні варіанти кода: ́́́́́b_1b_2...b_l; \bar {b}_1b_2...b_l; b_1\bar {b}_2...b_l;...;b_1b_2...\bar {b}_l .
Таким чином, число варіантів рівне l+1. Це пояснюється тим, що помилка може не відбутися, або вона відбудеться в одному з l розрядів і символ bi заміниться на протилежний . Число додаткових розрядів для побудови коду Хеммінга потрібно вибрати так, щоб їх вистачило для кодування перерахованих l+1 випадків. Отже, необхідно, щоб 2k≥ l+1 або 2m ≤ 2l/(l+1).
Тому, знаючи m, l вибираємо як найменше ціле число, що задовольняє умову: 2m ≤ 2l/(l+1).
Число l називається довжиною коду Хеммінга. Число m – число інформаційних символів. Враховуючи, що l=m+k, можна вибирати не l, а число k, яке називається числом контрольних символів і є найменшим цілим числом, що задовольняє умові: 2k ≥ k + 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с.: ил..

Див. також[ред.ред. код]

Посилання[ред.ред. код]