1. Vznik a vývoj teorie informace
2. Matematický aparát v teorii informace• Základy teorie pravděpodobnosti – Náhodné veličiny• Číselné soustavy
3. Informace• Základní pojmy – jednotka a zobrazení informace, informační hodnota• Entropie – vlastnosti entropie• Zdroje zpráv – spojité zdroje zpráv, diskrétní zdroje zpráv• Přenos informace – vlastnosti přenosu kanálů, poruchy a šumy přenosu,
způsoby boje proti šumu
4. Kódování• Elementární teorie kódování• Rovnoměrné kódy – telegrafní kód• Nerovnoměrné kódy – Morseova abeceda, konstrukce nerovnoměrných kódů• Efektivní kódy – Shannonova – Fanova metoda, Hoffmanova metoda
5. Bezpečností kódy • Zabezpečující schopnosti kódů, • Systematické kódy, • Nesystematické kódy
ZÁKLADY INFORMATIKY – ZÁKLADY INFORMATIKY – Systematické a nesystematické bezpečnostní Systematické a nesystematické bezpečnostní kódykódy
Systematické kódySystematické kódy
Kódové slovo obsahuje vedle symbolů nesoucí informaci také symboly zabezpečující
Nezabezpečený kód lze převést na systematický tak, že ke každému kódovému slovu přidáme zabezpečující symboly
Má-li kódové slovo mm míst, z toho k informačních míst a m-km-k zabezpečovacích míst, hovoříme o kódu K(m, k).K(m, k).
Pro systematické kódy platí:
LLzz << LL
Hammingova vzdálenost kódových slov je větší než 1 d(Cd(Cii, C, Cjj))>>11
Optimální kódOptimální kód - takový kód K(m, k)K(m, k) pro nějž neexistuje jiný kód o stejném mm a kk, který by poskytoval větší pravděpodobnost zachycení chyby, tj. který by měl větší zabezpečovací schopnost.
Těsný kód (perfektní)Těsný kód (perfektní) - takový kód, který pro dané mm a kk využívá kódová slova vzdálená vzájemně o předpokládanou minimální Hammingovu vzdálenost
dd(C(Cii, C, Cjj) ) min min
ttěsný kód je zároveň kódem optimálníměsný kód je zároveň kódem optimálním
Rozdělení bezpečnostních kódůRozdělení bezpečnostních kódů
LineárníLineární – libovolná kombinace kódových slov je opět kódovým slovem
Lineární systematickéLineární systematické – informační a zabezpečující místa v kódovém slově jsou oddělena (Slepianovy kódy)
Ostatní lineárníOstatní lineární – informační a zabezpečující místa jsou rozložena na různých místech kódového slova (Hammingovy kódy, cyklické kódy atd.)
NelineárníNelineární
Řetězové (rekurentní)Řetězové (rekurentní)
InversníInversní
ParitníParitní (s vnitřní a vnější paritou)
IteračníIterační (s blokovou paritou)
Paritní kódParitní kód
velmi jednoduchý, přitom však účinný a pružný způsob zabezpečení,
Princip spočívá v zajištění konstantní hodnoty součtu všech symbolů každého kódového slova (mod2)
konstam
ii
)(mod2
1
Platnost předchozí podmínky zajistíme doplněním každého kódového slova, které chceme zabezpečit, jedním nebo několika zabezpečovacími koeficienty aaii.
Hodnota koeficientu aaii je u binárního kódubinárního kódu pochopitelně 0 nebo 11
V případě binárního kódu přidáváme ke kódovému slovu znak 0 nebo 1 tak, aby výsledné kódové slovo mělo:
sudý počet jedniček (konst=0) - sudá parita
lichý počet jedniček (konst=1) - lichá parita
• Zabezpečení paritou lze provést pro libovolně dlouhé kódové slovo.
• Paritou lze zabezpečit kód i dodatečně.
• Např. uvnitř stroje se pracuje s nezabezpečeným kódem, pro přenos sdělovací cestou se provede paritní zabezpečení. Po kontrole na přijímací straně se paritní koeficienty odstraní a v dalším stroji se opět pracuje s nezabezpečeným kódem.
Příklad:
Zabezpečte paritním kódem trojmístný binární kód. Využijte sudou i lichou paritu.
Zabezpečené kódové slovo sudou paritousudou paritou konst
0 0 0 0 0 0 00 00
0 0 1 0 0 1 11 00
0 1 0 0 1 0 11 00
0 1 1 0 1 1 00 00
1 0 0 1 0 0 11 00
1 0 1 1 0 1 00 00
1 1 0 1 1 0 00 00
1 1 1 1 1 1 11 00
Zabezpečené kódové slovo lichou paritoulichou paritou konst
0 0 0 0 0 0 11 11
0 0 1 0 0 1 00 11
0 1 0 0 1 0 00 11
0 1 1 0 1 1 11 11
1 0 0 1 0 0 00 11
1 0 1 1 0 1 11 11
1 1 0 1 1 0 11 11
1 1 1 1 1 1 00 11
Předchozí kód se označuje KK((4,34,3)) - 3 znaky nesou informaci, 1 znak je redundantní a slouží k zabezpečení kódu.
Jaká je minimální Hammingova vzdálenost předchozího kódu ???
Na základě vztahů pro detekční a korekční schopnosti kódů lze stanovit, že výsledný kód objevuje všechny jednoduché (1-násobné) chyby ale nedokáže takové chyby opravit.
dd(C(Cii, C, Cjj) ) min min = 2 = 2
Iterační kódyIterační kódy
Kombinace dvou nebo více zabezpečujících kódů
Princip spočívá v tom, že zabezpečíme posloupnost kódových slov paritou v příčném a podélném směru – maticové zabezpečenímaticové zabezpečení
Takto zabezpečujeme celé skupiny (bloky) kódových slov - mluvíme spíše o zabezpečení zprávy
Na blok pohlížíme jako na jediné kódové slovo
Minimální Hammingova vzdálenost kódových slov maticově zabezpečeného kódu je rovna součinu minimálních vzdáleností dílčích kódů
minSjiminŘjiminMji )C,C(d)C,C(d)C,C(d
Příklad:
Zabezpečte iteračním kódem blok pěti kódových slov, které tvoří zprávu. Jednotlivá slova jsou dána takto: 11000, 00101, 10011, 01111, 10101. Využijte maticového zabezpečení.
Nezabezpečené kódové slovoZabezpečení
řádkové
1 1 0 0 01 1 0 0 0 00
0 0 1 0 10 0 1 0 1 00
1 0 0 1 11 0 0 1 1 11
0 1 1 1 10 1 1 1 1 00
1 0 1 0 11 0 1 0 1 11
11 0 1 0 00 1 0 0Zabezpečení sloupcové
00Kontrolní Kontrolní
symbolsymbol
Lineární kódy se vyznačují tím, že libovolná lineární kombinace kódových slov je opět kódovým slovem.
U binárních lineárních kódů je možné využít následujících pravidel pro operace sčítání a násobení binárních čísel.
Lineární kódyLineární kódy
00 11
00 00 11
11 11 00
00 11
00 00 00
11 00 11
Pro sčítání platí Pro násobení platí
Lineární kód tvoří lineární podprostor n-rozměrného prostoru binárních proměnných.
Tento podprostor je možné popsat jeho bází. bází.
Každý prvek báze je sám kódovým slovemsám kódovým slovem. Chceme-li nalézt kódová slova lineárního binárního kódu, stačí, když nalezneme bázi kódu.
Báze by měla být tvořena kódovými slovy s co nejmenším počtem jedniček a tato kódová slova musí být vzájemně nezávislá.
Ostatní kódová slova lineárního kódu mohou být získána sčítáním popř. násobením dvou slov báze.
Kódová slova bázeKódová slova báze zapsána pod sebe tvoří
- - generující matici Ggenerující matici G
kn1k
n111
g...g
::
g...g
G
Pro matici GG musí platit:
• každý její řádek je kódovým slovem,
• každé kódové slovo je lineární kombinací řádků,
• řádky jsou lineárně nezávislé (hodnost matice G=kG=k).
1
1
1
100
010
001
G
0
0
0
101
110
011
G
Příklad: Sestrojte generující matici pro systematický kód celkové parity (sudá parita) K(4,3). Získejte další kódová slova tohoto kódu.
1010CCC
1100CCC
315
214
0110CCC
1010CCC
315
214
Pozn. Kód liché parity není lineární (11011110=0011)
Většinou tvoří nezabezpečená kódová slova jednotkovou Většinou tvoří nezabezpečená kódová slova jednotkovou matici. Zabezpečovací místa vytváříme podle algoritmu matici. Zabezpečovací místa vytváříme podle algoritmu daného kódování. Seřadíme-li takto vytvořená zabezpečená daného kódování. Seřadíme-li takto vytvořená zabezpečená slova do řádků a uzavřeme do maticeslova do řádků a uzavřeme do matice - - generující matici generující matici systematického kódu Gsystematického kódu G
EEkk – jednotková matice řádu kk
RR – matice zabezpečujících prvků (rr zabezpečujících prvků)
Kódy u kterých lze generující matici zapsat jako součin jednotkové matice a matice zabezpečujících prvků - - systematické kódysystematické kódy
R|E
r...rr
::
rr
r...rr
1...00
::
0...10
0...01
G k
krk2k1
2r21
1r1211
1. Vysílané zabezpečené kódové slovo zz (1(1xxm)m) se vytváří z nezabezpečeného kódového slova v (v (11xxk)k) pomocí generující matice GG:
Gvz 2. Přijímané zabezpečené kódové slovo p (1p (1xxm)m) se bude rovnat vysílanému
kódovému slovu zz tehdy, jestliže:
0HzpH TT
Matice HH je kontrolní matice (r(rxxmm).). Definovaná je pomocí generující matice systematických kódů G=G=[[EEkk | | RR]]::
rT E|RH
3. Kontrolní matice se využívá při dekódování zpráv, zda při přenosu kódované informace nedošlo k chybě. Pro objevování případně i opravu chyb se používá vektor s (1 s (1 xx r) r) zvaný syndrom slova (soubor příznaků) a je definován jako:
Hps T
Princip (algoritmus) kódování a dekódování pomocí generující matice G:Princip (algoritmus) kódování a dekódování pomocí generující matice G:
jestli s = 0s = 0 bezchybný přenos
s s ≠ 0≠ 0 chyba v přenosu
Příklad: Zabezpečte sedmimístné kódové slovo sudou paritou. Použijte teorie lineárních systematických kódů. Studujte možnosti chybného popř. bezchybného přenosu.
Jedná se tedy o kód K(8,7).K(8,7). Generující matici GG můžeme zapsat ve tvaru:
11000000
10100000
10010000
10001000
10000100
10000010
10000001
1
1
1
1
1
1
1
1000000
0100000
0010000
0001000
0000100
0000010
0000001
R|EG k
Uvažujme, že vysílané zdrojové nezabezpečené kódové slovo odpovídá písmenu J v ASCII kódu – 0101001. Po zabezpečení pomocí generující matice dostáváme:
11001010
11000000
10100000
10010000
10001000
10000100
10000010
10000001
1001010Gvz
Kontrolní matice HH má u tohoto kódu tvar:
1111111 1E|RH rT
Pro přijímané zabezpečené slovo p (1 p (1 xx 8) 8) musí pak platit:
0pppppppp
0
1
1
1
1
1
1
1
1
pppppppp 0Hps
87654321
87654321T
Podle syndromu ss, který získáme výpočtem podle předchozího vzorce, můžeme rozhodnout o bezchybném přenosu. Např.:
Přijaté kódové slovoPřijaté kódové slovo Syndrom slovaSyndrom slova
0 1 0 1 0 0 1 10 1 0 1 0 0 1 1 => Bezchybný přenos
0 1 0 1 0 0 1 00 1 0 1 0 0 1 0 => Chyba při přenosu
0 1 1 1 0 0 1 10 1 1 1 0 0 1 1 => Chyba při přenosu
101001010s
111001110s
011001010s
Příklad: Mějme dvojkový binární kód K(5,3)K(5,3), u kterého je zadána kontrolní matice H . Podrobte kontrole přijatá kódová slova 01111, 01111, 0111001110.
Ke kontrole použijeme výpočet syndromu ss ve tvaru:
10101
01011H
531
42154321
T
ppp
ppp
10
01
10
01
11
pppppHps
0
0
10
01
10
01
11
11110s(01111)
1
0
10
01
10
01
11
01110s(01110)
Chybný přenos Chybný přenos BeBezzcchybný přenoshybný přenos
Hammingovy kódy jsou lineární kódy, které jsou určeny pro zabezpečování údajů ukládaných do pamětí počítačů, resp. pro přenosové kanály s nezávislými chybami.
• Lineární binární kódy se schopností opravy chyb.
• Tyto bezpečnostní kódy mají nejmenší možnou redundanci.
• Snadno se dekódují a jsou perfektníperfektní
• Hammingova vzdálenost je dána ddminmin= 3 = 3 (detekuje 2-násobnou chybu a opravuje jednu chybu)
Hammingovy kódyHammingovy kódy
Hammingův binární kód s rr kontrolními znaky (r = 2, 3, 4, …) (r = 2, 3, 4, …) má délku kódového slova 22rr-1-1. Takže vzniká kód K(3,1), K(7,4), K(15,11),K(3,1), K(7,4), K(15,11), atd.
r (m-k)r (m-k) 2 3 4 5 6 …
mm 3 7 15 31 63
kk 1 4 11 26 57
Kód byl sestaven tak, aby syndrom ss, pokud není nulový, udával svými prvky polohu chybného místa v kódovém slově.
Prvky vektoru syndromu ss jsou chápány jako zápis čísla ve dvojkové soustavě: 02r1r 222
]s...ss[s 11rr
Je proto výhodné uspořádat sloupce kontrolní matice H H tak, aby v i-tém sloupci bylo dvojkové vyjádření čísla i.
Binární kód se nazývá Hammingův jestliže má kontrolní matici, jejíž sloupce jsou všechna nenulová slova dané délky a žádné z nich se neopakuje.(používá se binární rozvoj čísel 1, 2, 3, …, 2r-1)
Pro r = 2 dostáváme kód K(3,1) s kontrolní matici ve tvaru:
101
110H Taková matice je kontrolní maticí opakovacího kódu
délky 3. Ten skutečně opravuje jednoduché chyby
Pro r = 3 dostáváme kód K(7,4) s kontrolní matici ve tvaru:
1010101
1100110
1111000
H
Abychom našli generující matici, musíme přemístit sloupce do tvaru:
rT E|RH'
100
010
001
1101
0111
1011
H'Tzn.
Došlo k přehození sloupců:
1-7, 2-6, 4-5
Protože se jedná o nesystematický kód
Generující matici GG’’ dostaneme ze vzorce: GG’=[E’=[Ekk|R]|R]
101
110
011
111
1000
0100
0010
0001
G'
Zpětným přeházením sloupců dostaneme generující matici původního Hammingova kódu:
001
000
010
100
1001
0111
1010
1011
G
Došlo k přehození sloupců:
1-7, 2-6, 4-5
Pro dekódování Hammingova kódu se využívá opět Pro dekódování Hammingova kódu se využívá opět syndromu syndromu s, s, pro kterýpro který platí:platí:
TTTTTT HcHc0HcHzHczHps
- při jednonásobné chybě vektor chyb - c pouze jednu jedničku.
Z toho vyplývá, že syndrom ss bude roven řádku matice HHTT, který odpovídá jedničce v chybovém vektoru cc a bude udávat pořadové číslo místa chybného znaku.
Příklad: Které z přijatých kódových slov 1100111, 0110101, 0011001 je chybné při použití Hammingova kódu K(7,4). V případě chyby určete místo výskytu chyby.
Pro kód K(7,4) dostáváme kontrolní matici ve tvaru:
1010101
1100110
1111000
H
Syndrom přijatého kódového slova je pak dán:
0
0
0
H1001100s(0011001) T
0
111
011
101
001
110
010
100
Hps T
7654321 ppppppp
1
1
1
H1110011s(1100111) T
1
1
0
H1010110s(0110101) T
Chybný přenos (poslední místo)Chybný přenos (poslední místo) Chybný přenos (třetí místo)Chybný přenos (třetí místo)
Bezchybný přenos Bezchybný přenos
Pro syndrom jednotlivých přijatých kódových slov pak platí:
Kde se nachází zabezpečující místa kódového slova v Kde se nachází zabezpečující místa kódového slova v Hammingových kódech s d=3 ?Hammingových kódech s d=3 ?
Uvažujme zabezpečené kódové slovo v obecném tvaru: z = z = aa1 1 aa2 2 aa3 3 aa4 4 aa5 5 aa6 6 aa77
Při bezchybném přenosu platí z = pz = p a dále platí: 0HzHps TT
0
111
011
101
001
110
010
100
Hzs T
7654321 aaaaaaa
Pokud sestrojíme kontrolní matici kódu K(7,4)K(7,4) a dosadíme do předchozí rovnice dostáváme:
0
0
0
7531
7632
7654
aaaa
aaaa
aaaa jako zabezpečující místa vybereme jako zabezpečující místa vybereme ty místa, které se vyskytují vždy jen ty místa, které se vyskytují vždy jen v jedné rovnici, tzn. kontrolními v jedné rovnici, tzn. kontrolními místy budou místa místy budou místa aa11, a, a22, a, a44..
Příklad: Sestrojte kódová slova Hammingova kódu K(7,4).
Pro každé kódové slovo musí platit následující soustava rovnic:
0
0
0
7531
7632
7654
aaaa
aaaa
aaaa
0 00 0 0 0 00 0 0 0 0 0 0 1 01 0 0 0 11 1 0 0 1 0 0 1 11 1 1 1 00 0 0 0 0 0 0 0 10 1 1 1 11 1 0 0 1 0 0
1 11 1 0 0 11 0 0 1 0 0 1 0 10 1 0 0 00 1 0 1 1 0 1 0 00 0 1 1 11 0 0 1 0 0 1 1 01 0 1 1 00 1 0 1 1 0 1
0 10 1 0 0 11 0 1 0 0 1 0 1 11 1 0 0 00 1 1 0 1 1 0 1 01 0 1 1 11 0 1 0 0 1 0 0 00 0 1 1 00 1 1 0 1 1 0
1 01 0 0 0 00 0 1 1 0 1 1 0 00 0 0 0 11 1 1 1 1 1 1 0 10 1 1 1 00 0 1 1 0 1 1 1 11 1 1 1 11 1 1 1 1 1 1
zabezpečující místa zabezpečující místa jsou jsou aa11, a, a22, a, a44. =. =>>
7531
7632
7654
aaaa
aaaa
aaaa
Tzn. místa 3, 5, 6, 7 budou tvořit všechna binární slova délky 4 a místa 1, 2, 4 budou kontrolní!!!
• Lineární binární kódy se schopností opravy chyb.
• Tyto bezpečnostní kódy již nemají nejmenší možnou redundanci = nejsou perfektníperfektní
• Hammingova vzdálenost je dána ddminmin= 4 = 4 (detekuje 3-násobnou chybu a opravuje jednu chybu)
Rozšířený Hammingův kódRozšířený Hammingův kód
Rozšířený Hammingův binární kód s rr kontrolními znaky (r = 3, 4, …) (r = 3, 4, …) má délku kódového slova 22r-1r-1. Takže vzniká kód K(4,1), K(8,4), K(16,11),K(4,1), K(8,4), K(16,11), atd.
r (m-k)r (m-k) 3 4 4 6 7 …
mm 4 8 16 32 64
kk 1 4 11 26 57
• Kontrolní matici tohoto kódu získáme z kontrolní matice Hammingova kódu tak, že ke každému řádku přidáme paritní bit sudé parity a do kontrolní matice doplníme řádek jedniček.
Příklad: Sestrojte kontrolní matici rozšířeného Hammingova kódu K(8,4). Které z přijatých kódových slov 11001011, 00000011, 00011110 je chybné? V případě jedné chyby určete místo výskytu chyby. Pokuste se sestrojit celý kód.
Pro Hammingův kód K(7,4) dostáváme kontrolní matici ve tvaru:
1010101
1100110
1111000
H
Syndrom přijatého kódového slova je pak dán:
0
1000
1111
1011
1101
1001
1110
1010
1100
Hps TR
87654321 pppppppp
Pro rozšířený Hammingův kód K(8,4) dostáváme pak kontrolní matici ve tvaru:
11111111
0
0
0
1010101
1100110
1111000
HR
1
1
0
0
H11010011)s(11001011 T
Chybný přenos (první místo)Chybný přenos (první místo)
Chybný přenos (více jak jedna chyba)Chybný přenos (více jak jedna chyba)
Bezchybný přenos Bezchybný přenos
Pro syndrom jednotlivých přijatých kódových slov pak platí:
Příklad: Sestrojte kontrolní matici rozšířeného Hammingova kódu K(8,4). Které z přijatých kódových slov 11001011, 00000011, 00011110 je chybné? V případě jedné chyby určete místo výskytu chyby. Pokuste se sestrojit celý kód.
0
1
1
1
H11000000)s(00000011 T
0
0
0
0
H01111000)s(00011110 T
1000
1111
1011
1101
1001
1110
1010
1100
H TR
• patří k nejmodernějším lineárním bezpečnostním kódům, které se osvědčily v praxi
• schopnost zabezpečovat shluky chyb
• podle způsobu manipulace s kódovým slovem se také označují – polynomické kódy
Kódová slova Ci (a0 a1 a2 …am-1) můžeme totiž chápat jako zkrácený zápis polynomu stupně m-1:
C(z) = a0 + a1z + a2z2 +…+ am-1zm-1
• jejich specifická vlastnost, podle které se také nazývají, spočívá v tom, že:
cyklickou záměnou prvků v použitém kódovém slově vzniká opět platné kódové slovo.
Cyklické kódyCyklické kódy
Je-li kódové slovo C1 platným kódovým slovem
C1 = a0 a1 a2 a3 …am-1
Pak pro cyklický kód jsou platnými kódovými slovy i kódová slova
C2 = am-1 a0 a1 a2 a3 …am-2
C3 = am-2 am-1 a0 a1 a2 a3 …am-3
Při práci s polynomy pak cyklický posun prvků kódového slova odpovídá násobení polynomu proměnnou z:
C2 (z) = z . C1(z) = a0 z + a1z2 + a2z3 + a3z4 …am-1zm
Přesun koeficientu u nejvyšší mocniny na začátek kódového slova vyřešíme zavedením:
zm = 1 zm+1 = z zm+2 = z2 …
Příklad:
Pomocí polynomického vyjádření (násobení proměnnou z) sestrojte další kódová slova k 11001011.
C1(z) = 1 + z + z4 +z6+z7
C2(z) = z .C1(z) = z + z2 + z5 +z7+z8 = 1 + z + z2 + z5 +z7
C3(z) = z .C2(z) = z + z2 + z3 +z6+z8 = 1 + z + z2 + z3 +z6
Cyklický kód můžeme definovat pomocí generujícího polynomu g(z).
Generující polynom cyklického kódu K(m,k)K(m,k) je polynom stupně m-k=r, který
musí dělit (být dělitelem) polynom (musí dělit (být dělitelem) polynom (zzmm-1-1)). .
Cyklickým posunem koeficientů generujícího polynomu vzniká generující matice G(z)generující matice G(z)
1k
km21
km-
0
1-km-10
km-210
ggg
00g
000
g000
ggg0
gggg
G
Řádky tvoří polynomy:g(z)z.g(z)..zk-1.g(z)
Kontrolní matici cyklického kódu K(m,k) získáme cyklickými posuvy koeficientů kontrolního polynomu čteného od nejvyšší mocniny
U cyklických kódů můžeme kontrolní matici nahradit kontrolním polynomem:
g(z)
1zh(z)
m
000hh
0hhhh
hhhhh
hhh
h00
000
H
01
012-k1-k
012-k1-kk
1km-
21-kk
k
Kontrolní matice má m-km-k řádků
Pro každý polynom v(z), který představuje zabezpečené kódové slovo a pro který platí:
v(z) . h(z) = 0
Splňuje kontrolní matice podmínku:
H . vT = 0T
Příklad:
Sestrojte kód celkové parity (sudá parita) délky 4, tedy K(4,3) pomocí polynomického vyjádření cyklického kódu. Najděte generující polynom a generující matici tohoto kódu. Najděte dále kontrolní polynom a kontrolní matici.
R.Farana: Kapitoly ze základů informatiky, str.29, příklad 1.
Příklad: Z dříve uvedených poznatků vyplývá, že každý cyklický kód rozkládá polynom zm-1 na součin g(z).h(z). To platí i naopak. Popište všechny binární cyklické kódy délky 5. (R.Farana: Kapitoly ze základů informatiky, str.30, příklad 3.)
Musí platit:
z5-1=g(z).h(z) tzn. hledáme všechny polynomy g(z) a h(z).
V našem případě je možné polynom (z5-1) rozložit na dva polynomy takto:
z5-1= (z+1).(z4+z3+z2+z+1)
Odtud dostáváme dva kódy:
1. Kód celkové kontroly parity: g(z)= (z+1) h(z)=(z4+z3+z2+z+1)
2. Opakovací kód: g(z)= z4+z3+z2+z+1) h(z)=(z+1)
1. nezabezpečené kódové slovo v (v (11xxk)k) čteme pozpátku (neboli polynomy zapisujeme od nejvyšší mocniny, tedy opačně než doposud). Z informačních bitů v0 v1 v2 … vk-1 vytvoříme tedy polynom:
v(z) = v0zm-1 + v1zm-2 + … +vk-1zm-k
2. Předchozí polynom dělíme generujícím polynomem g(z) a dostáváme:
Úpravou dostaneme:
g(z)
r(z)q(z)
g(z)
v(z)
Princip (algoritmus) kódování a dekódování pomocí cyklického kóduPrincip (algoritmus) kódování a dekódování pomocí cyklického kódu
zrv(z)C(z) zgzqzrv(z)
Při označení polynomu zbytku ve tvaru:
r(z) = rkzm-k-1 + rk+1zm-k-2 + … +rm-1z + rm
Vyšleme kódové slovo C = v0 v1 … vk-1 rk rk+1 … rm
3. Správnost přenosu lze na přijímací straně kontrolovat dělením polynomu p(z) – polynom přijatého kódového slova, generujícím polynomem g(z). (e(z) – chybový polynom)
Princip (algoritmus) kódování a dekódování pomocí cyklického kóduPrincip (algoritmus) kódování a dekódování pomocí cyklického kódu
Jestliže:Jestliže:
e(z) e(z) dělí g(z) beze zbytku - bezchybný přenos
e(z) e(z) nedělí g(z) beze zbytku - chyba v přenosu
Tvar zbytku neboli syndrom s(z) nám určuje místo chyby podle následující tabulky
g(z)
e(z)q(z)
g(z)
e(z)r(z)v(z)
g(z)
p(z)
Místo výskytu Místo výskytu chybychyby 00 11 zz zz22 zz33 zz44 zz55
Tvar zbytkuTvar zbytku Bez chyby 11 zz zz2 2 modmodg(z)g(z) zz3 3 modmodg(z)g(z) zz4 4 modmodg(z)g(z) ……
Příklad: U kódu K(7,4) zakódujte kódové slovo 1010 pomocí cyklického kódu. Proveďte kontrolu přijetí zabezpečeného kódového slova. Zvolte si náhodně chybu v kódovém slově a proveďte znovu kontrolu a nalezení chyby.
Řešení: 1) najdeme generující polynom: (musí být stupně m-k tj. 3 a musí dělit polynom z7-1 beze zbytku)
Všechny možnosti polynomu 3 stupně jsou:
z3, z3+1, z3+z, z3+z2, zz33+z+1+z+1, z3+z2+1, z3+z2+z, z3+z2+z+1
z7-1 : z3+z+1 = z4+z2+z+1z7+z5+z4
z5+z4+1 z5+z3+z2
z4+z3+z2+1 z4+z2+z z3+z+1 z3+z+1 0
2) Nezabezpečené kódové slovo převedeme na polynom:
1010 → v(z)=z6+z4
Příklad: U kódu K(7,4) zakódujte kódové slovo 1010 pomocí cyklického kódu. Proveďte kontrolu přijetí zabezpečeného kódového slova. Zvolte si náhodně chybu v kódovém slově a proveďte znovu kontrolu a nalezení chyby.
3) Předchozí polynom dělíme generujícím polynomem:
z6+z4 : z3+z+1 = z3+1z6+z4+z3
z3
z3+z+1 z+1 - zbytek
4) Polynom zbytku nám udává zabezpečující část kódového slova:
r(z)=z+1 → 011
5) Sestavíme celé zabezpečené kódové slovo:
C= 1010 011
Příklad: U kódu K(7,4) zakódujte kódové slovo 1010 pomocí cyklického kódu. Proveďte kontrolu přijetí zabezpečeného kódového slova. Zvolte si náhodně chybu v kódovém slově a proveďte znovu kontrolu a nalezení chyby.
Kontrola přijetí zabezpečeného kódového slova:
1010011 → p(z)=z6+z4+z+1
z6+z4+z+1 : z3+z+1 = z3+1z6+z4+z3
z3+z+1 z3+z+1 0 - zbytek→správný přenos
Kontrola přijetí zabezpečeného kódového slova s chybou:
10100001 → p(z)=z6+z4+1z6+z4+1 : z3+z+1 = z3+1z6+z4+z3
z3+1 z3+z+1 z - zbytek→nesprávný přenos
(chyba je na pozici z)
Příklad: U kódu K(7,4) zakódujte kódové slovo 1010 pomocí cyklického kódu. Proveďte kontrolu přijetí zabezpečeného kódového slova. Zvolte si náhodně chybu v kódovém slově a proveďte znovu kontrolu a nalezení chyby.
Kontrola přijetí zabezpečeného kódového slova:
10000011 → p(z)=z6+z4+z+1
z6+z+1 : z3+z+1 = z3+z+1z6+z4+z3
z4+z3+z+1 z4+z2+z _ z3+z2+1 z3+z +1
z2+z - zbytek→nesprávný přenos
(chyba je na pozici n, kde platí že zbytek po dělení zn: z3+z+1 je stejný jako získaný zbytek z2+z) – chyba je tedy na pozici z4 (viz níže)
z6 : z3+z+1 = z3+z+1 z6+z4+z3
z4+z3
z4+z2+z z3+z2+z z3+z +1 z2+1 – zbytek který odpovídá pozici zz66
z4 : z3+z+1 = z+1 z4+z2+z z2+z – zbytek který odpovídá pozici zz44
Používání cyklických kódů se v poslední době velmi rozšířilo.
Hlavním důvodem je schopnost cyklických kódů odhalovat shluky chyb (chyby v přenosových kanálech mají tendenci vyskytovat se blízko sebe a vytvářet tzv. shluky).
Tabulka nejrozšířenějších kódů CRC (Cyclic Redundance Code)
Počet kontrolních
bitů
Označení Generující polynom Použití
8 LRCG - 8 x8+1
12 CRC - 12 x12+ x11+ x3+ x2+ x+1 pro 6 bitové znaky
16 CRC - 16 x16+ x15+ x2+1 binární synchronní protokol
16 CDLC x16+ x12+ x5+1 linkový protokol IBM
32 CRC - 32 x32+ x26+ x23+ x22+ x16+ x12+ x11+ x10+ x8+ x7+ x5+ x4+ x2+ x+1
ETERNET sítě , Z-modem
Je to lineární binární kód, který opravuje volitelný počet chyb.
Je důležitý hlavně kvůli své jednoduchosti a jednoduše implementované metodě dekódování.
Byli objevené v roku 1954 a v porovnaní s BCH kódy mají slabší parametry .
Jsou prakticky významné (například kód RM (1,5) použil kosmický koráb Mariner 9 při vysílání fotografií z Marsu.
Reedovy-Mullerovy kódyReedovy-Mullerovy kódy
Jsou to obecné kódy s dobrými parametry.
Je to nejdůležitější třída cyklických bezpečnostních kódů
Mezi hlavní parametry patří:• velká volitelnost parametrů,
• jednoduchý vztah mezi počtem informačních znaků a počtem opravených chyb
• detailně vypracované dekódovací metody.
BCH kódy opravují dvojnásobné a vícenásobné chyby.
BCH kódyBCH kódy
V porovnání s REED-MULLERovými kódy mají BCH kódy o něco náročnější dekódování, ale za to mají lepší parametry.
Jsou speciálním případem BCH kódů.
Mají největší myslitelnou vzdálenost a dají se pomocí nich sestrojit dobré binární kódy.
Reed – Solomonovy kódyReed – Solomonovy kódy
Golayův kódGolayův kód
Je to jediný perfektní kód pro trojnásobné opravy.
Tento kód se zavádí pomocí generující matice.
Inversní kód patří do blokových, systematických, nelineárních kódů.
Inversní Inversní kódkód
Tento kód má Hammingovou kódovou vzdálenost d = 4. Z rovnice vyplývá, že může objevovat až trojnásobné chyby a z rovnice vyplývá, že může opravovat jednoduché chyby.
Prvním krokem postupu při použití inverzního kódu je, že vysílané nezabezpečené kódové slovo se zopakuje beze změny, je-li v něm sudý počet nul.
V případě, že je v něm počet nul lichý, vyšle se v druhé části inverze nezabezpečeného kódového slova.
Tak se zabezpečené kódové slovo bude skládat z dvou částí:
informační informační aa zabezpečovací zabezpečovací..
Princip si vysvětlíme na přenosu znaků G, L, X zakódovaných telegrafním kódem, které chceme zabezpečit inverzním kódem.
Způsob kódování je podrobně zobrazený v tabulce: G L X
Vyslané kódové slovo 01011 01011 01001 10110 10111 01000
Přijaté kódové slovo 000011 01011 010111 10110 10111 000000
Zaznamenané kód.slovo 00011 10100 01011 10110 10111 11111
Rozbor 00011 01011 10111
10100 10110 11111
místo korekce 100111 111001 011000
chyba chyba chyba
Dojde-li k chybě v informační části, pak při součtu mod 2 se shoduje jediný pár prvků (bitů) v místě chyby (u znaků G a L).
Nachází-li se chybný prvek v zabezpečovací části, pak při součtu mod 2 se pár prvků v místě chyby neshoduje (u znaku X).