Kodowanie Huffmana

Nasza ocena:

3
Pobrań: 49
Wyświetleń: 2583
Komentarze: 0
Notatek.pl

Pobierz ten dokument za darmo

Podgląd dokumentu
Kodowanie Huffmana - strona 1 Kodowanie Huffmana - strona 2 Kodowanie Huffmana - strona 3

Fragment notatki:


Temat I - Podstawy teorii informacji, Kodowanie Huffmana
Zagadnienia:
1.Zawartość informacyjna Shannona
2.Entropia
3.Entropia warunkowa
4.Dywergencja Kullbacka-Leiblera
5.Kod źródłowy
6.Kod symbolowy
7.Kod prefiksowy
8.Kod jednoznacznie dekodowalny
9.Nierówność Krafta
10.Kod Huffmana: algorytm, zalety, organiczenia
1. Twierdzenie Shannona Dla odniesienia zawartości informacyjnej (k) do prawdopodobieństwa, Shannon wprowadził proste równanie:  k=log 2 1/p  gdzie p jest prawdopodobieństwem uzyskania (otrzymania, zaistnienia) wiadomości. Wykorzystując powyższe równanie do przykładu z rzutem monetą obliczymy, że wiadomość polegająca na tym, że wyrzucimy "orła" albo "reszkę" ma zawartość informacyjną równą log 2 1/(1/2) czyli log 2 2 = 1 (bo 2 1 =2).
2.
Notatki wykład itp.
3. Entropia warunkowa  - wartość używana w  teorii informacji . Mierzy, ile wynosi  entropia  nieznanej  zmiennej losowej   Y , jeśli wcześniej znamy wartość innej zmiennej losowej  X . Zapisuje się ją jako   i tak jak inne entropie mierzy w  bitach .
Intuicyjnie entropia ta mierzy, o ile entropia pary zmiennych  X  i  Y  jest większa od entropii samej zmiennej  X , czyli ile dodatkowej informacji dostajemy na podstawie zmiennej  Y , jeśli znamy zmienną X .
Formalnie dla dyskretnych zmiennych losowych  X  i  Y  entropia  Y  warunkowana przez  X  może być zdefiniowana jako:
,
gdzie
.
A zatem:
.
4. Dywergencja Kullbacka-Leiblera  (zwana też  entropią względną  lub  relatywną entropią ) jest miarą stosowaną w  statystyce  i  teorii informacji   do określenia rozbieżności między dwoma rozkładami prawdopodobieństwa   p  i  q . Czasem zwana jest też  odległością Kullbacka-Leiblera , w rzeczywistości nie jest to jednak prawdziwa  metryka , gdyż nie jest  symetryczna  ani nie spełnia nierówności trójkąta .
Dywergencja Kullbacka-Leiblera dana jest wzorem:
,
dla  rozkładów dyskretnych , oraz
,
dla  rozkładów ciągłych W powyższej definicji przyjmuje się, że  p  reprezentuje dane rzeczywiste, zaś  q  teoretyczny model.
Entropia względna przyjmuje zawsze wartości nieujemne, przy czym 0 wtedy i tylko wtedy, gdy porównywane rozkłady są identyczne.
5. Definicja intuicyjna: Kod źródłowy  to zapis programu komputerowego w formie czytelnej dla człowieka umożliwiający jego modyfikację i rozwój.
6.
Przykładowo przeładowanie operatorów przykładowo w cpp?? Bądź mozliwosc działania na symbolach w matlabie??


(…)

… nie jest przedrostkiem innego słowa; taki kod jest jednoznacznie dekodowalny. Dodatkowo każdy kod prefiksowy można reprezentować w formie drzew (dla kodów dwójkowych drzewo binarne).
Dzięki tej cesze kody są jednoznacznie identyfikowane, nie ma potrzeby wstawiania dodatkowych informacji np. o tym, gdzie kończy się słowo kodowe (jest to jednoznaczne) albo jaką ma długość (długość każdego słowa kodowego jest znana z góry…
... zobacz całą notatkę



Komentarze użytkowników (0)

Zaloguj się, aby dodać komentarz