Codarea pentru canale cu perturbatii I- Coduri grup [629655]

Codarea pentru canale cu perturbatii I- Coduri grup
Codarea pentru canale cu perturbatii I- Coduri grup ………………………………………….. ……………………………………… 1
I. Introducere ………………………………… …………………………………………… …………………………………………… ……. 1
II. Determinarea numarului de simboluri …………… …………………………………………… ………………………………… 1
III. Distanta intre cuvintele de cod ………………. …………………………………………… ……………………………………… 2
IV. Sintaxa MATLAB ……………………………… …………………………………………… ………………………………………. 2
V. Aplicatii ………………………………….. …………………………………………… …………………………………………… ……. 3
VI. Teme ………………………………………. …………………………………………… …………………………………………… …… 3
Codor si decodor Hamming corector de o eroare…… …………………………………………… ………………………………… 4

I. Introducere
In matematica si teoria informatiei codurile grup reprezint a tipuri importante de coduri bloc (coduri la
care informatia este organizata in cuvinte, blocuri de n sim boluri) folosite in schemele de detectie si corectie a
erorilor. Codurile grup permit o codare si decodare eficien ta fata de alte coduri.
Codurile grup sunt folosite la transmiterea simbolurilor ( e.g. biti), in canalele de comunicatie astfel
incat erorile ce apar pot fi detectate de receptorul mesajulu i bloc. Un cod de lungime n transmite blocuri
continand n simboluri. De exemplul codul Hamming (7,4) este un cod binar ce reprezinta valori de 4 biti
folosind 7 biti. In acest fel, receptorul poate detecta eror i grave ca 2 biti pe bloc.
In codurile grup un numar de k biti de informatie este urm at de un numar de m biti de control, derivati
din cei de informatie astfel incat la receptor, bitii de c ontrol sunt folositi pentru a valida bitii de informat ie.
II. Determinarea numarului de simboluri
Un cuvant de cod de lungime n are k simboluri de informat ie si m simboluri de control si poote fi
reprezentata sub forma unei matrici linie:
/g1874= [/g1853/g2869,/g1853/g2870, … … . /g1853/g3041], n=m+k.
Daca se foloseste pentru codare un alfabet X=[0,1], pentru transmisiunea a N simboluri ale sursei sunt
necesare k simboluri de informatie, numar care satisface relati a:
2/g3038≥/g1840
Fiecare bloc de k biti este codat intr-un bloc de n biti ( /g1866>/g1863) prin adaugarea n-k=m biti de control.
Numarul de biti de control m este stabilit de marginea Ha mming prin relatia:
2/g3040≥/g3533 /g1829 /g3041/g3036/g3032
/g3036/g2880/g2869
care reprezinta o conditie necesara dar nu suficiena. In cazul cazul corectiei unei singure erori:
2/g3040− 1 ≥ /g1866

III. Distanta intre cuvintele de cod

Asa cum s-a precizat pentru ca un cod sa poata avea propri etati de corectie este necesar ca din multimea de
cuvinte de n litere, numai o parte sa constituie cuvinte cu s ens. Rezulta astfel in spatiul cuvintelor o distanta
care a fost definita de Hamming ca fiind egala cu numarul pozitiilor prin care 2 cuvinte difera. Distanta dintre
cuvintele de cod /g1874/g3036 si /g1874/g3037 reprezinta ponderea unui cuvant de cod /g1874/g3036.
Conditia necesara si suficienta pe care trebuie sa o indeplinea sca distanta dintre cuvinte pentru a se corecta /g2187
erori este:
/g1856/g3040/g3036/g3041 =/g1842/g3040/g3036/g3041 = 2/g1857+ 1
iar pentru a se detecta /g2187 erori conditia este:
/g1856/g3040/g3036/g3041 =/g1842/g3040/g3036/g3041 =/g1857+ 1
Se remarca ca un cod corector de /g1857 este detector de 2 /g1857 erori.
Orice cod corector sau detector de erori este caracterizat pri n matricea de control /g1834(/g1865,/g1866) si matricea
generatoare /g1833(/g1863,/g1866). Intre aceste doua matrici exista relatia: /g1834/g1833/g3021= 0. Orice cuvant de cod, fiind o
combinatie liniara a liniior matricii G satisface relati a /g1834/g1874/g3021= 0. Aceasta permite determinarea simbolurilor de
control cand se cunosc cei de informatie, operatie efectuata la codare.
Relatia /g1834/g1874/g3021= 0 este similara cu /g2204=/g2191/g2163 unde v este cuvantul de cod, i cuvantul de date iar G matr icea
generatoare scrisa /g1833= [/g1835/g3038|/g1842], cu /g1835/g3038 matricea unitate de ordin k iar P este regula predefinita de codare. In
continuare vom folosi matricea generatoare pentru a realiza c odarea.
IV. Sintaxa MATLAB

Pentru codare se foloseste functia encode , cu urmatoarea sintaxa:

code=encode(msg, n,k,’linear/fmt’,genmat)

unde lungimea cuvantului de cod este n iar lungime mesajului k.

msg reprezinta mesajul de codat ce poate fi in format binar sau zecimal. Valoarea default pentru acest
parametru este binar , valoare ce va fi folosita mai depar te.

Formatul msg poate fi un vector coloana binar dupa cum urmeaza:

msg=[ 0 1 1 0 0 1 0 1 1 0 0 1 ] ’.

SImbolul “ ’ ”indica transpunearea matricii. La fel formatul msg poate f i o matrice binara cu numar de coloane
egal cu k. Formatul rezultat code va fi o matrice binara cu n coloane.Acelasi mesaj:

msg=[0 1 1 0;0 1 0 1;1 0 0 1]. K=4.

Pentru codurile grup functia encode codeaza msg folosid genmat , respective matricea generatoare, o matrice
/g1863 /g1876 /g1866 , necesara ca intrare.
V. Aplicatii

Exemplul de mai jos ilustreaza 2 formate diferite de inform atie (vectorul binar si matricea binara) pentru
codurile bloc. Ca rezultat, cele doua coduri create de fu nctia encode au acelasi continut in formate
corespondente diferite.

k=11. m=4 satisface marginea Hamming 2/g3040− 1 ≥ /g1866
m=4; % m este numarului bitilor de control.
k=11; % numarul simbolurile de informatie, lungimea mesaj ului trimis de sursa
n=m+k; % lungimea cuvantului de cod
% creerea aleatoarea 100 de mesaje , de k biti fiec are.
msg1=randint(100*k,1,[0,1]); %vector coloana
msg2=vec2mat(msg1,k); % matrice cu K coloane create din vectorul definit intial
%creearea a 100 de cuvinte de cod, de n biti fiecar e
P=[1 1 1 1;0 1 1 1;1 1 1 0;1 1 0 1;0 0 1 1;0 1 0 1; 0 1 1 0;1 0 0 1;1 0 1 0;1 0 1
1;1 1 0 0]; %regula predefinita de codare
genmat=[eye(11) P] ; %concateneaza matricea identitate cu matricea prede finita P
pentru a creea matricea generatoare
code1 = encode(msg1,n,k, 'linear/binary' ,genmat)
code2 = encode(msg2,n,k, 'linear/binary' ,genmat)
if ( vec2mat(code1,n)==code2 )
disp( 'All two formats produced the same content.' )
end

In schimbul generarii aleatoare a cuvintelor in Matlab se poate creea o matrice de date ce le dorim a fi
codate.

VI. Teme
Fiind dat un cod bloc (6,3) generat de matricea pre definita :/g1842=/g34290 1 1
1 0 1
1 1 0/g3433
a) Codati mesajele [1 1 1] si [1 0 1] manual si veri ficati rezulatul in Matlab.
b) Codati toate mesajele posibile ( /g1840= 2/g3038) in Matlab, verificati rezultatul si scrieti cuvi ntele codate.
Mesaj Vectorul de cod
000
001
010
011
100
101
110
111
c) Distant Hamming minima este:______________________

d) Numarul de erori pe care codul il poate detecta est e:____________________
e) Numarul de erori pe care codul il poate corecta est e:____________________
f) Este acest cod sistematic? Justificati raspunsul.
Considerati un cod bloc sistematic generat de matri cea /g1842=/g34291 1 0
0 1 1
1 0 1/g3433 .
a) Identificati valoarea lui n si a lui k
b) Completati valorile cuvintelor de cod prin simulare si scrieti ponderea acestora (Denumim ponderea
unui cuvant de cod numarul componentelor sale difer ite de zero.)
c)
Mesaj Vectorul codului Weight Dmin
000

001

010

011

100

101

110

111

d) Care este valoarea lui /g1856/g3040/g3036/g3041 ?(Distanta Hamming a unui cod este cea mai mica di stanta Hamming dintre
cuvintele codului, fiind egala cu ponderea cea mai mica a cuvintelor de cod, exceptand cuvantul nul).

VII. Codor si decodor Hamming corector de o eroare

Fie k numarul simbolurilor informationale necesare transmi terii unei informatii. Numarul simbolurilor de
control, m, ce trebuie adaugate în scopul corectiei unei erori , se determina din relatia:
2m -1>=n
Hamming a propus întocmirea matricei de control dupa urm atoarea regula: coloana h i sa fie reprezentarea
binara a numarului i pe m biti, cu bitul cel mai semnif icativ în prima linie. Conform acestei reguli matricea de
control
va avea forma:

De asemenea, Hamming a propus ca în structura matriceala a c uvintelor de cod simbolurile de control sa fie

plasate pe pozitiile 2 0, 2 1, 2 2, …, 2 m-1, numaratoarea efectuându-se de la stânga la dreapta. Cele k simb oluri de
informatie vor ocupa locurile ramase libere, adica: [v]=[c 1,c 2, i3,c 4, i5, i 7, c 8, i 9…..i n].
Determinarea simbolurilor de control, cunoscute fiind sim bolurile informationale, se efectueaza cu relatia Hv T=0,
dupa cum urmeaza:

Ecuatia matriceala este echivalenta cu urmatorul sistem d e ecuatii:

Codorul, care are misiunea de a calcula simbolurile de contr ol, cunoscute fiind simbolurile informationale, va fi
format dintr-un registru care contine n circuite basculant e bistabile în care se stocheaza simbolurile
informationale în pozitiile corespunzatoare din cuvântul de cod si o serie de sumatoare modulo 2 care,
conform sistemului de ecuatii calculeaza simbolurile de cont rol. Simbolurile de control astfel calculate se
stocheaza apoi în pozitiile în care acestea intervin în cuvâ ntul de cod.

Decodorul implementeaza relatia z=Hv’ T unde z se numeste corectorul cuvantului receptionat.

Structura matriceala a corectorului e data de:

Deoarece coloana h i este reprezentarea binara a numarului i pe m biti, rezulta ca pozitia erorii în cuvântul
receptionat se deduce astfel:

– se calculeaza componentele corectorului cu sistemul de ecuat ii de mai sus;

– se transcrie în zecimal numarul binar corespunzator compon entelor corectorului.
În felul acesta se precizeaza pozitia i a erorii. Decodorul Hamm ing, corector de o eroare va fi fo
dintr-un registru cu n circuite basculante bistabile în care va fi m emorat cuvântul receptionat, o serie de
sumatoare modulo 2 care, conform sistemului de ecuatii, calculeaza componentele co rectorului si un
decodificator din binar în zecimal cu m intrari si n iesiri.

Relatiile de codare

se transcrie în zecimal numarul binar corespunzator compon entelor corectorului.
În felul acesta se precizeaza pozitia i a erorii. Decodorul Hamm ing, corector de o eroare va fi fo
registru cu n circuite basculante bistabile în care va fi m emorat cuvântul receptionat, o serie de
care, conform sistemului de ecuatii, calculeaza componentele co rectorului si un
m intrari si n iesiri.

Relatiile de decodare
Codul Hamming (7,4)
În felul acesta se precizeaza pozitia i a erorii. Decodorul Hamm ing, corector de o eroare va fi fo rmat, deci,
registru cu n circuite basculante bistabile în care va fi m emorat cuvântul receptionat, o serie de
care, conform sistemului de ecuatii, calculeaza componentele co rectorului si un