- Informacje i entropie
- Właściwości entropii
- Podstawy kodowania
ad (1)
informacja: dane którymi posługują się ludzie oraz za pomocą których sprawnie działają urządzenia nazywa się informacjami. Informacja występuje w dwóch postaciach. W postaci syntaktycznej oraz w postaci semantycznej. Postać syntaktyczna jest to forma informacji, a semantyczna jest to treść informacji.
Z punktu widzenia inżyniera najważniejszym aspektem infomacji jest aspekt syntaktyczny kiedy analizowana jest postać, co umożliwia zdobycie wiadomosci jak ją zakodować i rozkodować.
informatyka: dziedzina zajmująca się przetwarzaniem informacji.
Przjmijmy iż istnieje zbiór zdarzen:
S = {x1, x2, xn} S - alfabet
xi (i=1,2,…,n) -litery
Każdemu zdarzeniu odpowiada prawdopodobieństwo (xi —> Pi)
Zbiorowi zdarzeń odpowiada zbiór prawdopodobieństw. (P = {P1, P2, …, Pn})
Suma prawdopodobięństw = 1 (gdzie 0 <= Pi <= 1)
Przykład:
abacabca
S = {a, b, c, d, e}
Pa = 4/8
Pb = 2/8
Pc = 2/8
Pd = 0/8
Pe = 0/8
Pa + Pb + Pc = 1
Dla niezależnych zdarzen można użyć funkcji Harleja
I(xi) = -logk(Pi), gdzie k > 0, k != 1
I(a) = -log5(Pa) = -log5(4/8)
funkcje I(xi) nazywamy iloscią autoinformacji stowarzyszonej ze zdarzeniem xi innymi słowy jest to entropia indywidualna.
Jednostkę informacji nazywamy bitem jeśli używamy logarytmu przy podstawie 2.
H(P1, P2, …, Pn) = -/sigma,i=1,m/logPilog2(Pi)
Nazywa się entropią wszystkich zdażeń, można ją interpretować jako najmniejszą średnią liczbę pytań na które możemy odpowiedzieć tak lub nie. W kontekście kodowania entropie reprezentuje ograniczenie dolen na średnią liczbę butów przypadających na jedną wartość.
Temu zbiorowi zdarzeń odpowiada zbiór prawdopodobieństw:
S = {0, 1}
P = {P0, P1}
P0 +P1
P = {P0, 1 - P0}
H(P0, P1) =
= -P0log2P0-P1log2(P1) =
= -P0log2P0-(2-P0)log2()
braki
ad (2, 3)
Właściwości entropii:
- funkcja H jest ciągła na odcink, od 0 do 1.
- funkcja H jest smetryczna,
- funkcja H ma dolne i górne ograniczenie,
- dodanie do zbioru zdarzeń niemożliwego zdarzenie nie zmienia entropii.
Załóżmy ze istnieje zbiór S = {x1, x2, …, xm},
temu zbiorowi odpowiada zbior prawdopodobienstw P = {P1, P2, …, Pn}
Litera xi odpowiada ciag symboli lub slowa kodu Ci nalezace do zbioru slow kodu.
C = {C1, C2, …, Cn}
Kodem nazywamy odwzorowanie S na C, Ci = Si
Kod nazywamy binarnym jeśli słowa kodu składają się z zer i jedynek.
Przy kodowaniu dążymy do optymalizacji pamięci (do optymalizacji kosztów). Oczekiwane koszty oblicza się
Lśr = /sigma,l=1,m/ Pili
Pi — prawdopodobieństwo pewnego zdarzenia
li — długość słowa kodu
Im większe prawdopodobieństwo tym mniejsza długość kodu.
Przy kodowaniu
braki
iż kod ma być jednoznacznie dekodowalny. Kod nazywa się jednoznacznie dekodowalnym jeśli istnieje tylko jeden sposób podziału zakodowanego ciągu na oddzielne słowa. Kod jest optymalny jeśli lśr jest najmniejszą spośród wszystkich kodów.
Kod1 | Kod2 | Kod3 | Kod4 | |
a | 0 | 0 | 00 | 00 |
b | 1 | 11 | 01 | 01 |
c | 01 | 01 | 10 | 1 |
Kody
C1 = {0, 1, 01}
C2 = {0, 11, 01}
C3 = {00, 01, 10}
C4 = {00, 01, 1}
aacabcabc
- 000101010101 (nie dekodowalny)
- 00010110101101 (nie dekodowalny)
- 000010000110000110 (dekodowalny)
- 000010001100011 (dekodowalny)
Pa = 4/9; Pb = 2/9; Pc = 3/9;
Lśr= Pala + Pblb + Pclc
Lśr = 4/9*2 + 2/9*2 + 3/9*1 =<2
Kodowanie jest stosowane do kompresji danych. Współczynnik kompresji danych:
K= (Lwe - Lwy)/Lwe