Код Хеммінга

Question book-4.svg
У цій статті не вистачає інформації.
Інформація повинна бути проверяєма, інакше вона може бути поставлена ​​під сумнів і вилучена.
Ви можете відредагувати цю статтю, додавши посилання на авторитетні джерела.
Ця відмітка встановлена ​​9 липня 2011.

Коди Хеммінга - найбільш відомий з, ймовірно, перших Самоконтролюючою і самокорректірующіхся кодів. Побудовані вони стосовно до двійковій системі числення.


1. Історія

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

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


2. Систематичні коди

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

3. Самоконтролюючою коди

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

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


4. Самокорректірующіеся коди

Коди, в яких можливе автоматичне виправлення помилок, називаються самокорректірующіміся. Для побудови самокорректірующегося коду, розрахованого на виправлення одиночних помилок, одного контрольного розряду недостатньо. Як видно з подальшого, кількість контрольних розрядів k повинно бути вибрано так, щоб задовольнялося нерівність 2 ^ k \ geq k + m +1 або k \ geq \ log_2 (k + m +1) , Де m - кількість основних двійкових розрядів кодового слова. Мінімальні значення k при заданих значеннях m, знайдені у відповідності з цим нерівністю, наведені в таблиці.

Діапазон m k min
1 2
2-4 3
5-11 4
12-26 5
27-57 6

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

Основними характеристиками самокорректірующіхся кодів є:

  1. Число дозволених і заборонених комбінацій. Якщо n - число символів в блоці, r - число перевірочних символів в блоці, k - число інформаційних символів, то ~ 2 ^ n - Число можливих кодових комбінацій, ~ 2 ^ k - Число дозволених кодових комбінацій, ~ 2 ^ n - 2 ^ k - Число заборонених комбінацій.
  2. Надмірність коду. Величину ~ \ Tfrac {r} {n} називають надмірністю коригуючого коду.
  3. Мінімальна кодова відстань. Мінімальним кодовою відстанню d називається мінімальне число спотворених символів, необхідний для переходу одного дозволеної комбінації в іншу.
  4. Число виявляти і виправляти помилок. Якщо g - кількість помилок, яке код здатний виправити, то необхідно і достатньо, щоб ~ D \ geq 2g +1
  5. Коригувальні можливості кодів.

Кордон Плоткіна дає верхню межу кодового відстані ~ D \ leqslant \ tfrac {n * 2 ^ {k-1}} {2 ^ k-1} або ~ R \ geq 2 * (d-1) - \ log_2 d при ~ N \ geq 2 * d-1

Кордон Хеммінга встановлює максимально можливе число дозволених кодових комбінацій ~ 2 ^ k \ leq {2 ^ n} / \ sum_ {i = 0} ^ {\ tfrac {d-1} {2}} C_n ^ i де C_n ^ i - Число сполучень із n елементів по i елементам. Звідси можна отримати вираз для оцінки числа перевірочних символів: ~ R \ geq log_2 (\ sum_ {i = 0} ^ {\ tfrac {d-1} {2}} C_n ^ i) Для значень (D / n) \ leq 0.3 різниця між межею Хеммінга і кордоном Плоткіна невелика.

Кордон Варшамова-Гільберта для великих n визначає нижню межу числа перевірочних символів ~ R \ geq log_2 (\ sum_ {i = 0} ^ {d-2} C_ {n-1} ^ i) Всі вищеперелічені оцінки дають уявлення про верхню межу d при фіксованих n і k або оцінку знизу числа перевірочних символів


5. Література

  • Пітерсон У., Уелдон Е. Коди, що виправляють помилки: Пер. з англ. М.: Мир, 1976, 600 c.
  • Кларк Д., Кейн Д. Кодування з виправленням помилок у системах цифрового зв'язку: Пер. з англ. М.: Радіо і Зв'язок, 1987, 300 с.

6. Код Хеммінга

Побудова кодів Хеммінга засноване на принципі перевірки на парність числа одиничних символів: до послідовності додається елемент такий, щоб число одиничних символів в получившейся послідовності було парних. ~ R_1 = i_1 \ oplus i_2 \ oplus ... \ Oplus i_k. знак ~ \ Oplus тут означає складання по модулю 2

~ S = i_1 \ oplus i_2 \ oplus ... \ Oplus i_n \ oplus r_1 . ~ S = 0 - Помилки немає, ~ S = 1 однократна помилка. Такий код називається ~ (K +1, k) або ~ (N, n-1) . Перше число - кількість елементів послідовності, друге - кількість інформаційних символів. Для кожного числа перевірочних символів ~ R = 3,4,5 .. існує класичний код Хеммінга з маркуванням ~ (N, k) = (2 ^ r-1, 2 ^ r-1-r) тобто - ~ (7,4), (15,11), (31,26) . При інших значеннях k виходить так званий усічених код, наприклад міжнародний телеграфний код МТК-2, у якого ~ K = 5 . Для нього необхідний код Хеммінга ~ (9,5) , Який є усіченим від класичного ~ (15,11) . Для Примера розглянемо класичний код Хеммінга ~ (7,4) . Згрупуємо перевірочні символи наступним чином:

~ R_1 = i_1 \ oplus i_2 \ oplus i_3
~ R_2 = i_2 \ oplus i_3 \ oplus i_4
~ R_3 = i_1 \ oplus i_2 \ oplus i_4

знак \ Oplus тут означає додавання по модулю 2.

Отримання кодового слова виглядає наступним чином:
\ Begin {pmatrix} i_1 & i_2 & i_3 & i_4 & \ \ \ end {pmatrix}\ Begin {pmatrix} 1 & 0 & 0 & 0 & 1 & 0 & 1 \ \ 0 & 1 & 0 & 0 & 1 & 1 & 1 \ \ 0 & 0 & 1 & 0 & 1 & 1 & 0 \ \ 0 & 0 & 0 & 1 & 0 & 1 & 1 \ \ \ end {pmatrix} = \ Begin {pmatrix} i_1 & i_2 & i_3 & i_4 & r_1 & r_2 & r_3 \ \ \ end {pmatrix}

На вхід декодера надходить кодове слово ~ V = (i_1 ', i_2', i_3 ', i_4', r_1 ', r_2', r_3 ') де штрихом позначені символи, які можуть спотворитися в результаті перешкоди. У декодері в режимі виправлення помилок будується послідовність синдромів:

~ S_1 = r_1 \ oplus i_1 \ oplus i_2 \ oplus i_3
~ S_2 = r_2 \ oplus i_2 \ oplus i_3 \ oplus i_4
~ S_3 = r_3 \ oplus i_1 \ oplus i_2 \ oplus i_4

~ S = (s_1, s_2, s_3) називається синдромом послідовності.

Отримання синдрому виглядає наступним чином:

\ Begin {pmatrix} i_1 & i_2 & i_3 & i_4 & r_1 & r_2 & r_3 \ \ \ end {pmatrix}\ Begin {pmatrix} 1 & 0 & 1 \ \ 1 & 1 & 1 \ \ 1 & 1 & 0 \ \ 0 & 1 & 1 \ \ 1 & 0 & 0 \ \ 0 & 1 & 0 \ \ 0 & 0 & 1 \ \ \ end {pmatrix} = \ Begin {pmatrix} S_1 & S_2 & S_3 \ \ \ end {pmatrix}

Кодові слова ~ (7,4) коду Хеммінга

i_1i_2i_3i_4r_1r_2r_3
0 0 0 0 0 0 0
0 0 0 1 0 1 1
0 0 1 0 1 1 0
0 0 1 1 1 0 1
0 1 0 0 1 1 1
0 1 0 1 1 0 0
0 1 1 0 0 0 1
0 1 1 1 0 1 0
1 0 0 0 1 0 1
1 0 0 1 1 1 0
1 0 1 0 0 1 1
1 0 1 1 0 0 0
1 1 0 0 0 1 0
1 1 0 1 0 0 1
1 1 1 0 1 0 0
1 1 1 1 1 1 1

Синдром ~ (0,0,0) вказує на те, що в послідовності немає спотворень. Кожному ненульовий синдрому відповідає певна конфігурація помилок, яка виправляється на етапі декодування. Для коду ~ (7,4) в таблиці вказані ненульові синдроми та відповідні їм конфігурації помилок (для виду: i_1i_2i_3i_4r_3r_2r_1 ).

Синдром 001 010 011 100 101 110 111
Конфігурація помилок 0000001 0000010 0001000 0000100 1000000 0010000 0100000
Помилка в символі r_3r_2i_4r_1i_1i_3i_2

My hemcode.png

HemDecode.PNG


Література

  • Пітерсон У., Уелдон Е. Коди, що виправляють помилки: Пер. з англ. М.: Мир, 1976, 600 c.
  • Пенін П.Є., Філіппов Л.Н. Радіотехнічні системи передачі інформації. М.: Радіо і Зв'язок, 1984, 256 с.
  • Блейхут Р. Теорія і практика кодів, контролюючих помилки. Пер. з англ. М.: Мир, 1986, 576 с.

8. Застосування

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