- detekcne kody
To su kody, zistujuce chyby. Princip zistenia chyby spociva v zisteni, ci je prijate slovo kodovym slovom, alebo nie.
- samoopravne kody
Kody, ktore v pripade detekcie chyby dokazu nahradit chybne slovo najpravdepodobnejsim kodovym slovom.
Cast znakov bezpecnostneho kodu moze tvorit zobrazovana informacia. Takymto kodom sa hovori systematicky kod a uvedenej casti kodu nadavame informacna cast. Dalsia cast, kontrolna cast, je pridana kvoli detekcii a korekciam. Kod, ktoreho informacnu a kontrolnu cast nejde oddelit nazyvame nesystematicky kod.
Na vstupe mame povodne data a o velkosti k bitov. Tie prejdu koderom a vybehne kodove slovo b o velkosti n bitov (n > k). Slovo b je prenasane kanalom, kde moze/nemusi dojst k chybe e. Na konci kanalu je na vystupe prijate slovo c o velkosti n bitov. Ak doslo k chybe, tak c <> b, inak c == b. Slovo c prebehne dekoderom a odstrania sa kontrolne bity, kde sa moze najst chyba s priznakom s - to moze byt vlastne aj signal NOK/OK. Na vystupe dekoderu je povodne alebo opravene slovo d.
Kanal, ktorym nam informacia moze pretiect moze byt
- symetricky, kde chyba 0 -> 1 a 1 -> 0 sa mozu udiat s rovnakou pravdepodobnostou
- asymetricky, pravdepodnost ako v symetrickom kanali nie je fifty-fifty :)
- bez pamate, chyby v susednych bitoch su nezavisle
- s pamatou, chyby susednych bitov su pravdepodobnejsie (po tom, ako nastane chyba jedneho z nich)
Je dolezite zdoraznit, ze opravne a detekcne kody sa nepouzivaju len v telekomunikaciach, ale napriklad aj v pamatiach. Takze aj ten HW, na ktorom teraz tukam do klavesnice ma (a verim tomu, ze na viacerych miestach) nejaky algoritmus detekcie a opravy chyb. Napriklad Hammingov kod sa vraj pouziva v RAM-kach.
Na obrazku je priklad kodu K1, K2 a K3. Kazdy z nich ma inu velkost a inak koduje data. Podstatne teraz je, kolkymi bitmi koduju informaciu. Na vstupe mame 2 bity, K1 a K2 su 3 bitove, K3 je 5 bitovy. K1 a K2 nam umoznia zistit jednu chybu, K3 umozni zistit dve chyby, alebo opravit 1 chybu (nie oboje!).
Prikladom K3 moze byt prijate slovo 11100. Alfa sa lisi v 3 bitoch, Beta sa lisi v 4 bitoch, gama v 2 bitoch a delta v jednom bite. Najpravdepodobnejsie spravne slovo je delta. Pocet kodovych slov, ktore mozu vyhovovat mnozine je 2^k, kde k je pocet bitov povodnej spravy.
Iste ste zaregistrovali istu redundantnost v prenasanych informaciach. Ta je nielen dolezita, ale aj nevyhnutna, pretoze detekovat a opravovat chyby dokazeme len v pripade, ze
- predpokladame limitovany pocet chyb
- doplnkove informacie musia byt zahrnute
Hammingova vzdialenost
Hammingova vzdialenost je kodova vzdialenost 2 slov. Vzdialenost 2 slov je pocet odlisnych bitov. Kodova vzdialenost je minimalnou vzdialenostou dvojic kodovych slov, to znamena, v minimalne kolkych bitoch sa lisia jednotlive slova. Takze napriklad 11100 a 01011 maju kodovu vzdialenost 4.
Kodova vzdialenost v = d + o + 1, kde d je pocet chyb, ktore je mozne detekovat, o je pocet chyb, ktore je mozne opravit a plati, ze d => o. Takze pre v = 4 je mozne bud najst 3 chyby bez opravy, alebo detekovat 2 chyby a jednu opravit.
Vaha slova w(b) je pocet jedniciek v slove b. Plati, ze hamingova vzdialenost dvoch slov (a, b) = w(a XOR b).
Opakovaci (repeticny) kod (rm, m)
Repeticny kod je snad najjednoduchsim sposobom ako vytvorit bezpecnostny kod. Spociva v opakovanom prenose tej istej spravy. Jedna sa o detekcny kod a nie je schopny opravit chybu. Podla poctu opakovani r nazyvame kod repeticnym kodom r-teho stupna. Tento kod sa vyznacuje velkou redundanciou (rm - m) a malym informacnym obsahom. Trocha matematiky a priklad.
Mame mnozinu informacii, ktora obsahuje vsetky usporiadane m-tice bitov.
(a1 ... am) je povodnou informaciou
(b11 ... b1r, b21, ... ,bmr) je zakom repeticneho kodu r-teho stupna, kde r = pocet opakovani.
Vsimnite si, co sme to spachali, rozdelili sme informaciu do bitov a kazdy bit opakujeme. Predpoklada sa, ze v pripade, ze vsetko bude klapat, tak bude platit (0..9, m a r su indexy b a a).
b11 = b12 = ... = b1r = a1
b21 = b22 = ... = b2r = a2
...
bm1 = bm2 = ... = bmr = am
Priklad pre m = 2 a r =2. n = rm = 4.
m n m znaci m-tice bitov a n je vlastne pocet opakovani * m-tice bitov = dlzka kodu pre
00 0000 informaciu o dlzke m
01 0011
10 1100
11 1111
repeticny kod (5,1) by vyzeral asi takto
0 00000
1 11111
Chyba sa zisti tak, ze sa porovnaju data. Repeticny kod je systematickym kodom. Hammingova vzdialenost je r (pocet opakovani).
Koktavy kod (jk, k)
Je kod, kde sa j krat opakuje k bitov s . Koktavy kod ma velku renundanciu (jk - k) a maly informacny obsah. Kodova vzdialenost slova je rovna j - a to je dolezita informacia preto, lebo potom vieme, kolko chyb mozme najst! Ak ho porovname s opakovacim kodom, tak vidime rozdiel. Koktavy kod "kokta" cele slovo a opakovaci kod opakuje jeden bit r-krat a potom dalsi bit r-krat.
Kody zabezpecene paritou
Parita pridava k datam paritny bit. Tento bit je suctom vsetkych k bitov.
Paritny bit je redundantny bit pridany k datovemu slovu a obsahuje tzv. paritnu informaciu o pocte jednickovych bitov v slove. Je urceny k jednoduchej detekcii chyb v slove. Pomocou paritneho bitu sa da identifikovat neparny pocet chyb v slove (neparny pocet bitov).
Parita moze byt parna a neparna. Uplne po lopate by sme mohli povedat, ze parnost/neparnost je vlastne to, kam sa chceme dostat. Ak pouzivame parnu paritu, tak paritny bit je 1 ak je pocet 1-ovych bitov neparny a spravime ich tak parny. Ak pouzivame neparnu paritu, tak je paritny bit = 1 ak je pocet 1-ovych bitov parny.
Pomocou parity zistime chybu, pretoze v pripade chyby nam nebude sediet parita. Ale to len v pripade, ze chyby sa nestanu 2 :). Paritny bit nam umozni zistit chybu, ale neumozni nam zistit, ktory bit je chybny. Zvykne sa pouzivat na prenos ASCII znakov, napriklad. ASCII znaky maju 7-bitov a s paritou 8.
Priklad z wiki:
Transmission sent using even parity:
A wants to transmit: 1001 A computes parity bit value: 1^0^0^1 = 0 A adds parity bit and sends: 10010 B receives: 10010 B computes parity: 1^0^0^1^0 = 0 B reports correct transmission after observing expected even result.
Transmission sent using odd parity:
A wants to transmit: 1001 A computes parity bit value: ~(1^0^0^1) = 1 A adds parity bit and sends: 10011 B receives: 10011 B computes overall parity: 1^0^0^1^1 = 1
A teraz priklad, ked mame dve chyby
A wants to transmit: 1001 A computes even parity value: 1^0^0^1 = 0 A sends: 10010 *** TRANSMISSION ERROR *** B receives: 11011 B computes overall parity: 1^1^0^1^1 = 0 B reports correct transmission though actually incorrect.
Aby toho nebolo malo, tak existuje este nieco, co sa vola Cross-parity code, alebo horizontalne a vertikalne parity.
Horizontalna parita p1 = a1 XOR a2, p2 = a3 XOR a4. Vertikalna parita p3 = a1 XOR a3 a p4 = a2 XOR a4. Informacia, ktora sa prenesie po kodovani je (a1, a2, a3, a4, p1, p2, p3, p4) a po prejdeni kanalom dostaneme informaciu c (vid obrazok na zaciatku). Pri dekodovani budeme robit znovu xor a to takto, s1 = c1 xor c2 xor c5, teda a1 xor a2 xor p1. Ak syndrom budu same 0-y, tak je vsetko OK a je hotovo. Chceme preniest informaciu 1,0,1,0 a pouzijeme cross-parity (8,4). Teda, informacia ma 4 bity a 4 budu na kodovanie. Hammingova vzdialenost bude 3.
1 0 | 1
1 0 | 1
---------
0 0
informacia (1,0,1,0,1,1,0,0) prejde kanalom a my musime zistit, co sme to dostali. Predpokladajme, ze pride v poriadku (1,0,1,0,1,1,0,0).
s1 = 1 xor 0 xor 1 = 0
s2 = 1 xor 0 xor 1 = 0
s3 = 1 xor 1 xor 0 = 0
s4 = 0 xor 0 xor 0 = 0
Hammingov kod
Hammingov kod je linearny samoopravny kod. Pre kazdy integer m => 2 existuje kod s m paritnymi bitmi a 2^m - m - 1 datovymi bitmi. Takze, ak mame 0101, tak existuje kod so 4 paritnymi bitmi a 11 datovymi bitmi. Hammingov kod je prikladom perfektneho kodu, kodu ktory presne vyhovuje teoretickej hornej hranici, co sa tyka cisla rozdielnych kodovych slov pre dany pocet bitov a schopnosti opravit chyby.
Spravme si hammingov kod na priklade. Nech mame slova o 4-och bitoch a 3 paritne bity, teda Hammingov kod (7,4). Kodova vzdialenost v tomto pripade bude 3.
informacia a = (a1,a2,a3,a4)
po kodovani bude b = (b1, ..., b7), kde
b1 = a1 xor a2 xor a4
b2 = a1 xor a3 xor a4
b3 = a1
b4 = a2 xor a3 xor a4
b5 = a2
b6 = a3
b7 = a4
takze b1, b2, b4 bude parita. A teraz by nas asi malo zaujimat, ako sme na to preboha prisli. A odpoved nam da algoritmus hammingovho kodu:
- vsetky bitove pozicie, ktorych cislo je rovne mocnine 2 su pouzite ako paritne bity (1,2,4,8 .. )
- vsetky ostatne bitove pozicie su rovne kodovanemu slovu
- kazdy paritny bit je vypocitany z bitov informacneho slova (niektorych)
Nasledne vygenerujeme genrujucu a kontrolnu maticu hammingovho kodu. A toto sme uz nerobili, takze to necham na inokedy ..
