Curs Coduri Ciclice

8/3/2019 Curs Coduri Ciclice

1/10

Coduri ciclice

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

]...................[}1,0{,....................)(

1210

1

1

2

210

=

++++=

n

i

n

n

aaaavaxaxaxaaxv

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

Ideea de baza a mecanismului de detectie sau corectie consta in alegerea polinoamelordivizibile cu un polinom dat g(x) ca fiind cuvinte de cod (cuvinte cu sens). Polinomulg(x) se numestepolinom generatoral codului. Daca in procesul de transmisiune nus-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 restulobtinut se pot trage concluzii asupra pozitiei in care s-au introdus erorile, codul permitecorectarea lor.

Codul se numeste ciclic deoarece daca ]...................[ 1210 = naaaav este un cuvant

de cod, atunci si toate cuvintele de forma]...............................[

10121 ++= iniii aaaaaav 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). Altfelspus, 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 unpolinom p(x) de grad n de forma 1)( += nxxp , iar multimea cuvintelor cu sens (ceformeaza un ideal) este generata de un polinom g(x) numit polinom generator, de gradm, de forma:

m

m

m

m xgxgxgxggxg +++++=

1

1

2

210 ...........)(

Se poate arata ca intre cele doua polinoame p(x) si g(x) exista relatia:)()()( xhxgxp =

,undek

kxhxhxhhxh ++++= ............)(2

210 .

Orice cuvant de cod poate fi exprimat printr-o combinatie liniara a urmatorilor k vectoriindependenti : )(.,..........),(),(),( 12 xgxxgxxxgxg k .Cu alte cuvinte, un cuvant de cod se gaseste in spatiul linie al matricii generatoare G:


2/10

=

=

m

mm

mm

m

k gggg

gggg

gggg

gggg

xgx

xgx

xx g

xg

G

. . . . . .. . . .. . . . . . . . . .. . . . . . . . . .000

. . . . .. . . . . . . .. . . . . . . . . .. . . . . . . . . .. . . . . . . . . .. . . . . . . . . .. . . . . . . . . .

. . . . .. . . . . . . .. . . . . . . . . .. . . . . . . . . .. . . . . . . . . .. . . . . . . . . .. . . . . . . . . .

. . . . .. . . . . . . .. . . . . . . . . .. . . . . . . . . .. . . . . . . . . .. . . . . . . . . .. . . . . . . . . .

0. . .. . . . . .0. . . . . . . . . .00

0. . . .. . . . . .00. . . . . . . . . .0

0. . .. . . . . .000. . . . . . . . . .

)(

.

.

.

)(

)(

)(

210

110

110

210

1

2

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 matriceageneratoare G, respectiv structura codului ciclic. Matricea generatoare G are k vectorilinie liniar independenti cu care se pot forma 2k combinatii liniare, respectiv 2k cuvintede cod.

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

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

1

11

1

11

..........)(

..........)(

++

+

+++=

+++=

k

kmmm

k

nknkn

xaxaaxi

sauxaxaaxi

A) Determinarea simbolurilor de control folosind g(x)

Polinomul simbolurilor de control se noteaza cu :

1

1

2

210 ...............)(

++++=

m

m xaxaxaaxc


3/10

Deci cuvantul de cod se scrie : )()()( xixxcxv m+=

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

)(

)(

)(

)(

)(

xg

xix

xg

xc

xg

xv m+=

Termenul )(xixm reprezinta termenii cuvantului de cod care contin informatia

transmisa. Ultimul termen se rescrie:)(

)()(

)(

)(

xg

xrxq

xg

xixm+= , unde q(x) reprezinta catul

(de grad < k ), iar r(x) reprezinta restul (de grad < m) impartirii lui )(xixm la g(x).

)(

)()()()()()()(

)(

)(

)(

)()(

xg

xixrestxrxcxixxrxgxq

xg

xix

xg

xrxq

mm

m

==+=+= .

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

B) Ce-a de-a doua metoda pentru determinarea simbolurilor de control se bazeaza peintroducerea matricii generatoare G definita anterior, avand k linii si n coloane. Codareaare 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):

)(mod0)()()()()(

)(

1

)(

)()()()()()(

xpxhxgxqxhxv

xg

x

xg

xpxhxhxqxgxv

n

==

+===

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

=

000. . . .. . . . . . . . . .. . . . . . . . . .0. . . . . . . . .. . . . .. . . . . . . . . .

. . . . . . . .. . . . . . . . . .. . . . . . . . . .. . . . . . . . . .. . . . . . . . . .. . . . . . . . . .. . . . . . . . . .

00. . .. . . . . . . . . .. . . . .0. . . . .. . . . . . . . . .0

0. . . . .. . . . . . .. . . . . . . . . .0. . . . . . . .. . . . . . . . . .0

. . . . . . . . . .. . . . . . .. . . . . . . . . .0. . . . .. . . . . . . . . .. . . . . . . . . .0

0

021

01

0

hh

hhhh

hhh

hh

H

k

kkk

kk

k

Elementele hi sunt coeficientii polinomuluik

kxhxhxhhxh ++++= ............)(2

210

completat pana la gradul n-1 cu coeficienti nuli. Matricea H are m linii liniar


4/10

independente astfel incat relatia HvT= 0 este echivalenta cu m ecuatii liniare cedetermina 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 cicliccorector de o eroare.

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

4162 = kk

351212 =+=+++ mmkmn mm gradul polinomului g(x) va fi deci 3

743 =+=+= kmn rezulta ca polinomul p(x) va avea forma: 1)( 7 +=xxp

Polinomul generator se poate alege dintre divizorii lui p(x): 1)( 23 ++= xxxg

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

11

1)(

234

23

7

+++=

++

+= xxx

xx

xxh

Remember impartirea de polinoame :

///

1

1

1

1

1

11

23

23

245

345

356

46

234467

237

++

++

++

+++

++

++

+++++

+++

xx

xx

xxx

xxx

xxxxx

xxxxxx

xxx

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

a) codarea cu matricea G

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


5/10

],,,,,,[

1101000

0110100

0011010

0001101

][

1101000

0110100

0011010

0001101

6655464353436543 iiiiiiiiiiiiiiiii GvG

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 I60 0 0 0 0 0 0 0 0 0 0 01 0 0 0 1 0 0 0 1 0 1 12 0 0 1 0 0 0 1 0 1 1 0

3 0 0 1 1 0 0 1 1 1 0 14 0 1 0 0 0 1 0 1 1 0 05 0 1 0 1 0 1 0 0 1 1 1

6 0 1 1 0 0 1 1 1 0 1 07 0 1 1 1 0 1 1 0 0 0 1

8 1 0 0 0 1 0 1 1 0 0 09 1 0 0 1 1 0 1 0 0 1 1

10 1 0 1 0 1 0 0 1 1 1 011 1 0 1 1 1 0 0 0 1 0 1

12 1 1 0 0 1 1 1 0 1 0 013 1 1 0 1 1 1 1 1 1 1 114 1 1 1 0 1 1 0 0 0 1 015 1 1 1 1 1 1 0 1 0 0 1b) 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


6/10

++=++=

++=++=

++=

=

5434210

6545321

6432

6543210 0][

0010111

0101110

1011100

iiiiccc

iiiiicc

iiic

iiiiccc

Se pot determina astfel cele 16 mesaje transmise:

Nr. C0 C1 C2 I3 I4 I5 I60 0 0 0 0 0 0 01 0 1 1 0 0 0 12 1 1 0 0 0 1 03 1 0 1 0 0 1 14 1 1 1 0 1 0 05 1 0 0 0 1 0 16 0 0 1 0 1 1 07 0 1 0 0 1 1 1

8 1 0 1 1 0 0 09 1 1 0 1 0 0 110 0 1 0 1 0 1 011 0 0 1 1 0 1 112 0 1 1 1 1 0 013 0 0 1 1 1 0 114 1 0 0 1 1 1 015 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 cusens de 7 biti. De exemplu, cuvantul [1 1 1 1 1 1 1] corespunde in primul caz secventeiinformationale [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 :

)(

)(')(

xg

xvrestxzi = indicele i indica tipul de eroare i.


7/10

Se cauta intr-un tabel construit anterior corespondenta dintre corectorul zi(x) si cuvantuleroare, 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

)(

)()(

xg

xrestxz ii

= 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. Rezultaca din multimea configuratiilor posibile de erori, respectiv de polinoame (x) in numarde 2n, numai cele care pot fi puse in corespondenta biunivoca cu corectorii z(x), adica unnumar de 2m configuratii de erori pot fi corectate.

Realizarea codarii si a decodarii pentru detectia erorilor prin circuite demultiplicare 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:)(

)(')(

xg

xvrestxz =

2) Codarea si decodarea prin divizare

)()(

)()( xix

xg

xixrestxv m

m

+= 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:

C0 Cm-1Cm-2C1X

g0 g1 g2 gm-2 gm-1 gm

.

m

m

m

mxgxgxgxggxg +++++=

1

1

2

210...........)(


8/10

Pentru analiza circuitului vom folosi un operator de intarziere notat cu D care reprezintaintarzierea de un tactpe 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 : 02

2

1

1 ............ axaxaxan

n

n

n

n

n ++++

, atunci

secventa aplicata la intrare utilizand operatorul D poate fi pusa sub forma :

n

nnnDaDaDaDa 0

2

2

1

1

0 ............ ++++ , 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:X

YT =

Pentru determinarea lui T se ia un caz particular: se presupune ca la intrare se aplicag(x). Primul simbol aplicat la intrare ajunge la iesire dupa m tacte (gm=1). In acestmoment Y=gmDm si la intrarea tuturor celulelor va fi simbolul 0. La tactul m+1 iesirile

tuturor celulelor devin zero, deci Y=gmDm0 numai la tactul m, avand un singur termen:

m

m

m

mmm

m

m

DggDgDgDgDg

Dg

X

YT

++

=

++++

==

...........

1

............ 002

2

1

1

0

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 laiesirea circuitului dupa n tacte, in timp ce restul va apare stocat in registru la tactul n.

Exemplu: n=7, m=3

C0 C2C1X

g0 g2 g3

321)( xxxg ++=

a)Daca se alege polinomul de intrare : 2567)( xxxxxu +++=

0)(1

)(24

23

2567

=+=

++

+++= xresterestulxx

xx

xxxxxy

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


9/10

=

+=

=

+=

'

2

'

2

'

12

'

01

'

20

cy

ccc

cc

cuc

Catul : 24 xx +Restul: 0

b)Daca se alege polinomul de intrare : 1)(567

++++= xxxxxu

1)(1

1)(

224

23

567

++=+=

++

++++= xxxresterestulxx

xx

xxxxxy

Regulile de calcul pentru succesiunea starilor :

=

+=

=

+=

'

2

'

2

'

12

'

01

'

20

cy

ccc

cc

cuc

Catul : 24 xx +Restul: 12 ++xx

tact IN(u)

C0 C1 C2 OUT(y)

Catul

0 0 0 01 1 1 0 0 0

2 1 1 1 0 03 1 1 1 1 04 0 1 1 0 1 X4

5 0 0 1 1 06 1 0 0 0 1 X2

7 0 0 0 0 08 0 0 0 0 0Restul X0 X1 X2

tact IN(u)

C0 C1 C2 OUT(y)

Catul

0 0 0 01 1 1 0 0 02 1 1 1 0 03 1 1 1 1 0

4 0 1 1 0 1 X4

5 0 0 1 1 06 0 1 0 0 1 X2

7 1 1 1 0 08 1 1 1 1 0Restul X0 X1 X2


10/10

Curs Coduri Ciclice

Documents

Transcript of Curs Coduri Ciclice