Konvoluční 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é 27. září 2018; kontroly vyžadují 8 úprav .

Konvoluční kód je kód opravující chyby, ve kterém

v každém hodinovém cyklu kodéru jsou symboly vstupní polonekonečné sekvence převedeny na symboly výstupní sekvence $k$ $n>k$
předchozí postavy jsou také zapojeny do konverze $m$
vlastnost linearity je splněna (pokud dvě kódované sekvence a odpovídají kódovým sekvencím a , pak kódovaná sekvence odpovídá ). ${\mathbf x}$ ${\mathbf y}$ $\mathbf X$ $\mathbf Y$ $a\mathbf x+b\mathbf y$ $a\mathbf X+b\mathbf Y$

Konvoluční kód je speciální případ stromových a mřížových kódů.

Origins

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ů: $a_{i}$ $bi}$

$a_{1}b_{1}\,a_{2}b_{2}\,a_{3}b_{3}\,\tečky \,a_{k}b_{k}\,a_{k +1}b_{k+1}\,\tečky$

Informační symboly jsou určeny přenášenou zprávou a opravné symboly jsou tvořeny podle následujícího pravidla:

$b_{i}=\left(a_{ks}+a_{k+s+1}\right)\mod 2$ (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ě $s$ $s=0,1,2\tečky$ $i=k$ $a_{i}$ $k_i$ $k_{1}=is-1$ $k_{2}=i+s$ $b_{k}$ $k$ ${\displaystyle k=k_{1))$ ${\displaystyle k=k_{2))$

$k_{2}-k_{1}=2s+1$ (1.2)

pak musí být informační prvek obrácen. $a_{k_{1}+s+1}$

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). $1/2$ $s=0$

Obecné schéma nerekurzivního kodéru

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ů: $k$ $q$ $m_1. m_2,...,m_k$ $n$ $q$ $n>k$

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). $k$ $n$

Celková délka všech posuvných registrů se nazývá limit kódu a maximální délka se nazývá zpoždění . $m = \sum_{i=1}^k m_i$ $w = \max\{m_1,...,m_k\}$

Hodnoty posuvných registrů v každém okamžiku se nazývají stav kodéru.

Binární konvoluční kodéry

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. $R={\frac {k}{n}}$

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ý.

Parametry a charakteristiky konvolučních kódů

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.

Počet informačních symbolů přicházejících na vstup kodéru v jednom cyklu je k.
Počet symbolů na výstupu kodéru je n, což odpovídá k vstupním symbolům během cyklu.
Kódová rychlost je určena poměrem R=k/n a charakterizuje redundanci zavedenou během kódování.
Redundance kódu $\vartheta = 1 - R$
Paměť kódu (vstupní délka omezení kódu nebo informační délka kódového slova) je určena maximálním stupněm generujícího polynomu v generující matici G(X): $l = k \underset{i,j}{\max} \mathcal {b} \deg g _{i,j}(x)+1 \mathcal {c}$
Označení konvolučního kódu se ve většině případů označuje (n, k, l), ale jsou možné variace.
Váha w binárních kódových sekvencí je určena počtem "jednotek" obsažených v této sekvenci nebo kódových slovech.
Kódová vzdálenost ukazuje míru rozdílu mezi i-tou a j-tou kombinací kódu za předpokladu, že mají stejnou délku. Pro libovolné dvě kombinace binárních kódů je vzdálenost kódu rovna počtu znaků, které se v nich neshodují. Obecně může být kódová vzdálenost definována jako celkový výsledek modulo 2 sčítání stejnojmenných bitů kódových kombinací , kde a jsou k-tých symbolů kódových kombinací i a j; L je délka kombinace kódů. $d$
$d_{i,j} = \sum_{k=1}^L k_{i,k} \oplus k_{j,k}$ $k_{i,j}$ $k_{jk}$
Minimální kódová vzdálenost je nejmenší Hammingova vzdálenost pro sadu kódových slov konstantní délky. K jeho nalezení je nutné vyčíslit všechny možné dvojice kombinací kódů. Pak dostaneme . $d_{min}$ $d_{min} = \min d_{ij}$

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.

Celkový pohled na binární konvoluční kodér

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 . $1\le k<m$ $\geq$ $I_{all}=\frac{mn}{k}$

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) $g_{ij} = \begin{cases} 1,&\text{pokud je fáze i registru spojena s bránou XOR}\\ 0,&\text{v ostatních případech} \end{cases}$

Typické parametry konvolučních kódů: k, n= 1,2,…,8; R=k/n=1/4,…,7/8; m=2,…,10.

Metoda nastavení konvolučních kódů

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

A(X)=a_{0}+a_{1}X+a_{2}X^{2}+\tečky ,

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

B_{j}(X)=b_{0}^{j}+b_{1}^{j}X+b_{2}^{j}X^{2}+\dots ,

kde jsou binární kódové symboly na j -tém vstupu přepínače kodéru. $b_{i}^{j}=\left\{{0;1}\right\}$

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 . ${\displaystyle G_{j}(X)=g_{0}+g_{1}X+g_{2}X^{2}+\tečky +g_{m-1}X^{m-1))$ $g_{i}={0;1}$ $B_j(X) = G_j(X) A(X)$

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 $G^{j}={g_{0}^{j},g_{1}^{j},\dots ,g_{m-1}^{j))$ $A={a_{0},a_{1},a_{2},\dots }$ ${\displaystyle B_{j}={b_{0}^{j},b_{1}^{j},b_{2}^{j},\tečky ))$ $\mu$ $\mu =0,1,2,\tečky$

b_{\mu }^{j}=\sum _{i=0}^{m-1}a_{\mu -i}g_{i}^{j}.

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ů.

Aplikace

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í.

Viz také

Poznámky

↑ Fink L. M. Teorie přenosu diskrétních zpráv
↑ Sagalovich, 2014 , kapitoly 4 a 5.

Literatura

Gallagher R. Informační teorie a spolehlivá komunikace. - M . : Sovětský rozhlas, 1974. - 720 s.
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 .
Fink L. M. Teorie přenosu diskrétních zpráv. - M .: Sov. rozhlas, 1963. - 576 s.
Nikitin G.I. Konvoluční kódy: Učebnice. - Petrohrad. : Sovy. rozhlas, 2001. - 78 s.
Sagalovich Yu.L. Úvod do algebraických kódů - 3. vydání, revidováno. a doplňkové - M. : IPPI RAN , 2014. - 310 s. — ISBN 978-5-901158-24-1
Výuka konvolučních kódů Nikitin G.I
Banquet, VL "Konstrukce signálových kódů v telekomunikačních systémech." A: Phoenix (2009).
Kolesnik VD, Poltyrev G. Sh. Kurz teorie informace. - "Věda", kapitola. vyd. fyzikální a matematická literatura, 1982.
Ngok DK Zkoumání vyhledávacích metod pro optimální konvoluční a perforované konvoluční kódy: dis. – Disertační práce pro titul kandidáta technických věd. Petrohrad: LETI, 2014.

Slovníky a encyklopedie	velká čínština Britannica (online)