Code

Kódování převádí informace jednoho typu do jiné reprezentace. Například morseovka.

Neplést si s šifrováním! U kódování je známo jak se to převádí, u šifrování ne.

Shannon's source coding theorem

Forward error correction

Pokud se zprávy posílají po nespolehlivém médi na kterém vznikají chyby, používají se bezpečnostní kódy. Tyto kódy umožňují chybu detekovat, a ideálně i opravit. Slovo s bezpečnostním kódem musí být vždy delší než původní slovo, dochází k redundanci.

Linear code

Lineární bezpečnostní kód je takový kód, kde libovolná lineární kombinace kódových slov je také kódové slovo.

Hamming code, Hamming(7,4)

Hammingův kód (7, 4) znamená že ze 4 bitů zprávy vytvoříme 7 bitů přídáním 3 paritních bitů. Tento kód umožňuje detekovat 2 chybné bity a 1 bit opravit. Paritní a datové pity jsou uspořádány: PPDPDDD.

Potřebujeme generovací matici G a paritní matici H:

<m>G = (matrix{7}{4}{1 1 0 1 1 0 1 1 1 0 0 0 0 1 1 1 0 1 0 0 0 0 1 0 0 0 0 1})</m>

<m>H = (matrix{3}{7}{1 0 1 0 1 0 1 0 1 1 0 0 1 1 0 0 0 1 1 1 1})</m>

Všimněte si u matice G, že řádky 3, 5, 6 a 7 reprezentují datové bity a obsahují jen jednu 1. Oproti tomu řádky 1, 2 a 4 jsou bity paritní, a označují ze kterých bitů se bude parita počítat.

Jak si zapamatovat který paritní bit pokrýva které datové nevím.

Výslednou zprávu získáme vynásobením matice G zprávou (1011):

<m>(matrix{7}{4}{1 1 0 1 1 0 1 1 1 0 0 0 0 1 1 1 0 1 0 0 0 0 1 0 0 0 0 1}) * (matrix{4}{1}{1 0 1 1}) = (matrix{7}{1}{0 1 1 0 0 1 1})</m>

Výsledná zpráva tedy bude 0110011.

Při kontrole vynásobíme matici H zprávou:

<m>(matrix{3}{7}{1 0 1 0 1 0 1 0 1 1 0 0 1 1 0 0 0 1 1 1 1}) * = (matrix{7}{1}{0 1 1 0 0 1 1}) = (matrix{3}{1}{0 0 0})</m>

Opět můžeme použít trik se stejnými jedničkami.

Pokud vyjdou samé nuly, byla zpráva přijata v pořádku.

Pokud ne, porovnáme matici se sloupci matice H a ten u kterého se shoduje je chybný bit. Stejně tak můžeme binární čislo přečíst odzhora. Například 101 = 5, a také je to 5. sloupec v matici H.

Cyclic code

Convolutional code