Blokový kód

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 15. ledna 2019; kontroly vyžadují 2 úpravy .

Blokový kód  je typ kódování kanálu v informatice. Zvyšuje redundanci zprávy tak, aby ji příjemce mohl dešifrovat s minimální (teoreticky nulovou) chybou, za předpokladu, že rychlost přenosu informace (množství přenášené informace v bitech za sekundu) nepřekročí výkon kanálu .

Hlavní charakteristikou blokového kódu je, že se jedná o kanálový kód s pevnou délkou (na rozdíl od schématu kódování zdroje dat, jako je Huffmanovo kódování , a na rozdíl od metod kanálového kódování, jako je konvoluční kódování ("konvoluční" kódování)). Typicky systém blokového kódování bere k -místné kódové slovo W jako vstup a převádí ho na n - místné kódové slovo C(W) . Toto kódové slovo se nazývá blok.

Blokové kódování bylo hlavním typem kódování používaného v raných mobilních komunikačních systémech.

Formální definice

Blokový kód je kód, který kóduje sekvence znakových sad z abecedy S do kódových slov, přičemž každý znak převádí z písmene S samostatně. Dovolit být  posloupnost přirozených čísel , každé menší než |S| . Pokud je nějaké slovo W z abecedy S napsáno jako , pak kódové slovo odpovídající W , totiž C(W) , bude: .

[n, d]

Kompromis mezi efektivitou (vyšší informační rychlost) a možnostmi záplatování lze také vidět při pokusu o nastavení pevné délky klíčového slova a pevné možnosti záplatování (reprezentované Hammingovou vzdáleností d ) a maximalizaci celkového počtu klíčových slov. [n, d]  je maximální počet klíčových slov pro danou délku klíčového slova n a Hammingovu vzdálenost d .

Informační normy

Když C  je dvojitý blokový kód sestávající z klíčových slov A o délce n bitů, pak je informační norma C definována jako:

.

V případě, že prvních k bitů klíčového slova jsou nezávislé informační bity, pak informační norma bude vypadat takto:

.

Kulové těsnění a mřížky

Blokové kódy souvisejí s problémem kulového balení, který v posledních letech přitahuje pozornost. Ve dvou rozměrech je snadné si to představit tak, že vezmete hrst stejných mincí a seřadíte je na stůl do tvaru šestiúhelníku jako v pláství. Ve velkých rozměrech však nelze blokové kódy tak snadno vizualizovat. Silný Golayův kód používaný při komunikaci v hlubokém vesmíru používá 24 dimenzí. Pokud je použit binární kód (jak se obvykle dělá), měření se vztahuje k délce klíčového slova, jak je definováno výše.

Teorie kódování využívá N-rozměrný model koule. Například kolik mincí lze umístit do kruhu na plochu stolu nebo ve 3 rozměrech, kolik mramoru lze umístit na zeměkouli. Další úvahy se týkají výběru kódu. Například šestiúhelník umístěný v ohraničeném obdélníkovém rámečku zanechá v rozích prázdné místo. S rostoucími rozměry se procento prázdného prostoru zmenšuje. Ale v určitých dimenzích je celé místo vyplněno a tyto kódy jsou takzvané dokonalé kódy. Ale je jich velmi málo.

Další často opomíjenou položkou je počet sousedů, které může mít jedno klíčové slovo. Jako příklad opět použijeme mince. Nejprve je naskládáme do obdélníkové mřížky. Každá mince bude mít 4 blízké sousedy (a 4 v nejvzdálenějších rozích). V šestiúhelníku bude mít každá mince 6 blízkých sousedů. Jak zvyšujeme počet dimenzí, počet blízkých sousedů velmi rychle roste.

Výsledkem je také nárůst počtu cest, kde by hluk nutil přijímač vybrat si souseda; proto ta chyba. Toto je základní omezení blokových kódů a vlastně všech kódů. Pro jednoho souseda může být těžší způsobit chybu, ale počet sousedů může být dostatečně velký, aby byla celková pravděpodobnost chyby skutečně možná.

Literatura