В теорії кодування, метод Гемінг(7,4) — лінійний код, що кодує чотири біта даних в сім бітів, додавши три біта для підтвердження парності. Він є членом великої родини кодів Гемінга, але термін код Гемінга часто посилається на цей метод, який Річард Гемінг відкрив у 1950 році. Працюючи у компанії Bell Labs, Гемінг постійно стикався з помилками читання перфокарт, тому й почав працювати над кодом, що виправляє ці помилки.
Код Гемінга додає три додаткові біти парності на кожні чотири біта даних повідомлення. Алгоритм Гемінг(7,4) може виправляти всі одно-бітові помилки.
Мета Редагувати
Метод Гемінг(7,4) створює ряд бітів парності, які накладаються таким чином, що одно-бітова помилка (біт, дзеркально відображений в значенні) у біті даних або біті парності може бути виявлена і виправлена.
Гемінг(7,4) створює набір з 3-х бітів парності так, щоб при втраті інформації при передачі можна було відновити один з 4х бітів інформації.
Ця таблиця описує, які біти парності перекривають біти даних. Наприклад, p2 забезпечує рівну парність для бітів 2, 3, 6, і 7, d1 покритий p1, і у p2, але не p3
Багаторазові бітові помилки Редагувати
Очевидно, що в даному методі можуть бути виправлені тільки одно-бітові помилки. Альтернативно, коди Гемінга можуть використовуватися, щоб виявити одно- і дво-бітові помилки. У діаграмі поруч були дзеркально відображені біти 4 і 5. Це призводить тільки до однієї помилки парності (в зеленому колі), але така помилка є невідновлювальною.
Однак Гемінг(7,4) і подібні коди Гемінга не можуть розрізняти одно- і дво-бітові помилки. Тобто дво-бітові помилки виявляються як одно-бітові. Якщо корекція помилок буде виконуватися на дво-бітові помилку, то результат буде неправильним.
Так само метод Гемінг(7,4) не може виправити трьох-бітові помилки. Розгляньте схему: якби біт в зеленому колі (забарвлений в червоний) дорівнював 1, перевірка парності повернула б нульовий вектор, вказавши, що немає ніякої помилки в кодовій комбінації.
Кодові комбінації Редагувати
Оскільки метод Гемінг(7,4) містить лише 4 біта даних, є тільки 16 можливих переданих слів. Біти даних показані в синьому; біти парності показані в червоному, і додатковий біт парності, показаний в зеленому:
| Дані
| Гемінг(7,4) | Гемінг(7,4) з додатковим бітом парності (Гемінг(8,4)) | ||
|---|---|---|---|---|
| Слово
| Діаграма | Слово
| Діаграма | |
| 0000 | 0000000 | 00000000 | ||
| 1000 | 1110000 | 11100001 | ||
| 0100 | 1001100 | 10011001 | ||
| 1100 | 0111100 | 01111000 | ||
| 0010 | 0101010 | 01010101 | ||
| 1010 | 1011010 | 10110100 | ||
| 0110 | 1100110 | 11001100 | ||
| 1110 | 0010110 | 00101101 | ||
| 0001 | 1101001 | 11010010 | ||
| 1001 | 0011001 | 00110011 | ||
| 0101 | 0100101 | 01001011 | ||
| 1101 | 1010101 | 10101010 | ||
| 0011 | 1000011 | 10000111 | ||
| 1011 | 0110011 | 01100110 | ||
| 0111 | 0001111 | 00011110 | ||
| 1111 | 1111111 | 11111111 |