Státnice z elektroniky

<< předchozí     následující >>

Kapitola 19
Kódy

Systematické a cyklické kódy patří k nejběžnějším blokovým kódům . Blokové kódy mají pro každý přenášený symbol zvláštní kódovou kombinaci (způsob zakódování nezáleží na zakódování jiného bloku). Kódové kombinace systematických i cyklických kódů se dělí na základní (informační) a kontrolní (prověřovací). Každá z těchto skupin symbolů ve všech kódových kombinacích zaujímá tytéž pozice. Tyto kódy se obyčejně značí (n, k) kódy, kde n je délka kódu a k počet informačních znaků v kódové kombinaci. Písmenem N bude dále značen počet kódových kombinací (znaků, symbolů) kódu.

Lineární kód je takový, jehož kódová slova tvoří lineární prostor (součet dvou kódových slov je rovněž kódové slovo).

19.1  Systematické kódy

Do kódových kombinací systematického kódu se zahrnuje nulový vektor (samé nuly). Sestaví se vytvářecí matice G, která má k nenulových lineárně nezávislých vektorů. Sestavuje se tak, že se nejdříve sestaví čtvercová diagonální matice o k řádcích a sloupcích. Poté se řádky doplní o n - k znaků (zprava), které slouží kontrole. Kontrolní znaky se dopisují tak, aby počet jedniček v každém řádku nebyl menší než zadaná Hamingova kódová vzdálenost ρ (tato kódová vzdálenost samozřejmě musí být dodržena mezi všemi vektory vytvářecí matice G). Zbývajících N − k − 1 vektorů (k vektorů je ve vytvářecí matici, jeden vektor je nulový) se získá jako lineární kombinace vektorů vytvářecí matice. Nelze-li kód sestavit pro zadané n, je nutné n zvětšit.

Nyní potřebujeme sestavit prověřovací (kontrolní) matici H, Vektor této matice má délku n a vyžaduje se od něj, aby jeho skalární součin s kterýmkoliv vektorem vytvářecí matice byl nulový. Hledáme tedy prověřovací matici H, pro kterou platí G·HT = 0 (0 představuje nulovou matici). Z toho lze již vypočítat kontrolní matici H.

19.2  Cyklické kódy

Výchozí údaje pro sestavení cyklického kódu jsou tytéž, jako údaje pro sestavení systematického kódu. Odlišnost tkví v tom, že systematický kód lze vytvořit pro libovolnou kombinaci (n, k), zatímco cyklické kódy lze sestavit je pro některé kombinace (n, k). Cyklické kódy nevyužívají kombinaci s nulovými prvky, proto počet kombinací je o jednu nižší než počet kombinací, které může využít systematický kód.

Pro zápis vektorů cyklického kódu se používá polynomiální formy. Vektor s prvky a0 a1 … an−1 se zapíše

v(x) = a0 + a1 x + a2 x2 + … + an−1 xn−1.
Násobíme-li v(x) proměnnou x, dostáváme rotace. Aby došlo k přenosu prvku zprava doleva, formálně se zavádí xn = 1. Po vynásobení v(x) proměnnou x se tak an−1 ocitne zcela vlevo. Násobením v(x) proměnnou x získáme
v(x)·x = v'(x) = an−1 + a0 x + a1 x2 + … + an−2 xn−1.
Je zřejmé, že při takovémto způsobu vytváření mohu vytvořit pouze n kombinací.

Sestavení cyklického kódu začíná určením vytvářecího (generujícího) polynomu g(x) stupně n − k. Tento polynom se obvykle vybírá z tabulek, kde jsou vytvářecí polynomy cyklických kódů uvedeny pro kombinace (n, k), pro které existují. Vytvářecí polynom musí beze zbytku dělit polynom 1 + xn. Operace s polynomy se provádějí podle pravidel aritmetiky modulo 2. Podle vytvářecího polynomu se vytvoří vytvářecí matice G, která má k řádků. První řádek matice G tvoří koeficienty u mocnin x vytvářecího polynomu, který se zprava doplní nulami tak, aby měl n prvků. Další řádky matice se pak doplňují tak, že postupně přesouváme prvky prvního řádku o 1, o 2, … místa doprava (znaky vysunuté z matice vpravo se umísťují v matici na levé straně). Kód má mít N kombinací, ve vytvářecí matici jich je jen k. Zbývající najdu jako lineární kombinace vektorů vytvářecí matice.

Kontrolní polynom h(x) získáme tak, že polynom 1 + xn dělíme generačním polynomem g(x). Vzhledem k tomu, že generační polynom je stupně n − k a dělený polynom je stupně n, je kontrolní polynom h(x) stupně n − (n − k) = k.