SECVENE PSEUDOALEATOARE

Secvene pseudoaleatoare

1.1. Notiuni introductive

Secventele pseudoaleatoare generate de generatoarele cu registri de deplasare (SRG) sunt foarte utile in multe aplicatii din domeniul comunicatiilor: accesul multiplu, codarea in transmisiunile cu spectru imprastiat, secretizarea convorbirilor, protectia la bruiaj, radare greu de detectat de catre tinta urmarita, scrambling (transformarea semnalelor vocale sau de date in semnale cu bitii '0' si '1' echiprobabili), etc.

Un SRG este format din: celule de stocare care la fiecare tact transmit la celula urmatoare bitul memorat la tactul anterior, sumatoare modulo 2 si o linie de feedback. Starile celulelor si sumatoarele modulo 2 vor determina la fiecare tact informatia din prima celula de stocare.

Daca notam fiecare celula cu unde i este numarul celulei, putem spune ca registrul de deplasare (generatorul pseudoaleator) este liniar daca functia de recursivitate (feedback) poate fi exprimata ca o suma modulo 2 din , unde sunt coeficientii de conectare ai celulelor la reteaua recursiva si pot lua valorile 0 sau 1. Vom nota functia booleana de recursivitate (cu n intrari si o iesire) cu

1.2. Proprietati ale secventelor

Un registru de deplasare produce secvente care depind de lungimea registrului, de coeficientii si de conditiile initiale. Datorita acestui fapt, este convenabil sa grupam secventele de iesire in doua categorii: cu lungime maximala, respectiv nemaximala. Secventele maximale au proprietatea ca daca registrul are celule, secventa va avea lungimea . De exemplu, pentru un registru pseudoaleator de lungime , secventa maximala va avea lungimea . (Observatie: semnalul de iesire este periodic, secventa fiind succesiunea de biti pe o perioada.

Pentru o lungime data a generatorului, coeficientii vor fi cei care vor determina daca secventa va fi sau nu maximala. Pentru secventele nemaximale, conditiile initiale vor determina care secventa din cele posibile va fi generata.

Cateva teoreme pentru recunoasterea secventelor maximale:

TEOREMA 1: Nu este posibil sa se genereze o secventa maximala daca generatorul are un numar par de coeficienti nenuli.

TEOREMA 2: Daca si sunt doua secvente de iesire ale unui generator liniar, atunci si (suma modulo 2) este o secventa de iesire a acestui generator.

TEOREMA 3: Daca o secventa maximala este adunata cu ea insasi dar deplasata cu un numar oarecare de tacte, rezultatul va fi aceeasi secventa maximala dar deplasata cu un alt numar de tacte.

1.3. Caracterizarea matematica a generatoarelor cu registru de deplasare

In continuare vom numi aceste generatoare SRG (Shift Register Generator).

Putem caracteriza actiunea unui SRG cu ajutorul unei matrici de operare si cu ajutorul unui vector n-dimensional asociat continutului registrului. Elementele acestor matrici si vectori vor fi intregii 0 si 1.

Matricea A.

Matricea A inmultita cu vectorul n-dimensional asociat registrului va determina continutul acestuia la tactul urmator. Pentru un registru cu lungimea n, matricea A va avea dimensiunea n x n. Prima linie a matricii contine coeficientii , iar sub diagonala principala vom avea o diagonala de '1'.

Daca notam cu continutul celulei i la momentul j, atunci

Rezulta ca , unde

Putem de asemenea scrie ca:

Se observa de aici ca daca (matricea unitate), atunci , deci continutul registrului este acelasi dupa 'm' shiftari. Pentru a obtine o secventa maximala (de lungime ) va trebui ca A = I. Lungimea unei secvente nemaximale va fi egala cu puterea cea mai mica pentru care

1.4. Ecuatia caracteristica si polinomul caracteristic

Pentru orice matrice n x n ecuatia caracteristica rezulta din egalarea cu zero a determinantului

Exemplu:

Pentru cazul general (o matrice A de dimensiune n x n) vom avea:

Polinomul caracteristic este definit prin:

1.5. Functia generatoare

Un element important in analiza si caracterizarea secventei de iesire este functia generatoare. Notand iesirea SRG cu unde indicele m reprezinta momentul de timp, functia generatoare este data de:

unde x este o variabila reala iar este bitul de iesire la momentul k. Starea initiala a registrului este pentru un registru n-dimensional. Exista relatia de recurenta:

Se obtine pentru G(x) expresia urmatoare:

Se observa ca in cazul in care , G(x) se reduce la:

TEOREMA 6: Daca secventa SRG are lungime maximala, polinomul sau caracteristic f(x) este ireductibil.

1.6. Secvente pseudoaleatoare

Secventele pseudoaleatoare pot fi generate cu ajutorul SRG pentru care la iesire bitii '0' si '1' au probabilitatile de aparitie egale. Pentru ca semnalul sa aiba medie nula, se emit simbolurile 1 si -1. Daca secventa are simbolurile 0 si 1, atunci definim secventa cu simbolurile 1 si -1:

Functia de autocorelatie:

, unde p este perioada secventei pseudoaleatoare.

2. DESFASURAREA LUCRARII

I. CODURI CONVOLUTIONALE; ALGORITMUL VITERBI

Fie codul convolutional descris de polinoamele

Folosind functia encode sa se codeze convolutional mesajul

Desenati diagrama trellis asociata codorului si verificati pe baza acesteia corectitudinea mesajului astfel codat.

Nota: pentru definirea functiei de transfer se reprezinta fiecare polinom in binar, apoi se foloseste reprezentarea octala.

Folositi algoritmul Vitdec pentru a decodifica mesajul. Desenati diagrama trellis si determinati metricile asociate fiecarei stari. Comparati mesajul decodat cu cel initial.

Introduceti in mesajul codat la punctul 2, 5 erori

a)     in pozitii oarecare, separate prin minim 4 biti;

b)     in bloc

Decodati folosind functia Vitdec cele doua secvente astfel obtinute si comparati semnalul decodat cu cel original. Comentati rezultatele obtinute din punct de vedere al capacitatilor de corectie ale codului.

Construiti codul punctured astfel: pornind de la semnalul codat, se elimina fiecare al 4 lea bit. Acesta este echivalent cu un cod convolutional cu rata 2/3. Desenati structura codorului aferent si diagrama trellis asociata. Comparati codorul cu cel de la punctul 1 din punct de vedere al complexitat

Decodati codul astfel obtinut folosind algorimtul Viterbi. Comentati rezultatul.

Considerati codorul cu rata 2/3 reprezentat in figura

Fig.1.

Nota: daca sunt valabile ecuatiile

atunci matricea generatoare folosita in programul encode si vitdec se scrie sub forma

dupa care se trece in forma de reprezentare octala

Pentru mesajul de la punctul 1 sa se determine cuvantul de cod obtinut folosind acest cod.

Verificati analitic cuvantul de cod obtinut

Folosind functia Vitdec decodati cuvantul de cod astfel obtinut si comparati rezultatul cu mesajul original.

Desenati diagrama trellis asociata codorului si identificati traiectoria prin aceasta, calculati metricile aferente si trasati traiectoria prin trellis parcursa de decodor.

Refaceti punctul 3 folosind codul obtinut la punctul 5. Comparati rezultatele obtinute cu mesajul initial. Ce se poate spune despre proprietatile de corectie ale acestui cod ?

Presupunem in continuare ca functia de transfer a canalului este cea reprezentata in figura 2 .

Fig.2.

Peste codul obtinut la punctul 1 se adauga un zgomot aleator distribuit uniform intre (0,1). Folosind functia vitdec sa se decodeze secventa obtinuta, sa se determina metricile si supravietuitorii si sa se vizualizeze diagrama trellis.

CODURI PSEUDOALEATOARE SI CODURI GLOD

Coduri Pseudoaleatoare.

Pentru polinomul generator sa se scrie matricea generatoare

1.1. Considerand starea initiala [1 0 0 0 0], sa se genereze secventa PN de lungime 2⁵-1, astfel

>> x=x0

>> for i=1:31, x=A*x-2*floor(A*x/2); c(i)=x(1); end

1.2. Sa se translateze secventa binara obtinuta din valori logice in valori binare

>> cb=2*c-1;

1.3. Sa se calculeze functia de autocorelatie care se obtine prin inmultirea secventei PN cu toate variantele obtinute din secventa initiala prin rotatie ciclica cu cate o pozitie, astfel

>> c1=cb;

>> for i=1:31, c1=[c1(31), c1(1:30)]; r(i)=c*c1'/31; end

1.4. Sa se vizualizeze functia de autocorelatie si sa se reprezinte grafic. Ce observati ?

1.5. Sa se determine functia de corelatie partiala a codului pe lungimea de 5,10, 15, 20, 25. Astfel, pentru o lungime de corelatie de 5 se poate folosi sintaxa

» c1=cb;

» for i=1:31, c1= c1(31), c1(1:30)]; r5(i)=c(1:5)*c1(1:5)'/5; end

» plot(r5)

1.6 Sa se reprezinte grafic functiile de corelatie partiala obtinute. Ce observatii puteti face ?

Coduri Gold

2.1. Pornind de la codul PN generat la punctul 1 sa se construiasca un cod Gold obtinut prin decimare cu 3 a secventei originale astfel:

» c3=[c,c,c];

» cd=c3(1:3:length(c3));

» g=c+cd-2*floor((c+cd)/2);

Nota: se va lucra cu codul c obtinut la punctul 1.1. (valori logice)

Sa se construiasca functia de autocorelatie a secventei Gold obtinute la punctul 2.1, astfel

» g1=gb;

» for i=1:31, g1=[g1(31), g1(1:30)]; rg(i)=gb*g1'/31; end

Sa se reprezinte grafic rezultatul obtinut si sa se comenteze rezultatul. Cate niveluri are functia de corelatie a codului Gold ?

2.3. Sa se genereze inca trei coduri Gold din familia acestora, de exemplu si sa se calculeze functiile de intercorelatie intre acestea. Comentati rezultatele obtinute.

ANEX|: polinoame ireductibile:

ATENTIE!

Graficele pt punctul II se vor face cu functia "stem" si nu "plot"!