Teoria sygnałów dla opornych - PUTWiki
/**/







/**/





/**/





Teoria sygnałów dla opornych

Z PUTWiki

Skocz do: nawigacji, wyszukiwania


Spis treści [ukryj]

1 WAŻNE!
2 Podstawowe pojęcia

2.1 Ilość informacji

2.1.1 Przykład 1
2.1.2 Przykład 2


2.2 Entropia

2.2.1 Własności entropii
2.2.2 Przykład 1


2.3 Rozszerzenie źródła bezpamięciowego

2.3.1 Przykład 1
2.3.2 Przykład 2


2.4 Źródło ciągów Markowa


3 Kodowanie źródła

3.1 Kodowanie Huffmana
3.2 Kodowanie Shannona-Fano

3.2.1 Przykład 1
3.2.2 Przykład 2
3.2.3 Przykład 3


3.3 Dynamiczne kodowanie Huffmana
3.4 Inne algorytmy kodowania


4 Wykrywanie i korekcja błędów

4.1 Dodanie bitu parzystości

4.1.1 Przykład 1
4.1.2 Przykład 2


4.2 Ciąg sprawdzający parzystość ramki

4.2.1 Przykład 1
4.2.2 Przykład 2


4.3 Kodowanie Hamminga



if (window.showTocToggle) { var tocShowText = "pokaż"; var tocHideText = "ukryj"; showTocToggle(); }
[edytuj] WAŻNE!
W tym artykule nie znajdziesz (raczej) definincji podręcznikowych.
Ten artykuł jest napisany, aby pomóc Ci zrozumieć materiał. Powstał on
na podstawie wykładów z Mikroelektorniki prowadzonych przez prof. dr.
hab. inż. A. Handkiewicza oraz materiałów dostępnych w wikipedii.

[edytuj] Podstawowe pojęcia
Źródło informacji - coś, co wysyła informacje.
Alfabet źródła - wszystkie możliwe wiadomości elementarne wysyłane ze źródła.
Wiadomość - jeden element z alfabetu źródła.
Informacja - wiedza uzyskana dzięki wiadomościom wysyłanym ze źródła.

Przykład 1
Mamy alfabet bitowy X = {0,1}.
Wiadomościami tego alfabetu są: 0,1.
Przykładowa infomacja: 01001 składa się z pięciu (5) wiadomości, kolejno: 0,1,0,0,1.

Przykład 2
Mamy podane wszystkie wiadomości pewnego źródła informacji: 00,10,11
Alfabet tego źródła to X = {00,10,11} UWAGA! Ciąg 01 nie należy do tego źródła!
Przykładowa infomacja, którą można zapisać tym alfabetem to: 10001100, składa się z 4 wiadomości: 10,00,11,00

Źródło bezpamięciowe
Źródło nazywamy bezpamięciowym, gdy wiadomości należące do jego alfabetu X = {a1,...,aK} są generowane statystycznie niezaleźnie od siebie z prawdopodobieństwami odpowiednio P(a1),...,P(aK).


[edytuj] Ilość informacji
Wiadomość a jest wysyłana ze źródła z prawdopodobieństwem P(a). Gdy odbiorca otrzyma wiadomość uzyskuje jednostek informacji. Współczynnik r zależy od przyjętej jednostki informacji:
r = 2 - jednostką informacji jest bit,
r = e - jednostką informacji jest nat,
r = 10 - jednostką informacji jest hartley.


[edytuj] Przykład 1
Wiadomość x jest wysyłana ze źródła z prawdopodobieństwem P(x) = 0,5 (inne wiadomości tak na prawdę nas nie obchodzą). Oblicz, ile bitów informacji otrzyma odbiorca po odebraniu wiadomości x.
Podstawiamy do wzoru następujące wartości:
r = 2 (bo interesują nas bity informacji)
P(x) = 0,5 (podane w treści):

Odpowiedź: Odbiorca otrzymał 1 bit informacji.

[edytuj] Przykład 2
Wiadomość d jest wysyłana ze źródła z prawdopodobieństwem P(d) = 0,01. Oblicz, ile hartley'ów informacji otrzyma odbiorca po odebraniu wiadomości d.
Podstawiamy do wzoru następujące wartości:
r = 10 (bo interesują nas hartley'e informacji)
P(d) = 0,01 (podane w treści)

Odpowiedź: Odbiorca otrzymał 2 hartley'e informacji.

[edytuj] Entropia
Pod adresem http://pl.wikipedia.org/wiki/Entropia_%28teoria_informacji%29 można znaleźć artykuł dot. tego pojęcia, jednak postaram się przybliżyć tutaj w kilku słowach, o co chodzi.
Entropią nazywamy średnią ilość informacji przypadającą
na pojedynczą wiadomość ze źródła informacji. Innymi słowy jest to
średnia ważona ilości informacji niesionej przez pojedynczą wiadomość,
gdzie wagami są prawdopodobieństwa nadania poszczególnych wiadomości.
Wzór na entropię:
Dla danego alfabetu: X = {a1,...,aK}

W przypadku źródła bezpamięciowego:


[edytuj] Własności entropii

Entropia osiąga swoje maksimum, gdy każda wiadomość jest wysyłana z jednakowym prawdopodobienstwem P(ai) = 1 / K.
Własność superpozycji - gdy dwa systemy są niezależne to entropia sumy systemów równa się sumie entropii.

[edytuj] Przykład 1
Dany jest źródło o alfabecie X = {a,b,c,d} oraz prawdopodobieństwami P(a) = 0,5;P(b) = 0,25;P(c) = 0,125;P(d) = 0,125. Oblicz entropię tego źródła.


= 0,5 * log22 + 0,25 * log24 + 2 * 0,125 * log28 =
= 0,5 * 1 + 0,25 * 2 + 2 * 0,125 * 3 = 0,5 + 0,5 + 0,75 = 1,75
Entropia tego źródła wynosi: H(X) = 1,75 [bitów/wiadomość].

[edytuj] Rozszerzenie źródła bezpamięciowego
Dane jest źródło bezpamięciowe o alfabecie X = {a1,...,aK} i rozkładzie prawdopodobieństwa P(a1),...,P(aK). Rozszerzeniem n-tym tego źródła nazywamy źródło bezpamięciowe o alfabecie , w którym wiadomość bj jest blokiem składającym się z n wiadomości z alfabetu X oraz alfabet Xn zawiera wszystkie możliwe kombinacje n-elementowe ze zbioru X.
Rozszerzenie powinno zawierać Kn elementów.
Dodatkowo , czyli prawdopodobieństwo nowej wiadomości jest iloczynem prawdopodobieństw wiadomości "składowych" z pierwszego alfabetu.
Można wykazać, że entropia źródła rozszerzonego H(Xn) spełnia zależność: H(Xn) = nH(X).

[edytuj] Przykład 1
Dane jest źródło o alfabecie X = {a,b,c} oraz rozkaładzie prawdopodobieństwa P(a) = 0,5;P(b) = P(c) = 0,25. Podaj drugie rozszerzenie tego źródła oraz oblicz entropię źródła rozszerzenia.
Rozwiązanie:
Entropia źródła X:
H(X) = 0,5 * log22 + 2 * 0,25 * log24 = 1,5
Drugie rozszerzenie źródła
X2 = {aa,ab,ac,ba,bb,bc,ca,cb,cc} (32 = 9 elementów)
Rozkład prawdopodobieństw drugiego rozszerzenia:
P(aa) = P(a) * P(a) = 0,5 * 0,5 = 0,25
P(bb) = P(b) * P(b) = 0,25 * 0,25 = 0,0625
P(cc) = P(c) * P(c) = 0,25 * 0,25 = 0,0625
P(ab) = P(ba) = P(a) * P(b) = 0,5 * 0,25 = 0,125
P(ac) = P(ca) = P(a) * P(c) = 0,5 * 0,25 = 0,125
P(bc) = P(cb) = P(b) * P(c) = 0,25 * 0,25 = 0,0625
Entropia drugiego rozszerzenia:
H(X2) = 0,25 * log24 + 4 * 0,125 * log28 + 4 * 0,0625 * log216 = 0,5 + 1,5 + 1 = 3
Czyli prawdziwa jest zaleźność H(X2) = 2H(X).

[edytuj] Przykład 2
Dane jest źródło o alfabecie X = {0,1}. Podaj drugie, trzecie i czwarte rozszerzenie tego źródła.
Rozszerzenie drugie:
X2 = {00,01,10,11} (22 = 4 elementy)
Rozszerzenie trzecie:
X3 = {000,001,010,011,100,101,110,111} (23 = 8 elementów)
Rozszerzenie czwarte:
X4 = {0000,0001,0010,0011,0100,0101,0110,0111,1000,1001,1010,1011,1100,1101,1110,1111} (24 = 16 elementów)

[edytuj] Źródło ciągów Markowa
Dobrze jest to opisane na slajdach, może potem coś tu więcej dopiszę.

[edytuj] Kodowanie źródła
Kodowanie polega na przypisaniu do każdej wiadomości źródła jednoznacznego kodu zwanego ciągiem kodowym lub słowem kodowym. Długości słów kodowych mogą być różne.
Przykład 1
Alfabet źródła to X = {a,b,c}. Niestety medium, którym przesyłany jest sygnał oferuje nam tylko sygnały 0 i 1. Aby przesłać którąś z wiadomości nalezy ją odpowiednio zakodować. Przykładowo możemy się posłużyć nastepującym kodem: a = > 00, b = > 01, c = > 11. Dzięki temu prostemu zabiegowi możemy przesłać wiadomość (w postaci kodu) za pomocą dostępnego medium.
Przykład 2
Alfabet źródła składa się z 4 wiadomości: X = {0000,0011,1100,1111}. Możemy tu zastosować następujące kodowanie: 0000 = > 00, 0011 = > 01, 1100 = > 10, 1111 = > 11. Dzięki temu zabiegowi długość przesyłanego komunikatu skróciła nam się o połowę.
Jak widać na powyższych przykładach nawet proste sposoby kodowania mogą mieć przeróżne zastosowania.
Jak już zostało wcześniej napisane, długość słów kodowych może być różna. Wprowadzono więc pojęcie średniej długości ciągu kodowego oznaczanej przez L. Dla źródła bezpamięciowego o alfabecie X = {a1,...,aK} i rozkładzie prawdopodobieństwa P(a1),...,P(aK) opisana jest wzorem:
,
gdzie li jest długością i-tego słowa kodowego.
Łatwo wykazać, że:

Oznaczając przez Ln średnią długość słowa kodowanego dla n-tego rozszerzenia źródła oraz wiedząc, że H(Xn) = nH(X) otrzymujemy:
,
co oznacza, że im większe rozszerzenie źródła, tym długość
średnia słowa jest bliższa wartości entropii tego źródła, czyli
wartości minimalnej (długości słowa kodowego).

Sprawność kodowania
określona jest wzorem:

Podaje się ją w procentach i im większa, tym lepiej.
Kod zwięzły to taki, który jest jednoznacznie dekodowany bez opóźnień oraz posiada najniższą średnią długość słowa.

[edytuj] Kodowanie Huffmana
Bardzo dobrze i z przykładem opisane jest to na polskiej Wikipedii, polecam przejrzeć link: http://pl.wikipedia.org/wiki/Kodowanie_Huffmana#Algorytm_statycznego_kodowania_Huffmana

[edytuj] Kodowanie Shannona-Fano
Algorytm kodowania Shannona-Fano jest następujący:

Podziel zbiór wiadomości elementarnych X
uporządkowany według prawdopodobieństw malejąco na dwa podzbiory, tak
aby sumy prawdopodobieństw wiadomości w obu zbiorach były możliwie
bliskie sobie.
Utwórz jednobitowe początki słów kodowych dla poszczególnych wiadomości nadając 0 ciągom kodowym w pierwszym podzbiorze natomiast 1 w drugim.
W kolejnych krokach zastosuj metodę z poprzedniego punktu dla
każdego z podzbiorów dodając kolejne bity do tworzonych słów kodowych.
Algorytm kończy się w kroku, w którym wszystkie podzbiory są jednoelementowe.

UWAGA! Nie jest ważna liczność podzbiorów, a jedynie podobna wartość sumy prawdopodobieństw wystąpienia elementów podzbiorów!

[edytuj] Przykład 1
X = a,b,c,d,e;
P(a) = 0,3;P(b) = 0,3;P(c) = 0,2;P(d) = 0,1;P(e) = 0,1

|| KROK 1 || KROK 2 || KROK 3 ||
x | P(x)|| P(x)|kod|| P(x)|kod|| P(x)|kod||
--------||------|---||-----|---||-----|---||
a | 0,3 ||\ | || 0,3 |00 || 0,3 |00 ||
--|-----|| >0,6 | 0 ||-----|---||-----|---||
b | 0,3 ||/ | || 0,3 |01 || 0,3 |01 ||
--|-----||------|---||-----|---||-----|---||
c | 0,2 ||\ | || 0,2 |10 || 0,2 |10 ||
--|-----||| | ||-----|---||-----|---||
d | 0,1 || >0,4 | 1 ||\ | || 0,1 |110||
--|-----||| | || >0,2|11 ||-----|---||
e | 0,1 ||/ | ||/ | || 0,1 |111||

[edytuj] Przykład 2
X = a,b,c,d,e,f;
P(a) = 0,3;P(b) = 0,2;P(c) = 0,15;P(d) = 0,15;P(e) = 0,15;P(f) = 0,05

||KROK1||KROK2||KROK3||
x | P(x) || kod || kod || kod ||
--|------||-----||-----||-----||
a | 0,3 || || 00 || 00 ||
--|------|| 0 ||-----||-----||
b | 0,2 || || 01 || 01 ||
--|------||-----||-----||-----||
c | 0,15 || || || 100 ||
--|------|| || 10 ||-----||
d | 0,15 || || || 101 ||
--|------|| 1 ||-----||-----||
e | 0,15 || || || 110 ||
--|------|| || 11 ||-----||
f | 0,05 || || || 111 ||

[edytuj] Przykład 3
X = a,b,c,d;
P(a) = 0,45;P(b) = 0,3;P(c) = 0,2;P(d) = 0,05

||KROK1||KROK2||KROK3||
x | P(x) || kod || kod || kod ||
--|------||-----||-----||-----||
a | 0,45 || 0 || 0 || 0 ||
--|------||-----||-----||-----||
b | 0,3 || || 10 || 10 ||
--|------|| ||-----||-----||
c | 0,2 || 1 || || 110 ||
--|------|| || 11 ||-----||
d | 0,05 || || || 111 ||


[edytuj] Dynamiczne kodowanie Huffmana
[edytuj] Inne algorytmy kodowania
Podane tutaj algorytmy (chyba) nie były omawiane na wykładzie:

Kodowanie arytmetyczne: http://pl.wikipedia.org/wiki/Kodowanie_arytmetyczne

Algorytm Lempela-Ziva: http://pl.wikipedia.org/wiki/Lempel-Ziv_77

[edytuj] Wykrywanie i korekcja błędów
Szybkość transmisji (przepustowość) kanału infomacyjnego:
, gdzie:

B[Hz] - pasmo przepuszczania,
N0 - zakłócenia szumem gaussowskim o mocy ;
P - średnia moc przenoszonego sygnału.

Powyższy wzór nazywany jest ograniczeniem Shannona.

[edytuj] Dodanie bitu parzystości
Dodanie bitu parzystości polega na dodaniu do każdego n-bitowego wiersza n+1-szy bit parzystości. Bit ten przyjmuje wartość 1 lub 0, w taki sposób, aby wiersz zawierał parzystą liczbę jedynek.
Bit parzystości pozwala na wykrycie błędnego wiersza, ale nie niesie wystarczającej informacji, aby błąd ten skorygować.

[edytuj] Przykład 1
Do podanych niżej wierszy dopisz bit parzystości:

010010001_ => 1
001001110_ => 0
0101_ => 0
1111_ => 0
1000_ => 1
0000_ => 0

[edytuj] Przykład 2
Wskaż błędnie przesłane wiersze:

11011101 <= poprawnie
11011100 <= błędnie
11101000 <= poprawnie
01001001 <= błędnie
00000000 <= poprawnie

[edytuj] Ciąg sprawdzający parzystość ramki
W celu uzyskania możliwości korekcji błędów w algorytmie dodawania
bity parzystości, należy co kilka wierszy dodać wiersz parzystości.
Ramka taka ma postać poniższej macierzy:

__ __
| b1,1 ... b1,n p1 |
| b2,1 ... b2,n p2 |
| ... ... ... ... |
| bK,1 ... bK,n pK |
| q1 ... qn qn+1|
-- --

Dzięki zastosowaniu wiersza kontrolnego możemy skorygować tylko jeden błąd na ramkę.

[edytuj] Przykład 1
Znajdź błąd w poniższej ramce:

|0 0 1 0 1 0|
|1 0 0 1 1 1|
|1 0 0 0 1 1| <=
|0 1 0 1 0 0|
|0 1 0 0 1 0|
^

[edytuj] Przykład 2
Uzupełnij macierz poprawnym ciągiem sprawdzającym parzystość ramki:

__ __
| 0 1 0 0 0 1 1 1 |
| 1 0 0 0 1 0 0 0 |
| 0 0 1 1 0 1 0 1 |
| 1 1 1 1 0 1 0 1 |
| 0 1 1 0 1 0 0 1 |
| _ _ _ _ _ _ _ _ |
-- --

Poprawne rozwiązanie:

0 1 1 0 0 1 1 0

[edytuj] Kodowanie Hamminga





Źródło: �śhttp://putwiki.informatyka.org/wiki/Teoria_sygna%C5%82%C3%B3w_dla_opornych”
Kategoria: Mikroelektronika






Widoki



Strona
dyskusja
edytuj
historia i autorzy
Language



osobiste


Logowanie i rejestracja






if (window.isMSIE55) fixalpha();

nawigacja


Strona główna
Kierunki
Przedmioty
Zadania do rozwiązania
Do zrobienia
Ostatnie zmiany
Pomoc




Szukaj



 





narzędzia


Linkujące
Zmiany w dolinkowanych
Prześlij plik
Strony specjalne
Wersja do druku Link do tej wersjiWersja PDF







Tę stronę ostatnio zmodyfikowano 14:30, 27 maj 2007.
Tę stronę obejrzano 669 razy.
Zasady ochrony prywatności
O PUTWiki
Informacje prawne




if (window.runOnloadHook) runOnloadHook();