Teoria informatyki - kodowanie

Komunikat - porcja informacji przekazywana w dowolny sposób (słownie , pisemnie, za pomocą impulsów elektrycznych itp.)

Każda wiadomość jest komunikatem, chociaż może być odbierana w różny sposób

Im więcej informacji (K) zawiera komunikat tym mniejsze jest prawdopodobieństwo jego wystapienia

K = log₂

K - ilość informacji przypadająca na wiadomość elementarną (komunikat)

p - prawdopodobieństwo wystąpienia komunikatu (zawiera się w przedziale od 0 do 1)

p=1/2 p=1/2

p=1/4 p=1/4

p=1/4

p=1/4

p=1/8

p=1/8 p=1/8

p=1/8

p=1/16 p=1/16

p(a/b/c/d/e/f/g) = 1

p(a/c/d/g) = p(b/e/f) = 1/2

p(a/c) = p(d) = p(e) = p(f) = 1/8

p(a) = p(c)= 1/16

Średnia ważona ilości informacji dla całego źródła to:

H - entropia źródła

pi- prawdopodobieństwo wystąpienia komunikatu

H = 1/16*log ₂16+1/4*log₂ 4 +1/16*log₂16+1/8*log₂8+1/8*log₂8+1/4*log₂ 4+1/8*log₂8=

=2*1/16*4+2*1/4*2+3*1/8*3= 1/8+1+9/8=2+1/8+4/8 = 2

K = log ₂
K-ilość informacji

Dla p = 1 komunikat pewny

Ilość informacji =0

Każdy komunikat ma długość - ilość znaków np. /abba/ = 4

Średnia ważona długości słowa kodowego dla całego źródła:

L =
Ni-długość słowa kodowanego

Gdy nie znamy długości słowa kodowanego to liczymy go ze wzoru:

Ni = -log₂ pi

Różnica

R= L-H R -Redundancja -im mniejsza redundancja tym łatwiej popełnić błąd

Przy wydłuzonej redundancji łatwiej znaleźć błąd - są na to algorytmy dowodowe

0	0000	0
1	0001	1
2	0010	1
3	0011	0
4	0100	1
5	1000	1
6	1001	0
7	1010	0
8	1011	1
9	1111	0

pi = 1/10

H =
log₂ 10= log₂10 - entropia

Algorytm Huffmana

L=
4 = 4 -średnia ważona długości słowa

R = L - H pamiętamy że im większa redundancja tym mniejsze prawdopodobieństwo błędu

R= 4 - log₂10

W algorytmie Huffmana zwiększamy redundancję najczęściej przez zwiększenie długości słowa - Ni co wpływa na wzrost L a zatem i wzrost redundancji

Bit parzystości:

• 
  Parzysta liczba jedynek - dodajemy 0

• 
  Nieparzysta liczba jedynek - dodajemy 1

Algorytm Huffamna jest równoliczny

Zad1.

Źródło nadaje 3 komunikaty z jednakowym prawdopodobieństwem.

Oblicz H

H =
log₂
=
log₂ 3 = log₂ 3

Sposób kodowania na diagramie:

• Na lewo - 0

• Na prawo - 1

Zad 2

Na podstawie podanego diagramu znaleźć słowa kodowe oraz określić prawdopodobieństwo poszczególnych komunikatów

p=1/2 p=1/2

p=1/4

a: 0

b:10

c:110 p=1/8

d:1110

e:11110

f:11111

1/16

H =
log₂
1/32 1/32

H= ½ * log₂2 + ¼ *log₂4 + 1/8 *log₂8 + 1/16 *log₂16 + 2*1/32 *log₂32 =

= ½ * 1+ 1/4 * 2+ 1/8 *3 + 1/16 * 4 +2 * 1/32 *5=

=8/16 +6/16 + 4/16 + 5/16=31/16

L=
N_i = Ni-długość słowa(oznaczana też przez Li)

=1/2 * 1 + 1/4*2 + 1/8*3 + 1/16*4 + 2*1/32*5

= 8/16 + 8/16 + 6/16 + 4/16 + 5/16 =31/16

Prawo Shanona

L ≥ H

Nie może się zdarzyć że L<H

Zadanie

Źródło nadaje 5 komunikatów. Narysuj diagram

A 00

B 01

C 100

D 101

E 11

p=1/2 1 p=1/2

0

0 1 0 1

p=1/4 p=1/4

p=1/4 1

p=1/4 0

p=1/8

p=1/8

H =
log₂
= 3 * ¼ * log₂4 + 2 * 1/8 * log ₂8 =

=3 * ¼ * 2 + 2 * 1/8 * 3 = 6/4 +3/4 = 9/4

L=
Ni = 3 *1/4 *2 + 2 * 1/8 *3= 6/4 + ¾ =9/4

R = L - H = 0

Zadanie

Źródło nadaje 9 komunikatów z następującym prawdopodobieństwem:

P(a)= P(f)= P(h)= 1/16

P(b)= P(k)=1/32

P(c)= P(d)=1/8

P(e)= P(g)=1/4

Narysuj przykładowy diagram kodowania

p=1/2 p=1/2

p=1/4 p=1/4

p=1/4

p=1/4

p=1/8

1/8 1/8 p=1/8

a :0110 1/16

b :01110



1/16

c: 111

1/16

d: 010 1/16

e: 00

f;1101 1/32 1/32

g:10

h:1100

k:01111

Warunek kodu Fano:

Żadno słowo nie jest identyczne z początkiem słowa następnego

Kod Fano jest kodem różnolicznym

a,b,c,d,e,f,g

a,c,d,g

b, e,f

a,c,d

g

b

e, f

e

f

a,c

d

a

c

a,b,c,d,e,f

C, D

d,e,f

c

f

e

e,f,

c,d,e, f

b

b,c,d e,f

a

a,b,c,d,e,f

d

C, D, E

A B

E

B

A

C

D

b,k

a

c

h,f

a,b,k

d

e

h, f,c

g

g,h,f ,c

a,e,d,b,k

a,b,c,d,e,f,g,h,k

a,d,b,k

h,

f

b

k

---