BCH kód

Z Wikipedie, otevřené encyklopedie

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

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ů

  • 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 Reed-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ť 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

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í

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ů

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

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

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

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

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

Forneyův vzorec

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

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

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

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 nelezení 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í Fourney 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í

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

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

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

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

Citace

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

Reference

Hlavní zdroje

Sekundární zdroje

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