Základy teorie kódování, Shannonova věta. Entropie. Generování skutečně náhodných a pseudonáhodných sekvencí.
Entropie = nejistota.
Nechť je náhodná veličina,
a
, přičemž
.
Nejistota je funkce pravděpodobnosti dané veličiny.
Nejistota náhodné proměnné , která nabývá hodnoty
s pravděpodobností
je funkcí pouze pravděpodobností
. Tato funkce se značí
.
Pro funkci nejistoty platí:
Buď funkce definovaná pro každé
a pro všechny hodnoty
tak, že
a
. Pokud
splňuje výše uvedené axiomy, pak platí:
kde je libovolná kladná konstanta (například
) a sumuje se přes všechna
taková, že
.
Informace je funkce . Funkce
, definovaná pro všechny
, splňuje podmínky:
když je tvaru , kde
je kladná konstanta (například
).
Nejjednodušším modelem je zdroj bez paměti a kódování bez šumu. Zdroj je generátor posloupnosti symbolů z dané konečné abecedy. Pro zdroj bez paměti platí, značí-li
-tý vygenerovaný symbol, pak pro každý symbol
je pravděpodobnost
nezávislá na všech v minulosti nebo v budoucnosti vygenerovaných symbolech.
je posloupnost identicky distribuovaných nezávislých náhodných veličin.
Entropie zdroje bez paměti je , kde sčítáme přes množinu
takových, že
.
Kódování nebo kód je zobrazení z
do
. Zpráva je konečný řetěz zdrojových slov. Je li zpráva
a
kódování, pak rozšíření
k
je definováno:
.
Kódování je možné označovat taky jakou soubor kódových slov .
Kódování se nazývá jednoznačně dekódovatelné, jestliže každý konečný řetězec z je obraz nejvýše jedné zprávy.
Kódování se nazývá bezprostředně dekódovatelné nebo prefixové, jestliže neexistují různé a
takové, že
je prefix
.
Pokud má jednoznačné kódování minimální průměrnou délku slov, nazývá se kompaktní. Kompaktní kód je možné vytvořit například Huffmanovým kódováním.
Má-li zdroj bez paměti entropii , pak každé jednoznačně dekódovatelné kódování pro tento zdroj v abecedě o
symbolech musí mít délku alespoň
. Navíc existuje takové jednoznačně dekódovatelné kódování, které má průměrnou délku slov menší nebo rovnu
.
Uvážíme diskrétní kanál bez paměti. Kanál má vstupní a výstupní
abecedu.
Pro vypouštěcí kanál platí, že , kde
představuje chybu přenosu, ke které dojde s pravděpodobností
. Vypouštěcí kanál nedokáže zaměnit jeden znak abecedy za jiný znak vstupní abecedy, pouze zaměnit znak za
.
Nejběžnější model kanálu je binární symetrický kanál, kde a kanál může změnit
na
nebo naopak s pravděpodobností
.
Pro zajištění vyšší spolehlivosti přenosu zpráv je používaná redundance, parita, nebo jiné techniky, které umožňují detekovat nebo opravit chybně přenesenou zprávu.
Buď dán kanál bez paměti se vstupní abecedou a výstupní abecedou
. Kód délky
je libovolný systém
různých posloupností délky
symbolů ze
. Prvky
se nazývají kódová slova.
Je-li dán kód délky s kódovými slovy
, dekódovací pravidlo je libovolný rozklad množiny možných obdržených posloupností do disjunktních množin
se zřejmou interpretací toho, že je-li obdržená posloupnost
prvkem
, pak
je dekódováno jako kódové slovo
.
Předpokládáme, že neobsahuje symbol
, rozhodovací (dekódovací) pravidlo je funkce
. Je-li
slovo v
, pak dekódovací pravidlo dekóduje
na
, jinak hlásí chybu pokud
.
Kapacita kanálu je jeho míra schopnosti přenášet informace. Kapacita binárního symetrického kanálu s pravděpodobností chyby přenosu je určena vztahem
, kde
.
Buď dán binární symetrický kanál kapacity a libovolné
,
. Pak pro každou posloupnost
přirozených čísel splňujících
kde
, a všechna kladná
, existuje posloupnost kódů
a přirozené číslo
tak, že
má
kódových slov délky
a maximální pravděpodobnost chyby
pro všechna
.
Jakým způsobem funguje tato věta. Předpokládejme, že pravděpodobnost chyby takovéhoto kanálu je taková, že kapacita kanálu . Pak, je-li naše zpráva řetězec nul a jedniček, víme, že pro dostatečně velké
, položíme-li
, existuje množina
kódových slov délky
, která mají pravděpodobnost chyby menší než libovolně předem předepsaná hranice. Tudíž, abychom zakódovali zprávu ze zdroje, postup je následující:
Zjednodušená verzia (Honza R.): Kapacita kanálu je , hľadáme teda kód s kapacitou
. Správu rozdelíme do blokov dĺžky
a každý blok kódujeme slovom dĺžky
. Aby sme dosiahly kapacitu prenosu
, musí platiť
, t.j.
. Veta zaručuje, že pre dostatočne veľké
(a teda aj
) existuje kód s ľubovoľne malou chybou prenosu.
Buď přirozená čísla. Řekneme, že kód
určí
chyb, jestliže pokud každé kódové slovo změníme alespoň na jednom a ne více než
místech, nebude výsledný řetězec kódové slovo. Řekneme, že kód
určí právě
chyb, jestliže určí
chyb a neurčí
chyb.
Řekneme, že kód opraví
chyb, jestliže, pokud použijeme pravidlo minimální vzdálenosti, jsme schopni opravit alespoň
chyb a v případě, kdy se nebudeme moci rozhodnout, dostaneme na výstupu chybu v dekódování. Řekneme, že kód
opraví právě
chyb, jestliže opraví
chyb a neopraví
chyb.
Hammingova vzdálenost mezi vektory
a
je počet míst, ve kterých se
a
liší. Váha slova
je pak počet nenulových znaků slova
, t.j.
, kde
je slovo z
nul.
Buď . Sférou
v
se středem
a poloměrem
rozumíme množinu
.
Objemem sféry nazveme číslo
, t.j. počet řetězců délky
, které mají Hammingovu vzdálenost od
nejvýše
.
Platí, že .
Pro kód platí, že minimální vzdálenost kódu
je
. Má-li kód minimální vzdálenost
, lze opravit pomocí dekódování podle pravidla minimální vzdálenosti až
chyb. Kód
určí
chyb.
Pokud má kód právě
kódových slov délky
a minimální vzdálenost
, mluvíme o
-kódu.
-kód je maximální, pokud:
Považujme za těleso
o
prvcích. Buď dále
vektorový prostor dimenze
nad tělesem
. Typický prvek tohoto vektorového prostoru budeme psát jako
, případně
, kde
.
Lineární kód nad
je definován jakožto podprostor prostoru
. Má-li tento podprostor dimenzi
, mluvíme o
-kódu, pokud je minimální vzdálenost
, tak mluvíme o
-kódu. Protože každý k-dimenzionální podprostor nad
má
prvků, každý
-kód nad
je
-kód.
Generující matice pro lineární kód je libovolná matice rozměrů
, jejíž řádky tvoří
lineárně nezávislých kódových slov z
.
Každou generující matici je možné následujícími úpravami:
upravit do tvaru , kde
je jednotková matice typu
.
Minimální vzdálenost lineárního kódu
je minimální váha
všech nenulových vektorů z
.
Nechť je lineární
-kód nad
a má generující matici:
.
Kódová slova jsou vektory délky
tvaru
,
.
Pokud je zpráva braná jako posloupnost , zakódujeme
pomocí kódového slova
, kde
jsou určena předpisem
.
Matice kontroly parity kódu je matice
. Platí, že
právě tehdy, když
.
má minimální vzdálenost
tehdy a jen tehdy, když každých
sloupců matice
je nezávislých, ale některých
sloupců je lineárně závislých.
Nechť je obdržený vektor, pak
je možný chybový vektor vektoru
, pokud existuje
takové, že
. Pro dekódování podle pravidla minimální vzdálenosti stačí najít chybový vektor s minimální vahou.
Nechť a
. Nechť je kontrolní matice
typu
, jejíž sloupce tvoří navzájem nezávislé nenulové vektory z
.
je kontrolní matice binárního
-kódu, kde
. Mluvíme pak o Hammingově
-kódu. Každý Hammingův kód je perfektní kód opravující jednu chybu.
Kód se nazývá cyklický, pokud:
Vektor je možné identifikovat polynomem
. Je-li
polynomiální reprezentace
, je i
kódové slovo pro každý polynom
stupně nejvýše
.
Je-li nenulový polynom minimálního stupně v
, pak
generuje kód
v tom smyslu, že každé kódové slovo
je tvaru
pro vhodný polynom
.
Je-li cyklický kód délky
s generujícím polynomem
, pak jeho generující matice typu
má tvar:
Je-li generující polynom cyklického kódu
délky
, pak
dělí polynom
.
Typicky zdroj náhodnosti generuje náhodná data s nějakým rozdělením. Extraktor náhodnosti má za úkol převést toto rozdělení na uniformní rozdělení nebo se mu co nejvíce přiblížit.
Pro známé pravděpodobnosti je možné jednotlivé výstupy shlukovat tak, že extraktor vrátí stejnou hodnotu pro různé vstupy. Pravděpodobnost skupiny je součet pravděpodobností jednotlivých výstupů.
Pro neznámé pravděpodobnosti je možné využít například Von Neumannův extraktor. Zdroj generuje sekvenci náhodných bitů nezávisle podle neznámého pravděpodobnostního rozdělení, 0 s pravděpodobností a 1 s pravděpodobností
. Sekvenci je možné rozdělit na dvojice bitů:
Při generování skutečně náhodných sekvencí se využívají různé měřitelné fyzikální jevy, např. rozpad radioaktivních prvků nebo měření atmosferického šumu.
V deterministickém prostředí počítačů není možné generovat skutečně náhodná data bez použití specializovaného HW. Softwarově je možné generovat pouze pseudonáhodná data. Generátor pseudonáhodných čísel je algoritmus, který rozvojem náhodné vstupní hodnoty (semínko, seed) generuje výstupní sekvenci. V ideálním případě jsou tato data nerozlišitelná od náhodných. Kvalita generátoru záleží na kvalitě semínka a kvalitě algoritmu.
Vstup generátoru je libovolné číslo, to je umocněno. První a podlední čísla jsou odstraněna a zbytek je použit jako výstup a zároveň semínko pro další iteraci.
Příklad pro vstup :
Von Neumann použil 10místná čísla. Tento generátor není dobrý, protože má velmi malou periodu a některé hodnoty (například „0000“) se opakují ještě častěji.
DevelX - Martin Jurča (převzato z 3. otázky oboru PSK)
Drobné úpravy Ondra Mokoš
Opravy Honza Rusnačko