Коди Гемінга

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

Історія

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

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

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

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

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

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

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

Очевидно, що якщо початкове слово передавати без попереднього кодування, то відновити на виході дійсне повідомлення практично неможливо. Тому виникає завдання побудови за початковим, будь-яким словом a₁a₂...a_m його коду b₁b₂...b_l (l > m), що самокоректується і дає змогу за отриманим на виході каналу кодом b'₁b'₂...b'_l однозначно відновити передаваний код b₁b₂...b_l, а отже і початкове повідомлення a₁a₂...a_m. Під час передавання коду b₁b₂...b_l по каналу зв'язку код, можливо, спотворився, а отже, на виході каналу буде слово b'₁b'₂...b'_l, яке в загальному випадку відрізняється від b₁b₂...b_l не більше ніж у р позиціях.

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

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

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

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

• Розряд № 1: 1₁₀ = 000001₂ належить тільки до 1-ї контрольної групи.
• Розряд № 2: 2₁₀ = 000010₂ належить тільки до 2-ї контрольної групи.
• Розряд № 4: 4₁₀ = 000100₂ належить тільки до 3-ї контрольної групи.
• ...
• Розряд № 2^k-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

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

Позначимо p_і — контрольний розряд № і, а d_i — інформаційний розряд № 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-му символі і її можна виправити.

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

Вважатимемо, що в каналі зв'язку при передачі повідомлення може відбутися не більш ніж одна помилка. Це означає, що якщо початкове повідомлення a₁a₂...a_m кодується набором b₁b₂...b_l (l = m + k), то на виході можливі наступні варіанти кода: ́́́́́$b_{1}b_{2}...b_{l};{\bar {b}}_{1}b_{2}...b_{l};b_{1}{\bar {b}}_{2}...b_{l};...;b_{1}b_{2}...{\bar {b}}_{l}$. Таким чином, число варіантів рівне l + 1. Це пояснюється тим, що помилка може не відбутися, або вона відбудеться в одному з l розрядів і символ b_i заміниться на протилежний. Число додаткових розрядів для побудови коду Геммінга потрібно вибрати так, щоб їх вистачило для кодування перерахованих l + 1 випадків. Отже, необхідно, щоб

2^k ≥ l + 1 або 2^m ≤ 2^l / (l + 1).

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

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

Наприклад,

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

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

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

а=101110111=a₁a₂a₃a₄a₅a₆a₇a₈a₉.

Тоді l = 13, k = 4; код Гемінґа b = b₁b₂b₃b₄b₅b₆b₇b₈b₉b₁₀b₁₁b₁₂b₁₃.

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

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 підмножин таким чином:
L₀ = {і ∈ L₀ : V₀ = 1}; L₀ = {1, 3, 5, 7, 9, 11, 13},
L₁ = {і ∈ L₁ : V₁ = 1}; L₁ = {2, 3, 6, 7, 10, 11},
L₂ = {і ∈ L₂ : V₂ = 1}; L₂ = {4, 5, 6, 7, 12, 13},
L₃ = {і ∈ L₃ : V₃ = 1}; L₃ = {8, 9, 10, 11, 12, 13}.

Крок 3. Перші елементи (їх рівно k) цих множин є степенем числа 2; вони визначають номери контрольних розрядів коду Гемінґа. Решта елементів множини L визначають номери інформаційних розрядів. Отже, в коді Геммінга розряди b₁b₂b₄b₈ – контрольні, решта розрядів b₃b₅b₆b₇b₉b₁₀b₁₁b₁₂b₁₃ – інформаційні.

Крок 4. Формування значень інформаційних символів. Інформаційні символи коду Геммінга формуються природним чином з символів початкового повідомлення a₁a₂...a_m . А саме: b₃=a₁, b₅=a₂, b₆=a₃, b₇=a₄, b₉=a₅, b₁₀=a₆, b₁₁=a₇, b₁₂=a₈, b₁₃=a₉.
Оскільки початкове повідомлення а = 101110111, то b₃=1 b₅=0, b₆=1, b₇=1, b₉=1, b₁₀=0, b₁₁=1, b₁₂=1, b₁₃=1.

Крок 5. Формування значень контрольних символів.
Після визначення інформаційних символів контрольні символи визначаються таким чином:
b₁= ⊕ ∑ b_j ; j ∈ L₀ ; j ≠ 1
b₂= ⊕ ∑ b_j ; j ∈ L₁ ; j ≠ 2
b₄= ⊕ ∑ b_j ; j ∈ L₂ ; j ≠ 4
b₈= ⊕ ∑ b_j ; j ∈ L₃ ; j ≠ 8.
Тут ⊕ ∑ – сума по модулю два, b_j – розряди, що мають номери з відповідної множини L_j. У розглянутому прикладі матимемо:
b₁ = b₃ ⊕ b₅ ⊕ b₇ ⊕ b₉ ⊕ b₁₁ ⊕ b₁₃ = 1 ⊕ 0 ⊕ 1 ⊕ 1 ⊕ 1 ⊕ 1 = 1
b₂ = b₃ ⊕ b₆ ⊕ b₇ ⊕ b₁₀ ⊕ b₁₁ =1 ⊕ 1 ⊕ 1 ⊕ 0 ⊕ 1= 0
b₄ = b₅ ⊕ b₆ ⊕ b₇ ⊕ b₁₂ ⊕ b₁₃ = 0 ⊕ 1 ⊕ 1 ⊕ 1 ⊕ 1 = 0
b₈ = b₉ ⊕ b₁₀ ⊕ b₁₁ ⊕ b₁₂ ⊕ b₁₃ = 1 ⊕ 0 ⊕ 1 ⊕ 1 ⊕ 1 = 0

Крок 6. Остаточно, для повідомлення а = 101110111 код Гемінґа b буде наступним: b=b₁b₂b₃b₄b₅b₆b₇b₈b₉b₁₀b₁₁b₁₂b₁₃ = 1010011010111.
Таким чином можна побудувати код Гемінґа для довільного повідомлення довжиною m.

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

Нехай при передачі коду b = b₁b₂...b_l відбулася помилка в розряді з номером t, тобто на виході каналу отримано слово b' = b₁b₂…b_t-1b_tb_t+1…b_l.
Представимо t у вигляді к-розрядного двійкового числа: t = V_k-1...V₁V₀. Покажемо, як за кодом b' знайти розряди V_i числа t.
Розглянемо t' = V'_k-1...V'₁V'₀ де:
V'₀= ⊕ ∑b'_j ; j ∈ L₀ ,
V'₁= ⊕ ∑b'_j ; j ∈ L₁ ,
…
V'_k-1= ⊕ ∑b'_j ; j ∈ L_k-1.

Покажемо, що t' = t, тобто V'₀= V₀ ; V'₁=V₁ ; … ; V'_k-1= V_k-1 .
Розглянемо ситуації:
1. Нехай V_i = 0; це означає, що t ∉ L_i = {j ∈ L_i : V_i = 1}.
Отже, всі розряди з номерами з L_i отримані на виході каналу без спотворення, тобто b'_t = b_t ; t ∈ L_i .
2. Нехай V_i = 1, тоді t ∈ L_i = {j ∈ L_i : V_i = 1}, і деякий розряд з номером з L_i отриманий на виході каналу із спотворенням, тобто для деякого q з L_i , а для всіх j ∈ L_i, j≠q, b'_j = b_j.
Звідси отримуємо V'_i= ⊕ ∑b'_j = (⊕ ∑b_j) ⊕ 1= 0 ⊕ 1 = 1. Отже, і в цьому випадку V_i=V'_i.
Нехай в розглянутому вище прикладі помилка при передачі кодового слова b = b₁b₂b₃b₄b₅b₆b₇b₈b₉b₁₀b₁₁b₁₂b₁₃ = 1010011010111 відбулася в 11 розряді (t = 11). Тобто на виході каналу отримано повідомлення b' = b'₁b'₂b'₃b'₄b'₅b'₆b'₇b'₈b'₉b'₁₀b'₁₁b'₁₂b'₁₃ = 1010011010011.
Для цього кодового повідомлення отримуємо:
V₀ = b'₁ ⊕ b'₃ ⊕ b'₅ ⊕ b'₇ ⊕ b'₉ ⊕ b'₁₁ ⊕ b'₁₃ = 1 ⊕ 1 ⊕ 0 ⊕ 1 ⊕ 1 ⊕ 0 ⊕ 1 = 1
V₁ = b'₂ ⊕ b'₃ ⊕ b'₆ ⊕ b'₇ ⊕ b'₁₀ ⊕ b'₁₁ =0 ⊕1 ⊕ 1 ⊕ 1 ⊕ 0 ⊕ 0= 1
V₂ = b'₄ ⊕ b'₅ ⊕ b'₆ ⊕ b'₇ ⊕ b'₁₂ ⊕ b'₁₃ = 0 ⊕ 0 ⊕ 1 ⊕ 1 ⊕ 1 ⊕ 1 = 0
V₃ = b'₈ ⊕ b'₉ ⊕ b'₁₀ ⊕ b'₁₁ ⊕ b'₁₂ ⊕ b'₁₃ = 0 ⊕ 1 ⊕ 0 ⊕ 0 ⊕ 1 ⊕ 1 = 1
Таким чином, двійкове представлення номера розряду, в якому відбулася помилка, є 1011. Але це не що інше, як двійкове представлення числа 11. Отже, помилковий розряд 11.
Для виправлення помилки необхідно біт помилкового розряду змінити протилежним.
Декодування (отримання початкового повідомлення) здійснюється так: після виправлення помилки виписати послідовно зліва направо з коду повідомлення інформаційні символи, тобто a₁a₂…a_m = b₃b₅b₆b₇b₉b₁₀b₁₁b₁₂b₁₃. У нашому прикладі з коду b = 1010011010111 виписуємо а = 101110111. Це і є початкове повідомлення.

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

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

Джерела

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

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

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

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

Див. також

• Геміґг(7,4) — побудова конкретного коду Гемінґа
• Код Ріда-Соломона
• БЧХ
• Код Джонсона
• Код Грея

Посилання

• Електронні системи: навчальний посібник / Й. Й. Білинський, К. В. Огороднік, М. Й. Юкиш. – Вінниця : ВНТУ, 2011. – 208 с.