TeRq

1. Informacje i entropie
2. Właściwości entropii
3. 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 = {x₁, x₂, x_n} S - alfabet
xi (i=1,2,…,n) -litery

Każdemu zdarzeniu odpowiada prawdopodobieństwo (x_i —> P_i)
Zbiorowi zdarzeń odpowiada zbiór prawdopodobieństw. (P = {P₁, P₂, …, P_n})
Suma prawdopodobięństw = 1 (gdzie 0 <= Pi <= 1)

Przykład:
abacabca
S = {a, b, c, d, e}
P_a = 4/8
P_b = 2/8
P_c = 2/8
P_d = 0/8
P_e = 0/8
P_a + P_b + P_c = 1

Dla niezależnych zdarzen można użyć funkcji Harleja
I(x_i) = -log_k(P_i), gdzie k > 0, k != 1
I(a) = -log₅(P_a) = -log₅(4/8)

funkcje I(x_i) nazywamy iloscią autoinformacji stowarzyszonej ze zdarzeniem x_i innymi słowy jest to entropia indywidualna.

Jednostkę informacji nazywamy bitem jeśli używamy logarytmu przy podstawie 2.

H(P₁, P₂, …, P_n) = -/sigma,i=1,m/logP_ilog₂(P_i)
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 = {P₀, P₁}
P₀ +P₁
P = {P₀, 1 - P₀}
H(P₀, P₁) =
= -P₀log₂P₀-P₁log₂(P₁) =
= -P₀log₂P₀-(2-P₀)log₂()

braki

ad (2, 3)

Właściwości entropii:

1. funkcja H jest ciągła na odcink, od 0 do 1.
2. funkcja H jest smetryczna,
3. funkcja H ma dolne i górne ograniczenie,
4. dodanie do zbioru zdarzeń niemożliwego zdarzenie nie zmienia entropii.

Załóżmy ze istnieje zbiór S = {x₁, x₂, …, x_m},
temu zbiorowi odpowiada zbior prawdopodobienstw P = {P₁, P₂, …, P_n}
Litera x_i odpowiada ciag symboli lub slowa kodu C_i nalezace do zbioru slow kodu.
C = {C₁, C₂, …, C_n}

Kodem nazywamy odwzorowanie S na C, C_i = S_i

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/ P_il_i

P_i — prawdopodobieństwo pewnego zdarzenia
l_i — 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.

Kody
C₁ = {0, 1, 01}
C₂ = {0, 11, 01}
C₃ = {00, 01, 10}
C₄ = {00, 01, 1}

aacabcabc

1. 000101010101 (nie dekodowalny)
2. 00010110101101 (nie dekodowalny)
3. 000010000110000110 (dekodowalny)
4. 000010001100011 (dekodowalny)

P_a = 4/9; P_b = 2/9; P_c = 3/9;
L_śr= P_al_a + P_bl_b + P_cl_c
L_śr = 4/9*2 + 2/9*2 + 3/9*1 =<2

Kodowanie jest stosowane do kompresji danych. Współczynnik kompresji danych:

K= (L_we - L_wy)/L_we