Bowes-Chowdhury-Hockwingham-koden

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 25. februar 2021; checks kræver 3 redigeringer .

Bowes-Chowdhury-Hokvingham-koder (BCH-koder) - i kodningsteori er dette en bred klasse af cykliske koder , der bruges til at beskytte information mod fejl (se Fejldetektering og -korrektion ). Det adskiller sig ved muligheden for at bygge en kode med forudbestemte korrigerende egenskaber, nemlig den mindste kodeafstand. Et særligt tilfælde af BCH-koder er Reed-Solomon-koden .

Formel beskrivelse

En BCH-kode er en cyklisk kode , der kan gives af et generatorpolynomium . For at finde den i tilfælde af en BCH-kode er det nødvendigt på forhånd at bestemme længden af koden (den kan ikke være vilkårlig) og den nødvendige minimumsafstand . Du kan finde et genererende polynomium på følgende måde. $n$ $d\leqslant n$

Lade være et primitivt element i feltet (dvs. ), lad , være et element i ordensfeltet , . Så er et normaliseret polynomium af minimumsgrad over et felt, hvis rødder er successive potenser af et element for et eller andet heltal (inklusive 0 og 1) et genererende polynomium af en BCH-kode over et felt med længde og minimumsafstand . $\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$

Lad os forklare, hvorfor den resulterende kode vil have præcis sådanne egenskaber (kodelængde , minimumafstand ). Faktisk, som vist af Sagalovich [1] , er længden af BCH-koden lig med elementrækkefølgen if , og lig med elementrækkefølgen if . Da vi ikke er interesserede i sagen (en sådan kode kan ikke rette fejl, kun opdage dem), vil længden af koden være lig med rækkefølgen af elementet , det vil sige lig med . Minimumsafstanden kan være større, end når rødderne af elementernes minimale funktioner [2] er de elementer, der udvider rækkefølgen, det vil sige elementerne . $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))$

Antallet af kontrolsymboler er lig med graden , antallet af informationssymboler , værdien kaldes den konstruktive afstand af BCH-koden. Hvis , så kaldes koden primitiv , ellers ikke- primitiv . $r$ $g(x)$ $k=nr$ $d$ $n=q^{m}-1$

Ligesom for den cykliske kode kan kodepolynomiet opnås fra informationspolynomiet af grad ved at multiplicere og : $c(x)$ $m(x)$ $k-1$ $m(x)$ $g(x)$

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

Bygning

For at finde det genererende polynomium er det nødvendigt at udføre flere trin [3] :

vælg , det vil sige det felt , som koden skal bygges over; $q$ $GF(q)$
vælg kodelængden fra betingelsen , hvor er positive heltal; $n$ $n=(q^{m}-1)/s$ $m,s$
indstille værdien af den konstruktive afstand; $d$
konstruere cyklotomiske klasser af et feltelement over et felt , hvor er et primitivt element ; $\beta =\alpha ^{s}$ $GF(q^{m})$ $GF(q)$ $\alfa$ $GF(q^{m})$
da hver sådan cyklotomisk klasse svarer til et irreducerbart polynomium over , hvis rødder er elementer i denne og kun denne klasse, med en grad lig med antallet af elementer i klassen, så vælg på en sådan måde, at den samlede længde af cyklotomiske klasser er minimal; dette gøres for at minimere antallet af kontroltegn for kodens givne karakteristika ; $GF(q)$ $\beta ^{l_{0}},\beta ^{l_{0}+1},\ldots ,\beta ^{l_{0}+d-2}$ $n$ $d$ $k$
beregn det genererende polynomium , hvor er polynomiet svarende til den -th cyclotomic klasse; eller beregn som LCM for minimumsfunktionerne af elementerne i . $g(x)=f_{1}(x)f_{2}(x)\ldots f_{h}(x)$ $rette op)$ $jeg$ $g(x)$ $\beta ^{l_{0}},\beta ^{l_{0}+1},\ldots ,\beta ^{l_{0}+d-2}$

Kodeeksempler

Primitiv binær (15, 7, 5) kode

Lad , den nødvendige kodelængde og minimumsafstanden . Tag — et primitivt element i feltet , og — fire på hinanden følgende potenser af elementet . De tilhører to cyclotomic klasser over det felt , som de irreducible polynomier og svarer til . Derefter polynomiet $q=2$ $n=2^{4}-1=15$ $d_{0}\geqslant d=5$ $\alfa$ $GF(16)$ ${\displaystyle \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

har elementer som rødder og er et genererende polynomium af BCH-koden med parametre . ${\displaystyle \alpha ,\alpha ^{2},\alpha ^{3},\alpha ^{4))$ $(15,7,5)$

Hexadecimal (15, 11, 5) kode (Reed-Solomon-kode)

Lad , og vær et primitivt element af . Derefter $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}.

Hvert element i feltet kan afbildes til 4 bit , så et kodeord svarer til 60 = 15 × 4 bit, så et sæt på 44 bit er afbildet til et sæt på 60 bit. Vi kan sige, at en sådan kode fungerer med småting af information. $GF(16)$

Kodning

Til kodning med BCH-koder anvendes de samme metoder som til kodning med cykliske koder.

Afkodningsmetoder

BCH-koder er cykliske koder, så alle metoder, der bruges til at afkode cykliske koder, gælder for dem. Der er dog meget bedre algoritmer udviklet specifikt til BCH-koder [4] .

Hovedideen ved afkodning af BCH-koder er at bruge elementerne i det endelige felt til at nummerere kodeordets positioner (eller tilsvarende i rækkefølgen af koefficienterne for det tilknyttede polynomium). Nedenfor er en sådan opregning for vektoren svarende til polynomiet . $r=(r_{0},r_{1},\ldots ,r_{n-1})$ $r(x)$

værdier	$r_{0}$	$r_{1}$	$\ldots$	$r_{{n-1}}$
positionssøgere	$en$	$\alfa$	$\ldots$	$\alpha ^{{n-1}}$

Lad det modtagne ord være forbundet med polynomiet , hvor fejlpolynomiet er defineret som: , hvor er antallet af fejl i det modtagne ord. Sæt og kaldes henholdsvis fejlværdier og fejlfindere , hvor , og . $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}\i GF(q)$ $\alpha \in GF(q^{m})$

Syndromer er defineret som værdierne af det modtagne polynomium ved nullerne i det genererende kodepolynomium: $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}}\ alpha ^{(b+1)J_{2}}+\ldots +e_{J_{\nu }}\alpha ^{(b+1)J_{\nu )),

\vprikker

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

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

For at finde sættet af fejlfindere introducerer vi fejlfinderpolynomiet

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

hvis rødder er lig med de reciproke fejlfindere. Så er følgende relation gyldig mellem koefficienterne for fejlfindingspolynomiet og syndromer [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},

\vprikker

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

Følgende metoder er kendte til at løse dette ligningssystem med hensyn til koefficienterne for fejlfindingspolynomiet ( nøglesystem af ligninger ). $\sigma _{i},\ i=1,2,\ldots ,\nu$

Berlekamp-Massey algoritme (BMA) . Med hensyn til antallet af operationer i et begrænset felt er denne algoritme yderst effektiv. BMA bruges almindeligvis til programmatisk at implementere eller modellere BCH-koder og Reed-Solomon-koder .
Euklidisk algoritme (EA) . På grund af den høje regelmæssighed af strukturen af denne algoritme, er den meget brugt til hardwareimplementering af BCH-dekodere og Reed-Solomon-koder .
Direkte løsning (Peterson-Gorenstein-Zierler-algoritme, PGC). Historisk set er dette den første afkodningsmetode fundet af Peterson for det binære tilfælde ( ), derefter af Gorenstein og Zierler for det generelle tilfælde. Denne algoritme finder fejlfinderpolynomielkoefficienterne ved direkte løsning af det tilsvarende system af lineære ligninger. Faktisk, da kompleksiteten af denne algoritme vokser som kuben af minimumsafstanden , kan den direkte algoritme kun bruges til små værdier på , men det er denne algoritme, der bedst tydeliggør den algebraiske idé om afkodningsprocessen. $q=2$ $d$ $d$

Berlekamp-Massey algoritme

Denne algoritme ses bedst som en iterativ proces til at konstruere et minimum feedback (shift) register, der genererer en kendt sekvens af syndromer . Dets egentlige mål er at konstruere et polynomium af den mindste grad, der opfylder ligningen $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 .

Løsningen af denne ligning svarer til betingelsen

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

Den iterative proces med at konstruere et sådant polynomium er Berlekamp-Massey-algoritmen .

Euklidisk algoritme

Denne metode er baseret på den velkendte Euklids algoritme til at finde den største fælles divisor af to tal (gcd), kun i dette tilfælde leder vi efter gcd ikke af to tal, men af to polynomier. Lad os betegne polynomiet af fejlværdier som , hvor det syndromiske polynomium er lig med . Det følger af ligningssystemet, at . Problemet går i det væsentlige ned til at bestemme, hvilken der opfylder den sidste ligning, og samtidig er graden ikke højere . Faktisk vil en sådan løsning give den udvidede euklidiske algoritme anvendt på polynomier og , hvor . Hvis den udvidede euklidiske algoritme i det th trin producerer en løsning sådan, at , så , og . I dette tilfælde deltager det fundne polynomium ikke yderligere i afkodningen (det søges kun som et hjælpe). På denne måde vil fejlfindingspolynomiet blive fundet . $\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)$ ${\displaystyle 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)$

Direkte løsning (Petersson-Gorenstein-Zierler-algoritme, PGC)

Lad BCH-koden over længdefeltet og med en konstruktiv afstand være givet af et genererende polynomium , som blandt sine rødder har elementer - et heltal (f.eks. 0 eller 1). Så har hvert kodeord egenskaben, at . Det modtagne ord kan skrives som , hvor er fejlpolynomiet. Lad fejl opstå ved positioner ( er det maksimale antal korrigerbare fejl), så , og er størrelsen af fejl. $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}}$

Du kan komponere syndromet af det accepterede ord : $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.

Opgaven er at finde antallet af fejl , deres positioner og deres betydning for kendte syndromer . $u$ $i_{1},i_{2},\ldots ,i_{u}$ $e_{i_{1}},e_{i_{2}},\ldots ,e_{i_{u}}$ $S_j$

Antag til at begynde med, at nøjagtigt svarer til . Vi skriver syndromerne i form af et system af ikke-lineære ligninger i eksplicit form: $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}}

Angiv med locatoren af den -th fejl, og med - størrelsen af fejlen, . I dette tilfælde er alle forskellige, da rækkefølgen af elementet er , og derfor, når kendt , kan defineres som . $X_{k}=\beta ^{{i_{k}}}$ $k$ $Y_{k}=e_{{i_{k}}}$ $k=1,\ldots ,t$ $X_{k}$ $\beta$ $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}+\ldots +Y_{t}X_{t}^{l_{0}+ d-2}.\end{cases}}

Lad os sammensætte et polynomium af fejlfindere :

\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ødderne af dette polynomium er de elementer, der er omvendt til fejlfinderne. Gang begge sider af dette polynomium med . Den resulterende lighed vil være gyldig for : ${\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}.

Hvis vi erstatter her , så får vi en lighed, der gælder for alle og enhver : ${\displaystyle x=X_{l}^{-1))$ $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}.

Således kan du for hver , skrive din egen ligestilling. Hvis de summeres , får vi en lighed, der er gyldig for hver : $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}.

Da (det vil sige, det ændrer sig inden for de samme grænser som før), transformeres ligningssystemet for syndromer til et system af lineære ligninger : $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}}

eller i matrixform,

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

hvor

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

Hvis antallet af fejl faktisk er lig med , så er dette system løseligt, og man kan finde værdierne af koefficienterne . Hvis tallet er , så vil determinanten af matricen være lig med . Dette er et tegn på, at antallet af fejl er mindre . Derfor er det nødvendigt at sammensætte et system, der antager antallet af fejl lig med , beregne determinanten for den nye matrix osv. indtil vi fastslår det sande antal fejl. $t$ ${\displaystyle \Lambda _{1},\ldots ,\Lambda _{t))$ $u<t$ $S^{{(t)}}$ $0$ $t$ $t-1$ $S^{{(t-1)}}$

Søg efter Chen

Efter at nøglesystemet af ligninger er løst, opnås koefficienterne for fejlfindingspolynomiet. Dens rødder (elementerne omvendt til fejlfinderne) kan findes ved blot at gentage alle elementerne i feltet . For dem skal du finde elementer, der er omvendt til multiplikation - disse er fejlfindere . Denne proces er nem at implementere i hardware. $GF(q^{m})$ $X_{k},\ k=1,\ldots ,u$

Forneys algoritme

Ved hjælp af lokalisatorerne kan du finde fejlpositionerne ( ) og fejlværdierne fra systemet for syndromer ved at acceptere . Afkodning afsluttet. ${\displaystyle i_{k}=\log _{\beta}X_{k))$ $Y_{k}$ $t=u$

Se også

Noter

↑ Sagalovich, 2007 , s. 175-176.
↑ Sagalovich, 2007 , s. 176.
↑ Sagalovich, 2007 , s. 168.
↑ Kunsten at fejlkorrigere kodning Arkiveret 1. april 2013 på Wayback Machine , s. 91.
↑ Sagalovich, 2007 , s. 200.

Litteratur

Blahut R. Teori og praksis for fejlkontrolkoder. — M .: Mir , 1986. — 576 s.
Peterson W, Weldon E. Fejlretningskoder . - M . : Mir, 1976. - S. 596 .
Sagalovich Yu. L. Introduktion til algebraiske koder - M. : MIPT , 2007. - 262 s. — ISBN 978-5-7417-0191-1
Morelos-Zaragoza R. Kunsten at fejlkorrigere kodning. Metoder, algoritmer, anvendelse. - M . : Technosfera, 2005. - 320 s. — ISBN 5-94836-035-0 .