Kanal

Kanal lahko povzroči napake v podatkih (npr. šum) $\to$ sporočila opremimo z dodatnimi podatki za preverjanje in/ali popravljanje napak

Diskretni kanal brez spomina

Prehodna / pogojna verjetnost - če smo imeli na vhodu $x_i$, da je iz kanala prišel $y_j$

$$p(y_j)=\sum _{i=1}^{r}p(x_i)\ast p(y_j/x_i)$$ $$\sum _{j=1}^{s}p(y_j/x_i)=1$$

Vezana verjetnost:

$$\sum _{i=1}^r\sum _{j=1}^{s}p(x_i,y_j)=1$$

Obrat kanala

Bayesovo pravilo - če smo dobili iz kanala $y_j$, kako verjetno je bil poslan $x_i$

$$p(x_i/y_j)=\frac{p(x_i)\ast p(y_j/x_i)}{p(y_j)}$$

Pogojna entropija

Verjetnost za nek $y$ pr nekem $x_i$:

$$H(Y/X=x_i)=-\sum _{j=1}^{s}p(y_j/x_i)\ast lo{g}_r(y_j/x_i)$$

Verjetnost za nek $y$ pri kateremkoli $x$:

$$H(Y/X)=-\sum _{i=1}^{r}p(x_i)\ast H(y/X=x_i)=-\sum _{i=1}^r\sum _{j=1}^{s}p(x_i,y_j)\ast lo{g}_r(p(y_j/x_i))$$ $$0\le H(Y/X)\le H(Y)$$

Vezana entropija

$$H(X,Y)=-\sum _{i=1}^r\sum _{j=1}^{s}p(x_i,y_j)\ast log(p(x_i,y_j))$$

Medsebojna informacija

Kapaciteta kanala

$$C=maxI(X;Y)$$

Kapaciteto kanala maksimiziramo preko verjetnosti vhdonih znakov

Binarni Simetrični Kanal: $C=1-H(p,1-p)$

Binarni Kanal z Brisanjem (BEC): $C=1-p$

II. Shannnov teorem

Združevanje znakov v bloke $\to$ bolj verjeten zanesljiv prenos
Več kontroolnih bitov $\to$ večja zanesljivost, a počasneje

Histrost koda:
$k$ podatkovnih bitov, $m$ kontrolnih bitov, $n$ vseh poslanih bitov v bloku; $M$ št. različnih kodnih zamenjav

$$R=\frac{maxH(X^n)}{n}=\frac{log(M)}{n}$$

Za $R\le C$ obstaja kod, ki zagotavlja tako prevajanje informacije, da je verjetnost napake pri dekodiranju poljubno majhna
Za $R>C$ tak kod ne obstaja