Hammingův kód

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

V oblasti telekomunikací je Hammingův kód lineární kód pro opravu jedné chyby, pojmenovaný po jeho objeviteli Richardu Hammingovi.

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[editovat | editovat zdroj]

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 (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)[editovat | editovat zdroj]

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ě. 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)[editovat | editovat zdroj]

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. 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[editovat | editovat zdroj]

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ě. 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)