Osnova přednášky. Informace v počítači. Interpretace dat. Údaje, data. Úvod do teorie informace. Výpočetní technika I. Ochrana dat

.

2/44

Osnova přednášky .

Úvod do teorie informace

Informace v počítači

.

— základní pojmy — měření množství informace ve zprávě — přenos a kódování dat

Výpočetní technika I

Ochrana dat

Ing. Pavel Haluza ústav informatiky PEF MENDELU v Brně

— parita — kontrolní součet — samoopravný kód

[email protected]

.


.

Přednáška 4: Informace v počítači




Základní pojmy

Základní pojmy

3/44

Údaje, data

Data v počítači – jedničky a nuly Pro člověka musí být zobrazeny Zobrazení stejné posloupnosti jedniček a nul může být provedeno nekonečně mnoha způsoby Interpretace zobrazení – přisouzení významu zobrazeným údajům Datový typ – definován oborem povolených hodnot a kolekcí povolených operací Implementace – přisouzení datového typu posloupnosti binárních hodnot v paměti počítače Modeluje objektivní realitu – hodnoty jsou zobrazeny pro vstup i výstup

— hodnota libovolné reálné veličiny — příklad: „167 cm“

Data — zprávy nebo výroky, které mohou (ale nemusí) snižovat neznalost daného jevu (neurčitost, entropii) — jakékoli vyjádření (reprezentace) skutečnosti, schopné přenosu, uchování, interpretace či zpracování — sama o sobě jsou nehmotná, i když pro jejich uložení potřebujeme hmotné médium — příklad: „Průměrná výška ženy je 167 cm.“



4/44

Interpretace dat

Údaje

.


.



.



Základní pojmy

Základní pojmy

5/44

Informace, znalosti

6/44

Jak informaci chápat?

Informace

Kvalitativní hledisko

— snižují neurčitost a vyvolávají změnu stavu či chování příjemce — změna stavu po přijetí zprávy je tím větší, čím větším je informace pro příjemce překvapením — množství informace ve zprávě je relativní vzhledem k určitému příjemci a určité situaci — každou informaci lze považovat za součást dat, ale každá data nemusí obsahovat informaci

— získávání, uchovávání, zpracování a přenos informací — zkoumá informatika

Kvantitativní hledisko — — — —

Znalosti

množství informace ve zprávě a jeho měření kódování a dekódování zpráv přenos zpráv zkoumá teorie informace

— ucelený komplex informací o nějaké objektivní realitě — výsledek poznávacího procesu, předpoklad uvědomělé činnosti, umožňují porozumět skutečnosti — příklad: „Průměrná žena je docela malá.“

.


.





Základní pojmy

Základní pojmy

7/44

Pojem informace

8/44

Informační systém

Mnoho různých definic podle toho, co autoři definice považovali za nejdůležitější

Systém – komplex prvků a vazeb ve vzájemné interakci (definice v teorii systémů)

Informace je obsah jakéhokoli oznámení, údaje o čemkoli, s určením pro přenos v prostoru a čase. V nejširším slova smyslu je to obsah vztahů mezi materiálními objekty, projevující se změnami těchto objektů

Informační systém – dynamický systém, jehož vazby tvoří informace a prvky systému jsou místa transformace informací

Informace je obsah zprávy, sdělení, objasnění, vysvětlení, poučení

Dílčí úlohy IS – sběr informací, přenos, redukce, archivace, zpracování, distribuce

Úkol IS – poskytovat potřebné informace v požadovaném rozsahu, lhůtách, podrobnostech i formě

Informace jsou údaje, čísla, znaky, povely, instrukce, příkazy, zprávy apod. Za informace považujeme také podněty a vjemy přijímané a vysílané živými organismy

.




.



.



Měření množství informace ve zprávě



9/44


Americký fyzik Claude Shannon (1916–2001)

Jak kvantifikovat rozšíření okruhu znalostí příjemce? Pravděpodobnost zprávy

— položení základů teorie informace — stanovení možností měření informačního množství

— spojeno s individuálními vlastnostmi příjemce (Shannon)

Informace je míra množství neurčitosti nebo nejistoty o nějakém náhodném ději odstraněná realizací tohoto děje

Jev

Množství informace ve zprávě tedy měříme podle toho, o kolik se sníží neurčitost nebo nejistota, když zprávu přijmeme a pochopíme

Realizace jevu

— náhodný proces s n možnými realizacemi — tah sportky, účast na přednášce, semafor na křižovatce aj. — jeden projev, získání výsledku — vytažení 6 čísel, konkrétní počet osob na přednášce, svítící zelená na semaforu aj.

Pojem informační entropie – míra neurčitosti, která se po přijetí zprávy odstraňuje a vyjadřuje tak množství informace obsažené ve zprávě .


.








Požadované vlastnosti funkce pro výpočet množství informace

Jediná funkce, která vyhovuje uvedeným podmínkám, je logaritmus I(x) = log n Předpokládáme, že pravděpodobnost každé realizace je stejná, tedy 1 p(x) = ,

— množství informace je rovno nule

Současně probíhající nezávislé jevy X a Y — p(x, y) = p(x) · p(y)

n

kde n je počet realizací

— množství informace je dáno součtem množství informace u jednotlivých jevů: f(x, y) = f(x) + f(y)

Úpravou dostáváme

Porovnání pro dva odlišné jevy X a Y

n=

— jev X má n realizací, jev Y má m realizací — je-li m > n, pak chceme i f(m) > f(n) Výpočetní technika I


12/44

Výpočet vlastní informace 11/44

Jev X má n realizací, množství informace je tedy funkcí n Jediná realizace jevu X — pokud n = 1, jedná se o jev jistý

.

10/44

.


1 p(x) Přednáška 4: Informace v počítači

.





13/44

Výpočet vlastní informace Vlastní informace výsledku realizace x

Výpočet vlastní informace v bitech = výpočet prostoru pro zadaný počet hodnot

I(x) = − log p(x)

— příklad: barevná hloubka rastrového obrazu

Základ logaritmu – principiálně není podstatný, ale používají se logaritmy o základu 2 (výsledek v bitech)

Velikost prostoru v počítači pro určitý údaj – hodnocení úspornosti

I(x) = − log2 p(x)

— příklad: uložení 6 tažených čísel Sportky – znaky, čísla malá, velká, souhrn, kódování

Vlastní informace se nazývá též částečná informace Počítání s logaritmy loga x =

14/44

Aplikace vlastní informace

Příklad: věta s nezávislými současně vzniklými realizacemi (Auto 1B1 8877 černé barvy přijelo na křižovatku Horní–Jasanová v 19:10 hodin.)

logb x = loga b · logb x logb a

log2 x = log2 10 · log x = 3,322 · log x .


.







15/44

Řešený příklad

16/44

Entropie Jak spočítat informační množství celého jevu? Pomůžeme si shrnutím všech vlastních informací jednotlivých realizací Předpokládejme, že jev X má n realizací x1 , x2 , …, xn s pravděpodobnostmi p(x1 ), p(x2 ), …, p(xn ) Entropie H(X) je dána určitou střední hodnotou vlastních informací všech realizací jevů

Jakou vlastní informaci nese zpráva o výsledku losování určitých 5 čísel z 20?

Aplikujeme vztah pro výpočet vlastní informace I(x) = − log2 p(x)

Jaká je pravděpodobnost vytažení konkrétní pětice čísel? Dosadíme do vzorce 1

I(x) = − log2 (20) = − log2 5

H(X) = −

1 = 13,92 15 504



n ∑

p(xi ) · log2 p(xi ) =

i=1

n ∑

p(xi ) · I(xi )

i=1

Entropie zahrnující informační množství celého jevu se nazývá též úplná informace

V jakých jednotkách je výsledek a co nám výsledná hodnota říká? .


.



.





17/44

Příklad

18/44

Příklad

Počáteční situace

Následující situace

— soutěžící v televizní soutěži má na výběr ze čtyř odpovědí na zadanou otázku — správnou odpověď však nezná a dokonce ani žádnou variantu nepreferuje

— soutěžící požádá o nápovědu „50 na 50“ — na výběr už má jen dvě varianty

Nejistota soutěžícího v této situaci — správná odpověď může být se stejnou pravděpodobností kterákoliv ze dvou nabídnutých

Nejistota soutěžícího v této situaci — správná odpověď může být se stejnou pravděpodobností kterákoliv ze čtyř nabídnutých

p(xi ) = 0,5

p(xi ) = 0,25

Hodnota informační entropie soutěžícího

Hodnota informační entropie soutěžícího H(X) = −2 · 0,5 · log2 0,5 = − log2 0,5 = 1

H(X) = −4 · 0,25 · log2 0,25 = − log2 0,25 = 2

.


.








19/44

Příklad

Odvození nejmenší míry informace

Následující situace

Entropie nabývá nejvyšší hodnoty při stejné pravděpodobnosti výskytu realizací xi

— soutěžící si vybere jednu variantu a odpoví na otázku — vzápětí se dozví správnou odpověď

Potom platí H(X) = − log2 p(x)

Nejistota soutěžícího v této situaci — správnou odpověď soutěžící v tuto chvíli již zná

Nejmenší jednotka míry informace (1 bit) je odvozena od entropie jevu, který má jen dvě stejně pravděpodobné realizace

p(x) = 1

H(X) = −2 · 0,5 · log2 0,5 = − log2 0,5 = 1

Hodnota informační entropie soutěžícího H(X) = −1 · log2 1 = − log2 1 = 0

.



.



20/44

.



Přenos a kódování dat


21/44

Řešený příklad

22/44

Signál

Vypočtěte entropii zdroje zpráv: Na železničním návěstidle je možné nastavit návěstí „Stůj“, které svítí 80 % času, a pak dalších 5 různých návěští s přibližně stejnou pravděpodobností Možné realizace jevu X — x1 p(x1 ) = 0,8 — x2 p(x2 ) = 0,04 — x3 p(x3 ) = 0,04 — x4 p(x4 ) = 0,04 — x5 p(x5 ) = 0,04 — x6 p(x6 ) = 0,04 Dosadíme do vzorce

Základní podmínkou využívání informací je jejich výměna mezi příjemci a odesilateli Informace má nehmotnou povahu, přenos musí být proveden nějakým fyzikálním procesem Nositelem informace nazýváme signál Fyzikální veličinu lze matematicky modelovat funkcí prostoru a času s = f(x, y, z, t), kde s je libovolný signál vyjádřený nezávislými souřadnicemi místa (x, y, z) a časovým parametrem t

.

H(X) = −(0,8 · log2 0,8 + 5 · 0,04 · log2 0,04) = 1,19

.


.








Dělení signálů dle časového parametru t

23/44

24/44

Diskrétní signál

Spojité — každý časový okamžik signálu nese určitou informaci — telefonní rozhovory

Diskrétní — signál nese informaci jen v některých okamžicích — telegrafní zprávy

vzorkování

před přenosem

Statické — hodnota t nemá vliv na hodnotu signálu — kniha, mapa

Dynamické — hodnota signálu závisí na hodnotě t — televizní přenos

.



po přenosu zkresleno .

rekonstrukce Výpočetní technika I


.





25/44

Komunikace

26/44

Kódování informace

Informační vazba – vzniká mezi dvěma systémy tvorbou, přenosem a výměnou informace Informační vazba umožňuje tzv. komunikaci Komunikace jedním směrem tvoří jednoduchý komunikační řetěz

Základní podmínkou komunikace je vytvoření signálního komunikačního kanálu Informaci je pro tento účel nutné transformovat, tj. vyjádřit v jiném jazyce s jinou abecedou Přiřazení znaků jedné abecedy znakům jiné abecedy se nazývá kódování, inverzní postup pak dekódování Předpis, který toto přiřazování definuje, se nazývá kód

zdroj

.

kódování

přenosový kanál


dekódování

cíl

.








27/44

Kvalita kódování, redundance Z hlediska optimálního přenosu je efektivní kód, který obsahuje minimální počet informačních prvků, každý znak kódu tedy má maximální entropii Maximální entropii má kód, kde všechny znaky abecedy jsou stejně možné a jejich vzájemný výskyt není závislý Kvantitativně je hospodárnost kódu vyčíslitelná redundancí (nadbytečností) R=1−

28/44

Způsoby kódování Rovnoměrné kódování — každému znaku je přiřazen stejně dlouhý kód — obvykle je jednodušší, rychlejší na zpracování, ale méně hospodárné — Baudotovo kódování

Nerovnoměrné kódování — každému znaku je přiřazen jinak dlouhý kód — pro konstrukci a zpracování je obtížnější, může však být maximálně hospodárné — Shannon–Fanovo kódování, Huffmanovo kódování

H Hmax

— H – entropie jazyka — Hmax – maximální entropie při použití téže abecedy

Redundance evropských jazyků je větší než 0,5 (0,75?) .



.



.





29/44

Příklady kódů Zdroj produkuje 4 nezávislé znak A, B, C, D Stejné pravděpodobnosti

Různé pravděpodobnosti

Znak p1 (x) Kód 1 Kód 2

Znak p2 (x) Kód 1 Kód 2

A B C D

0,250 0,250 0,250 0,250

00 01 10 11

A B C D

0 10 110 111

0,500 0,250 0,125 0,125

00 01 10 11

0 10 110 111

Znak

p(x)

Výskytů

Kód 1

0

1

Kód 2

0

1

A B C D

0,250 0,250 0,250 0,250

250 250 250 250

00 01 10 11

500 250 250 0

0 250 250 500

0 10 110 111

250 250 250 0

0 250 500 750

Zpráva

×

1000

×

1000 1000

( H(X1 ) = −

Který kód je efektivnější?

( H(X2 ) = −

.


.


×

1000 1000 1000 1000 · log2 + · log2 2000 2000 2000 2000 750 750 1500 1500 · log2 + · log2 2250 2250 2250 2250 Výpočetní technika I

750 1500

) = 1,000 ) = 0,918






31/44

Zjištění efektivnosti kódu výpočtem entropie Znak

p(x)

Výskytů

Kód 1

A B C D

0,500 0,250 0,125 0,125

500 250 125 125

00 01 10 11

1000 0 250 250 125 125 0 250

0 10 110 111

500 0 250 250 125 250 0 375

Zpráva

×

1000

×

1375 625

×

875 875

( H(X1 ) = −

( H(X2 ) = −

.

30/44

Zjištění efektivnosti kódu výpočtem entropie

0

1

Kód 2

1375 1375 625 625 · log2 + · log2 2000 2000 2000 2000 875 875 875 875 · log2 + · log2 1750 1750 1750 1750 Výpočetní technika I


0

32/44

Výpočet optimálního kódu Shannon–Fanův algoritmus

1

Znaky uspořádáme sestupně podle pravděpodobnosti jejich výskytu Vypočteme kumulativní pravděpodobnosti Rozdělíme znaky do dvou skupin tak, aby jejich součtové pravděpodobnosti byly blízké 0,5

)

Předchozí krok opakujeme tak dlouho, dokud existují vícečlenné skupiny znaků

= 0,896 ) = 1,000

.



.

Ochrana dat

Úvod do teorie informace Přenos a kódování dat

33/44

Shannon–Fanův algoritmus Znak

p(x)

s(x)

x1

0,30

1,00

x2

0,24

0,70

x3

0,20

0,46

x4

0,15

0,26

0,11

0,11

x5

(

H(X) = −

Skupiny

0

1

1

Při přenosu může nastat chyba vlivem technické nedokonalosti přenosového kanálu

Výsledek

0

00

1

01

0

10 0

110

1

111

139 139 107 107 · log2 + · log2 246 246 246 246

34/44

Proč zabezpečovat?

Při přenosu může nepovolaná osoba číst přenášená data Při přenosu může nepovolaná osoba modifikovat přenášená data

) = 0,988

0,988 R=1− = 0,012 1 .


.



Ochrana dat

Ochrana dat

Zabezpečení proti technickým nedokonalostem přenosu

Detekce chyby – zjištění, že v přeneseném úseku nastala chyba, není však známo přesné místo Možnosti detekce — parita � — kontrolní součet

— jednonásobná chyba – například jedna chyba v přeneseném bytu — dvojnásobná chyba, vícenásobná chyba — četnost chyb s násobností obvykle prudce klesá (např. 0,001/s; 0,000 03/s) — četnost chyb je velmi relativní, záleží na zařízení



36/44

Detekce chyby 35/44

Chyba – změna 0 → 1 nebo 1 → 0 Násobnost chyby – počet chyb v jednotce dat

.


Obojí na podobném principu — detekce chyb s lichou násobností — jednoduchá realizace — široké použití

.



.

Ochrana dat

Ochrana dat

Kontrolní součet

Parita

37/44

Detekce – parita Parita – doplnění binárních jedniček na

Kontrolní součet – přídavný údaj vypočtený z dat zvoleným způsobem a kontrolovaný stejným postupem na přijímací straně Používají se různé varianty pro různé účely

— sudý počet – sudá parita — lichý počet – lichá parita

Jednoduchá parita – jeden paritní bit Kombinovaná parita – více paritních bitů Příklady:

— — — — —

— jednoduchá parita realizovaná devátým bitem (operační paměť) sudá: 01010110 0 lichá: 01010110 1 — jednoduchá parita realizovaná osmým bitem (Internet) sudá: 01010110 lichá: 11010110 — kombinovaná parita pracuje na stejném principu, ale paritních bitů je vícenásobná (první čtveřice, druhá, liché bity, sudé bity) sudá: 01011001 0011

.


38/44

Detekce – kontrolní součet

podélná parita CRC (Cyclic Redundancy Check) hashování (otisk prstu, miniatura) MD5 (Message Digest Algorithm) SHA (Secure Hash Algorithm)

.




Ochrana dat

Ochrana dat

Kontrolní součet

Kontrolní součet

39/44

Podélná parita

40/44

Oprava chyb

Operace aritmetického součtu bez přenosu do vyššího řádu (XOR) 01101010 11001011 00101010 10001011

Detekce místa chyby – pak stačí provést opravu inverzí příslušného bitu Jednoduchá detekce – kombinovanou paritou nebo kombinací příčné a podélné parity Složitější detekce – použitím samoopravného kódu

Každý bit kontrolního součtu doplňuje počet binárních jedniček v příslušném řádu na sudý počet Proto se kontrolnímu součtu někdy říká podélná parita

.



.



.

Ochrana dat

Ochrana dat

Samoopravný kód

Kontrolní součet

41/44

Kombinace parit

Kód schopný detekovat místo chyby

Chyba se projeví v několika místech – podle hodnoty paritních bitů lze zjistit místo chyby 01101010 01001011 10101010 10001011

42/44

Samoopravný kód Příklad: Hammingův kód – založen na existenci povolených a zakázaných kódových kombinací

01101010 01011011 10101010 10001011

Hammingova vzdálenost – určuje se pro dvě hodnoty a je rovna počtu rozdílných bitů x = 011010111010 y = 001010101110 h=3

.


.




Ochrana dat

Ochrana dat

Samoopravný kód

Samoopravný kód

43/44

Princip Hammingova kódu

44/44

Detekce a oprava chyby

Povolené hodnoty – kódové kombinace, které mají od sebe navzájem Hammingovu vzdálenost minimálně k

povolené hodnoty vyznačeny, k = 4

Kód (část):

100101101010 100101101000 100101101001 100101101101 100101100101

Zakázané hodnoty – všechny ostatní kódové kombinace, jejich podstatně více než povolených Přenos kódové informace – získá-li se po přenosu zakázaná kombinace, buď je detekována chyba, nebo se podle Hammingovy vzdálenosti určí nejbližší povolená hodnota

Přenos: 100101100101 −→ 100101100101 100101100101 −→ 100101101101 100101100101 −→ 100101101001

OK Oprava Detekce

Násobnost chyby < k/2 ... oprava, násobnost = k/2 ... detekce .



.



Osnova přednášky. Informace v počítači. Interpretace dat. Údaje, data. Úvod do teorie informace. Výpočetní technika I. Ochrana dat

Recommend Documents