Samoopravné kódy, k čemu to je

[1]

BI-LIN, kody, 18, P. Olsˇa´k

[2]

Samoopravne´ ko´dy, k cˇemu to je

´ vod do ko´dovańı´ U

• Data jsou ulozˇena (nebo posı´lańa do linky) kode´rem podle urcˇite´ho pravidla (ko´dovańı´). Posle´ze jsou cˇtena dekode´rem a restaurovańa do pu˚vodnı´ podoby. • Kode´r mu˚zˇe prˇidat k datu˚m doplnˇujıćı´ 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ńı´ mu˚zˇe dekode´r chybu opravit.

• samoopravne´ ko´dy: terminologie, princip • blokove´ linea´rnı´ ko´dy • Hammingu˚v ko´d

Ko´d je mnozˇina slov (tj. u´seku˚ dat), ktere´ mu˚zˇe generovat kode´r.

• cyklicke´ ko´dy

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)

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


[3]


[4]

Bina´rnı´, blokovy´ ko´d

Linea´rnı´ ko´d

je ko´d, kde jsou vsˇechna slova stejneˇ dlouha´.

Bina´rnı´ blokovy´ ko´d K de´lky n je podmnozˇinou lin. prostoru Zn2 .

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

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ˇı´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

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 .


[5]


[6]

Generujıćı´ a kontrolnı´ matice

Vy´pocˇet jedne´ matice, zna´me-li druhou

Generujıćı´ matice linea´rnı´ho ko´du K je matice, ktera´ v rˇa´dcıćh obsahuje ba´zi ko´du.

Je-li dańa generujıćı´ (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ıćı´) matice.

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ıćı´ matice G a kontrolnı´ matice H jsou:   1 0 0 1 H = (1 1 1 1) G = 0 1 0 1, 0 0 1 1

Pro systematicky´ ko´d dokonce platı´: Je-li G = (E | C), pak H = (CT | E′ ).

Pozorovańı´: Generujıćı´ matice (n, k) ko´du je typu (k, n) a kontrolnı´ matice je typu (n − k, n). Platı´: G ⋅ HT = O.


[7]


[8]

Kode´r a dekode´r

Prˇı´klad: opakovacı´ ko´d

→ 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:

→ 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´.

− → → v =− u ⋅ G. → Dekode´r mu˚zˇe zkontrolovat prˇijate´ slovo − w pomocı´ testu: → H⋅− w = o. T

→ Ko´dovańı´ je systematicke´, jsou-li informacˇnı´ bity (ze slova − u ) beze zmeˇny zkopı´rovańy 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ńı´m prvnıćh k pozic prˇijate´ho slova. Pozorovańı´: Ko´dovańı´ je systematicke´, je-li generujıćı´ matice tvaru G = (E | C). Prˇida´vane´ kontrolnı´ bity pak kode´r spocˇ´ıta´ po′ → → mocı´ vzorce − v =− u ⋅ C.

Generujıćı´ 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ń a jak je pomocı´ H kontrolovań. Nevy´hoda: prˇ´ılisˇ mnoho kontrolnıćh bitu˚ za „ma´lo muziky“.


[9]


[10]

Hammingova va´ha, vzda´lenost

Prˇı´klady

→ Definice: Hammingova va´ha slova − v je pocˇet jeho nenulovyćh → → 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 ). − → Ko´d K objevuje t chyb, pokud pro kazˇde´ slovo u ∈ K a kazˇde´ slovo − → → → e va´hy mensˇ´ı nebo rovno t platı´ − u +− e 6∈ K.

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ńeˇ nezˇ 2/2 chyb, tedy neopravuje zˇa´dnou chybu.

→ Ko´d K opravuje t chyb, pokud pro kazˇde´ slovo − u ∈ K a kazˇde´ → → → → slovo − e va´hy mensˇ´ı nebo rovno t platı´: slovo − u ma´ od slova − u +− e nejmensˇ´ı vzda´lenost mezi ko´dovy´mi slovy.

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.

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.


[11]

Syndrom


[12]

Hammingu ˚ v ko´d

→ 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. T → → Ko´d rozpozna´ chybu − e , pra´veˇ kdyzˇ s = H ⋅ − e je nenulovy´ vektor. T

Pozorovańı´ 1: Syndrom neza´visı´ na ko´dove´m sloveˇ (jen na chyT T T T → → → → → → bove´m sloveˇ): H ⋅ (− v +− e )T = H ⋅ − v +H⋅− e = o+H⋅− e = H⋅− e . Pozorovańı´ 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.

Sloupce kontrolnı´ matice H jsou prvky Zn−k ˇ et nenulovyćh a 2 . Poc vza´jemneˇ ru˚znyćh 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ńı´: index bitu, ktery´ je potrˇeba opravit, je zapsań v syndromu jako cˇ´ıslo ve dvojkove´ soustaveˇ.


[13]


[14]

Rozsˇı´rˇeny´ Hammingu ˚ v ko´d

Na´vrh pocˇtu kontrolnıćh bitu ˚

je Hammingu˚v ko´d, ke ktere´mu kode´r prˇida´va´ kontrolnı´ bit parity. Naprˇ´ıklad (8, 4) ko´d ma´ matice     1 0 0 0 0 1 1 1 0 0 0 1 1 1 1 0 0 1 0 0 1 0 1 1 0 1 1 0 0 1 1 0    H= 1 0 1 0 1 0 1 0, G = 0 0 1 0 1 1 0 1.

Oznacˇme n de´lku bina´rnı´ho ko´du, k dimenzi ko´du (pocˇet informacˇnıćh bitu˚) a c = n − k pocˇet kontrolnıćh bitu˚.

1 1 1 1 1 1 1 1

0 0 0 1 1 1 1 0

Ko´d opravı´ jednu chybu (v prvnıćh 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ıćh 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.


[15]

Linea´rnı´ ko´d nemu˚zˇe opravit vıće rozdı´lnyćh chyb nezˇ je pocˇet nenulovyćh syndromu˚. Teˇch je 2c − 1. Pocˇet ru˚znyćh chyb s va´hou jedna je n. Proto, chceme-li opravit jednu chybu, musı´ 2c − 1 ≥ n. Pocˇet ru˚znyćh chyb (vcˇetneˇ stavu „bez chyby“) s va´hou nejvy´sˇe m je rovno n n n + ··· + + m 1 0 Chceme-li opravovat m chyb ve sloveˇ, musı´ tedy pocˇet kontrolnıćh bitu˚ splnˇovat: n n n + ···+ + 2c ≥ m 1 0 Ko´dy navrzˇene´ tak, zˇe zde nasta´va´ rovnost, se nazy´vajı´ perfektnı´.


[16]

Cyklicke´ ko´dy

Za´kladnı´ vlastnosti cyklicke´ho ko´du

jsou beˇzˇneˇ uzˇ´ıvane´ samoopravne´ ko´dy (naprˇ. prˇi za´pisu/cˇtenı´ CD). Viz google: CRC (cyclic redundancy check).

Definice: Nenulovy´ polynom cyklicke´ho ko´du nejmensˇ´ıho stupneˇ nazy´va´me generujıćı´ polynom.

Definice: Ko´d K se nazy´va´ cyklicky´, pokud

Tvrzenı´: Je-li K cyklicky´ ko´d de´lky n a g je jeho generujıćı´ polynom, pak K = {f ⋅ g; st f < n − st g}

• je linea´rnı´ a navıć → → • 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 + a1 x + a2 x2 + · · · + 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“.

Du˚kaz: v = (fm−1xm−1 + · · · + f1 x + f0) ⋅ g je linea´rnı´ kombinace cyklickyćh posunu˚, takzˇe lezˇ´ı v K. Obraćeneˇ, 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.


[17]


[18]

Vlastnosti generujıćı´ho polynomu

Generujıćı´ polynom: postacˇujıćı´ podmıńka

Tvrzenı´: Necht’ g je generujıćı´ polynom (n, k) cyklicke´ho ko´du K.

Tvrzenı´: Aby byl polynom g generujıćı´ polynom neˇjake´ho cyklicke´ho ko´du, stacˇ´ı, aby deˇlil polynom xn − 1 beze zbytku.

• polynom g ma´ stupenˇ n − k,

Du˚kaz: Zjistı´me, zˇe lin. obal vsˇech cyklickyćh posunu˚ g neobsahuje nenulovy´ polynom st. mensˇ´ıho nezˇ g. Necht’ f je libovolny´ polynom.

• {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´.

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ıćh polynomu˚ a generujıćı´ polynom g zvolı´me jako soucˇin neˇkteryćh takto nalezenyćh ireducibilnıćh polynomu˚. Stupenˇ g je pocˇet kontrolnıćh 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.


[19]


[20]

Odhalenı´ souvisle´ chyby

Prˇı´klad: Cyklicky´ Hammingu ˚ v ko´d

Souvisla´ chyba de´lky t je chyba meˇnıćı´ ko´dove´ slovo v u´seku neˇkteryćh po sobeˇ jdoucıćh 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.

Sestavme (7, 4) cyklicky´ ko´d, ktery´ ma´ generujıćı´ polynom x3 +x+1. Je to generujıćı´ polynom, protozˇe deˇlı´ polynom x7 − 1. Ko´d ma´ na´sledujıćı´ generujıćı´ 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= , H = 1 1 1 0 0 1 0, 0 0 1 1 0 1 0 0 1 1 1 0 0 1 0 0 0 1 1 0 1

Pozorovańı´: Cyklicky´ (n, k) ko´d odhaluje vsˇechny souvisle´ chyby de´lky n − k. → Du˚kaz: Na souvislou chybu − e mu˚zˇeme prove´st (opakovaneˇ) cyk→ licky´ posun a zı´skat polynom − e ′ , ktery´ je stupneˇ mensˇ´ıho nezˇ n−k. ′ − → − → Takzˇe e ani e nenı´ ko´dove´ slovo. 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ıć umeˇjı´ opravit vsˇechny souvisle´ chyby de´lky (n − k)/2.

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.


[21]


[22]

Generujıćı´ a kontrolnı´ matice

Kode´r a dekode´r cyklicke´ho ko´du

Protozˇe cyklicky´ ko´d ma´ ba´zi g, x ⋅ g, x2 ⋅ g, . . . , xk−1 ⋅ g, kde g je generujıćı´ polynom, g(x) = g0 +g1x+g2x2 +· · ·+gn−kxn−k, je generujıćı´ 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

Ko´dovańı´ podle generujıćı´ matice nenı´ systematicke´. Kode´r → → z informacˇnıćh bitu˚ − u vytvorˇ´ı ko´dove´ slovo − u ⋅ G. Fakticky tedy vytva´rˇ´ı ko´dove´ slovo ve tvaru u ⋅ g.

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ćh ko´du v deko´deru prˇ´ılisˇ nevyuzˇ´ıva´.


u(x) = u1 x

+ u2x

+ · · · + uk−1 x

n−k+1

+ uk x

n−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ıć soucˇet u − z neposˇkodı´ poslednıćh k informacˇnıćh 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ıćh k bitu˚ obsahuje informaci. O analy´ze syndromu si povı´me za chvı´li.

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.


[24]

Zbytek po deˇlenı´ polynomu polynomem

Kode´r z informacˇnıćh bitu˚ (u1 , u2 , . . . , uk) sestavı´ polynom: n−2

Pozorovańı´: Syndrom neza´visı´ na ko´dovane´m slovu, ale pouze na chybeˇ:

[23]

Systematicke´ ko´dovańı´ n−1

Dekode´r spocˇ´ıta´ syndrom prˇijate´ho slova jako zbytek po deˇlenı´ generujıćı´m polynomem. Je-li nulovy´, je prˇijate´ slovo ko´dove´. Vy´sledek deˇlenı´ obsahuje informacˇnı´ bity.

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)


[25]


[26]

Analy´za syndromu

Analy´za syndromu podle Meggitta

Sestavı´me tabulku chyb a jejich syndromu˚: − → → → → → → e ↔− s ,− e ↔− s , ..., − e ↔− s . Tabulku vyplnı´me (drˇ´ıv, nezˇ

Ucˇinˇme pozorovańı´ na prˇ´ıkladu (7, 4) cyklicke´ho ko´du. Tabulka − → → ei↔− s 1, ktera´ obsahuje vsˇechny chyby va´hy 1, vypada´ takto:

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´ → → → syndrom − s i dekode´r najde zpeˇtneˇ − e i a prˇijate´ slovo − w opravı´ → → → takto: − v =− w −− e i. Proble´m: pameˇt’ova´ na´rocˇnost + nutnost pro kazˇde´ prˇijate´ slovo prohledat tabulku.

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.


[27]


[28]

Algoritmus podle Meggitta

Korekce souvislyćh chyb

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.

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ćˇenı´ syndromu“ dospeˇjeme k syndromu stupneˇ mensˇ´ıho nezˇ t, pak lze nara´z opravit v odpovı´dajıćı´m (cyklicky posunute´m) prˇijate´m sloveˇ vsˇechny kontrolnı´ bity prˇ´ımo podle (protocˇene´ho) syndromu.

Necht’ de´lka ko´du je n. Dekode´r provede postupneˇ n cyklickyćh posunu˚ prˇijate´ho slova (tı´m ho dostane nakonec do pu˚vodnı´ho stavu) a soucˇasneˇ cyklicky protaćˇ´ı 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).

Inspirace: podı´vejte se na prvnı´ rˇa´dek tabulky na str. [26].


[29]

Prˇı´klady „veˇtsˇıćh“ cyklickyćh ko´du ˚ • Golay code je perfektnı´ ko´d opravujıćı´ trˇi chyby. Je to cyklicky´ (23, 12) ko´d s generujıćı´m polynomem: 1 + x2 + x4 + x5 + x6 + x10 + x11 • CRC 32 je metoda pocˇ´ıtańı´ kontrolnıćh soucˇtu˚ (syndromu˚) dat libovolne´ de´lky s generujıćı´m polynomem: 1 + x + x2 + x4 + x5 + x7 + x8 + x10 + x11 + x12 + x16 + x22 + x23 + x26 + x32 K hlubsˇ´ımu zkoumańı´ 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.

Samoopravné kódy, k čemu to je

Recommend Documents