Codul Bowes-Chowdhury-Hockwingham

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 25 februarie 2021; verificările necesită 3 modificări .

Codurile Bowes-Chowdhury-Hokvingham (coduri BCH) - în teoria codificării, aceasta este o clasă largă de coduri ciclice utilizate pentru a proteja informațiile de erori (vezi Detectarea și corectarea erorilor ). Se deosebește prin posibilitatea de a construi un cod cu proprietăți corective predeterminate, și anume distanța minimă a codului. Un caz special al codurilor BCH este codul Reed-Solomon .

Descriere formală

Un cod BCH este un cod ciclic care poate fi dat de un polinom generator . Pentru a-l găsi în cazul unui cod BCH, este necesar să se determine în prealabil lungimea codului (nu poate fi arbitrar) și distanța minimă necesară . Puteți găsi un polinom generator în felul următor. $n$ $d\leqslant n$

Fie un element primitiv al câmpului (adică ), fie , fie un element al câmpului de ordine , . Atunci un polinom normalizat de grad minim peste un câmp ale cărui rădăcini sunt puteri succesive ale unui element pentru un număr întreg (inclusiv 0 și 1) este un polinom generator al unui cod BCH pe un câmp cu lungime și distanță minimă . $\alfa$ $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}$ $\beta$ $l_{0}$ $GF(q)$ $n$ $d_{0}\geqslant d$

Să explicăm de ce codul rezultat va avea exact astfel de caracteristici (lungimea codului , distanța minimă ). Într-adevăr, după cum arată Sagalovici [1] , lungimea codului BCH este egală cu ordinea elementelor dacă , și egală cu ordinea elementelor dacă . Deoarece nu ne interesează cazul (un astfel de cod nu poate corecta erorile, ci doar le detectează), lungimea codului va fi egală cu ordinea elementului , adică egală cu . Distanța minimă poate fi mai mare decât atunci când rădăcinile funcțiilor minime [2] ale elementelor sunt elementele care extind succesiunea, adică elementele . $n$ $d_{0}$ $\beta$ $d>2$ $\beta ^{l_{0}}$ $d=2$ $d=2$ $\beta$ $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))$

Numărul simbolurilor cec este egal cu gradul , numărul simbolurilor informaționale , valoarea se numește distanța constructivă a codului BCH. Dacă , atunci codul se numește primitiv , în caz contrar - non- primitiv . $r$ $g(x)$ $k=nr$ $d$ $n=q^{m}-1$

La fel ca și pentru codul ciclic, polinomul de cod poate fi obținut din polinomul informațional de grad cel mult , prin înmulțirea și : $c(x)$ $m(x)$ $k-1$ $m(x)$ $g(x)$

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

Clădire

Pentru a găsi polinomul generator, este necesar să se efectueze mai mulți pași [3] :

selectați , adică câmpul peste care va fi construit codul; $q$ $GF(q)$
selectați lungimea codului din condiția , unde sunt numere întregi pozitive; $n$ $n=(q^{m}-1)/s$ $m,s$
stabiliți valoarea distanței constructive; $d$
construiți clase ciclotomice ale unui element câmp peste un câmp , unde este un element primitiv ; $\beta =\alpha ^{s}$ $GF(q^{m})$ $GF(q)$ $\alfa$ $GF(q^{m})$
întrucât fiecărei astfel de clase ciclotomice îi corespunde un polinom ireductibil peste , ale cărui rădăcini sunt elemente ale acestei clase și numai ale acestei clase, cu un grad egal cu numărul de elemente din clasă, atunci alegeți în așa fel încât lungimea totală a claselor ciclotomice să fie minim; acest lucru se face pentru a minimiza numărul de caractere de verificare pentru caracteristicile date ale codului ; $GF(q)$ $\beta ^{l_{0}},\beta ^{l_{0}+1},\ldots ,\beta ^{l_{0}+d-2}$ $n$ $d$ $k$
se calculează polinomul generator , unde este polinomul corespunzător clasei --a ciclotomică; sau calculați ca LCM al funcțiilor minime ale elementelor lui . $g(x)=f_{1}(x)f_{2}(x)\ldots f_{h}(x)$ $f_{i}(x)$ $i$ $g(x)$ $\beta ^{l_{0}},\beta ^{l_{0}+1},\ldots ,\beta ^{l_{0}+d-2}$

Exemple de cod

Cod binar primitiv (15, 7, 5)

Fie , lungimea codului necesară și distanța minimă . Luați — un element primitiv al câmpului și — patru puteri consecutive ale elementului . Ele aparțin a două clase ciclotomice peste câmpul căruia îi corespund polinoamele ireductibile și . Apoi polinomul $q=2$ $n=2^{4}-1=15$ $d_{0}\geqslant d=5$ $\alfa$ $GF(16)$ $\alpha,\alpha ^{2},\alpha ^{3},\alpha ^{4)$ $\alfa$ $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

are elemente ca rădăcini și este un polinom generator al codului BCH cu parametri . $\alpha,\alpha ^{2},\alpha ^{3},\alpha ^{4)$ $(15,7,5)$

Cod hexazecimal (15, 11, 5) (codul Reed-Solomon)

Fie , și un element primitiv al . Apoi $n=q-1=15$ $\alfa$ $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}.

Fiecare element al câmpului poate fi mapat la 4 biți , deci un cuvânt de cod este echivalent cu 60 = 15 × 4 biți, deci un set de 44 de biți este mapat la un set de 60 de biți. Putem spune că un astfel de cod funcționează cu fragmente de informații. $GF(16)$

Codificare

Pentru codificarea cu coduri BCH se folosesc aceleași metode ca și pentru codarea cu coduri ciclice.

Metode de decodare

Codurile BCH sunt coduri ciclice, așa că li se aplică toate metodele utilizate pentru a decoda codurile ciclice. Cu toate acestea, există algoritmi mult mai buni dezvoltați special pentru codurile BCH [4] .

Ideea principală în decodificarea codurilor BCH este de a folosi elementele câmpului final pentru a numerota pozițiile cuvântului de cod (sau, echivalent, în ordinea coeficienților polinomului asociat). Mai jos este o astfel de enumerare pentru vectorul corespunzător polinomului . $r=(r_{0},r_{1},\ldots, r_{n-1})$ $r(x)$

valorile	$r_{0}$	$r_{1}$	$\ldots$	$r_{{n-1}}$
localizatori de poziție	$unu$	$\alfa$	$\ldots$	$\alpha ^{{n-1}}$

Fie asociat cuvântului primit cu polinomul , unde polinomul de eroare este definit ca: , unde este numărul de erori din cuvântul primit. Seturile și sunt numite valori de eroare și , respectiv, localizatori de erori , unde și . $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 }}\}$ $\{\alpha ^{J_{1}),\alpha ^{J_{2)),\ldots,\alpha ^{J_{\nu ))\)$ $e_{J}\în GF(q)$ $\alpha \in GF(q^{m})$

Sindroamele sunt definite ca valorile polinomului primit la zerourile polinomului cod generator: $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 )),

unde . $2t_{d}=d-1$

Pentru a găsi setul de localizatori de erori, introducem polinomul localizator de erori

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

ale căror rădăcini sunt egale cu reciprocele locatorilor de erori. Atunci următoarea relație este valabilă între coeficienții polinomului de localizare a erorilor și sindroame [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}.

Următoarele metode sunt cunoscute pentru rezolvarea acestui sistem de ecuații în raport cu coeficienții polinomului de localizare a erorilor ( sistemul cheie de ecuații ). $\sigma _{i},\i=1,2,\ldots ,\nu$

Algoritmul Berlekamp-Massey (BMA) . În ceea ce privește numărul de operații într-un câmp finit, acest algoritm este foarte eficient. BMA este folosit în mod obișnuit pentru a implementa sau modela în mod programatic codurile BCH și codurile Reed-Solomon .
Algoritmul euclidian (EA) . Datorită regularității ridicate a structurii acestui algoritm, este utilizat pe scară largă pentru implementarea hardware a decodoarelor BCH și a codurilor Reed-Solomon .
Soluție directă (algoritm Peterson-Gorenstein-Zierler, PGC). Din punct de vedere istoric, aceasta este prima metodă de decodare găsită de Peterson pentru cazul binar ( ), apoi de Gorenstein și Zierler pentru cazul general. Acest algoritm găsește coeficienții polinomii de localizare a erorilor prin rezolvarea directă a sistemului corespunzător de ecuații liniare. De fapt, deoarece complexitatea acestui algoritm crește pe măsură ce cubul distanței minime , algoritmul direct poate fi utilizat numai pentru valori mici ale , dar acest algoritm clarifică cel mai bine ideea algebrică a procesului de decodare. $q=2$ $d$ $d$

Algoritmul Berlekamp-Massey

Acest algoritm este cel mai bine privit ca un proces iterativ de construire a unui registru de feedback minim (deplasare) care generează o secvență cunoscută de sindroame . Scopul său real este de a construi un polinom de cel mai mic grad care satisface ecuația $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+ one .

Rezolvarea acestei ecuații este echivalentă cu condiția

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

Procesul iterativ de construire a unui astfel de polinom este algoritmul Berlekamp-Massey .

Algoritm euclidian

Această metodă se bazează pe cunoscutul algoritm al lui Euclid pentru găsirea celui mai mare divizor comun a două numere (mcd), doar că în acest caz căutăm mcd nu a două numere, ci a două polinoame. Să notăm polinomul valorilor de eroare ca , unde polinomul sindromic este egal cu . Din sistemul de ecuaţii rezultă că . Problema se rezumă în esență la a determina care satisface ultima ecuație și, în același timp, gradul nu este mai mare . De fapt, o astfel de soluție va da algoritmul Euclid extins aplicat polinoamelor și , unde . Dacă la pasul al treilea algoritmul euclidian extins produce o soluție astfel încât , atunci , și . În acest caz, polinomul găsit nu mai participă la decodare (este căutat doar ca unul auxiliar). În acest fel, se va găsi polinomul de localizare a erorilor . $\Lambda =\sigma (x)S(x)$ $S(x)=1+S_{1}x+\ldots +S_{2t_{d}}x^{2t_{d}}$ $\Lambda (x)=\sigma (x)S(x)\mod x^{2t_{d}+1)$ $\Lambda(x)$ $t_{d)$ $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)$ $\deg[r_{j}(x)]\leqslant t_{d)$ $\Lambda (x)=r_{j}(x)$ $\sigma _{i}(x)=b_{j}(x)$ $a_{j}(x)$ $\sigma (x)$

Soluție directă (algoritm Petersson-Gorenstein-Zierler, PGC)

Fie codul BCH peste câmpul de lungime și cu o distanță constructivă să fie dat de un polinom generator , care are printre rădăcini elemente - un număr întreg (de exemplu, 0 sau 1). Apoi fiecare cuvânt de cod are proprietatea că . Cuvântul primit poate fi scris ca , unde este polinomul de eroare. Fie ca erorile să apară la poziții ( este numărul maxim de erori corectabile), deci , și sunt mărimile erorilor. $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}}$

Puteți compune al treilea sindrom al cuvântului acceptat : $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.

Sarcina este de a găsi numărul de erori , pozițiile și semnificațiile lor pentru sindroamele cunoscute . $u$ $i_{1},i_{2},\ldots, i_{u}$ $e_{i_{1}},e_{i_{2}},\ldots ,e_{i_{u}}$ $S_j$

Să presupunem pentru început că este exact egal cu . Scriem sindroamele sub forma unui sistem de ecuații neliniare în formă explicită: $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}}

Se notează prin locatorul erorii --a și prin — mărimea erorii, . În acest caz, toate sunt diferite, deoarece ordinea elementului este și, prin urmare, atunci când este cunoscută , poate fi definită ca . $X_{k}=\beta ^{{i_{k}}}$ $k$ $Y_{k}=e_{{i_{k}}}$ $k=1,\ldots ,t$ $X_{k}$ $\beta$ $n$ $X_{k}$ $eu_{k}$ $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}+\ldots +Y_{t}X_{t}^{l_{0}+ d-2}.\end{cazuri}}

Să compunem un polinom de localizatori de erori :

\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.

Rădăcinile acestui polinom sunt elementele inverse locatorilor de erori. Înmulțiți ambele părți ale acestui polinom cu . Egalitatea rezultată va fi valabilă pentru : $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}.

Dacă înlocuim aici , atunci obținem o egalitate care este valabilă pentru fiecare și pentru toți : $x=X_{l}^{-1)$ $l\in \{1,2,\ldots,t\)$ $\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}.

Astfel, pentru fiecare , puteți scrie propria egalitate. Dacă sunt însumate , atunci obținem o egalitate care este valabilă pentru fiecare : $l$ $l$ $\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}.

Deoarece (adică se schimbă în aceleași limite ca și înainte), sistemul de ecuații pentru sindroame este transformat într- un sistem de ecuații liniare : $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}}

sau, sub formă de matrice,

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

Unde

S^{(t)}={\begin{pmatrix}S_{1}&S_{2}&\ldots &S_{t}\\S_{2}&S_{3}&\ldots &S_{t+1 }\\\vdots &\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 }}.

Dacă numărul de erori este într-adevăr egal cu , atunci acest sistem este rezolvabil și se pot găsi valorile coeficienților . Dacă numărul este , atunci determinantul matricei va fi egal cu . Acesta este un semn că numărul de erori este mai mic . Prin urmare, este necesar să se compună un sistem, presupunând numărul de erori egal cu , să se calculeze determinantul noii matrice , etc. până când stabilim numărul adevărat de erori. $t$ $\Lambda _{1},\ldots,\Lambda _{t)$ $u<t$ $S^{{(t)}}$ $0$ $t$ $t-1$ $S^{{(t-1)}}$

Caută Chen

După rezolvarea sistemului cheie de ecuații, se obțin coeficienții polinomului de localizare a erorilor. Rădăcinile sale (elementele inverse locatorilor de erori) pot fi găsite prin simpla iterare peste toate elementele câmpului . Pentru ei, găsiți elemente care sunt inverse înmulțirii - aceștia sunt localizatori de erori . Acest proces este ușor de implementat în hardware. $GF(q^{m})$ $X_{k},\k=1,\ldots ,u$

Algoritmul lui Forney

Folosind locatoarele, puteți găsi pozițiile de eroare ( ) și valorile de eroare din sistemul pentru sindroame, acceptând . Decodificarea finalizată. $i_{k}=\log _{\beta}X_{k)$ $Y_{k}$ $t=u$

Vezi și

Note

↑ Sagalovici, 2007 , p. 175-176.
↑ Sagalovici, 2007 , p. 176.
↑ Sagalovici, 2007 , p. 168.
↑ Arta codificării corectării erorilor Arhivat la 1 aprilie 2013 la Wayback Machine , p. 91.
↑ Sagalovici, 2007 , p. 200.

Literatură

Blahut R. Teoria și practica codurilor de control al erorilor. — M .: Mir , 1986. — 576 p.
Peterson W, Weldon E. Codurile de corectare a erorilor . - M . : Mir, 1976. - S. 596 .
Sagalovici Yu. L. Introducere în codurile algebrice - M. : MIPT , 2007. - 262 p. — ISBN 978-5-7417-0191-1
Morelos-Zaragoza R. Arta codificării corectoare de erori. Metode, algoritmi, aplicare. - M . : Technosfera, 2005. - 320 p. — ISBN 5-94836-035-0 .