Treti prednaska z Kodovani a sifrovani
Zaklady teorie kodovani
Obsah
Kodovanim zpravy rozumime jeji zmenu, ktera obvykle zpravu
prodlouzi a zajisti jeji prenos bezpecnejsim zpusobem (oproti
naruseni vnejsimi vlivy - sum atp.).
Obecne schema prenosu zpravy
zdroj zpravy -> kodovani -> vysilac -> sum -> prijimac ->
dekodovani -> prijemce zpravy.
Pro jednoduchost budeme uvazovat kody nad dvouprvkovou abecedou
0,1. Podobne definice a uvahy se daji provadet pro libovolnou
abecedu, nad jejimiz prvky lze definovat operace nasobeni a
scitani tak, aby vysledna struktura tvorila teleso. Netrivialni
algerbaicky vysledek rika, ze takova abeceda musi mit p^n prvku,
kde p je prvocislo.
Blokovy kod
Blokovym kodem stupne n nazveme libovolnou mnozinu n-tic prvku
vstupni abecedy 0,1.
Linearni kod
Linearnim (n,k)-kodem nazveme linearni podprostor K dimenze k
prostoru {0,1}^n. Prvky tohoto prostoru chapeme jako "povolena"
kodova slova (je jich 2^k). Kazde toto slovo je posloupnost n nul
a jednicek. Ukolem dekoderu je pro libovolny prvek prostoru
{0,1}^n predstavujici zasumene prijate slovo najit nejblizsi
prvek kodoveho podprostoru K.
Prenosovy pomer
je pomer delky nezakodovane zpravy a zpravy zakodovane. U
linearnich (n-k)-kodu je na zakodovani informace delky k potreba
vyslat posloupnost n znaku a prenosovy pomer kodu je tedy k/n.
Vaha kodu
Vaha slova je pocet jeho nenulovych slozek. Vaha kodu je
minimalni vaha jeho nenulovych slov.
Hammingova vzdalenost
Hammingovou vzdalenosti dvou slov u a v rozumime vahu slova u-v,
tedy pocet mist, na kterych se slova u a v lisi. Hammingova
vzdalenost splnuje axiomy metriky. Uloha dekodovani zni nalezt
pro dane slovo u z {0,1}^n prvek v z kodoveho podprostoru K,
ktery ma od u nejmensi Hammingovu vzdalenost. Pokud je takovy
prvek urcen jednoznacne, rikame, ze chyba vznikla pri prenosu je
opravitelna.
Opravovani chyb
Rikame, ze linearni kod je schopen opravovat t chyb, pokud pro
kazdy prvek prostoru u {0,1}^n, ktery ma od nejakeho kodoveho
slova v kodu K
Hammingovu vzdalenost mensi nebo rovnu t, neexistuje jine kodove
slovo v' z K, ktere by od u melo Hammingovu vzdelenost tez mensi nebo rovnu
t. Jinymi slovy, dekodovani slov, u kterych doslo pri prenosu
k maximalne t chybam je jednoznacne. Plati, ze pokud je d vaha
kodu K a t<2d, pak kod K je schopen opravovat alespon t chyb.
Generujici matice
Necht K je (n,k)-linearni kod. u1, u2, ..., uk je libovolna baze
tohoto kodu. Pak matice A velikosti n krat k, kde jsou v
jednotlivych radcich pod sebou napsany vektory u1,u2, ..., un se
nazyvy generujici matice kodu.
Proverkova matice
Necht K je (n,k)-linearni kod. Matice B velikosti (n-k,n) takova,
ze jeji radky jsou linearne nezavisle a ze pro kazde kodove slovo
v z K plati Bv=0 se nazyva proverkova matice kodu K.
Syndrom
Necht K je (n,k)-linearni kod, B jeho proverkova matice a u
libovolne slovo z {0,1}^n. Slovo B.u (jeho delka je n-k) se
nazyva syndrom slova u pro kod K. Slova s nulovym syndromem jsou
prave kodova slova kodu K.
Dualni kod
Necht K je (n,k)-linearni kod, A jeho generujici matice a
B jeho proverkova matice. Kod K', ktery ma B za generujici matici
a A za proverkovou matici se nazyva dualni kod ke kodu K. Jedna
se skutecne o dualitu, dualni kod ke kodu K' je opet kod K.
Opakovaci kod radu 3 ma obsahuje slova (0,0,0) a (1,1,1). Je to
(3,1)-linearni kod. Jeho generujici matice je velikosti 3x1
proverkova matice je velikosti 3x2
Vaha kodu je 3, kod je schopen opravovat 1 chybu. Kapacita kodu
je 1/3.
Opakovaci kod radu 5 ma obsahuje slova (0,0,0,0,0) a (1,1,1,1,1). Je to
(5,1)-linearni kod. Jeho generujici matice je velikosti 5x1
proverkova matice je velikosti 5x4.
Vaha kodu je 5, kod je schopen opravovat 2 chyby. Kapacita kodu
je 1/5.
Priklad (6,3)-kodu.
Generujici matice je
Proverkova matice je
Vaha kodu je 3, kod opravuje jednu chybu, prenosovy pomer je 1/2. Dualni
kod ma stejne vlastnosti ((6,3)-kod, vaha 3, opravuje 1 chybu, prenosovy pomer
1/2).
Hamminguv kd radu n je (2^n-1,2^n-n-1) kod, jehoz proverkova
matice vznikne tak, ze se do sloupcu napisou nenulove
vektory delky n.
Takovych vektoru je 2^n-1, proverkova metice ma tedy n radku a
2^n-1 sloupcu. Generujici matice ma 2^n-1 sloupcu a 2^n-1-n
radku.
Hammingovy kody maji vahu 3 a opravuji 1 chybu (bez dukazu -
plyne to z obecnych algebraickych vet). Jejich prenosovy pomer
je rovna (2^n-1-n)/2^n-1 a se zvysujicim n se tedy zvysuje k 1.
Timto zpusobem je tedy mozne sestrojit kod s libovolnym
prenosovym pomerem (mensi nez 1), ktery opravuje 1 chybu. Ovsem za cenu
velmi sloziteho kodovani a dekodovani pri vysokem n.
Hamminguv kod radu 2 je opakovaci kod radu 3.
Hamminguv kod radu 3 ma proverkovou matici velikosti 7x3
| 1 | 1 | 1 | 0
| 1 | 0 | 0 |
| 1 | 1 | 0 | 1
| 0 | 1 | 0 |
| 1 | 0 | 1 | 1
| 0 | 0 | 1 |
Genrujici matice je velikosti 7x4, napr.
| 1 | 1 | 0 | 0
| 0 | 0 | 1 |
| 1 | 0 | 1 | 0
| 0 | 1 | 0 |
| 1 | 0 | 0 | 1
| 1 | 0 | 0 |
| 0 | 1 | 1 | 1
| 0 | 0 | 0 |
Je to (7,4)-kod, ktery ma vahu 3, opravuje 1 chybu a ma prenosovy pomer
4/7.
Tuto stranku vytvoril
Tomas Vanicek a jedna se o soucast volitelnych prednasek z
Kodovani a sifrovani pro
vsechny obory
Stavebni fakulty
Ceskeho vysokeho uceni technickeho v Praze.