Ciklikus kód

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. január 28-án felülvizsgált verziótól ; az ellenőrzések 2 szerkesztést igényelnek .

A ciklikus kód egy lineáris blokkkód , amely a ciklikusság tulajdonságával rendelkezik, vagyis egy kódszó minden ciklikus permutációja egyben kódszó is. Az információk átalakítására szolgál, hogy megvédje azokat a hibáktól (lásd: Hibaészlelés és -javítás ).

Bevezetés

Legyen egy n hosszúságú szó egy véges mező elemeinek ábécéjén, és legyen ennek a szónak megfelelő polinom egy formális változóban . Látható, hogy ez a megfeleltetés lineáris terek izomorfizmusa . Mivel a "szavak" a mezőből származó betűkből állnak, összeadhatók és szorozhatók (elemenként), és az eredmény ugyanabban a mezőben lesz. A szópár lineáris kombinációjának megfelelő polinom és egyenlő e szavak polinomjainak lineáris kombinációjával . ${\overline {y}}=(y_{0},y_{1},\dots ,y_{n-1})\in L^{n}$ $L=GF(q)$ ${\displaystyle y(x)=y_{0}+y_{1}x+y_{2}x^{2}+\pontok +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},\dots ,y_{1,n-1})$ ${\overline {y_{2}}}=(y_{2,0},\dots ,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)$

Ez lehetővé teszi számunkra, hogy a véges mező feletti n hosszúságú szavak halmazát a mező felett legfeljebb n − 1 fokos polinomok lineáris terének tekintsük . $GF(q)$

Algebrai leírás

Ha egy kódszót kapunk a szótól egy bittel balra történő ciklikus eltolással , akkor a hozzá tartozó polinomot az előzőből x -szel megszorozva kapjuk meg : $\overrightarrow {c_{1}}$ $\overright arrow {c}$ $c_{1}(x)$

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

, felhasználva azt a tényt

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

Eltolás jobbra és balra, bitenként: $j$

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

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

Ha egy tetszőleges polinom a mező felett , és egy ciklikus kód kódszava, akkor szintén ennek a kódnak a kódszava. $m(x)$ $GF(q)$ $c(x)$ ${\megjelenítési stílus (n,k)}$ $m(x)c(x)\mod (x^{n}-1)$

Polinom generálása

Meghatározás

Egy ciklikus kód generáló polinomja olyan nem nulla polinom -ból , amelynek foka a legkisebb, együtthatója pedig a legmagasabb fokon . ${\megjelenítési stílus (n,k)}$ $C$ ${\displaystyle g(x)=\sum \limits _{i=0}^{r}g_{i}x^{i))$ $C$ $g_{r}=1$

1. tétel

Ha ciklikus kód, és a generáló polinomja, akkor a foka , és minden kódszó egyedileg ábrázolható $C$ ${\megjelenítési stílus (n,k)}$ $g(x)$ $g(x)$ $r=nk$

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

ahol a fok kisebb vagy egyenlő, mint . $m(x)$ $k-1$

2. tétel

$g(x)$ — a ciklikus kód generáló polinomja — a binomiális osztója . ${\megjelenítési stílus (n,k)}$ $x^{n}-1$

Következmények

Így bármely osztópolinom kiválasztható generáló polinomnak . A kiválasztott polinom mértéke határozza meg az ellenőrző szimbólumok számát, az információs szimbólumok számát . $x^{n}-1$ $r$ $k=nr$

Mátrix generálása

A polinomok lineárisan függetlenek, egyébként nem nulla esetén, ami lehetetlen. $g(x),xg(x),x^{2}g(x),\dots ,x^{k-1}g(x)$ $m(x)g(x)=0$ $m(x)$

Tehát a kódszavak a lineáris kódokhoz hasonlóan a következőképpen írhatók:

{\overline {m}}G=(m_{0},m_{1},\dots ,m_{k-1}){\begin{bmatrix}g(x)\\xg(x)\ \\pontok \\x^{k-1}g(x)\end{bmátrix}}=m(x)g(x),

ahol a generáló mátrix , az információs polinom. $G$ $m(x)$

A mátrix felírható szimbolikus formában: $G$

G={\begin{bmatrix}g_{0}&g_{1}&\pontok &g_{r-1}&g_{r}&0&\pontok &0\\0&g_{0}&\pontok &g_{r-2 }&g_{r-1}&g_{r}&\pontok &0\\\vpontok &\vpontok &\dpontok &\vpontok &\vpontok &\vpontok &\dpontok &\vpontok \\0&0&\pontok &0&g_{0}&g_ {1}&\pontok &g_{r}\end{bmátrix}}.

Ellenőrizze a mátrixot

Egy ciklikus kód minden kódszava esetén . Ezért az ellenőrző mátrix így írható fel $c(x)=0\mod g(x)$

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

Akkor

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

Kódolás

Rendszertelen

Nem szisztematikus kódolással a kódszót egy információs polinom szorzataként kapja meg egy generáló:

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

Polinomok szorzásával valósítható meg.

Szisztematikus

A szisztematikus kódolással a kódszó információs részblokk és ellenőrzés formájában kerül kialakításra:

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

Legyen tehát az információs szó a kódszó legmagasabb hatványa

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

Aztán a feltételből következik $c(x)=x^{r}m(x)+s(x)=0\mod g(x)$

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

Ez az egyenlet határozza meg a szisztematikus kódolási szabályt. Megvalósítható többciklusú lineáris szűrőkkel (MLF) .

Példák

Bináris (7,4,3) kód

Osztóként egy harmadfokú generáló polinomot választunk , ekkor a kapott kódnak lesz egy hosszúsága , az ellenőrző szimbólumok száma (a generáló polinom foka) , az információs szimbólumok száma , a minimális távolság . $x^{7}-1$ $g(x)=x^{3}+x+1$ $n=7$ $r=3$ $k = 4$ $d=3$

Kódmátrix generálása :

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{bmátrix)

ahol az első sor egy polinom , amelynek együtthatói növekvő sorrendben vannak. $g(x)$

A fennmaradó sorok az első sor ciklikus eltolódásai.

Ellenőrizze a mátrixot :

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{bmátrix)

ahol az i -edik oszlop az 1.-től kezdve a polinommal való osztás maradéka , felfelé haladva növekvő mértékben írva. $x^{i-1}$ $g(x)$

Így például a 4. oszlop , vagy vektoros jelölésben . $h_{4}(x)=x^{3}\mod g(x)=x+1$ $[110]$

Ezt könnyű ellenőrizni . $GH^{T}=0$

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

Generáló polinomként két osztó szorzatát választhatja ki : $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.

Ekkor minden kódszót az információs polinom fokszámú szorzatával kaphatunk meg a következő módon: $m(x)$ $k-1$

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

Például egy információs szó egy polinomnak felel meg , majd egy kódszónak vagy vektoros formában . ${\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]$

Lásd még

Linkek

Adatintegritás-ellenőrzési mechanizmusok.