② Закодоване кодове слово (натисніть будь-який біт для перекидання — симуляція помилки)
✓ Помилок не виявлено
③ Виправлені / отримані біти повідомлення
Матриця перевірки парності H (рядки = перевірки парності)
Синдром s = H · r̃ (отримане кодове слово)
s = 000 → помилок немає
Про коди виправлення помилок Геммінга
Коди Геммінга, винайдені Річардом Геммінгом у Bell Labs у 1950 році, є найпростішим класом лінійних кодів виправлення помилок. Вставляючи надлишкові біти парності на позиціях, що є степенями двійки, у межах слова даних, вони створюють кодове слово, у якому будь-яке однобітове пошкодження можна знайти та відновити без повторної передачі даних.
Ключова ідея — матриця перевірки парності H: кожен стовпець є двійковим представленням його індексу позиції, тому синдром s = H·r, обчислений із отриманого кодового слова r, безпосередньо вказує позицію помилкового біта у двійковому форматі. Інвертуйте цей біт — і вихідне повідомлення відновлено. SECDED розширює це ще одним загальним бітом парності, збільшуючи мінімальну відстань Геммінга до 4 — достатньо для виявлення двох одночасних помилок, навіть якщо можна виправити лише одну.
Ця симуляція дозволяє інтерактивно досліджувати Hamming(7,4) та SECDED(8,4). Перемикайте чотири біти повідомлення, потім натискайте будь-який біт закодованого кодового слова для введення однобітової помилки (або два біти для тестування виявлення подвійної помилки). Спостерігайте, як синдром виділяє позицію несправного біта та миттєво відображається виправлене повідомлення.
Часті запитання
Що таке код Геммінга?
Код Геммінга — це лінійний код виправлення помилок, винайдений Річардом Геммінгом у 1950 році. Він додає надлишкові біти парності до слова даних, щоб будь-яку однобітову помилку можна було виявити та виправити. Hamming(7,4) кодує 4 біти даних у 7-бітне кодове слово, використовуючи 3 біти парності на позиціях, що є степенями двійки.
Як працює синдромне декодування?
Після отримання кодового слова декодер множить його на матрицю перевірки парності H, отримуючи вектор синдрому s = H·r mod 2. Якщо s = 0 — помилок немає. Якщо s ненульовий, його двійкове значення безпосередньо вказує позицію помилкового біта, який потім інвертується для виправлення помилки.
Що таке SECDED і чому це важливо?
SECDED означає Single Error Correct, Double Error Detect (виправлення однієї помилки, виявлення двох помилок). Він розширює Hamming(7,4) до Hamming(8,4), додаючи загальний біт парності. Цей біт збільшує мінімальну відстань Геммінга з 3 до 4. ОЗП з ЕКВ у серверах використовує SECDED для захисту від перекидань бітів, спричинених космічними променями або коливаннями напруги.
Де використовуються коди Геммінга на практиці?
Коди Геммінга використовуються в ОЗП з ЕКВ у серверах та робочих станціях, у каналах супутникового зв'язку, у контролерах пам'яті DRAM, у деяких системах флеш-пам'яті NAND. Вони є концептуальною основою для більш просунутих кодів, таких як Ріда-Соломона та турбокоди.
Чому біти парності розміщуються на позиціях — степенях двійки?
Позиції 1, 2, 4, 8, … вибрані так, щоб кожен біт парності охоплював унікальну підмножину позицій даних. Це гарантує, що синдром будь-якої однобітової помилки безпосередньо кодує позицію помилки у двійковому форматі, роблячи виправлення простим без таблиці пошуку.
Що таке відстань Геммінга?
Відстань Геммінга між двома двійковими рядками — це кількість позицій, у яких вони різняться. Мінімальна відстань Геммінга d_min коду визначає його потужність виправлення помилок. Hamming(7,4) має d_min = 3, тому виправляє 1 помилку; SECDED має d_min = 4, виправляючи 1 та виявляючи 2.
Яка швидкість коду Hamming(7,4)?
Швидкість коду — це відношення бітів даних до загальної кількості бітів кодового слова. Для Hamming(7,4) швидкість становить 4/7 ≈ 0,571, тобто близько 57% переданих бітів несуть інформацію. Зі збільшенням розміру блоку коди Геммінга стають ефективнішими: Hamming(15,11) має швидкість 11/15 ≈ 0,733.
Чи можуть коди Геммінга виправляти більше однієї бітової помилки?
Стандартний Hamming(7,4) може виправляти лише однобітові помилки. Якщо перекинути два біти, синдром вказуватиме на неправильну позицію. SECDED може виявляти (але не виправляти) двобітові помилки. Для виправлення кількох помилок використовуються більш потужні коди: Ріда-Соломона, LDPC або турбокоди.
Як будується матриця перевірки парності H?
Для Hamming(7,4) кожен стовпець H є двійковим представленням номера стовпця (від 1 до 7). Стовпець 1 = 001, стовпець 2 = 010, стовпець 3 = 011 і так далі. Рядки відповідають перевіркам парності s1, s2, s4. Синдром s = H·r ізолює позицію помилки, оскільки кожна бітова позиція має унікальне двійкове кодування як стовпець H.
У чому різниця між виявленням і виправленням помилок?
Виявлення помилок означає, що приймач може визначити, що щось пішло не так, але не може виправити помилку. Виправлення помилок означає, що приймач має достатньо надлишковості для відновлення вихідних даних без повторної передачі. Коди Геммінга забезпечують обидва режими: виявляють до 2 помилок та виправляють 1.
Про коди Хемінга SECDED
Коди Хемінга — сімейство лінійних кодів із виправленням помилок, винайдених Річардом Хемінгом у Bell Labs у 1950 році. Код Хемінга(7,4) кодує 4 біти даних у 7-бітне кодове слово, додаючи 3 перевірних біти на позиціях степенів двійки (1, 2, 4); кожен перевірний біт покриває певну підмножину позицій бітів даних, визначену стовпцями перевірної матриці H. Це дає мінімальну відстань Хемінга 3, гарантуючи виправлення будь-якої однобітової помилки та виявлення будь-якої двобітової. Додавання одного загального біта парності дає код SECDED (Single-Error Correcting, Double-Error Detecting) Хемінга(8,4), що використовується в ECC-пам'яті, де перевернутий біт пам'яті автоматично виправляється при кожному зчитуванні.
Симулятор дозволяє вводити 4-бітні слова даних, спостерігати, як матриця перевірки кодує їх у 7- або 8-бітні кодові слова, вводити однобітові або двобітові помилки і спостерігати декодування за синдромом: вектор синдрому s = H·r (mod 2) безпосередньо вказує на позицію помилкового біта, дозволяючи автоматичне виправлення за один крок.
Часті запитання
Як декодування за синдромом знаходить однобітову помилку?
Після отримання кодового слова r декодер обчислює синдром s = H·r (mod 2), де H — матриця перевірки. Якщо s = 0, помилок не виявлено. Якщо s ≠ 0, він збігається з одним зі стовпців H; позиція цього стовпця вказує на біт, який потрібно перевернути. Для Хемінга(7,4) синдром — 3-бітне двійкове число, що безпосередньо дорівнює 1-базованому індексу помилкового біта.
Що таке відстань Хемінга і чому вона важлива?
Відстань Хемінга між двома кодовими словами — кількість бітів, якими вони відрізняються. Код із мінімальною відстанню Хемінга d_min може виявляти до d_min − 1 помилок і виправляти до ⌊(d_min − 1)/2⌋ помилок. Хемінг(7,4) має d_min = 3: виправляє 1 помилку і виявляє 2.
Що таке ECC-пам'ять і як вона використовує коди Хемінга?
Оперативна пам'ять із виправленням помилок (ECC RAM) використовує схему Хемінга SECDED для кожного 64-бітного слова пам'яті, додаючи 8 перевірних бітів (72 біти на слово). Синдром обчислюється апаратно при кожному зчитуванні; однобітова помилка виправляється прозоро за один цикл пам'яті (~60 нс для DDR5) без залучення програмного забезпечення.
Чому перевірні біти розміщуються на позиціях степенів двійки?
У конструкції Хемінга перевірний біт на позиції 2ᵏ охоплює всі позиції бітів, двійкове представлення яких містить 1 на k-й позиції. Наприклад, перевірний біт 1 (позиція 001₂) охоплює позиції 1, 3, 5, 7. Це гарантує, що кожна позиція даних покрита унікальною непорожньою підмножиною перевірних бітів, тому синдром однозначно ідентифікує позицію будь-якої однобітової помилки.
Яка різниця між Хемінгом(7,4) і Хемінгом(8,4) SECDED?
Хемінг(7,4) використовує 3 перевірні біти для 4 бітів даних і виправляє 1 помилку (d_min = 3). Додавання четвертого загального біта парності (XOR усіх 7 бітів) дає Хемінг(8,4), який виявляє подвійні помилки: ненульовий синдром при збіжній загальній парності сигналізує про 2-бітну помилку замість спроби виправлення. Ця властивість SECDED критична для систем пам'яті, де двобітові помилки можливі при космічних подіях або збоях кількох клітинок.
Що таке коди Ріда-Соломона і як вони порівнюються?
Коди Ріда-Соломона оперують над більшими алфавітами (символи по k бітів, а не окремі біти) і можуть виправляти кілька символьних помилок. Код Ріда-Соломона(255,223) (використовується на CD, DVD, QR-кодах і в космічному зв'язку) виправляє до 16 символьних помилок на 255-символьний блок. Коди Хемінга оптимальні для виправлення однобітових помилок з мінімальною надлишковістю, а Рід-Соломон набагато потужніший для серій помилок.
Що таке межа Хемінга (межа пакування сфер)?
Межа Хемінга стверджує: для двійкового коду довжини n, що виправляє t помилок, кількість кодових слів M задовольняє M · Σᵢ₌₀ᵗ C(n,i) ≤ 2ⁿ. Коди, що досягають рівності, називаються досконалими; коди Хемінга є досконалими — їхні сфери помилок радіуса 1 без прогалин розбивають весь n-бітний простір. Єдині інші двійкові досконалі коди — тривіальний код повторення і код Голея(23,12).
Що відбувається при двох одночасних бітових помилках у Хемінгу(7,4)?
При лише однобітовому виправленні (без загального біта парності) 2-бітова помилка дає ненульовий синдром, що збігається з якимось стовпцем H — але не тим. Декодер «виправляє» неправильний біт, вносячи третю помилку і приховано псуючи дані. SECDED (8,4) запобігає цьому: загальний біт парності розрізняє 1-бітові помилки (непарне порушення парності + ненульовий синдром) від 2-бітових (парне порушення + ненульовий синдром), позначаючи останні замість неправильного виправлення.