Wykład I
  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 = {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:

  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 = {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

  1. 000101010101 (nie dekodowalny)
  2. 00010110101101 (nie dekodowalny)
  3. 000010000110000110 (dekodowalny)
  4. 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

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License