Wykład 1

Teoria informacji - teoria opisująca prawa (matematyczne) rządzące przesyłaniem i przetwarzaniem informacji.

Teoria informacji zajmuje się - pomiarem informacji, reprezentacją informacji (m.in. kodowaniem) oraz pojemnością i możliwościami systemów informacyjnych i (tele)komunikacyjnych, służących przesyłaniu i przetwarzaniu informacji.

Kodowanie odnosi się m.in. do zamiany np. mowy lub obrazów na sygnały elektryczne i elektromagnetyczne lub szyfrowania wiadomości w celu zapewnienia prywatności.

Teoria informacji dostarcza w szczególności odpowiedzi na dwa pytania:

•Jaka jest nieredukowalna złożoność sygnału, poniżej której sygnał ten nie może już zostać skomprymowany?

•Jaka jest największa możliwa szybkość transmisji, zapewniająca niezawodną komunikację za pośrednictwem zaszumionego kanału?

Ważnym wynikiem otrzymanym na podstawie Teorii informacji jest stwierdzenie, że jeśli entropia źródła jest mniejsza od pojemności kanału, możliwa jest bezbłędna komunikacja za pośrednictwem kanału.

Informacja jest wiadomością, która zmienia naszą wiedzę i należy traktować ją jako synonim słów„nowa wiadomość”

INFORMACJĄ nazywamy wielkość abstrakcyjną, która może być:

•przechowywana w pewnych obiektach,

•przesyłana między pewnymi obiektami,

•przetwarzana w pewnych obiektach,

•stosowana do sterowania pewnymi obiektami,

Komunikat jest samoistnym obiektem fizycznym (np. tekst pisany, modulowana fala elektromagnetyczna), podczas gdy wiadomość skłonni bylibyśmy traktować jako relację zachodzącą między nadawcą i odbiorcą.

Wiadomość może być przekazana tylko w postaci komunikatu

Teoria informacji to matematyczna teoria przekazywania sygnałów niosących informację.

Zakres problemów wchodzących w teorię informacji, to ocena ilości informacji jaką niesie sygnał(wiadomość)oraz sposób przetwarzania w celu zabezpieczenia przed błędami w trakcie przesyłania w zawodnym, losowo przekształcającym sygnały, kanale.

Podstawowe założenie ilościowej teorii informacji polega na tym,że dany komunikat zawiera tym więcej informacji, im mniejsze jest prawdopodobieństwo wystąpienia sytuacji w nim opisanej.

Wykład 2

Bezpamięciowe źródło wiadomości - jest to obiekt, który z wiadomości elementarnych, tworzących ustalony i skończony zbiór: S = {s1, s2, …, sq},wytwarza ciąg wiadomości elementarnych P(s1), P(s2),……, P(sq),przy czym Źródło Psiiq()=Σ=11

Niech E będzie pewnym zdarzeniem, które zachodzi z prawdopodobieństwem P(E).Jeżeli zaobserwowaliśmy zdarzenie E wtedy mówimy, że odebraliśmy

I(E)=log(1/P(E)) jednostek informacji

Jednostka entropii 2 - bit, e - nat, 10 hartley

Warunki ilości informacji:

1) I(s_i) = 0 dla p_i=1 nieuzyskujemy żadnej informacji

2) I(s_i) >= 0 dla 0=<p_i=<1 nie tracimy informacji

3) I(s_i) > I(s_q) dla p_i<p_q im mnie. Prawd. Zdarzenia, tym więcej zyskujemy przez jego zaistnienie

4) I(s_i s_q) = I(s_i) + I(s_q) gdy si i sq statys. niezależne

Średnia ilość informacji przypadająca na wiadomość elementarną wytwarzaną przez to źródło

Ilość przekazywanych informacji jest odwrotnie Proporcjonalna do prawdopodobieństwa wystąpienia zdarzenia.

Entropia jest funkcją częstotliwości występowania określonych konfiguracji.

Aby móc określić entropię musimy mieć do czynienia z wielokrotnym pomiarem zmieniającego się układu.

Entropia osiąga maksymalną wartość, jeśli każda możliwa konfiguracja występuje tak samo często. Entropia jes tminimalna, ma wartość 0, jeśli układ znajduje się zawsze w jednej konfiguracji.

H(X) =

0=<H(X)<=log₂Q

Entropia charakteryzuje tylko rozkład prawdopodobieństwa

Własności entropii (średnia ilość informacji przypadająca na realizację zmiennej losowej).

1. Entropia zawsze ma dodatnią wartość.

H(X)>=0, bo pi*log(1/pi)>=0

2. Wartość Min gdy jedno ze zdarzeń jest pewne a pozostałe 0

Pi = 1 gdy i = k

Pi = 0 gdy i != k } H(X) = Hmin = 0 bo lim p->0 (p log (1/p)) = 0

Warunek normy prawdopodobieństwa

3. Przy zadanej mocy N zbioruX jego entropia będzie maksymalna (log N), jeżeli Prawdopodobieństwa wystąpienia wszystkich zdarzeń należących do X są jednakowe i wynoszą 1/N. Górny kres entropii odpowiada maksimum niepewności

max H(X) = log n dla x1 = .. x1/n, gdzie p(x1), …, p(xn) = 1/n

Własności entropii bin. Źródła bez pamięci:

1. Gdy p0=0, H(X)=0 (xlogx ->0 gdy x->0)

2. Gdy p0=1, H(X)=0

3. Hmax = 1 bit, przy p1=p0=1/2, gdy symbole 1,0 są równoprawdopodobne

Entropia binarnego źródła bez pamięci

H(p0) = -p0 log₂ p0 -(1-p0) log₂ (1-p0)

Wykład 3

Źródło dyskretne bezpamięciowe - mamy źródło S, które generuje {s1,s2, ,sk} z pradopodobieństwem wiadomości p1,p2,p3, pk, n-krotne rozszerzenia źródła Sⁿ , źródła S - nazywać będziemy bezpamięciowe źródło wiadomości generujące ciągi n-wiadomości(czyli k^{n .}

Elementów) {σ1, σ2, σkⁿ }

Sⁿ = σi = S_i1,S_i2, Sij, , S_in

P(σi)=1,2,3...,kⁿ .

Pojedyncza wiadomosc ze zródła Sn odpowiada n

wiadomoscia elementarnym ze zródła S, entropia

przypadajaca na pojedyncza wiadomosc ze

zbioru Sn bedzie n razy wieksza ni% entropia

przypadajaca na pojedyncza wiadomosc ze

zbioru S

H(Sⁿ ) nH(S)

Entropia n-tego rozszerzenia jest n razy większa od entropii źródła.

Zmienna losowa dwuwymiarowa:

p(xi) p(yj/xi) p(xi,yj) i=1, 2, ...,n, j=1, 2,...,m

p(xi) * p(yj/xi) = p(xi,yj)

Entropia zmiennej losowej dwuwymiarowej

H(X,Y)=H(X)+H(Y/X)=H(Y)+H(X/Y)

Jeśeli zdarzenia wchodzace w skład zbiorów X i Y sa

statystycznie niezależne wtedy to entropia prostego iloczynu

tych zbiorów (X oraz Y) bedzie równa sumie entropii tych

zbiorów

p(xi,yj)= p(xi) p(yj)

H(X,Y)=H(X)+H(Y)

Zależności łączące pradopodobieństwa:

H(X,Y)=H(X)+H(Y/X)=H(Y)+H(X/Y)

Ilość informacji:

Ile informacji niesie zdarzenie: zmiana entropii.

I(A)=H(X) - H(X/A)

Oraz

I(X,Y)- srednia ilosc informacj

I(X,Y)=H(X)+H(Y)-H(X,Y)

H(X,Y)= H(X)+H(Y/X)=H(Y)+H(X/Y)

I(X,Y)=H(Y)-H(Y/X)

I(X,Y)=H(X)-H(X/Y)

X->Y

I(X,Y)=I(Y,X) przy przekazywaniu jednego

znaku -> gdy macierz kanału jest

symetryczna.

I(Y,X)=H(X) - H(X/Y)

I(X,Y)=H(Y) - H(Y/X)

Srednia ilosc informacji przypadajaca na

odbiór jednego znaku.

Entropia Układów ciągłych:

H_R(X)-entropia zredukowana

Δx-dok.pomiaru

Wykład 4

Źródło ciągów Markowa m-tego rzędu nazywamy źródło wytwarzające q różnych wiadomości, w których pojawienie się danej wiadomości si może zależeć od skończonej liczby m wiadomości, jakie pojawiło się ostatnio.

Własności źródła:

Jeżeli dany jest zbiór jego elementów S i zbiór prawdopodobieństw warunkowych

Dla źródeł ciągów Markowa m-tego rzędu prawdopodobieństwo wytworzenia danej wiadomości jest określone, jeżeli znamy m poprzednich wiadomości.

Dla dowolnego momentu czasu, m poprzednich wiadomości traktujemy jako stan źródła ciągów Markowa m-tego rzędu w tym momencie. Źródło może wytwarzać q różnych wiadomości, może zatem przyjmować q^m różnych stanów.

Stan źródła ulega więc zmianom wraz z wytwarzaniem kolejnych wiadomości.

Rodzaje źródeł:

-nieergodyczne, występuje gdy nie możemy przejść do innego stanu

-ergodyczne, jest to źródło, które będzie wytwarzać z prawdopodobieństwem 1, typowy ciąg wiadomości

Istnieje pewien specyficzny rozkład pradopodobieństwa na zbiorze stanów ergodycznego źródła ciągów Markowa, według którego będą pojawiały się poszczególne stany w długim ciągu wiadomości wytwarzanych przez to źródło. Rozkład ten nazywamy stacjonarnym rozkładem prawdopodobienstwa egodycznego procesu Markowa.

Prawdopodobieństwo zdarzenia łącznego wynosi:

Entropia źródła S ciągów Markowa m-tego rzędu:

Prawdopodobieństwo pojawienia się wiadomości si

Źródła stowarzyszone ze źródłem Markowa:

Dla źródła ciągów Markowa pierwszego rzędu zbiór stanów jest identyczny ze zbiorem wiadomości wytwarzanych przez źródło, a rozkład stacjonarny daje nam bezpośrednio rozkład prawdopodobieństwa pierwszego rzędu.

Źródło bezpamęciowe nieS generujące ten sam zbiór wiadomości co źródło S z prawdopodobieństwami granicznymi takimi samymi jak w Markowie nazywamy źródłem stowarzyszonym ze źródłem S:.

Zdefiniowane źródło nieS, które generuje nam taki sam ciąg wiadomości i robi to z takimi samymi pradopodobieństwami:

Entropia źródła stowarzyszonego nieS nie jest nigdy mniejsza niż entropia źródła S.

.

Obydwa źródła maja identyczne rozkłady prawdopodobieństw pierwszego rzędu, różnią się one tym, że na źródło S narzucone są dodatkowe ograniczenia wyrażone za pomocą warunkowych rozkładów prawdopodobieństwa, którym podlegają wytworzone przez to źródło ciągi wyjściowe.

Warunkiem równości jest fakt, żeby źródło S było rzeczywiście bezpamięciowe.

Wykład 5

Teoria informacji:

-dyskretyzacja źródeł ciągłych

-kwantowanie i próbkowanie

-twierdzenie Shannona

-Interpolacje

-Częstotliwość próbkowania

Większość urządzeń pomiarowych lub rejestrów sygnałów w systemach pomiarowych kontaktujących się bezpośrednio z obiektami badań reaguje na oddziaływania fizyczne zmieniające się w sposób ciągły. Aby te informacje mogły być przetworzone przez system komputerowy muszą być przetworzone w kodowane sygnały cyfrowy. Rolę tę spełniają przetworniki analogowo-cyfrowo(A/C) umieszczone na styku części analogowej i cyfrowej systemu.

Wybór przetwornika na podstawie:

-rodzaj stosowanego kodu

-fizyczny charakter sygnału analogowego i dopuszczalny zakres jego zmian na wejściu przetwornika

Parametry charakteryzujące

• rzeczywisty zakres przetwarzania

• całkowy błąd przetwarzania

• współczynnik różniczkowej nieliwości przetwornik

• częstotliwość przetwarzania

Przetwarzanie ciągłego sygnały analogowego sygnał polega: dyskretyzacji sygnału w czasie czyli próbkowaniu, dyskretyzacji wartości sygnału czyli kwantowaniu oraz na kodowaniu tak uzyskanego sygnału dyskretnego.

Sygnały dyskretne - próbkowane pod względem czasu powstają przez próbkowanie sygnałów analogowych w dyskretnych przedziałach czasu bez kwantowania amplitudy

Sygnały kwantowane - sygnały dyskretne pod względem amplitudy, przyjmującymi skończoną liczbę stanów

Sygnały cyfrowe - uzyskuje się, gdy sygnał wejściowy jest próbkowany w dyskretnych przedziałach czasowych, zaś amplituda jest kwantowana na dyskretne poziomy ze zbioru wartości dopuszczonego przez konkretne urządzenie. Sygnały te są określone przez dobrze zdefiniowane poziomy nazywane poziomami logicznymi. W urządzeniach cyfrowych są to zazwyczaj dwa poziomy, odpowiadające cyfrom 0 oraz 1 w kodzie binarnym.

Dyskretyzacja - przekształcenie funkcji ciągłej na jej wartości chwilowe, wyborze pewnego skończonego ciągu par (xi,ti) z nieskończonego zbioru ( x(t),t).

Próbkowanie - fizyczne pobieranie próbek, czyli chwilowych reprezentacji wielkości analogowej. Gdy wybiera się ti, i dla nich mierzy się xi może przebierać każdą wartość z tego przedziału.

Częstotliwośc próbkowania powoduje, że oryginalny sygnał analogowy będzie posiadał lepszą reprezentacje w systemie cyfrowym.

Kwantowanie polega na zaokrąglaniu wartości wyznaczonej próbki do takiej, którą przy danej rozdzielczości cyfrowej można zapisać w postaci zadanej liczby bitów.

Minimalny błąd średniokwadratowy kwantowania równomiernego ze skokiem delta.

Twierdzenie Shannona o próbkowaniu:

Jeśli funkcja losowa x(t) spełnia warunki Dirichleta:

-jest ograniczona

-odcinkami ciągła

-ma skończoną liczbę ekstremów

-jeśli jej widmo jest ograniczone i równe zeru poczynając od częstotliwości f_g

Twierdzenie Bernsteina:

Jeśli funkcja losowa X(t) posiada widmo ograniczone i równe zero począwszy od częstotliwości fg oraz ograniczony moduł |X|_max, to maksymalna wartość jej k-tej pochodnej |X^(k)|_max

Spełnia nierówność:

---