TIiK vol. 2

1) Źródło generuje dziewięć wiadomości

x

1,

x

2,

... , x

9

. Zakoduj kodem binarnym

natychmiastowo dekodowalnym to źródło w taki sposób, żeby najczęściej generowane
wiadomości

x

1,

x

2

były związane z najkrótszymi możliwymi słowami kodowymi, a

pozostałe wiadomości ze słowami o jednakowej, najmniejszej z możliwych długości słowa
kodowego.

x

1,

x

2

muszą być zakodowane na dwóch bitach (jakbyśmy zrobili na jednym, to wtedy kod

byłby niejednoznaczny).

Wtedy, pozostała ilość (korzystając z nierówności Krafta):

∑

i

=1

n

2

−l

i

≤1 ⇔ 2⋅

1

2

2

7⋅

1

2

k

≤1 ⇔

1

2

k

≤

1

14

⇔ k ≥log

2

7

1⇔ k

min

=4

Propozycja kodu:

x

1

00

x

2

01

x

3

1000

x

4

1001

x

5

1010

x

6

1011

x

7

1100

x

8

1101

x

9

1110

2) Zbiór 6 wiadomości

x

1,

... , x

i

,... , x

6

zakodowano według sześciu kodów A - F

danych w tabeli. Określ, które kody są jednoznacznie dekodowalne, a które natychmiastowo
dekodowalne. Policz średnią długość dla każdego kodu jednoznacznie dekodowalnego.

Wiadomość

p

 x

i



Kod A Kod B

Kod C

Kod D

Kod E

Kod F

x

1

1/2

000

0

0

0

0

1

x

2

1/4

001

01

10

10

10

100

x

3

1/16

010

011

110

110

1100

101

x

4

1/16

011

0111

1110

1110

1011

110

x

5

1/16

100

01111

11110

1011

1110

111

x

6

1/16

101

011111 111110

1101

1111

011

Aby był jednoznaczny, to jedno słowo nie może być początkiem innego (dlatego np. ruch i

ruchać jest niejednoznaczne, ba, nawet dwuznaczne :P ) -> tak dokładnie jest to warunek
wystarczający, ale nie jest on konieczny-> przykładem są kody przecinkowe. Kody D, E i F
odpadają w przedbiegach, ponieważ można otrzymać sekwencje niejednoznaczne na wyjściu.

Kod A -> jednoznaczny, natychmiastowo dekodowalny (wiemy, że każde słowo ma długość

trzech bitów).

Krzychoo, TIiK



L

A

=

∑

i

=1

6

p

i

⋅l

i

=3

(chyba oczywiste)

Kod B -> jednoznaczny, nie jest jednak natychmiastowy (zakończenie słowa oznacza

przyjście '0' do odbiornika, a '0' to początek kolejnego słowa)



L

B

=2

1
8

Kod C -> jednoznaczny, natychmiastowy (zero jest końcem każdego słowa kodowego, nie

musimy więc czekać na następne słowo)



L

C

=2

1
8

3) Źródło generuje równoprawdopodobne słowa kodowe kodu zwięzłego

trójsymbolowego o długościach równych cztery symbole. Policz, ile informacji o źródle
uzyskano po odebraniu 8 słów.

D = 3
L = 4

Równość prawdopodobieństw, więc kod jest optymalny. Zatem możemy zapisać:

L

=

H

X 

log

2

D

⇔ H  X =L⋅log

2

D

[bitów /słowo]

(entropia dla pojedynczego słowa). Słów

przesłano n =8, zatem:

I

X

n

=n⋅L⋅log

2

D

=32 log

2

3

=50,72[bit ]

4) Czy można, w alfabecie liczącym trzy elementy skonstruować kod natychmiastowo

dekodowalny, jeśli długości słów kodowych miałyby wynosić:

1,2,2,2,2,2,3,3,3,3?

A jeśli długości słów kodowych wynoszą:

1,2,2,2,2,2,3,3,3,?

Jak wiele takich kodów można skonstruować?

Musi być spełniona nierówność Krafta. Dla pierwszego przypadku nie jest:

∑

i

=1

n

3

−l

i

=

1
3

5⋅

1

3

2

4⋅

1

3

3

=

28
27

1

Dla drugiego zaś jest.
Pomyślmy wobec tego, ile takich kodów można skonstruować.
Najpierw tworzymy jedno słowo o długości jeden:

K

1

=W

3

1

=3

Teraz utworzymy słowa o długości dwa, z uwzględnieniem, że kod musi być jednoznacznie

dekodowalny:

K

2

=W

3

1

−1⋅W

3

1

=6

No i słowa o długości trzy, biorąc pod uwagę, ile już słów zużyliśmy do poprzednich

kodowań:

K

3

=W

3

2

−5−1⋅W

3

1

⋅W

3

1

=3

Teraz, spośród tych symboli, musimy wybrać jeden o długości jeden, pięć o długości dwa i

Krzychoo, TIiK

trzy o długości trzy (tyle będzie kombinacji słów kodowych).

K

S

=C

3

1

⋅C

6

5

⋅C

3

3

=



3
1



6
5



3
3



=18

Z tym, że w zadaniu należy chyba wziąć pod uwagę to, że A=01 i B=11 to inny kod niż A=11

i B=01, zatem ilość znacznie wzrośnie:

K

K

=[C

3

1

C

9

1

]⋅[P

5

C

8

5

C

6

5

]⋅[ P

3

C

3

3

C

3

3

]=P

9

⋅K

S

Ot, zwyczajny dobór "przestrzeni życiowej" dla poszczególnych słów...

5) Ile najwięcej słów kodowych może liczyć binarny natychmiastowo dekodowalny

kod, którego najdłuższe słowo ma długość 7?

Najwięcej możliwości (słów kodowych) będziemy mieli, jeśli każde ze słów będzie miało 7

bitów długości. Oznaczać to będzie przy okazji, że kod będzie natychmiastowo dekodowalny.

No to walnijmy jeszcze nierówność Krafta:

N

2

7

≤1⇔ N

max

=2

7

=128

6) Załóżmy, że alfabet kodu liczy D elementów oraz że sekwencja n liczb całkowitych

l

i

:1

≤l

1

≤l

2

...

≤l

n

spełnia nierówność Krafta. Na ile sposobów można wybrać słowa

kodowe

w

1

... w

n

, dla których długości

l

w

i

=l

i

, tak żeby zbiór

{ w

1

... w

n

}

był kodem

natychmiastowo dekodowalnym?

Zapiszmy więc dla pierwszego słowa:

K

1

=W

D

l

1

Dla drugiego słowa:

K

2

= K

1

−1⋅W

D

l

2

−l

1

=W

D

l

1

−1⋅W

D

l

2

−l

1

=W

D

l

2

−W

D

l

2

−l

1

Dla trzeciego:

K

3

=K

2

−1⋅W

D

l

3

−l

2

=W

D

l

2

−W

D

l

2

−l

1

−1⋅W

D

l

3

−l

2

=W

D

l

3

−W

D

l

3

−l

2

−W

D

l

3

−l

1

Itd., dochodząc do n-tego:

K

n

=W

D

l

n

−W

D

l

n

−l

n

−1

−...−W

D

l

n

−l

1

Sprawdźmy jeszcze, czy przypadkiem gdzieś po drodze nie wyczerpią nam się możliwości

(wtedy dalsze kodowanie byłoby niemożliwe). Zajmijmy się najdalej położonym, czyli też
najbardziej "wyczerpanym",

K

n

:

K

n

=W

D

l

n

−W

D

l

n

−l

n

−1

−...−W

D

l

n

−l

1

=D

l

n

− D

l

n

−l

n

−1

−...− D

l

n

−l

1

=D

l

n

⋅[1− D

−l

1

... D

−l

n

−1

]=D

l

n

⋅1−

∑

i

=1

n

−1

D

−l

i





>0

Dlaczego niby większe od zera? Bo czynnik w nawiasie wynika z nierówności Krafta.

Liczba sposobów zaś:

K

=K

1

⋅K

2

⋅...⋅K

n

7) Udowodnij, że dla każdego zwięzłego źródła o rozkładzie prawdopodobieństwa

 p

i



istnieje następująca zależność pomiędzy prawdopodobieństwami wystąpienia

wiadomości a długościami reprezentujących je kodów:

L=min∧ p

j

 p

k

⇒ l

j

≤l

k

(1)

Możemy zapisać, że:

L=

∑

i

=1

N

p

i

⋅l

i

=S p

k

l

k

 p

j

l

j

Krzychoo, TIiK

Teraz zakładamy (metoda nie wprost):

L=min∧l

j

l

k

∧ p

j

 p

k

(2)

Oznacza to, że dla każdego ciągu kodowego wartość minimalna będzie dla powyższych

założeń.

Wystarczy więc choćby jeden kontrprzykład, aby obalić hipotezę (2), dzięki czemu

udowodnimy prawdziwość twierdzenia (1).

No to jedziemy:



L

2

=S  p

k

l

k2

 p

j

l

j2

Jako ciąg hipotetycznie większy weźmy ten z twierdzenia (1):



L

2

=S  p

k

l

k2

 p

j

l

j2

≤ 

L

1

=S  p

k

l

k1

 p

j

l

j1

Przy założeniach:

l

k1

≥l

j1

∧l

k2

l

j2

∧ p

k

 p

j

Wobec tego mamy:

p

k

l

k2

 p

j

l

j2

≤ p

k

l

k1

 p

j

l

j1

⇔l

k2

−l

k1

≤

p

j

p

k

l

j1

−l

j2



Przyjmijmy, że

l

k2

=l

k1

⇒ l

j1

l

j2



Tak więc mamy:

l

k2

−l

k1



=0

≤

p

j

p

k

l

j1

−l

j2





< 0

A to jest bzdura!
Hipoteza została obalona, wobec czego twierdzenie (1) jest prawdziwe.

8) Źródło generuje trzy wiadomości z prawdopodobieństwem

p

1

≥ p

2

≥ p

3

. Pokaż,

że średnia długość binarnego kodu Huffmana C dla tego źródła wynosi:

L

C =2− p

1

Ile będzie wynosiła długość takiego kodu dla źródła generującego cztery wiadomości

z prawdopodobieństwami:

p

1

≥ p

2

≥ p

3

≥ p

4

?

a)

Wiadomości S1

S2

Długość

m1

p1

p1

1 znak

m2

p2

p2 + p3

2 znaki

m3

p3

Wobec tego:

L

C = p

1

⋅1 p

2

 p

3

⋅2= p

1

 p

2

 p

3



1

 p

2

 p

3



1

− p

1

=2− p

1

b)

Wiadomości

S1

S2

S3

Długość

m1

p1

p1

p1

1

m2

p2

p2

p2 + p3 + p4

2

m3

p3

p3 + p4

3

m4

p4

3

L

C =3−2p

1

− p

2

Inny przypadek:

Krzychoo, TIiK

Wiadomości

S1

S2

S3

Długość

m1

p1

p3 + p4

p1 + p2

2

m2

p2

p1

p3 + p4

2

m3

p3

p2

2

m4

p4

2

L

C =2

itp.

9) Algorytm Huffmana polega między innymi na tworzeniu ciągu zredukowanych źródeł

wiadomości w taki sposób, że za każdym razem (tzn. na etapie redukcji numer i) musimy
obliczać prawdopodobieństwo

p



i

pewnej liczby najmniej prawdopodobnych wiadomości.

Pokaż, że średnią długość binarnego kodu Huffmana C można obliczyć jako:

L

C =1

∑

i

p



i

Rozważmy etap i oraz i +1:

L

C

i

=

∑

j

=1

M

p

j

⋅l

j

=

∑

j

=1

M

−2

p

j

⋅l

j

 p

M

−1

⋅l

M

−1

 p

M

⋅l

M

=

∑

j

=1

M

−2

p

j

⋅l

j

 p

M

−1

 p

M





p



i

⋅l

M

l

M

i l

M

−1

są sobie równe.

L

C

i

1

=

∑

j

=1

M

−1

p

j

⋅l

'

j

=

∑

j

=1

M

−2

p

j

⋅l

j

 p



i

⋅l

M

−1

'

L

C

i

− LC

i

1

= p



i

⋅l

M

−l

M

−1

'





1

= p



i 

Teraz, przechodząc do finału:

L

C = LC

1

=LC

1

[L C

2

−LC

2

]...[ L C

N

−L C

N

]

L

C =[ LC

1

−LC

2

][ LC

2

−L C

3

]...L C

N





1

=1

∑

i

p



i

10) Na podstawie analizy kodowania Huffmana dla bezpamięciowego źródła

generującego

N

≥2

wiadomości, pokaż że tworzone w alfabecie binarnym słowa kodowe

o długościach

l

i

spełniają poniższą nierówność:

∑

i

=1

N

l

i

≤

1
2

⋅ N

2

 N −2

Skorzystajmy z indukcji matematycznej:
1)
N = 2
L = 1 + 1 =2
P = 2
L = P (prawda)
2)
Założenie: dla N =n twierdzenie prawdziwe.
Czy N = n +1 twierdzenie jest prawdziwe?

L =

∑

i

=1

n

1

l

i

=

∑

i

=1

n

l

i

2=

n

2

P =

1
2

⋅n1

2

n1−2=

1
2

⋅n

2

n−2

1
2

⋅ 2 n2

Krzychoo, TIiK



n

2≤

?

1
2

n

2

n−2[n1]

Wystarczy tylko wykazać, że n + 1jest większe od dwóch, co dla N określonych w zadaniu

zawsze jest prawdziwe.

Zatem twierdzenie udowodnione.

11) Znajdź entropię źródła X, które ma nieskończenie wiele symboli o

prawdopodobieństwach

p

i

=2

−i

(i = 1,2,3 ...). Znajdź optymalny binarny kod

natychmiastowo dekodowalny i oblicz jego średnią długość.

H

 X =

∑

i

=1

∞

i

2

i

=

x

 x−1

2

| x

=2

=2

Wiemy, że dla kodu optymalnego zachodzi równość:

L=

H

 X 

log

2

D

⇔ L=H  X ⇔

∑

i

=1

∞

p

i

⋅l

i



L

=

∑

i

=1

∞

p

i

⋅i





H

 X 

⇔∀ n :l

n

=n

W zasadzie tutaj mamy znalezioną średnią długość (równa entropii wszakże). Przy okazji też
wiemy, że n-ty symbol powinien być zakodowany na n bitach. A teraz pora na jakąś propozycję:

m1

0

m2

10

m3

110

m4

1110

m5

11110

m6

111110

m7

1111110

m8

11111110

m9

111111110

m10

1111111110

m11

11111111110

...

...

Krzychoo, TIiK