[1]
´ Uvod do ko´dova´nı´ • samoopravne´ ko´dy: terminologie, princip • blokove´ linea´rnı´ ko´dy • Hammingu˚v ko´d
[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)
[3]
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
[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 .
[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.
[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).
[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.
[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“.
[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.
[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 my´ 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.
[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.
[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ˇ.
[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.
[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ı´.
