DevDays
← Усі нотатки

Нотатка · Кодування

Код Геммінга: як відновити чотири біти після помилки

У Telegram:

Потрібно передати чотири біти:

1011

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

Тому до чотирьох корисних бітів додамо три перевірочні. Отримаємо код Геммінга 7,4: сім бітів передають чотири біти даних і дозволяють виправити одну помилку.

Розкладаємо біти по позиціях:

Позиція:  1  2  3  4  5  6  7
Вміст:   p1 p2 d1 p4 d2 d3 d4
Значення: p1 p2  1 p4  0  1  1

Перевірочні біти відповідають за різні групи:

p1 перевіряє позиції 1, 3, 5, 7
p2 перевіряє позиції 2, 3, 6, 7
p4 перевіряє позиції 4, 5, 6, 7

Їх підбираємо так, щоб XOR усіх бітів у кожній групі дорівнював нулю. Для 1011 отримуємо:

p1 = 0
p2 = 1
p4 = 0

Передаємо: 0110011

Припустимо, шостий біт пошкодився:

Було:     0110011
Прийшло:  0110001

Приймач повторює три перевірки:

s1 = 0
s2 = 1
s4 = 1

s4 s2 s1 = 110₂ = 6

Число 6 прямо вказує на пошкоджену позицію. Змінюємо шостий біт назад, а з позицій 3, 5, 6 і 7 забираємо початкові дані:

0110001 → 0110011 → 1011

На рівні процесора саме виправлення займає кілька команд. Три перевірки вже записали номер пошкодженої позиції в BL, а отримані сім бітів лежать у AL:

test bl, bl
jz   .done

mov  cl, 7
sub  cl, bl
mov  dl, 1
shl  dl, cl
xor  al, dl

.done:

test bl, bl перевіряє, чи дорівнює номер помилки нулю. jz .done завершує виправлення, якщо всі перевірки пройшли.

Позиції в нашому записі рахуються зліва направо від 1 до 7, а зсув у регістрі — справа наліво від 0. Команди mov cl, 7 і sub cl, bl переводять номер позиції у потрібну кількість зсувів. Для позиції 6 отримаємо один зсув.

mov dl, 1 створює одиницю, а shl dl, cl пересуває її до пошкодженого біта. Для шостої позиції маска виглядає так:

00000010

xor al, dl перемикає лише цей біт: 0 стає 1, а 1 — 0. Інші біти не змінюються.

За можливість відновлення заплатили трьома додатковими бітами. Код Геммінга 7,4 виправляє одну помилку, але не врятує від довільної кількості пошкоджень. Складніші коди додають більше надлишкової інформації.

Саме завдяки їй працюють ECC-пам’ять, QR-коди, супутниковий зв’язок і носії даних. Надлишкові біти здаються зайвими лише доти, доки щось не зламається 😄

Ще нотатки