Hammingův kód

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 $n-k=r$$n-k=r$ a žádné z nich se neopakuje.

Jedná se o speciální případ lineárních dvojkových $(n,k)$$(n,k)$ kódů. Tyto kódy opravují jednu chybu při vzdálenosti kódových slov $d_{min}({\overrightarrow {b}}_{i},{\overrightarrow {b}}_{j})=3$$d_{min}({\overrightarrow {b}}_{i},{\overrightarrow {b}}_{j})=3$ a v rozšířené variantě $d_{min}({\overrightarrow {b}}_{i},{\overrightarrow {b}}_{j})=4$$d_{min}({\overrightarrow {b}}_{i},{\overrightarrow {b}}_{j})=4$.

Generování Hammingova kódu

Algoritmus pro generování Hammingova kódu:

1. Všechny bitové pozice, jejichž číslo je rovné mocnině 2, jsou použity pro paritní bit (1, 2, 4, 8, 16, 32, …).
2. 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, …).
3. 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 $p_{1}$$p_{1}$ (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 $p_{2}$$p_{2}$ (pozice 2) se přeskočí první bit, 2 zkontrolují, 2 přeskočí, 2 zkontrolují, atd.
Pro $p_{3}$$p_{3}$ (pozice 4) se přeskočí první 3 bity, 4 zkontrolují, 4 přeskočí, 4 zkontrolují, atd.

Hammingův kód (7,4)

Pro kód $(7,4)$$(7,4)$ platí ${\overrightarrow {b}}=\left(p_{1}^{(2^{0})},p_{2}^{(2^{1})},a_{1}^{3},p_{3}^{(2^{2})},a_{2}^{5},a_{3}^{6},a_{4}^{7}\right)$${\overrightarrow {b}}=\left(p_{1}^{(2^{0})},p_{2}^{(2^{1})},a_{1}^{3},p_{3}^{(2^{2})},a_{2}^{5},a_{3}^{6},a_{4}^{7}\right)$:

• $p_{1}\oplus a_{1}\oplus a_{2}\oplus a_{4}=0$$p_{1}\oplus a_{1}\oplus a_{2}\oplus a_{4}=0$ (podle bodu 3 sestaveno z $b_{1},b_{3},b_{5},b_{7}$$b_{1},b_{3},b_{5},b_{7}$),
• $p_{2}\oplus a_{1}\oplus a_{3}\oplus a_{4}=0$$p_{2}\oplus a_{1}\oplus a_{3}\oplus a_{4}=0$ ($b_{2},b_{3},b_{6},b_{7}$$b_{2},b_{3},b_{6},b_{7}$),
• $p_{3}\oplus a_{2}\oplus a_{3}\oplus a_{4}=0$$p_{3}\oplus a_{2}\oplus a_{3}\oplus a_{4}=0$ ($b_{4},b_{5},b_{6},b_{7}$$b_{4},b_{5},b_{6},b_{7}$).

Generující matice $\mathbb {G} _{H}$$\mathbb {G} _{H}$ Hamming. kódu $(7,4)$$(7,4)$ se sestrojí tak, že se postupně zakóduje posloupnost $1000_{1},0100_{2},0010_{3},0001_{4}$$1000_{1},0100_{2},0010_{3},0001_{4}$ (proto, aby řádky byly lineárně nezávislé a tvořily bázi prostoru).

$\mathbb {G} _{H}=\left({\begin{matrix}&~_{1}&~_{2}&~_{3}&~_{4}&~_{5}&~_{6}&~_{7}\\~_{1}&p_{1_{1}}&p_{2_{1}}&1&p_{3_{1}}&0&0&0\\~_{2}&p_{1_{2}}&p_{2_{2}}&0&p_{3_{2}}&1&0&0\\~_{3}&p_{1_{3}}&p_{2_{3}}&0&p_{3_{3}}&0&1&0\\~_{4}&p_{1_{4}}&p_{2_{4}}&0&p_{3_{4}}&0&0&1\\\end{matrix}}\right)=\left({\begin{matrix}&~_{1}&~_{2}&~_{3}&~_{4}&~_{5}&~_{6}&~_{7}\\~_{1}&1&1&1&0&0&0&0\\~_{2}&1&0&0&1&1&0&0\\~_{3}&0&1&0&1&0&1&0\\~_{4}&1&1&0&1&0&0&1\\\end{matrix}}\right)$$\mathbb {G} _{H}=\left({\begin{matrix}&~_{1}&~_{2}&~_{3}&~_{4}&~_{5}&~_{6}&~_{7}\\~_{1}&p_{1_{1}}&p_{2_{1}}&1&p_{3_{1}}&0&0&0\\~_{2}&p_{1_{2}}&p_{2_{2}}&0&p_{3_{2}}&1&0&0\\~_{3}&p_{1_{3}}&p_{2_{3}}&0&p_{3_{3}}&0&1&0\\~_{4}&p_{1_{4}}&p_{2_{4}}&0&p_{3_{4}}&0&0&1\\\end{matrix}}\right)=\left({\begin{matrix}&~_{1}&~_{2}&~_{3}&~_{4}&~_{5}&~_{6}&~_{7}\\~_{1}&1&1&1&0&0&0&0\\~_{2}&1&0&0&1&1&0&0\\~_{3}&0&1&0&1&0&1&0\\~_{4}&1&1&0&1&0&0&1\\\end{matrix}}\right)$

Kontrolní matice $\mathbb {H} _{H}$$\mathbb {H} _{H}$ Hamming. kódu $(7,4)$$(7,4)$ se určí následovně. Po přijetí kódového slova ${\overrightarrow {b}}$${\overrightarrow {b}}$ víme, že bity $b_{3},b_{5},b_{6},b_{7}$$b_{3},b_{5},b_{6},b_{7}$ obsahují informační slovo a zbylé redundantní bity jsou určeny tak, aby

${\begin{matrix}s_{1}=b_{4}\oplus b_{5}\oplus b_{6}\oplus b_{7}=0\\s_{2}=b_{2}\oplus b_{3}\oplus b_{6}\oplus b_{7}=0\\s_{3}=b_{1}\oplus b_{3}\oplus b_{5}\oplus b_{7}=0\\\end{matrix}}\Rightarrow \mathbb {H} _{H}=\left({\begin{matrix}~_{1}&~_{2}&~_{3}&~_{4}&~_{5}&~_{6}&~_{7}\\0&0&0&1&1&1&1\\0&1&1&0&0&1&1\\1&0&1&0&1&0&1\\\end{matrix}}\right).$${\begin{matrix}s_{1}=b_{4}\oplus b_{5}\oplus b_{6}\oplus b_{7}=0\\s_{2}=b_{2}\oplus b_{3}\oplus b_{6}\oplus b_{7}=0\\s_{3}=b_{1}\oplus b_{3}\oplus b_{5}\oplus b_{7}=0\\\end{matrix}}\Rightarrow \mathbb {H} _{H}=\left({\begin{matrix}~_{1}&~_{2}&~_{3}&~_{4}&~_{5}&~_{6}&~_{7}\\0&0&0&1&1&1&1\\0&1&1&0&0&1&1\\1&0&1&0&1&0&1\\\end{matrix}}\right).$

Vektor ${\overrightarrow {s}}=(s_{1},s_{2},s_{3})$${\overrightarrow {s}}=(s_{1},s_{2},s_{3})$ se nazývá syndrom a pokud byla informace přijata bezchybně, jeho hodnota je ${\overrightarrow {s}}=(0,0,0)$${\overrightarrow {s}}=(0,0,0)$.

Rozšířený Hammingův kód (8,4)

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 $p_{0}$$p_{0}$ je zvolen tak, aby $p_{0}\oplus b_{1}\oplus b_{2}\oplus b_{3}\oplus b_{4}\oplus b_{5}\oplus b_{6}\oplus b_{7}$$p_{0}\oplus b_{1}\oplus b_{2}\oplus b_{3}\oplus b_{4}\oplus b_{5}\oplus b_{6}\oplus b_{7}$ 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 $\mathbb {G} _{H}'$$\mathbb {G} _{H}'$ rozšířeného Hamming. kódu $(8,4)$$(8,4)$ se sestrojí tak, že se postupně zakóduje posloupnost $1000_{1},0100_{2},0010_{3},0001_{4}$$1000_{1},0100_{2},0010_{3},0001_{4}$.

$\mathbb {G} _{H}'=\left({\begin{matrix}~&~_{0}&~_{1}&~_{2}&~_{3}&~_{4}&~_{5}&~_{6}&~_{7}\\~_{1}&p_{0_{1}}&p_{1_{1}}&p_{2_{1}}&1&p_{3_{1}}&0&0&0\\~_{2}&p_{0_{2}}&p_{1_{2}}&p_{2_{2}}&0&p_{3_{2}}&1&0&0\\~_{3}&p_{0_{3}}&p_{1_{3}}&p_{2_{3}}&0&p_{3_{3}}&0&1&0\\~_{4}&p_{0_{4}}&p_{1_{4}}&p_{2_{4}}&0&p_{3_{4}}&0&0&1\\\end{matrix}}\right)=\left({\begin{matrix}~&~_{0}&~_{1}&~_{2}&~_{3}&~_{4}&~_{5}&~_{6}&~_{7}\\~_{1}&1&1&1&1&0&0&0&0\\~_{2}&1&1&0&0&1&1&0&0\\~_{3}&1&0&1&0&1&0&1&0\\~_{4}&0&1&1&0&1&0&0&1\\\end{matrix}}\right)$$\mathbb {G} _{H}'=\left({\begin{matrix}~&~_{0}&~_{1}&~_{2}&~_{3}&~_{4}&~_{5}&~_{6}&~_{7}\\~_{1}&p_{0_{1}}&p_{1_{1}}&p_{2_{1}}&1&p_{3_{1}}&0&0&0\\~_{2}&p_{0_{2}}&p_{1_{2}}&p_{2_{2}}&0&p_{3_{2}}&1&0&0\\~_{3}&p_{0_{3}}&p_{1_{3}}&p_{2_{3}}&0&p_{3_{3}}&0&1&0\\~_{4}&p_{0_{4}}&p_{1_{4}}&p_{2_{4}}&0&p_{3_{4}}&0&0&1\\\end{matrix}}\right)=\left({\begin{matrix}~&~_{0}&~_{1}&~_{2}&~_{3}&~_{4}&~_{5}&~_{6}&~_{7}\\~_{1}&1&1&1&1&0&0&0&0\\~_{2}&1&1&0&0&1&1&0&0\\~_{3}&1&0&1&0&1&0&1&0\\~_{4}&0&1&1&0&1&0&0&1\\\end{matrix}}\right)$

Dekódování a kontrola

Nejprve se po přijetí kódového slova ${\overrightarrow {b}}$${\overrightarrow {b}}$ určí syndrom ${\overrightarrow {s}}=\mathbb {H} _{H}\cdot {\overrightarrow {b}}^{T}$${\overrightarrow {s}}=\mathbb {H} _{H}\cdot {\overrightarrow {b}}^{T}$. Například pro přijaté slovo ${\overrightarrow {b}}=(1010111)$${\overrightarrow {b}}=(1010111)$ je syndrom

$\mathbb {H} _{H}\cdot {\overrightarrow {b}}^{T}=\left({\begin{matrix}0&0&0&1&1&1&1\\0&1&1&0&0&1&1\\1&0&1&0&1&0&1\\\end{matrix}}\right)\cdot \left({\begin{matrix}1\\0\\1\\0\\1\\1\\1\\\end{matrix}}\right)=\left({\begin{matrix}1\\1\\0\\\end{matrix}}\right)$$\mathbb {H} _{H}\cdot {\overrightarrow {b}}^{T}=\left({\begin{matrix}0&0&0&1&1&1&1\\0&1&1&0&0&1&1\\1&0&1&0&1&0&1\\\end{matrix}}\right)\cdot \left({\begin{matrix}1\\0\\1\\0\\1\\1\\1\\\end{matrix}}\right)=\left({\begin{matrix}1\\1\\0\\\end{matrix}}\right)$

Vidíme, že syndrom ${\overrightarrow {s}}$${\overrightarrow {s}}$ je nenulový, tj. při přenosu došlo k chybě. Syndrom, který vyšel ${\overrightarrow {s}}=(1,1,0)$${\overrightarrow {s}}=(1,1,0)$ odpovídá sloupci 6 kontrolní matice $\mathbb {H} _{H}$$\mathbb {H} _{H}$ a z toho vyplývá, že je třeba opravit šestý bit kódového slova ${\overrightarrow {b}}'=(10101{\underline {0}}1)$${\overrightarrow {b}}'=(10101{\underline {0}}1)$. Pro rozšířený Hammingův kód (8,4) kontrolní matici $\mathbb {H} _{H}$$\mathbb {H} _{H}$ přidáme jednotkový řádek a nulový sloupec

$\mathbb {H} _{H}\ =\left({\begin{matrix}0&0&0&1&1&1&1&0\\0&1&1&0&0&1&1&0\\1&0&1&0&1&0&1&0\\1&1&1&1&1&1&1&1\\\end{matrix}}\right)$$\mathbb {H} _{H}\ =\left({\begin{matrix}0&0&0&1&1&1&1&0\\0&1&1&0&0&1&1&0\\1&0&1&0&1&0&1&0\\1&1&1&1&1&1&1&1\\\end{matrix}}\right)$