Coduri convolutionale

Coduri convolutionale

Introducere teoretica

Parametrii unui cod convolutional sunt:

numarul de simboluri de intrare k, la un singur tact, din secventa de intrare u;

numarul de simboluri de iesire n, la un singur tact, din secventa de iesire x;

dimensiunea memoriei m.

Arhitectura codor

Un cod convolutional [n,k] poate fi implementat cu un circuit secvential care are n iesiri liniare, k intrari si m celule de memorie (de intarziere). Se mai foloseste si notatia [n,k,m].

• Pentru codul [2,1] prezentat in figura 1, definim cuvantul de cod ca o succesiune semi-infinita de simboluri de informatie si simboluri de control :

.

Constructie cod

• Fiecare drum i, care leaga o iesire de o intrare poate fi caracterizat in termenii unui polinom generator, definit ca transformata de intarziere cu o unitate a raspunsului la impuls:

unde coeficientii sunt din GF(2), iar D este variabila de intarziere cu o unitate de timp.

• Codorul este descris de setul de polinoame generatoare:

,

unde kxn este numarul total de cai ale unui codor general cu k intrari si n iesiri, [n,k].

• Matricea generatoare G, de dimensiune semi-infinita, se scrie ca fiind multimea tuturor polinoamelor generatoare ale codului convolutional:

unde matricea generatoare de baza G_b, de dimensiune o linie si nx(m+1) coloane, se obtine prin intreteserea coeficientilor polinoamelor generatoare g¹(D), g²(D), ., gⁿ(D):

.

Pentru o lungime a mesajului de intrare k₀, matricea G este de dimensiune finita, avand k₀ linii si coloane.

Codarea

• Consideram secventa de intrare u, de dimensiune k₀, scrisa polinomial si matricial:

.

Analog, secventa de iesire, de lungime n₀, este definita de relatiile:

.

Pentru a obtine polinomul de iesire, se realizeaza intreteserea:

,

operatorul D² realizand operatia de intarziere cu doua tacte.

• Pentru un cod oarecare [n,k], avem k polinoame de intrare, si n polinoame de iesire . Polinoamele generatoare pentru fiecare pereche intrare-iesire sunt .

Codarea polinomiala se face pentru fiecare iesire , calculand polinoamele intermediare :

.

In final, se va face o intretesere a coeficientilor polinoamelor intermediare:

.

Pentru a calcula polinomul de iesire din codorul [n,k] mai facem o intretesere a polinoamelor :

.

Probleme rezolvate

Problema 1. Codul [2,1] cu m=2. (curs)

Fie circuitul din figura 1 avand urmatorii parametri:

Tabel 1. Tabelul de stari pentru codorul [2,1] cu m=2

Tabelul se completeaza astfel: presupunem ca suntem in starea . Daca la intrare avem simbolul 0, simbolurile de iesire vor fi 00, conform polinoamelor generatoare, iar noua stare va fi tot . Daca la intrare aplicam simbolul 1, atunci iesirea va fi 11, iar noua stare va fi .

Cu ajutorul tabelului de stari, putem realiza diagrama fluture (vezi Figura 2), care reprezinta totalitate tranzitiilor ce se pot efectua de la momentul de timp j la momentul de timp j+1. Pentru un simbol de intrare 0, tranzitia s-a reprezentat cu linie continua, iar pentru un simbol de intrare 1, tranzitia s-a reprezentat cu linie punctata. Pe ramuri sunt trecute simbolurile de iesire din codor.

d)   Datorita caracterului periodic al diagramei fluture, putem uni nodurile din stanga cu cele din dreapta, obtinand astfel, diagrama de stare a codorului, aratata in Figura 3.b.

O alta varianta de diagrama de stare este in Figura 3.a. Am notat a/bc faptul ca tranzitia are loc daca la intrare avem simbolul a, iar la iesire din codor se obtine bc.

Diagrama trellis se obtine prin repetarea structurii diagramei fluture (din Figura 2) pentru toate momentele de timp (vezi Figura 4). La momentul 0, presupunem ca codorul se afla in starea S =00. Dupa m = 2 tranzitii, ne putem afla in orice stare din cele patru posibile. Structura de fluture se repeta de la momentul de timp 2 pana la momentul de timp k₀, dat de lungimea mesajului de intrare in codor. Dupa ce s-au codat toate simbolurile de intrare, codorul va fi adus in starea initiala, pe durata a m=2 tranzitii. Acest proces se numeste terminarea trellisului.

b)     Construiti trellisul codorului;

c)     Gasiti secventa de iesire produsa de mesajul de intrare ;

Problema 4. (rez)

Pentru codul convolutional [3,1] cu m=5 si secventele generatoare , si , calculati:

a)     Matricea generatoare G;

b)     Secventa de cod c, corespunzatoare secventei de intrare ;

c)     Desenati schema codorului. Codul este sistematic?

Problema 5. Codare, decodare Viterbi pt cod [2,1], cu K=3.

Fie un cod convolutional [2,1], avand lungimea de constrangere K = 3 si diagrama fluture din figura.

a)      Calculati polinomial si matricial secventa de iesire, daca la intrare s-a aplicat mesajul ;

b)      Folosind algoritmul de decodare Viterbi, decideti ce mesaj a fost transmis, daca s-a receptionat secventa de simboluri .