Cod de convoluție

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 27 septembrie 2018; verificările necesită 8 modificări .

Un cod convoluțional este un cod de corectare a erorilor în care

la fiecare ciclu de ceas al codificatorului, simbolurile secvenței semi-infinite de intrare sunt convertite în simboluri ale secvenței de ieșire $k$ $n>k$
personajele anterioare sunt de asemenea implicate în conversie $m$
proprietatea liniarității este îndeplinită (dacă două secvențe codificate și corespund secvențelor de cod și , atunci secvența codificată corespunde cu ). ${\mathbf x}$ ${\mathbf y}$ $\mathbf X$ $\mathbf Y$ $a\mathbf x+b\mathbf y$ $a\mathbf X+b\mathbf Y$

Un cod convoluțional este un caz special de coduri de arbore și spalier .

Origini

În 1955, L. M. Fink , care la acea vreme era șeful departamentului Academiei de Comunicații din Leningrad, a propus primul cod recurent.

În 1959, specialistul occidental Hegelberger ( Hegelbeger ), care habar n-avea despre munca oamenilor de știință sovietici în domeniul codificării, a „redescoperit” codul recurent și l-a numit după sine.

Fink însuși în monografia sa „Theory of Discrete Message Transmission” [1] a scris: „În acest cod, succesiunea simbolurilor de cod nu este împărțită în combinații separate de cod. Simbolurile de corecție sunt incluse în fluxul de simboluri de informații, astfel încât câte un simbol de corecție este plasat între fiecare două simboluri de informații. Notând caractere informaționale prin , și corective prin obținem următoarea secvență de caractere: $a_{i}$ $b_{i}$

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

Simbolurile informaționale sunt determinate de mesajul transmis, iar simbolurile corective sunt formate conform următoarei reguli:

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

unde este un număr întreg arbitrar numit pas de cod ( ). Evident, dacă un simbol corectiv b i este primit din greșeală, relația (1.1) din secvența primită nu va fi satisfăcută pentru . În cazul recepționării eronate a simbolului informațional, relația (1.1) nu va fi valabilă pentru două valori ale lui , și anume, pentru și pentru . De aici este ușor să derivați o regulă de corectare a erorilor de decodare. În secvența de cod acceptată , relația (1.1) este verificată pentru fiecare . Dacă nu este mulțumit cu două valori ( și ), și în același timp $s$ $s=0,1,2\dots$ $i=k$ $a_{i}$ $k_i$ $k_{1}=este-1$ $k_{2}=i+s$ $b_{k}$ $k$ $k=k_{1}$ $k=k_{2}$

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

atunci elementul de informare trebuie inversat. $a_{k_{1}+s+1}$

Evident, redundanța codului este . Vă permite să corectați toate caracterele primite eronat, cu excepția unor combinații proaste. Deci, dacă , oferă decodarea corectă atunci când există cel puțin trei (și în unele cazuri două) simboluri recepționate corect între două simboluri primite eronat (se iau în considerare atât simbolurile de informare, cât și simbolurile de testare). $1/2$ $s=0$

Schema generală a unui codificator nerecursiv

Diagrama codificatorului unui cod convoluțional nerecursiv este prezentată în Fig.1 . Este format din registre de deplasare -ari cu lungimi . Unele (poate toate) intrările și ieșirile de registru ale unor celule de memorie sunt conectate la mai multe sumatoare modulo . Numărul de sumatori este mai mare decât numărul de registre de deplasare: $k$ $q$ $m_1. m_2,...,m_k$ $n$ $q$ $n>k$

La fiecare ciclu de ceas al codificatorului, la intrarea acestuia sunt furnizate simboluri informative, acestea, împreună cu simbolurile stocate în registrele de deplasare, sunt alimentate la intrările acelor sumatori cu care există o conexiune. Rezultatul adăugării sunt simboluri de cod gata de transmisie. Apoi are loc o deplasare în fiecare registru de deplasare: toate celulele sunt deplasate la dreapta cu un bit, în timp ce celulele din stânga sunt umplute cu caractere de intrare, iar celulele din dreapta sunt șterse. După aceea, ritmul se repetă. Starea inițială a registrelor este cunoscută dinainte (de obicei zero). $k$ $n$

Lungimea totală a tuturor registrelor de deplasare se numește limită de cod , iar lungimea maximă se numește întârziere . $m = \sum_{i=1}^k m_i$ $w = \max\{m_1,...,m_k\}$

Valorile registrelor de deplasare în fiecare moment se numesc starea codificatorului.

Codificatori binari convoluționali

Pentru claritatea prezentării, vom descrie codarea convoluțională în funcție de acțiunea dispozitivului de codificare corespunzător.

Un encoder convoluțional este un dispozitiv care primește în general k simboluri de informații de intrare la fiecare ciclu de funcționare și emite n simboluri de ieșire la ieșirea fiecărui ciclu. Numărul se numește rata de cod relativă. k este numărul de simboluri de informare, n este numărul de simboluri transmise canalului de comunicație într-un ciclu de sosire la codificatorul simbolului de informații. Simbolurile de ieșire ale ciclului luat în considerare depind de m simboluri de informații care ajung la ciclul acesta și anterioare, adică simbolurile de ieșire ale codului convoluțional sunt determinate în mod unic de simbolurile sale de intrare și starea, care depinde de m - k simboluri de informații anterioare. . Elementele principale ale codului convoluțional sunt: registrul de deplasare, sumatorul modulo 2, comutatorul. $R={\frac {k}{n}}$

Registrul de deplasare este un dispozitiv de stocare dinamic care stochează caracterele binare 0 și 1. Memoria de coduri determină numărul de celule de declanșare m din registrul de deplasare. Când un nou caracter de informare ajunge la intrarea registrului de deplasare, caracterul stocat în bitul din dreapta este eliminat din registru și resetat. Caracterele rămase sunt mutate cu o cifră la dreapta și, astfel, cifra din stânga este eliberată, unde va ajunge noul caracter de informare.

Adunatorul modulo 2 adaugă simbolurile 1 și 0 care ajung la el. Regula de adunare modulo 2 este următoarea: suma simbolurilor binare este 0 dacă numărul unu dintre simbolurile care intră în intrări este par și este egal cu 1 dacă acest număr este ciudat.

Comutatorul citește secvențial simbolurile care ajung la intrările sale și setează secvența simbolurilor codului în canalul de comunicație de la ieșire. Prin analogie cu codurile bloc, codurile convoluționale pot fi clasificate în sistematice și nesistematice.

Un cod convoluțional sistematic este un cod care conține în secvența sa de ieșire de simboluri de cod secvența de simboluri de informații care l-a generat. În caz contrar, codul se numește nesistematic.

Parametrii și caracteristicile codurilor convoluționale

Cu codificarea convoluțională, transformarea secvențelor de informații în secvențe de ieșire și de cod are loc continuu. Codificatorul binar convoluțional conține un registru de deplasare de m biți și sumatori modulo 2 pentru a genera simboluri de cod în secvența de ieșire. Intrările sumatoarelor sunt conectate la anumiți biți ai registrului. Comutatorul de ieșire determină ordinea în care simbolurile de cod sunt trimise către canalul de comunicație. Apoi, structura codului este determinată de următoarele caracteristici.

Numărul de simboluri informaționale care ajung la intrarea codificatorului într-un ciclu este k.
Numărul de simboluri la ieșirea codificatorului este n, corespunzător celor k simboluri de intrare în timpul ciclului.
Rata de codificare este determinată de raportul R=k/n și caracterizează redundanța introdusă în timpul codificării.
Redundanța codului $\vartheta = 1 - R$
Memoria de cod (lungimea de intrare a constrângerii de cod sau lungimea informației a cuvântului de cod) este determinată de gradul maxim al polinomului generator din matricea generatoare G(X): $l = k \underset{i,j}{\max} \mathcal {b} \deg g _{i,j}(x)+1 \mathcal {c}$
Marcarea codului convoluțional se notează în majoritatea cazurilor (n, k, l), dar sunt posibile variații.
Greutatea w a secvențelor de cod binar este determinată de numărul de „unități” incluse în această secvență sau cuvinte de cod.
Distanța codului arată gradul de diferență dintre combinațiile de cod i-a și j-a, cu condiția ca acestea să fie de aceeași lungime. Pentru oricare două combinații de cod binar, distanța codului este egală cu numărul de caractere care nu se potrivesc în ele. În general, distanța de cod poate fi definită ca rezultatul total al adunării modulo 2 a biților cu același nume ai combinațiilor de cod , unde și sunt simbolurile k-ale ale combinațiilor de cod i și j; L este lungimea combinației de coduri. $d$
$d_{i,j} = \sum_{k=1}^L k_{i,k} \oplus k_{j,k}$ $k_{i,j}$ $k_{jk}$
Distanța minimă de cod este cea mai mică distanță Hamming pentru un set de cuvinte de cod de lungime constantă. Pentru a-l găsi, este necesar să enumerați toate perechile posibile de combinații de cod. Apoi primim . $d_{min}$ $d_{min} = \min d_{ij}$

Dar! Această definiție este valabilă pentru codurile bloc cu lungime constantă. Codurile convoluționale sunt continue și se caracterizează prin multe distanțe minime determinate de lungimile segmentelor inițiale ale secvențelor de cod, între care se ia distanța minimă. Numărul de simboluri din lungimea segmentului L primite pentru procesare determină, pe partea de recepție, numărul de celule din decodor.

Vedere generală a unui codificator binar convoluțional

Fie ca registrul de deplasare să conțină m celule, adică memoria de cod este egală cu m, comutatorul efectuează un ciclu de interogare, trecând valorile simbolurilor informaționale, unde m este un multiplu al lui k , în timp ce într-un ciclu interogează n 2 iesiri encoder. Numărul de simboluri de cod de ieșire afectate de o modificare a unui simbol de informații de intrare este . Valoarea I all se numește lungimea totală a constrângerii de cod . $1\le k<m$ $\geq$ $I_{toate}=\frac{mn}{k}$

Deoarece proprietățile corective ale unui anumit cod convoluțional sunt determinate de lungimea constrângerii codului și de alegerea legăturilor registrului de deplasare la sumatorul modulo 2 ( XOR ), atunci pentru a specifica structura codificatorului convoluțional , este necesar să se specificați ce biți ai registrului de deplasare sunt asociați cu fiecare dintre sumatorii modulo 2 ( XOR ).

Conexiunea j-lea sumator modulo 2 este descrisă de j-a secvență generatoare:

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

unde (4.2) $g_{ij} = \begin{cases} 1,&\text{dacă etapa i a registrului este legată de poarta XOR}\\ 0,&\text{în alte cazuri} \end{cases}$

Parametri tipici ai codurilor convoluționale: k, n= 1,2,…,8; R=k/n=1/4,…,7/8; m=2,…,10.

Metoda de setare a codurilor convoluționale

Este convenabil să specificați un cod convoluțional utilizând polinoame generatoare, care sunt determinate de forma formulei (4.1) prin analogie cu modul în care se face acest lucru pentru codurile ciclice de bloc liniare . [2]

Polinomul generator definește complet structura codificatorului binar al codului convoluțional. Spre deosebire de codurile bloc , fiecare dintre acestea fiind descris de un singur polinom generator , un cod convoluțional este descris de mai multe polinoame generatoare. Numărul de polinoame care descriu codul convoluțional este determinat de numărul de simboluri de ieșire n . Să reprezentăm secvența simbolurilor informaționale care vin la intrarea codificatorului ca un polinom

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

unde X i este simbolul operatorului de întârziere pentru i cicluri ale registrului de deplasare și i = {0, 1} sunt simboluri binare informaționale. Polinoamele care descriu n secvențe de simboluri de cod care intră în intrarea comutatorului codificatorului și apoi în canalul de comunicație au forma

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

unde sunt simboluri de cod binar la intrarea j -a a comutatorului codificatorului. $b_{i}^{j}=\stanga\{{0;1}\dreapta\)$

Polinomul generator j - al codului convoluțional are forma Mai mult, datorită liniarității codului convoluțional și a notației acceptate, obținem . ${\displaystyle G_{j}(X)=g_{0}+g_{1}X+g_{2}X^{2}+\dots +g_{m-1}X^{m-1))$ $g_{i}={0;1}$ $B_j(X) = G_j(X) A(X)$

Folosind reprezentarea unui cod convoluțional folosind polinoame generatoare, se poate specifica un cod convoluțional prin intermediul unor secvențe de coeficienți ai polinoamelor generatoare scrise în formă binară sau octală. Notația octală este mai compactă și este utilizată atunci când registrul de deplasare al codificatorului este lung.

În cazul general, șirul de coeficienți al celui de-al j -lea polinom generator va avea forma și coincide cu șirul generator de cod (4.1). Atunci, dacă este o secvență de simboluri codificate și este o secvență de simboluri cod la intrarea j -a a comutatorului codificatorului, atunci pentru oricare dintre ele care apar la a -lea moment ( ), putem scrie $G^{j}={g_{0}^{j},g_{1}^{j},\dots,g_{m-1}^{j))$ ${\displaystyle A={a_{0},a_{1},a_{2},\dots ))$ ${\displaystyle B_{j}={b_{0}^{j},b_{1}^{j},b_{2}^{j},\dots ))$ $\mu$ $\mu =0,1,2,\dots$

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

Astfel, fiecare simbol de cod al secvenței de ieșire a codificatorului codului convoluțional este determinat de convoluția informațiilor codificate și secvența generatoare, care determină numele codurilor convoluționale. Codurile convoluționale sunt un caz special de coduri iterative sau recurente.

Aplicație

Codurile convoluționale sunt folosite pentru transmisia fiabilă a datelor: video, comunicații mobile, comunicații prin satelit. Ele sunt folosite împreună cu codul Reed-Solomon și alte coduri similare. Înainte de inventarea codurilor turbo , astfel de modele erau cele mai eficiente și satisface limita lui Shannon. De asemenea, codificarea convoluțională este utilizată în protocolul 802.11a la nivelul fizic MAC pentru a obține o distribuție uniformă a 0 și 1 după ce semnalul trece prin scrambler , în urma căreia numărul de simboluri transmise este dublat și, prin urmare, vom poate realiza o recepție favorabilă la dispozitivul receptor.

Vezi și

Note

↑ Fink L. M. Teoria transmiterii mesajelor discrete
↑ Sagalovici, 2014 , capitolele 4 și 5.

Literatură

Gallagher R. Teoria Informației și Comunicarea Fiabilă. - M . : Radio sovietică, 1974. - 720 p.
Morelos-Zaragoza R. Arta codificării corectoare de erori. Metode, algoritmi, aplicație / per. din engleza. V. B. Afanasiev . - M . : Technosfera, 2006. - 320 p. — (Lumea comunicării). - 2000 de exemplare. — ISBN 5-94836-035-0 .
Fink L. M. Teoria transmiterii mesajelor discrete. - M . : Sov. radio, 1963. - 576 p.
Nikitin G.I. Coduri convoluționale: manual. - Sankt Petersburg. : Bufnițe. radio, 2001. - 78 p.
Sagalovici Yu. L. Introducere în codurile algebrice - ed. a 3-a, revizuită. si suplimentare - M. : IPPI RAN , 2014. - 310 p. — ISBN 978-5-901158-24-1
Nikitin G.I. Tutorial coduri convoluționale
Banchet, VL „Construcții cu coduri de semnal în sistemele de telecomunicații”. A: Phoenix (2009).
Kolesnik VD, Poltyrev G. Sh. Curs de Teoria Informației. - „Știință”, capitol. ed. literatură fizică și matematică, 1982.
Ngok DK Investigarea metodelor de căutare pentru coduri convoluționale optime și perforate: dis. – Disertație pentru gradul de candidat în științe tehnice. Sankt Petersburg: LETI, 2014.

Dicționare și enciclopedii	mare chinezesc Britannica (online)