CODURI BLOC LINIARE

CODURI BLOC LINIARE

I.          Coduri bloc lineare; Generalitati

Fie matricea generatoare pentru codul bloc linear (8, 4)

I.1. Sa se determine cuvintele de cod corespunzatoare tuturor mesajelor posibile. Care este distanta Hamming minima a codului ?

m G=c

d_Hmin = 2 = w(c₁₃) = d(c₂,c₁₅)

I.2. Sa se scrie matricea G sub forma sistematica [I_4x4 Q] (daca este posibil, se vor pastra din matricea Q numai acele coloane care au cate doua simboluri 1). Sa se determine toate cuvintele de cod sub forma sistematica.

~

I.3. Sa se scrie matricea H sub forma sistematica. Sa se determine toate cuvintele de cod corespunzatoare codului dual. Sa se verifice proprietatea de ortogonalitate a codului original cu cel dual.

H = [Q^TI_4x4] =    

Distanta Hamming minima este egala cu nr. Minim de coloane a caror suma este vectorul nul deci:

D_Hmin = 2

G_S H^T = = O_4x4

Se deduce ca orice cuvant al codului original, c_i , exista un cuvant d_k al codului dual astfel incat :

c_i d_k^T = 0, i,k =

c₁ d₁^T = 0 c₉ d₁₁^T = 0

c₂ d₃^T = 0 c₁₀ d₈^T = 0

c₃ d₄^T = 0 c₁₁ d₁₃^T = 0

c₄ d₁₂^T = 0 c₁₂ d₉^T = 0

c₅ d₅^T = 0 c₁₃ d₁₄^T = 0

c₆ d₆^T = 0 c₁₄ d₁₅^T = 0

c₇ d₁₀^T = 0 c₁₅ d₂^T = 0

c₈ d₇^T = 0

I.4. Sa se determine matricea standard de decodare. Sa se determine sindromurile corespunzatoare tuturor cuvintelor eroare alese .

Tabela are 16 coloane cu 16 linii adica 256 cuvinte binare(8 biti).Sunt luati 15 vectori de eroare

s_i = e_i H^T    i =

=>    s₁ = [0001]; s₂ = [0010]; s₃ = [0100]; s₄ = [1000]; s₅ = [0110]; s₆ = [1000];

s₇ = [1101]; s₈ = [0010]; s₉ = [0001]; s₁₀ = [0111]; s₁₁ = [1011]; s₁₂ = [0101];

s₁₃ = [1110]; s₁₄ = [0011]; s₁₅ = [1110];

Distanta minima Hamming este d_Hmin = 2 poate detecta vectori eroare de d_Hmin -1= 1 biti nenuli.

II. Coduri Hamming

Codurile Hamming sunt coduri bloc lineare (2^m-1, 2^m-m‑1) corectoare de o singura eroare (deci distanta Hamming minima este 3). Matricea de verificare a paritatii H, de dimensiune (m x (2^m-1)) are urmatoarea proprietate: coloanele sale corespund vectorilor asociati tuturor secventelor binare de lungime m, cu exceptia vectorului nul.

II.1. Sa se determine analitic matricile G si H codul Hamming (7,4) in forma sistematica.

Matricea de verificare a paritatii H are dimensiunea (3x7);

H=

G =

II.2 Sa se determine matricile G si H pentru codul Hamming (7,4), folosind functia hammgen. Corespund aceste matrici formei sistematice ?

[H,G] = hammgen (3)

H=    G=

Matricile corespund formei sistematice H = [I_3x3 Q^T]    G = [Q I_4x4]    Q =

II.3. Sa se determine toate cuvintele de cod posibile, folosind functia encode

msg = [0 0 0 0 ; 0 0 0 1 ; 0 0 1 0 ; 0 0 1 1 ; 0 1 0 0 ; 0 1 0 1 ; 0 1 1 0 ; 0 1 1 1 ; ;1 1 1 1 ]

code = encode(msg,7,4,'hamming')

II.4. Sa se determine matricea (tabela) standard de decodare si sindromurile asociate cuvintelor de cod alese.

Tabela va avea 2⁴ coloane, fiecare corespunde unui cuvant cod, pentru acoperirea celor 2⁷=128 cuvinte binare de 7 biti sunt necesare 8 linii, deci trebuie alesi 7 vectori de eroare.

Tabela standard de decodare va fi in figura urmatoare.

s = r H^T = [1010110]     = [ 0 0 1]

sindromurile cuvintelor alese vor fi:

s₁ = [0 0 0 0 0 0 1] H^T = [1 0 1]

s₂ = [0 0 0 0 0 1 0] H^T = [1 1 1]

s₃ = [0 0 0 0 1 0 0] H^T = [0 1 1]

s₄ = [0 0 0 1 0 0 0] H^T = [1 1 0]

s₅ = [0 0 1 0 0 0 0] H^T = [0 0 1]

s₆ = [0 1 0 0 0 0 0] H^T = [0 1 0]

s₇ = [1 0 0 0 0 0 0] H^T = [1 0 0]

II.4. Sa se decodeze mesajul [ 1 0 1 0 1 1 0]

a)     analitic;

b)    folosind functia decode;

c)     calculand sindromul si folosind matricea (tabela) standard de decodare.   

a) s = r H^T = e H^T =[e_{0 +} e_{3 +} e_{5 +} e_{6 ,} e_{1 +} e_{3 +} e_{4 +} e₅ , e_{2 +} e_{4 +} e_{5 +} e₆ ] = [0 0 1]

daca e₂ = 1 (e₀,e_1,e₂..sunt bitii vectorului eroare) => e = [0 0 1 0 0 0 0]

=> ĉ = r + e = [1 0 0 0 1 1 0 ] => m=[ 0 1 1 0]

b)           msg = decode ([1 0 1 0 1 1 0],7,4,'hamming')

msg =

c)              sindromul vectorului receptionat este cel corespunzator erorii [0 0 1 0 0 0 0];

in coloana 7 ĉ se regaseste in prima linie ĉ = [1010110] + [0010000] = [1000110] =>

m = [0 1 1 0]

III. Coduri ciclice

III.1. Folosind functia cyclpoly determinati polinomul generator corespunzator codului ciclic (8,3). Desenati structura codorului cu registru de deplasare.

g=cyclpoly(8,3)

g=[1 1 0 0 1 1]

g(D)=1+D+D⁴+D⁵

Circuitul de codare folosind registru in configuratia MSRG

III.2. Folosind functia encode generati biti de verificare a paritatii. Toate cuvintele de cod corespunzatoare unui nod ciclic (7,3).

Verificati proprietatea de deplasare ciclicxa.

Msg=[0 0 0 ; 0 0 1 ; 0 1 0 ; 0 1 1 ; 1 0 0 ; 1 0 1 ; 1 1 0 ; 1 1 1]

Code=encode (msg, 7.3 ; `cyclic` ; cyclpoly(7,3)

Se deplaseaza circular cu o pozitie fiecare cuvand de cod.

III.3. Pe baza polinomului generator sa se scrie matricea G

III.4.

Folosind functia cyclgen determinati matricile G si H in forma sistematica. Verificati analitic care este forma cea mai corecta.

[H , G]= cyclgen(7 , cyclpoly (7,3))

Impartim polinoamele la g(D)=1+D²+D³+D⁴

D⁴= g(D)+D³+D²+1

D⁵= D*g(D)+g(D)+D²+D+1=g(D)*(D+1)+D²+D+1

D⁶= D²*g(D)+D*g(D)+D=g(D)*(D²+D)+D

n (D)=b_i(D)+D⁴⁺ⁱ,    i=0,1,2

n (D)= 1+D²+D³+D⁴

n (D)= D+D⁶

n (D)= 1+D+D²+D⁵

=>

si

Se observa ca G si H determinate analitic au acceasi forma cu cele determinate de functia cyclgen.

III.5. Care este sindromul corespunzator vectorului receptionat r= [0 1 1 1 0 0 0 ] ? Verificati analitic, folosind diviziunea polinomiala, rezultatul obtinut.

s = r H^T = [0111000] = [0111]

r(D)=D+D²+D³

grad<grad => s(D)=r(D)= D+D²+D³ => s₁=s₂=s₃=1, iar s₀=0

III.6. Folosind functia decode determinati mesajul si pozitia erorii corespunzatoare mesajului receptionat de la punctul III.5. Verificati analitic rezultatul obtinut.

msg = decode([0111000],7,3,'cyclic',cyclpoly(7,3))

msg = 0

0

1

m = [001] caruia ii corespunde cuvantul de cod [0111001]

Petru determinarea pozitiei erorii:

e = encode(msg,7,3,'cyclic',cyclpoly(7,3))-[0;1;1;1;0;0;0];

e^'= 0 0 0 0 0 0 1

e₆(D)=D⁶ s(D)=D+D²+D³ s=[0 1 1 1]

e₅(D)=D⁵ s(D)=D+D² s=[0 1 1 0]

e₄(D)=D⁴    s(D)=1+D²+D³ s=[1 0 1 1]

e₃(D)=D³ s(D)=D³ s=[0 0 0 1]

e₂(D)=D² s(D)=D² s=[0 0 1 0]

e₁(D)=D s(D)=D s=[0 1 0 0]

e₀(D)=1 s(D)=1 s=[1 0 0 0]

Sindromul corespunzator lui r este cel corespunzator e₆, deci este eronat bitul al saptelea, deci    ĉ=[0 1 1 1 0 0 1] care corespunde mesajului [0 0 1]

IV. Coduri convolutionale

Fie codorukl convolutional descris de polinoamele

g₁(D)=1+D+D²

g₂(D)=1+D²

g₁(D)=1+D

IV.1. Sa se rezolve analitic:

a)     sa se deseneze schema codorului,

b)    sa se deseneze diagrama de tranzitii;

c)     sa se deseneze diagrama trellis

d)     sa se determine cuvantul de cod cod corespunzator mesajului m=[110101]

m=[1 1 0 1 0 1] => w(D)= 1+D+D³+D⁵

x₁(D) = (1+D+D³+D⁵)(1+D+D²) =1+D+D³+D⁵+D+D²+D⁴+D⁶+D²+D³+D⁵+D⁷ = 1+D⁴+D⁶+D⁷

ð     x₁=[1 0 0 0 1 0 1 1]

x₂(D)= (1+D+D³+D⁵)(1+D²)= 1+D+D³+D⁵+D²+D³+D⁵+D⁷=1+D+D²+D⁷

ð     x₂=[1 1 1 0 0 0 0 1]

x₃(D)= (1+D+D³+D⁵)(1+D)= 1+D+D³+D⁵+D+D²+D⁴+D⁶=1+D²+D³+D⁴+D⁵+D⁶

ð     x₃=[1 0 1 1 1 1 1 0]

secventa de cod generatoare va fi:

e)     folosind algoritmul Viterbi sa se decodeze semnalul r=[101111011101000000]

Cuvantul de cod se putea determina din diagrama de tranzitie saau din diagrama trellis, pornind din starea 00 si mergand pe linie continua daca bitul de intrare e 0 sau punctata daca bitul de intrare e 1, ultimele doua grupe de cate trei biti se obtin cand ultimul simbol al mesajului iese din circuit .

La fiecare pas se compara secventa receptionata cu cele doua iesiri posibile; acestea au cate trei biti iar cele doua iesiri sunt una valoarea negata a celeilalte si se alege din ele cea care are cel putin doi biti identici cu secventa receptionata.