Cesko.wiki BCH kód
Author
Albert FloresV teorii kódování tvoří BCH kódy skupinu cyklických samoopravných kódů, které jsou konstruovány pomocí konečných těles. BCH kódy byly vynalezeny v roce 1959 Hocquenghemem, a nezávisle v roce 1960 Bosem a Ray-Chaudhurim. Zkratka BCH je tvořena počátečními jmény těchto objevitelů.
Klíčovou vlastností BCH kódů je možnost v průběhu návrhu kódu přesně kontrolovat počet opravitelných chyb ve výsledném kódu. Další výhodou BCH kódů je jednoduchost jejich dekódování pomocí algebraických metod známých jako syndrome decoding. +more To zjednodušuje návrh dekodérů s použitím malého výkonnostně slabého hardwaru.
BCH kódy jsou používány například v satelitní komunikaci, CD a DVD přehrávačích, pevných discích, flash discích a QR kódech.
Konstrukce
Nechť A je GF(qa). BCH kód kóduje slova pevné délky k nad vstupní abecedou A tak, že kódové slovo předem dané délky n vznikne doplněním vstupního slova dalšími znaky nad abecedou A. +more Konstrukce kódu je založena na nadtělese B GF(qb) tělesa A v němž existuje prvek α jehož řád je alespoň délka n kódových slov, tedy a|b a ord(α)≥n. Nechť c a d jsou celá čísla. Kódová slova jsou taková slova v1v2…vn, kde polynom v1xn-1+v2xn-2+…+vn-1x1+vn má kořeny αc, αc+1, …, αc+d-2.
Při konstrukci je nalezen polynom g(x) nejmenšího stupně, který má uvedené kořeny. Tomuto polynomu říkáme generující polynom. +more Je-li m jeho stupeň, pak je takto možno kódovat slova délky k=n-m. Kódové slovo vznikne tak, že zjistíme zbytek R(x) při dělení polynomu V(x)=v1xn-1+v2xn-2+…+vkxm polynomem P(x).
Kódové slovo vznikne z polynomu V(x)-R(x), tak že vi bude tvořeno koeficientem u xn-i.
Konstrukce garantuje Hammingovu vzdálenost kódových slov alespoň d. Užitečnou vlastností BCH kódů je, že zpráva je pouze doplněna zabezpečovacím podslovem, ale začátek zprávy je nezměněn.
Speciální případy BCH kódů
BCH kód s c=1 je nazýván doslovný kód. * BCH kód s n=qb/a−1 je nazýván primitivní kód. +more * BCH kód s nb/a−1 je nazýván zkrácený kód. * BCH kód s A=Zq je nazýván základní BCH kód. * BCH kód s A=Z2 je nazýván binární BCH kód. * BCH kód s A=B je nazýván Reed Solomonův kód.
Běžně jsou používány primitivní doslovné základní BCH kódy.
Může se stát, že pro vhodnou volbu c dostaneme řád generujícího polynomu menší než při volbě c=1. Taková volba pak přináší více prostoru pro data (a kód přestává být doslovný).
Pro Reedovy-Solomonovy kódy jsou všechny volby c stejně dobré, protože minimální polynom pro každé αi je prvního řádu. Používány jsou především Reed Solomonovy kódy s c=0.
Kódy s b>a>1 nejsou pravděpodobně používány.
Příklad základních primitivních doslovných BCH kódů
Nechť q=2 a b=4 (tedy n=15). Uvažujme různé hodnoty d.
Existuje primitivní prvek \alpha\in GF(16) splňující \alpha^4+\alpha+1=0 (*), jeho minimální polynom nad Z_2 je :m_1(x) = x^4+x+1.
Poznamenejme, že v GF(2^4), platí (a+b)^2 = a^2 + ab + ab + b^2 = a^2 + b^2, proto m_1(\alpha^2) = m_1(\alpha)^2 = 0.
Tudíž \alpha^2 je kořen polynomu m_1(x), a :m_2(x) = m_1(x) = x^4+x+1.
Abychom spočítali m_3(x), poznamenejme, že opakovanou aplikací (*), dostáváme následující rovnice: * 1 = 0\alpha^3 + 0\alpha^2 + 0\alpha + 1 * \alpha^3 = 1\alpha^3 + 0\alpha^2 + 0\alpha + 0 * \alpha^6 = 1\alpha^3 + 1\alpha^2 + 0\alpha + 0 * \alpha^9 = 1\alpha^3 + 0\alpha^2 + 1\alpha + 0 * \alpha^{12} = 1\alpha^3 + 1\alpha^2 + 1\alpha + 1
Pět pravých stran délky čtyři musí být lineárně závislých a tak najdeme lineární závislost \alpha^{12}+\alpha^9+\alpha^6+\alpha^3+1=0.
Protože neexistuje závislost nižšího řádu, je minimálním polynomem pro \alpha^3 polynom :m_3(x) = x^4+x^3+x^2+x+1.
Budeme-li pokračovat obdobně, získáme
:m_4(x) = m_2(x) = m_1(x) = x^4+x+1,\, :m_5(x) = x^2+x+1,\, :m_6(x) = m_3(x) = x^4+x^3+x^2+x+1,\, :m_7(x) = x^4+x^3+1.\,
BCH kódy s d=1,2,3 mají generující polynom
:g(x) = m_1(x) = x^4+x+1.\,
Kód má minimální Hammingovu vzdálenost alespoň 3 a opravuje nejvýš 1 chybu. Protože generující polynom je stupně 4, má tento kód 11 datových bitů a 4 zabezpečovací bity.
BCH kódy s d=4,5 mají generující polynom
:g(x) = {\rm nsn}(m_1(x),m_3(x)) = (x^4+x+1)(x^4+x^3+x^2+x+1) = x^8+x^7+x^6+x^4+1.\,
Jeho minimální Hammingova vzdálenost je alespoň 5 a opravuje nejvýš 2 chyby. Protože generující polynom je stupně 8, má tento kód 7 datových bitů a 8 zabezpečovacích bitů.
BCH kódy s d=6,7 mají generující polynom
: \begin{align} g(x) & {} = {\rm nsn}(m_1(x),m_3(x),m_5(x)) \\ & {} = (x^4+x+1)(x^4+x^3+x^2+x+1)(x^2+x+1) \\ & {} = x^{10}+x^8+x^5+x^4+x^2+x+1. \end{align}
Má minimální Hammingovu vzdálenost alespoň 7 a opravuje nejvýš 3 chyby. Tento kód má 5 datových bitů a 10 zabezpečovacích bitů.
BCH kód s d\ge8 má generující polynom
: \begin{align} g(x) & {} = {\rm nsn}(m_1(x),m_3(x),m_5(x),m_7(x)) \\ & {} = (x^4+x+1)(x^4+x^3+x^2+x+1)(x^2+x+1)(x^4+x^3+1) \\ & {} = x^{14}+x^{13}+x^{12}+\cdots+x^2+x+1. \end{align}
Kód má minimální Hammingovu vzdálenost 15 a opravuje nejvýš 7 chyb. Má 1 datový bit a 14 zabezpečovacích bitů. +more Tento kód má tedy jen dvě kódová slova: 000000000000000 a 111111111111111.
Vlastnosti
1. Generující polynom BCH kódu má stupeň nejvýš (d-1)(b/a). Navíc, pokud A=Z_2 a c=1, pak generující polynom má stupeň nejvýš db/2a.
:Důkaz: každý minimální polynom m_i(x) má stupeň nejvýš b/a. Proto minimální společný násobek d-1 z nich má stupeň nejvýš (d-1)(b/a). +more Navíc, pokud A=Z_2, pak m_i(x) = m_{2i}(x) pro každé i. Proto, g(x) je nejmenší společný násobek nejvýš d/2 minimálních polynomů m_i(x) pro liché indexy i, každý z nich je stupně nejvýš b/a.
2. BCH kód má minimální Hammingovu vzdálenost alespoň d.
Důkaz: Předpokládejme, že p(x) je kód (jemu odpovídající polynom) s méně než d nenulovými koeficienty. Potom nechť
:p(x) = b_1x^{k_1} + \cdots + b_{d-1}x^{k_{d-1}},\text{ kde }k_1
Připomeňme, že \alpha^c,\ldots,\alpha^{c+d-2} jsou kořeny g(x), tudíž i jeho násobku p(x). Z toho plyne, že b_1,\ldots,b_{d-1} splňuje následující rovnice pro i=c,\ldots,c+d-2: :p(\alpha^i) = b_1\alpha^{ik_1} + b_2\alpha^{ik_2} + \cdots + b_{d-1}\alpha^{ik_{d-1}} = 0.
V maticovém tvaru dostáváme :\begin{bmatrix} \alpha^{ck_1} & \alpha^{ck_2} & \cdots & \alpha^{ck_{d-1}} \\ \alpha^{(c+1)k_1} & \alpha^{(c+1)k_2} & \cdots & \alpha^{(c+1)k_{d-1}} \\ \vdots & \vdots && \vdots \\ \alpha^{(c+d-2)k_1} & \alpha^{(c+d-2)k_2} & \cdots & \alpha^{(c+d-2)k_{d-1}} \\ \end{bmatrix} \begin{bmatrix} b_1 \\ b_2 \\ \vdots \\ b_{d-1} \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ \vdots \\ 0 \end{bmatrix}.
Determinant této matice je roven :\left(\prod_{i=1}^{d-1}\alpha^{ck_i}\right)\det\begin{pmatrix} 1 & 1 & \cdots & 1 \\ \alpha^{k_1} & \alpha^{k_2} & \cdots & \alpha^{k_{d-1}} \\ \vdots & \vdots && \vdots \\ \alpha^{(d-2)k_1} & \alpha^{(d-2)k_2} & \cdots & \alpha^{(d-2)k_{d-1}} \\ \end{pmatrix} = \left(\prod_{i=1}^{d-1}\alpha^{ck_i}\right) \det(V).
Matice V je Vandermondova matice, a její determinant je :\det(V) = \prod_{1\le i což je nenulové. Odtud vyplývá, že b_1,\ldots,b_{d-1}=0, a tudíž p(x)=0.
3. Kód, kde délka kódových slov n je rovna řádu prvku α je cyklický. Speciálně pak každý primitivní kód je cyklický.
Důkaz: Kód generovaný pomocí polynomů délky n je cyklický právě když generující polynom dělí x^n-1. Protože g(x) je minimální polynom s kořeny \alpha^c,\ldots,\alpha^{c+d-2}, stačí zkontrolovat, že každé z \alpha^c,\ldots,\alpha^{c+d-2} je kořen polynomu x^n-1. +more To plyne přímo z toho, že \alpha je podle definice ntá odmocnina z jedné.
Dekódování
Existuje mnoho algoritmů pro dekódování BCH kódů. Nejběžnější používají následující schéma: # Spočtěme pro přijaté slovo syndromy sj. +more # Ze syndromů určeme počet chyb t a polynom pro lokalizaci chyb Λ(x). # Nalezněme kořeny polynomu pro lokalizaci chyb xj a jejich logaritmy -ij, tak že α−ij=xj. # Spočtěme chybové hodnoty ei v pozicích ij. # Opravme chyby.
V průběhu algoritmu může dekódovací algoritmus určit, že přijaté slovo obsahuje příliš mnoho chyb a nemůže být opraveno. Například, pokud vhodná hodnota pro t není nalezena, korekce selže. +more V případě zkráceného kódu, může být vypočtena pozice chyby mimo kódové slovo. Pokud přijaté slovo má více chyb než kód dokáže opravit, dekodér může vrátit zdánlivě korektní zprávu, která se liší od zprávy odeslané.
Pokud jsou některá písmena zprávy nečitelná, můžeme jejich pozici považovat za pozici chyby. Nalezení chyby na neznámé pozici vyžaduje stejně informací jako opravení dvou chyb na známých pozicích.
Výpočet syndromů
Přijaté slovo R je součet korektního kódového slova C a neznámého chybového slova E. Hodnoty syndromů jsou získány dosazením hodnot \alpha^c,\ldots,\alpha^{c+d-2} do R vnímaného jakožto polynom. +more Proto jsou syndromy :s_{j} = R(\alpha^{j}) = C(\alpha^{j}) + E(\alpha^{j}), pro j od c do c+d-2. Protože \alpha^{j} jsou kořeny g(x), jehož je C(x) násobek, C(\alpha^{j}) = 0. Zkoumání hodnot syndromů proto izoluje chybový vektor, takže můžeme začít v jeho hledání.
Pokud v přenosu nevznikly chyby, je s_j = 0 pro každé j. V takovém případě dekódování končí.
Výpočet polynomu pro lokalizaci chyb
Pokud jsou některé syndromy nenulové, jsou v přijaté zprávě chyby. Dekodér musí zjistit, kolik jich je a kde se vyskytují.
Předpokládejme, že
:E(x) = e_1 x^{i_1} + e_2 x^{i_2} + \cdots + e_v x^{i_v} \, . Není zřejmé, jak začít řešit rovnice s neznámými e_k a i_k vysvětlující syndromy.
Prvním krokem je nalezení polynomu pro lokalizaci chyb :\Lambda(x)=\prod_{j=1}^v (x\alpha^{i_j}-1) kompatibilního se spočtenými syndromy a s minimálním možným v.
Dva populární algoritmy pro tuto úlohu jsou: # Algoritmus Peterson-Gorenstein-Zierler # Algoritmus Berlekamp-Massey
Cílem obou algoritmů je nalézt : \Lambda(x) = \lambda_0 + \lambda_1 x + \lambda_2 x^2 + \cdots + \lambda_v x^v takové, aby pro každé j od c do c+d-2-v platilo : \sum_{i=0}^v \lambda_i s_{j+v-i} = 0. Navíc požadujeme \lambda_0 = 1.
Zdůvodnění rovnic pro výpočet polynomu pro lokalizaci chyb
Vzhledem k tomu, že \alpha^{-i_k} je kořenem polynomu \Lambda(x), musí být : 0 = \sum_{i=0}^v \lambda_i \alpha^{-i\cdot i_k}. Po pronásobení e_k\alpha^{(j+v)i_k} dostáváme : 0 = \sum_{i=0}^v \lambda_i e_k\alpha^{(j+v-i)i_k}. +more Po sečtení přes jednotlivé chyby pak : 0 = \sum_{i=0}^v \lambda_i \sum_{k=0}^v e_k\alpha^{(j+v-i)i_k}, neboli : 0 = \sum_{i=0}^v \lambda_i s_{j+v-i}.
Algoritmus Peterson-Gorenstein-Zierler
Algoritmus řeší soustavu rovnic hrubou silou. Nachází jediné v a Λ, které může vyhovovat, správně by měl nakonec zkontrolovat, zda skutečně vyhovují i pro ve výpočtu nepoužité syndromy.
Začněme s v=[t=(d-1)/2].
* Nejprve sestavme matici ::S_{v \times v}=\begin{bmatrix}s_c&s_{c+1}&\dots&s_{c+v-1}\\ s_{c+1}&s_{c+2}&\dots&s_{c+v}\\ \vdots&\vdots&\ddots&\vdots\\ s_{c+v-1}&s_{c+v}&\dots&s_{c+2v-2}\end{bmatrix},
* pak vektor c_{v \times 1} ::C_{v \times 1}=\begin{bmatrix}s_{c+v}\\ s_{c+v+1}\\ \vdots\\ s_{c+2v-1}\end{bmatrix}.
* Nechť neznámé koeficienty polynomu \Lambda jsou ::\Lambda_{v \times 1} = \begin{bmatrix}\lambda_{v}\\ \lambda_{v-1}\\ \vdots\\ \lambda_{1}\end{bmatrix}.
* Pokud má S_{v \times v} nenulový determinant, pak maticová rovnice ::S_{v \times v} \Lambda_{v \times 1} = -C_{v \times 1\,}
:má řešení. Nalezněme tedy koeficienty polynomu \Lambda a skončeme.
* Jinak pokud v = 0, deklarujme nulový polynom lokalizace chyb a skončeme. * Jinak snižme v o 1 a vraťme se k sestavení matice S_{v\times v}.
V případě v větším než je počet chyb (můžeme dodefinovat nadbytečná e_k nulou). Pak ::S_{v\times v} =\begin{bmatrix}\alpha^{0i_1}&\alpha^{0i_2}&\dots&\alpha^{0i_v}\\ \alpha^{1i_1}&\alpha^{1i_2}&\dots&\alpha^{1i_v}\\ \vdots&\vdots&\ddots&\vdots\\ \alpha^{(v-1)i_1}&\alpha^{(v-1)i_2}&\dots&\alpha^{(v-1)i_v}\end{bmatrix} \begin{bmatrix}e_1\alpha^{ci_1}&0&\dots&0\\ 0&e_2\alpha^{ci_2}&\dots&0\\ \vdots&\vdots&\ddots&\vdots\\ 0&0&\dots&e_v\alpha^{ci_v}\end{bmatrix} \begin{bmatrix}\alpha^{0i_1}&\alpha^{1i_1}&\dots&\alpha^{(v-1)i_1}\\ \alpha^{0i_2}&\alpha^{1i_2}&\dots&\alpha^{(v-1)i_2}\\ \vdots&\vdots&\ddots&\vdots\\ \alpha^{0i_v}&\alpha^{1i_v}&\dots&\alpha^{(v-1)i_v}\end{bmatrix},
a determinant je nulový, dokud není v minimální možné.
Algoritmus Berlekamp-Massey
Algoritmus udržuje Λ odpovídající počátečnímu úseku posloupnosti syndromů. Postupně prodlužuje délku úseku a koriguje Λ.
Nalezení kořenů polynomu pro lokalizaci chyb
Není znám algoritmus, který by hledal kořeny jinak než hrubou silou postupným dosazováním prvků tělesa B. Algoritmus Chien search optimalizuje výpočet tím, že minimalizuje násobení proměnnými na úkor stejného počtu násobení konstantami.
Výpočet chybových hodnot
Jakmile jsou známy polohy chyb, zbývá určit velikosti chyb na těchto místech. Odečtením nalezených velikostí chyb dostaneme z přijatého slova kódové slovo.
V případě binárního kódu a původně neznámé polohy chyby stačí negovat příslušný bit. V případě nečitelných dat je pro účely hledání chyby nahrazeno nečitelné písmeno nulou a pokračujeme jako v obecném případě. +more V obecném případě mohou být velikosti chyb e_j určeny řešením soustavy lineárních rovnic.
:s_c = e_1 \alpha^{c\,i_1} + e_2 \alpha^{c\,i_2} + \ldots :s_{c+1} = e_1 \alpha^{(c + 1)\,i_1} + e_2 \alpha^{(c + 1)\,i_2} + \ldots :…
Forneyův vzorec
Existuje ale efektivnější metoda známá jako Forneyův vzorec.
Nechť S(x)=\sum_{i=0}^{d-2} s_{c+i}x^i. Nechť v\le d-1, \lambda_0\neq 0 a \Lambda(x)=\sum_{i=0}^v\lambda_ix^i=\lambda_0\cdot\prod_{k=0}^{v} (\alpha^{-i_k}x-1).
Nechť \Omega(x) = S(x)\,\Lambda(x) \pmod{x^{d-1}} je polynom vyhodnocující chyby.
Nechť \Lambda'(x) = \Sigma_{i=1}^v i \cdot \lambda_i x^{i-1}, kde i\cdot x zde značí \textstyle\sum_{k=1}^i x místo násobení v příslušném tělese.
Pokud je možno syndromy vysvětlit chybovým slovem, které může být nenulové jedině na pozicích i_k, pak jsou velikosti chyb :e_k=-{\alpha^{i_k}\Omega(\alpha^{-i_k})\over \alpha^{c\cdot i_k}\Lambda'(\alpha^{-i_k})}.
Pro doslovné kódy, c = 1, takže můžeme výraz vykrátit na: :e_k=-{\Omega(\alpha^{-i_k})\over \Lambda'(\alpha^{-i_k})}.
Zdůvodnění Forneyova vzorce
Algoritmus je založen na Lagrangeově interpolaci a technikách vytvořujících funkcí.
Prozkoumejme S(x)\Lambda(x). Pro jednoduchost dodefinujme \lambda_k=0 pro k>v a s_k=0 pro k>c+d-2.
Pak S(x)\Lambda(x)=\sum_{j=0}^{\infty}\sum_{i=0}^j s_{j-i+c}\lambda_i x^j. Vztah \sum_{i=0}^v s_{v-i+j}\lambda_i=0 jsme již odvodili dříve, takže víme pro důkaz nepodstatnou informaci, že koeficienty u x^j jsou 0 pro v\le j\le d-2.
Zkoumejme dál význam jednotlivých koeficientů: :S(x)=\sum_{i=0}^{d-2}\sum_{j=1}^v e_j\alpha^{(c+i)\cdot i_j} x^i=\sum_{j=1}^v e_j\alpha^{c\,i_j}\sum_{i=0}^{d-2}(\alpha^{i_j})^i x^i = \sum_{j=1}^v e_j\alpha^{c\,i_j} {(x\alpha^{i_j})^{d-1}-1\over x\alpha^{i_j}-1},
:S(x)\Lambda(x)=S(x)\lambda_0\prod_{\ell=1}^v (\alpha^{i_\ell}x-1)=\lambda_0\sum_{j=1}^v e_j\alpha^{c\,i_j} {(x\alpha^{i_j})^{d-1}-1\over x\alpha^{i_j}-1}\prod_{\ell=1}^v (\alpha^{i_\ell}x-1). Můžeme získat následující formu polynomu : :S(x)\Lambda(x)=\lambda_0\sum_{j=1}^v e_j\alpha^{c\,i_j} ((x\alpha^{i_j})^{d-1}-1)\prod_{\ell\in\{1,\dots,v\}\setminus\{j\}} (\alpha^{i_\ell}x-1). +more Chceme spočítat neznámé e_j, a můžeme zjednodušit kontext odstraněním (x\alpha^{i_j})^{d-1} členů. To vede k definici polynomu vyhodnocujícího chyby :\Omega(x) = S(x)\,\Lambda(x) \pmod{x^{d-1}}.
Díky předpokladu v\le d-1 dostáváme :\Omega(x) = -\lambda_0\sum_{j=1}^v e_j\alpha^{c\,i_j} \prod_{\ell\in\{1,\dots,v\}\setminus\{j\}} (\alpha^{i_\ell}x-1).
Zaměřme se na \Omega(\alpha^{-i_k}). Díky \Lambda (trik Lagrangeovy interpolace) suma degeneruje na jediný sčítanec :\Omega(\alpha^{-i_k})=-\lambda_0e_k\alpha^{c\cdot i_k}\prod_{\ell\in\{1,\dots,v\}\setminus\{k\}}(\alpha^{i_\ell}\alpha^{-i_k}-1) . +more K nalezení e_k již stačí zbavit se nadbytečného součinu. Můžeme jej spočítat přímo z již známých kořenů \alpha^{-i_j} polynomu \Lambda, ale můžeme využít jednodušší výraz.
Protože formální derivace \Lambda'(x)=\lambda_0\sum_{j=1}^v \alpha^{i_j}\prod_{\ell\in\{1,\dots,v\}\setminus\{j\}}(\alpha^{i_\ell}x-1).
Získáváme v bodě \alpha^{-i_k} opět jediný sčítanec :\Lambda'(\alpha^{-i_k})= \lambda_0\alpha^{i_k}\prod_{\ell\in\{1,\dots,v\}\setminus\{k\}}(\alpha^{i_\ell}\alpha^{-i_k}-1).
Takže konečně :e_k=-{\alpha^{i_k}\Omega(\alpha^{-i_k})\over \alpha^{c\cdot i_k}\Lambda'(\alpha^{-i_k})}
Tato formule je zjednodušením v případě, kdy formální derivaci \Lambda počítáme z tvaru \Lambda(x)=\sum_{i=1}^v\lambda_ix^i pomocí :\Lambda'(x) = \Sigma_{i=1}^v i \cdot \lambda_i x^{i-1},
kde i\cdot x značí \textstyle\sum_{k=1}^i x místo násobení v příslušném tělese.
Dekódování založené na rozšířeném Euklidově algoritmu
Celý proces hledání lokalizačního polynomu Λ i hledání velikosti chyb je možno založit na # Rozšířeném Eukleidově algoritmu. Navíc přitom můžeme opravovat i nečitelné znaky na neznámých pozicích.
Nechť k_1, . ,k_k jsou pozice nečitelných znaků. +more Sestavíme tomu odpovídající polynom \Gamma(x)=\prod_{i=1}^k(x\alpha^{k_i}-1). Dodefinujme nečitelná místa nulou a spočtěme syndromy. Tak jak jsme si popsali u Forneyova vzorce nechť S(x)=\sum_{i=0}^{d-2}s_{c+i}x^i.
Spustíme rozšířený Euklidův algoritmus na hledání nejmenšího společného dělitele polynomů S(x)\Gamma(x) a x^{d-1}. Naším cílem ale nebude nalézt nejmenšího společného dělitele, ale polynom r(x) stupně nejvýš \lfloor (d+k-3)/2\rfloor a polynomy a(x), b(x) tak, aby r(x)=a(x)S(x)\Gamma(x)+b(x)x^{d-1}. +more Nízký stupeň polynomu r(x) zajistí, že pro a(x) budou platit zobecněné (o polynom opravující nečitelné znaky) definiční vztahy které jsme kladli na \Lambda.
Při definici \Xi(x)=a(x)\Gamma(x) a použití \Xi na místě \Lambda ve Fourney algoritmu pak dostaneme odhad velikosti chyb.
Hlavní výhodou algoritmu je, že zároveň spočítá ve Forneyově vzorci potřebné \Omega(x)=S(x)\Xi(x)\bmod x^{d-1}=r(x).
Zdůvodnění nejen dekódování založeném na rozšířeném Euklidově algoritmu
Naší snahou je nalézt kódové slovo, které se od přijatého slova na čitelných pozicích liší co nejméně. Při vyjádření přijatého slova jako součtu nejbližšího kódového slova a chybového slova tak hledáme chybové slovo s nejmenším počtem nenulových souřadnic na čitelných pozicích. +more Syndrom s_i klade na chybové slovo podmínku s_i=\sum_{j=0}^{n-1}e_j\alpha^{ij}. Tyto podmínky můžeme zapisovat samostatně, nebo můžeme vytvořit polynom S(x)=\sum_{i=0}^{d-2}s_{c+i}x^i a klást podmínky na koeficienty u mocnin 0 až d-2. S(x){\textstyle{\{0,\ldots,\,d-2\}\atop =}}E(x)=\sum_{i=0}^{d-2}\sum_{j=0}^{n-1}e_j\alpha^{ij}\alpha^{cj}x^i.
Víme-li, že na pozici k_1 je nečitelný znak, můžeme množinu syndromů \{s_c,\ldots,s_{c+d-2}\} nahradit množinou syndromů \{t_c,\ldots,t_{c+d-3}\} definovaných vztahem t_i=\alpha^{k_1}s_i-s_{i+1}. Pokud platí pro chybové slovo podmínky kladené množinou syndromů \{s_c,\ldots,s_{c+d-2}\}, pak t_i=\alpha^{k_1}s_i-s_{i+1}=\alpha^{k_1}\sum_{j=0}^{n-1}e_j\alpha^{ij}-\sum_{j=0}^{n-1}e_j\alpha^j\alpha^{ij}=\sum_{j=0}^{n-1}e_j(\alpha^{k_1}-\alpha^j)\alpha^{ij}. +more Nová množina syndromů má vůči chybovému vektoru f_j=e_j(\alpha^{k_1}-\alpha^j) stejný vztah jako měla původní množina syndromů vůči chybovému vektoru e_j. Všimněme si, že s výjimkou souřadnice k_1, kde je f_{k_1}=0, je f_j nenulové, právě když je e_j nenulové. Co se týče hledání pozic chyb, můžeme proto takto upravit množinu syndromů postupným zohledněním pozic neznámých znaků. Výsledná množina syndromů bude kratší o počet k nečitelných znaků.
Při formulaci v řeči polynomů nám náhrada množiny syndromů \{s_c,\ldots,s_{c+d-2}\} množinou syndromů \{t_c,\ldots,t_{c+d-3}\} vede k T(x)=\sum_{i=0}^{d-3}t_{c+i}x^i=\alpha^{k_1}\sum_{i=0}^{d-3}s_{c+i}x^i-\sum_{i=1}^{d-2}s_{c+i}x^{i-1}. Odtud xT(x){\textstyle{\{1,\ldots,\,d-2\}\atop =}}(x\alpha^{k_1}-1)S(x).
Po nahrazení S(x) pomocí S(x)\Gamma(x) pak proto budeme hledat shodu u koeficientů k,\ldots,d-2.
Obdobně jako odstraňování vlivu nečitelných znaků můžeme vnímat i hledání chybných pozic. Pokud najdeme v souřadnic tak, že odstranění jejich vlivu povede k tomu, že zbylé syndromy budou nulové, existuje chybový vektor jenž má nenulové hodnoty pouze v těchto souřadnicích. +more Pokud označíme \Lambda(x) polynom odstraňující vliv těchto souřadnic, dostaneme S(x)\Gamma(x)\Lambda(x){\textstyle{\{k+v,\ldots,\,d-2\}\atop =}}0.
V Euklidově algoritmu se snažíme odstranit nejvýš (d-1-k)/2 chyb (na čitelných místech), protože při větším počtu chyb může být více kódových slov od přijatého slova stejně daleko. Proto musí pro hledané \Lambda(x) nastat ve výše uvedeném vztahu rovnost u všech souřadnic počínaje k+\lfloor(d-1-k)/2\rfloor.
Ve Forney vzorci (pro nelezení velikosti chyb) nezáleželo na tom, zda je \Lambda(x) vynásobena nenulovou konstantou, proto je podmínka \lambda_0=1 zbytečná. Může se stát, že Euklidův algoritmus najde \Lambda(x) stupně většího než (d-1-k)/2, který má tolik různých kořenů, jako je jeho stupeň, a pomocí Forney algoritmu bude možno opravit chyby v polohách všech jeho kořenů, přesto opravovat takto nalezené chyby je nebezpečné. +more Obvykle při nalezení \Lambda(x) většího stupně odmítáme chyby opravovat. Stejně tak oprava chyb selže, pokud má \Lambda(x) vícenásobné kořeny či jejich počet neodpovídá stupni \Lambda(x). Selhání také může detekovat to, když Forney vzorec vrátí chybu z rozdílu těles B\setminus A.
Příklady dekódování
Dekódování binárního kódu bez nečitelných znaků
Nechť d=7 a používáme dříve uvedený kód s g(x) = x^{10} + x^8 + x^5 + x^4 + x^2 + x + 1 v GF(24). (Tento generátor je použit v QR kódech. +more) Nechť přenášená zpráva je.
, nebo jako polynom M(x) = x^4 + x^3 + x + 1. Zabezpečovací symboly jsou spočteny dělením x^{10} M(x) polynomem g(x) a přičtením (odečtením) zbytku x^9 + x^4 + x^2 neboli
k x^{10} M(x). Přidáním ke zprávě tak dostáváme přenášené kódové slovo
.
Předpokládejme, že dva bity byly poškozeny v průběhu přenosu, takže přijaté slovo je [ 1 0 1 1 1 0 0 0 1 0 1 0 0 ]. Jakožto polynom tedy: :R(x) = C(x) + x^{13} + x^5 = x^{14} + x^{11} + x^{10} + x^9 + x^5 + x^4 + x^2 Abychom chyby opravili, spočteme nejprve syndromy. +more Přitom \alpha = 0010, dostaneme s_1 = R(\alpha^1) = 1011, s_2 = 1001, s_3 = 1011, s_4 = 1101, s_5 = 0001 a s_6 = 1001. K zápisu bychom mohli používat hexadecimální číslice, ale držme se v tomto úvodním příkladu dvojkové soustavy.
Následně aplikujme Petersonův algoritmus. :\left [ S_{3 \times 3} | C_{3 \times 1} \right ] = \begin{bmatrix}s_1&s_2&s_3&s_4\\ s_2&s_3&s_4&s_5\\ s_3&s_4&s_5&s_6\end{bmatrix} = \begin{bmatrix}1011&1001&1011&1101\\ 1001&1011&1101&0001\\ 1011&1101&0001&1001\end{bmatrix} \Rightarrow \begin{bmatrix}0001&0000&1000&0111\\ 0000&0001&1011&0001\\ 0000&0000&0000&0000\end{bmatrix} Protože je singulární, což není překvapením, protože slovo obsahuje pouze dvě chyby. +more Nyní levý horní roh matice je identický s [S2×2 C2×1], což vede k řešení \lambda_2 = 1000, \lambda_1 = 1011. Výsledný polynom pro lokalizaci chyb je \Lambda(x) = 1000 x^2 + 1011 x + 0001. Polynom má kořeny 0100 = \alpha^{-13} a 0111 = \alpha^{-5}. Exponenty \alpha odpovídají pozicím chyb. Nemusíme v tomto případě počítat chybové hodnoty, protože jedinou možnou hodnotou je hodnota 1.
Dekódování s nečitelnými znaky a maximálním opravitelným počtem chyb
Předpokládejme nyní, stejný případ, ale přijaté slovo má dva nečitelné znaky [ 1 0 . 1 1 . +more 0 0 1 0 1 0 0 ]. Nahradíme nečitelné znaky (např. ) nulami, vytvořme polynom potlačující vliv nečitelných znaků \Gamma(x)=(\alpha^8x-1)(\alpha^{11}x-1). Najděme syndromy s_1=\alpha^{-7}, s_2=\alpha^{1}, s_3=\alpha^{4}, s_4=\alpha^{2}, s_5=\alpha^{5} a s_6=\alpha^{-7}. (Používáme logaritmické vyjádření, které je vzhledem k isomorfismu GF(24) nezávislé na reprezentaci pro sčítání. Možné reprezentace jednotlivých mocnin jsou stejně jako v předchozím případě hexadecimálními číslicemi 1, 2, 4, 8, 3, 6, C, B, 5, A, 7, E, F, D, 9 se sčítáním založeném na bitovém xor. ) Vytvořme polynom syndromů S(x)=\alpha^{-7}+\alpha^{1}x+\alpha^{4}x^2+\alpha^{2}x^3+\alpha^{5}x^4+\alpha^{-7}x^5, spočtěme S(x)\Gamma(x)=\alpha^{-7}+\alpha^{4}x+\alpha^{-1}x^2+\alpha^{6}x^3+\alpha^{-1}x^4+\alpha^{5}x^5+\alpha^{7}x^6+\alpha^{-3}x^7.
Spusťme rozšířený euklidův algoritmus:
\begin{pmatrix}S(x)\Gamma(x)\\ x^6\end{pmatrix}= \begin{pmatrix}\alpha^{-7}+\alpha^{4}x+\alpha^{-1}x^2+\alpha^{6}x^3+\alpha^{-1}x^4+\alpha^{5}x^5+\alpha^{7}x^6+\alpha^{-3}x^7\\ x^6\end{pmatrix}=
\begin{pmatrix}\alpha^{7}+\alpha^{-3}x&1\\ 1&0\end{pmatrix} \begin{pmatrix}x^6\\ \alpha^{-7}+\alpha^{4}x+\alpha^{-1}x^2+\alpha^{6}x^3+\alpha^{-1}x^4+\alpha^{5}x^5+(\alpha^{7}+\alpha^{7})x^6+(\alpha^{-3}+\alpha^{-3})x^7\end{pmatrix}=
\begin{pmatrix}\alpha^{7}+\alpha^{-3}x&1\\ 1&0\end{pmatrix} \begin{pmatrix}\alpha^4+\alpha^{-5}x&1\\ 1&0\end{pmatrix} \begin{pmatrix} \alpha^{-7}+\alpha^{4}x+\alpha^{-1}x^2+\alpha^{6}x^3+\alpha^{-1}x^4+\alpha^{5}x^5\\ \alpha^{-3}+(\alpha^{-7}+\alpha^{3})x+(\alpha^{3}+\alpha^{-1})x^2+\\ (\alpha^{-5}+\alpha^{-6})x^3+(\alpha^3+\alpha^{1})x^4+(\alpha^{-6}+\alpha^{-6})x^5+(\alpha^0+1)x^6\end{pmatrix}=
\begin{pmatrix}(1+\alpha^{-4})+(\alpha^{1}+\alpha^{2})x+\alpha^{7}x^2&\alpha^{7}+\alpha^{-3}x \\ \alpha^4+\alpha^{-5}x&1\end{pmatrix} \begin{pmatrix} \alpha^{-7}+\alpha^{4}x+\alpha^{-1}x^2+ \alpha^{6}x^3+\alpha^{-1}x^4+\alpha^{5}x^5\\ \alpha^{-3}+\alpha^{-2}x+\alpha^{0}x^2+ \alpha^{-2}x^3+\alpha^{-6}x^4\end{pmatrix}=
\begin{pmatrix}\alpha^{-3}+\alpha^{5}x+\alpha^{7}x^2&\alpha^{7}+\alpha^{-3}x \\ \alpha^4+\alpha^{-5}x&1\end{pmatrix} \begin{pmatrix}\alpha^{-5}+\alpha^{-4}x&1\\ 1&0\end{pmatrix} \begin{pmatrix} \alpha^{-3}+\alpha^{-2}x+\alpha^{0}x^2+ \alpha^{-2}x^3+\alpha^{-6}x^4\\ (\alpha^{7}+\alpha^{-7})+ (\alpha^{-7}+\alpha^{-7}+\alpha^{4})x+\\ (\alpha^{-5}+\alpha^{-6}+\alpha^{-1})x^2+\\ (\alpha^{-7}+\alpha^{-4}+\alpha^{6})x^3+\\ (\alpha^{4}+\alpha^{-6}+\alpha^{-1})x^4+ (\alpha^{5}+\alpha^{5})x^5\end{pmatrix}=
\begin{pmatrix}\alpha^{7}x+\alpha^{5}x^2+\alpha^{3}x^3&\alpha^{-3}+\alpha^{5}x+\alpha^{7}x^2\\ \alpha^{3}+\alpha^{-5}x+\alpha^{6}x^2&\alpha^4+\alpha^{-5}x\end{pmatrix} \begin{pmatrix} \alpha^{-3}+\alpha^{-2}x+\alpha^{0}x^2+ \alpha^{-2}x^3+\alpha^{-6}x^4\\ \alpha^{-4}+\alpha^{4}x+\alpha^{2}x^2+ \alpha^{-5}x^3\end{pmatrix}.
Dostali jsme se k polynomu stupně 3, a vzhledem k tomu, že
\begin{pmatrix}-(\alpha^4+\alpha^{-5}x)&\alpha^{-3}+\alpha^{5}x+\alpha^{7}x^2\\ \alpha^{3}+\alpha^{-5}x+\alpha^{6}x^2&-(\alpha^{7}x+\alpha^{5}x^2+\alpha^{3}x^3)\end{pmatrix} \begin{pmatrix}\alpha^{7}x+\alpha^{5}x^2+\alpha^{3}x^3&\alpha^{-3}+\alpha^{5}x+\alpha^{7}x^2\\ \alpha^{3}+\alpha^{-5}x+\alpha^{6}x^2&\alpha^4+\alpha^{-5}x\end{pmatrix} =\begin{pmatrix}1&0\\ 0&1\end{pmatrix},
dostáváme
\begin{pmatrix}-(\alpha^4+\alpha^{-5}x)&\alpha^{-3}+\alpha^{5}x+\alpha^{7}x^2\\ \alpha^{3}+\alpha^{-5}x+\alpha^{6}x^2&-(\alpha^{7}x+\alpha^{5}x^2+\alpha^{3}x^3)\end{pmatrix} \begin{pmatrix}S(x)\Gamma(x)\\ x^6\end{pmatrix}= \begin{pmatrix} \alpha^{-3}+\alpha^{-2}x+\alpha^{0}x^2+\\ \alpha^{-2}x^3+\alpha^{-6}x^4\\ \alpha^{-4}+\alpha^{4}x+\alpha^{2}x^2+\\ \alpha^{-5}x^3\end{pmatrix},
a tedy
S(x)\Gamma(x)(\alpha^{3}+\alpha^{-5}x+\alpha^{6}x^2)- (\alpha^{7}x+\alpha^{5}x^2+\alpha^{3}x^3)x^6= \alpha^{-4}+\alpha^{4}x+\alpha^{2}x^2+\alpha^{-5}x^3.
Nechť \Lambda(x)=\alpha^{3}+\alpha^{-5}x+\alpha^{6}x^2. Netrapme se tím, že absolutní člen není 1. +more Nalezněme hrubou silou kořeny polynomu \Lambda. Jsou jimi \alpha^2 a \alpha^{10} (po nalezení prvního můžeme vydělit \Lambda polynomem (x-\alpha^2) a kořen polynomu stupně 1 nalezneme snadno).
Označme \Xi(x)=\Gamma(x)\Lambda(x)=\alpha^3+\alpha^4x^2+\alpha^2x^3+\alpha^{-5}x^4 a \Omega(x)=S(x)\Xi(x)\bmod x^6=\alpha^{-4}+\alpha^4x+\alpha^2x^2+\alpha^{-5}x^3. Velikosti chyb hledáme ve tvaru e_j=-\Omega(\alpha^{-i_j})/\Xi'(\alpha^{-i_j}), kde \alpha^{-i_j} jsou kořeny polynomu \Xi(x). +more \Xi'(x)=\alpha^{2}x^2. Dostáváme e_1=-\Omega(\alpha^4)/\Xi'(\alpha^{4})=(\alpha^{-4}+\alpha^{-7}+\alpha^{-5}+\alpha^{7})/\alpha^{-5}=\alpha^{-5}/\alpha^{-5}=1, e_2=-\Omega(\alpha^7)/\Xi'(\alpha^{7})=(\alpha^{-4}+\alpha^{-4}+\alpha^{1}+\alpha^{1})/\alpha^{1}=0, e_3=-\Omega(\alpha^{10})/\Xi'(\alpha^{10})=(\alpha^{-4}+\alpha^{-1}+\alpha^{7}+\alpha^{-5})/\alpha^{7}=\alpha^{7}/\alpha^{7}=1, e_4=-\Omega(\alpha^{2})/\Xi'(\alpha^{2})=(\alpha^{-4}+\alpha^{6}+\alpha^{6}+\alpha^{1})/\alpha^{6}=\alpha^{6}/\alpha^{6}=1. To, že e_3=e_4=1, by nás nemělo překvapit.
Opravený kód tedy má být [ 1 0 1 1 0 0 1 0 1 0 0].
Dekódování s nečitelnými znaky a malým počtem chyb
Ještě ukažme průběh výpočtu v případě, kdy je v přijatém kódu pouze jedna chyba [ 1 0 . 1 1 . +more 0 0 0 1 0 1 0 0 ]. Opět nahradíme nečitelné znaky nulami, spočteme \Gamma(x)=(\alpha^8x-1)(\alpha^{11}x-1) a syndromy s_1=\alpha^{4}, s_2=\alpha^{-7}, s_3=\alpha^{1}, s_4=\alpha^{1}, s_5=\alpha^{0}, a s_6=\alpha^{2}. Sestavíme polynom syndromů S(x)=\alpha^{4}+\alpha^{-7}x+\alpha^{1}x^2+\alpha^{1}x^3+\alpha^{0}x^4+\alpha^{2}x^5, a S(x)\Gamma(x)=\alpha^{4}+\alpha^{7}x+\alpha^{5}x^2+\alpha^{3}x^3+\alpha^{1}x^4+\alpha^{-1}x^5+\alpha^{-1}x^6+\alpha^{6}x^7. Spusťme rozšířený Euklidův algoritmus:.
\begin{pmatrix}S(x)\Gamma(x)\\ x^6\end{pmatrix}= \begin{pmatrix}\alpha^{4}+\alpha^{7}x+\alpha^{5}x^2+\alpha^{3}x^3+\alpha^{1}x^4+\alpha^{-1}x^5+\alpha^{-1}x^6+\alpha^{6}x^7\\ x^6\end{pmatrix}=
\begin{pmatrix}\alpha^{-1}+\alpha^{6}x&1\\ 1&0\end{pmatrix} \begin{pmatrix}x^6\\ \alpha^{4}+\alpha^{7}x+\alpha^{5}x^2+\alpha^{3}x^3+\alpha^{1}x^4+\alpha^{-1}x^5+(\alpha^{-1}+\alpha^{-1})x^6+(\alpha^{6}+\alpha^{6})x^7 \end{pmatrix}=
\begin{pmatrix}\alpha^{-1}+\alpha^{6}x&1\\ 1&0\end{pmatrix} \begin{pmatrix}\alpha^{3}+\alpha^{1}x&1\\ 1&0\end{pmatrix} \begin{pmatrix} \alpha^{4}+\alpha^{7}x+\alpha^{5}x^2+\alpha^{3}x^3+\alpha^{1}x^4+\alpha^{-1}x^5\\ \alpha^{7}+(\alpha^{-5}+\alpha^{5})x+ (\alpha^{-7}+\alpha^{-7})x^2+ (\alpha^{6}+\alpha^{6})x^3+\\ (\alpha^{4}+\alpha^{4})x^4+ (\alpha^{2}+\alpha^{2})x^5+ (\alpha^{0}+1)x^6 \end{pmatrix}=
\begin{pmatrix}(1+\alpha^{2})+(\alpha^{0}+\alpha^{-6})x+\alpha^{7}x^2&\alpha^{-1}+\alpha^{6}x\\ \alpha^{3}+\alpha^{1}x&1\end{pmatrix} \begin{pmatrix}\alpha^{4}+\alpha^{7}x+\alpha^{5}x^2+\alpha^{3}x^3+\alpha^{1}x^4+\alpha^{-1}x^5\\ \alpha^{7}+\alpha^{0}x \end{pmatrix}.
Dostali jsme se k polynomu stupně nejvýš 3, a vzhledem k tomu, že
\begin{pmatrix}-(1)&\alpha^{-1}+\alpha^{6}x\\ \alpha^{3}+\alpha^{1}x&-(\alpha^{-7}+\alpha^{7}x+\alpha^{7}x^2)\end{pmatrix} \begin{pmatrix}\alpha^{-7}+\alpha^{7}x+\alpha^{7}x^2&\alpha^{-1}+\alpha^{6}x\\ \alpha^{3}+\alpha^{1}x&1\end{pmatrix} =\begin{pmatrix}1&0\\ 0&1\end{pmatrix},
dostáváme
\begin{pmatrix}-(1)&\alpha^{-1}+\alpha^{6}x\\ \alpha^{3}+\alpha^{1}x&-(\alpha^{-7}+\alpha^{7}x+\alpha^{7}x^2)\end{pmatrix} \begin{pmatrix}S(x)\Gamma(x)\\ x^6\end{pmatrix}= \begin{pmatrix}\alpha^{4}+\alpha^{7}x+\alpha^{5}x^2+\alpha^{3}x^3+\alpha^{1}x^4+\alpha^{-1}x^5\\ \alpha^{7}+\alpha^{0}x \end{pmatrix},
a tedy
S(x)\Gamma(x)(\alpha^{3}+\alpha^{1}x)- (\alpha^{-7}+\alpha^{7}x+\alpha^{7}x^2)x^6= \alpha^{7}+\alpha^{0}x.
Nechť \Lambda(x)=\alpha^{3}+\alpha^{1}x. Netrapme se tím, že absolutní člen není 1. Kořenem polynomu je \alpha^{3-1}.
Označme \Xi(x)=\Gamma(x)\Lambda(x)=\alpha^{3}+\alpha^{-7}x+\alpha^{-4}x^2+\alpha^{5}x^3 a \Omega(x)=S(x)\Xi(x)\bmod x^6=\alpha^{7}+\alpha^{0}x. Velikosti chyb hledáme ve tvaru e_j=-\Omega(\alpha^{-i_j})/\Xi'(\alpha^{-i_j}), kde \alpha^{-i_j} jsou kořeny polynomu \Xi(x). +more \Xi'(x)=\alpha^{-7}+\alpha^{5}x^2. Dostáváme e_1=-\Omega(\alpha^4)/\Xi'(\alpha^{4})=(\alpha^{7}+\alpha^{4})/(\alpha^{-7}+\alpha^{-2})=\alpha^{3}/\alpha^{3}=1, e_2=-\Omega(\alpha^7)/\Xi'(\alpha^{7})=(\alpha^{7}+\alpha^{7})/(\alpha^{-7}+\alpha^{4})=0/\alpha^{5}=0, e_3=-\Omega(\alpha^2)/\Xi'(\alpha^2)=(\alpha^{7}+\alpha^{2})/(\alpha^{-7}+\alpha^{-6})=\alpha^{-3}/\alpha^{-3}=1. To, že e_3=1, by nás nemělo překvapit.
Opravený kód tedy má být [ 1 0 1 1 0 0 0 1 0 1 0 0].