Teoria informacji
i kodowanie
Wykład nr 1
Wykład: prof. dr hab. inż. Andrzej Pach
Ćwiczenia i zastępstwo: dr inż. Piotr Chołda
Zalecana literatura
po angielsku:
Todd K. Moon: Error Correction Coding:
Mathematical Methods and Algorithms.
J. Wiley, 2005.
J. Wiley, 2005.
po polsku:
Krzysztof Wesołowski: Podstawy cyfrowych
systemów telekomunikacyjnych.
WKiA, 2003.
Teoria informacji i kodowanie
Wykład nr 1 2
Plan
Trochę historii
System przesyłania informacji
Koszty systemów liczenia
Koszty systemów liczenia
Entropia
Modele kanałów dyskretnych
Przepustowość
Teoria informacji i kodowanie
Wykład nr 1 3
Ważne daty w historii teorii
informacji i kodowania
1948: Claude Elwood
Shannon (1916-2001)
publikuje fundamentalną
pracę pt. A Mathematical
pracę pt. A Mathematical
Theory of
Communication w The
Bell System Technical
Journal. Tekst liczy 55
stron
Teoria informacji i kodowanie
Wykład nr 9 4
Ważne daty w historii teorii
informacji i kodowania cd.
1928: Ralph Vinton Lyon Hartley (1888-1970) publikuje
artykuł Transmission of Information
1950: Richard Wesley Hamming (1915-1998) proponuje
kody nazwane od jego nazwiska
1952: David Albert Huffman (1925-1999) publikuje jako
1952: David Albert Huffman (1925-1999) publikuje jako
doktorant propozycję kodu nienadmiarowego znanego od
jego nazwiska
1954: Irving Reed (ur. 1923) i D. Muller niezależnie od
siebie wprowadzają kody nazwane od ich nazwisk; w
latach 1969-76 NASA będzie ich używać w programie
Mariner
1955: Peter Elias (1923-2001) wprowadza kody splotowe;
Elias zdefiniował również kanał binarny z wymazywaniem
Teoria informacji i kodowanie
Wykład nr 9 5
Ważne daty w historii teorii
informacji i kodowania cd.
1957: E. Prange proponuje kody cykliczne
1959-1960: A. Hocquenghem proponuje niezależnie
od pary Raj Chandry Bose (1901-1987) i Dwijendra
Ray-Chaudhuri (ur. 1933) opisują ważną klasę kodów
Ray-Chaudhuri (ur. 1933) opisują ważną klasę kodów
wielomianowych zwanych skrótowo BCH
wielomianowych zwanych skrótowo BCH
1960: Irving Reed (znany z kodów RM) oraz Gustave
Solomon (1930-1996) proponują ważną klasę kodów
znanych jako kody Reeda-Solomona (w 1977 NASA
użyje ich w misji Voyager, a w 1980 Sony i Philips
zestandaryzują dysk kompaktowy, korzystający z
zabezpieczenia opartego na tym kodzie)
Teoria informacji i kodowanie
Wykład nr 9 6
Ważne daty w historii teorii
informacji i kodowania cd.
1962: wprowadzenie pierwszego modemu o przepływności
2400 b/s tzw. Bell 201 (wcześniej, w latach 50-tych, pojawiły
się modemy 300 i 1200 b/s)
1971: Andrew Viterbi (ur. 1935) proponuje słynny algorytm
Viterbiego dekodowania kodów splotowych (w 1985 był
Viterbiego dekodowania kodów splotowych (w 1985 był
współzałożycielem Qualcommu, który początkowo
produkował urządzenia do transmisji satelitarnej, m.in. z
dekoderem Viterbiego; obecnie Viterbi jest milionerem)
1993: Claude Berrou (ur. 1951), Alain Glavieux (1949-2004)
i Punya Thitimajshima (1954-2006) proponują turbokody;
komitet techniczny konferencji ICC nie chciał przyjąć
artykułu, ponieważ część recenzentów uważała, że
przewidywane właściwości kodu są niewiarygodnie dobre!
Teoria informacji i kodowanie
Wykład nr 9 7
Model systemu telekomunikacyjnego
(rysunek z książki Moona)
Teoria informacji i kodowanie
Wykład nr 1 8
System otwarty
Teoria informacji i kodowanie
Wykład nr 1 9
System zamknięty
Teoria informacji i kodowanie
Wykład nr 1 10
yródła wiadomości
Ze względu na zbiór wiadomości:
- ziarniste (dyskretne)
- ciągłe
- ciągłe
Ze względu na rodzaj rozkładu
prawdopodobieństwa:
- deterministyczne
- probabilistyczne (losowe)
Teoria informacji i kodowanie
Wykład nr 1 11
Przykład 1
A 8.5 R 4.3 U 2.3 1.0
I 7.9 T 4.0 J 2.2 Ż 1.0
O 7.8 Y 4.0 A 2.1 Ó 0.9
O 7.8 Y 4.0 A 2.1 Ó 0.9
E 7.8 C 3.8 L 2.0 Ś 0.7
Z 5.6 K 3.6 G 1.6 0.4
N 5.2 D 3.3 B 1.5 F 0.2
S 5.1 P 3.0 1.3 C 0.2
W 4.6 M 2.8 H 1.2 y 0.1
Teoria informacji i kodowanie
Wykład nr 1 12
Koszt systemów liczenia
Cw(b)
1
b
0,942
Cw(L) =
2log2 b
1 2 e 3 4 5 6 7 b
Teoria informacji i kodowanie
Wykład nr 1 13
Entropia - definicja
m1 m2 ... mN
ł łł
Zbiór wiadomości: M = {m1, m2, ..., mN} M
S = =
[ ]
łp p2 ... pN śł
P
Zbiór prawdopodobieństw: P = {p1, p2, ..., pN}
ł 1 ł
Ilość informacji dostarczona przez jedną wytworzoną
wiadomość ze zródła jest równa średniej niepewności co do
jej otrzymania:
N
( )
H S = - pi log2 pi
[bit /wiadomość]
"
i=1
Teoria informacji i kodowanie
Wykład nr 1 14
Funkcja entropii: postulaty
Postulaty dotyczące entropii mają ujmować nasze intuicje
dotyczące miary niepewności
X zmienna losowa dyskretna (pi=Pr{X=xi})
H(X)=H(p1,p2,& ,pn) entropia (niepewność)
(A1) Funkcja entropii osiąga maksimum, wtedy gdy rozkład
(A1) Funkcja entropii osiąga maksimum, wtedy gdy rozkład
jest jak najbardziej równomierny:
1 1 1
ł ł
max, H(p1, p2,K, pn )= H , ,K,
ł ł
{p1, p2 ,K pn}
n n n
ł łł
(A2) Ą permutacja zbioru {1,& ,n}:
H(p1, p2,K, pn )= H(pĄ (1), pĄ (2),K, pĄ (n))
Liczy się tylko rozkład prawdopodobieństwa, a nie
przyporządkowanie prawdopodobieństw poszczególnym
realizacjom zmiennej losowej
Teoria informacji i kodowanie
Wykład nr 9 15
Funkcja entropii: postulaty cd.
(A3) Miara niepewności jest nieujemna i wynosi zero
jedynie wtedy, gdy losowość zanika:
H(p1, p2 ,K, pn )e" 0, H(p1, p2 ,K, pn )= 0 ! " pi = 1
i
i
(A4)
H(p1, p2,K, pn )= H(p1, p2,K, pn ,0)
Niepewność rzutu sprawiedliwą kostką sześcienną
jest taka sama jak rzutu kostką siedmiościenną, w
której nie może wypaść 7, a pozostałe sześć pól
wypada sprawiedliwie
Teoria informacji i kodowanie
Wykład nr 9 16
Funkcja entropii: postulaty cd.
(A5) Monotoniczność:
ł ł ł ł
ł ł ł ł
1 1 1 1 1 1
H , ,K, d" H , ,K,
ł ł ł ł
n n n +1 n +1 n +
ł 1424n ł ł 144 3
3 424441ł
ł n łł ł n+1 łł
ł n łł ł n+1 łł
Wynik wyścigu, w którym startują dwa konie jest
Wynik wyścigu, w którym startują dwa konie jest
bardziej przewidywalny niż wyścigu, w którym
startują trzy konie
(A6) Entropia jest funkcją ciągłą
Nie może być tak, że niewielka zmiana
prawdopodobieństw realizacji zmiennej losowej
drastycznie zmienia niepewność
Teoria informacji i kodowanie
Wykład nr 9 17
Funkcja entropii: postulaty cd.
(A7) m, n " Z+:
1 1 1 1 1 1 1 1 1
ł ł ł ł ł ł
H , ,K, = H , ,K, + H , ,K,
ł ł ł ł ł ł
mn mn mn m m m n n n
ł łł ł łł ł łł
Warunek liniowości (niepewność co do rzutu kostką m-ścienną, a
następnie n-ścienną jest taka sama jak suma niepewności związanych z
następnie n-ścienną jest taka sama jak suma niepewności związanych z
każdym z tych zdarzeń z osobna)
(A8) p=p1+p2+& +pi+& +pm ; q=q1+q2+& +qj+& +qn ; p+q=1:
ł p1 p2 pi pm ł ł ł
q1 q2 q j qn
ł ł
H(p1, p2,K, pi ,K, pm,q1,q2,K,q ,K,qn)= H(p,q)+ pHł , ,K, ,K, ł + qHł , ,K, ,K,
j
ł ł
ł
p p p p q q q q
ł łł ł łł
Wyobrazmy sobie wyścig, w którym bierze udział m koni czarnych i n
koni białych, w którym prawdopodobieństwo, że wygra i-ty koń czarny
wynosi pi (analogicznie z qj dla koni białych). Całkowita niepewność co
do wyniku wyścigu równa się niepewności związanej z tym, czy wygra
koń czarny czy biały plus ważona suma niepewności co do wygranej
konkretnego konia czarnego lub białego
Teoria informacji i kodowanie
Wykład nr 9 18
Funkcja entropii: postulaty cd.
Tylko funkcja zdefiniowana jako
N
( )
( )
H S = - pi log2 pi
H S = - pi log2 pi
"
"
i=1
spełnia aksjomaty (A1)-(A8)
Teoria informacji i kodowanie
Wykład nr 9 19
Entropia najważniejsze
właściwości
( )
1.
0d" H S d" log2 N
2.
2.
dla równomiernego rozkładu
dla równomiernego rozkładu
prawdopodobieństwa
P = {1/N, 1/N, ..., 1/N}
entropia osiąga maksimum równe:
( )
Hmax S = log2 N
Teoria informacji i kodowanie
Wykład nr 1 20
Entropia binarnego zródła
wiadomości
H (S)
1
m1 m2
m1 m2
ł łł
ł łł
S =
S =
ł śł
łp 1- pśł
0.5
ł ł
p
0.5 1
N
H (S)= -
"p log2pi = -log2 (1-pp
i
p-1
p)
i=1
Teoria informacji i kodowanie
Wykład nr 1 21
Przykład 2
m1 m2
m1 m2
ł łł
ł łł
S1 =
S2 =
ł0.99 0.01śł
ł0.5 0.5śł
ł0.5 0.5śł
2
ł ł
ł0.99 0.01ł
ł ł
ł ł
H(S1) = -0.99log2 0.99 - 0.01log2 0.01 = 0.081 [bit/wiadomośc]
H(S2) = -0.5log2 0.5 - 0.5log2 0.5 = 1 [bit/wiadomośc]
Teoria informacji i kodowanie
Wykład nr 1 22
Rozszerzenie zródła
Niech
X x1 x2 Y y1 y2
ł łł ł łł ł łł ł łł
S1 = = =
2
łP śł łp p2 śł i S = łQśł łq q2 śł
ł ł ł 1 ł ł ł ł 1 ł
Utwórzmy nowe zródło S , które określone jest w sposób następujący:
X Y
ł łł
S'=
łP Q śł
ł ł
W przypadku, gdy S1 = S2 = S, to tak utworzone zródło
nazywamy drugim rozszerzeniem zródła S i oznaczamy je
przez S2. Postępując w podobny sposób możemy utworzyć k -
krotne rozszerzenie zródła S, które będziemy oznaczać przez
Sk.
Teoria informacji i kodowanie
Wykład nr 1 23
Przykład 3
m1 m2
ł łł
S =
ł0.4 0.6śł
ł ł
m1m1 m1m2 m2m1 m2m2
ł łł
S2 =
ł0.16 0.24 0.24 0.36 śł
ł ł
m1m1m1 m1m2m1 m2m1m1 m2m2m1 m1m1m2 m1m2m2 m2m1m2 m2m2m2
ł łł
S3 =
ł 0.064 0.096 0.096 0.144. 0.096 0.144 0.144 0.216 śł
ł ł
Teoria informacji i kodowanie
Wykład nr 1 24
Rozszerzenie zródła, cd.
Jeśli:
m1 m2 ... mn
ł łł
S =
łp p2 ... pN śł
ł 1 ł
jest bezpamięciowym zródłem wiadomości, to:
H(Sk) = k"H(S)
Teoria informacji i kodowanie
Wykład nr 1 25
Przykład 4
m1 m2
ł łł
S =
ł0.4 0.6śł
ł ł
H(S) = -0.4 log20.4 - 0.6 log20.6 = 0.971 [bit]
H(S2) = 2H(S) = 2 " 0.971 = 1.942 [bit]
H(S3) = 3H(S) = 3 " 0.971 = 2.913 [bit]
Teoria informacji i kodowanie
Wykład nr 1 26
Markowowskie zródło
wiadomości
Markowowskim zródłem wiadomości L - tego rzędu
nazywamy zródło, z którego pojawienie się wiadomości zależy
od L wiadomości wygenerowanych przez to zródło w
przeszłości.
Aby takie zródło scharakteryzować, należy każdej wiadomości
Aby takie zródło scharakteryzować, należy każdej wiadomości
przypisać zbiór prawdopodobieństw warunkowych:
( )
mi P mi mj mj ...mjL i,jk "{1,2,...,N}
1 2
Każdej wiadomości jest przyporządkowanych N L
prawdopodobieństw.
Teoria informacji i kodowanie
Wykład nr 1 27
Przykład 5
0.1
Zbiór wiadomości: M = {m1, m2}, L = 2
m1m1
0.9 0.5
0.5
m1m2
m2m1
0.3
P {m1 m1m1}= 0.1, P {m2 m1m1}= 0.9
0.4
0.7
m2m2
P {m1 m1m2}= 0.3, P {m2 m1m2}= 0.7
P {m1 m2m1}= 0.5, P {m2 m2 m1}= 0.5
P {m1 m2m2}= 0.4, P {m2 m2m2}= 0.6.
0.6
Teoria informacji i kodowanie
Wykład nr 1 28
Języki naturalne: przybliżenie
zerowego i pierwszego rzędu
Założenie o rozkładzie równomiernym liter
(przybliżenie zerowego rzędu):
DM QASCJDGFOZYNX ZSDZLXIKUD
Założenie o rozkładzie częstotliwości
Założenie o rozkładzie częstotliwości
występowania liter (przybliżenie pierwszego
rzędu) dla języka angielskiego:
OR L RW NILI E NNSBATEI
Widać, że trzeba uwzględnić zależności
wewnątrzwyrazowe
Teoria informacji i kodowanie
Wykład nr 9 29
Języki naturalne: przybliżenie
Markowa pierwszego rzędu
Dla języka angielskiego:
OUCTIE IN ARE AMYST TE TUSE SOBE
CTUSE
Dla łaciny:
IENEC FES VIMONILLITUM M ST ER PEM
ENIM PTAUL
Teoria informacji i kodowanie
Wykład nr 9 30
Języki naturalne: przybliżenia
Markowa wyższych rzędów
2-go rzędu dla j. angielskiego:
HE AREAT BEIS HEDE THAT WISHBOUT SEED
DAY OFTE, AND HE IS FOR THAT MINUMB
LOOTS WILL AND GIRLS, A DOLL WILL IS
FRIECE ABOARICE STRED SAYS
FRIECE ABOARICE STRED SAYS
2-go rzędu dla łaciny:
SENECTOR VCI QUAEMODOMIS SE NON
FRATURDIGNAVIT SINE VELIUS
2-go rzędu dla j. francuskiego:
MAITAIS DU VEILLECALCAMAIT DE LEU DIT
3-go rzędu dla j. francuskiego:
DU PARUT SE NE VIENNER PERDENT LA TET
Teoria informacji i kodowanie
Wykład nr 9 31
Przykład 6
Rozważmy zródło markowowskie pierwszego rzędu. Prawdopodobieństwo
wystąpienia pary wiadomości (mi, mj) jest określone wzorem
P mimj = P mi " P mj mi .
( )
( ) ( )
Zatem średnia ilość informacji związana z parą wiadomości dostarczona przez
zródło (entropia łączna H(mi m )) wynosi
zródło (entropia łączna H(m mj)) wynosi
N N
H mimj = - P mimj log2 P mimj .
( ) " " ( ) ( )
i=1 j=1
Średnia ilość informacji związana z wiadomością podaną przez zródło pod
warunkiem, że znamy wiadomość ją poprzedzającą (entropia warunkowa
H(mjłmi) wynosi
N N
H (mj | mi)= - (mimj)log2 P (mj | mi).
""P
j=1 i=1
Teoria informacji i kodowanie
Wykład nr 1 32
Kanały
Dyskretne (ziarniste)
Ciągłe
Binarne
Binarne
Bezpamięciowe
Stacjonarne
Symetryczne
Bezszumowe
Teoria informacji i kodowanie
Wykład nr 1 33
Kanał dyskretny z
zakłóceniami
Ciągi odebrane
Ciągi nadane
1 1
2 2
2 2
i j
M N
Zakłócenia w kanale
Teoria informacji i kodowanie
Wykład nr 1 34
Typy kanałów
Ciągi nadane - xi = xi1,xi2 ,...,xin , i = 1,2,...,M
( )
yj = yj1,yj2,...,yjn , j = 1,2,...,N
Ciągi odebrane - ( )
łP(y1 x1) P(y1 x2) L P(y1 xi) L P(y1 xM) łł
ł śł
(y2
(y2
łP x1) P(y2 x2)L P(y2 xi)L P(y2 xM) śł
łP x1) P(y2 x2) L P(y2 xi) L P(y2 xM) śł
ł M M M M śł
ł śł
łP x1) P(yj x2) L P(yj xi) L P(yj xM) śł
(yj
ł śł
ł M M M M śł
łP x1) P(yN x2) LP(yN xi)L P(yN xM) śł
(yN
ł ł
( ) ( ) ( )
P (y x )= P yj1 xi1 " P yj2 xi2 "..." P yjn xin Kanał bezpamięciowy
i
j
P S1 S2 = P S2 S1 = pe Binarny kanał symetryczny
( ) ( )
Teoria informacji i kodowanie
Wykład nr 1 35
Kanał binarny
P(S1łS1) = 1 - P(S2łS1)
S1 S1
P(S1łS2)
P(S2łS1)
S2
S2
P(S2łS2) = 1 - P(S1łS2)
Teoria informacji i kodowanie
Wykład nr 1 36
Binarny kanał symetryczny
P(S1łS1) = 1 - P(S2łS1)
S1 S1
P(S1łS2)
łS
P (S1 S2)= P (S2 S1)= BER
P(S2łS1)
BER = Bit Error Rate
S2
S2
(bitowa stopa błędów)
P(S2łS2) = 1 - P(S1łS2)
Teoria informacji i kodowanie
Wykład nr 1 37
Kanał binarny z
wymazywaniem
P(s1łs1)
s1 s1
P(xłs1)
x
P(xłs2)
s2 s2
P(s2łs2)
Teoria informacji i kodowanie
Wykład nr 1 38
Kanał bezszumowy
x1
y1
y2
x2
xN
yN
Teoria informacji i kodowanie
Wykład nr 1 39
Kanał z paczką błędów
Teoria informacji i kodowanie
Wykład nr 1 40
Informacja wzajemna
(transinformacja)
X = {x1, x2, ..., xm} - zbiór sygnałów wejściowych
Y = {y1, y2, ..., yn} - zbiór sygnałów wyjściowych
Wówczas transinformacja (miara średniej ilości informacji
związanej z wiadomością przesłaną kanałem), to:
związanej z wiadomością przesłaną kanałem), to:
n m
P xi yj
( )
( )
I X ;Y = P xi , yj log2
"" ( )
P xi
( )
j=1i=1
Teoria informacji i kodowanie
Wykład nr 1 41
Przepustowość kanału
Przepustowością kanału C nazywamy
maksymalną wartość transinformacji:
C = max I (X ;Y )= max[H (X )- H (X Y)]
{pi} {pi}
Teoria informacji i kodowanie
Wykład nr 1 42
Przykład 7
Dla kanału bezszumowego, przepustowość jest największa:
log N
2
[ ]
C = log2 N bit / wiadomość . ( C = [bit/s] )
Dla kanału symetrycznego:
Dla kanału symetrycznego:
C = max [H(X )- H(X Y)]= 1+ pe log2 pe + (1- pe)log2(1- pe)
{pe ;1- pe}
1
dla pe = 1- pe = .
2
Dla kanału z wymazywaniem:
C = max[H(X )- H(X Y)]= q
p;1- p
Teoria informacji i kodowanie
Wykład nr 1 43
Twierdzenie Shannona o kodowaniu
kanałowym
Transmisja kanałem binarnym z
dowolnie małym
prawdopodobieństwem błędu
prawdopodobieństwem błędu
jest możliwa wtedy, jeśli
sprawność kodowania R nie
jest większa od
przepustowości kanału C.
Teoria informacji i kodowanie -
Wykład 1 44
Wyszukiwarka
Podobne podstrony:
wyklad 1pTIiK Wykład 11 2008Sieci komputerowe I Wykład 1PTIiK Wykład 11P 2009TIiK Wykład 1TIiK Wykład 9 2009PChF Wyklad 1pSieci komputerowe wyklady dr FurtakWykład 05 Opadanie i fluidyzacjaWYKŁAD 1 Wprowadzenie do biotechnologii farmaceutycznejmo3 wykladyJJZARZĄDZANIE WARTOŚCIĄ PRZEDSIĘBIORSTWA Z DNIA 26 MARZEC 2011 WYKŁAD NR 3więcej podobnych podstron