Kodex Bowes-Chowdhury-Hockwingham

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 25. února 2021; kontroly vyžadují 3 úpravy .

Bowes-Chowdhury-Hokvingham kódy (BCH kódy) - v teorii kódování se jedná o širokou třídu cyklických kódů používaných k ochraně informací před chybami (viz Detekce a oprava chyb ). Liší se možností sestavení kódu s předem určenými korekčními vlastnostmi, konkrétně minimální kódovou vzdáleností. Speciálním případem BCH kódů je Reed-Solomonův kód .

Formální popis

BCH kód je cyklický kód , který může být dán polynomem generátoru . Pro jeho nalezení v případě BCH kódu je nutné předem určit délku kódu (nemůže být libovolná) a požadovanou minimální vzdálenost . Generující polynom můžete najít následujícím způsobem. $n$ $d\leqslant n$

Nechť je primitivní prvek pole (tj. ), nechť , je prvek pole objednávky , . Pak normalizovaný polynom minimálního stupně nad polem, jehož kořeny jsou po sobě jdoucí mocniny prvku pro nějaké celé číslo (včetně 0 a 1), je generujícím polynomem BCH kódu nad polem o délce a minimální vzdálenosti . $\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}$ $\beta$ $l_{0}$ $GF(q)$ $n$ $d_{0}\geqslant d$

Pojďme si vysvětlit, proč bude mít výsledný kód právě takové vlastnosti (délka kódu , minimální vzdálenost ). Jak ukazuje Sagalovich [1] , délka BCH kódu je skutečně rovna pořadí prvků if a rovna pořadí prvků if . Jelikož nás případ nezajímá (takový kód neumí chyby opravovat, pouze je detekovat), bude délka kódu rovna pořadí prvku , tedy rovna . Minimální vzdálenost může být větší, než když kořeny minimálních funkcí [2] prvků jsou prvky, které rozšiřují posloupnost, tedy prvky . $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))$

Počet kontrolních symbolů je roven stupni , počtu informačních symbolů , hodnota se nazývá konstruktivní vzdálenost BCH kódu. Jestliže , pak se kód nazývá primitivní , jinak - neprimitivní . $r$ $g(x)$ $k=č$ $d$ $n=q^{m}-1$

Stejně jako u cyklického kódu lze polynom kódu získat z informačního polynomu stupně nejvýše , vynásobením a : $c(x)$ $m(x)$ $k-1$ $m(x)$ $g(x)$

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

Konstrukce

Pro nalezení generujícího polynomu je nutné provést několik kroků [3] :

vyberte , tedy pole, přes které bude kód vytvořen; $q$ $GF(q)$
vyberte délku kódu z podmínky , kde jsou kladná celá čísla; $n$ $n=(q^{m}-1)/s$ $m,s$
nastavte hodnotu konstruktivní vzdálenosti; $d$
konstruovat cyklotomické třídy elementu pole nad polem , kde je primitivní element ; $\beta =\alpha ^{s}$ $GF(q^{m})$ $GF(q)$ $\alpha$ $GF(q^{m})$
protože každá taková cyklotomická třída odpovídá neredukovatelnému polynomu nad , jehož kořeny jsou prvky této a pouze této třídy, se stupněm rovným počtu prvků ve třídě, pak zvolte tak, aby celková délka cyklotomických tříd byla minimální; to se provádí za účelem minimalizace počtu kontrolních znaků pro dané vlastnosti kódu ; $GF(q)$ $\beta ^{l_{0}},\beta ^{l_{0}+1},\ldots ,\beta ^{l_{0}+d-2}$ $n$ $d$ $k$
vypočítat generující polynom , kde je polynom odpovídající -té cyklotomické třídě; nebo vypočítat jako LCM minimálních funkcí prvků . $g(x)=f_{1}(x)f_{2}(x)\ldots f_{h}(x)$ $opravit)$ $i$ $g(x)$ $\beta ^{l_{0}},\beta ^{l_{0}+1},\ldots ,\beta ^{l_{0}+d-2}$

Příklady kódu

Primitivní binární (15, 7, 5) kód

Let , požadovaná délka kódu a minimální vzdálenost . Vezměte — primitivní prvek pole a — čtyři po sobě jdoucí mocniny prvku . Patří do dvou cyklotomických tříd na poli , kterému odpovídají ireducibilní polynomy . Pak polynom $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

má prvky jako kořeny a je generujícím polynomem BCH kódu s parametry . ${\displaystyle \alpha ,\alpha ^{2},\alpha ^{3},\alpha ^{4))$ $(15,7,5)$

Hexadecimální (15, 11, 5) kód (Reed-Solomonův kód)

Dovolit , a být primitivní prvek . Pak $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}.

Každý prvek pole lze mapovat na 4 bity , takže jedno kódové slovo je ekvivalentní 60 = 15 × 4 bitům, takže sada 44 bitů je mapována na sadu 60 bitů. Dá se říci, že takový kód pracuje s útržky informací. $GF(16)$

Kódování

Pro kódování pomocí BCH kódů se používají stejné metody jako pro kódování s cyklickými kódy.

Metody dekódování

BCH kódy jsou cyklické kódy, takže se na ně vztahují všechny metody používané k dekódování cyklických kódů. Existují však mnohem lepší algoritmy vyvinuté speciálně pro BCH kódy [4] .

Hlavní myšlenkou při dekódování BCH kódů je použití prvků konečného pole k očíslování pozic kódového slova (nebo ekvivalentně v pořadí koeficientů přidruženého polynomu). Níže je takový výčet pro vektor odpovídající polynomu . $r=(r_{0},r_{1},\ldots ,r_{n-1})$ $r(x)$

hodnoty	$r_{0}$	$r_{1}$	$\ldots$	$r_{{n-1}}$
lokátory polohy	$jeden$	$\alpha$	$\ldots$	$\alpha ^{{n-1}}$

Nechť je přijaté slovo spojeno s polynomem , kde chybový polynom je definován jako: , kde je počet chyb v přijatém slově. Sady a se nazývají chybové hodnoty a lokátory chyb , kde , a . $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})$

Syndromy jsou definovány jako hodnoty přijatého polynomu na nulách polynomu generujícího kódu: $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 )),

\vtečky

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

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

Abychom našli sadu lokátorů chyb, zavedeme polynom lokátoru chyb

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

jejichž kořeny se rovnají převráceným hodnotám lokátorů chyb. Pak platí následující vztah mezi koeficienty polynomu lokátoru chyb a syndromy [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},

\vtečky

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

Pro řešení této soustavy rovnic s ohledem na koeficienty polynomu lokátoru chyb ( klíčová soustava rovnic ) jsou známy následující metody. $\sigma _{i},\ i=1,2,\ldots ,\nu$

Algoritmus Berlekamp-Massey (BMA) . Z hlediska počtu operací v konečném poli je tento algoritmus vysoce efektivní. BMA se běžně používá k programové implementaci nebo modelování BCH kódů a Reed-Solomonových kódů .
Euklidovský algoritmus (EA) . Díky vysoké pravidelnosti struktury tohoto algoritmu je široce používán pro hardwarovou implementaci BCH dekodérů a Reed-Solomonových kódů .
Přímé řešení (Peterson-Gorenstein-Zierlerův algoritmus, PGC). Historicky se jedná o první metodu dekódování, kterou pro binární případ našel Peterson ( ), pro obecný případ pak Gorenstein a Zierler. Tento algoritmus najde polynomiální koeficienty lokátoru chyb přímým řešením odpovídajícího systému lineárních rovnic. Ve skutečnosti, protože složitost tohoto algoritmu roste s krychlí minimální vzdálenosti , lze přímý algoritmus použít pouze pro malé hodnoty , ale je to právě tento algoritmus, který nejlépe objasňuje algebraickou myšlenku procesu dekódování. $q=2$ $d$ $d$

Algoritmus Berlekamp-Massey

Tento algoritmus je nejlépe vidět jako iterativní proces konstrukce minimálního zpětnovazebního (posunového) registru generujícího známou sekvenci syndromů . Jeho skutečným cílem je sestrojit polynom nejmenšího stupně, který splňuje rovnici $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+ jedna .

Řešení této rovnice je ekvivalentní podmínce

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

Iterační proces konstrukce takového polynomu je Berlekamp-Massey Algorithm .

Euklidovský algoritmus

Tato metoda je založena na známém Euklidově algoritmu pro nalezení největšího společného dělitele dvou čísel (gcd), pouze v tomto případě nehledáme gcd dvou čísel, ale dvou polynomů. Označme polynom chybových hodnot jako , kde syndromický polynom je roven . Ze soustavy rovnic vyplývá, že . Problém se v podstatě scvrkává na určení , který splňuje poslední rovnici a zároveň stupeň není vyšší . Ve skutečnosti takové řešení poskytne rozšířený Euklidův algoritmus aplikovaný na polynomy a , kde . Jestliže v th kroku rozšířený euklidovský algoritmus vytvoří řešení takové, že , pak , a . V tomto případě se nalezený polynom dále nepodílí na dekódování (hledá se pouze jako pomocný). Tímto způsobem bude nalezen polynom lokátoru chyb . $\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)$

Přímé řešení (Petersson-Gorenstein-Zierlerův algoritmus, PGC)

Nechť BCH kód přes pole délky a s konstruktivní vzdáleností je dán generujícím polynomem , který má mezi kořeny prvky - celé číslo (například 0 nebo 1). Pak má každé kódové slovo vlastnost, že . Přijaté slovo lze zapsat jako , kde je chybový polynom. Nechat chyby se vyskytují na pozicích ( je maximální počet opravitelných chyb), takže , a jsou velikosti chyb. $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}}$

Syndrom přijatého slova můžete sestavit : $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.

Úkolem je zjistit počet chyb , jejich polohu a význam pro známé syndromy . $u$ $i_{1},i_{2},\ldots ,i_{u}$ $e_{i_{1}},e_{i_{2}},\ldots ,e_{i_{u}}$ $S_j$

Pro začátek předpokládejme, že se přesně rovná . Syndromy zapisujeme ve formě soustavy nelineárních rovnic v explicitní podobě: $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}}

Označte lokátorem -té chyby a — velikostí chyby, . V tomto případě jsou všechny různé, protože pořadí prvku je , a proto, když je známo , může být definováno jako . $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}}

Pojďme sestavit polynom lokátorů chyb :

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

Kořeny tohoto polynomu jsou prvky inverzní k lokátorům chyb. Vynásobte obě strany tohoto polynomu číslem . Výsledná rovnost bude platná pro : ${\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}.

Pokud zde dosadíme , dostaneme rovnost , která platí pro každého a pro všechny : ${\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}.

Pro každý tedy můžete napsat svou vlastní rovnost. Pokud se sečtou , dostaneme rovnost, která platí pro každý z nich : $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}\součet _{l =1}^{t}Y_{l}X_{l}^{\vartheta +1}+\ldots +\Lambda _{1}\sum _{l=1}^{t}Y_{l}X_{ l}^{\vartheta +t-1}+\součet _{l=1}^{t}Y_{l}X_{l}^{\vartheta +t}.

Protože (to znamená, že se mění ve stejných mezích jako dříve), je soustava rovnic pro syndromy transformována na soustavu lineárních rovnic : $S_{j+p}=\součet _{l=1}^{t}Y_{l}X_{l}^{l_{0}+j+p-1}=\součet _{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},\\\vtečky \\S_{t}\Lambda _{t}+S_{t+1}\Lambda _{t-1}+\ldots +S_{2t-1}\Lambda _{ 1}=-S_{2t},\end{cases}}

nebo ve formě matrice,

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

kde

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

Pokud je počet chyb skutečně roven , pak je tento systém řešitelný a lze najít hodnoty koeficientů . Pokud je číslo , pak se determinant matice bude rovnat . To je známka toho, že počet chyb je menší . Proto je nutné sestavit systém za předpokladu, že počet chyb se rovná , vypočítat determinant nové matice atd., dokud nezjistíme skutečný počet chyb. $t$ ${\displaystyle \Lambda _{1},\ldots ,\Lambda _{t))$ $u<t$ $S^{{(t)}}$ $0$ $t$ $t-1$ $S^{{(t-1)}}$

Hledat Chen

Po vyřešení klíčové soustavy rovnic jsou získány koeficienty polynomu lokátoru chyb. Jeho kořeny (prvky inverzní k lokátorům chyb) lze najít jednoduchým opakováním všech prvků pole . K nim najděte prvky, které jsou inverzní k násobení - to jsou lokátory chyb . Tento proces lze snadno implementovat do hardwaru. $GF(q^{m})$ $X_{k},\ k=1,\ldots ,u$

Forneyho algoritmus

Pomocí lokátorů můžete najít chybové pozice ( ) a chybové hodnoty ze systému pro syndromy přijetím . Dekódování dokončeno. ${\displaystyle i_{k}=\log _{\beta }X_{k))$ $Y_{k}$ $t=u$

Viz také

Poznámky

↑ Sagalovich, 2007 , str. 175-176.
↑ Sagalovich, 2007 , str. 176.
↑ Sagalovich, 2007 , str. 168.
↑ Umění kódování opravující chyby Archivováno 1. dubna 2013 na Wayback Machine , str. 91.
↑ Sagalovich, 2007 , str. 200

Literatura

Blahut R. Teorie a praxe kódů kontroly chyb. — M .: Mir , 1986. — 576 s.
Peterson W, Weldon E. Kódy pro opravu chyb . - M .: Mir, 1976. - S. 596 .
Sagalovich Yu.L. Úvod do algebraických kódů - M .: MIPT , 2007. - 262 s. — ISBN 978-5-7417-0191-1
Morelos-Zaragoza R. Umění kódování opravující chyby. Metody, algoritmy, aplikace. - M. : Technosfera, 2005. - 320 s. — ISBN 5-94836-035-0 .