SECVENTE PSEUDOALEATOARE

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

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 . 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 a si b sunt doua secvente de iesire ale unui generator liniar, atunci si (a) + (b)(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.

1.4. Ecuatia caracteristica si polinomul caracteristic

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

determinantului

Polinomul caracteristic este definit prin:

1.5. Functia generatoare

Se obtine pentru functia generatoare 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

II. CODURI PSEUDOALEATOARE SI CODURI GLOD

Coduri Pseudoaleatoare.

Pentru polinomul generator sa se scrie matricea generatoare

Considerand starea initiala x0=[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

PN=[1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0]

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

>> cb=2*c-1;

cb

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)=cb*c1'/31; end

R=[0.4839 -0.0323 -0.5484 -0.9355 -0.4194 0.0968 0.6129 0.8710 0.3548 -0.1613 -0.6774 -0.8065 -0.2903 0.2258 0.7419 0.7419 0.2258 -0.2903 -0.8065 -0.6774 -0.1613 0.3548 0.8710 0.6129 0.0968 -0.4194 -0.9355 -0.5484 -0.0323 0.4839 1.0000]

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

In figura de mai jos avem prezentata functia de autocorelatie rezultata:

OBS: Se poate observa faptul ca functia de autocorelatie prezinta minime si maxime.

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)=cb(1:5)*c1(1:5)'/5; end; stem(r5)

r5    r10 r15 r20 r25

0.2000 0.3000 0.2000 0.1000 0.1200

-0.6000 0.1000 0.0667 0 -0.0400

-1.0000 -0.3000 -0.0667 -0.1000 -0.1200

-0.6000 -0.5000 -0.3333 -0.3000 -0.2000

0.2000 -0.3000 -0.2000 -0.1000 -0.1200

0.6000 0.1000 -0.0667 0 0.0400

1.0000 0.5000 0.0667 0.1000 0.1200

0.6000 0.3000 0.3333 0.3000 0.2000

-0.2000 0.1000 0.2000 0.1000 0.1200

-0.6000 -0.3000 0.0667 0 -0.0400

-1.0000 -0.5000 -0.2000 -0.1000 -0.1200

-0.6000 -0.3000 -0.2000 -0.3000 -0.2000

0.6000 0.3000 0.0667 0 0.0400

1.0000 0.5000 0.3333 0.2000 0.1200

0.6000 0.3000 0.2000 0.2000 0.2000

-0.2000 0.1000 0.0667 0 0.1200

-0.6000 -0.3000 -0.0667 -0.1000 -0.0400

-1.0000 -0.5000 -0.3333 -0.3000 -0.1200

-0.6000 -0.3000 -0.2000 -0.1000 -0.2000

0.2000 -0.1000 -0.0667 0 -0.0400

0.6000 0.3000 0.0667 0.1000 0.1200

1.0000 0.5000 0.3333 0.3000 0.2000

0.6000 0.3000 0.2000 0.1000 0.1200

-0.2000 0.1000 0.0667 0 -0.0400

-0.6000 -0.3000 -0.0667 -0.1000 -0.1200

-1.0000 -0.5000 -0.3333 -0.3000 -0.2000

-0.6000 -0.3000 -0.2000 -0.1000 -0.1200

0.2000 -0.1000 -0.0667 0 0.0400

0.6000 0.3000 0.0667 0.1000 0.1200

1.0000 0.5000 0.3333 0.3000 0.2000

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

Figurile de mai jos prezinta reprezentarile grafice ale functiilor de corelatie partiale r5--r25.

OBS: Din figura de mai sus se observa faptul ca:

functiile partiale de corelatie pastreaza caracterul de alternanta a minimelor cu maximelor.

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)

g=[0 1 1 1 0 1 1 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 0 0 1 0 0 0 1 0]

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 ?

Valorile functiei de autocorelatie rezultate in urma calculelor sunt cele de mai jos

Rg=[0.1935 0.3226 0.1935 0.4516 0.1935 0.2903 0.1935 0.3871 0.1935 0.2581 0.1935 0.3226 0.1935 0.2258 0.2581 0.2581 0.2258 0.1935 0.3226 0.1935 0.2581 0.1935 0.3871 0.1935 0.2903 0.1935 0.4516 0.1935 0.3226 0.1935 0.5161]

In figura de mai jos prezentam graficul functiei de autocorelatie rezultata:

Numarul de niveluri ale functiei de autocorelatie a codului Gold este dupa cum reiese din figura de mai sus de: 5 sau 6 daca luam in seama si ultimul punct din reprezentarea grafica.

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.

Utilizand algoritmul pentru calculul codului Gold am determinat inca 3 coduri Gold din familia acestora dupa cum se vede pe urmatoarele 3 coloane:

0 0

1 1 0

1 1 0

1 1 0

0 0 0

1 1 0

1 0 1

1 1 0

0 0 0

1 0 1

1 0 1

1 1 0

0 1 1

1 0 1

0 1 1

1 0 1

0 1 1

1 0 1

0 0 0

1 0 1

0 1 1

1 1 0

0 0 0

0 1 1

0 1 1

1 1 0

0 0 0

0 1 1

0 0 0

1 1 0

0 0 0

In mod similar putem determina si cele 3 functii de autocorelatie corespunzatoare dupa cum urmeaza:

Rg Rg Rg

In ceea ce priveste reprezentarile grafice ale celor 3 functii de autocorelatie obtinem urmatoarea figura.

Intercorelatie

c&cd cd&cdc c&cdc

O reprezentare grafica a celor mentiuonate mai sus vedem in figura de mai jos:

OBS: Se observa faptul ca toate cele 3 functii de intercorelatie prezinta alternata minimelor si a maximelor}.