[1]
´ Uvod do ko´dova´nı´ • samoopravne´ ko´dy: terminologie, princip • blokove´ linea´rnı´ ko´dy • Hammingu˚v ko´d • cyklicke´ ko´dy
a) kody, 18, b) P. Olsˇa´k, FEL CˇVUT, c) P. Olsˇa´k 2010, d) BI-LIN, e) L, f) 2009/2010, g)
L
. Viz p. d. 4/2010
BI-LIN, kody, 18, P. Olsˇa´k
[2]
Samoopravne´ ko´dy, k cˇemu to je • Data jsou ulozˇena (nebo posı´la´na do linky) kode´rem podle urcˇite´ho pravidla (ko´dova´nı´). Posle´ze jsou cˇtena dekode´rem a restaurova´na do pu˚vodnı´ podoby. • Kode´r mu˚zˇe prˇidat k datu˚m doplnˇujı´cı´ informaci (zhruba rˇecˇeno kontrolnı´ soucˇet) a umozˇnit tı´m dekode´ru, aby poznal, zda prˇi prˇenosu dat dosˇlo k chybeˇ. Dokonce prˇi vhodneˇ zvolene´m ko´dova´nı´ mu˚zˇe dekode´r chybu opravit. Ko´d je mnozˇina slov (tj. u´seku˚ dat), ktere´ mu˚zˇe generovat kode´r. Prˇı´klady ko´du ˚: • ASCII (slova sedmibitova´, ne vsˇechna) • Morseova abeceda (slova ru˚zneˇ dlouha´, efektivnı´ prˇenos) • UTF-8 (slova ru˚zneˇ dlouha´, de´lka rozpoznana´ podle prefixu)
BI-LIN, kody, 18, P. Olsˇa´k
Bina´rnı´, blokovy´ ko´d je ko´d, kde jsou vsˇechna slova stejneˇ dlouha´. Definice: Necht’ A je mnozˇina znaku˚ (abeceda). Slovo je konecˇna´ posloupnost znaku˚ z mnozˇiny A. Pocˇet znaku˚ ve sloveˇ je de´lka slova. Ko´d K je mnozˇina vsˇech slov, ktera´ generuje kode´r. Prvek ko´du K se nazy´va´ ko´dove´ slovo. Blokovy´ ko´d K obsahuje jen slova stejne´ de´lky. Bina´rnı´ ko´d je ko´d se slovy nad abecedou A = {0, 1}. Prˇı´klady: • ASCII je bina´rnı´ blokovy´ ko´d de´lky 7. • Moreseovka nenı´ bina´rnı´ a nenı´ blokovy´ ko´d. • UTF-8 je bina´rnı´, ale ne blokovy´ ko´d. Da´le se budeme zaby´vat jen bina´rnı´mi blokovy´mi ko´dy
[3]
BI-LIN, kody, 18, P. Olsˇa´k
[4]
Linea´rnı´ ko´d Bina´rnı´ blokovy´ ko´d K de´lky n je podmnozˇinou lin. prostoru Zn2 . Definice: Je-li K liena´rnı´ podprostor Zn2 , pak se ko´d nazy´va´ linea´rnı´. Je-li dimenze ko´du k, pak mluvı´me o linea´rnı´m (n, k) ko´du. Prˇı´klad: Ko´d s kontrolnı´m bitem parity je linea´rnı´. Kode´r prˇida´va´ nulu nebo jednicˇku k informacˇnı´m bitu˚m tak, aby ko´dove´ slovo obsahovalo sudy´ pocˇet jednicˇek. Mnozˇina vsˇech slov de´lky n se sudy´m pocˇtem jednicˇek je linea´rnı´ podprostor linea´rnı´ho prostoru Zn2 .
BI-LIN, kody, 18, P. Olsˇa´k
[5]
Generujı´cı´ a kontrolnı´ matice Generujı´cı´ matice linea´rnı´ho ko´du K je matice, ktera´ v rˇa´dcı´ch obsahuje ba´zi ko´du. Kontrolnı´ matice linea´rnı´ho ko´du K je matice H, pro kterou platı´, zˇe K je rˇesˇenı´m soustavy H x = o. Prˇı´klad: Prˇedpokla´dejme linea´rnı´ (4, 3) ko´d s kontrolnı´m bitem parity (prˇida´vany´ na konec slova za trˇi informacˇnı´ bity). Generujı´cı´ matice G a kontrolnı´ matice H jsou: 1 0 0 1 G = 0 1 0 1, H = (1 1 1 1) 0 0 1 1 Pozorova´nı´: Generujı´cı´ matice (n, k) ko´du je typu (k, n) a kontrolnı´ matice je typu (n − k, n). Platı´: G ⋅ HT = O.
BI-LIN, kody, 18, P. Olsˇa´k
[6]
Vy´pocˇet jedne´ matice, zna´me-li druhou Je-li da´na generujı´cı´ (resp. kontrolnı´) matice, vyrˇesˇ´ıme homogennı´ soustavu rovnic s touto maticı´ a ba´zi rˇesˇenı´ zapı´sˇeme do rˇa´dku˚ kontrolnı´ (resp. generujı´cı´) matice. Pro systematicky´ ko´d dokonce platı´: Je-li G = (E | C), pak H = (CT | E0).
BI-LIN, kody, 18, P. Olsˇa´k
[7]
Kode´r a dekode´r − Kode´r lin. (n, k) ko´du mu˚zˇe prˇevzı´t ko´dovane´ slovo → u (de´lky k) a − vytvorˇit z neˇj ko´dove´ slovo → v (de´lky n) maticovy´m na´sobenı´m: → − − v =→ u ⋅ G. − Dekode´r mu˚zˇe zkontrolovat prˇijate´ slovo → w pomocı´ testu: − H⋅→ w = o. T
− Ko´dova´nı´ je systematicke´, jsou-li informacˇnı´ bity (ze slova → u ) beze zmeˇny zkopı´rova´ny do ko´dove´ho slova a za nimi na´sledujı´ kontrolnı´ bity. Pak mu˚zˇe dekode´r (po provedene´m testu) rekonstruovat informacˇnı´ bity zkopı´rova´nı´m prvnı´ch k pozic prˇijate´ho slova. Pozorova´nı´: Ko´dova´nı´ je systematicke´, je-li generujı´cı´ matice tvaru G = (E | C). Prˇida´vane´ kontrolnı´ bity pak kode´r spocˇ´ıta´ po0 − − mocı´ vzorce → v =→ u ⋅ C.
BI-LIN, kody, 18, P. Olsˇa´k
[8]
Prˇı´klad: opakovacı´ ko´d − Kode´r vezme ko´dovane´ slovo → u de´lky k a vytvorˇ´ı ko´dove´ slovo − − de´lky n = 2k tak, ko´dove´ slovo je tvaru (→ u,→ u ), tj. ko´dovane´ slovo je zdvojene´. Generujı´cı´ matice tohoto ko´du je G = (E | E) a kontrolnı´ matice je take´ tvaru H = (E | E). Uveˇdomte si, jak je ko´d pomocı´ G generova´n a jak je pomocı´ H kontrolova´n. Nevy´hoda: prˇ´ılisˇ mnoho kontrolnı´ch bitu˚ za „ma´lo muziky“.
BI-LIN, kody, 18, P. Olsˇa´k
[9]
Hammingova va´ha, vzda´lenost − Definice: Hammingova va´ha slova → v je pocˇet jeho nenulovy´ch − − znaku˚. Hammingova vzda´lenost dvou slov → v a→ w je pocˇet pozic, − − kde jsou znaky odlisˇne´ (pro bina´rnı´ ko´d je to va´ha slova → v +→ w ). − u ∈ K a kazˇde´ slovo Ko´d K objevuje t chyb, pokud pro kazˇde´ slovo → → −e va´hy mensˇ´ı nebo rovno t platı´ → − −e 6∈ K. u +→ − Ko´d K opravuje t chyb, pokud pro kazˇde´ slovo → u ∈ K a kazˇde´ −e va´hy mensˇ´ı nebo rovno t platı´: slovo → − − −e slovo → u ma´ od slova → u +→ nejmensˇ´ı vzda´lenost mezi ko´dovy´mi slovy. Tvrzenı´ 1: Je-li nejmensˇ´ı vzda´lenost mezi ko´dovy´mi slovy d, pak ko´d objevuje d − 1 chyb a opravuje t < d2 chyb. Tvrzenı´ 2: Nejmensˇ´ı vzda´lenost mezi ko´dovy´mi slovy linea´rnı´ho ko´du je rovna nejmensˇ´ı va´ze nenulove´ho ko´dove´ho slova.
BI-LIN, kody, 18, P. Olsˇa´k
[10]
Prˇı´klady Ko´d s kontrolnı´m bitem parity ma´ nejmensˇ´ı va´hu nenulove´ho slova 2, takzˇe objevuje 2 − 1 = 1 chybu ve sloveˇ. Opravuje me´neˇ nezˇ 2/2 chyb, tedy neopravuje zˇa´dnou chybu. Opakovacı´ ko´d ma´ rovneˇzˇ nejmensˇ´ı va´hu nenulove´ho slova 2. Aby ko´d doka´zal opravit jednu chybu ve sloveˇ, musı´ mı´t nejmensˇ´ı va´hu neulove´ho slova rovnu trˇem.
BI-LIN, kody, 18, P. Olsˇa´k
[11]
Syndrom − Dekode´r vyhodnotı´ s = H ⋅ → w . Tomuto vektoru s rˇ´ıka´me syndrom → − prˇijate´ho slova w . Prˇijate´ slovo je ko´dove´, pra´veˇ kdyzˇ ma´ nulovy´ syndrom. −e , pra´veˇ kdyzˇ s = H ⋅ → −e T je nenulovy´ vektor. Ko´d rozpozna´ chybu → T
Pozorova´nı´ 1: Syndrom neza´visı´ na ko´dove´m sloveˇ (jen na chyT − −e )T = H ⋅ → − −e T = o + H ⋅ → −e T = H ⋅ → −e T . bove´m sloveˇ): H ⋅ (→ v +→ v +H⋅→ Pozorova´nı´ 2: Lin. ko´d ma´ minima´lnı´ vzda´lenost dvou slov d, pra´veˇ kdyzˇ kazˇdy´ vy´beˇr d − 1 sloupcu˚ z kontrolnı´ matice H je linea´rneˇ neza´visly´. Jmenoviteˇ: ko´d opravuje jednu chybu kdyzˇ kazˇde´ dva sloupce kontrolnı´ matice H jsou LN, tj. jsou nenulove´ a vza´jemneˇ ru˚zne´ (to v Zn−k stacˇ´ı). Kontrolnı´ matice s touto vlastnostı´ je kontrolnı´ ma2 tice Hammingova ko´du.
BI-LIN, kody, 18, P. Olsˇa´k
[12]
Hammingu ˚ v ko´d Sloupce kontrolnı´ matice H jsou prvky Zn−k ˇ et nenulovy´ch a 2 . Poc vza´jemneˇ ru˚zny´ch sloupcu˚ je maxima´lneˇ 2n−k − 1. Pocˇet sloupcu˚ uda´va´ de´lku ko´du n, tedy n = 2n−k − 1. De´lku ko´du je tedy vhodne´ volit jako mocninu dvou bez jedne´. Dosta´va´me tak Hammingovy ko´dy: (7, 4), (15, 11), (31, 26), (63, 57), . . . . Prˇ´ıklad: Hammingu˚v ko´d (7, 4) – de´lka 7, informacˇnı´ bity 4: 1 0 0 0 0 1 0 0 0 1 1 1 1 0 1 0 0 1 0 H = 0 1 1 0 0 1 1, G = 0 0 1 0 1 1 1 0 1 0 1 0 1 0 0 0 1 1 1
1 1 . 0 1
Vy´hoda tohoto usporˇa´da´nı´: index bitu, ktery´ je potrˇeba opravit, je zapsa´n v syndromu jako cˇ´ıslo ve dvojkove´ soustaveˇ.
BI-LIN, kody, 18, P. Olsˇa´k
[13]
Rozsˇı´rˇeny´ Hammingu ˚ v ko´d je Hammingu˚v ko´d, ke ktere´mu kode´r prˇida´va´ kontrolnı´ bit parity. Naprˇ´ıklad (8, 4) ko´d ma´ matice 0 0 0 1 1 1 1 0 1 0 0 0 0 1 1 1 0 1 1 0 0 1 1 0 , G = 0 1 0 0 1 0 1 1. H= 1 0 1 0 1 0 1 0 0 0 1 0 1 1 0 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 0 Ko´d opravı´ jednu chybu (v prvnı´ch trˇech bitech je syndrom jako v (7, 4) ko´du a cˇtvrty´ bit musı´ by´t 1) a odhalı´ dveˇ chyby (v prvnı´ch trˇech bitech syndromu je nenulove´ cˇ´ıslo a cˇtvrty´ bit je 0). Nejmensˇ´ı vzda´lenost dvou slov v tomto ko´du je 4.
BI-LIN, kody, 18, P. Olsˇa´k
[14]
Na´vrh pocˇtu kontrolnı´ch bitu ˚ Oznacˇme n de´lku bina´rnı´ho ko´du, k dimenzi ko´du (pocˇet informacˇnı´ch bitu˚) a c = n − k pocˇet kontrolnı´ch bitu˚. Linea´rnı´ ko´d nemu˚zˇe opravit vı´ce rozdı´lny´ch chyb nezˇ je pocˇet nenulovy´ch syndromu˚. Teˇch je 2c − 1. Pocˇet ru˚zny´ch chyb s va´hou jedna je n. Proto, chceme-li opravit jednu chybu, musı´ 2c − 1 ≥ n. Pocˇet ru˚zny´ch chyb (vcˇetneˇ stavu „bez chyby“) s va´hou nejvy´sˇe m je rovno n n n + + ··· + 0 1 m Chceme-li opravovat m chyb ve sloveˇ, musı´ tedy pocˇet kontrolnı´ch bitu˚ splnˇovat: n n n 2c ≥ + + ··· + 0 1 m Ko´dy navrzˇene´ tak, zˇe zde nasta´va´ rovnost, se nazy´vajı´ perfektnı´.
BI-LIN, kody, 18, P. Olsˇa´k
[15]
Cyklicke´ ko´dy jsou beˇzˇneˇ uzˇ´ıvane´ samoopravne´ ko´dy (naprˇ. prˇi za´pisu/cˇtenı´ CD). Viz google: CRC (cyclic redundancy check). Definice: Ko´d K se nazy´va´ cyklicky´, pokud • je linea´rnı´ a navı´c − − • je-li → v ko´dove´ slovo, pak cyklicky´ posun → v je take´ ko´dove´ slovo. Vhodna´ matematicka´ reprezentace slov de´lky n jsou polynomy: → − v = (a0, a1, a2 . . . , an−1)
↔
v(x) = a0 + a1x + a2x2 + · · · + an−1xn−1
− Cyklicky´ posun slova → v o jednu pozici popı´sˇeme na´sobenı´m polynomu v(x) polynomem x a ztotozˇneˇnı´m xn = x0, neboli na´sobenı´m v okruhu Zp[x]/(xn − 1). Od te´to chvı´le nerozlisˇujeme mezi pojmem „slovo“ a „polynom“.
BI-LIN, kody, 18, P. Olsˇa´k
[16]
Za´kladnı´ vlastnosti cyklicke´ho ko´du Definice: Nenulovy´ polynom cyklicke´ho ko´du nejmensˇ´ıho stupneˇ nazy´va´me generujı´cı´ polynom. Tvrzenı´: Je-li K cyklicky´ ko´d de´lky n a g je jeho generujı´cı´ polynom, pak K = {f ⋅ g; st f < n − st g} Du˚kaz: v = (fm−1xm−1 + · · · + f1x + f0) ⋅ g je linea´rnı´ kombinace cyklicky´ch posunu˚, takzˇe lezˇ´ı v K. Obra´ceneˇ, necht’ v ∈ K, pak vydeˇlı´me v polynomem g se zbytkem: v = f ⋅ g + z, protozˇe v ∈ K, f ⋅ g ∈ K, musı´ z ∈ K. Protozˇe st z < st g a polynom g ma´ nejmensˇ´ı stupenˇ, musı´ z = 0.
BI-LIN, kody, 18, P. Olsˇa´k
[17]
Vlastnosti generujı´cı´ho polynomu Tvrzenı´: Necht’ g je generujı´cı´ polynom (n, k) cyklicke´ho ko´du K. • polynom g ma´ stupenˇ n − k, • {g, x ⋅ g, x2 ⋅ g, . . . , xk−1 ⋅ g} je ba´ze ko´du, • polynom xn − 1 je deˇliteny´ polynomem g. Du˚kaz: K = {f ⋅ g; st f < n − st g}, takzˇe dim K = n − st g, neboli stupeˇnˇ g = n − dim K. Puntı´k druhy´: zrˇejme´. Puntı´k trˇetı´: polynom xn − 1 vydeˇlı´me polynomem g se zbytkem. V polynomech mod xn − 1 je zbytek roven −f ⋅ g, takzˇe lezˇ´ı v ko´du a ma´ mensˇ´ı stupenˇ, nezˇ g, takzˇe zbytek je nulovy´.
BI-LIN, kody, 18, P. Olsˇa´k
[18]
Generujı´cı´ polynom: postacˇujı´cı´ podmı´nka Tvrzenı´: Aby byl polynom g generujı´cı´ polynom neˇjake´ho cyklicke´ho ko´du, stacˇ´ı, aby deˇlil polynom xn − 1 beze zbytku. Du˚kaz: Zjistı´me, zˇe lin. obal vsˇech cyklicky´ch posunu˚ g neobsahuje nenulovy´ polynom st. mensˇ´ıho nezˇ g. Necht’f je libovolny´ polynom. f ⋅ g = z mod (xn − 1),
tj. f ⋅ g = u ⋅ (xn − 1) + z
Je trˇeba oveˇrˇit, zˇe z = 0 nebo st z ≥ st g. Protozˇe je f ⋅ g deˇlitelny´ g a u ⋅ (xn − 1) je deˇlitelny´ g, musı´ te´zˇ z by´t deˇlitelny´ g, takzˇe z = v ⋅ g. Na´vrh cyklicke´ho ko´du: Zvolı´me de´lku bloku n, rozlozˇ´ıme polynom xn − 1 na soucˇin ireducibilnı´ch polynomu˚ a generujı´cı´ polynom g zvolı´me jako soucˇin neˇktery´ch takto nalezeny´ch ireducibilnı´ch polynomu˚. Stupenˇ g je pocˇet kontrolnı´ch bitu˚ ko´du. ´ mluva: Vsˇechny gen. polynomy stejne´ho ko´du se lisˇ´ı azˇ na skaU la´rnı´ na´sobek. Volme takovy´, co ma´ u nejvysˇsˇ´ı mocniny jednicˇku.
BI-LIN, kody, 18, P. Olsˇa´k
[19]
Odhalenı´ souvisle´ chyby Souvisla´ chyba de´lky t je chyba meˇnı´cı´ ko´dove´ slovo v u´seku neˇktery´ch po sobeˇ jdoucı´ch t bitu˚, jinde je slovo nezmeˇneˇno. Pocˇet chyb (va´ha chybove´ho slova) nemusı´ by´t t, ale je mensˇ´ı nebo rovna t. Pozorova´nı´: Cyklicky´ (n, k) ko´d odhaluje vsˇechny souvisle´ chyby de´lky n − k. −e mu˚zˇeme prove´st (opakovaneˇ) cykDu˚kaz: Na souvislou chybu → −e 0, ktery´ je stupneˇ mensˇ´ıho nezˇ n−k. licky´ posun a zı´skat polynom → −e 0 ani → −e nenı´ ko´dove´ slovo. Takzˇe → Pozna´mka: toto je du˚vod, procˇ se v praxi pouzˇ´ıvajı´ cyklicke´ ko´dy. Chyby se totizˇ ra´dy v konkre´tnı´m technicke´m prostrˇedı´ soustrˇed’ujı´ do bloku˚ (drupouty, sˇkra´bance na CD atd.). Existujı´ cyklicke´ (n, k) ko´dy, ktere´ navı´c umeˇjı´ opravit vsˇechny souvisle´ chyby de´lky (n − k)/2.
BI-LIN, kody, 18, P. Olsˇa´k
[20]
Prˇı´klad: Cyklicky´ Hammingu ˚ v ko´d Sestavme (7, 4) cyklicky´ ko´d, ktery´ ma´ generujı´cı´ polynom x3 +x+1. Je to generujı´cı´ polynom, protozˇe deˇlı´ polynom x7 − 1. Ko´d ma´ na´sledujı´cı´ generujı´cı´ a kontrolnı´ matici 1 1 0 1 0 0 0 1 0 1 1 1 0 0 0 1 1 0 1 0 0 G= 0 0 1 1 0 1 0, H = 1 1 1 0 0 1 0 , 0 1 1 1 0 0 1 0 0 0 1 1 0 1 takzˇe vidı´me, zˇe H ma´ ru˚zne´ a nenulove´ sloupce. Je to tedy Hammingu˚v (7, 4) ko´d. Hammingu˚v (7, 4) ko´d, ktery´ ko´duje podle te´to G a pouzˇ´ıva´ tuto kontrolnı´ matici H umı´ odhalit i trˇi souvisle´ chyby. Od Hammingova ko´du ze strany [12] se lisˇ´ı porˇadı´m bitu˚ ko´dove´ho slova.
BI-LIN, kody, 18, P. Olsˇa´k
[21]
Generujı´cı´ a kontrolnı´ matice Protozˇe cyklicky´ ko´d ma´ ba´zi g, x ⋅ g, x2 ⋅ g, . . . , xk−1 ⋅ g, kde g je generujı´cı´ polynom, g(x) = g0 +g1x+g2x2 +· · ·+gn−kxn−k, je generujı´cı´ matice tvaru g0 g1 g2 . . . gn−k 0 0 ... 0 0 0 g0 g1 . . . gn−k−1 gn−k 0 ... 0 0 G = 0 0 g0 . . . gn−k−2 gn−k−1 gn−k . . . 0 0 ... ... 0 0 0 ... ... g0 g1 . . . gn−k−1 gn−k Polynom h = (xn − 1)/g se nazy´va´ kontrolnı´ polynom. Da´ se uka´zat, zˇe matice s koeficienty kontrolnı´ho polynomu hk, hk−1, . . . , h1, h0 umı´steˇny´mi (v tomto porˇadı´) opakovaneˇ „pode´l vedlejsˇ´ı diagona´ly“, je maticı´ kontrolnı´. Ta se v prˇ´ıpadeˇ cyklicky´ch ko´du v deko´deru prˇ´ılisˇ nevyuzˇ´ıva´.
BI-LIN, kody, 18, P. Olsˇa´k
[22]
Kode´r a dekode´r cyklicke´ho ko´du Ko´dova´nı´ podle generujı´cı´ matice nenı´ systematicke´. Kode´r − − z informacˇnı´ch bitu˚ → u vytvorˇ´ı ko´dove´ slovo → u ⋅ G. Fakticky tedy vytva´rˇ´ı ko´dove´ slovo ve tvaru u ⋅ g. Dekode´r spocˇ´ıta´ syndrom prˇijate´ho slova jako zbytek po deˇlenı´ generujı´cı´m polynomem. Je-li nulovy´, je prˇijate´ slovo ko´dove´. Vy´sledek deˇlenı´ obsahuje informacˇnı´ bity. Pozorova´nı´: Syndrom neza´visı´ na ko´dovane´m slovu, ale pouze na chybeˇ: f ⋅ g + e = s1 mod g,
e = s2 mod g,
pak s1 = s2.
Du˚kaz: f ⋅ g + e = r1 ⋅ g + s1, e = r2 ⋅ g + s2. s1 − s2 je na´sobek g se stupneˇm mensˇ´ım, takzˇe s1 − s2 = 0.
BI-LIN, kody, 18, P. Olsˇa´k
[23]
Systematicke´ ko´dova´nı´ Kode´r z informacˇnı´ch bitu˚ (u1, u2, . . . , uk) sestavı´ polynom: u(x) = u1xn−1 + u2xn−2 + · · · + uk−1xn−k+1 + ukxn−k, vypocˇ´ıta´ z jako zbytek po deˇlenı´ u polynomem g a odesˇle ko´dove´ slovo u − z. Procˇ je ko´dove´? Je u = f ⋅ g + z. Protozˇe f ⋅ g je na´sobek g, musı´ i u − z by´t na´sobek g. Navı´c soucˇet u − z neposˇkodı´ poslednı´ch k informacˇnı´ch bitu˚. Dekode´r spocˇ´ıta´ syndrom s jako zbytek po deˇlenı´ prˇijate´ho slova polynomem g. Je-li s = 0, je prˇijate´ slovo ko´dove´. Poslednı´ch k bitu˚ obsahuje informaci. O analy´ze syndromu si povı´me za chvı´li.
BI-LIN, kody, 18, P. Olsˇa´k
[24]
Zbytek po deˇlenı´ polynomu polynomem se v prˇ´ıpadeˇ polynomu˚ nad Z2 hleda´ snadno. V prˇ´ıkladu zapisujeme bity v opacˇne´m porˇadı´ nezˇ dosud, tj. (an−1, an−2, . . . , a1, a0) ↔ an−1xn−1 + an−2xn−1 + · · · + a1x + a0. Prˇı´klad: Necht’ g = (1011). Chceme ko´dovat informaci (1111). Sestavı´me polynom u = (1111000) a deˇlı´me ho polynomem g: kode´r: 1111000 1011 0100000 1011 0001100 1011 0000111 = z,
u − z = 1111111
dekode´r: 1111111 1011 0100111 1011 0001011 1011 0000000 = s (syndrom)
BI-LIN, kody, 18, P. Olsˇa´k
[25]
Analy´za syndromu Sestavı´me tabulku chyb a jejich syndromu˚: → −e ↔ → −s , → −e ↔ → −s , . . . , → −e ↔ → −s . Tabulku vyplnı´me (drˇ´ıv, nezˇ 1
1
2
2
m
m
zacˇneme ko´dovat) tak, zˇe pro kazˇdou chybu ei spocˇ´ıta´me zbytek prˇi deˇlenı´ polynomem g a dostaneme si. Kdybychom meˇli v pameˇti ulozˇenu tuto tabulku, pak pro kazˇdy´ −s dekode´r najde zpeˇtneˇ → −e a prˇijate´ slovo → − syndrom → w opravı´ i i − − −e . takto: → v =→ w −→ i Proble´m: pameˇt’ova´ na´rocˇnost + nutnost pro kazˇde´ prˇijate´ slovo prohledat tabulku.
BI-LIN, kody, 18, P. Olsˇa´k
[26]
Analy´za syndromu podle Meggitta Ucˇinˇme pozorova´nı´ na prˇ´ıkladu (7, 4) cyklicke´ho ko´du. Tabulka → −e ↔ → −s , ktera´ obsahuje vsˇechny chyby va´hy 1, vypada´ takto: i 1 e1 e2 e3 e4 e5 e6 e7
= x0 = x1 = x2 = x3 = x4 = x5 = x6
↔ ↔ ↔ ↔ ↔ ↔ ↔
s1 s2 s3 s4 s5 s6 s7
=1 =x = x2 =x+1 = x2 + x = x2 + x + 1 = x2 + 1 . . . syndrom poslednı´ho bitu
Pro syndromy platı´: si+1 = x⋅si mod g. Prˇitom s8 = s1. Je tedy mozˇne´ „protocˇit syndromy“ postupnou aplikacı´ operace x ⋅ si mod g. V jednom okamzˇiku se z kazˇde´ho syndromu stane syndrom poslednı´ho bitu. Deˇla´me-li soucˇasneˇ cyklicky´ posun prˇijate´ho slova, dostal se opravovany´ bit na poslednı´ pozici. Opravı´me ho tam.
BI-LIN, kody, 18, P. Olsˇa´k
[27]
Algoritmus podle Meggitta Sestavme seznam vsˇech syndromu˚, ktere´ odpovı´dajı´ vsˇem chyba´m, ktere´ majı´ na poslednı´ pozici jednicˇku (seznam vsˇech syndromu˚ poslednı´ho bitu). Ulozˇme tento seznam do pameˇti dekode´ru. Seznam zdaleka neobsahuje vsˇechny syndromy. Necht’ de´lka ko´du je n. Dekode´r provede postupneˇ n cyklicky´ch posunu˚ prˇijate´ho slova (tı´m ho dostane nakonec do pu˚vodnı´ho stavu) a soucˇasneˇ cyklicky prota´cˇ´ı syndrom podle vzorce si+1 = x⋅si mod g. Kdykoli se sydrom shoduje s neˇktery´m syndromem poslednı´ho bitu (ze seznamu), opravı´ dekode´r poslednı´ bit (cyklicky pounute´ho) prˇijate´ho slova. Opravuje-li ko´d jedinou chybu, obsahuje seznam jediny´ syndrom poslednı´ho bitu. Opravuje-li dveˇ chyby, pak seznam obsahuje n syndromu˚. Vy´pocˇet probı´ha´ s linea´rnı´ slozˇitostı´ (existuje dobrˇe popsana´ hw implementace pomocı´ hradel).
BI-LIN, kody, 18, P. Olsˇa´k
[28]
Korekce souvisly´ch chyb Existujı´ cyklicke´ ko´dy, ktere´ opravujı´ souvisle´ chyby de´lky t. Da´ se uka´zat, zˇe pro takove´ ko´dy platı´: pokud prˇi „prota´cˇenı´ syndromu“ dospeˇjeme k syndromu stupneˇ mensˇ´ıho nezˇ t, pak lze nara´z opravit v odpovı´dajı´cı´m (cyklicky posunute´m) prˇijate´m sloveˇ vsˇechny kontrolnı´ bity prˇ´ımo podle (protocˇene´ho) syndromu. Inspirace: podı´vejte se na prvnı´ rˇa´dek tabulky na str. [26].
BI-LIN, kody, 18, P. Olsˇa´k
[29]
Prˇı´klady „veˇtsˇı´ch“ cyklicky´ch ko´du ˚ • Golay code je perfektnı´ ko´d opravujı´cı´ trˇi chyby. Je to cyklicky´ (23, 12) ko´d s generujı´cı´m polynomem: 1 + x2 + x4 + x5 + x6 + x10 + x11 • CRC 32 je metoda pocˇ´ıta´nı´ kontrolnı´ch soucˇtu˚ (syndromu˚) dat libovolne´ de´lky s generujı´cı´m polynomem: 1 + x + x2 + x4 + x5 + x7 + x8 + x10 + x11 + x12 + x16 + x22 + x23 + x26 + x32 K hlubsˇ´ımu zkouma´nı´ te´to problematiky mu˚zˇete pouzˇ´ıt: Jirˇ´ı Ada´mek: Foundations of Coding, A Wiley-Interscience publication, 1991, ISBN 0-471-62187-0. Pozna´mka: Prof. Jirˇ´ı Ada´mek byl v letech 1990–1994 vedoucı´ nasˇ´ı katedry, nynı´ pu˚sobı´ na University of Braunschweig.
