Hammingkódokat

Hammingkódok olyan bináris lineáris blokk-kódok, amelyeket Richard Hamming fejlesztett ki 1950-ben. Céljuk egységnyi vagy egy bit hibák kijavítása, illetve legfeljebb kettő bit hibájának detektálása adatátvitelben vagy memóriákban. A kódok minimális távolsága dmin = 3, ezért egy hibát javítani és kettő hibát detektálni lehet.

Formálisan a kód egy [n, k, d] lineáris kód, ahol n = 2^m − 1, k = n − m és d = 3. A kódolt szavak a generátormátrixszal, G-vel meghatározott módon keletkeznek: c = uG. Paritásellenőrző mátrixot H használva a kód megfelelési feltétele cH^T = 0. Dekódolásnál a kapott r szót szindrómával számítjuk: s = rH^T. Ha s = 0, nincs hiba; ha s ≠ 0, a szindróma bináris alakja megadja a hibás bit pozícióját, amelyet ki kell javítani. Így a Hammingkódok egyetlen bit hibát képesek helyreállítani, és a kettő vagy több hibát csak detektálni.

Példaként a legismertebb Hamming-kód az (7,4,3). Ebben az esetben n = 7, k = 4 és dmin = 3. Az adatbitok a 3., 5., 6., 7. pozíciókban helyezkednek el, a 1., 2., 4. pozíciókban pedig paritásbiteket számolunk ki. A paritásfeltételek például így érvényesek: c1 = d1 ⊕ d2 ⊕ d4, c2 = d1 ⊕ d3 ⊕ d4, c4 = d2 ⊕ d3 ⊕ d4. Így a kódolt szó c = [c1, c2, d1, c4, d2, d3, d4]. Egy hibás bit esetén a szindróma meghatározza a hibás pozíciót, amelyet ki kell javítani.

Bővített ( extended ) Hamming-kódoknál egy további paritásbitet adnak hozzá, így n = 2^m, k = 2^m − m − 1, dmin = 4. Ez lehetővé teszi, hogy kettő hibát detektáljunk és egyet korrigáljunk. A Hamming-kódok egyszerűsége és gyors dekódolhatósága miatt széles körben alkalmazzák memória- és adatszövetek megbízhatóságának növelésére, például ECC RAM-ban vagy adatátviteli protokollokban.