Opravný kód

Opravný kód (také kód pro opravu chyb ) je kód určený k detekci a opravě chyb .

Hlavní technikou je přidání speciálně strukturovaných redundantních informací (například kontrolní číslo ) do užitečného zatížení při zápisu (přenosu) a při čtení (přijímání) pomocí těchto redundantních informací k detekci a opravě chyb. Počet chyb, které lze opravit, je omezený a závisí na konkrétním použitém kódu.

Kódy detekce chyb (které mohou pouze zjistit skutečnost, že došlo k chybě) patří do stejných tříd kódů jako kódy pro opravu chyb. Ve skutečnosti lze k detekci chyb použít také jakýkoli kód opravující chyby (přitom bude schopen detekovat více chyb, než byl schopen opravit). Kódy pro opravu chyb se používají v digitálních komunikačních systémech , včetně: satelitu, rádiového relé, mobilní sítě, přenosu dat přes telefonní kanály a také v systémech pro ukládání informací, včetně magnetických a optických. Kódy pro detekci chyb se používají v různých úrovních síťových protokolů .

Podle způsobu práce s daty se kódy opravující chyby dělí na blokové , které rozdělují informace na fragmenty konstantní délky a zpracovávají každý z nich samostatně, a konvoluční , které pracují s daty jako souvislý proud. .

Blokové kódy

Blokový kód, který rozděluje informace na fragmenty bitové délky a převádí je na kódová slova bitové délky, se obvykle označuje ; toto číslo se nazývá kódová sazba . Pokud kód ponechá původní bity beze změny a přidá kontroly, nazývá se takový kód systematický , jinak - nesystematický . $k$ $n$ $(n,\;k)$ $R=\frac{k}{n}$ $k$ $nk$

Blokový kód můžete nastavit různými způsoby, včetně tabulky, kde je každá sada informačních bitů spojena s bitem kódového slova. Dobrý kód však musí splňovat alespoň následující kritéria: $k$ $n$

schopnost opravit co nejvíce chyb,
co nejmenší redundanci,
snadnost kódování a dekódování.

Výše uvedené požadavky si obecně odporují, takže existuje velké množství kódů, z nichž každý je vhodný pro určitý okruh úkolů. Téměř všechny používané kódy jsou lineární , což je způsobeno skutečností, že nelineární kódy je mnohem obtížnější studovat a je pro ně obtížné poskytnout přijatelnou snadnost kódování a dekódování.

Lineární kódy obecného tvaru

Lineární blokový kód je takový kód, že sada jeho kódových slov tvoří -rozměrný lineární podprostor v -rozměrném lineárním prostoru , izomorfní s prostorem -bitových vektorů . $k$ $C$ $n$ $k$

To znamená, že operace kódování odpovídá násobení původního -bitového vektoru nedegenerovanou maticí , nazývanou generátorová matice. $k$ $G$

Pro podprostor ortogonální vzhledem k matici , která definuje základ tohoto podprostoru, a pro jakýkoli vektor platí následující: $C$ $C^{\perp}$ $H$ $\overrightarrow{v}\v C$

{\overrightarrow {v}}H^{T}={\overrightarrow {0}}

. Minimální vzdálenost a korekční síla

Hammingova vzdálenost (Hammingova metrika) mezi dvěma kódovými slovy je počet různých bitů v odpovídajících pozicích: $\overrightarrow{u}$ $\overrightarrow{v}$

d_H(\overrightarrow{u},\;\overrightarrow{v})=\sum_s{|u^{(s)}-v^{(s)}|}

Minimální Hammingova vzdálenost je důležitou charakteristikou lineárního blokového kódu. Ukazuje, jak „daleko“ jsou kódy od sebe. Definuje další, neméně důležitou vlastnost - korekční schopnost : $d_\min=\min_{u\ne v}d_H(\overrightarrow{u},\;\overrightarrow{v})$

t=\left\lfloor\frac{d_\min-1}{2}\right\rfloor

Opravná síla určuje, kolik chyb přenosu kódu (typu ) lze zaručit, že budou opraveny. To znamená, že kolem každého kódového slova máme -neighborhood , které se skládá ze všech možných možností pro přenos kódového slova s počtem chyb ( ) ne větším než . Žádná dvě sousedství jakýchkoli dvou kódových slov se navzájem neprotínají, protože vzdálenost mezi kódovými slovy (tj. středy těchto sousedství) je vždy větší než dva jejich poloměry . $1\leftrightarrow 0$ $A$ $t$ $V$ $A$ $1\leftrightarrow 0$ $t$ $d_H(A,\;B)\geqslant d_\min>2t$

Po přijetí zkreslené kódové kombinace od , dekodér rozhodne, že původní kódová kombinace byla , čímž již neopravuje žádné chyby. $V$ $A$ $t$

Například, pokud existují pouze dvě kódová slova a Hammingova vzdálenost mezi nimi je rovna 3, lze chybu v jednom bitu slova opravit, protože i v tomto případě je přijaté slovo blíže kódovému slovu než . Pokud však kanál zavedl chyby ve dvou bitech (ve kterých se lišil od ), pak bude výsledek chybného přenosu blíže než a dekodér rozhodne, že slovo bylo přeneseno . $A$ $B$ $A$ $A$ $B$ $A$ $B$ $A$ $B$ $A$ $B$

Hammingovy kódy

Hammingovy kódy jsou nejjednodušší lineární kódy s minimální vzdáleností 3, to znamená, že jsou schopné opravit jednu chybu. Hammingův kód může být reprezentován takovým způsobem, že syndrom je:

\overrightarrow{s}=\overrightarrow{r}H^T

kde je přijatý vektor, se bude rovnat číslu pozice, ve které došlo k chybě. Tato vlastnost velmi usnadňuje dekódování. $\overrightarrow{r}$

Obecná metoda pro dekódování řádkových kódů

Jakýkoli kód (včetně nelineárního) lze dekódovat pomocí běžné tabulky, kde každá hodnota přijatého slova odpovídá nejpravděpodobnějšímu přenášenému slovu . Tato metoda však vyžaduje použití obrovských tabulek již pro relativně malá kódová slova. $\overrightarrow{r}_i$ $\overrightarrow{u}_i$

U lineárních kódů lze tento způsob výrazně zjednodušit. V tomto případě se pro každý přijatý vektor vypočítá syndrom . Protože , kde je kódové slovo a je chybový vektor, pak . Poté se pomocí tabulky syndromů určí chybový vektor, s jehož pomocí se určí přenášené kódové slovo. V tomto případě je tabulka mnohem menší než při použití předchozí metody. $\overrightarrow{r}_i$ $\overrightarrow{s}_i=\overrightarrow{r}_i H^T$ $\overrightarrow{r}_i=\overrightarrow{v}_i+\overrightarrow{e}_i$ $\overrightarrow{v}_i$ $\overrightarrow{e}_i$ $\overrightarrow{s}_i=\overrightarrow{e}_i H^T$

Lineární cyklické kódy

Navzdory skutečnosti, že dekódování lineárních kódů je mnohem jednodušší než dekódování většiny nelineárních kódů, pro většinu kódů je tento proces stále poměrně komplikovaný. Cyklické kódy mají kromě jednoduššího dekódování další důležité vlastnosti.

Cyklický kód je lineární kód s následující vlastností: jestliže je kódové slovo, pak jeho cyklická permutace je také kódovým slovem. $\overrightarrow{v}$

Slova cyklického kódu jsou vhodně reprezentována jako polynomy. Například kódové slovo je reprezentováno jako polynom . V tomto případě je cyklický posun kódového slova ekvivalentní násobení polynomu modulo . $\overrightarrow{v}=(v_0,\;v_1,\;\ldots,\;v_{n-1})$ $v(x)=v_0+v_1 x+\ldots+v_{n-1}x^{n-1}$ $X$ $x^n-1$

Nejčastěji se používají binární cyklické kódy (to znamená, že mohou nabývat hodnot 0 nebo 1). $v_0,\;v_1,\;\ldots$

Generování polynomu

Lze ukázat, že všechna kódová slova konkrétního cyklického kódu jsou násobky určitého generujícího (generujícího) polynomu . Polynom generátoru je dělitel . $g(x)$ $x^n-1$

Pomocí generujícího polynomu se kódování provádí cyklickým kódem. Zejména:

nesystematické kódování se provádí vynásobením zakódovaného vektoru : ; $g(x)$ $v(x)=u(x)g(x)$
systematické kódování se provádí „přidáním“ ke zakódovanému slovu zbytek dělení , tedy . $x^{nk}u(x)$ $g(x)$ $v(x)=x^{nk}u(x)+[x^{nk}u(x)\,\bmod\,g(x)]$

CRC kódy

CRC kódy ( anglicky cyclic redundancy check - cyclic redundant check) jsou systematické kódy určené nikoli k opravě chyb, ale k jejich odhalování. Používají metodu systematického kódování uvedenou výše: „kontrolní součet“ se vypočítá vydělením . Protože není vyžadována žádná oprava chyb, lze ověření přenosu provést stejným způsobem. $x^{nk}u(x)$ $g(x)$

Tvar polynomu tedy specifikuje konkrétní CRC kód. Příklady nejoblíbenějších polynomů: $g(x)$

Krycí jméno	Stupeň	Polynom
CRC-12	12	$x^{12}+x^{11}+x^{3}+x^{2}+x+1$
CRC-16	16	$x^{16}+x^{15}+x^{2}+1$
CRC- CCITT	16	$x^{16}+x^{12}+x^{5}+1$
CRC-32	32	$x^{32}+x^{26}+x^{23}+x^{22}+x^{16}+x^{12}+x^{11}+x^{10}+x^ {8}+x^{7}+x^{5}+x^{4}+x^{2}+x+1$

BCH kódy

Bose-Chowdhury-Hockwingham (BCH) kódy jsou podtřídou cyklických kódů. Jejich rozlišovacím znakem je schopnost zkonstruovat BCH kód s minimální vzdáleností, která není menší než daná. To je důležité, protože obecně řečeno je určení minimální vzdálenosti kódu velmi obtížný úkol.

Kódy opravy chyb Reed-Solomon

Reed-Solomonovy kódy jsou nebinární cyklické kódy, které umožňují opravovat chyby v datových blocích. Prvky kódového vektoru nejsou bity, ale skupiny bitů (bloky). Reed-Solomonovy kódy, které pracují s byty ( oktety ), jsou velmi běžné.

Matematicky jsou Reed-Solomonovy kódy BCH kódy .

Výhody a nevýhody blokových kódů

Ačkoli blokové kódy obecně fungují dobře s řídkými, ale velkými shluky chyb , jsou méně účinné pro časté, ale malé chyby (například v kanálu AWGN ).

Konvoluční kódy

Konvoluční kódy na rozdíl od blokových nerozdělují informace na fragmenty a pracují s nimi jako s nepřetržitým datovým tokem. Takové kódy jsou zpravidla generovány diskrétním lineárním časově invariantním systémem . Na rozdíl od většiny blokových kódů je tedy konvoluční kódování velmi jednoduchou operací, což se o dekódování říci nedá.

Konvoluční kódování kódu se provádí pomocí posuvného registru , jehož odbočky se sčítají modulo dva. Takových součtů mohou být dvě (nejčastěji) i více.

Konvoluční kódy jsou obvykle dekódovány pomocí Viterbiho algoritmu , který se snaží obnovit přenášenou sekvenci podle kritéria maximální pravděpodobnosti .

Konvoluční kódy fungují efektivně v kanálu bílého šumu, ale nevypořádávají se dobře se shluky chyb. Navíc, pokud dekodér udělá chybu, vždy na svém výstupu vytvoří shluk chyb.

kaskádové kódování. Iterativní dekódování

Výhody různých metod kódování lze kombinovat použitím zřetězeného kódování . V tomto případě jsou informace nejprve zakódovány jedním kódem a poté dalším, výsledkem je kód produktu .

Oblíbená je například následující konstrukce: data jsou zakódována pomocí Reed-Solomonova kódu, poté proložena (se znaky umístěnými blízko, daleko od sebe) a zakódována konvolučním kódem. V přijímači je konvoluční kód nejprve dekódován, poté je provedeno zpětné prokládání (v tomto případě shluky chyb na výstupu konvolučního dekodéru spadají do různých kódových slov Reed-Solomonova kódu) a poté Reed-Solomonův kód. Šalamounův kód je dekódován.

Některé produktové kódy jsou speciálně navrženy pro iterativní dekódování, ve kterém se dekódování provádí ve více průchodech, přičemž každý využívá informace z předchozího. To umožňuje vysokou efektivitu, ale dekódování je náročné na zdroje. Tyto kódy zahrnují turbo kódy a LDPC kódy (Gallagerovy kódy).

Hodnocení účinnosti kódů

Účinnost kódů je dána počtem chyb, které dokáže opravit, množstvím nadbytečných informací, které je třeba přidat, a složitostí implementace kódování a dekódování (jak hardware, tak počítačový software ).

Hammingovo vázané a dokonalé kódy

Nechť existuje binární blokový kód s opravnou schopností . Pak platí nerovnost (nazývaná Hammingova vazba): $(n,k)$ $t$

\sum_{i=0}^t {n\vyberte i}\leqslant 2^{nk}.

Kódy splňující tuto hranici rovnosti se nazývají dokonalé. Mezi dokonalé kódy patří například Hammingovy kódy . Kódy s velkou korekční silou , které se v praxi často používají (jako Reed-Solomonovy kódy ), nejsou dokonalé.

Literatura

Blahut R. Teorie a praxe kódů kontroly chyb. — M .: Mir , 1986. — 576 s.
McWilliams F. J., Sloan N. J. A. Theory of error-corpairing codes. Moskva: Rádio a komunikace, 1979.
Morelos-Zaragoza R. Umění kódování opravující chyby. Metody, algoritmy, aplikace / per. z angličtiny. V. B. Afanasjev . - M. : Technosfera, 2006. - 320 s. — (Svět komunikace). - 2000 výtisků. — ISBN 5-94836-035-0 .