V 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.[1] 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. 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,[2] CD a DVD přehrávačích, pevných discích, flash discích[3] a QR kódech.

Konstrukce

editovat

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. 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 v1v2vn, 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. 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ů

editovat
  • 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.
  • BCH kód s n<qb/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.[4]

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ů

editovat

Nechť   a   (tedy  ). Uvažujme různé hodnoty  

Existuje primitivní prvek   splňující   jeho minimální polynom nad   je

 

Poznamenejme, že v   platí   proto  

Tudíž   je kořen polynomu   a

 

Abychom spočítali   poznamenejme, že opakovanou aplikací (*), dostáváme následující rovnice:

  •  
  •  
  •  
  •  
  •  

Pět pravých stran délky čtyři musí být lineárně závislých a tak najdeme lineární závislost  

Protože neexistuje závislost nižšího řádu, je minimálním polynomem pro   polynom

 

Budeme-li pokračovat obdobně, získáme

 
 
 
 

BCH kódy s   mají generující polynom

 

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   mají generující polynom

 

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   mají generující polynom

 

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   má generující polynom

 

Kód má minimální Hammingovu vzdálenost 15 a opravuje nejvýš 7 chyb. Má 1 datový bit a 14 zabezpečovacích bitů. Tento kód má tedy jen dvě kódová slova: 000000000000000 a 111111111111111.

Vlastnosti

editovat

1. Generující polynom BCH kódu má stupeň nejvýš   Navíc, pokud   a   pak generující polynom má stupeň nejvýš  

Důkaz: každý minimální polynom   má stupeň nejvýš  

Proto minimální společný násobek   z nich má stupeň nejvýš   Navíc, pokud   pak   pro každé   Proto,   je nejmenší společný násobek nejvýš   minimálních polynomů   pro liché indexy   každý z nich je stupně nejvýš  

2. BCH kód má minimální Hammingovu vzdálenost alespoň  

Důkaz: Předpokládejme, že   je kód (jemu odpovídající polynom) s méně než   nenulovými koeficienty. Potom nechť

 

Připomeňme, že   jsou kořeny   tudíž i jeho násobku   Z toho plyne, že   splňuje následující rovnice pro  

 

V maticovém tvaru dostáváme

 

Determinant této matice je roven

 

Matice   je Vandermondova matice, a její determinant je

 

což je nenulové. Odtud vyplývá, že   a tudíž  

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   je cyklický právě když generující polynom dělí   Protože   je minimální polynom s kořeny   stačí zkontrolovat, že každé z   je kořen polynomu   To plyne přímo z toho, že   je podle definice  tá odmocnina z jedné.

Dekódování

editovat

Existuje mnoho algoritmů pro dekódování BCH kódů. Nejběžnější používají následující schéma:

  1. Spočtěme pro přijaté slovo syndromy sj.
  2. Ze syndromů určeme počet chyb t a polynom pro lokalizaci chyb Λ(x).
  3. Nalezněme kořeny polynomu pro lokalizaci chyb xj a jejich logaritmy -ij, tak že α−ij=xj.
  4. Spočtěme chybové hodnoty ei v pozicích ij.
  5. 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. 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ů

editovat

Přijaté slovo   je součet korektního kódového slova   a neznámého chybového slova   Hodnoty syndromů jsou získány dosazením hodnot   do   vnímaného jakožto polynom. Proto jsou syndromy[5]

 

pro   od   do   Protože   jsou kořeny   jehož je   násobek,   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   pro každé   V takovém případě dekódování končí.

Výpočet polynomu pro lokalizaci chyb

editovat

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

 

Není zřejmé, jak začít řešit rovnice s neznámými   a   vysvětlující syndromy.

Prvním krokem je nalezení polynomu pro lokalizaci chyb

  kompatibilního se spočtenými syndromy a s minimálním možným  

Dva populární algoritmy pro tuto úlohu jsou:

  1. Algoritmus Peterson–Gorenstein–Zierler[6]
  2. Algoritmus Berlekamp–Massey

Cílem obou algoritmů je nalézt

 

takové, aby pro každé   od   do   platilo

 

Navíc požadujeme  


Zdůvodnění rovnic pro výpočet polynomu pro lokalizaci chyb

editovat

Vzhledem k tomu, že   je kořenem polynomu   musí být

 

Po pronásobení   dostáváme

 

Po sečtení přes jednotlivé chyby pak

 

neboli

 

Algoritmus Peterson–Gorenstein–Zierler

editovat

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
 
  • pak vektor  
 
  • Nechť neznámé koeficienty polynomu   jsou
 
  • Pokud má   nenulový determinant, pak maticová rovnice
 
má řešení. Nalezněme tedy koeficienty polynomu   a skončeme.
  • Jinak pokud   deklarujme nulový polynom lokalizace chyb a skončeme.
  • Jinak snižme   o   a vraťme se k sestavení matice  

V případě   větším než je počet chyb (můžeme dodefinovat nadbytečná   nulou). Pak

 

a determinant je nulový, dokud není   minimální možné.

Algoritmus Berlekamp–Massey

editovat

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

editovat

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

editovat

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ě. V obecném případě mohou být velikosti chyb   určeny řešením soustavy lineárních rovnic

 
 

Forneyův vzorec

editovat

Existuje ale efektivnější metoda známá jako Forneyův vzorec.

Nechť   Nechť     a  

Nechť   je polynom vyhodnocující chyby.[7]

Nechť   kde   zde značí   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  , pak jsou velikosti chyb

 

Pro doslovné kódy, c = 1, takže můžeme výraz vykrátit na:

 

Zdůvodnění Forneyova vzorce

editovat

Algoritmus je založen na Lagrangeově interpolaci a technikách vytvořujících funkcí.

Prozkoumejme   Pro jednoduchost dodefinujme   pro   a   pro  

Pak   Vztah   jsme již odvodili dříve, takže víme pro důkaz nepodstatnou informaci, že koeficienty u   jsou 0 pro  

Zkoumejme dál význam jednotlivých koeficientů:

 
 

Můžeme získat následující formu polynomu :

 

Chceme spočítat neznámé   a můžeme zjednodušit kontext odstraněním   členů. To vede k definici polynomu vyhodnocujícího chyby

 

Díky předpokladu   dostáváme

 

Zaměřme se na   Díky   (trik Lagrangeovy interpolace) suma degeneruje na jediný sčítanec

 

K nalezení   již stačí zbavit se nadbytečného součinu. Můžeme jej spočítat přímo z již známých kořenů   polynomu   ale můžeme využít jednodušší výraz.

Protože formální derivace  

Získáváme v bodě   opět jediný sčítanec

 

Takže konečně

 

Tato formule je zjednodušením v případě, kdy formální derivaci   počítáme z tvaru   pomocí

 

kde   značí   místo násobení v příslušném tělese.

Dekódování založené na rozšířeném Euklidově algoritmu

editovat

Celý proces hledání lokalizačního polynomu Λ i hledání velikosti chyb je možno založit na

  1. Rozšířeném Eukleidově algoritmu. Navíc přitom můžeme opravovat i nečitelné znaky na neznámých pozicích.

Nechť   jsou pozice nečitelných znaků. Sestavíme tomu odpovídající polynom   Dodefinujme nečitelná místa nulou a spočtěme syndromy. Tak jak jsme si popsali u Forneyova vzorce nechť  

Spustíme rozšířený Euklidův algoritmus na hledání nejmenšího společného dělitele polynomů   a   Naším cílem ale nebude nalézt nejmenšího společného dělitele, ale polynom   stupně nejvýš   a polynomy   tak, aby   Nízký stupeň polynomu   zajistí, že pro   budou platit zobecněné (o polynom opravující nečitelné znaky) definiční vztahy které jsme kladli na  

Při definici   a použití   na místě   ve Fourney algoritmu pak dostaneme odhad velikosti chyb.

Hlavní výhodou algoritmu je, že zároveň spočítá ve Forneyově vzorci potřebné  

Zdůvodnění nejen dekódování založeném na rozšířeném Euklidově algoritmu

editovat

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. Syndrom   klade na chybové slovo podmínku   Tyto podmínky můžeme zapisovat samostatně, nebo můžeme vytvořit polynom   a klást podmínky na koeficienty u mocnin     

Víme-li, že na pozici   je nečitelný znak, můžeme množinu syndromů   nahradit množinou syndromů   definovaných vztahem   Pokud platí pro chybové slovo podmínky kladené množinou syndromů   pak   Nová množina syndromů má vůči chybovému vektoru   stejný vztah jako měla původní množina syndromů vůči chybovému vektoru   Všimněme si, že s výjimkou souřadnice   kde je   je   nenulové, právě když je   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   nečitelných znaků.

Při formulaci v řeči polynomů nám náhrada množiny syndromů   množinou syndromů   vede k   Odtud  

Po nahrazení   pomocí   pak proto budeme hledat shodu u koeficientů  

Obdobně jako odstraňování vlivu nečitelných znaků můžeme vnímat i hledání chybných pozic. Pokud najdeme   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. Pokud označíme   polynom odstraňující vliv těchto souřadnic, dostaneme  

V Euklidově algoritmu se snažíme odstranit nejvýš   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é   nastat ve výše uvedeném vztahu rovnost u všech souřadnic počínaje  

Ve Forney vzorci (pro nalezení velikosti chyb) nezáleželo na tom, zda je   vynásobena nenulovou konstantou, proto je podmínka   zbytečná. Může se stát, že Euklidův algoritmus najde   stupně většího než   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é. Obvykle při nalezení   většího stupně odmítáme chyby opravovat. Stejně tak oprava chyb selže, pokud má   vícenásobné kořeny či jejich počet neodpovídá stupni   Selhání také může detekovat to, když Forney vzorec vrátí chybu z rozdílu těles  

Příklady dekódování

editovat

Dekódování binárního kódu bez nečitelných znaků

editovat

Nechť   a používáme dříve uvedený kód s   v GF(24). (Tento generátor je použit v QR kódech.) Nechť přenášená zpráva je [1 1 0 1 1], nebo jako polynom   Zabezpečovací symboly jsou spočteny dělením   polynomem   a přičtením (odečtením) zbytku   neboli [ 1 0 0 0 0 1 0 1 0 0 ] k   Přidáním ke zprávě tak dostáváme přenášené kódové slovo [ 1 1 0 1 1 1 0 0 0 0 1 0 1 0 0 ].

Předpokládejme, že dva bity byly poškozeny v průběhu přenosu, takže přijaté slovo je [ 1 0 0 1 1 1 0 0 0 1 1 0 1 0 0 ]. Jakožto polynom tedy:

 

Abychom chyby opravili, spočteme nejprve syndromy. Přitom   dostaneme           a   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.

 

Protože S3×3 je singulární, což není překvapením, protože slovo obsahuje pouze dvě chyby. Nyní levý horní roh matice je identický s [S2×2 C2×1], což vede k řešení     Výsledný polynom pro lokalizaci chyb je   Polynom má kořeny   a   Exponenty   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

editovat

Předpokládejme nyní, stejný případ, ale přijaté slovo má dva nečitelné znaky [ 1 0 0 ? 1 1 ? 0 0 1 1 0 1 0 0 ]. Nahradíme nečitelné znaky (např.) nulami, vytvořme polynom potlačující vliv nečitelných znaků   Najděme syndromy           a   (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ů   spočtěme  

Spusťme rozšířený euklidův algoritmus:  

 

 

 

 

 

Dostali jsme se k polynomu stupně 3, a vzhledem k tomu, že   dostáváme  

a tedy  

Nechť   Netrapme se tím, že absolutní člen není 1. Nalezněme hrubou silou kořeny polynomu   Jsou jimi   a   (po nalezení prvního můžeme vydělit   polynomem   a kořen polynomu stupně 1 nalezneme snadno).

Označme   a   Velikosti chyb hledáme ve tvaru   kde   jsou kořeny polynomu     Dostáváme         To, že   by nás nemělo překvapit.

Opravený kód tedy má být [ 1 1 0 1 1 1 0 0 0 0 1 0 1 0 0].

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

editovat

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 0 ? 1 1 ? 0 0 0 1 0 1 0 0 ]. Opět nahradíme nečitelné znaky nulami, spočteme   a syndromy           a   Sestavíme polynom syndromů   a   Spusťme rozšířený Euklidův algoritmus:

       

Dostali jsme se k polynomu stupně nejvýš 3, a vzhledem k tomu, že   dostáváme  

a tedy  

Nechť   Netrapme se tím, že absolutní člen není 1. Kořenem polynomu je  

Označme   a   Velikosti chyb hledáme ve tvaru   kde   jsou kořeny polynomu     Dostáváme       To, že   by nás nemělo překvapit.

Opravený kód tedy má být [ 1 1 0 1 1 1 0 0 0 0 1 0 1 0 0].

Reference

editovat
  1. Reed & Chen 1999, s. 189
  2. Phobos Lander Coding System: Software and Analysis [online]. [cit. 2012-02-25]. Dostupné online. 
  3. Sandforce SF-2500/2600 Product Brief [online]. [cit. 2012-02-25]. Dostupné online. 
  4. Gill unknown, s. 3
  5. Lidl & Pilz 1999, s. 229
  6. Gorenstein, Peterson & Zierler 1960
  7. Gill unknown, s. 47

Literatura

editovat

Hlavní literatura

editovat

Sekundární literatura

editovat
  • GILBERT, W. J.; NICHOLSON, W. K. Modern Algebra with Applications. 2nd. vyd. [s.l.]: John Wiley, 2004. 
  • GILL, John. EE387 Notes #7, Handout #28. [s.l.]: Stanford University, unknown. Dostupné v archivu pořízeném dne 30-06-2014. S. 42–45. 
  • GORENSTEIN, Daniel; PETERSON, W. Wesley; ZIERLER, Neal. Two-Error Correcting Bose-Chaudhuri Codes are Quasi-Perfect. Information and Control. 1960, s. 291–294. 
  • LIDL, Rudolf; PILZ, Günter. Applied Abstract Algebra. 2nd. vyd. [s.l.]: John Wiley, 1999. 
  • LIN, S.; COSTELLO, D. Error Control Coding: Fundamentals and Applications. Englewood Cliffs, NJ: Prentice-Hall, 2004. 
  • MACWILLIAMS, F. J.; SLOANE, N. J. A. The Theory of Error-Correcting Codes. New York, NY: North-Holland Publishing Company, 1977. 
  • REED, Irving S.; CHEN, Xuemin. Error-Control Coding for Data Networks. Boston, MA: Kluwer Academic Publishers, 1999. ISBN 0-7923-8528-4. 
  • RUDRA, Atri. CSE 545, Error Correcting Codes: Combinatorics, Algorithms and Applications. [s.l.]: University at Buffalo Dostupné v archivu pořízeném dne 02-07-2010.