Kódování: Entropie, nejistota, informace. Kódování a dekódovací pravidla, kódování s šumem. Shannonova věta, kódy opravující chyby. Lineární, binární Hammingovy a cyklické kódy.
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í:
log
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 log
, kde
je kladná konstanca (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 log
, 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 sprá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á 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í.
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ň
log
: Navíc existuje takové jednoznačně dekódovatelné kódování, které má průměrnou délku slov menší nebo rovnu
log
.
Kompaktní kód je možné vytvořit například Huffmanovým kódováním.
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
log
log
, 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
, 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í:
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.
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 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
.
PřF:M8170 Teorie kódování (jaro 2009), doc. RNDr. Jan Paseka, CSc.
-
DevelX - Martin Jurča
stav - 100 %