UL/FRI/UNI-RI/OTI/Izpiti/2007-03-28

Iz E-študij, proste zakladnice študentskega znanja

Skoči na: navigacija, iskanje

Izpit z dne 28.03.2007
UL/FRI/UNI-RI/OTI

Čas pisanja: 60 minut.
Literatura: samo kalkulator.

1. naloga

Za komunikacijo po dvojiškem komunikacijskem kqanalu se uporabljata znaka "nič" in "ena". Zaradi motenj pri prenosu prihaja do napak. Ve se, da je verjetnost oddajanja znaka "nič" 0.5, verjetnost previlnega prenosa znaka "nič" 0.75 in verjetnost napake pri prenosu znaka "ena" 0.5. Kdaj sprejemete več informacije: v primeru, ko poznate sprejeti znak in izveste kateri znak je bil oddan, ali v primeru, ko poznate oddani znak in izveste kateri znak je bil sprejet? Kolkišna je razlika?

Rešitev

najprej razpredelnica:

Y\X    0     1
0    0.375  0.25   0.625
1    0.125  0.25   0.375
     0.5    0.5    1

naloga sprašuje po $H (X | Y)$ in $H (Y | X)$ , računamo po delih

$H (X | Y = 0) = H (0.6,0.4) = 0.97 b i t$

$H (X | Y = 1) = H (1 / 3,2 / 3) = 0.92 b i t$

$H (X | Y) = 0.625 * H (X | Y = 0) + 0.375 * H (X | Y = 1) = 0.9512 b i t$

podobno za $H (Y | X)$ dobimo 0.9056 bit

razlika med njima je 0.0456 bit

Opomba: $H (X | Y)$ lahko računamo tudi po $H (X | Y) = H (X, Y) - H (Y)$ , kar saj pri meni povzroča dosti manj napak.

2. naloga

Vir brez spomina oddaja znake A={a, b, c, d} z vrejetnostmi P = {0.2, 0.2, 0.2, 0.4}. Znake želimo s Huffmanovim postopkom kodirati v abecedo B = {0, 1}. Opredelite dobljene kode glede enakomernosti, enoznačnosti in trenutnosti, ter izračunajte učinkovitost!

Rešitev

lahko dobimo 2 kombinaciji huffmanovih kodov, sta enakovredni:

a=11, b=10, c=01, d=00: enakomeren, enoznačen, trenuten

a=111, b=110, c=10, d=0: neenakomeren, enoznačen, trenuten

povprečna dolžina je pri obeh 2

H(0.2, 0.2, 0.2, 0.4)=1.922 bit

učinkovitost: H/N=1.922/2=0.961

3. naloga

Izračunajte kapaciteto diskretnega komunikacijskega kanala, v katerega vstopata znaka $x 1$ in $x 2$ iz njega pa izstopajo $y 1$ , $y 2$ in $y 3$ ! Kanal dobro opisuje verjetnostna matrika

$P_k = \left[\begin{array}{ccc} 0,5 & 0,25 & 0,25\\ 0,5 & 0 & 0,5 \end{array} \right]$

Rešitev

kapaciteta: $C = m a x {I (X; Y)} = m a x {H (X) - H (X | Y)}$

za ta maksimum moramo uporabit razporeditev X (0.5, 0.5)

A ne bi mogl to nalogo tko delat da daš za vrjetnosti $α$ in $1 - α$ pol bi pa odvajal da dobiš vn maksimalne zadeve...Vsaj pomojem...

se strinjam. To se rešuje kot na vajah, torej z nelepim odvodom :)

zdej iz tiste matrike izračunamo $H (X | Y)$ :

$H (X | Y = y 1) = H (0.5,0.5) = 1 b i t$

a tuki si se Px kr spomnu... vidm da gledaš vsoto stolpca samo zakaj tako: jst sm vzel razmerje med zgornjo in spodnjo številko v stolpcu, če kdo misli da to ni prav nej kr pove, tud jst nism doktor OTIja :P

$H (X | Y = y 2) = H (1,0) = 0 b i t$

$H (X | Y = y 3) = H (1 / 3,2 / 3) = 0.918 b i t$

pol to skupi zmečemo:

$H (X | Y) = (0.5 * p x 1 + 0.5 * p x 2) * 1 b i t + (0.25 * p x 1 + 0.5 * p x 2) * 0.918 b i t$

v drugi vrstici smo modro ugotovili da sta $p_x1,\ p_x2=0.5$

zato je $H (X | Y) = 0.724 b i t$

$C = H (0.5,0.5) - H (X | Y) = 1 - 0.724 = 0.276$

Pravilna resitev (100%) je $I (X; Y) = 0,16$ // Da, to je pravilna resitev! Dodajam svoj postopek:

$p 1 = x$ $p 2 = 1 - x$

To sta verjetnosti, ki nam povesta, ce pride na vhod x1 ali x2.

Nato si lahko naredimo tabelo:

  x/y|   y1  |  y2 | y3    | X
  x1 |  x/2  | x/4 | x/4   | x
  x2 |(1-x)/2| 0   |(1-x)/2| 1-x
Y-lon|  1/2  | x/4 |(2-x)/4|

Zadeva je malo zamaknjena, ampak sej, ce se potrudte, boste vidl kaj pise. :) Skratka...dobis ji tko, da prvo vrstica matrike mnozis z x, drugo vrstico pa z (1-x).

Ko imamo to, lahko zapisemo:

$C = m a x {I (x; y)}$

Vemo, da je $I (x; y) = H (x) - H (x | y) = H (y) - H (y | x)$

Jaz sem si za racunanje zbram drugo varjanto, ker pridejo lepse stevilke...

Se pravi zapisemo:

$H (y) = H (1 / 2, x / 4,(2 - x) / 4)$

$H (y | x) = x * H ((x / 2) / x,(x / 4) / x,(x / 4) / x) + (1 - x) * H ((1 - x) / 2) / (1 - x),0 / (1 - x),((1 - x) / 2) / (1 - x)) =$ $= x * H (1 / 2,1 / 4,1 / 4) + (1 - x) * H (1 / 2,0,1 / 2) = 3 x / 2 + (1 - x) = '''(2 + x) / 2'''$

In zdej pride na vrsto zoperen del...racunanje. :)

$I (x; y) = - 1 / 2 * l o g 1 / 2 - x / 4 * l o g x / 4 - (2 - x) / 4 * l o g (2 - x) / 4 - (2 + x) / 2$

Ker iscemo maksimalno kapaciteto, moramo najti maksimum tega, kot zgoraj pise( $C = m a x {I (x; y)}$ ). Zato moramo to odvajati po x-u in ker iscemo maksimum, enacimo odvod informacije z 0.

Also...to se mi ne da pisat, kako to odvajamo, mal ponovite odvode pa bo slo. :) Skratka, ven dobimo $x = 0.4$ .

(/////****** ekola tu imete postopek za odvod in resitev x

http://www.wolframalpha.com/input/?i=solve[D[-1/2*log[2,1/2]+-+x/4+*+log[2,+x/4]+-+(2-x)/4+*+log[2,+(2-x)/4]+-+(2%2Bx)/2+,x],x]

)

Zdaj lahko poracunamo:

$H (y) = H (1 / 2,1 / 10,4 / 10) = 1,36$

$H (y / x) = 1,2$

$I (x; y) = 1,36 - 1,2 = 0,16$

4. naloga

Izdelajte logično shemo za kodirnik cikličnega polinoma $g (p) = p 3 + p + 1$ , nato pa za kod z=(0101) pokažite, kako se s kodirnikom zgenerira ustrezna kodna zamenjava!

Rešitev

ne da se mi razlagat kako deluje LFSR, glejte učbenik.

korak	x	vhod	p^3
0	000	0	0
1	000	1	1
2	110	0	0
3	011	1	0
4	001

tako dobimo $x = (0101 | 100)$

5. naloga

Z uporabo z-transformacije rešite diferenčno enačbo $8x(k)-6x(k-1)+x(k-2)=0,\ k \ge 0$ , z začetnima pogojema $x ( - 2) = 0$ , $x ( - 1) = - 1$ !

Uporabna zveza: $Z\{a^k\} = {z \over z-a}$

Rešitev

Za potrebe Z transformacije enačbo najprej množimo z $z - k$ ter sumiramo od $k = 0$ do $\infty$ :

$8 \cdot \sum_{k=0}^{\infty} x(k) \cdot z^{-k} - 6 \cdot \sum_{k=0}^{\infty} x(k-1) \cdot z^{-k} + \sum_{k=0}^{\infty} x(k-2) \cdot z^{-k} = 0$

Ker moramo enačbo spraviti v obliko, primerno za transformacijo, izračunamo nekaj členov iz vsote, da bomo kasneje s premikom k-ja lahko dobili vsote enakih oblik:

$8 \cdot \sum_{k=0}^{\infty} x(k) \cdot z^{-k} - 6\cdot x(-1) - 6 \cdot z^{-1} \cdot \sum_{k=1}^{\infty} x(k-1) \cdot z^{-(k-1)} + x(-2) + x(-1)\cdot z^{-1} + z^{-2}\cdot \sum_{k=2}^{\infty} x(k-2) \cdot z^{-(k-2)} = 0$

Sedaj uvedemo $k' = k - 1$ ter $k'' = k - 2$ , vstavimo začetne pogoje, opravimo Z transformacijo in dobimo:

$8\cdot X(z) - 6 - 6\cdot z^{-1}\cdot X(z) + z^{-1} + z^{-2}\cdot X(z) = 0$

Izpostavimo X(z) ter preuredimo enačbo in razčlenimo imenovalec:

$X(z) = \frac{\frac{1}{8} z\cdot (6\cdot z-1)}{(z-\frac{1}{2})\cdot (z-\frac{1}{4})}$

Sledi razvoj v delne ulomke ter izračun residuumov:

$x(z) = \frac{X(z)}{z} = \frac{\frac{1}{8} \cdot (6\cdot z-1)}{(z-\frac{1}{2})\cdot (z-\frac{1}{4})} = \frac{R_{\frac{1}{2}\, 1}}{(z-\frac{1}{2})^1} + \frac{R_{\frac{1}{4}\, 1}}{(z-\frac{1}{4})^1}$