Cyklický kód

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

Lineární kód C se na­zý­vá cyklický kód, jestliže pro každé kódové slovo (a₀, a₁, a₂, ...,a_n-1) je také slovo (a_n-1, a₀, a₁,..., a_n-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 $(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 xⁿ-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) 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), x²g(x),...,x^k-1g(x) tvoří bázi kódu C.
• Polynom g(x) dělí polynom xⁿ-1 beze zbytku.

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

Kontrolní polynom

Polynom h(x) = (xⁿ-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 (xⁿ-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)=g₀+g₁x+...+g_n-kx^n-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.

Autoritní data	PSH: 6566