Home - Rasfoiesc.com
Educatie Sanatate Inginerie Business Familie Hobby Legal
Doar rabdarea si perseverenta in invatare aduce rezultate bune. stiinta, numere naturale, teoreme, multimi, calcule, ecuatii, sisteme


Biologie Chimie Didactica Fizica Geografie Informatica
Istorie Literatura Matematica Psihologie

Matematica


Index » educatie » Matematica
Coduri ciclice


Coduri ciclice




Coduri ciclice

Codurile ciclice sunt coduri bloc in care cele n simboluri din cuvant sunt considerate ca fiind coeficientii unui polinom de grad n-1:

Cuvantul de cod fiind identificat cu un polinom, asupra lui se pot efectua operatii matematice mai complexe, pe langa operatia de adunare si inversa ei fiind definita si operatia de inmultire si inversa ei.

Ideea de baza a mecanismului de detectie sau corectie consta in alegerea polinoamelor divizibile cu un polinom dat g(x) ca fiind cuvinte de cod (cuvinte cu sens). Polinomul g(x) se numeste polinom generator al codului. Daca in procesul de transmisiune nu s-au introdus erori, polinomul care reprezinta cuvantul receptionat, divizat cu g(x) va da un rest nul. Daca s-au introdus erori restul va fi diferit de 0.



Existenta unui rest diferit de 0 este un criteriu pentru detectia erorilor. Daca din restul obtinut se pot trage concluzii asupra pozitiei in care s-au introdus erorile, codul permite corectarea lor.

Codul se numeste ciclic deoarece daca este un cuvant de cod, atunci si toate cuvintele de forma sunt cuvinte de cod. Cu alte cuvinte, orice permutare ciclica a unui cuvant de cod conduce tot la un cuvant de cod.

Presupunand ca numarul de simboluri dintr-un cuvant este n, rezulta ca se pot forma 2n cuvinte. Dintre acestea se considera ca 2k cuvinte sunt cuvinte de cod (cu sens). Altfel spus, obtinem m=n-k simboluri de control, servind la detectia sau corectia erorilor.

Consideram ca multimea tuturor cuvintelor (ce formeaza o algebra) este generata de un polinom p(x) de grad n de forma , iar multimea cuvintelor cu sens (ce formeaza un ideal) este generata de un polinom g(x) numit polinom generator, de grad m, de forma:

Se poate arata ca intre cele doua polinoame p(x) si g(x) exista relatia: , unde .

Orice cuvant de cod poate fi exprimat printr-o combinatie liniara a urmatorilor k vectori independenti : .

Cu alte cuvinte, un cuvant de cod se gaseste in spatiul linie al matricii generatoare G:

Polinomul g(x) de grad m a fost completat pana la gradul n-1 cu componente nule. Rezulta ca prin cunoasterea polinomului generator g(x) se determina matricea generatoare G, respectiv structura codului ciclic. Matricea generatoare G are k vectori linie liniar independenti cu care se pot forma 2k combinatii liniare, respectiv 2k cuvinte de cod.

Codarea cuvintelor de cod ca elemente in multimea cuvintelor cu sens generata de g(x)

Fie g(x) polinomul generator al codului, de grad m, si i(x) polinomul de grad k=n-m care are drept coeficienti simbolurile de informatie:

A) Determinarea simbolurilor de control folosind g(x)

Polinomul simbolurilor de control se noteaza cu :

Deci cuvantul de cod se scrie :

Impartind expresia de mai sus prin g(x) rezulta:

Termenul reprezinta termenii cuvantului de cod care contin informatia transmisa. Ultimul termen se rescrie: , unde q(x) reprezinta catul (de grad < k ), iar r(x) reprezinta restul (de grad < m) impartirii lui la g(x).

.

Astfel, polinomul simbolurilor de control se obtine prin divizarea polinomului simbolurilor de informatie multiplicat cu xm prin g(x). In acest fel se obtine un cuvant de cod SISTEMATIC.

B) Ce-a de-a doua metoda pentru determinarea simbolurilor de control se bazeaza pe introducerea matricii generatoare G definita anterior, avand k linii si n coloane. Codarea are loc cu ajutorul relatiei :

v=iG , unde i=[am am+1 am+k-1].

Codarea cuvintelor de cod cu ajutorul polinomului de control h(x)

Se pleaca de la relatia potrivit careia v(x) este multiplu de g(x):

Sau, sub forma matriceala: HvT= 0, unde matricea H are forma (m linii, n coloane):

Elementele hi sunt coeficientii polinomului completat pana la gradul n-1 cu coeficienti nuli. Matricea H are m linii liniar independente astfel incat relatia HvT= 0 este echivalenta cu m ecuatii liniare ce determina cele m simboluri de control in functie de cele k simboluri de informatie.

De asemenea, se poate arata ca GHT=HGT.

Exemplu:

Se transmit N=16 mesaje pe un canal afectat de perturbatii, utilizand un cod ciclic corector de o eroare.

Se pot determina parametrii codului: pentru a transmite 16 mesaje sunt necesari cel putin 4 biti de informatie, adica:

gradul polinomului g(x) va fi deci 3

rezulta ca polinomul p(x) va avea forma:

Polinomul generator se poate alege dintre divizorii lui p(x):

Polinomul h(x) de grad k=m-n se determina din relatia p(x)=g(x)h(x)

Remember impartirea de polinoame J :

Codarea se poate realiza fie cu matricea G fie cu matricea H:

a) codarea cu matricea G

G(k,n)=G(4,7)

Cele 16 mesaje transmise vor fi codate corespunzator, ca in tabelul de mai jos:

Nr.

I3

I4

I5

I6

I3

I4

I3+I5

I3+I4+I6

I4+I5

I5+I6

I6

0

0

0

0

0

0

0

0

0

0

0

0

1

0

0

0

1

0

0

0

1

0

1

1

2

0

0

1

0

0

0

1

0

1

1

0

3

0

0

1

1

0

0

1

1

1

0

1

4

0

1

0

0

0

1

0

1

1

0

0

5

0

1

0

1

0

1

0

0

1

1

1

6

0

1

1

0

0

1

1

1

0

1

0

7

0

1

1

1

0

1

1

0

0

0

1

8

1

0

0

0

1

0

1

1





0

0

0

9

1

0

0

1

1

0

1

0

0

1

1

10

1

0

1

0

1

0

0

1

1

1

0

11

1

0

1

1

1

0

0

0

1

0

1

12

1

1

0

0

1

1

1

0

1

0

0

13

1

1

0

1

1

1

1

1

1

1

1

14

1

1

1

0

1

1

0

0

0

1

0

15

1

1

1

1

1

1

0

1

0

0

1

b) Codarea cu matricea H

cuvantul de cod obtinut are o forma sistematica : v=[c0 c1 c2 i3 i4 i5 i6]

se foloseste relatia de codare HvT=0

Se pot determina astfel cele 16 mesaje transmise:

Nr.

C0

C1

C2

I3

I4

I5

I6

0

0

0

0

0

0

0

0

1

0

1

1

0

0

0

1

2

1

1

0

0

0

1

0

3

1

0

1

0

0

1

1

4

1

1

1

0

1

0

0

5

1

0

0

0

1

0

1

6

0

0

1

0

1

1




0

7

0

1

0

0

1

1

1

8

1

0

1

1

0

0

0

9

1

1

0

1

0

0

1

10

0

1

0

1

0

1

0

11

0

0

1

1

0

1

1

12

0

1

1

1

1

0

0

13

0

0

1

1

1

0

1

14

1

0

0

1

1

1

0

15

1

1

1

1

1

1

1

Observatie: Spatiul cuvintelor cu sens este acelasi, indiferent de modul de codare, cu H sau G, insa difera corespondenta intre secventa informationala de 4 biti si cuvintele cu sens de 7 biti. De exemplu, cuvantul [1 1 1 1 1 1 1] corespunde in primul caz secventei informationale [1 1 0 1], iar in al doilea caz secventei [1 1 1 1].

Decodarea codurilor ciclice. Formarea corectorilor

Pentru un cuvant receptionat v(x) se calculeaza corectorul :

indicele i indica tipul de eroare εi.

Se cauta intr-un tabel construit anterior corespondenta dintre corectorul zi(x) si cuvantul eroare, respectiv εi(x).

Se calculeaza v(x)=v(x)+ εi(x)

O metoda de a stabili tabelul mentionat anterior este sa se calculeze zi pe baza relatiei

pentru diversi εi(x).

Se observa ca exista un singur tip de corector zi pentru toate cuvintele eronate εi(x). Polinomul z(x) are gradul cel mult m-1, deci numarul acestor corectori este 2m. Rezulta ca din multimea configuratiilor posibile de erori, respectiv de polinoame ε(x) in numar de 2n, numai cele care pot fi puse in corespondenta biunivoca cu corectorii z(x), adica un numar de 2m configuratii de erori pot fi corectate.

Realizarea codarii si a decodarii pentru detectia erorilor prin circuite de multiplicare sau divizare

1) Codarea si decodarea prin multiplicare

v(x)=i(x)g(x) in acest caz se obtine un cod nesistematic.

Demodularea se face prin divizare:

2) Codarea si decodarea prin divizare

in acest caz se obtine un cod sistematic.

Decodarea se face ca in cazul precedent prin divizare.

Codarea prin circuite de divizare

Fie circuitul secvential urmator, care foloseste celule binare notate cu Ci si sumatoare modulo 2 interioare:

Pentru analiza circuitului vom folosi un operator de intarziere notat cu D care reprezinta intarzierea de un tact pe care o introduce o celula binara.

Daca in registru se introduc coeficientii in ordine descrescatoare a indicilor: an, an-1, ., a1, a0, care corespund polinomului : , atunci secventa aplicata la intrare utilizand operatorul D poate fi pusa sub forma :

, cu interpretarea ca simbolul a0 ajunge in prima celula de intrare dupa n tacte.

Pentru a evidentia operatia efectuata de circuit se defineste functia de transfer T ca fiind raportul dintre secventa de iesire Y si cea de intrare X:

Pentru determinarea lui T se ia un caz particular: se presupune ca la intrare se aplica g(x). Primul simbol aplicat la intrare ajunge la iesire dupa m tacte (gm=1). In acest moment Y=gmDm si la intrarea tuturor celulelor va fi simbolul 0. La tactul m+1 iesirile tuturor celulelor devin zero, deci Y=gmDm≠0 numai la tactul m, avand un singur termen:

Daca D-1 tinde la x atunci se poate afirma ca circuitul realizeaza divizarea cu g(x).

In cazul general, cand polinomul de intrare este de grad n, catul divizarii se obtine la iesirea circuitului dupa n tacte, in timp ce restul va apare stocat in registru la tactul n.

Exemplu: n=7, m=3

a)Daca se alege polinomul de intrare :

Regulile de calcul pentru succesiunea starilor (C desemneaza starea celulei la momentul anterior):

tact

IN (u)

C0

C1

C2

OUT (y)

Catul

0

0

0

0

1

1

1

0

0

0

2

1

1

1

0

0

3

1

1

1

1

0

4

0

1

1

0

1



X4

5

0

0

1

1

0

6

1

0

0

0

1

X2

7

0

0

0

0

0

8

0

0

0

0

0

Restul

X0

X1

X2

 

Catul :

Restul: 0

b)Daca se alege polinomul de intrare :

Regulile de calcul pentru succesiunea starilor :

tact

IN (u)

C0

C1

C2

OUT (y)

Catul

0

0

0

0

1

1

1

0

0

0

2

1

1

1

0

0

3

1

1

1

1

0

4

0

1

1

0

1

X4

5

0

0

1

1

0

6

0

1

0

0

1

X2

7

1

1

1

0

0

8

1

1

1

1

0

Restul

X0

X1

X2

 
Catul :

Restul:






Politica de confidentialitate


Copyright © 2019 - Toate drepturile rezervate

Matematica


Statistica


INEGALITATI SI INDUCTIA MATEMATICA
Notiuni generale despre multimi, operatii cu multimi
NUMERELE NATURALE DE LA 30 LA 100
Metoda coeficientilor nedeterminati
Functii bijective
Rezolvarea numerica a ecuatiilor diferentiale si a sistemelor de ecuatii diferentiale
Factorizarea LU
PROGRESII ARITMETICE - set de probleme
TRIUNGHIUL ISOSCEL
Forma canonica Jordan