Hammingův kód

Technology

12 hours ago

Author

Hammingův kód, pojmenovaný po Richardu Hammingovi, je lineární kód používaný 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 a žádné z nich se neopakuje.

Jedná se o speciální případ lineárních dvojkových (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 a v rozšířené variantě d_{min}({\overrightarrow{b}}_i, {\overrightarrow{b}}_j)=4.

Generování Hammingova kódu

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, …). +more # 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 (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 (pozice 2) se přeskočí první bit, 2 zkontrolují, 2 přeskočí, 2 zkontrolují, atd.

Pro 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) 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):

* 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), * p_2 \oplus a_1\oplus a_3 \oplus a_4 = 0 (b_2, b_3, b_6, b_7), * p_3 \oplus a_2\oplus a_3 \oplus a_4 = 0 (b_4, b_5, b_6, b_7).

Generující matice \mathbb{G}_H Hamming. kódu (7, 4) se sestrojí tak, že se postupně zakóduje posloupnost 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)

Kontrolní matice \mathbb{H}_H Hamming. kódu (7, 4) se určí následovně. +more Po přijetí kódového slova {\overrightarrow{b}} víme, že bity 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).

Vektor {\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).

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 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 vycházelo jako sudé číslo. +more 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' rozšířeného Hamming. kódu (8, 4) se sestrojí tak, že se postupně zakóduje posloupnost 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)

Dekódování a kontrola

Nejprve se po přijetí kódového slova {\overrightarrow{b}} určí syndrom {\overrightarrow{s}} = \mathbb H_H\cdot{\overrightarrow{b}}^T. Například pro přijaté slovo {\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)

Vidíme, že syndrom {\overrightarrow{s}} je nenulový, tj. při přenosu došlo k chybě. +more Syndrom, který vyšel {\overrightarrow{s}} = (1,1,0) odpovídá sloupci 6 kontrolní matice \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). Pro rozšířený Hammingův kód (8,4) kontrolní matici \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)