Konvolúciós kód

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2018. szeptember 27-én felülvizsgált verziótól ; az ellenőrzések 8 szerkesztést igényelnek .

A konvolúciós kód egy hibajavító kód , amelyben

a kódoló minden órajelében a bemeneti félvégtelen sorozat szimbólumai a kimeneti sorozat szimbólumaivá alakulnak $k$ $n>k$
a korábbi karakterek is részt vesznek az átalakításban $m$
a linearitás tulajdonsága teljesül (ha két kódolt szekvencia és megfelel a és kódsorozatoknak , akkor a kódolt sorozat megfelel a -nak ). ${\mathbf x}$ ${\mathbf y}$ $\mathbf X$ $\mathbf Y$ $a\mathbf x+b\mathbf y$ $a\mathbf X+b\mathbf Y$

A konvolúciós kód a fa- és rácskódok speciális esete .

Eredet

1955 -ben L. M. Fink , aki akkoriban a Leningrádi Hírközlési Akadémia tanszékének vezetője volt, javasolta az első visszatérő kódot.

1959 -ben a nyugati szakember, Hegelberger ( Hegelbeger ), akinek fogalma sem volt a szovjet tudósok kódolási munkásságáról, 1959-ben "újrafelfedezte" a visszatérő kódot, és elnevezte magáról.

Fink a „Theory of Discrete Message Transmission” [1] című monográfiájában ezt írta: „Ebben a kódban a kódszimbólumok sorozata nincs külön kódkombinációkra osztva. A korrekciós szimbólumok az információs szimbólumfolyamban szerepelnek, így minden két információs szimbólum közé egy korrekciós szimbólum kerül. Az információs karaktereket a -n keresztül jelölve és a javító karaktereket a -n keresztül a következő karaktersorozatot kapjuk: $a_{i}$ $kettős}$

$a_{1}b_{1}\,a_{2}b_{2}\,a_{3}b_{3}\,\dots \,a_{k}b_{k}\,a_{k +1}b_{k+1}\,\pontok$

Az információs szimbólumokat a továbbított üzenet határozza meg, a javító szimbólumokat pedig a következő szabály szerint alakítják ki:

$b_{i}=\left(a_{ks}+a_{k+s+1}\right)\mod 2$ (1.1)

ahol a kódlépésnek ( ) nevezett tetszőleges egész szám. Nyilvánvaló, hogy ha valamilyen b i javító szimbólumot tévedésből kapunk, akkor a kapott sorozatban az (1.1) reláció nem teljesül . Az információs szimbólum hibás vétele esetén az (1.1) reláció nem érvényes két értékre , nevezetesen a for és for -re . Innen könnyen levezethető egy dekódolási hibajavító szabály. Az elfogadott kódsorozatban az (1.1) relációt mindegyikre ellenőrzi. Ha nem elégedett két értékkel ( és ), és egyidejűleg $s$ $s=0,1,2\dots$ $i=k$ $a_{i}$ $k_i$ $k_{1}=is-1$ $k_{2}=i+s$ $b_{k}$ $k$ ${\displaystyle k=k_{1))$ $k=k_{2}$

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

akkor az információs elemet meg kell fordítani. $a_{k_{1}+s+1}$

Nyilvánvaló, hogy a kód redundancia . Lehetővé teszi az összes hibásan fogadott karakter javítását, kivéve néhány rossz kombinációt. Tehát, ha , akkor helyes dekódolást biztosít, ha legalább három (és bizonyos esetekben kettő) helyesen vett szimbólum van két hibásan vett szimbólum között (az információt és a tesztszimbólumot is figyelembe veszik). $1/2$ $s=0$

A nem rekurzív kódoló általános sémája

A nem rekurzív konvolúciós kód kódoló diagramja az 1. ábrán látható . Hosszúságú -ary shift regiszterekből áll . Egyes memóriacellák egyes (talán az összes) regiszterbemenetei és kimenetei több modulo adderhez csatlakoznak . Az összeadók száma nagyobb, mint a műszakregiszterek száma: $k$ $q$ $m_1. m_2,...,m_k$ $n$ $q$ $n>k$

A kódoló minden órajelciklusánál információs szimbólumok kerülnek a bemenetére, amelyek a váltásregiszterekben tárolt szimbólumokkal együtt azon összeadók bemeneteire kerülnek, amelyekkel kapcsolat van. Az összeadás eredményeként átvitelre kész kódszimbólumok jönnek létre. Ekkor minden eltolási regiszterben eltolás történik: az összes cellát egy bittel jobbra toljuk, miközben a bal szélső cellákat kitöltjük bemeneti karakterekkel, a jobb szélső cellákat pedig töröljük. Ezt követően az ütem megismétlődik. A regiszterek kezdeti állapota előre ismert (általában nulla). $k$ $n$

Az összes műszakregiszter teljes hosszát kódhatárnak , a maximális hosszt pedig késleltetésnek nevezzük . $m = \sum_{i=1}^k m_i$ $w = \max\{m_1,...,m_k\}$

Az eltolási regiszterek értékeit minden időpontban a kódoló állapotának nevezzük.

Bináris konvolúciós kódolók

A bemutatás érthetősége érdekében leírjuk a konvolúciós kódolást a megfelelő kódolóeszköz működése szerint.

A konvolúciós kódoló olyan eszköz, amely általában k bemeneti információszimbólumot fogad minden egyes műveleti ciklusban, és n kimeneti szimbólumot ad ki minden egyes ciklus kimenetén. A számot relatív kódsebességnek nevezzük. k az információs szimbólumok száma, n a kommunikációs csatornára továbbított szimbólumok száma az információszimbólum kódolójához való megérkezés egy ciklusában. A vizsgált ciklus kimeneti szimbólumai m darab információszimbólumtól függenek, amelyek ebben és az előző ciklusban érkeznek, vagyis a konvolúciós kód kimeneti szimbólumait a bemeneti szimbólumok és az állapot, amely m - k korábbi információszimbólumtól függ, egyedileg határozza meg. . A konvolúciós kód fő elemei: shift regiszter, modulo 2 összeadó, kommutátor. $R={\frac {k}{n}}$

A shift regiszter egy dinamikus tárolóeszköz, amely a 0 és 1 bináris karaktereket tárolja. A kódmemória határozza meg az m trigger cellák számát a shift regiszterben. Amikor egy új információs karakter érkezik a shift regiszter bemenetére, a jobb szélső bitben tárolt karakter törlődik a regiszterből és visszaáll. A fennmaradó karakterek egy számjeggyel jobbra kerülnek, így a bal szélső számjegy felszabadul, ahová az új információs karakter érkezik.

A modulo 2 összeadó összeadja a hozzá érkező 1-es és 0-s szimbólumokat.A modulo 2 összeadási szabálya a következő: a bináris szimbólumok összege 0, ha a bemenetekre érkező szimbólumok között páros az egyesek száma, és 1-gyel egyenlő, ha ez a szám furcsa.

A kapcsoló szekvenciálisan olvassa be a bemeneteire érkező szimbólumokat, és a kimeneten beállítja a kódszimbólumok sorozatát a kommunikációs csatornába. A blokkkódokhoz hasonlóan a konvolúciós kódok szisztematikus és nem szisztematikus kódokra oszthatók.

A szisztematikus konvolúciós kód olyan kód, amely a kimeneti kódszimbólum-sorozatában tartalmazza az azt generáló információs szimbólumok sorozatát. Ellenkező esetben a kódot nem szisztematikusnak nevezik.

Konvolúciós kódok paraméterei és jellemzői

A konvolúciós kódolással az információsorozatok kimeneti és kódsorozatokká történő átalakítása folyamatosan történik. A bináris konvolúciós kódoló egy m bites eltolási regisztert és modulo 2 összeadókat tartalmaz, amelyek kódszimbólumokat generálnak a kimeneti sorozatban. Az összeadók bemenetei a regiszter bizonyos bitjeihez kapcsolódnak. A kimeneti kapcsoló határozza meg a kódszimbólumok kommunikációs csatornára való küldésének sorrendjét. Ezután a kódszerkezetet a következő jellemzők határozzák meg.

Az egy ciklus alatt a kódoló bemenetére érkező információs szimbólumok száma k.
A kódoló kimenetén a szimbólumok száma n, ami megfelel a ciklus alatti k bemeneti szimbólumnak.
A kódsebességet az R=k/n arány határozza meg, és a kódolás során bevezetett redundanciát jellemzi.
Kód redundancia $\vartheta = 1 - R$
A kódmemóriát (a kódkényszer bemeneti hosszát vagy a kódszó információhosszát) a generáló polinom maximális foka határozza meg a G(X) generáló mátrixban: $l = k \underset{i,j}{\max} \mathcal {b} \deg g _{i,j}(x)+1 \mathcal {c}$
A konvolúciós kód jelölését a legtöbb esetben jelöljük (n, k, l), de lehetségesek a variációk.
A bináris kódsorozatok w súlyát az ebben a sorozatban vagy kódszavakban található "egységek" száma határozza meg.
A kódtávolság az i-edik és a j-edik kódkombinációk közötti különbség mértékét mutatja, feltéve, hogy azonos hosszúságúak. Bármely két bináris kódkombináció esetén a kód távolsága megegyezik a nem egyező karakterek számával. Általában a kódtávolság a kódkombinációk azonos nevű bitjeinek modulo 2 összeadásának teljes eredményeként definiálható , ahol és az i és j kódkombinációk k-edik szimbólumai; L a kódkombináció hossza. $d$
$d_{i,j} = \sum_{k=1}^L k_{i,k} \oplus k_{j,k}$ $k_{i,j}$ $k_{jk}$
A minimális kódtávolság az állandó hosszúságú kódszavak halmazának legkisebb Hamming-távolsága . Ennek megtalálásához fel kell sorolni az összes lehetséges kódkombinációpárt. Akkor kapunk . $d_{min}$ $d_{min} = \min d_{ij}$

De! Ez a meghatározás állandó hosszúságú blokkkódokra érvényes. A konvolúciós kódok folytonosak, és sok minimális távolság jellemzi őket, amelyeket a kódsorozatok kezdeti szegmenseinek hossza határozza meg, amelyek között a minimális távolságot veszik. A feldolgozásra kapott L szegmenshosszúságú szimbólumok száma határozza meg a vevő oldalon a dekóderben lévő cellák számát.

Egy bináris konvolúciós kódoló általános nézete

Legyen a shift regiszterben m cella, vagyis a kódmemória egyenlő m-mel, a kapcsoló egy lekérdezési ciklust hajt végre, átadva az információs szimbólumok értékeit, ahol m a k többszöröse , míg egy ciklusban lekérdezi n -et 2 kódoló kimenet. Az egy bemeneti információs szimbólum változása által érintett kimeneti kódszimbólumok száma . Az I all értéket a kódkényszer teljes hosszának nevezzük . $1\le k<m$ $\geq$ $I_{all}=\frac{mn}{k}$

Mivel egy adott konvolúciós kód korrekciós tulajdonságait a kódkényszer hossza és az eltolási regiszter és a modulo 2 összeadó ( XOR ) hivatkozásainak megválasztása határozza meg, ezért a konvolúciós kódoló szerkezetének megadásához szükséges adja meg, hogy a shift regiszter mely bitjei legyenek társítva az egyes modulo 2 összeadókhoz ( XOR ).

A j-edik összeadó modulo 2 kapcsolatát a j-edik generáló szekvencia írja le:

g j =(g j0 , g j1 ,g j2 ,…,g jm-1 ), (4.1)

ahol (4.2) $g_{ij} = \begin{cases} 1,&\text{ha a regiszter i. szakasza össze van kötve az XOR kapuval}\\ 0,&\text{egyéb esetekben} \end{cases}$

A konvolúciós kódok jellemző paraméterei: k, n= 1,2,…,8; R=k/n=1/4,…,7/8; m=2,…,10.

Konvolúciós kódok beállítási módja

Kényelmes konvolúciós kódot megadni polinomok generálásával, amelyeket a (4.1) képlet alakja határoz meg, analóg módon, ahogyan ez lineáris blokkciklikus kódoknál történik . [2]

A generátorpolinom teljes mértékben meghatározza a konvolúciós kód bináris kódolójának szerkezetét. Ellentétben a blokkkódokkal , amelyek mindegyikét csak egy generáló polinom írja le, a konvolúciós kódot több generáló polinom ír le. A konvolúciós kódot leíró polinomok számát az n kimeneti szimbólumok száma határozza meg . A kódoló bemenetére érkező információs szimbólumok sorozatát ábrázoljuk polinomként

A(X)=a_{0}+a_{1}X+a_{2}X^{2}+\pontok ,

ahol X i az eltolási regiszter i ciklusának késleltetési operátorának szimbóluma , és i = {0, 1} információs bináris szimbólumok. A kódolókapcsoló bemenetére, majd a kommunikációs csatornára belépő n kódszimbólum-sorozatot leíró polinomok alakja

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

ahol bináris kód szimbólumok vannak a kódoló kapcsoló j -edik bemenetén. $b_{i}^{j}=\left\{{0;1}\right\}$

A konvolúciós kód j - edik generáló polinomja alakja Ráadásul a konvolúciós kód linearitása és az elfogadott jelölés miatt azt kapjuk, hogy . ${\displaystyle G_{j}(X)=g_{0}+g_{1}X+g_{2}X^{2}+\pontok +g_{m-1}X^{m-1))$ $g_{i}={0;1}$ $B_j(X) = G_j(X) A(X)$

Egy konvolúciós kód polinomok generálásával történő reprezentációjával konvolúciós kód adható meg a bináris vagy oktális formában írt polinomok generálásának együtthatóinak sorozataival. Az oktális jelölés kompaktabb, és akkor használatos, ha a kódoló eltolási regisztere hosszú.

Általános esetben a j -edik generáló polinom együtthatósorozatának alakja és egybeesik a kód generáló sorozatával (4.1). Ekkor, ha kódolt szimbólumok sorozata, és kódszimbólumok sorozata a kódolókapcsoló j -edik bemenetén, akkor bármelyik -edik időpontban megjelenő ( ) esetén írhatjuk $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},\pontok ))$ $\mu$ $\mu =0,1,2,\pontok$

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

Így a konvolúciós kód kódolójának kimeneti sorozatának minden kódszimbólumát a kódolt információ és a generáló szekvencia konvolúciója határozza meg, amely meghatározza a konvolúciós kódok nevét. A konvolúciós kódok az iteratív vagy ismétlődő kódok speciális esetei.

Alkalmazás

Konvolúciós kódokat használnak a megbízható adatátvitelhez: videó, mobil kommunikáció, műholdas kommunikáció. A Reed-Solomon kóddal és más hasonló kódokkal együtt használatosak. A turbókódok feltalálása előtt ezek a tervek voltak a leghatékonyabbak, és kielégítik Shannon korlátait. Ezenkívül a 802.11a protokollban konvolúciós kódolást használnak a fizikai MAC rétegen, hogy egyenletes 0 és 1 eloszlást érjenek el, miután a jel áthalad a kódolón , aminek eredményeként a továbbított szimbólumok száma megduplázódik, és ezért kedvező vételt érhet el a vevőkészüléken.

Lásd még

Jegyzetek

↑ Fink L. M. A diszkrét üzenetek továbbításának elmélete
↑ Sagalovich, 2014 , 4. és 5. fejezet.

Irodalom

Gallagher R. Információelmélet és megbízható kommunikáció. - M . : Szovjet rádió, 1974. - 720 p.
Morelos-Zaragoza R. A hibajavító kódolás művészete. Módszerek, algoritmusok, alkalmazás / per. angolról. V. B. Afanasjev . - M . : Technosfera, 2006. - 320 p. — (A kommunikáció világa). - 2000 példányban. — ISBN 5-94836-035-0 .
Fink L. M. A diszkrét üzenetek továbbításának elmélete. - M . : Szov. rádió, 1963. - 576 p.
Nikitin G.I. Konvolúciós kódok: Tankönyv. - Szentpétervár. : Baglyok. rádió, 2001. - 78 p.
Sagalovich Yu. L. Bevezetés az algebrai kódokba - 3. kiadás, átdolgozva. és további - M. : IPPI RAN , 2014. - 310 p. — ISBN 978-5-901158-24-1
Nikitin G.I. Konvolúciós kódok bemutatója
Bankett, VL "Jelkód konstrukciók távközlési rendszerekben." V: Főnix (2009).
Kolesnik VD, Poltyrev G. Sh. Információelmélet tanfolyam. - „Tudomány”, fejezet. szerk. fizikai és matematikai irodalom, 1982.
Ngok DK Optimális konvolúciós és perforált konvolúciós kódok keresési módszereinek vizsgálata : dis. – Értekezés a műszaki tudományok kandidátusi fokozatához. Szentpétervár: LETI, 2014.

Szótárak és enciklopédiák	nagy kínai Britannica (online)