Cesko.wiki Cyklický kód
Author
Albert FloresCyklický kód je v teorii kódování lineární kód, který je uzavřený vzhledem k cyklickému posunu.
Formální definice
Lineární kód C se nazývá cyklický kód, jestliže pro každé kódové slovo (a0, a1, a2, . ,an-1) je také slovo (an-1, a0, a1,. +more, an-2) kódový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 (a_{0},a_{1},\dots,a_{n-1}) \to a_{0}+a_{1}x+\cdots+a_{n-1}x^{n-1}.
Cyklický posun odpovídá násobení polynomem x modulo xn-1: x \cdot(a_{0}+a_{1}x+\cdots+a_{n-1}x^{n-1})\bmod(x^n-1)= a_{n-1}+a_{0}x+a_{1}x^2+\cdots+a_{n-2}x^{n-1}.
Generující polynom
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) polynom g(x) stupně n-k. +more 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
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
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 \mathbf{G}=\begin{pmatrix} g_0 & g_1 & \dots & g_{n-k} & 0 & 0 & \dots & 0 \\ 0 & g_0 & \dots & g_{n-k-1} & g_{n-k} & 0 & \dots & 0 \\ \vdots& & \ddots& & \ddots & & \ddots & \vdots \\ 0 & 0 & \dots & g_0 & g_1 & & \dots & g_{n-k} \end{pmatrix}.
Kvazicyklické kódy
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.