uvedení do problematiky i Bezpečnostní kódy: detekční kódy = kódy zjišťující chyby samoopravné kódy = kódy opravující chyby příklady kódů:

I. Bezpečnostní kódy • • • • • • • • • • • • • •

úvod základní pojmy počet zjistitelných a opravitelných chyb 2prvkové těleso a lineární prostor jednoduché bezpečnostní kódy lineární kódy Hammingův kód smysluplnost bezpečnostních kódů kódy a mnohočleny násobení mnohočlenů dělení mnohočlenů kódy generované mnohočleny detekce shluků chyb cyklické kódy

JPO 2005/6

c A. Pluháček 31.5.2006

uvedení do problematiky

i

Bezpečnostní kódy: • detekční kódy = kódy zjišťující chyby • samoopravné kódy = kódy opravující chyby příklady kódů: b a 0 0 1 1

0 1 0 1

K1 000 011 101 110

a = (a1 , . . . , ak ) b = (b1 , . . . , bn ) kódová, slova nekódová, JPO 2005/6

K2 111 001 010 100

0 0 1 1

K3 000 101 010 111

0 1 1 0

α β γ δ

původní informace slovo, vektor, znak přípustné, anebo znaky nepřípustné. I1



ii

principy: • zjišťování (detekce) chyb: slovo není kódovým slovem • opravy (korekce) chyb: slovo se nahradí „nejpodobnějšímÿ kódovým slovem K1 umožňuje zjistit 1 chybu (ale i jiný lichý počet chyb) K2 umožňuje zjistit 1 chybu (ale i jiný lichý počet chyb) K3 umožňuje zjistit 2 chyby (ale i nějaký jiný počet chyb) anebo opravit 1 chybu, ale nikoliv obojí ! ! ! příklad: kód K3 — přijato (přečteno) ψ=11100 α se liší ve 3 bitech „správnéÿslovo: δ=11110 β se liší ve 4 bitech =⇒ γ se liší ve 2 bitech a = 11 (pravděpodobně) δ se liší ve 1 bitu JPO 2005/6

I2



a b e c s d JPO 2005/6

— — — — — —

původní data kódové slovo chyba přijaté slovo syndrom opravená data I3

(k bitů) (n bitů) (n bitů) (n bitů) (m bitů) (k bitů)

iii

příklad 11 11110 00010 11100 010 11 c A. Pluháček 5.6.2006 (opraveno)

základní pojmy kód: a → b, ale někdy pouze množina kódových slov !!! kód (n, k): a → b, kde b je nbitové a a je kbitové k . . . informační obsah (entropie) m = n − k . . . nadbytečnost (redundance) systematický kód: a → b, kde bi = ai pro i ≤ k bity bi pro i ≤ k . . . informační část slova bity bi pro i > k . . . kontrolní část slova příklady: K1 je systematický kód (3,2) K2 je nesystematický kód (3,2) K3 je systematický kód (5,2)

Hammingova vzdálenost: • vzdálenost dvou slov — počet odlišných bitů např. vzdálenost 11100 a 01011 je rovna 4 • kódová vzdálenost kvzd — minimální vzdálenost dvojic kódových slov, např. K1 : kvzd=2, K2 : kvzd=2, K3 : kvzd=3 JPO 2005/6

I4


geometrická interpretace Hammingovy vzdálenosti

n

n

K1

JPO 2005/6

K3

I5


počet zjistitelných a opravitelných chyb

Je-li kódová vzdálenost kvzd = dch + och + 1 , kde dch a och jsou přirozená čísla a platí dch ≥ och, lze detekovat (zjistit) dch chyb a opravit och z nich. příklady: kvzd = 2 ⇒ lze zjistit 1 chybu, ale nelze ji opravit kvzd = 3 ⇒ lze zjistit 2 chybu, ale nelze je opravit anebo zjistit a opravit 1 chybu (je třeba se rozhodnout pro jednu alternativu) kvzd = 4 ⇒ lze zjistit 3 chybu, ale nelze je opravit anebo zjistit 2 chyby a ale opravit jenom 1 chybu

JPO 2005/6

I6


2prvkové těleso a lineární prostor

2prvkové těleso GF(2):

[Galoise ﬁeld]

0 + 0 = 0 0 · 0 = 0 0 + 1 = 1 0 · 1 = 0 1 + 0 = 1 1 · 0 = 0 1 + 1 = 0 1 · 1 = 1 tzn. XOR tzn. AND x + x = 0 ⇒ −x = +x x+0=x

a

x+1=x

lineární / vektorový prostor nad tělesem GF(2): v = (v1 , . . . , vj ), u = (u1 , . . . , uj ), v + u = (v1 + u1 , . . . , vj + uj ) v+0=v 0·v=0 JPO 2005/6

a a

v+v=0

⇒

a

0 = (0, . . . , 0)

−v = +v

1·v=v I7

c A. Pluháček 5.6.2006 (opraveno)

jednoduché bezpečnostní kódy

① opakovací (repetiční) kód

i

př.: n = 5

(n, 1):

b1 = . . . = bn = a1 0 00000 1 11111 kvzd = n velká redundance =⇒ malý informační obsah

② „koktavýÿ kód

(jk, k): jkrát se opakuje totéž (k bitů) př.: j = 3, k = 4 K′ 0000 0001 0010 ... 1110 1111

☞

0000 0000 0000 0001 0001 0001 0010 0010 0010 ... 1110 1110 1110 1111 1111 1111

K′ nebo K′′ K′′

000 000 000 000 000 000 000 111 000 000 111 000 ... 111 111 111 000 111 111 111 111

kvzd = j velká redundance =⇒ malý informační obsah JPO 2005/6

I8



ii

③ parita

(k+1, k): a = (a1 , . . . , ak ) → b = (b1 , . . . , bn ), kde n = k + 1 b1 = a1 , . . . , bk = ak , bn = p, kde p = a1 + · · · + ak — parita (sudá) b1 + · · · + bn = 0 chyby — vektor chyb e = (e1 , . . . , en ) ⇒ c = (c1 , . . . , cn ) = b+e žádná chyba ⇒ c1 + · · · + cn = 0 syndrom s = s = c1 + · · · + cn s = 0 ⇒ žádná chyba anebo sudý počet chyb s 6= 0 ⇒ chyba anebo chyby (lichý počet) příklady:

JPO 2005/6

1.

a=11010 b=11010 1 e=00010 0 c=11000 1 s=1 I9

2.

a=11110 b=11110 0 e=00000 0 c=11110 0 s=0 c A. Pluháček 31.5.2006


iii

③ parita

(k+1, k): pokračování b = (a1 , . . . , ak , p) minimální redundance × pouze detekce 1 chyby sudá: p = a1 + · · · + ak parita lichá: p = a1 + · · · + ak + 1

④ příčná a podélná parita: kbitové a, kde k = kr × ks ➜ kr řádků a ks sloupců každý řádek a každý sloupec zabezpečen paritou př.: k = 4 = 2×2 b = (a1 , . . . , a4 , p1 , . . . , p4 ), resp. b = (a1 , . . . , a4 , p1 , . . . , p5 ): kód (9,4) a1 a2 p1 a3 a4 p2 p3 p4 p5 kvzd = 4

kód (8,4) a1 a2 p1 a3 a4 p2 p3 p4 kvzd = 3 JPO 2005/6

I 10


lineární kódy

i

Příklad: 4 bity zabezpečené 3 paritami b1 b2 b3 b4 b5 b6 b7

= = = = = = =

a1 a2 a3 a4 a1 + a2 + a4 = p1 a1 + a3 + a4 = p2 a2 + a3 + a4 = p3

b =a·G,

kde



1  0 G=  0 0

b1 + b2 + b4 + b5 = 0 b1 + b3 + b4 + b6 = 0 b2 + b3 + b4 + b7 = 0 JPO 2005/6

I 11

0 0 0 1 1 1 0 0 1 0 0 1 0 0 1 0 0 1 1 1 generovací matice

 0 1   1  1


lineární kódy

c1 + c2 + c4 + c5 = s1 c1 + c3 + c4 + c6 = s2 c2 + c3 + c4 + c7 = s3 s = c · HT ,

kde

ii

s = (s1 , s2 , s3 ) — syndrom 

1 H= 1 0

1 0 1 1 0 0 1 1 0 1 1 1 1 0 0 kontrolní matice

 0 0  1

• Kódovými slovy jsou lineární kombinace řádků matice G. • Množina kódových slov tvoří lineární (neboli vektorový) prostor

lineární kód — kódová slova tvoří lineární prostor. pozn.: Opakovací i „koktavéÿ kódy a všechny kódy zabezpečené sudými paritami jsou lineární kódy. JPO 2005/6

I 12


lineární kódy

b · HT = 0

⇒

iii

s = c · HT = (b + e) · HT = 0 + e · HT

s = c · HT = e · HT

⇒ Syndrom závisí pouze na chybě!

špatně i-tý bit v c ⇒ e = 0. . .010. . .0 — jednička v pozici i s = c · HT = e · HT = i-tý sloupec matice H Příklad:

b = a · G = 1101 100 e = 0001 000 c = 1100 100 s = c · HT = 1 1 1 ⇒ špatně 4. bit a = 1 1 0 1,

kód pro opravu 1 chyby: sloupce matice H musí být nenulové a vzájemně různé JPO 2005/6

I 13


lineární kódy

G = (Ik , F)

←→

iv

H = (−FT , Im )

Im a Ik . . . jednotkové matice m × m a k × k počet sloupců obou matic n = m + k

Nemá-li matice požadovaný tvar, lze u ní • zaměňovat řádky, • přičítat k řádkům lineární kombinaci jiných řádků. Nestačí-li to, lze permutovat sloupce matice, ale u získané druhé matice je třeba provést opačnou permutaci sloupců.

JPO 2005/6

I 14


Hammingův kód

i

Hammingův kód: • tzv. „perfektní kód pro opravu 1 chybyÿ, jinak: • matice H o m řádcích má všech n = 2m − 1 sloupců tedy: m n k 2 3 1 3 7 4 4 15 11 5 31 27 6 63 57 7 127 120 8 255 247 9 512 503 10 1023 1013 .. .. .. . . . JPO 2005/6

I 15


Hammingův kód

příklad — Hammingův  0 H= 0 1 operace:

1+2 → 1’,  0 H’ =  1 1  1  0 G=  0 0

ii

kód (7,4) 0 1 0

0 1 1

1 0 0

3+1’ → 3’, 1 0 1

1 1 0

1 1 1

0 1 0 0

0 0 1 0

0 0 0 1

1 0 1

1 1 0

 1 1  1

2+3’ → 2’  1 0 0 0 1 0  0 0 1  0 1 1 1 0 1   1 1 0  1 1 1

Jako kontrolní matici, lze použít matici H’ i matici H. JPO 2005/6

I 16


Hammingův kód

iii

kodér — Hammingův kódu (7,4) 

1  0 G=  0 0

JPO 2005/6

0 1 0 0

0 0 1 0

I 17

0 0 0 1

0 1 1 1

1 0 1 1

 1 1   0  1


Hammingův kód

iv

dekodér — Hammingův kódu (7,4) 

0 H= 0 1

JPO 2005/6

0 1 0

0 1 1

I 18

1 0 0

1 0 1

1 1 0

 1 1  1


smysluplnost bezpečnostních kódů

Má vůbec smysl používat bezpečnostní kódy ? • parita: • Hammingův kód: .. .. . . Pravděpodobnost: P . . . pravděpodobnost n bitů i chybných: P jinak: P = 10−9

příklad:

polovina chyb n z 2n −1 chyb .. .

výskytu chybného bitu n · P i · (1 − P )n − i i 32b / 1µsec 32 · 10−9 . . . 31 sec 33 · 10−9

nějaká chyba kód

nějaká chyba

53 · 10−15 . . . 61,3 roků 38 · 10−9

(33,32) sudý počet chyb kód

??? ??? ???

nějaká chyba

(38,32) neopravitelná chyba 7 · 10−16 . . . 46,0 roků JPO 2005/6

I 19


kódy a mnohočleny mnohočleny nad tělesem GF(2): C(x) = cn−1xn−1 + · · · + c1x + c0

ci ∈ GF(2) x∈?

mnohočleny stupně < n: • vektorový/lineární prostor (bez skalárního součinu) • izomorfní s prostorem uspořádaných ntic: cn−1xn−1 + · · · + c0 ∼ (cn−1, . . . , c0) př.: n = 7 x5 +x3 +x+1 ∼ 0101011 • izomorﬁe — jen:

součet

&

násobení skalárem

mnohočleny: • násobení a dělení mnohočlenů — obv. postup • analogie s okruhem celých čísel — dělitelnost značení: P (x) | Q(x) . . . P (x) je dělitelem Q(x) P (x) 6 | Q(x) . . . P (x) není dělitelem Q(x) JPO 2005/6

I 20


násobení mnohočlenů

i

G(x) = x3+x+1 A(x) = x2+1 B(x) = G(x) · A(x) = ? (x3+x+1) · (x2+1)

x5+x3+x2 x3+ x+1 x5+ x2+x+1 = B(x)

zkrácený zápis: g = 1011 a = 0101 b=g·a=? 1011 · 0101

0 0 0 0

1 0 1 1

0 0 0 0

1 0 1 1 0 1 0 0 1 1 1 = b JPO 2005/6

I 21


násobení mnohočlenů

JPO 2005/6

I 22

ii


dělení mnohočlenů

i

zkrácený zápis: C(x) : G(x)

6543210

C(x) = x6+x2+x G(x) = x3+x+1

1000110 1011

1·x6 +0·x5 +0·x4 +0·x3 +1·x2 +1·x+0 =⇒ 1·x6 +0·x5 +1·x4 +1·x3 0·x5 +1·x4 +1·x3 +1·x2 =⇒ 0·x5 +0·x4 +0·x3 +0·x2 1·x4 +1·x3 +1·x2 +1·x =⇒ 4+ 3+ 2+ 1·x 0·x 1·x 1·x 1·x3 +0·x2 +0·x+0 =⇒ 1·x3 +0·x2 +1·x+1 0·x2 +1·x+1 ⇓ zbytek C(x) % G(x) = x+1 podíl C(x) ÷ G(x) = x3+x+1 JPO 2005/6

I 23

1·x3 ←֓ 0·x2 ←֓ 1·x ←֓ 1 ←֓ ⇓ ⇐

1011 011 c A. Pluháček 31.5.2006


ii

C(x) : G(x) C(x) = x6+x2+x = c6x6 + · · · + c0 G(x) = x3+x+1 = g 3x3 + · · · + g 0 dělení přímo ve zkráceném zápise: 1 0 0 1 0 1 0 0 1 0 0 0 1 1 0

0 1 1 0 1 0 1 1 0

1 ↓ 1 0 1 1 0 0 0

JPO 2005/6

1 | | ↓ 1 1 0 1 1

0 : 1 0 1 1 =1 0 1 1 | | | | ↓ 0 1 1

I 24



JPO 2005/6

I 25

iii


kódy generované mnohočleny A(x) ∼ a B(x) ∼ b G(x)

... ... ...

původní informace vyslané slovo generovací mnohočlen B(x) = A(x) · G(x)

C(x) ∼ c E(x) ∼ e

... ...

přijaté slovo chybový mnohočlen C(x) = B(x) + E(x)

S(x)

...

syndrom S(x) = C(x) % G(x)

B(x) % G(x) = 0 S(x) = C(x) % G(x) = E(x) % G(x) syndrom závisí pouze na chybách JPO 2005/6

I 26


detekce shluků chyb E(x) = E ′ (x)·xj x 6 | E (x) ′

=⇒

E(x) je shluk chyb délky l = (deg E ′ (x))+1 posunutý o j míst doleva

př.: E(x) = x5+x3+x2 ∼ 0101100 shluk chyb délky 4 E ′ (x) = x3+x+1 ∼ 1011 j = 2 deg E ′ (x) = 3 detekce chyb: S(x) = E(x) % G(x) = 0 ? x 6 | G(x) =⇒ xj nemá vliv E ′ (x) % G(x) = 0 ? ′ deg E (x) < deg G(x) =⇒ E ′ (x) % G(x) 6= 0 ′ E (x) 6= 0 =⇒ detekce shluků chyb délky l ≤ m = deg G(x) Např. kód generovaný mnohočlenem G(x) = x16+1 zjišťuje shluky chyb délky l ≤ 16 JPO 2005/6

I 27


cyklické kódy cyklický kód: 1. lineární kód 2. cyklický posuv kódového slova → kódové slovo Každý kód generovaný mnohočlenem je lineární. G(x) | (xn −1) , kde n je délka kódového slova Potom ∃H(x) G(x)·H(x) = xn − 1 a kód generovaný mnohočlenem G(x) je cyklický. Předp.

H(x)

...

kontrolní mnohočlen

př.: x7+1 = (x3+x+1)(x4+x2+x+1) Kód (7,4) generovaný G(x) = x3+x+1 je cyklický. H(x) = x4+x2+x+1 je kontrolní mnohočlen. Skutečnost, že kód je cyklický, je důležitá pro opravy shluků chyb. JPO 2005/6

I 28


uvedení do problematiky i Bezpečnostní kódy: detekční kódy = kódy zjišťující chyby samoopravné kódy = kódy opravující chyby příklady kódů:

Recommend Documents