1. Vznik a vývoj teorie informace

2. Matematický aparát v teorii informace• Základy teorie pravděpodobnosti – Náhodné veličiny• Číselné soustavy

3. Informace• Základní pojmy – jednotka a zobrazení informace, informační hodnota• Entropie – vlastnosti entropie• Zdroje zpráv – spojité zdroje zpráv, diskrétní zdroje zpráv• Přenos informace – vlastnosti přenosu kanálů, poruchy a šumy přenosu,

způsoby boje proti šumu

4. Kódování• Elementární teorie kódování• Rovnoměrné kódy – telegrafní kód• Nerovnoměrné kódy – Morseova abeceda, konstrukce nerovnoměrných kódů• Efektivní kódy – Shannonova – Fanova metoda, Huffmanova metoda

5. Bezpečností kódy • Zabezpečující schopnosti kódů, • Systematické kódy, • Nesystematické kódy

ZÁKLADY INFORMATIKY – Elementární teorie kódováníZÁKLADY INFORMATIKY – Elementární teorie kódování

ELEMENTÁRNÍ TEORIE KÓDOVÁNÍ

ELEMENTÁRNÍ TEORIE KÓDOVÁNÍ

ELEMENTÁRNÍ TEORIE ELEMENTÁRNÍ TEORIE KÓDOVÁNÍKÓDOVÁNÍ

Dvojková soustava, s kterou počítače běžně pracují, je nevýhodná pro lidské uvažování - neumíme v ní běžně počítat.

Proto k převodu mezi „lidskými“ informacemi a počítači existují převodní pravidla kódy.

Kód je množina symbolů, kterými vyjadřujeme různé stavy systému.

Kód lze libovolně převádět jeden na druhý, aniž by se změnila velikost a

množství informace.

Kódování pak můžeme charakterizovat jako převod jednoho kódu na druhý a to buď pomocí tabulky anebo algoritmu.

Pro ukázku si zvolme jako zkušební systém hrací kostku. Po hodu se může kostka nacházet v jednom ze šesti stavů (poloh). Stav (poloha) kostky se nejčastěji vyjadřuje pomocí množiny tečkových symbolů:

Když si chceme poznamenat jak nám kostka při hře padla neuděláme to zápisem tečkových symbolů, ale číslicemi (1,2,3,4,5,6) odpovídajícími počtu teček převedeme z jedné množiny symbolů do druhé.

Vztah mezi symbolem, kódem a kódováním nám znázorňuje obrázek:

123456

ABCDEF

456789

kostka

Síť kostky (symboly) Kód 1 Kód 2 Kód 3

Na obrázku je ukázka kódování do třech různých kódů.

kódování

Vyjádřeno matematicky: Při přenosu informací používáme dvě základní abecedy.

Přenosová abeceda (abeceda přenosového kanálu) Y={ y1, ... , yR } je konečná množina znaků yj, kterou

můžeme přenášet přes nějaké přenosové zařízení.

Např. zařízení se dvěma úrovněmi řízení (0,1) bude mít abecedu Y={ y1, y2 }={ 0,1 }.

Zdrojová abeceda (abeceda zdroje) A={ a1, ... , aN }

je konečná množina znaků (symbolů) ai, kterou

chceme přenést přes nějaké přenosové zařízení (přenosový kanál).

Pod kódováním pak rozumíme zobrazení, které každému znaku aiA přiřadí nějakou skupinu

znaků yjY kódové slovo.

Množina všech kódových slov se pak nazývá kód.

Délka kódu – počet kódových slov daného kódu

Pokud délka kódového slova je mm pak délka kódu je dána vztahem: (R – počet prvků přenosové abecedy)R – počet prvků přenosové abecedy)

L = RL = Rm m

Dále se budeme zabývat pouze dvojkovými (binárními) kódydvojkovými (binárními) kódy ==> > přenosová abeceda má jen dva prvky {0, 1}

Délka kódu LL se bude tedy pohybovat v rozmezí daném nerovností:

1 1 ≤ L ≥ 2≤ L ≥ 2mm

Výskyt jednotlivých znaků zdrojové abecedy = Výskyt jednotlivých znaků zdrojové abecedy = různá pravděpodobnostrůzná pravděpodobnost

pravděpodobnost výskytu kódových slopravděpodobnost výskytu kódových slov se liv se liší ší

rozdílná hodnota rozdílná hodnota kkódovacích klíčůódovacích klíčů

Výhodnější jsou takové kódovací klíče, které přiřazují odolnější kódové slova (kratší) nejčastěji se vyskytujícím znakům zdrojové abecedy.

Je výhodnější nevyužívat maximální délky kódu LL, nýbrž počítat (s ohledem

na zvýšení bezpečnosti přenosu) pouze s délkou zkrácenou LLZZ .

Kombinační možnost vzájemného přiřazení množiny kódových slov

a množiny znaků zdrojové abecedy je dána permutací, tj. 22mm!!

Říkáme, že kód má 22mm!! kódovacích klíčů.kódovacích klíčů.

L LZ

Kódování však nemá pouze mechanicky nahrazovat jednu konkrétní abecedu jinou.

Mění-li se při kódování množina použitých symbolů i rozložení pravděpodobností, mění se také entropie na symbol zprávy.

Hlavním cílem je zajistit nejmenší počet symbolů na dané množství informace.

Důležité je, aby bylo možné ze zakódované zprávy získat zprávu zdrojovou kódování musí být jednoznačně dekódovatelné.

Kódování je jednoznačně dekódovatelné tehdy, jestliže zobrazení, které každému znaku aiA přiřadí

nějakou skupinu znaků yjY je prostým zobrazením.

Pojem slovoslovo (kódové slovo) nad danou abecedou se liší od pojmu slova používaného v běžném hovorovém jazyce (slovem rozumíme nejmenší samostatnou jazykovou jednotku mající věcný a mluvnický význam).

Umělým jazykemUmělým jazykem (stručně jazykem) nazýváme nějakou abecedu spolu s pravděpodobnostními zákony, podle nichž vzniká z dané abecedy zpráva.

Je-li H entropie daného jazyka a Hmax je maximální entropie při použití téže abecedy pak můžeme definovat redundanci (nadbytečnost)redundanci (nadbytečnost) daného jazyka jako:

Redundance evropských jazyků je větší než 0.5 a podle některých propočtů se pohybuje od 0.68 do 0.75.

maxH

H1R

Rozdělení kódůRozdělení kódů

• Podle použití se dělí dvojkové kódyPodle použití se dělí dvojkové kódy

– kódy určené k matematickým operacím,

– kódy určené k přenosu zpráv

• Podle struktury naPodle struktury na

– kódy nesystematické

– kódy systematické

• Podle délky na Podle délky na

– kódy rovnoměrné

– kódy nerovnoměrné