Hamming˚ uv (7, 4)-k´ od Hammingova vzd´ alenost
Line´ arn´ı k´ ody, ˇ c´ ast 2
Odpˇrednesenou l´ atku naleznete v kapitole 3.3 skript Diskr´etn´ı matematika.
Jiˇr´ı Velebil: A7B01LAG
22.12.2014: Line´ arn´ı k´ ody, ˇ c´ ast 2
1/12
Hamming˚ uv (7, 4)-k´ od Hammingova vzd´ alenost
Dneˇsn´ı pˇredn´ aˇska 1
Anal´yza Hammingova (7, 4)-k´ odu.
2
N´avrh line´arn´ıho k´ odu s pˇredepsan´ymi vlastnostmi.
Dalˇs´ı moˇ zn´ e doplˇ nuj´ıc´ı informace 1
J. Ad´amek, Foundations of coding , John Wiley & sons, 1991
2
D. J. C. MacKay, Information Theory, Inference and Learning Algorithms, Cambridge Univ. Press, 2003
Jiˇr´ı Velebil: A7B01LAG
22.12.2014: Line´ arn´ı k´ ody, ˇ c´ ast 2
2/12
Hamming˚ uv (7, 4)-k´ od Hammingova vzd´ alenost
Pˇripomenut´ı: Z2 = {0, 1}, s operacemi sˇc´ıt´an´ı a n´asoben´ı dan´ymi tabulkami + 0 1
0 0 1
1 1 0
· 0 1
0 0 0
1 0 1
je tˇeleso. Teorie line´arn´ıch prostor˚ u nad obecn´ym tˇelesem F byla vybudov´ana. Pro F = Z2 tedy um´ıme: 1 2
Urˇcit b´azi a dimensi podprostor˚ u W line´arn´ıho prostoru (Z2 )n . Pracovat s maticemi nad Z2 a ˇreˇsit soustavy line´arn´ıch rovnic nad Z2 .
Jiˇr´ı Velebil: A7B01LAG
22.12.2014: Line´ arn´ı k´ ody, ˇ c´ ast 2
3/12
Hamming˚ uv (7, 4)-k´ od Hammingova vzd´ alenost
Definice Line´arn´ı 2-k´od d´elky n a dimense k je line´arn´ı podprostor W prostoru (Z2 )n , dim(W ) = k, 0 ≤ k ≤ n. Terminologie: 1
Prvk˚ um W ˇr´ık´ame k´ odov´a slova.
2
Generuj´ıc´ı matice: b´aze G = (g1 , . . . , gk ) prostoru W napsan´a do ˇr´adk˚ u matice G. Plat´ı: rank(G) = k.
3
Souˇradnic´ım coordG (x) = (a1 , . . . , ak ) ˇr´ık´ame informaˇcn´ı bity. Souˇcin odov´e slovo P(a1 , . . . , ak ) · G je pˇr´ısluˇsn´e k´ w = ki=1 ai · gi .
4
Kontroln´ı matice: b´aze H = (h1 , . . . , hn−k ) ortogon´aln´ıho doplˇ nku prostoru W napsan´a do ˇr´adk˚ u matice H.
5
Test pˇri pˇrijet´ı slova v: v´ypoˇcet syndromu pˇrijat´eho slova s = H · vT . Jiˇr´ı Velebil: A7B01LAG
22.12.2014: Line´ arn´ı k´ ody, ˇ c´ ast 2
4/12
Hamming˚ uv (7, 4)-k´ od Hammingova vzd´ alenost
Pˇr´ıklad (Hamming˚ uv (7, 4)-k´ od) Jde o line´arn´ı 2-k´od d´elky 7 a dimense g1 1 0 0 g2 0 1 0 G= g3 = 0 0 1 g4 0 0 0
4 s generuj´ıc´ı matic´ı 0 0 1 1 0 1 0 1 0 1 1 0 1 1 1 1
1
rank(G) = 4, tud´ıˇz m´ame k disposici 4 info bity.
2
Dimense ortogon´aln´ıho doplˇ nku 7 − 4 = 3. Informace bude chr´anˇena tˇremi bity (redundance).
3
Pos´ıl´an´ı zpr´av: info (1, 1, 0, 1) vytv´aˇr´ı k´ odov´e slovo (1, 1, 0, 1) · G = (1, 1, 0, 1, 0, 0, 1). Pozorov´an´ı: G je tvaru (E | B). Jde o systematick´y k´od (v´ıce pozdˇeji). Jiˇr´ı Velebil: A7B01LAG
22.12.2014: Line´ arn´ı k´ ody, ˇ c´ ast 2
5/12
Hamming˚ uv (7, 4)-k´ od Hammingova vzd´ alenost
Pˇr´ıklad (Hamming˚ uv (7, 4)-k´ od, pokraˇ c.) Kontroln´ı (Hammingova) matice h1 0 0 0 1 1 1 1 H = h2 = 0 1 1 0 0 1 1 h3 1 0 1 0 1 0 1 Jde o ide´aln´ı k´od, pokud doˇslo nejv´yˇse k jedn´e chybˇe: 1
2
3
Odesl´ano w, pˇrijmeme v a pˇredpokl´ad´ame, ˇze doˇslo k nejv´yˇse jedn´e chybˇe. Tj. v = w + e (e je error pattern). V´ıme, ˇze e obsahuje nejv´yˇse jednu jedniˇcku. Spoˇcteme syndrom s slova v: sT = HvT = HeT . Jestliˇze s = o, pˇri pˇrenosu nedoˇslo k chybˇe. Jestliˇze s je i-t´y sloupec H, doˇslo k chybˇe na i-t´em m´ıstˇe, oprav´ıme. Isolujeme info bity. Jiˇr´ı Velebil: A7B01LAG
22.12.2014: Line´ arn´ı k´ ody, ˇ c´ ast 2
6/12
Hamming˚ uv (7, 4)-k´ od Hammingova vzd´ alenost
Pˇr´ıklad (Hamming˚ uv (8, 4)-k´ od: u ´prava (7, 4)-k´ odu) Hamming˚ uv (7, 4)-k´od nen´ı schopen detekovat dvˇe chyby. Napˇr´ıklad: chyba na 3. posici je nerozeznateln´a od dvou chyb na 1. a 2. posici souˇcasnˇe. D˚ uvod: v matici 0 0 0 1 1 1 1 H = 0 1 1 0 0 1 1 1 0 1 0 1 0 1 je souˇcet 1. a 2. sloupce roven 3. Uprav´ıme H na 0 0 0 0 1 1 H0 = 1 0 1 1 1 1
sloupci. 1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 1
0 0 0 1
T´ım se zmˇen´ı i generuj´ıc´ı matice. Nov´a matice G0 m´a ale opˇet hodnost 4. Zvˇetˇsili jsme d´elku k´ odu. Jiˇr´ı Velebil: A7B01LAG
22.12.2014: Line´ arn´ı k´ ody, ˇ c´ ast 2
7/12
Hamming˚ uv (7, 4)-k´ od Hammingova vzd´ alenost
Obecn´ y vztah matic G a H Rozmˇery G: n sloupc˚ u, k ˇr´adk˚ u, rank(G) = k. Rozmˇery H: n sloupc˚ u, n − k ˇr´adk˚ u, rank(H) = n − k. G a H jsou ortogon´aln´ı, tj. G · HT = 0k,n−k (nulov´a matice: k ˇr´adk˚ u, n − k sloupc˚ u). 1
Zn´ame-li G, lze spoˇc´ıst H: ˇr´adky H jsou prvky fundament´aln´ıho syst´emu homogenn´ı rovnice Gx = o.
2
Zn´ame-li H, lze spoˇc´ıst G: ˇr´adky G jsou prvky fundament´aln´ıho syst´emu homogenn´ı rovnice Hx = o. T T T D˚ uvod: 0n−k,k = 0T k,n−k = (G · H ) = H · G .
3
Jestliˇze G = (Ek | B), kde Ek je jednotkov´a matice typu k × k (tj. kdyˇz jde o systematick´y k´ od), pak je moˇzn´e zvolit H = (−BT | En−k ). Nad Z2 je samozˇrejmˇe −BT = BT . V´yhoda systematick´ych k´ od˚ u: je snadn´e oddˇelit informaˇcn´ı a kontroln´ı bity. Hamming˚ uv (7, 4)-k´ od a 10-ISBN k´od jsou pˇr´ıklady systematick´ych k´ od˚ u. Jiˇr´ı Velebil: A7B01LAG
22.12.2014: Line´ arn´ı k´ ody, ˇ c´ ast 2
8/12
Hamming˚ uv (7, 4)-k´ od Hammingova vzd´ alenost
Pˇr´ıklad (opakovac´ı k´ od) Jde o systematick´y k´od d´elky n = 2k, dimense k, s generuj´ıc´ı matic´ı G = (Ek | Ek ) a kontroln´ı matic´ı H = (En−k | En−k ) = (Ek | Ek ). Plat´ı totiˇz n − k = k. Informace x vytv´aˇr´ı k´odov´e slovo w = (x, x). Nev´yhoda: pˇr´ıliˇs mnoho kontroln´ıch bit˚ u. Probl´ em n´ avrhu line´ arn´ıho k´ odu Jak vyv´aˇzit n´asleduj´ıc´ı poˇzadavky? Chceme co nejvˇetˇs´ı opravn´e schopnosti k´odu a co nejmenˇs´ı poˇcet kontroln´ıch bit˚ u. Tyto poˇzadavky jsou protich˚ udn´e. To plyne z anal´yzy hodnost´ı matic G a H.
Jiˇr´ı Velebil: A7B01LAG
22.12.2014: Line´ arn´ı k´ ody, ˇ c´ ast 2
9/12
Hamming˚ uv (7, 4)-k´ od Hammingova vzd´ alenost
Definice (Hammingova v´ aha a vzd´ alenost) Pro vektor w v (Z2 )n definujeme jeho Hammingovu v´ahu weight(w) jako poˇcet nenulov´ych poloˇzek vektoru w. Hammingova vzd´alenost dist(w1 , w2 ) vektor˚ u w1 a w2 v (Z2 )n je ˇc´ıslo weight(w1 − w2 ). Lemma (Hammingova vzd´ alenost je metrika na (Z2 )n ) Plat´ı:a 1
dist(w1 , w2 ) ≥ 0, dist(w1 , w2 ) = 0 pr´avˇe tehdy, kdyˇz w1 = w2 .
2
dist(w1 , w2 ) = dist(w2 , w1 ).
3
dist(w1 , w3 ) ≤ dist(w1 , w2 ) + dist(w2 , w3 ). a
Vzpomeˇ nte si na vlastnosti metriky indukovan´e normou.
Jiˇr´ı Velebil: A7B01LAG
22.12.2014: Line´ arn´ı k´ ody, ˇ c´ ast 2
10/12
Hamming˚ uv (7, 4)-k´ od Hammingova vzd´ alenost
Tvrzen´ı (v´ ypoˇ cet minim´ aln´ı distance k´ odu) At’ W je jine´arn´ı k´od d´elky n a dimense k nad Z2 , at’ w0 je ve W . Potom plat´ı rovnost: min{dist(w, w0 ) | w 6= w0 } = min{weight(w) | w je nenulov´y vektor ve W } D˚ ukaz. Plyne z dist(w, w0 ) = dist(w − w0 , o) = weight(w − w0 ). Definice (minim´ aln´ı distance k´ odu) ˇ ıslu min{weight(w) | w je nenulov´y vektor ve W } ˇr´ık´ame C´ minim´aln´ı distance k´odu W a znaˇc´ıme ji dW .
Jiˇr´ı Velebil: A7B01LAG
22.12.2014: Line´ arn´ı k´ ody, ˇ c´ ast 2
11/12
Hamming˚ uv (7, 4)-k´ od Hammingova vzd´ alenost
Definice (detekce a oprava chyb) ˇ At’ W je jine´arn´ı k´od d´elky n a dimense k nad Z2 . Rekneme, ˇze 1
W detekuje t chyb, pokud pro kaˇzd´e w ve W a kaˇzd´e e takov´e, ˇze weight(e) ≤ t, plat´ı: w + e nen´ı ve W .
2
W opravuje t chyb, pokud pro kaˇzd´e w ve W a kaˇzd´e e takov´e, ˇze weight(e) ≤ t, plat´ı: dist(w, w + e) = dW .
Vˇ eta Line´arn´ı k´od W detekuje dW − 1 chyb a opravuje t <
dW 2
chyb.
Pˇr´ıklady 1
Hamming˚ uv (7, 4)-k´ od: dW = 3.
2
Hamming˚ uv (8, 4)-k´ od: dW = 4.
V´ıce napˇr´ıklad v knize D. J. C. MacKay, Information Theory, Inference and Learning Algorithms, Cambridge Univ. Press, 2003 Jiˇr´ı Velebil: A7B01LAG
22.12.2014: Line´ arn´ı k´ ody, ˇ c´ ast 2
12/12
