1 of 32

Teorie informací

Maskot

říjen 221

2 of 32

25 %

25 %

25 %

25 %

Počasí v Obůrce

3 of 32

Binární abeceda

  • Hledáme binární abecedu. Jakým způsobem svému kamarádovi sdělíte, jaké je právě počasí v Obůrce tak, abyste použili co nejméně znaků?

Binární abeceda

  • Abeceda, která obsahuje právě dva znaky.
  • Je to například morseovka (·−) nebo binární soustava (01).

Počasí v Obůrce

4 of 32

0 0

0 1

1 0

1 1

Počasí v Obůrce

5 of 32

0 0

0 1

1 0

1 1

bit

Počasí v Obůrce

6 of 32

  • bit (z anglického binary digit) je základní a současně nejmenší jednotkou dat

7 of 32

100 %

0 %

0 %

0 %

Počasí v Češkovicích

8 of 32

Nemusím sdělovat nic.

9 of 32

25 %

12,5 %

50 %

12,5 %

​

​

​

​

​

​

​

​

Počasí v Těchově

10 of 32

Počasí v Těchově

  • Hledáme binární abecedu. Jakým způsobem svému kamarádovi sdělíte, jaké je právě počasí v Těchově tak, abyste použili co nejméně znaků?

11 of 32

10

101

0

111

Počasí v Těchově

12 of 32

Lze dokázat, že efektivnější kódování již nelze nalézt.

13 of 32

V jakém městě máme o počasí více informací?

14 of 32

Kolik zjišťovacích otázek musím položit, abych s jistotou věděla, jaké je ve městě počasí?

15 of 32

Počasí v Obůrce

Je slunečno nebo prší?

Je aktuální počasí mezi možnostmi {slunečno, prší}?

Ano.

Ne.

Je slunečno, nebo prší?

Je polojasno, nebo zataženo?

16 of 32

Počasí v Těchově

Je polojasno?

Ano.

Ne, je slunečno?

Ne. Prší, nebo je zataženo?

17 of 32

O počasí v Těchově mám míň informací, jelikož lze lépe predikovat.

18 of 32

Abeceda

  • Mějme danou binární abecedu. Rozluštěte následující slova.

​

  • 11011110

​

  • 0110101000

​

  • 01010100110
  • A 11
  • B 010
  • C 0111
  • D 00
  • E 10
  • F 0110

Dekódování slov

19 of 32

Kódování slov

  • Hledáme binární abecedu. Jakým způsobem svému kamarádovi sdělíte slovo MISSISSIPPI tak, abyste použili co nejméně znaků?

20 of 32

Řešení

21 of 32

22 of 32

23 of 32

24 of 32

Formalizace

25 of 32

Funkce nepravděpodobnosti

  •  
  • Délku znaku můžeme přeformulovat jako „jak moc hluboko ve stromu jsme“?

 

26 of 32

Zavedení nepravděpodobnosti

  1. Budou-li mít všechny stavy stejnou pravděpodobnost, funkce H bude maximální.
  2. Výsledek funkce H(p1, p2, … pn) nezávisí na pořadí p.
  3. Vždy platí H(p1, p2, … pn) ≥ 0, přičemž rovnost nastává pokud pi = 1 pro nějaké i.
  4. H(p1, . . . , pn, 0) = H(p1, . . . , pn).
  5. H(1/n, . . . , 1/n) ≤ H(1/(n + 1), . . . , 1/(n + 1)).
  6. H je spojitá funkce.
  7. H(1/mn, . . . , 1/mn) = H(1/m, . . . , 1/m) + H(1/n, . . . , 1/n).

​

​

​

27 of 32

Entropie H

  •  

28 of 32

Entropie vrhu mincí

  •  

29 of 32

30 of 32

Důsledky

  • Tvrzení. Nechť H(x) je entropie a L průměrná délka kódových slov popisující určitou veličinu. Pak vždy platí, že L ≥ H(x).

​

  • Definice. Efektivitu kódování zaveďme jakožto podíl L/H(x).
  • Pak čím více se efektivita blíží 1, tím efektivnější kódování je.

​

​

31 of 32

  • menší entropie ≈ větší komprese
  • větší entropie ≈ menší komprese

32 of 32

Použité prameny a další literatura

​

​

  • Předmět PřF:M8170 Teorie kódování

​