Hammingův kód, pojmenovaný po Richardu Hammingovi, je lineární kód použiváný v oblasti telekomunikací pro detekci až dvou chybných bitů nebo pro opravu jednoho chybného bitu. Základem je Hammingův kód (7,4), ale lze jej zobecnit i na jiné počty datových a paritních bitů.
Binární kód se nazývá Hammingův, jestliže má kontrolní matici, jejíž
sloupce jsou všechna nenulová slova dané délky
a žádné z nich
se neopakuje.
Jedná se o speciální případ lineárních dvojkových
kódů. Tyto kódy
opravují jednu chybu při vzdálenosti kódových slov
a v rozšířené variantě
.
Algoritmus pro generování Hammingova kódu:
- Všechny bitové pozice, jejichž číslo je rovné mocnině 2, jsou použity pro paritní bit (1, 2, 4, 8, 16, 32, …).
- Všechny ostatní bitové pozice náleží kódovanému informačnímu slovu (3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17, …).
- Každý paritní bit je vypočítán z některých bitů informačního slova. Pozice paritního bitu udává sekvenci bitů, které jsou v kódovém slově zjišťovány a které přeskočeny.
Pro paritní bit
(pozice 1) se ve zbylém kódovém slově 1 bit přeskočí, 1
zkontroluje, 1 bit přeskočí, 1 zkontroluje, atd.
Pro paritní bit
(pozice 2) se přeskočí první bit, 2 zkontrolují, 2 přeskočí, 2 zkontrolují, atd.
Pro
(pozice 4) se přeskočí první 3 bity, 4 zkontrolují, 4 přeskočí,
4 zkontrolují, atd.
Pro kód
platí
:
(podle bodu 3 sestaveno z
),
(
),
(
).
Generující matice
Hamming. kódu
se sestrojí tak, že se
postupně zakóduje posloupnost
(proto, aby řádky byly lineárně nezávislé a tvořily bázi prostoru).
Kontrolní matice
Hamming. kódu
se určí
následovně. Po přijetí kódového slova
víme, že bity
obsahují informační slovo a zbylé redundantní
bity jsou určeny tak, aby
Vektor
se nazývá syndrom a pokud byla
informace přijata bezchybně, jeho hodnota je
.
Rozšíření binárního Hammingova kódu vychází z toho, že přidáme na
začátek každého kódového slova nový symbol určený pro kontrolu parity
celého kódového slova. Bit
je zvolen tak, aby
vycházelo jako sudé
číslo. Rozšířený kód dovoluje, tak jako předchozí opravit jednu chybu
a navíc je schopen detekovat dvě chyby.
Generující matice
rozšířeného Hamming. kódu
se
sestrojí tak, že se postupně zakóduje posloupnost
.
Nejprve se po přijetí kódového slova
určí syndrom
. Například pro přijaté slovo
je syndrom
Vidíme, že syndrom
je nenulový, tj. při přenosu došlo k
chybě. Syndrom, který vyšel
odpovídá sloupci
6 kontrolní matice
a z toho vyplývá, že je třeba opravit
šestý bit kódového slova
.
Pro rozšířený Hammingův kód (8,4) kontrolní matici
přidáme jednotkový řádek a nulový sloupec