Гемінг(7,4)

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
Графічне подання 4 бітів даних інформації D1-D4 і 3 бітів парності Р1-Р3

В теорії кодування, метод Гемінг(7,4) — лінійний код, що кодує чотири біта даних в сім бітів, додавши три біта для підтвердження парності. Він є членом великої родини кодів Гемінга, але термін код Гемінга часто посилається на цей метод, який Річард Гемінг відкрив у 1950 році. Працюючи у компанії Bell Labs, Гемінг постійно стикався з помилками читання перфокарт, тому й почав працювати над кодом, що виправляє ці помилки.

Код Гемінга додає три додаткові біти парності на кожні чотири біта даних повідомлення. Алгоритм Гемінг(7,4) може виправляти всі одно-бітові помилки.

Мета[ред. | ред. код]

Метод Гемінг(7,4) створює ряд бітів парності, які накладаються таким чином, що одно-бітова помилка (біт, дзеркально відображений в значенні) у біті даних або біті парності може бути виявлена і виправлена.

Гемінг(7,4) створює набір з 3-х бітів парності так, щоб при втраті інформації при передачі можна було відновити один з 4х бітів інформації.

Біт # 1 2 3 4 5 6 7
Переданий біт
Так Ні Так Ні Так Ні Так
Ні Так Так Ні Ні Так Так
Ні Ні Ні Так Так Так Так

Ця таблиця описує, які біти парності перекривають біти даних. Наприклад, p2 забезпечує рівну парність для бітів 2, 3, 6, і 7, d1 покритий p1, і у p2, але не p3

Багаторазові бітові помилки[ред. | ред. код]

Помилка у біті 4 та 5 представлена (показано в синьому тексті) з порушенням парності тільки в зеленому колі (показано в червоному тексті)

Очевидно, що в даному методі можуть бути виправлені тільки одно-бітові помилки. Альтернативно, коди Гемінга можуть використовуватися, щоб виявити одно- і дво-бітові помилки. У діаграмі поруч були дзеркально відображені біти 4 і 5. Це призводить тільки до однієї помилки парності (в зеленому колі), але така помилка є невідновлювальною.

Однак Гемінг(7,4) і подібні коди Гемінга не можуть розрізняти одно- і дво-бітові помилки. Тобто дво-бітові помилки виявляються як одно-бітові. Якщо корекція помилок буде виконуватися на дво-бітові помилку, то результат буде неправильним.

Так само метод Гемінг(7,4) не може виправити трьох-бітові помилки. Розгляньте схему: якби біт в зеленому колі (забарвлений в червоний) дорівнював 1, перевірка парності повернула б нульовий вектор, вказавши, що немає ніякої помилки в кодовій комбінації.

Кодові комбінації[ред. | ред. код]

Оскільки метод Гемінг(7,4) містить лише 4 біта даних, є тільки 16 можливих переданих слів. Біти даних показані в синьому; біти парності показані в червоному, і додатковий біт парності, показаний в зеленому:

Дані

Гемінг(7,4) Гемінг(7,4) з додатковим бітом парності (Гемінг(8,4))
Слово

Діаграма Слово

Діаграма
0000 0000000 Hamming code for 0000 becomes 0000000 00000000 Hamming code for 0000 becomes 0000000 with extra parity bit 0
1000 1110000 Hamming code for 1000 becomes 1000011 11100001 Hamming code for 1000 becomes 1000011 with extra parity bit 1
0100 1001100 Hamming code for 0100 becomes 0100101 10011001 Hamming code for 0100 becomes 0100101 with extra parity bit 1
1100 0111100 Hamming code for 1100 becomes 1100110 01111000 Hamming code for 1100 becomes 1100110 with extra parity bit 0
0010 0101010 Hamming code for 0010 becomes 0010110 01010101 Hamming code for 0010 becomes 0010110 with extra parity bit 1
1010 1011010 Hamming code for 1010 becomes 1010101 10110100 Hamming code for 1010 becomes 1010101 with extra parity bit 0
0110 1100110 Hamming code for 0110 becomes 0110011 11001100 Hamming code for 0110 becomes 0110011 with extra parity bit 0
1110 0010110 Hamming code for 1110 becomes 1110000 00101101 Hamming code for 1110 becomes 1110000 with extra parity bit 1
0001 1101001 Hamming code for 0001 becomes 0001111 11010010 Hamming code for 0001 becomes 0001111 with extra parity bit 0
1001 0011001 Hamming code for 1001 becomes 1001100 00110011 Hamming code for 1001 becomes 1001100 with extra parity bit 1
0101 0100101 Hamming code for 0101 becomes 0101010 01001011 Hamming code for 0101 becomes 0101010 with extra parity bit 1
1101 1010101 Hamming code for 1101 becomes 1101001 10101010 Hamming code for 1101 becomes 1101001 with extra parity bit 0
0011 1000011 Hamming code for 0011 becomes 0011001 10000111 Hamming code for 0011 becomes 0011001 with extra parity bit 1
1011 0110011 Hamming code for 1011 becomes 1011010 01100110 Hamming code for 1011 becomes 1011010 with extra parity bit 0
0111 0001111 Hamming code for 0111 becomes 0111100 00011110 Hamming code for 0111 becomes 0111100 with extra parity bit 0
1111 1111111 Hamming code for 1111 becomes 1111111 11111111 Hamming code for 1111 becomes 1111111 with extra parity bit 1