BCH kód: Porovnání verzí

V [[kódování|teorii kódování]] tvoří '''BCH kódy''' skupinu [[cyklický kód|cyklických]] [[samoopravný kód|samoopravných kódů]] které jsou konstruovány pomocí [[konečné těleso|konečných těles]]. BCH kódy byly vynalezeny v roce 1959 [[Alexis Hocquenghem|Hocquenghemem]], a nezávisle v roce 1960 [[Raj Chandra Bose|Bosem]] a [[D.K. Ray-Chaudhuri|Ray-Chaudhurim]].<ref>{{Harvnb|Reed|Chen|1999|p=189}}</ref> Zkratka ''BCH'' je tvořena počátečními jmény těchto objevitelů.

 

 

BCH kódy jsou používány například v satelitní komunikaci,<ref>{{cite web|title=Phobos Lander Coding System: Software and Analysis|url=http://ipnpr.jpl.nasa.gov/progress_report/42-94/94V.PDF|accessdate=25 February 2012}}</ref> [[Kompaktní disk|CD]] a [[DVD]] přehrávačích, [[Pevný disk|pevných discích]], [[Solid-state_drive|flash discích]]<ref>{{cite web|title=Sandforce SF-2500/2600 Product Brief|url=http://www.sandforce.com/index.php?id=133&parentId=2&top=1|accessdate=25 February 2012}}</ref> a [[QR kód|QR kódech]].

:<math>g(x) = m_1(x) = x^4+x+1.\,</math>

 

 

BCH kódy s <math>d=4,5</math> mají generující polynom

=== Vlastnosti ===

 

Navíc, pokud <math>A=Z_2</math> a <math>c=1,</math> pak generující polynom má stupeň nejvýš <math>db/2.</math>

 

 

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.

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

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.

 

 

*Nejprve sestavme matici

=== 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

 

Nechť <math>k_1, ... ,k_k</math> jsou pozice nečitelných znaků. Sestavíme tomu odpovídající polynom <math>\Gamma(x)=\prod_{i=1}^k(x\alpha^{k_i}-1).</math>

Tak jak jsme si popsali u Forneyova vzorce nechť <math>S(x)=\sum_{i=0}^{d-2}s_{c+i}x^i.</math>

 

Vytvořme polynom syndromů <math>S(x)=\alpha^{-7}+\alpha^{1}x+\alpha^{4}x^2+\alpha^{2}x^3+\alpha^{5}x^4+\alpha^{-7}x^5,</math> spočtěme <math>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.</math>

 

<math>

\begin{pmatrix}S(x)\Gamma(x)\\ x^6\end{pmatrix}=

 

==== Dekódování s nečitelnými znaky a malým počtem chyb ====

Opět nahradíme nečitelné znaky nulami, spočteme <math>\Gamma(x)=(\alpha^8x-1)(\alpha^{11}x-1)</math> a syndromy

<math>s_1=\alpha^{4},</math> <math>s_2=\alpha^{-7},</math> <math>s_3=\alpha^{1},</math>