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