Konvoluční kód je kód opravující chyby, ve kterém
Konvoluční kód je speciální případ stromových a mřížových kódů.
V roce 1955 navrhl L. M. Fink , který byl v té době vedoucím katedry Leningradské akademie spojů, první opakující se kód.
V roce 1959 západní specialista Hegelberger ( Hegelbeger ), který o práci sovětských vědců v oblasti kódování neměl ani ponětí, „znovuobjevil“ opakující se kód a pojmenoval jej po sobě.
Sám Fink ve své monografii „The Theory of Discrete Message Transmission“ [1] napsal: „V tomto kódu není sekvence kódových symbolů rozdělena na samostatné kódové kombinace. Korekční symboly jsou zahrnuty v proudu informačních symbolů tak, že jeden korekční symbol je umístěn mezi každé dva informační symboly. Označením informačních znaků prostřednictvím a opravných znaků získáme následující posloupnost znaků:
Informační symboly jsou určeny přenášenou zprávou a opravné symboly jsou tvořeny podle následujícího pravidla:
(1.1)
kde je libovolné celé číslo nazývané krok kódu ( ). Je zřejmé, že pokud je omylem přijat nějaký opravný symbol b i , vztah (1.1) v přijaté sekvenci nebude pro . V případě chybného příjmu informačního symbolu nebude vztah (1.1) platit pro dvě hodnoty , totiž pro a pro . Odtud je snadné odvodit pravidlo opravy chyb dekódování. V akceptované posloupnosti kódů je vztah (1.1) kontrolován pro každý . Pokud není spokojen se dvěma hodnotami ( a ), a současně
(1.2)
pak musí být informační prvek obrácen.
Je zřejmé, že redundance kódu je . Umožňuje opravit všechny chybně přijaté znaky, kromě některých špatných kombinací. Pokud tedy , poskytuje správné dekódování, když jsou mezi dvěma chybně přijatými symboly alespoň tři (a v některých případech dva) správně přijaté symboly (v úvahu se berou jak informační, tak testovací symboly).
Schéma kodéru nerekurzivního konvolučního kódu je znázorněno na obr.1 . Skládá se z -ary posuvných registrů s délkami . Některé (možná všechny) registrační vstupy a výstupy některých paměťových buněk jsou připojeny k několika modulovým sčítačkám . Počet sčítaček je větší než počet posuvných registrů:
Při každém hodinovém cyklu kodéru jsou na jeho vstup přiváděny informační symboly, které jsou spolu se symboly uloženými v posuvných registrech přiváděny na vstupy těch sčítačů, se kterými je spojení. Výsledkem přidání jsou kódové symboly připravené k přenosu. Poté dojde k posunu v každém posuvném registru: všechny buňky jsou posunuty doprava o jeden bit, zatímco buňky nejvíce vlevo jsou vyplněny vstupními znaky a buňky nejvíce vpravo jsou vymazány. Poté se úder opakuje. Počáteční stav registrů je znám předem (obvykle nula).
Pro názornost prezentace popíšeme konvoluční kódování podle činnosti odpovídajícího kódovacího zařízení.
Konvoluční kodér je zařízení, které obecně přijímá k vstupních informačních symbolů v každém cyklu činnosti a vydává n výstupních symbolů na výstupu každého cyklu. Číslo se nazývá relativní kódová rychlost. k je počet informačních symbolů, n je počet symbolů přenesených do komunikačního kanálu v jednom cyklu příchodu informačního symbolu do kodéru. Výstupní symboly uvažovaného cyklu závisí na m informačních symbolech přicházejících do tohoto a předchozích cyklů, to znamená, že výstupní symboly konvolučního kódu jsou jednoznačně určeny jeho vstupními symboly a stavem, který závisí na m - k předchozích informačních symbolech . Hlavními prvky konvolučního kódu jsou: posuvný registr, sčítačka modulo 2, komutátor.
Posuvný registr je dynamické paměťové zařízení, které ukládá binární znaky 0 a 1. Paměť kódu určuje počet spouštěcích buněk m v posuvném registru. Když na vstup posuvného registru dorazí nový informační znak, znak uložený v bitu nejvíce vpravo je z registru odstraněn a resetován. Zbývající znaky se posunou o jednu číslici doprava a tím se uvolní číslice zcela vlevo, kam dorazí nový informační znak.
Sčítačka modulo 2 sčítá přicházející symboly 1 a 0. Pravidlo sčítání modulo 2 je následující: součet binárních symbolů je 0, pokud je počet jedniček mezi symboly vstupujícími na vstupy sudý, a rovná se 1, pokud je toto číslo je liché.
Přepínač postupně čte symboly přicházející na jeho vstupy a nastavuje sekvenci kódových symbolů do komunikačního kanálu na výstupu. Analogicky s blokovými kódy lze konvoluční kódy rozdělit na systematické a nesystematické.
Systematický konvoluční kód je kód, který ve své výstupní sekvenci kódových symbolů obsahuje sekvenci informačních symbolů, které jej vygenerovaly. Jinak se kód nazývá nesystematický.
Při konvolučním kódování probíhá transformace informačních sekvencí na výstupní a kódové sekvence kontinuálně. Binární konvoluční kodér obsahuje posuvný registr m bitů a modulo 2 sčítačky pro generování kódových symbolů ve výstupní sekvenci. Vstupy sčítaček jsou připojeny k určitým bitům registru. Výstupní spínač určuje pořadí, ve kterém jsou kódové symboly odesílány do komunikačního kanálu. Poté je struktura kódu určena následujícími charakteristikami.
Ale! Tato definice platí pro blokové kódy s konstantní délkou. Konvoluční kódy jsou spojité a jsou charakterizovány mnoha minimálními vzdálenostmi určenými délkami počátečních segmentů kódových sekvencí, mezi nimiž se bere minimální vzdálenost. Počet symbolů v délce segmentu L přijatých pro zpracování určuje na přijímací straně počet buněk v dekodéru.
Nechť posuvný registr obsahuje m buněk, to znamená, že paměť kódu je rovna m, switch provede jeden cyklus dotazování, předá hodnoty informačních symbolů, kde m je násobek k , zatímco v jednom cyklu se dotazuje n 2 výstupy kodéru. Počet výstupních kódových symbolů ovlivněných změnou jednoho vstupního informačního symbolu je . Hodnota I all se nazývá celková délka omezení kódu .
Protože korekční vlastnosti konkrétního konvolučního kódu jsou určeny délkou omezení kódu a volbou vazeb posuvného registru na sčítačku modulo 2 ( XOR ), pak pro specifikaci struktury konvolučního kodéru je nutné určete, které bity posuvného registru jsou spojeny s každou ze sčítaček modulo 2 ( XOR ).
Zapojení j-té sčítačky modulo 2 je popsáno j-tou generující sekvencí:
g j = (g j0 , g j1 ,g j2 ,…,g jm-1 ), (4.1)kde (4.2)
Typické parametry konvolučních kódů: k, n= 1,2,…,8; R=k/n=1/4,…,7/8; m=2,…,10.
Konvoluční kód je vhodné specifikovat pomocí generujících polynomů, které jsou určeny formou vzorce (4.1) analogicky s tím, jak se to dělá u lineárních blokových cyklických kódů . [2]
Generátorový polynom zcela definuje strukturu binárního kodéru konvolučního kódu. Na rozdíl od blokových kódů , z nichž každý je popsán pouze jedním generujícím polynomem , je konvoluční kód popsán několika generujícími polynomy. Počet polynomů, které popisují konvoluční kód, je určen počtem výstupních symbolů n . Představme posloupnost informačních symbolů přicházejících na vstup kodéru jako polynom
kde X i je symbol operátoru zpoždění pro i cykly posuvného registru a i = {0, 1} jsou informační binární symboly. Polynomy popisující n sekvencí kódových symbolů vstupujících na vstup přepínače kodéru a poté do komunikačního kanálu mají tvar
kde jsou binární kódové symboly na j -tém vstupu přepínače kodéru.
j -tý generující polynom konvolučního kódu má tvar Navíc díky linearitě konvolučního kódu a akceptované notaci získáme .
Pomocí reprezentace konvolučního kódu pomocí generujících polynomů lze specifikovat konvoluční kód pomocí sekvencí koeficientů generujících polynomů zapsaných v binárním nebo osmičkovém tvaru. Osmičková notace je kompaktnější a používá se, když je posuvný registr kodéru dlouhý.
V obecném případě bude mít posloupnost koeficientů j- tého generujícího polynomu tvar a shoduje se s generující sekvencí kódu (4.1). Pak, pokud je posloupnost kódovaných symbolů a je posloupností kódových symbolů na j -tém vstupu přepínače kodéru, pak pro kterýkoli z nich, který se objeví v -tém čase ( ), můžeme napsat
Každý kódový symbol výstupní sekvence kodéru konvolučního kódu je tedy určen konvolucí kódované informace a generující sekvencí, která určuje název konvolučních kódů. Konvoluční kódy jsou speciálním případem iterativních nebo opakujících se kódů.
Konvoluční kódy se používají pro spolehlivý přenos dat: video, mobilní komunikace, satelitní komunikace. Používají se ve spojení s Reed-Solomonovým kódem a dalšími podobnými kódy. Před vynálezem turbo kódů byly takové návrhy nejúčinnější a uspokojily Shannonův limit. Konvoluční kódování se také používá v protokolu 802.11a na fyzické vrstvě MAC k dosažení rovnoměrného rozložení 0 a 1 poté, co signál projde scramblerem , v důsledku čehož se počet přenášených symbolů zdvojnásobí, a proto může dosáhnout příznivého příjmu na přijímacím zařízení.
Slovníky a encyklopedie |
---|