YaChudo

Гемінг(7,4)

Переглядів: 0. Оновлено 24.10.2026.

Графічне подання 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
Переданий біт p 1 {\displaystyle p_{1}} p 2 {\displaystyle p_{2}} d 1 {\displaystyle d_{1}} p 3 {\displaystyle p_{3}} d 2 {\displaystyle d_{2}} d 3 {\displaystyle d_{3}} d 4 {\displaystyle d_{4}}
p 1 {\displaystyle p_{1}} Так Ні Так Ні Так Ні Так
p 2 {\displaystyle p_{2}} Ні Так Так Ні Ні Так Так
p 3 {\displaystyle p_{3}} Ні Ні Ні Так Так Так Так

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

Багаторазові бітові помилки

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

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

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

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

Кодові комбінації

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

Дані

( d 1 , d 2 , d 3 , d 4 ) {\displaystyle ({\color {blue}d_{1}},{\color {blue}d_{2}},{\color {blue}d_{3}},{\color {blue}d_{4}})}

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

( p 1 , p 2 , d 1 , p 3 , d 2 , d 3 , d 4 ) {\displaystyle ({\color {red}p_{1}},{\color {red}p_{2}},{\color {blue}d_{1}},{\color {red}p_{3}},{\color {blue}d_{2}},{\color {blue}d_{3}},{\color {blue}d_{4}})}

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

( p 1 , p 2 , d 1 , p 3 , d 2 , d 3 , d 4 , p 4 ) {\displaystyle ({\color {red}p_{1}},{\color {red}p_{2}},{\color {blue}d_{1}},{\color {red}p_{3}},{\color {blue}d_{2}},{\color {blue}d_{3}},{\color {blue}d_{4}},{\color {green}p_{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

    Джерело: стаття у Вікіпедії та історія редагувань (автори).