13.10.2015
Kódování Radim Farana Podklady pro výuku
Obsah Galoisova tělesa. Cyklické kódy BCH kódy. Évariste Galois * 25. 10. 1811, Bourg-la-Reine, Francie + 31. 5. 1832, Paříž, Francie http://www.qcm-de-culture-generale.com/fiche-de-revision2735-Evariste-Galois-1811-1831-.html
Galoisova tělesa Těleso je algebraická struktura, na které jsou definovány dvě binární operace (sčítání – a násobení – ). Je rozšířením okruhu, oproti kterému navíc přináší existenci inverzního prvku pro obě binární operace (okruh vyžadoval existenci inverzního prvku jen pro operaci ). Běžně pracujeme s tělesem R, které je tvořeno reálnými čísly a definicí jejich sčítání a násobení, tělesem C, tvořeným komplexními čísly a jejich sčítáním a násobením nebo tělesem Q, které tvoří racionální čísla a definice jejich sčítání a násobení. Všechna tato tělesa mají nekonečný počet prvků, proto je nutné existenci těles ověřovat.
1
13.10.2015
Galoisova tělesa Pro popisy kódů jsou významná především konečná tělesa, nazývaná Galoisova tělesa, není nutné axiómy ověřovat, stačí znát popis všech těles. Galoisovo těleso je určeno počtem svých prvků q a označuje se GF(q). Všechna Galoisova tělesa musí mít definován nulový a jednotkový prvek. Operace s nimi mohou být definovány např. tabulkou.
Galoisova tělesa Pro GF(2) to budou tabulky:
0
1
0
1
0
0
1
0
0
0
1
1
0
1
0
1
Galoisova tělesa Pro naše potřeby jsou důležitá zejména Galoisova tělesa s algebraickým rozšířením. Pro každé těleso T a každý polynom q(x) stupně n je definován okruh T/q(x), který nazýváme algebraické rozšíření tělesa T. Prvky tohoto okruhu jsou všechny polynomy nad tělesem T stupně menšího nebo rovného n – 1. Algebraické rozšíření T/q(x) splňuje podmínky toho, aby bylo tělesem právě tehdy, když je polynom q(x) nerozložitelný (ireducibilní).
2
13.10.2015
Galoisova tělesa Uvažujeme těleso Z2, které bude rozšířeno polynomem q(x) = x2 + x + 1. Tato nová nula, kterou označíme α, je definována rovnicí α2 + α + 1 = 0, platí tedy α2 = α + 1. Těleso vzniklé tímto rozšířením tedy bude mít dva nové prvky α a α + 1. Celkově tedy máme čtyři prvky, pro které definujeme operace sčítání a násobení:
Galoisova tělesa
0
1
0
0
1
1
α α+1
α
α+1
0
1
1
α
α+1
0
0
0
0
0
0
α+1
α
1
0
1
α
α+1
α
α+1
0
1
α
0
α
α+1
1
α+1
α
1
0
α+1
0
α+1
1
α
α
α+1
Galoisova tělesa GF(4) = Z2/(x2 + x + 1) 0 1 = α0 = α3 α = α1 1 + α = α2
GF(8) = Z2/(x3 + x + 1) 0 1 = α0 = α7 α = α1 α2 = α2 1 + α = α3 α + α2 = α4 1 + α + α2 = α5 1 + α2 = α6
3
13.10.2015
BCH kódy Objevili na konci 50. let R. C. Bose a D. K. Ray - Chaudhuri, nezávisle na nich současně také A. Hocquenghem.
Hocquenghem, Alexis
Bose, Raj Chandra
* 14. 1. 1908 Lille, France + 17. 4. 1990 Nice, France
* 19. 6. 1901, Hoshangabad, India + 31. 10. 1987, Fort Collins, USA http://www-history.mcs.stand.ac.uk/BigPictures/Bose_Raj.jpeg
Ray-Chaudhuri, Dwijendra Kumar * 1. 11. 1933, Narayanganj, India http://www.math.osu.edu/people/image/raychaudhuri.1
Oprava jednoduchých chyb Pro opravu jednoduchých chyb slouží cyklické Hammingovy kódy. Popis kódu pomocí generujících kořenů, kontrolní matice:
H 1 2 ... 14
kde je α – primitivní prvek Galoisova tělesa GF(16). Galoisovo těleso je tvořeno rozšířením tělesa polynomů pomocí nerozložitelného (ireducibilního) polynomu.
BCH kódy BCH kódy jsou pak těmito nástroji definovány jako zobecnění Hammingových kódů. Zatímco pro opravu jednoduché chyby má kontrolní matice H jeden řádek [nad Galoisovým tělesem GF(16)], pro dvojnásobné chyby pak má dva řádky. Pro kód o délce 15 je to matice: 1 H 3 1
2
3 2
... ...
14
3 14
4
13.10.2015
Kontrolní matice Kontrolní matici můžeme přepsat pomocí tabulky převodů do binární matice s osmi řádky. Kódová slova vyhovují rovnici:
1 3 1
2
3 2
... ...
w0 w 1 14 w2 0 14 . 3 ... 0 w13 w14
Kontrolní matice Kontrolní matice složená z prvků αi Galoisova tělesa GF(16) je převoditelná do binárních polynomů: 1 0 0 0 H 1 0 0 0
0 0 0 1 0 0 1 1 0 1 0 1 1 1 1 0 0 1 1 0 1 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 1 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 0 0 1 1 0 0 0 1 1 0 0 0 1 1 0 1 0 1 0 0 1 0 1 0 0 1 0 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1
BCH kód Tento BCH-kód je (15, 7)-kód, neboť matice H má lineárně nezávislé řádky. Jestliže α má minimální polynom M1(x) = x4 + x + 1 a α3 má minimální polynom M3(x) = x4 + x3 + x2 + 1. Potom každé kódové slovo w(x) je představováno polynomem, který je dělitelný jak polynomem M1(x), tak polynomem M3(x). Poslední polynom je nerozložitelný, to znamená, že kódové slovo musí být dělitelné součinem polynomů M1(x)M3(x). Tento kód opravuje dvojnásobné chyby.
5
13.10.2015
Generující polynom Polynom s nejnižším stupněm, který představuje nenulové slovo, je generujícím polynomem našeho kódu: g(x) = M1(x)M3(x) = (x4 + x + 1)( x4 + x3 + x2 + 1) = x8 + x7 + x6 + x4 + 1
Příklad 1 použijeme-li BCH-kód délky 15 s plánovanou vzdáleností 7, generující polynom bude například: g(x) = (x4 + x + 1)( x4 + x3 + x2 + 1) (x2 + x + 1) = = x10 + x8 + x5+ x4 + x2 + x + 1 Informační znaky 01001 zakódujeme následovně: g(x)(x + x4) = (x14 + x12 + x11+ x8 + x4 + x3 + x2 + x) a získáme kódové slovo 011110001001101.
Dekódování BCH-kódu Pro dekódování BCH-kódů sestavíme kontrolní matici. Z kontrolní matice můžeme vypočítat: w0 w 1 w w( ) s1 w0 w1 w2 2 ... wn 1 n 1 H 2 3 3 3 2 3 n 1 ... w 0 w1 w2 ( ) ... wn 1 ( ) w( ) s3 wn 2 wn 1
6
13.10.2015
Dekódování BCH-kódu Přijaté slovo je: w w0 w1 ... w14
které se od vyslaného slova liší na i-tém a j-tém místě. Chybové slovo (rozdíl vyslaného a přijatého slova) pak je e = 00…010…010…00,
nebo ve tvaru polynomu: e = zi + zj.
Dekódování BCH-kódu Jeho syndrom je i j s1 T T s Hw He 3i 3j 3
Chceme tedy určit čísla i a j, pro která platí: s1 i j s3 3i 3 j
Dekódování BCH-kódu Z první rovnice dostáváme:
s13 i j 3i 2i j i 2 j 3 j s3 2i j i 2 j s3 i j i j 3
s3 s1 i j .
Známe tedy součet i součin
i j
i j s1 s13 s3 s12 s3 s11 s1
neznámých veličin αi a αj.
7
13.10.2015
Dekódování BCH-kódu Tyto veličiny jsou kořeny kvadratické rovnice
2 s1 s12 s3 s11 0 Pro řešení této rovnice dosazujeme postupně λ = 1, α, α2, … (obvyklý vzorec pro řešení kvadratických rovnic samozřejmě nad konečným tělesem neplatí). Tak získáme kořeny αi a αj a opravíme následně prvky přijatého slova wi a wj.
BCH-kód s plánovanou vzdáleností Binární BCH-kód s plánovanou vzdáleností d = 2, 3, 4, … je kód liché délky n ≥ d s generujícími kořeny , 2 , 3 , ..., d 1 , kde α je prvek n-tého řádu v tělese GF(2m).
BCH-kód s plánovanou vzdáleností BCH-kód s plánovanou vzdáleností d můžeme také definovat pomocí kontrolní matice: 1 3 1 5 H 1 ... ... 1 d 2
2
3 2
5 2
3
3 3
5 3
...
...
d 2 2
d 2 3
... ... ... ... ...
n 1
... n 1 d 2 3 n 1
5 n 1
8
13.10.2015
BCH-kód s plánovanou vzdáleností Počet kontrolních znaků BCH-kódu je nk
1 md 1 . 2
Kontrolní matice má
1 (d 1) 2
řádků nad tělesem GF(2m), a proto má 1 md 1 2
řádků nad tělesem Z2.
Pokud jsou tyto řádky lineárně nezávislé, platí n k 1 md 1 , 2 pokud jsou závislé, bude n – k menší.
Dekódování BCH-kódů Pro dekódování můžeme použít maticovou metodu dekódování. BCH-kód s plánovanou vzdáleností 2t + 1 je schopen opravit t-násobné chyby. Abychom je opravili, najdeme částečné dekódování : Z K takové, že kdykoliv při vyslání kódového slova v dojde k t-násobné chybě, potom přijaté slovo w splňuje (w) v Stačí ovšem najít chybové slovo e = w – v ( n) 2
Dekódování BCH-kódů Pro každé slovo w = w0w1…wn-1 pak nastávají tyto možnosti: Došlo k t-násobné chybě, existuje tedy slovo e váhy ≤ t takové, že w – e je kódové slovo. Pak ze skutečnosti, že minimální vzdálenost kódu je alespoň 2t + 1 plyne, že takové slovo existuje pouze jedno. Dekódování tedy určí chybové slovo e. Došlo k chybě více než t-násobné. Tuto situaci naše dekódování někdy objeví, místo určení chybového slova e pak bude ohlášena velká chyba. V některých případech ale taková chyba vůbec nebude objevena a dekódování skončí nalezením nesprávného slova e.
9
13.10.2015
Dekódování BCH-kódů Předpokládáme, že došlo k t-násobné chybě. Hledané chybové slovo e má váhu p (≤ t), takže existují souřadnice ei1 , ei2 , ..., ei p rovné 1, zatímco ostatní souřadnice mají hodnotu 0. Určíme polynom f(x), tzv. lokátor chyb, jehož kořeny jsou i , i , ..., i Prozkoumáním kořenů tohoto polynomu pak určíme. která místa přijatého slova je třeba opravit: opravíme wi, právě když f ( i ) 0 1
2
p
Dekódování BCH-kódů 1. Určení syndromu přijatého slova. 1 2 1 s Hw 1 3 ... ... 1 2t T
T
2
3
2 2
2 3
3 2
3 3
...
...
2t 2
2t 3
n1 w0
... ... ...
... ...
w1 . w2 ... ... n 1 2t wn1 2 n 1 3 n 1
w( ) w0 w1 w2 2 ... wn 1 n 1 n 1 2 2 2 2 ... wn 1 2 w0 w1 w1 w( ) 2 n 1 3 3 3 w( 3 ) w0 w1 w1 ... wn 1 ... ... w w 2t w 2t 2 ... w 2t n 1 w( 2t ) 1 1 n 1 0
Dekódování BCH-kódů 2. Určení koeficientů lokátoru chyb f ( x) (1 a1 x)(1 a2 x)...(1 a p x)
jakmile určíme tento polynom a jeho kořeny, což jsou prvky a pro n = 1, 2, …, p, máme určeno chybové slovo e: i n
in
1 pokud f ( i ) 0, ei jinak. 0
10
13.10.2015
Dekódování BCH-kódů polynom f ( x) f 0 f1 x ... f p x p má první koeficient f0 = 1 (protože f(0) = 1) a ostatní koeficienty určíme ze soustavy lineárních rovnic. K jejímu odvození použijeme mocninnou řadu:
S ( x) s k x k k 1
p
kde koeficienty jsou:
s k a1k a 2k ... a kp a nk n 1
Dekódování BCH-kódů Známe tedy pouze koeficienty s1, s2, …, s2t, ale to nám postačuje. Pro koeficienty lokátoru chyb platí rovnice: s1
f1 s 2 f1 s 4 f1
s1 f 2 s3 f 2
f3 s2 f 3
...
...
...
s 2 p 2 f1
s 2 p 3 f 2
s 2 p 4 f 3
s1 f 4
f5
s3 s5
... ...
... s p f p 1 s p 1 f p
... s 2 p 1
Dekódování BCH-kódů 3. Oprava chyb nalezením kořenů polynomu f(x) postupným dosazováním prvků 1, 1 , 2 , ..., a opravíme i-tý znak slova w, když platí
f i 0
11
13.10.2015
Použití BCH-kódů V praxi se často používají BCH-kódy, které opravují dvojnásobné chyby a současně detekují trojnásobné chyby. Jejich minimální vzdálenost musí být alespoň 6. Nejčastěji má kontrolní matice tvar: 1 1 ... 1 1 1 H 1 2 3 1 3 6 9
n 1 ... 3( n 1)
...
kde je α primitivní prvek Galoisova tělesa GF(2m) a výrazy αi jsou mocniny tohoto primitivního prvku pro i = 0, 1, 2, …, 2m – 2.
12
