Cyklický kód

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 28. ledna 2021; kontroly vyžadují 2 úpravy .

Cyklický kód je lineární blokový kód , který má vlastnost cykličnosti, to znamená, že každá cyklická permutace kódového slova je také kódovým slovem. Používá se k transformaci informací, aby byly chráněny před chybami (viz Detekce a oprava chyb ).

Úvod

Nechť je slovo délky n nad abecedou prvků konečného tělesa a je polynom odpovídající tomuto slovu ve formální proměnné . Je vidět, že tato korespondence je izomorfismus lineárních prostorů. Protože se „slova“ skládají z písmen z pole, lze je sčítat a násobit (prvek po prvku) a výsledek bude ve stejném poli. Polynom odpovídající lineární kombinaci dvojice slov a je roven lineární kombinaci polynomů těchto slov . ${\overline {y}}=(y_{0},y_{1},\tečky ,y_{n-1})\in L^{n}$ $L=GF(q)$ ${\displaystyle y(x)=y_{0}+y_{1}x+y_{2}x^{2}+\tečky +y_{n-1}x^{n-1))$ $X$ ${\overline {y}}=m_{1}{\overline {y_{1}}}+m_{2}{\overline {y_{2}}}$ ${\overline {y_{1}}}=(y_{1,0},\tečky ,y_{1,n-1})$ ${\overline {y_{2}}}=(y_{2,0},\tečky ,y_{2,n-1})$ ${y}(x)=\sum _{k=0}^{n-1}(m_{1}y_{1k}+m_{2}y_{2k})x^{k}=m_ {1}{\overline {y_{1}}}(x)+m_{2}{\overline {y_{2}}}(x)$

To nám umožňuje považovat množinu slov délky n nad konečným tělesem za lineární prostor polynomů se stupněm nejvýše n − 1 nad polem . $GF(q)$

Algebraický popis

Jestliže je kódové slovo získáno cyklickým posunem o jeden bit doleva od slova , pak jemu odpovídající polynom získáme z předchozího vynásobením x : $\overrightarrow {c_{1}}$ $\overright arrow {c}$ $c_{1}(x)$

c_{1}(x)=xc(x)\mod (x^{n}-1)

s využitím skutečnosti, že

x^{n}\equiv 1\mod (x^{n}-1).

Posun doprava a doleva po bitech: $j$

c_{j}(x)=x^{j}c(x)\mod (x^{n}-1),

c_{-j}(x)x^{j}=c(x)\mod (x^{n}-1).

Jestliže je libovolný polynom nad polem a je kódovým slovem cyklického kódu, pak je také kódovým slovem tohoto kódu. $m(x)$ $GF(q)$ $c(x)$ $(n,k)$ $m(x)c(x)\mod (x^{n}-1)$

Generování polynomu

Definice

Generující polynom cyklického kódu je takový nenulový polynom od , jehož stupeň je nejmenší a koeficient je nejvyšší . $(n,k)$ $C$ $g(x)=\sum \limits _{i=0}^{r}g_{i}x^{i}$ $C$ $g_{r}=1$

Věta 1

Jestliže je cyklický kód a je jeho generujícím polynomem, pak stupeň je a každé kódové slovo může být jednoznačně reprezentováno jako $C$ $(n,k)$ $g(x)$ $g(x)$ $r=nk$

c(x)=m(x)g(x),

kde stupeň je menší nebo roven . $m(x)$ $k-1$

Věta 2

$g(x)$ — generující polynom cyklického kódu — je dělitel binomu . $(n,k)$ $x^{n}-1$

Důsledky

Jako generující polynom lze tedy zvolit libovolný polynom dělitele . Stupeň zvoleného polynomu určí počet kontrolních symbolů , počet informačních symbolů . $x^{n}-1$ $r$ $k=č$

Generování matice

Polynomy jsou lineárně nezávislé, jinak pro nenulové , což je nemožné. $g(x),xg(x),x^{2}g(x),\tečky ,x^{k-1}g(x)$ $m(x)g(x)=0$ $m(x)$

Kódová slova lze tedy psát, stejně jako lineární kódy, následovně:

{\overline {m}}G=(m_{0},m_{1},\tečky ,m_{k-1}){\begin{bmatrix}g(x)\\xg(x)\ \\tečky \\x^{k-1}g(x)\end{bmatrix}}=m(x)g(x),

kde je generující matice , je informační polynom. $G$ $m(x)$

Matici lze zapsat v symbolické formě: $G$

G={\begin{bmatrix}g_{0}&g_{1}&\tečky &g_{r-1}&g_{r}&0&\tečky &0\\0&g_{0}&\tečky &g_{r-2 }&g_{r-1}&g_{r}&\tečky &0\\\vtečky &\vtečky &\dtečky &\vtečky &\vtečky &\vtečky &\dtečky &\vtečky \\0&0&\tečky &0&g_{0}&g_ {1}&\tečky &g_{r}\end{bmatrix}}.

Kontrolní matice

Pro každé kódové slovo cyklického kódu, . Kontrolní matici lze tedy zapsat jako $c(x)=0\mod g(x)$

H={\begin{bmatrix}1&x&x^{2}&\tečky &x^{n-2}&x^{n-1}\\\end{bmatrix}}\mod g(x).

Pak

{\overline {c}}H^{T}=\sum \limits _{i=0}^{n-1}c_{i}x^{i}=0\mod g(x).

Kódování

Nesystematické

Při nesystematickém kódování se kódové slovo získá jako součin informačního polynomu generujícím:

c(x)=m(x)g(x).

Lze to realizovat násobením polynomů.

Systematický

Při systematickém kódování se kódové slovo tvoří ve formě informačního podbloku a kontroly:

c(x)=[s(x)\;m(x)].

Nechť tedy informační slovo tvoří nejvyšší mocniny kódového slova

c(x)=x^{r}m(x)+s(x),\quad r=nk.

Pak to vyplývá z podmínky $c(x)=x^{r}m(x)+s(x)=0\mod g(x)$

s(x)=-x^{r}m(x)\mod g(x).

Tato rovnice definuje pravidlo systematického kódování. Lze jej implementovat pomocí vícecyklových lineárních filtrů (MLF) .

Příklady

Binární (7,4,3) kód

Jako dělitel zvolíme generující polynom třetího stupně , výsledný kód pak bude mít délku , počet kontrolních znaků (stupeň generujícího polynomu) , počet informačních znaků , minimální vzdálenost . $x^{7}-1$ $g(x)=x^{3}+x+1$ $n=7$ $r=3$ $k = 4$ $d=3$

Generování matice kódu:

G={\begin{bmatrix}1&1&0&1&0&0&0\\0&1&1&0&1&0&0\\0&0&1&1&0&1&0\\0&0&0&1&1&0&1\end{bmatrix)),

kde první řádek je polynom s koeficienty ve vzestupném pořadí. $g(x)$

Zbývající řádky jsou cyklické posuny prvního řádku.

Kontrolní matice :

H={\begin{bmatrix}1&0&0&1&0&1&1\\0&1&0&1&1&1&0\\0&0&1&0&1&1&1\end{bmatrix)),

kde i -tý sloupec, počínaje 1., je zbytek dělení polynomem , psaný ve vzestupných stupních, počínaje shora. $x^{i-1}$ $g(x)$

Takže například 4. sloupec je , nebo ve vektorové notaci . $h_{4}(x)=x^{3}\mod g(x)=x+1$ $[110]$

Je snadné si to ověřit . $GH^{T}=0$

Binární (15,7,5) BCH kód

Jako generující polynom si můžete vybrat součin dvou dělitelů : $g(x)$ $x^{15}-1$

g(x)=g_{1}(x)g_{2}(x)=(x^{4}+x+1)(x^{4}+x^{3}+x^{ 2}+x+1)=x^{8}+x^{7}+x^{6}+x^{4}+1.

Potom lze každé kódové slovo získat pomocí součinu informačního polynomu se stupněm následujícím způsobem: $m(x)$ $k-1$

c(x)=m(x)g(x).

Například informační slovo odpovídá polynomu , poté kódovému slovu nebo ve vektorové podobě . ${\overline {m}}=[1000111]$ $m(x)=x^{6}+x^{5}+x^{4}+1$ $c(x)=(x^{6}+x^{5}+x^{4}+1)(x^{8}+x^{7}+x^{6}+x^ {4}+1)=x^{14}+x^{12}+x^{9}+x^{7}+x^{5}+1$ ${\overline {c}}=[100001010100101]$

Viz také

Odkazy

Mechanismy kontroly integrity dat.