Коди Хеммінга: Виправлення перевернутого біта без повторного запиту

Цілеспрямоване надлишко

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

Розміщення бітів парності на степенях двійки

Ключова ідея полягає в тому, де розташовані біти парності. У 7-бітному слові, нумерованому від 1 до 7, біти парності знаходяться у позиціях 1, 2 та 4 — степенях двійки; а дані – у позиціях 3, 5, 6 і 7. Кожен біт парності охоплює конкретний, перекривний підмножину позицій, визначений його власною бітовою представленням номера позиції: біт парності в позиції 1 охоплює кожну позицію, у якій встановлено біт 0 (1, 3, 5, 7), біт парності в позиції 2 охоплює позиції з встановленим бітом 1 (2, 3, 6, 7), а біт парності в позиції 4 охоплює позиції з встановленим бітом 2 (4, 5, 6, 7).

позиція: 1 2 3 4 5 6 7 міст: p1 p2 d1 p4 d2 d3 d4 p1 перевіряє позиції 1,3,5,7 (біт 0 у номері позиції встановлено) p2 перевіряє позиції 2,3,6,7 (біт 1 у номері позиції встановлено) p4 перевіряє позиції 4,5,6,7 (біт 2 у номері позиції встановлено) kждый pi встановлюється так, щоб парність (XOR) у покритих позиціях була навіть Це перекриття є всім секретом: кожен біт даних покривається унікальною комбінацією бітів парності, тому помилка в цьому одному біті даних порушує унікальний та ідентифікований підмножину перевірок парності.

position:   1  2  3  4  5  6  7
content:    p1 p2 d1 p4 d2 d3 d4

p1 checks positions 1,3,5,7   (bit 0 of position set)
p2 checks positions 2,3,6,7   (bit 1 of position set)
p4 checks positions 4,5,6,7   (bit 2 of position set)

each pi is set so the parity (XOR) of its covered positions is even

Синдром: три перевірки, що визначають позицію

На приймаючій стороні обчислюється три перевірки парності над отриманим словом. Якщо перевірка виявляється непарною, результат дорівнює 1; якщо парною — 0. Три результати стовпцями утворюють синдром. Синдром може бути рівним нулю (без помилок) або точному положенню перевернутої біта, оскільки набори покриття будувалися безпосередньо з біт-цифр кожного місця.

синдром = (перевірка_p4 << 2) | (перевірка_p2 << 1) | перевірка_p1 синдром == 0 → не виявлено помилок синдром == k → біт у позиції k неправильний — переверніть його і ви закінчили

syndrome = (check_p4 << 2) | (check_p2 << 1) | check_p1

syndrome == 0   → no error detected
syndrome == k   → bit at position k is wrong — flip it and you're done

SECDED: додавання четвертого біта для подвійного виявлення помилок

Основний (7,4) код Гармінга має недоліки: якщо дві біти одночасно змінюються, синдром все ще вказує впевнено на певну позицію – неправильну, і декодер виправля стілько разів, коли помилки не було, непомітно погіршуючи її. Виправлення, яке використовується практично у всіх реальних розгортаннях, це SECDED (виправлення однієї помилки, виявлення подвійних помилок): додайте один додатковий біт загальної парності, що охоплює все слово, включаючи інші біти парності. Однобітова помилка змінює загальну парність і дає невід’ємний синдром – виправляється як зазвичай. Двобітова помилка дає невід’ємний синдром (неправильно вказує кудись), але залишає загальну парність без змін, і ця розбіжність між «синдромом каже про помилку» та «загальна парність говорить про відсутність помилки» є чітким сигналом невідремонтованої подвійної помилки, тому декодер позначає її замість того, щоб неправильно виправляти.

Визначення місця фактичної роботи

Коди Хеммінга SECDed захищають ECC пам’ять у серверах та робочих станціях від випадкових збоїв бітів, спричинених космічним випромінюванням і альфа-частинками, а також зв’язків телеметрії в космосі та контролерів NAND flash, де час на повторний запит може становити кілька хвилин. Ця схема узагальнюється за межами (7,4): код Хеммінга з r бітами парності захищає 2^r − 1 загальних бітів (2^r − r − 1 даних), тому коди (15,11), (31,26) та (63,57) обмінюються меншим відсотковим навантаженням за ту ж гарантію однобітової корекції при збільшенні розміру блоку — але з більшим радіусом ураження, якщо випадково виникне ще один збій бітів всередині того ж розширеного блоку.

Frequently asked questions

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Hamming Codes і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.