Syklinen koodi

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 28. tammikuuta 2021 tarkistetusta versiosta . tarkastukset vaativat 2 muokkausta .

Syklinen koodi on lineaarinen lohkokoodi , jolla on syklisyyden ominaisuus, eli jokainen koodisanan syklinen permutaatio on myös koodisana. Käytetään tietojen muuntamiseen suojaamaan niitä virheiltä (katso Virheiden havaitseminen ja korjaaminen ).

Johdanto

Olkoon sana, jonka pituus on n äärellisen kentän elementtien aakkoston päällä, ja olkoon tätä sanaa vastaava polynomi muodollisessa muuttujassa . Voidaan nähdä, että tämä vastaavuus on lineaaristen avaruuksien isomorfismi . Koska "sanat" koostuvat kentän kirjaimista, ne voidaan lisätä ja kertoa (elementti kerrallaan), jolloin tulos on samassa kentässä. Sanaparin lineaarista yhdistelmää vastaava polynomi on yhtä suuri kuin näiden sanojen polynomien lineaariyhdistelmä . ${\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}+\dots +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)$

Tämä mahdollistaa sen, että n pituisten sanojen joukkoa äärellisessä kentässä voidaan pitää polynomien lineaarisena avaruutena , joiden aste on enintään n − 1 kentän yli . $GF(q)$

Algebrallinen kuvaus

Jos on koodisana, joka saadaan syklisellä siirrolla yhden bitin verran sanasta vasemmalle , niin sitä vastaava polynomi saadaan edellisestä kertomalla x :llä: $\overrightarrow {c_{1}}$ $\overright arrow {c}$ $c_{1}(x)$

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

, käyttämällä sitä tosiasiaa

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

Siirrä oikealle ja vasemmalle, vastaavasti, biteillä: $j$

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

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

If on mielivaltainen polynomi kentän päällä ja on syklisen koodin koodisana, niin se on myös tämän koodin koodisana. $m(x)$ $GF(q)$ $c(x)$ ${\näyttötyyli (n,k)}$ $m(x)c(x)\mod (x^{n}-1)$

Polynomin luominen

Määritelmä

Syklisen koodin generoiva polynomi on sellainen nollasta poikkeava polynomi kohdasta , jonka aste on pienin ja kerroin korkeimmalla asteella . ${\näyttötyyli (n,k)}$ $C$ ${\displaystyle g(x)=\sum \limits _{i=0}^{r}g_{i}x^{i))$ $C$ $g_{r}=1$

Lause 1

Jos on syklinen koodi ja on sen generoiva polynomi, niin aste on , ja jokainen koodisana voidaan esittää yksilöllisesti $C$ ${\näyttötyyli (n,k)}$ $g(x)$ $g(x)$ $r=nk$

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

jossa aste on pienempi tai yhtä suuri kuin . $m(x)$ $k-1$

Lause 2

$g(x)$ — syklisen koodin generoiva polynomi — on binomiaalin jakaja . ${\näyttötyyli (n,k)}$ $x^{n}-1$

Seuraukset

Siten mikä tahansa jakajapolynomi voidaan valita generoivaksi polynomiksi . Valitun polynomin aste määrittää tarkistussymbolien määrän, tietosymbolien määrän . $x^{n}-1$ $r$ $k = nro$

Luodaan matriisia

Polynomit ovat lineaarisesti riippumattomia, muuten ei-nollalle , mikä on mahdotonta. ${\näyttötyyli g(x),xg(x),x^{2}g(x),\pisteet ,x^{k-1}g(x)}$ $m(x)g(x)=0$ $m(x)$

Joten koodisanat voidaan kirjoittaa, kuten lineaarisille koodeille, seuraavasti:

{\overline {m}}G=(m_{0},m_{1},\dots ,m_{k-1}){\begin{bmatrix}g(x)\\xg(x)\ \\pisteet \\x^{k-1}g(x)\end{bmatriisi}}=m(x)g(x),

missä on generoiva matriisi , on informaatiopolynomi . $G$ $m(x)$

Matriisi voidaan kirjoittaa symboliseen muotoon: $G$

G={\begin{bmatrix}g_{0}&g_{1}&\pisteet &g_{r-1}&g_{r}&0&\pisteet &0\\0&g_{0}&\pisteet &g_{r-2 }&g_{r-1}&g_{r}&\pisteet &0\\\vpisteet &\vpisteet &\dpisteet &\vpisteet &\vpisteet &\vpisteet &\dpisteet &\vpisteet \\0&0&\pisteet &0&g_{0}&g_ {1}&\pisteet &g_{r}\end{bmatrix}}.

Tarkista matriisi

Kullekin syklisen koodin koodisanalle . Siksi tarkistusmatriisi voidaan kirjoittaa muodossa $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).

Sitten

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

Koodaus

Epäjärjestelmällinen

Ei-systeemisessä koodauksessa koodisana saadaan informaatiopolynomin tulona generoimalla:

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

Se voidaan toteuttaa kertomalla polynomit.

Systemaattinen

Systemaattisella koodauksella koodisana muodostetaan tiedon alilohkon ja tarkistuksen muodossa:

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

Olkoon tietosana sitten koodisanan korkeimmat voimat

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

Se seuraa sitten ehdosta $c(x)=x^{r}m(x)+s(x)=0\mod g(x)$

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

Tämä yhtälö määrittelee systemaattisen koodaussäännön. Se voidaan toteuttaa käyttämällä monisyklisiä lineaarisia suodattimia (MLF) .

Esimerkkejä

Binääri (7,4,3) koodi

Jakajaksi valitaan kolmannen asteen generoiva polynomi , jolloin tuloksena olevalla koodilla on pituus , tarkistussymbolien määrä (generoivan polynomin aste) , informaatiosymbolien määrä , minimietäisyys . $x^{7}-1$ $g(x)=x^{3}+x+1$ $n=7$ $r = 3$ $k = 4$ $d = 3$

Koodimatriisin luominen :

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{bmatriisi)

jossa ensimmäinen rivi on polynomi , jonka kertoimet ovat nousevassa järjestyksessä. $g(x)$

Loput rivit ovat ensimmäisen rivin syklisiä siirtymiä.

Tarkista matriisi :

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)),

jossa i . sarake, alkaen 1.:stä, on polynomin jaon loppuosa kirjoitettuna nousevin astein, alkaen ylhäältä. $x^{i-1}$ $g(x)$

Joten esimerkiksi 4. sarake on , tai vektorimuodossa . $h_{4}(x)=x^{3}\mod g(x)=x+1$ $[110]$

Se on helppo varmistaa . $GH^{T}=0$

Binääri (15,7,5) BCH-koodi

Generoivaksi polynomiksi voit valita kahden jakajan tulon : $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.

Sitten jokainen koodisana voidaan saada käyttämällä informaatiopolynomin tuloa asteella seuraavasti: $m(x)$ $k-1$

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

Esimerkiksi informaatiosana vastaa polynomia , sitten koodisanaa tai vektorimuodossa . ${\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]$

Katso myös

Linkit

Tietojen eheyden valvontamekanismit.