S4 - Coduri Bloc v2

8/12/2019 S4 - Coduri Bloc v2

1/16

Seminar nr. 4. Coduri grup Rodica Stoian, TTI 1, 2005/2006, II C + II F

1

Seminar 4. Coduri grup

I. Breviar teoretic

Un cod binar ( , )n kC este determinat complet de un set de 2k cuvinte de cod, fiecare de lungime n biti si o functie de transformare de la cuvintele de informatie la cuvintele de cod.

Dimensionare cod:k, m, n;

Un cuvnt de cod de lungime nare ksimboluri de informatie si msimboluri de control si poate fireprezentat sub forma unui vector:

[ ]1 2 na a a= v VL ,

unde n= k+ m. Multimea tuturor cuvintelor de cod diferite formeaza spatiul cuvintelor de cod, V.

Determinarea numarului de simboluri de informatie k. Daca se foloseste un cod cu alfabetul{0,1}=X pentru transmiterea a Nsimboluri ale sursei S, atunci sunt necesare un numar de k

simboluri de informatie, dupa relatia:2k .

Determinarea numarului de simboluri de control m. Pentru a corecta terori, codul trebuie saaiba un numar de msimboluri de control stabilit de relatiile:o Marginea Hamming (conditie necesara dar nu suficienta):

0

2tm i

n

i

C=

.

o Marginea Varsamov-Gilbert (conditie suficienta dar nu necesara):2 1

11

2t

m i

n

i

C

=

.

Exemplu: Pentru corectia unei erori (t= 1), rezulta relatiile echivalente:o Marginea Hamming (conditie necesara dar nu suficienta):

0 12 1 1m n nC C n m k + = + = + + .o Marginea Varsamov-Gilbert (conditie suficienta dar nu necesara):

112 1 1

m

nC n m k = = + .

Constructie

Cuvintele de cod trebuie alese astfel nct distanta Hamming dintre ele sa fie ct mai mare.

Matricea de control HMultimea tuturor vectorilor ortogonali pe vectorii din spatiul V formeaza un spatiu ai caruivectori de baza, n numar de m, determina liniile matricei de control H:


2/16


2

[ ]

1 11 1 2 1

2 21 22 21 2

1 2

n

n

n

m m m mn

h h h

h h h

h h h

= = =

u

uH h h h

u

L

LL

M M M O M

L

.

Prin transformari elementare, matricea Hpoate fi adusa la una din formele canonice echivalentedin punctul de vedere al posibilitatilor de corectie:

[ ]

11 12 1

21 22 2

1 2

1 0 0

0 1 0'

0 0 1

k

k

m

m m mk

q q q

q q q

q q q

= =

H Q I

L L

L L

M M O M M M O M

L L

,

sau

[ ]

11 12 1

21 22 2

1 2

1 0 0

0 1 0''

0 0 1

k

k

m

m m mk

q q q

q q q

q q q

= =

H I Q

L L

L L

M M O M M M O M

L L

,

cuvntul de cod scriindu-se n forma sistematica:

[ ]bitiinformatie | biti controlk m=v ,sau

[ ]biti control | biti informatiem k=v .

Matricea generatoare GVectorii de baza, de dimensiune n, ai spatiului V, n numar de k, determina liniile matriciigeneratoare G:

1 11 12 1

2 21 22 2

1 2

n

n

k k k kn

g g

g g

g g

= =

v

vG

v

L

L

M M M O M

L

.

Cu ajutorul unei transformari elementare, matricea Gpoate fi adusa la una din formele canoniceechivalente:

[ ]

11 12 1

21 22 2

1 2

1 0 0

0 1 0'

0 0 1

k

km

k k km

p p p

p p p

p p p

= =

G I P

L L

L L

M M O M M M O M

L L

,

sau

[ ]

11 12 1

21 22 2

1 2

1 0 0

0 1 0''

0 0 1

k

k

m

k k km

p p p

p p p

p p p

= =

G P I

L L

L L

M M O M M M O M

L L

.

Relatia dintre matricile G si H


3/16


3

Orice cod corector sau detector de erori este caracterizat de matricea de control H, cu mlinii si ncoloane si de matricea generatoare G, cu klinii si ncoloane. ntre aceste matrici, exista relatia :

T =HG 0 ,unde TG este matricea transpusa matricei G.

Avnd n vedere relatiile de mai sus, putem scrie ca:T=P Q

siT=Q P .

Codare

Procesul de codare nseamna determinarea simbolurilor de control din simbolurile deinformatie.

Orice cuvnt de cod, fiind o combinatie liniara a liniilor matricii G, satisface relatia:T =Hv 0 ,

unde am folosit aritmetica modulo 2.

Folosind matricea G, orice cuvnt de cod se poate determina din:= v i G ,

unde [ ]1 2 ki i i=i L este cuvntul de informatie (un vector linie format numai din simboluri deinformatie). Astfel, orice cuvnt de cod al unui cod liniar se poate determina ca o combinatie liniaraa liniilor matricii G .

Transmisie prin CBS

Cuvntul eronat va fi cuvintul transmis vadunat cu un cuvnt eroare e:= +r v e .

Decodarea

Pentru un cuvnt receptionat r , se defineste sindromul ca fiind:( )T T T T T = = + = + =s H r H v e Hv He He .

Pe baza unei corespondente biunivoce ntre corector si pozitia eronata se stabileste pozitia eronata,ca apoi sa se corecteze eroarea.

Parametrii de performanta

Pentru ca un cod sa poata avea proprietati de corectie, este necesar ca din multimea tuturorcuvintelor de lungime n, numai o parte sa constituie cuvinte de cod cu sens. Rezulta astfel n spatiul

cuvintelor o distanta ntre cuvintele de cod [ ]1 2i i i ina a a=v L

si 1 2j j j jna a a = v L

carea fost definita de Hamming astfel:


4/16


4

1

( , )n

H i j ik jk

k

d a a=

= v v ,

unde reprezinta adunarea n corpul numerelor reale, iar adunarea modulo doi.

Cu alte cuvinte, distanta dintre doua cuvinte de cod reprezinta numarul de pozitii prin care cele douacuvinte difera. Se observa ca distanta dintre cuvintele de cod iv si jv reprezinta ponderea unui

cuvnt de cod k i j= v v v :

( , ) ( )H i j kd w=v v v .

Conditia necesara si suficienta pentru ca un cod sa poatacorecta t erori, este ca distanta minimadintre cuvintele de cod sa fie:

min min 2 1d w t= = + .

Conditia necesara si suficienta pentru ca un cod sa poatadetecta t erori, este ca distanta minimadintre cuvintele de cod sa fie:

min min 1d w t= = + .

Se observa ca un cod corector de terori este detector de 2terori.

Relatii ntre coloanele matricii HDistanta minima a unui cod este egala cu numarul minim de coloane ale matricii H care adunatedau un vector nul.Pentru a putea face corectia a terori, oricare 2t+1 coloane ale matricii H trebuie sa fie liniarindependente (suma oricaror tcoloane ale matricii H trebuie sa difere de suma oricaror altor tcoloane ale matricii H).Pentru a putea face detectia a t erori, trebuie ca t+1 coloane ale matricii H sa fie liniar

independente.

Cod extins

Daca pe lnga corectia unei erori simple, trebuie sa facem si detectia de erori duble, matricea decontrol va fi de forma:

1 2 3*

1 1 1 1 1 1nh h h h = =

0 H 0H

1

L

L,

unde Heste matricea de control a codului Hamming corector de o eroare. Astfel, la cele msimboluri

de control ale codului Hamming se mai adauga un simbol de control c0, denumit simbol de verificarea paritatii. Astfel, numarul total de simboluri de control este :

* 1m m= + ,iar dimensiunea cuvntului de cod:

* 1n n= + .

La decodare, se va calcula sindromul:

* * *

0

T T

s

= = =

ss H r H e .

Daca 0 0s = si =s 0 , atunci cuvntul receptionat este corect (nu au aparut erori n procesul detransmisie).


5/16


5

Daca 0 0s = si s 0 , atunci cuvntul receptionat are doua erori care sunt doar detectabile, decodorul

putnd cere retransmisia cuvntului de cod (ARQ).Daca 0 1s = , atunci cuvntul receptionat are un s ingur simbol eronat ce poate fi corectat, sindromul s

fiind reprezentarea n binar a pozitiei unde a aparut eroarea (FEC).

II. Probleme rezolvate

1. Codul Hamming (9,5)C . [MSG83], Pb2.4.Un numar de 20 simboluri se transmit pe un canal cu perturbatii utiliznd un cod Hamming grupcorector de o eroare.a) Sa se determine numarul kde simboluri de informatie, numarul m de simboluri de control

si lungimea n a unui cuvnt de cod. Codul este perfect?b) Sa se scrie matricea de control H a codului;c) Sa se scrie lista cuvintelor de cod. Calculati distanta minima

mind si ponderea minima

minw

ale codului;d) Sa se scrie matricea de control H n forma sistematica;e) Sa se deduca formele sistematice 'G si ''G ale matricii generatoare a codului. Sa se

determine matricea generatoare G a codului;f) Sa se deseneze schema codorului si a decodorului Hamming;g) Sa se calculeze sindromul pentru cazul n care simbolul de pe pozitia 4 din cuvntul

receptionat este eronat;h) Ce se ntmpla daca sunt eronate simbolurile de pe pozitiile 2 si 7?Rezolvare

a)

Deoarece n marginea Hamming nu se obtine egalitate, codul nu este perfect. O altaexplicatie ar fi data de utilizarea la corectie numai a 9n= sindromuri din totalul de2 1 15m = sindromuri posibile. Celelalte 6 sindromuri ar putea fi utilizate pentru detectia adoua erori.


6/16


6


7/16


7


8/16


8


9/16


9


10/16


10

2. Matricea H, cuvintele de cod, dmin pentru (7,3)C , [(140)3.2]Pentru un cod liniar (7,3)C peste (2)GF matricea generatoare este :

0 0 1 0 1 1 1

0 1 0 1 1 1 0

1 0 1 1 1 0 0

=

G .

a) Sa se determine matricea de control H a codului.b) Sa se listeze cuvintele de cod generate de ambele matrici Gsi H si sa se demonstreze ca

aceste matrici genereaza aceeasi multime de cuvinte de cod.c) Sa se determine distanta minima a codului.Rezolvare

a) Pentru a gasi codul sistematic echivalent se fac permutari pe coloane astfel nct sa se ajungala G= [ ]PI3 .

1 0 0 0 1 1 1

' 0 1 0 1 1 1 0

0 0 1 1 1 0 1

=

G .

b)0 1 1

1 1 1

1 1 01 0 1

T

= =

Q P ,


11/16


11

[ ]4

0 1 1 1 0 0 0

1 1 1 0 1 0 0'

1 1 0 0 0 1 0

1 0 1 0 0 0 1

= =

H Q I .

c) Se foloseste relatia = v i G . Parametrii codului sunt: n = 7,k = 3, m = n k = 4.[ ]1 2 3

0 0 1 0 1 1 1

0 1 0 1 1 1 0

1 0 1 1 1 0 0

i i i

= =

v i G

[ ]3 2 1 3 2 3 1 2 3 1 2 1i i i i i i i i i i i i = + + + + +v

Lista cuvintelor de cod nesistematic:

Cuvntul de cod [ ]3 2 1 3 2 3 1 2 3 1 2 1

i i i i i i i i i i i i= + + + + +v Cuvntul mesaj

[ ]1 2 3i i i=i i3 i2 i1+i3 i2+i3 i1+i2+i3 i1+i2 i1

000 0 0 0 0 0 0 0100 0 0 1 0 1 1 1010 0 1 0 1 1 1 0110 0 1 1 1 0 0 1001 1 0 1 1 1 0 0101 1 0 0 1 0 1 1011 1 1 1 0 0 1 0

111 1 1 0 0 1 0 1

Pentru varianta de cod sistematic, relatia de codare este:

[ ]1 2 3

1 0 0 0 1 1 1

' ' 0 1 0 1 1 1 0

0 0 1 1 1 0 1

i i i

= =

v i G

[ ]1 2 3 2 3 1 2 3 1 2 1 3' i i i i i i i i i i i i = + + + + +v

Lista cuvintelor de cod sistematic:

Cuvntul de cod [ ]1 2 3 2 3 1 2 3 1 2 1 3' i i i i i i i i i i i i= + + + + +v Cuvntul mesaj[ ]1 2 3i i i=i

i1 i2 i3 i2+i3 i1+i2+i3 i1+i2 i1+i3

000 0 0 0 0 0 0 0100 1 0 0 0 1 1 1010 0 1 0 1 1 1 0110 1 1 0 1 0 0 1001 0 0 1 1 1 0 0

101 1 0 1 1 0 1 1011 0 1 1 0 0 1 0111 1 1 1 0 1 0 1


12/16


12

d) Din tabelele anterioare se observa ca distanta minima dintre oricare doua cuvinte de cod este3.

3. Cod sistematic, nesistematic C(6,3). [(139)3.1]Pentru codul liniar C(6,3) peste GF(2) matricea generatoare este :0 1 1 0 1 0

1 1 0 0 0 1

1 1 0 1 1 0

=

G .

a) Sa se exprime Gn forma sistematica;b) Sa se gaseasca cuvntul de cod avnd simbolurile de informatie 110 ;c) Sa se precizeze cuvntul de cod generat de matricea Gn forma sistematica si nesistematica.Rezolvare

a) Pentru a gasi codul sistematic echivalent se fac permutari ale coloanelor matricii Gastfelnct sa se ajunga la [ ]3' =G I P :

1 0 0 0 1 1

' 0 1 0 1 0 1

0 0 1 1 1 1

=

G ,

permutarea folosita fiind1 2 3 4 5 6

4 6 1 3 5 2

=

.

A doua forma canonica pentru matricea G este [ ]3'' =G P I , sau :

0 1 1 1 0 0'' 1 0 1 0 1 0

1 1 1 0 0 1

=

G .

b) Daca cuvntul de informatie de la intrarea codului este [110]=i , atunci cuvntul de codcorespunzator va fi:

[ ] [ ]

0 1 1 1 0 0

1 1 0 1 0 1 0 1 0 1 1 0 1 1 0

1 1 1 0 0 1

= =

v i G .

c)Se folosesc relatiile = v i G si ' '= v i G :

[ ] [ ]1 2 3 1 2 3 2 3 1 3 1 2 3

1 0 0 0 1 1

' ' 0 1 0 1 0 1

0 0 1 1 1 1

i i i i i i i i i i i i i

= = = + + + +

v i G

[ ] [ ]1 2 3 2 3 1 2 3 1 3 1 3 2

0 1 1 0 1 0

1 1 0 0 0 1

1 1 0 1 1 0

i i i i i i i i i i i i i

= = = + + + +

v i G .

4. Schema de codare pt C(6,3), sistematic, nesistematic. (141)3.3


13/16


13

Sa se proiecteze o schema de codare n varianta sistematica(a) si nesistematica(b) pentru codulC(6,3) peste GF(2) cu matricea generatoare

0 1 1 0 1 0

1 1 0 0 0 1

1 1 0 1 1 0

=

G .

Rezolvare :

Pentru a proiecta schema trebuie sa cunoastem relatiile de codare n cele doua cazuri. Acestea aufost determinate n problema (139)3.1 (este aceeasi matrice G, deci acelasi cod).

a) [ ] [ ]1 2 3 2 3 1 3 1 2 3 1 2 3 1 2 3' i i i i i i i i i i i i i c c c= + + + + =v .

b) [ ] [ ]2 3 1 2 3 1 3 1 3 2 1 2 1 3 3 2i i i i i i i i i i c c i i c i= + + + + =v

S-au folosit urmatoarele notatii :+ - sumator modulo 2i - simbol de informatiec - simbol de control

5. Schema calcul sindrom pt codul C(7,3). (142)3.4Pentru un cod liniar C(7,3) peste GF(2) matricea generatoare este

i1 i2 i3 c1 c2 c3

+

+

+

c1 c2 i1 i3 c3 i2

+

+

+


14/16


14

0 0 1 0 1 1 1

0 1 0 1 1 1 0

1 0 1 1 1 0 0

=

G .

Sa se proiecteze circuitul de calcul al sindromului.

Rezolvare

Ecuatiile de codare au fost determinate n problema (140)3.2.

[ ] [ ]3 2 1 3 2 3 1 2 3 1 2 1 3 2 1 2 3 4 1i i i i i i i i i i i i i i c c c c i= + + + + + =v .Sindromul se calculeaza folosind relatia:

'T= s H v ,unde matricea Heste cea calculata anterior.

Rezulta urmatoarele componente ale sindromului:

)''('

)'''(')''('

)''('

2144

32133

3222

3111

iics

iiics

iics

iics

++=

+++=++=

++=

Schema pentru calculul sindromului :

6. Cod autodual C(8,4), H dat. Cod perfect. (145)3.10.Consideram codul bloc liniar C(8,4) caracterizat de matricea

1 0 0 0 1 1 0 1

0 1 0 0 1 0 1 1

0 0 1 0 1 1 1 0

0 0 0 1 0 1 1 1

=

H

a) Este acest cod autodual?

i i2 c1 c2 c3 c4 i1

+

+

+

+ s1

s2

s3

s4


15/16


15

b) Codul este perfect?Rezolvare

a) Codul dual al unui cod C(n,k) este ( , ) ( , )C n n k C n m = . Asadar codul dual al coduluiC(8,4) este tot C(8,4). Putem, deci, afirma ca C(8,4) este autodual.

b) Dimensiunile matricii Hpermit sa se determine: n = 8, m = 4 sik = 4.Cu acest cod se pot transmite 16 simboluri si se poate corecta o eroare (t = 1).Se verifica marginea Hamming:

9811620

=+ =

t

i

i

n

mC .

Se verifica pentru t=1 si conditia pentru marginea Varsamov- Gilbert

7162 1712

11 =

= CC

t

i

i

n

m .

Codul nu este perfect deoarece se pot forma 15 corectori distincti, dintre care se utilizeazapentru corectia unei erori numai 8.

III. Probleme propuse

7. Cod Hamming grup corector de 1 eroare, detector de 2 erori. [MSG83], Pb 2.5.Un numar de 8 simboluri de informatie se transmit printr-un canal afectat de perturbatii cuajutorul unui cod Hamming grup corector de o eroare si detector de erori duble.a) Sa se determine numarul simbolurilor de informatie k, al celor de control msi lungimea na

fiecarui cuvnt de cod;b) Sa se scrie matricea de control a codului H;c) Sa se scrie cuvintele de cod;d) Sa se stabileasca expresia sindromului pentru cazul n care se eroneaza c2;e) Sa se stabileasca expresia sindromului corespunzator eronarii simbolurilor c1si c2;f) Sa se precizeze daca [1100110]=v este cuvnt al acestui cod;

8. Cod grup oarecare cu matricea H data. [MSG83], Pb 2.7.Se considera un cod grup cu matricea de control de forma:

1 0 0 1 1

0 1 0 0 1

0 0 1 1 0

=

H .

a) Sa se determine proprietatile de corectie ale codului. Codul este perfect?b) Sa se stabileasca daca matricea:

1 0 1 1 0

1 1 0 0 1

=

G

poate fi matrice generatoare a codului;c) Sa se scrie cuvintele de cod utiliznd matricile Hsi G.

9. Cod grup specificat prin cuv de cod. [MSG83], Pb 2.8.Se da un cod grup sistematic ale carui cuvinte de cod sunt:


16/16


16

0

1

2

3

[0000000]

[1111101]

[1111010]

[0000111]

=

=

=

=

v

v

v

v

.

a) Sa se stabileasca proprietatile de corectie ale acestui cod;b) Sa se scrie o matrice Hcorespunzatoare acestui cod;c) Sa se faca tabelul claselor alaturate si sa se specifice corectorii aferenti.

IV. Bibliografie

[MSG83]A. T. Murgan, I. Spnu, Inge Gavat, I. Sztojanov, V. E. Neagoe, Adriana Vlad, TeoriaTransmisiunii Informatiei probleme, Editura Didactica si Pedagogica, Bucuresti, 1983.

[Mur98] A. T. Murgan, Principiile teoriei Informatiei n ingineria informatiei si a comunicatiilor,Editura Academiei Romne, Bucuresti, 1998.

[Spa83] Al. Spataru, Teoria Transmisiunii Informatiei, Editura Didactica si Pedagogica,Bucuresti, 1983.

[Sto] Rodica Stoian, Note de seminar.

[Per] L. Perisoara, Note de seminar.

S4 - Coduri Bloc v2

Documents

Transcript of S4 - Coduri Bloc v2