У цій статті не вистачає інформації.
Коди Хеммінга - найбільш відомі і, ймовірно, перші з Самоконтролюючою і самокорегуюча кодів. Побудовані вони стосовно двійковій системі числення.
1. Історія
В середині 1940-х років Річард Хеммінга працював в знаменитих Лабораторіях Белла на лічильної машині Bell Model V. Це була електромеханічна машина, яка використовує релейні блоки, швидкість яких була дуже низька: один оборот за кілька секунд. Дані вводилися в машину за допомогою перфокарт, і тому в процесі читання часто відбувалися помилки. У робочі дні використовувалися спеціальні коди, щоб виявляти і виправляти знайдені помилки, при цьому оператор дізнавався про помилку за світінням лампочок, виправляв і запускав машину. У вихідні дні, коли не було операторів, при виникненні помилки машина автоматично виходила з програми і запускала іншу.
2. Систематичні коди
Систематичні коди утворюють велику групу серед блокових, разделімих кодів (в яких всі символи можна розділити на перевірочні та інформаційні). Особливістю систематичних кодів є те, що перевірочні символи утворюються в результаті лінійних операцій над інформаційними символами. Крім того, будь-яка дозволена кодова комбінація може бути отримана в результаті лінійних операцій над набором лінійно незалежних кодових комбінацій.
3. Самоконтролюючою коди
Коди Хеммінга є Самоконтролюючою кодами, тобто кодами, що дозволяють автоматично виявляти помилки при передачі даних. Для їх побудови досить приписати до кожного слова один додатковий (контрольний) двійковий розряд і вибрати цифру цього розряду так, щоб загальна кількість одиниць в зображенні будь-якого числа було, наприклад, парних. Одиночна помилка в будь-якому розряді переданого слова (в тому числі, може бути, і в контрольному розряді) змінить парність загальної кількості одиниць. Лічильники по модулю 2, підраховують кількість одиниць, які містяться серед довічних цифр числа, можуть давати сигнал про наявність помилок.
При цьому неможливо дізнатися, в якому саме розряді сталася помилка, і, отже, немає можливості виправити її. Залишаються непоміченими також помилки, що виникають одночасно в двох, в чотирьох або взагалі в парній кількості розрядів. Втім, подвійні, а тим більше Чотириразові помилки покладаються малоймовірними.
4. самокорегуюча коди
Коди, в яких можливе автоматичне виправлення помилок, називаються самокорегуюча. Для побудови самокорегуюча коду, розрахованого на виправлення одиночних помилок, одного контрольного розряду недостатньо. Як видно з подальшого, кількість контрольних розрядів k має бути вибрано так, щоб задовольнялося нерівність або, де m - кількість основних двійкових розрядів кодового слова. Мінімальні значення k при заданих значеннях m, знайдені в Відповідно до цього нерівністю, наведені в таблиці.
В даний час найбільший інтерес представляють виконавчі блокові коригувальні коди. При використанні таких кодів інформація передається у вигляді блоків однакової довжини і кожен блок кодується і декодується незалежно один від одного. Майже у всіх блокових кодах символи можна розділити на інформаційні та перевірочні. Таким чином, всі комбінації кодів поділяються на дозволені (для яких співвідношення інформаційних і перевірочних символів можливо) і заборонені.
Основними характеристиками самокорегуюча кодів є:
- Число дозволених і заборонених комбінацій. Якщо n - число символів в блоці, r - число перевірочних символів в блоці, k - число інформаційних символів, то - число можливих кодових комбінацій, - скільки разів ще можна кодових комбінацій, - число заборонених комбінацій.
- Надмірність коду. Величину називають надмірністю коригуючого коду.
- Мінімальна кодова відстань. Мінімальним кодовою відстанню d називається мінімальне число спотворених символів, необхідне для переходу однієї дозволеної комбінації в іншу.
- Число виявлених і виправляє помилок. Якщо g - кількість помилок, яке код здатний виправити, то необхідно і достатньо, щоб
- Коригувальні можливості кодів.
Кордон Плоткина дає верхню межу кодового відстані або при
Кордон Хеммінга встановлює максимально можливе число дозволених кодових комбінацій де - число сполучень із n елементів по i елементам. Звідси можна отримати вираз для оцінки числа перевірочних символів: Для значень різниця між межею Хеммінга і кордоном Плоткіна невелика.
Кордон Варшамова-Гільберта для великих n визначає нижню межу числа перевірочних символів Всі перераховані вище оцінки дають уявлення про верхню межу d при фіксованих n і k або оцінку знизу числа перевірочних символів
5. Література
- Пітерсон У. Уелдон Е. Коди, що виправляють помилки: Пер. з англ. М. Світ, 1976, 600 c.
- Кларк Д. Кейн Д. Кодування з виправленням помилок в системах цифрового зв'язку: Пер. з англ. М. Радіо і Зв'язок, 1987, 300 с.
6. Код Хеммінга
Побудова кодів Хеммінга засноване на принципі перевірки на парність числа одиничних символів: до послідовності додається елемент такої, щоб число одиничних символів в вийшла послідовності було парних. знак тут означає складання по модулю 2
. - помилки немає, одноразова помилка. Такий код називається або. Перше число - кількість елементів послідовності, друге - кількість перевірочних символів. Для кожного числа перевірочних символів існує класичний код Хеммінга з маркуванням тобто -. При інших значеннях k виходить так званий усічених код, наприклад міжнародний телеграфний код МТК-2, у якого. Для нього необхідний код Хеммінга, який є усіченим від класичного. Для Прімера розглянемо класичний код Хеммінга. Згрупуємо перевірочні символи наступним чином:
знак тут означає складання по модулю 2.
Отримання кодового слова виглядає наступним чином: =
На вхід декодера надходить кодове слово де штрихом позначені символи, які можуть спотворитися в результаті перешкоди. У декодере в режимі виправлення помилок будується послідовність синдромів:
називається синдромом послідовності.
Отримання синдрому виглядає наступним чином:
=
Кодові слова коду Хеммінга