Informace v počítači. Výpočetní technika I. Ing. Pavel Haluza ústav informatiky PEF MENDELU v Brně

. .

Informace v počítači Výpočetní technika I Ing. Pavel Haluza ústav informatiky PEF MENDELU v Brně [email protected]

Výpočetní technika I

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

Osnova přednášky Úvod do teorie informace — základní pojmy — měření množství informace ve zprávě — přenos a kódování dat

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



Úvod do teorie informace Základní pojmy

Údaje, data Údaje — 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.“




Interpretace dat 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 Výpočetní technika I



Informace, znalosti Informace — 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

Znalosti — 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á.“ Výpočetní technika I



Jak informaci chápat? Kvalitativní hledisko — získávání, uchovávání, zpracování a přenos informací — zkoumá informatika

Kvantitativní hledisko — — — —

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




Pojem informace Mnoho různých definic podle toho, co autoři definice považovali za nejdůležitější 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ů Informace je obsah zprávy, sdělení, objasnění, vysvětlení, poučení 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




Informační systém Systém – komplex prvků a vazeb ve vzájemné interakci (definice v teorii systémů) Informační systém – dynamický systém, jehož vazby tvoří informace a prvky systému jsou místa transformace informací Úkol IS – poskytovat potřebné informace v požadovaném rozsahu, lhůtách, podrobnostech i formě Dílčí úlohy IS – sběr informací, přenos, redukce, archivace, zpracování, distribuce



Úvod do teorie informace Měření množství informace ve zprávě

Měření množství informace ve zprávě Americký fyzik Claude Shannon (1916–2001) — položení základů teorie informace — stanovení možností měření informačního množství

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

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 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ě Výpočetní technika I



Měření množství informace ve zprávě Jak kvantifikovat rozšíření okruhu znalostí příjemce? Pravděpodobnost zprávy — spojeno s individuálními vlastnostmi příjemce (Shannon)

Jev — náhodný proces s n možnými realizacemi — tah sportky, účast na přednášce, semafor na křižovatce aj.

Realizace jevu — 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.




Požadované vlastnosti funkce pro výpočet množství informace Jev X má n realizací, množství informace je tedy funkcí n Jediná realizace jevu X — pokud n = 1, jedná se o jev jistý — množství informace je rovno nule

Současně probíhající nezávislé jevy X a Y — p(x, y) = p(x) · p(y) — množství informace je dáno součtem množství informace u jednotlivých jevů: f(x, y) = f(x) + f(y)

Porovnání pro dva odlišné jevy X a Y — 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



Výpočet vlastní 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) = , n

kde n je počet realizací Úpravou dostáváme n=


1 p(x)



Výpočet vlastní informace Vlastní informace výsledku realizace x I(x) = − log p(x)

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

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

logb x = loga b · logb x logb a

log2 x = log2 10 · log x = 3,322 · log x Výpočetní technika I



Aplikace vlastní informace Výpočet vlastní informace v bitech = výpočet prostoru pro zadaný počet hodnot — příklad: barevná hloubka rastrového obrazu

Velikost prostoru v počítači pro určitý údaj – hodnocení úspornosti — příklad: uložení 6 tažených čísel Sportky – znaky, čísla malá, velká, souhrn, kódování

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.)




Řešený příklad 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

1 = 13,92 15 504

V jakých jednotkách je výsledek a co nám výsledná hodnota říká? Výpočetní technika I



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ů H(X) = −

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ýpočetní technika I



Příklad Počáteční 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

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,25

Hodnota informační entropie soutěžícího H(X) = −4 · 0,25 · log2 0,25 = − log2 0,25 = 2 Výpočetní technika I



Příklad Následující situace — 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 p(xi ) = 0,5

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



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

Nejistota soutěžícího v této situaci — správnou odpověď soutěžící v tuto chvíli již zná p(x) = 1

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




Odvození nejmenší míry informace Entropie nabývá nejvyšší hodnoty při stejné pravděpodobnosti výskytu realizací xi Potom platí H(X) = − log2 p(x)

Nejmenší jednotka míry informace (1 bit) je odvozena od entropie jevu, který má jen dvě stejně pravděpodobné realizace H(X) = −2 · 0,5 · log2 0,5 = − log2 0,5 = 1




Řešený příklad 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

.

H(X) = −(0,8 · log2 0,8 + 5 · 0,04 · log2 0,04) = 1,19 Výpočetní technika I


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

Signál 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




Dělení signálů dle časového parametru t 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

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

Dynamické — hodnota signálu závisí na hodnotě t — televizní přenos Výpočetní technika I



Diskrétní signál

vzorkování

před přenosem

po přenosu zkresleno

rekonstrukce Výpočetní technika I



Komunikace 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

zdroj

kódování

přenosový kanál


dekódování


cíl


Kódování informace 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




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−

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?) Výpočetní technika I



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í




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

0 10 110 111

A B C D

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

00 01 10 11

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



0 10 110 111


Zjištění efektivnosti kódu výpočtem entropie 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 ) = −

( 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


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 ) = −

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

1

) = 0,896 ) = 1,000


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

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ů




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

x5

0,11

0,11

(

H(X) = −

Skupiny

0

1

1

Výsledek

0

00

1

01

0

10 0

110

1

111

139 139 107 107 · log2 + · log2 246 246 246 246 R=1−

)

0,988 = 0,012 1



= 0,988

Ochrana dat

Proč zabezpečovat? Při přenosu může nastat chyba vlivem technické nedokonalosti přenosového kanálu 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



Ochrana dat

Zabezpečení proti technickým nedokonalostem přenosu Chyba – změna 0 → 1 nebo 1 → 0 Násobnost chyby – počet chyb v jednotce dat — 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í



Ochrana dat

Detekce chyby 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

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



Ochrana dat Parita

Detekce – parita Parita – doplnění binárních jedniček na — 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 Výpočetní technika I


Ochrana dat Kontrolní součet

Detekce – kontrolní součet 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 — — — — —

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




Podélná parita Operace aritmetického součtu bez přenosu do vyššího řádu (XOR) 01101010 11001011 00101010 10001011 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




Oprava chyb 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




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


01101010 01011011 10101010 10001011


Ochrana dat Samoopravný kód

Samoopravný kód Kód schopný detekovat místo chyby Příklad: Hammingův kód – založen na existenci povolených a zakázaných kódových kombinací Hammingova vzdálenost – určuje se pro dvě hodnoty a je rovna počtu rozdílných bitů x = 011010111010 y = 001010101110 h=3




Princip Hammingova kódu Povolené hodnoty – kódové kombinace, které mají od sebe navzájem Hammingovu vzdálenost minimálně k 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




Detekce a oprava chyby povolené hodnoty vyznačeny, k = 4

Kód (část):

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

OK Oprava Detekce

Násobnost chyby < k/2 ... oprava, násobnost = k/2 ... detekce Výpočetní technika I


Informace v počítači. Výpočetní technika I. Ing. Pavel Haluza ústav informatiky PEF MENDELU v Brně

Recommend Documents