Varno kodiranje

Enostavni kodi

Ponavljajoči kodi

$L(n,1)$: namesto enega pošljemo $n$ enakih znakov

Kod je zelo počasen $\to$ naj se $n$ in $k$ povečueta hitreje kot $m=n-k$

Kontrolne vsote

Podatkovnim bitom dodamo nekaj paritetnih bitov za preverjanje parnosti
Nastavljeni so, da je vsota bitov po modulu 2 fiksna vrednost ($0$ ali $1$)

Pravokotni in trikotni kod

Pravokotni kod: sodost po vrsticah in stolpcih

• Zaznavanje in popravljanje 1 napake

Trikotni kod: vsota elementov v stolpcu in vrstici s paritetnim bitom mora biti soda

• Zaznavanje in popravljanje 1 napake, a z manj kontrolnimi biti - boljša hitrost
  

Hammingova razdalja koda

Hammingova razdalja med kodnima zamenjavama: št. znakov, po katerih se razlikujeta (primerjaš 1., 2. itd. zaporedni znak in šteješ razlike)

Hammingova razdalja koda:

$$d_H=mind(\overrightarrow{x_a},\overrightarrow{x_b})$$

Pove nam, koliko napak lahko:

• odkrijemo

$$e_{MAX}=d_H-1$$

• popravimo

$$f_{MAX}=\lfloor \frac{d_H-1}{2}\rfloor$$

Hammingov pogoj

Da bi pravilno dekodirali vse kodne zamenjave, kjer je prišlo do $e$ ali manj napak, mora veljati:

$$M\le \frac{2^n}{{\sum }_{i=0}^f\left(\genfrac{}{}{0ex}{}{n}{i}\right)}$$

oz.

$$\check{s}t.razli\check{c}nihsporo\check{c}il\le \frac{vsemo\check{z}nosti}{velikostotoka}$$

Linearni bločni kodi

Linearni bločni kodi $L(n,k)$:

• vsota kodnih besed je kodna beseda
• produkt kodne besede s konstanto je kodna beseda (zato moramo imeti zmeraj kodno zamenjavo samih ničel)

Hammingova razdalja linearnega koda = št. enic v kodni zamenjavi z najmanj enicami
Generatorska matrika: $G$ dimenzij $k\ast n$

$$\vec{x}=\vec{z}\ast G$$

Paritetna matrika: $H$ dimenzij $m\ast n$ (dobimo jo iz enačb)

$$\vec{x}\ast H^T=0⟺H\ast \overrightarrow{x^t}=0$$ $$G\ast H^T=0$$

Sistematični kodi: podatkovni in varnostni biti v $G$ so ločeni: $G=(I_k|A)oz.G=(A|I_k)$

Sindrom

Ko se v kanalu zgodijo napake, prejemnik zaradi njih ne more takoj preveriti podatkov
Izračunamo sindrom in preverimo, kje se je zgodila napaka: $\vec{s}=\vec{0}$ - ni napake, v primeru $>1$ napak pa lahko poslabšamo

$$\vec{s}=\vec{y}\ast H^T=\vec{e}\ast H^T$$

Ker je verjetnost dveh (ali več) napak veliko manjša od verjetnosti ene napake, popravljamo samo enojne

Hammingov kod

$H(2^m-1,2^m-1-m)$ zna popraviti 1 napako

Ciklični kodi

$C(n,k)$ je LBK, v katerem vsak krožni premik kodne zamenjave da drugo kodno zamenjavo, in nobena kodna zamenjava ne manjka

Zapis s polinomi

$$x(p)=x_{n-1}{p}^{n-1}+...+x_{1}p+x_0$$

Krožni premik polinoma za $i$ mest:

$$x^i(p)=p^i\ast x(p)mod(p^n+1)$$

Generatorski in paritetni polinom

$$g(p)=1p^m+g_{m-1}{p}^{m-1}+...+g_{1}p+1$$

Krožni premiki: $[g(p),p\ast g(p),p^{2}g(p),...]$

$$g(p)\ast h(p)=0mod(p^n-1)$$ $$x(p)\ast h(p)=0$$