Wykład 9, Informatyka Magisterskie SGGW, Teoria Informacji TI, Egzamin
[ Pobierz całość w formacie PDF ]
//-->Teoria informacji, 16.05.2013Kanał: [X,P(Y|X),Y]C=maxI(X;Y)p(x)I(X;Y) =H(Y)−H(Y|X)=−∑ ∑p(x, y)log2x yp(y|x)p(y)p(y|x)=∑ ∑p(y|x)p(x)log2∑p(y|x)p(x)x yxC=1−H2(p)H2(p) =−plogp−(1−p)log(1−p)Fundamentalne twierdzenia ShannonaTwierdzenie 1 - kanał bezszumny˙Niech zródło ma entropi˛H(bitów/symbol) oraz niech kanał komunikacyjny ma przepustowo´cC(bitów/sek). Wtedy mozli-´es´C˙ ´we jest zakodowanie informacji wysyłanej ze zródła przez ten kanał w taki sposób, ze srednia pr˛ dko´c transmisji wynosiH−ε´e s´C˙symboli/sek, gdzieεjest dowolnie małe. Niemozliwa jest transmisja z pr˛ dko´cia wi˛ ksza nizH.e s ˛ e˛ ˙Twierdzenie 2 - kanał zaszumionyDany jest dyskretny kanał o przepustowo´ciCoraz dyskretne zródło o entropiiH.Je´liH C,to istnieje system kodowania taki,s´s˙˙˙ze sygnał zródła moze by´ transmitowany przez kanał z dowolnie mała cz˛ sto´cia bł˛ dów. Je´liH>Cto mozliwe jest zakodowanie´c˛ e s ˛ es˙sygnału ze zródła w taki sposób, ze niejednoznaczno´c jest mniejsza odH−C+ε,gdzieεjest dowolnie małe. Nie istnieje metoda´s´kodowania, która daje mniejsza niejednoznaczno´c nizH−C.˛s´ ˙Kod blokowy Humminga (7,4)s(source)t(transmission)00000000000000100010110010001011100110011100010001001100101010110101100110001011101110101000100010110011001110101010100101011101100111001100011110111010001110111010011111111111Tst=G1100001000010GT=0001111001111011Pierwsze transmitowane bity - identyczne z bitami zródła, pozostałe 3 bity - bity parzysto´ci´sI - parzysto´c bitów zródłowych 1,2,3s´´II - parzysto´c bitów zródłowych 2,3,4s´´III - parzysto´c bitów zródłowych 1,3,4s´´Kod Humminga odebrany:r1,r2,r3,r4,r5,r6,r7˙˛Aby wykry´ bład szukamy bitu wspólnego dla wszystkich kół nieszcz˛ sliwych, ale jednocze´nie lezacego na zewnatrz kół szcz˛ -c ˛e´s˛e´sliwychPrzykład 11000101⇒1100101Przykład 21000101⇒1010101Przykład 31000101⇒100011123
[ Pobierz całość w formacie PDF ]