Cyklický kód

Z Wikipedie, otevřené encyklopedie
(přesměrováno z Generující polynom)

Cyklický kód je v teorii kódování lineární kód, který je uzavřený vzhledem k cyklickému posunu.

Formální definice[editovat | editovat zdroj]

Lineární kód C se na­zý­vá cyklický kód, jestliže pro každé kódové slovo (a0, a1, a2, ...,an-1) je také slovo (an-1, a0, a1,..., an-2) kó­do­vým slovem.

Kódová slova cyklického kódu délky n se zapisují ve tvaru formálních polynomů stupně men­šího než n s využitím izomorfismu .

Cyklický posun odpovídá násobení polynomem x modulo xn-1: .


Generující polynom[editovat | editovat zdroj]

Každý netriviální (tj. obsahující více než jedno slovo) cyklický (n,k)-kód C obsahuje (právě jeden, až na násobek) po­lynom g(x) stupně n-k. Je to polynom nejmenšího stupně mezi všemi nenulovými polynomy kó­du C. Polynom g(x) se nazývá generující polynom kódu C a má následující vlastnosti:

  • Kód C se skládá právě ze všech násobků polynomu g(x).
  • Polynomy g(x), xg(x), x2g(x),...,xk-1g(x) tvoří bázi kódu C.
  • Polynom g(x) dělí polynom xn-1 beze zbytku.

Cyklický kód je tedy jednoznačně určen svým generujícím polynomem.

Kontrolní polynom[editovat | editovat zdroj]

Polynom h(x) = (xn-1):g(x) nazveme kontrolním polynomem kódu C. Platí, že daný polynom v(x) je v kódu C, právě když platí v(x)h(x)≡0 mod (xn-1).

Kód, generovaný polynomem h(x), je ekvivalentní s kódem, duálním ke kódu C.

Generující matice[editovat | editovat zdroj]

Jedna z generujících matic cyklického kódu C s generujícím polynomem g(x)=g0+g1x+...+gn-kxn-k (o k řádcích a n sloupcích) má tvar

Kvazicyklické kódy[editovat | editovat zdroj]

Zobecněním cyklických kódů jsou kódy kvazicyklické. Kód C je kvazicyklický, pokud pro nějaké celé číslo s platí, že cyklickým posunutím kódového slova o s pozic vznikne opět kódové slovo.