62

SISTEM DE CODARE ŞI DECODARE PENTRU UN COD CICLIC

CORECTOR DE O EROARE

1. Introducere teoretică

Un cuvânt de cod ciclic se poate reprezenta ca un polinom:

( ) 1 21 2 1 0n n

n nv x a x a x a x a− −− −= ⊕ ⊕ ⊕ ⊕… (1)

în care cei n coeficienÛi ia ∈{0,1} constituie simbolurile cuvântului de cod, k dintre simboluri sunt

de informaÛie Õi m=n-k sunt de control.

Un cod ciclic este definit prin polinomul s|u generator ( )g x , de grad m. Cuvintele codului

ciclic generat de ( )g x sunt polinoame de grad n-1 sau mai mic, multipli ai polinomului ( )g x .

Altfel spus, orice cuvânt de cod ciclic ( )v x este divizibil prin ( )g x . Aceast| proprietate a

cuvintelor de cod ciclic este utilizat| în realizarea cod|rii Õi decod|rii: la codare, fiind date

simbolurile de informaÛie, trebuie determinate simbolurile de control, astfel încât s| rezulte un

cuvânt ( )v x , care împ|rÛit prin ( )g x s| dea restul nul; la recepÛie, decodorul verific| dac| restul

împ|rÛirii cuvântului recepÛionat ( )v x′ ) prin ( )g x este sau nu zero. Dac| restul este zero, cuvântul

recepÛionat este corect, iar în caz contrar cuvântul recepÛionat este eronat datorit| perturbaÛiilor de pe

canal. În acest ultim caz, dac| structura codului permite corecÛia erorii, se va determina cuvântul

eroare ( )xε , iar cuvântul corect va rezulta din relaÛia:

( ) ( ) ( )v x v x xε′= ⊕ (2)

unde cuvântul eroare ( )xε este un cuvânt de lungime n cu unit|Ûi plasate pe poziÛiile în care s-au

introdus erori Õi zerouri pe poziÛiile în care nu s-au introdus erori în cuvântul recepÛionat.

Pornindu-se de la polinomul informaÛional

( ) 1 21 2 1 0k k

k ki x a x a x a x a− −

− −= ⊕ ⊕ ⊕ ⊕… (3)

construit numai cu simbolurile de informaÛie, se pot construi coduri nesistematice sau sistematice, în

conformitate cu relaÛiile:

- cod nesistematic:

( ) ( ) ( )v x g x i x= ⋅ (4)

- cod sistematic:

( ) ( ) ( ) ( ){ }restm mv x x i x x i x g x= ⊕ (4)

În cazul codului sistematic, simbolurile de informaÛie sunt plasate pe poziÛiile

corespunz|toare coeficienÛilor termenilor de grad n-1 pân| la n-k.

63

Determinarea posibilit|Ûilor de corecÛie sau detecÛie a codului se face prin alegerea adecvat|

a polinomului generator ( )g x . În cazul corecÛiei unei erori, polinomul generator se alege primitiv de

grad m, determinat din relaÛia: 2m $ m + k + 1.

2. Codor ciclic corector de o eroare

În cele ce urmeaz| se va considera un cod ciclic sistematic în care n=7 Õi k=4. Din relaÛia

2m $m+4+1, rezult| m=3 Õi deci cuvintele de cod au structura: ( ) 6 5

6 5 1 0v x a x a x a x a= ⊕ ⊕ ⊕ ⊕… ,

unde 6 5 4 3, , ,a a a a sunt simbolurile de informaÛie, iar 2 1 0, ,a a a de control. Cu ajutorul acestui cod se

pot transmite N # 2k = 16 mesaje Õi se poate corecta o eroare, indiferent de poziÛia în care apare.

Drept polinom generator se poate folosi fie ( ) 3 1g x x x= ⊕ ⊕ , fie ( ) 3 2 1g x x x= ⊕ ⊕ . (Liste de

polinoame primitive de diferite grade sunt indicate în literatura de specialitate).

Un circuit care poate realiza codarea cuvintelor de cod ciclic generate de ( )g x este circuitul

divizor de polinoame realizat cu registru de deplasare cu reacÛie, dat în fig.1.

Figura 1

C2, C1, C0 sunt cele trei celule binare ale registrului de deplasare, ig sunt multiplicatoare cu

constanta ig ∈{0,1}, iar ⊕ sunt sumatoare modulo doi. Pentru acest circuit se poate defini matricea

caracteristic| [T]:

[ ]0 1 2

0 1 0

0 0 1T

g g g

=

(6)

care permite determinarea evoluÛiei stărilor registrului. Se noteaz|0

1

2

stC

[S] = stC

stC

o stare a registrului,

64

stCk - starea celulei k Õi

0

[U] = 0

1

specificând c| C0 Õi C1 sunt în "0" logic Õi C2 în "1" logic. Starea

registrului la tactul "i" se determin| cu relaÛia:

[ ] [ ] [ ] [ ]1i i n iS T S a U− −= ⋅ ⊕ (7)

FuncÛionarea circuitului este urm|toarea: în primele patru tacte pe intrarea A se aplic|

simbolurile cunoscute, de informaÛie, 6 5 4 3, , ,a a a a , iar în ultimele trei tacte comutatorul este trecut pe

poziÛia 2, pe intr|rile A Õi B ale sumatorului S3 aplicându-se aceleaÕi simboluri (intrarea A se uneÕte

astfel cu B), respectiv cele de la ieÕirea sumatorului S2. Din acest motiv starea final| a registrului este

nul|. Prin urmare, în punctul A, la ultimele trei tacte se obÛin simbolurile de control 2 1 0, ,a a a ale

cuvântului de cod. În continuare, se vor determina relaÛiile dintre simbolurile de informaÛie Õi cele de

control, scriind cu ajutorul matricei caracteristice succesiunea de st|ri a registrului cu reacÛie.

Se alege polinomul generator ( ) 3 1g x x x= ⊕ ⊕ , pentru care:

[ ]0 1 0

0 0 1

1 1 0

T

=

(8)

Utilizând relaÛia (7), se obÛine:

[ ] [ ]1 6

6

0

0S a U

a

= =

(9)

[ ] [ ] [ ] [ ] [ ] [ ] [ ]2 1 5 6 6 5

5

0

S T S a U a a T U a U

a

= ⋅ ⊕ = = ⋅ ⊕

(10)

[ ] [ ] [ ] [ ] [ ] [ ] [ ][ ] [ ]6

2

3 2 4 5 6 5 4

6 5

a

S T S a U a a T U a T U a U

a a

= ⋅ ⊕ = = ⊕ ⊕ ⊕

(11)

[ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ][ ] [ ]5

3 2

4 3 3 6 4 6 5 4 3

6 5 3

a

S T S a U a a a T U a T U a T U a U

a a a

= ⋅ ⊕ = ⊕ = ⊕ ⊕ ⊕ ⊕ ⊕

(12)

[ ] [ ] [ ] [ ]6 4

5 4 2 6 5 3

6 5 4 2

a a

S T S a U a a a

a a a a

⊕ = ⋅ ⊕ = ⊕ ⊕ = ⊕ ⊕ ⊕

65

[ ] [ ] [ ] [ ] [ ] [ ] [ ][ ] [ ]4 3 2

6 5 4 3 2a T U a T U a T U a T U a U= ⊕ ⊕ ⊕ ⊕ (13)

[ ] [ ] [ ] [ ]6 5 3

6 5 1 6 5 4 2

3 4 5 1

a a a

S T S a U a a a a

a a a a

⊕ ⊕ = ⋅ ⊕ = ⊕ ⊕ ⊕ = ⊕ ⊕ ⊕

[ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ][ ] [ ]5 4 3 2

6 5 4 3 2 1a T U a T U a T U a T U a T U a U= ⊕ ⊕ ⊕ ⊕ ⊕ (14)

[ ] [ ] [ ] [ ]6 5 4 2

7 6 0 3 4 5 1

2 3 4 0

a a a a

S T S a U a a a a

a a a a

⊕ ⊕ ⊕ = ⋅ ⊕ = ⊕ ⊕ ⊕ = ⊕ ⊕ ⊕

[ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ][ ] [ ]6 5 4 3 2

6 5 4 3 2 1 0a T U a T U a T U a T U a T U a T U a U= ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ (14)

Dac| se are în vedere c| starea dup| Õapte tacte a registrului este nul|, se pot obÛine relaÛiile

dintre simbolurile de informaÛie Õi cele de control:

7

0

[ ] = 0S

0

Õi deci 2 6 5 4

1 3 4 5

0 3 5 6

a a a a

a a a a

a a a a

= ⊕ ⊕

= ⊕ ⊕ = ⊕ ⊕

(16)

Se poate ar|ta c| expresia [S7] dat| de relaÛia (15) se poate pune sub forma:

[ ] [ ][ ]7

TS H v= (17)

unde:

[ ] [ ] [ ][ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]2 3 4 5 6H U T U T U T U T U T U T U = (18)

este matricea de control a codului, iar cuvântul de cod [v] se reprezint| sub forma unei matrice linie:

[ ] [ ]0 1 2 3 4 5 6v a a a a a a a= (19)

În figura 2 Õi tabelul 1 sunt prezentate circuitul de codare, respectiv st|rile intr|rii, ieÕirii Õi

st|rile celulelor registrului în cazul folosirii polinomului generator ( ) 3 1g x x x= ⊕ ⊕ . Dup| ce

utimul simbol informaÛional, 3a , a fost introdus în R.D.R., cheia K este trecut| pe poziÛia 2.

Începând cu tactul 8 se face codarea pentru al doilea cuvânt de cod.

Figura 2

66

Tabelul 1

Tact

Cheia K

Intrare

Stare registru

C2 C1 C0

IeÕire

1

a6

0

0

0

a6

2

a5

a6

0

0 a5

3

a4

a5

a6

0 a4

4

poz.1

a3

a6 r a4

a5

a6 a3

5

0

a6 r a5 r a3

a6 r a4

a5 a2 = a6 r a5 r a4

6

0

0

a6 r a5 r a3

a6 r a4 a1 = a5 r a4 r a3

7

poz.2

0

0

0

a6 r a5 r a3 a0 = a6 r a5 r a3

8

poz.1

a6

0

0

0 a6

3. Decodor ciclic corector de o eroare

În fig.3 este prezentat| principial schema unei unit|Ûi de decodare realizat| cu dou|

decodoare identice construite cu registre de deplasare cu reacÛie similare cu cele de la codare.

La decodare pe intrarea A se aplic| succesiv timp de Õapte tacte simbolurile 6 5 1 0, , , ,a a a a′ ′ ′ ′…

ale cuvântului recepÛionat, starea registrului devenind conform relaÛiei (7):

[ ] [ ] [ ] [ ] [ ][ ] [ ]6 5

7 6 5 1 0S a T U a T U a T U a U ′ ′ ′ ′ ′= ⊕ ⊕ ⊕ ⊕

… (20)

Úinând cont de (17), se poate scrie:

[ ][ ] [ ]7

TS H v Z ′ ′= =

(21)

unde [ ]Z se numeÕte corectorul cuvântului recepÛionat.

Dac| simbolurile ka′ sunt toate corecte, [ ] [ ]7 0S Z ′ = =

. Dac| unul din simbolurile ka

′ este

eronat, [ ] [ ]7 0S Z ′ = ≠

. Fie eronat simbolul ia ′ , adic|:

pt cu 0,1, ,6

1 pt

k k

k k

a a k i k

a a k i

′ = ≠ =

′ = ⊕ =

…

(22)

În acest caz, relaÛia (21) devine:

[ ] [ ] [ ] [ ] [ ] [ ][ ] [ ] [ ] [ ] [ ] [ ]6 5

6 5 1 0

i iZ a T U a T U a T U a U T U T U= ⊕ ⊕ ⊕ ⊕ ⊕ =… (23)

Õi este clar c| pentru fiecare poziÛie eronat|, deci pentru fiecare cuvânt eroare, avem alt corector,

adic| acest cod are propriet|Ûi de corecÛie.

67

Figura 3

Pentru corecÛia erorii de pe poziÛia "i" registrul de deplasare cu reacÛie este l|sat s| evolueze

liber (la intrarea sa se aplic| "0" logic) în decursul urm|toarelor Õapte tacte. Succesiunea de st|ri a

registrului de deplasare cu reacÛie în evoluÛie liber| se poate determina cu relaÛiile:

[ ] [ ][ ] [ ]

[ ] [ ] [ ] [ ]

[ ] [ ] [ ] [ ] [ ]

8 7

2

9 8

7 1 1

14 1

1

0

0

i

i

i i

i

S T S T T U

S T S T T U

S T T U T U− − −

− −

′ ′= = ′ ′= =

′ = = =

……………………… (24)

deoarece [ ] [ ]7T I= , unde [ ]I este matricea unitate.

Deci, dac| este eronat simbolul ia , la tactul 14-i-1, adic| atunci când simbolul eronat ajunge

68

în celula binar| 7 a lui RD1, registrul trece prin starea fix|

1

0

0

, caz în care la ieÕirea porÛii ÔI1 rezult|

"1" logic care, sumat modulo 2 cu a'i recepÛionat eronat, îl corecteaz|.

4. Dispozitivul de laborator

Dispozitivul de laborator este construit pentru coduri ciclice 7:4 generate de

( ) 3 2 1g x x x= ⊕ ⊕ (caz a) sau ( ) 3 1g x x x= ⊕ ⊕ (caz b). fig.4.

Figura 4

Cu ajutorul comutatoarelor de pe panoul frontal se poate selecta orice combinaÛie de 4

simboluri binare informaÛionale, iar prin intermediul comutatoarelor de la canalul de transmisiune se

poate erona oricare simbol al cuvântului de cod. Dispozitivul genereaz| periodic acelaÕi cuvânt de

cod.

5. Schema electrică a dispozitivului de laborator

Schema logic| a dispozitivului de laborator este prezentat| în fig.5.

Comutatorul K al codorului este implementat cu porÛile SAU2, SAU3, ÔI1. Registrul în inel

R1 are 7 celule Õi se iniÛializeaz| în cu un 1 Õi restul de 0. Atunci când celula 6 se afl| în starea 1, la

ieÕirea porÛii SAU1 se obÛine 6a (egal cu 1 sau cu 0, dup| cum comutatorul respectiv de la intrarea

corespunz|toare a porÛii SAU1 este închis pe ieÕirea 6 sau la mas|). La tactele urm|toare se obÛin în

mod similar 5 4 3, ,a a a selectabile prin comutatoarele respective. În tot acest timp, poarta SAU2 are 0

la ieÕire, care blocheaz| poarta ÔI1. Se asigur| astfel aplicarea simbolurilor de informaÛie 6 3a a−

prin SAU3 atât registrului de deplasare cu reacÛie (pe S3), cât Õi c|tre canalul de transmisiuni simulat

cu XOR1. Când unitatea se deplaseaz| prin celulele 2, 1 Õi 0 ale registrului R1, se obÛine 1 la ieÕirea

69

SAU2, care valideaz| poarta ÔI1. Simultan poarta SAU1 are 0 la ieÕire. Se obÛin simbolurile de

control care se aplic| prin ÔI1, SAU3 atât c|tre ieÕire (XOR1), cât Õi pe a doua intrare a lui S3. Prin

comutatoarele de la intrarea porÛii SAU4 se prescriu simbolurile cuvântului eroare. De exemplu,

dac| este "1" logic în celula 3, pe linie se transmite 3a ; în funcÛie de poziÛia comutatorului al treilea,

la ieÕirea porÛii SAU4 se obÛine 3ε de valoare 0 sau 1; poarta XOR1 realizeaz| 3 3a ε⊕ . O dat| cu

revenirea unit|Ûii în celula 6 se începe transmiterea unui nou cuvânt de cod.

Decodorul este construit conform schemei de principiu, comutatorul C al decodorului fiind

realizat cu bistabilul CB care valideaz| când ÔI2, ÔI5, când ÔI3, ÔI4.

Pentru corecta sincronizare a codorului cu decodorul, tactul decodorului este întârziat prin

selectarea frontului opus faÛ| de tactul codorului.

La sfârÕitul fiec|rui cuvânt se d| tact pentru CB, iar la tactul urm|tor se d| tact pentru

registrele de afiÕare, care încarc| paralel cuvintele.

Figura 5

6. Desfăşurarea lucrării

1. Se întocmeÕte un tabel cu funcÛionarea codorului în cazul polinomului

70

( ) 3 2 1g x x x= ⊕ ⊕ .

2. Se verific| faptul c| ( )v x obÛinut la ieÕirea codorului este cuvânt de cod, divizibil prin

( )g x .

3. Se scriu toate cuvintele de cod pentru ambele polinoame generatoare Õi se verific|:

- distanÛa Hamming între cuvinte;

- proprietatea de ciclicitate.

4. Să se găsească cuvintele de cod ciclice sistematice pentru transmiterea numerelor

zecimale de la 0 la 7. Numerele se transcriu în binar pe numărul minim de biŃi.

5. CalculaÛi resturile diviz|rii polinoamelor ( )i xε la ( )g x , unde ( ) i

i x xε = Õi

i∈{0,1,2,...,6}. Concluzii.

6. Să se deseneze structura decodorului în cazul polinomului ( ) 3 2 1g x x x= ⊕ ⊕ şi să

se afle cuvântele de cod rezultate în urma decodării, dacă s-au recepŃionat cuvintele

[ ] [ ]1 1 0 1 1 1 0 0v′ = , [ ] [ ]2 1 0 0 0 0 1 0v′ = , respectiv

[ ] [ ]3 1 0 0 1 1 0 0v′ = . Cuvintele recepŃionate sunt date în forma

[ ] [ ]0 1 2 3 4 5 6v a a a a a a a′ ′ ′ ′ ′ ′ ′ ′= .

7. Ce se întâmpl| dac| se produc dou| erori ? Dar dac| se produc trei erori ?

8. Se analizeaz| funcÛionarea pe schema electric|.

9. AplicaÛÛÛÛia MATLAB BBBB> Simulink:

Se lanseaz| programul Matlab Õi din meniul 'FileB>Open' se selecteaz| Õi se deschide

modelul lucr|rii de laborator ‘ciclic.mdl’. Se urm|reÕte funcÛionarea sistemului de codare/decodare

astfel:

- Se identific| Õi se studiaz| blocurile de pe schem|;

- Se alege polinomul generator g(x) dorit prin modificarea structurii codorului Õi decodorului

(blocurile "Codor" Õi "Decodor");

- Se prescrie rata erorilor introduse de canalul de transmisiuni (dublu-click pe blocul "B-

error" B> "error probability");

- Prin acÛionarea butonului 'Start' se porneÕte simularea, la terminarea ei obÛinându-se un

raport asupra ratei erorilor f|cute la decodare (recepÛie);

- F|când dublu-click pe blocurile de tip "scope" se observ| formele de und| din punctele

respective. ObservaÛii.

Se deschide apoi modelul lucr|rii de laborator ‘ciclic_1cuvant_de_cod.mdl’. Se urm|reÕte

funcÛionarea schemei, astfel:

- Se prescriu cele 4 simboluri de informaŃie cu ajutorul comutatoarelor din intrare;

71

- Se prescrie poziŃia erorii din blocul „canal de comunicatie”;

- Se acŃionează butonul 'Start' şi se urmăresc formele de undă corespunzătoare secvenŃei de

date, cuvântului de cod, cuvântului recepŃionat şi cuvântului decodat din blocurile de tip "scope".