Bowes-Chowdhury-Hockwingham koodi

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

Bowes-Chowdhury-Hokvingham-koodit (BCH-koodit) - koodausteoriassa tämä on laaja luokka syklisiä koodeja , joita käytetään suojaamaan tietoja virheiltä (katso Virheiden havaitseminen ja korjaaminen ). Se eroaa mahdollisuudesta rakentaa koodi, jolla on ennalta määrätyt korjaavat ominaisuudet, nimittäin minimikoodietäisyys. BCH-koodien erikoistapaus on Reed-Solomon-koodi .

Muodollinen kuvaus

BCH - koodi on syklinen koodi , joka voidaan antaa generaattoripolynomilla . Sen löytämiseksi BCH-koodin tapauksessa on tarpeen määrittää etukäteen koodin pituus (se ei voi olla mielivaltainen) ja vaadittava vähimmäisetäisyys . Voit löytää generoivan polynomin seuraavalla tavalla. $n$ $d\leqslant n$

Olkoon kentän primitiivinen elementti ( eli ), olkoon , järjestyskentän elementti , . Tällöin normalisoitu polynomi , jonka vähimmäisaste on kentässä, jonka juuret ovat elementin peräkkäisiä potenssit jollekin kokonaisluvulle (mukaan lukien 0 ja 1), on generoiva BCH-koodin polynomi kentällä , jonka pituus ja minimietäisyys on . $\alpha$ $GF(q^{m})$ $\alpha ^{q^{m}-1}=1,\ \alpha ^{i}\neq 1,\ i<q^{m}-1$ $\beta =\alpha ^{s}$ $GF(q^{m})$ $n$ $s=(q^{m}-1)/n$ $g(x)$ $GF(q)$ $d-1$ $\beta ^{l_{0}},\beta ^{l_{0}+1},\ldots ,\beta ^{l_{0}+d-2}$ $\beeta$ $l_{0}$ $GF(q)$ $n$ $d_{0}\geqslant d$

Selvitetään, miksi tuloksena olevalla koodilla on juuri tällaiset ominaisuudet (koodin pituus , minimietäisyys ). Todellakin, kuten Sagalovich [1] osoittaa, BCH-koodin pituus on yhtä suuri kuin elementtijärjestys , jos , ja yhtä suuri kuin elementtijärjestys, jos . Koska emme ole kiinnostuneita tapauksesta (sellainen koodi ei voi korjata virheitä, vain havaita ne), koodin pituus on yhtä suuri kuin elementin järjestys, eli yhtä suuri kuin . Minimietäisyys voi olla suurempi kuin silloin , kun elementtien minimifunktioiden [2] juuret ovat sarjaa laajentavia elementtejä eli alkioita . $n$ $d_{0}$ $\beeta$ $d>2$ $\beta ^{l_{0}}$ $d=2$ $d=2$ $\beeta$ $n$ $d_{0}$ $d$ $\beta ^{l_{0}},\beta ^{l_{0}+1},\ldots ,\beta ^{l_{0}+d-2}$ ${\displaystyle \beta ^{l_{0}+d-1},\beta ^{l_{0}+d},\ldots ,\beta ^{l_{0}+d_{0}-2))$

Tarkistussymbolien määrä on yhtä suuri kuin aste , informaatiosymbolien lukumäärä , arvoa kutsutaan BCH-koodin rakentavaksi etäisyydeksi . Jos , niin koodia kutsutaan primitiiviksi , muuten - ei- primitiiviksi . $r$ $g(x)$ $k = nro$ $d$ $n=q^{m}-1$

Kuten sykliselle koodille, koodipolynomi voidaan saada korkeintaan asteisen tietopolynomista kertomalla ja : $c(x)$ $m(x)$ $k-1$ $m(x)$ $g(x)$

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

Rakennus

Generoivan polynomin löytämiseksi on suoritettava useita vaiheita [3] :

valitse , eli kenttä, jonka päälle koodi rakennetaan; $q$ $GF(q)$
valitse koodin pituus ehdosta , jossa ovat positiivisia kokonaislukuja; $n$ $n=(q^{m}-1)/s$ $m,s$
aseta rakentavan etäisyyden arvo; $d$
rakentaa kenttäelementin syklotomisia luokkia kentän päälle , missä on primitiivinen elementti ; $\beta =\alpha ^{s}$ $GF(q^{m})$ $GF(q)$ $\alpha$ $GF(q^{m})$
koska jokainen tällainen syklotominen luokka vastaa redusoitumatonta polynomia yli , jonka juuret ovat tämän ja vain tämän luokan elementtejä asteella, joka on yhtä suuri kuin luokan alkioiden lukumäärä, niin valitse siten, että syklotomisten luokkien kokonaispituus on minimaalinen; tämä tehdään koodin annettujen ominaisuuksien tarkistusmerkkien määrän minimoimiseksi ; $GF(q)$ $\beta ^{l_{0}},\beta ^{l_{0}+1},\ldots ,\beta ^{l_{0}+d-2}$ $n$ $d$ $k$
laske generoiva polynomi , jossa on -: ttä syklotomista luokkaa vastaava polynomi ; tai laskea elementtien vähimmäisfunktioiden LCM :nä . $g(x)=f_{1}(x)f_{2}(x)\ldots f_{h}(x)$ $korjata)$ $i$ $g(x)$ $\beta ^{l_{0}},\beta ^{l_{0}+1},\ldots ,\beta ^{l_{0}+d-2}$

Koodiesimerkkejä

Primitiivinen binäärikoodi (15, 7, 5)

Olkoon , vaadittu koodin pituus ja minimietäisyys . Otetaan — kentän primitiivinen elementti ja — elementin neljä peräkkäistä potenssia . Ne kuuluvat kahteen syklotomiseen luokkaan sen kentän yläpuolella , jota redusoitumattomat polynomit ja vastaavat . Sitten polynomi $q = 2$ $n=2^{4}-1=15$ $d_{0}\geqslant d=5$ $\alpha$ $GF(16)$ ${\displaystyle \alpha ,\alpha ^{2},\alpha ^{3},\alpha ^{4))$ $\alpha$ $GF(2)$ $f_{1}(x)=x^{4}+x+1$ $f_{2}(x)=x^{4}+x^{3}+x^{2}+x+1$

g(x)=f_{1}(x)f_{2}(x)=x^{8}+x^{7}+x^{6}+x^{4}+1

sisältää elementtejä juurina ja se on BCH-koodin generoiva polynomi parametrien kanssa . ${\displaystyle \alpha ,\alpha ^{2},\alpha ^{3},\alpha ^{4))$ $(15,7,5)$

Heksadesimaali (15, 11, 5) koodi (Reed-Solomon koodi)

Antaa , ja olla primitiivinen osa . Sitten $n=q-1=15$ $\alpha$ $GF(16)$

g(x)=(x-\alpha )(x-\alpha ^{2})(x-\alpha ^{3})(x-\alpha ^{4})=x^{4} +\alpha ^{13}x^{3}+\alpha ^{6}x^{2}+\alpha ^{3}x+\alpha ^{10}.

Jokainen kentän elementti voidaan kuvata 4- bittiseksi , joten yksi koodisana vastaa 60 = 15 × 4 bittiä, joten 44 bitin joukko kartoitetaan 60 bitin joukkoon. Voimme sanoa, että tällainen koodi toimii tiedon nappuloiden kanssa. $GF(16)$

Koodaus

BCH-koodeilla koodattaessa käytetään samoja menetelmiä kuin koodauksessa syklisillä koodeilla.

Dekoodausmenetelmät

BCH-koodit ovat syklisiä koodeja, joten kaikki syklisten koodien dekoodaukseen käytetyt menetelmät koskevat niitä. On kuitenkin olemassa paljon parempia algoritmeja , jotka on kehitetty erityisesti BCH-koodeille [4] .

Pääideana BCH-koodien dekoodauksessa on käyttää viimeisen kentän elementtejä koodisanan paikkojen numeroimiseen (tai vastaavasti siihen liittyvän polynomin kertoimien järjestyksessä). Alla on tällainen luettelo polynomia vastaavalle vektorille . $r=(r_{0},r_{1},\ldots ,r_{n-1})$ $r(x)$

arvot	$r_{0}$	$r_{1}$	$\ldots$	$r_{{n-1}}$
sijainnin paikantimet	$yksi$	$\alpha$	$\ldots$	$\alpha ^{{n-1}}$

Olkoon vastaanotettu sana yhdistetty polynomiin , jossa virhepolynomi määritellään seuraavasti: , jossa on vastaanotetun sanan virheiden määrä. Joukkoja ja kutsutaan vastaavasti virhearvoiksi ja virheen paikantimiksi , missä , ja . $r(x)=\nu(x)+e(x)$ $e(x)=e_{J_{1}}x^{J_{1}}+e_{J_{2}}x^{J_{2}}+\ldots +e_{J_{\nu } }x^{J_{\nu }}$ $\nu \leqslant t_d$ $\{e_{J_{1}},e_{J_{2}},\ldots ,e_{J_{\nu }}\}$ ${\displaystyle \{\alpha ^{J_{1)),\alpha ^{J_{2)),\ldots ,\alpha ^{J_{\nu ))\))$ $e_{J}\in GF(q)$ $\alpha \in GF(q^{m})$

Oireet määritellään vastaanotetun polynomin arvoina generoivan koodipolynomin nollapisteissä: $r(x)$

S_{1}=r(\alpha ^{b})=e_{J_{1}}\alpha ^{bJ_{1}}+e_{J_{2}}\alpha ^{bJ_{2} }+\ldots +e_{J_{\nu }}\alpha ^{bJ_{\nu )),

S_{2}=r(\alpha ^{b+1})=e_{J_{1}}\alpha ^{(b+1)J_{1}}+e_{J_{2}}\ alfa ^{(b+1)J_{2}}+\ldots +e_{J_{\nu }}\alpha ^{(b+1)J_{\nu )),

\vdots

S_{2t_{d}}=r(\alpha ^{b+2t_{d}-1})=e_{J_{1}}\alpha ^{(b+2t_{d}-1)J_ {1}}+e_{J_{2}}\alpha ^{(b+2t_{d}-1)J_{2}}+\ldots +e_{J_{\nu }}\alpha ^{(b+ 2t_ {d}-1)J_{\nu )),

missä . $2t_{d}=d-1$

Virheenpaikantimien joukon löytämiseksi otamme käyttöön virheenpaikannuspolynomin

\sigma (x)=\prod _{l=1}^{\nu }(1+\alpha ^{J_{l}}x)=1+\sigma _{1}x+\sigma _{ 2}x^{2}+\ldots +\sigma _{\nu }x^{\nu },

joiden juuret ovat yhtä suuret kuin virheenpaikantimien käänteiset. Tällöin virheenpaikannuspolynomin ja oireyhtymien kertoimien välillä pätee seuraava suhde [5] :

\sigma _{1}S_{t}+\sigma _{2}S_{t-1}+\ldots +\sigma _{t}S_{1}=-S_{t+1},

\sigma _{1}S_{t+1}+\sigma _{2}S_{t}+\ldots +\sigma _{t}S_{2}=-S_{t+2},

\vdots

\sigma _{1}S_{2t-1}+\sigma _{2}S_{2t-2}+\ldots +\sigma _{t}S_{t}=-S_{2t}.

Seuraavat menetelmät tunnetaan tämän yhtälöjärjestelmän ratkaisemiseksi suhteessa virheenpaikannuspolynomin kertoimiin ( avainyhtälöjärjestelmä ). $\sigma _{i},\ i=1,2,\ldots ,\nu$

Berlekamp-Massey-algoritmi (BMA) . Mitä tulee operaatioiden määrään äärellisessä kentässä, tämä algoritmi on erittäin tehokas. BMA:ta käytetään yleisesti BCH-koodien ja Reed-Solomon-koodien ohjelmallisesti toteuttamiseen tai mallintamiseen .
Euklidinen algoritmi (EA) . Tämän algoritmin rakenteen suuren säännöllisyyden vuoksi sitä käytetään laajalti BCH-dekooderien ja Reed-Solomon-koodien laitteistototeutukseen .
Suora ratkaisu (Peterson-Gorenstein-Zierler-algoritmi, PGC). Historiallisesti tämä on ensimmäinen dekoodausmenetelmä, jonka Peterson löysi binääritapaukselle ( ), sitten Gorenstein ja Zierler yleiselle tapaukselle. Tämä algoritmi löytää virheenpaikantimen polynomikertoimet vastaavan lineaariyhtälöjärjestelmän suoralla ratkaisulla. Itse asiassa, koska tämän algoritmin monimutkaisuus kasvaa minimietäisyyden kuution myötä , suoraa algoritmia voidaan käyttää vain pienille arvoille , mutta juuri tämä algoritmi selventää parhaiten dekoodausprosessin algebrallista ideaa. $q = 2$ $d$ $d$

Berlekamp-Massey-algoritmi

Tämä algoritmi on parasta nähdä iteratiivisena prosessina, jossa muodostetaan minimipalauterekisteri (siirtorekisteri), joka tuottaa tunnetun oireyhtymien sarjan . Sen varsinainen tavoite on rakentaa pienimmän asteisen polynomi, joka täyttää yhtälön $S_{1},S_{2},\ldots ,S_{2t_{d))$ $\sigma ^{{i+1}}(x)$

\sum _{j=0}^{l_{i}+1}S_{kj}\sigma _{j}^{i+1}=0,\quad l_{i}<k<i+ yksi .

Tämän yhtälön ratkaisu vastaa ehtoa

\sigma ^{i+1}(x)=1+\sigma _{1}^{i+1}x+\ldots +\sigma _{l_{i+1}}^{i+1} x^{l_{i+1}}.

Iteratiivinen prosessi tällaisen polynomin muodostamiseksi on Berlekamp-Massey-algoritmi .

Euklidinen algoritmi

Tämä menetelmä perustuu tunnettuun Euklidesin algoritmiin kahden luvun suurimman yhteisen jakajan (gcd) löytämiseksi, vain tässä tapauksessa ei etsitä gcd:tä kahdesta luvusta, vaan kahdesta polynomista. Merkitään virhearvojen polynomi muodossa , jossa syndrominen polynomi on yhtä suuri kuin . Yhtälöjärjestelmästä seuraa, että . Ongelma tiivistyy pohjimmiltaan sen määrittämiseen, mikä täyttää viimeisen yhtälön, ja samalla aste ei ole korkeampi . Itse asiassa tällainen ratkaisu antaa laajennetun Euclid-algoritmin, jota sovelletaan polynomeihin ja , missä . Jos th vaiheessa laajennettu euklidinen algoritmi tuottaa ratkaisun siten, että , niin , ja . Tässä tapauksessa löydetty polynomi ei enää osallistu dekoodaukseen (se haetaan vain apu). Tällä tavalla virheenpaikannuspolynomi löydetään . $\Lambda =\sigma (x)S(x)$ $S(x)=1+S_{1}x+\ldots +S_{2t_{d}}x^{2t_{d}}$ ${\displaystyle \Lambda (x)=\sigma (x)S(x)\mod x^{2t_{d}+1))$ $\lambda(x)$ ${\näyttötyyli t_{d))$ ${\displaystyle r_{0}(x)=x^{d))$ $r_{1}(x)=S(x)$ $d=2t_{d}+1$ $j$ $r_{j}=a_{j}(x)x^{2t_{d}+1}+b_{j}(x)S(x)$ ${\displaystyle \deg[r_{j}(x)]\leqslant t_{d))$ $\Lambda (x)=r_{j}(x)$ $\sigma _{i}(x)=b_{j}(x)$ $a_{j}(x)$ $\sigma (x)$

Suora ratkaisu (Petersson-Gorenstein-Zierler-algoritmi, PGC)

Olkoon BCH-koodi pituuskentän yli ja konstruktiivisella etäisyydellä generoiva polynomi , jonka juurielementtien joukossa on kokonaisluku (esim. 0 tai 1). Sitten jokaisella koodisanalla on ominaisuus, joka . Vastaanotettu sana voidaan kirjoittaa muodossa , missä on virhepolynomi. Olkoon virheitä paikoissa ( on korjattavien virheiden enimmäismäärä), joten , ja ovat virheiden suuruudet. $GF(q)$ $n$ $d$ $g(x)$ $\beta ^{l_{0}},\beta ^{l_{0}+1},\ldots ,\beta ^{l_{0}+d-2},\ \beta \in GF(q ^{m}),\ \beta ^{n}=1,\ l_{0}$ $c(\beta ^{l_{0}-1+j})=0,\ j=1,2,\ldots ,d-1$ $r(x)$ $r(x)=c(x)+e(x)$ $e(x)$ $u\leqslant t=(d-1)/2$ $i_{1},i_{2},\ldots ,i_{u}$ $t$ $e(x)=e_{i_{1}}x^{i_{1}}+e_{i_{2}}x^{i_{2}}+\ldots +e_{i_{u}} x^{i_{u}}$ $e_{i_{1}},e_{i_{2}},\ldots ,e_{i_{u}}$

Voit muodostaa hyväksytyn sanan syndroman : $j$ $S_j$ $r(x)$

S_{j}=r(\beta ^{l_{0}-1+j})=e(\beta ^{l_{0}-1+j}),\quad j=1,\ldots ,d-1.

Tehtävänä on löytää virheiden lukumäärä , niiden sijainti ja merkitys tunnetuille oireyhtymille . $u$ $i_{1},i_{2},\ldots ,i_{u}$ $e_{i_{1}},e_{i_{2}},\ldots ,e_{i_{u}}$ $S_j$

Oletetaan aluksi, että se on täsmälleen yhtä suuri . Kirjoitamme oireyhtymät epälineaaristen yhtälöiden järjestelmän muodossa eksplisiittisessä muodossa: $u$ $t$

{\begin{cases}S_{1}=e_{i_{1}}\beta ^{l_{0}i_{1}}+e_{i_{2}}\beta ^{l_{0} i_{2}}+\ldots +e_{i_{t}}\beta ^{l_{0}i_{t}},\\S_{2}=e_{i_{1}}\beta ^{(l_ {0}+1)i_{1}}+e_{i_{2}}\beta ^{(l_{0}+1)i_{2}}+\ldots +e_{i_{t}}\beta ^ {(l_{0}+1)i_{t}},\\\vdots \\S_{d-1}=e_{i_{1}}\beta ^{(l_{0}+d-2)i_ {1}}+e_{i_{2}}\beta ^{(l_{0}+d-2)i_{2}}+\ldots +e_{i_{t}}\beta ^{(l_{0 }+d-2)i_{t}}.\\\end{cases}}

Merkitään -: nnen virheen paikantimella ja - virheen suuruudella , . Tässä tapauksessa kaikki ovat erilaisia, koska elementin järjestys on , ja siksi, kun se tunnetaan , se voidaan määritellä muodossa . $X_{k}=\beta ^{{i_{k}}}$ $k$ $Y_{k}=e_{{i_{k}}}$ $k=1,\ldots ,t$ $X_{k}$ $\beeta$ $n$ $X_{k}$ $i_{k}$ ${\displaystyle i_{k}=\log _{\beta }X_{k))$

{\begin{cases}S_{1}=Y_{1}X_{1}^{l_{0}}+Y_{2}X_{2}^{l_{0}}+\ldots +Y_ {t}X_{t}^{l_{0}},\\S_{2}=Y_{1}X_{1}^{l_{0}+1}+Y_{2}X_{2}^{ l_{0}+1}+\ldots +Y_{t}X_{t}^{l_{0}+1},\\\vdots \\S_{d-1}=Y_{1}X_{1} ^{l_{0}+d-2}+Y_{2}X_{2}^{l_{0}+d-2}+\lpisteet +Y_{t}X_{t}^{l_{0}+ d-2}.\end{cases}}

Muodostetaan polynomi virheenpaikantimista :

\Lambda (x)=(1-xX_{1})(1-xX_{2})\ldots (1-xX_{t})=\Lambda _{t}x^{t}+\Lambda _{t-1}x^{t-1}+\ldots +\Lambda _{1}x+1.

Tämän polynomin juuret ovat elementit, jotka ovat käänteisiä virheen paikantimille. Kerro tämän polynomin molemmat puolet . Tuloksena oleva tasa-arvo on voimassa : ${\displaystyle Y_{l}X_{l}^{\vartheta +t))$ $\vartheta =l_{0},l_{0}+1,\ldots ,l_{0}+d-1,\ l=1,\ldots ,t$

\Lambda (x)Y_{l}X_{l}^{\vartheta +t}=\Lambda _{t}x^{t}Y_{l}X_{l}^{\vartheta +t} +\Lambda _{t-1}x^{t-1}Y_{l}X_{l}^{\vartheta +t}+\ldots +\Lambda _{1}xY_{l}X_{l}^ {\vartheta +t}+Y_{l}X_{l}^{\vartheta +t}.

Jos korvaamme tämän, saamme tasa-arvon, joka on voimassa jokaiselle ja kaikille : ${\displaystyle x=X_{l}^{-1))$ ${\displaystyle l\in \{1,2,\ldots ,t\))$ ${\displaystyle \vartheta \in \{l_{0},l_{0}+1,\ldots ,l_{0}+d-1\))$

0=\Lambda _{t}Y_{l}X_{l}^{\vartheta }+\Lambda _{t-1}Y_{l}X_{l}^{\vartheta +1}+\ ldots +\Lambda _{1}Y_{l}X_{l}^{\vartheta +t-1}+Y_{l}X_{l}^{\vartheta +t}.

Siten jokaiselle voit kirjoittaa oman tasa-arvosi. Jos ne lasketaan yhteen , niin saadaan tasa-arvo, joka on voimassa jokaiselle : $l$ $l$ ${\displaystyle \vartheta \in \{l_{0},l_{0}+1,\ldots ,l_{0}+d-1\))$

0=\Lambda _{t}\sum _{l=1}^{t}Y_{l}X_{l}^{\vartheta }+\Lambda _{t-1}\sum _{l =1}^{t}Y_{l}X_{l}^{\vartheta +1}+\ldots +\Lambda _{1}\sum _{l=1}^{t}Y_{l}X_{ l}^{\vartheta +t-1}+\sum _{l=1}^{t}Y_{l}X_{l}^{\vartheta +t}.

Koska (eli se muuttuu samoissa rajoissa kuin ennen), oireyhtymien yhtälöjärjestelmä muutetaan lineaaristen yhtälöiden järjestelmäksi : $S_{j+p}=\sum _{l=1}^{t}Y_{l}X_{l}^{l_{0}+j+p-1}=\sum _{l= 1}^{t}Y_{l}X_{l}^{\vartheta +p},\ j=1,\ldots ,d-1,\ \vartheta =l_{0}+j-1$ $\vartheta$

{\begin{cases}S_{1}\Lambda _{t}+S_{2}\Lambda _{t-1}+\ldots +S_{t}\Lambda _{1}=-S_{ t+1},\\S_{2}\Lambda _{t}+S_{3}\Lambda _{t-1}+\ldots +S_{t+1}\Lambda _{1}=-S_{ t+2},\\\vdots \\S_{t}\Lambda _{t}+S_{t+1}\Lambda _{t-1}+\ldots +S_{2t-1}\Lambda _{ 1}=-S_{2t},\end{cases}}

tai matriisimuodossa

S^{(t)} \bar\Lambda^{(t)} = -\bar s^{(t)},

missä

S^{(t)}={\begin{pmatrix}S_{1}&S_{2}&\lpisteet &S_{t}\\S_{2}&S_{3}&\lpisteet &S_{t+1 }\\\vpisteet &\vdots &\ddots &\vdots \\S_{t}&S_{t+1}&\ldots &S_{2t-1}\end{pmatrix)),\quad {\bar {\Lambda }}^{(t)}={\begin{pmatrix}\Lambda _{t}\\\Lambda _{t-1}\\\vdots \\\Lambda _{1}\end{pmatrix}}, \quad {\bar {s}}^{(t)}={\begin{pmatrix}S_{t+1}\\S_{t+2}\\\vdots \\S_{2t}\end{pmatrix }}.

Jos virheiden määrä on todellakin yhtä suuri kuin , niin tämä järjestelmä on ratkaistavissa, ja kertoimien arvot voidaan löytää . Jos luku on , niin matriisin determinantti on yhtä suuri kuin . Tämä on merkki siitä, että virheiden määrä on pienempi . Siksi on välttämätöntä muodostaa järjestelmä olettaen, että virheiden lukumäärä on yhtä suuri , laskea uuden matriisin determinantti jne. kunnes saadaan selville virheiden todellinen lukumäärä. $t$ ${\displaystyle \Lambda _{1},\ldots ,\Lambda _{t))$ $u<t$ $S^{{(t)}}$ $0$ $t$ $t-1$ $S^{{(t-1)}}$

Etsi Chen

Kun avainyhtälöjärjestelmä on ratkaistu, saadaan virheenpaikannuspolynomin kertoimet. Sen juuret (virheen paikantimille käänteiset elementit) voidaan löytää yksinkertaisesti iteroimalla kaikki kentän elementit . Etsi heille elementtejä, jotka ovat käänteisiä kertolaskulle - nämä ovat virheen paikantajia . Tämä prosessi on helppo toteuttaa laitteistossa. $GF(q^{m})$ $X_{k},\ k=1,\ldots ,u$

Forneyn algoritmi

Paikantimien avulla löydät oireyhtymien järjestelmästä virhepaikat ( ) ja virhearvot hyväksymällä . Dekoodaus valmis. ${\displaystyle i_{k}=\log _{\beta }X_{k))$ $Y_{k}$ $t=u$

Katso myös

Muistiinpanot

↑ Sagalovich, 2007 , s. 175-176.
↑ Sagalovich, 2007 , s. 176.
↑ Sagalovich, 2007 , s. 168.
↑ Virheenkorjauksen taito Arkistoitu 1. huhtikuuta 2013 Wayback Machinessa , s. 91.
↑ Sagalovich, 2007 , s. 200.

Kirjallisuus

Blahut R. Virheenhallintakoodien teoria ja käytäntö. — M .: Mir , 1986. — 576 s.
Peterson W, Weldon E. Virheenkorjauskoodit . - M .: Mir, 1976. - S. 596 .
Sagalovich Yu. L. Johdatus algebrallisiin koodeihin - M .: MIPT , 2007. - 262 s. — ISBN 978-5-7417-0191-1
Morelos-Zaragoza R. Virheenkorjauskoodauksen taito. Menetelmät, algoritmit, sovellus. - M . : Technosfera, 2005. - 320 s. — ISBN 5-94836-035-0 .