Indrumator TIC

7/26/2019 Indrumator TIC

1/49

TEORIA INFORMAIEI I A CODRII

ndrumtor de lucrri la laborator

Horia BALTA Maria KOVACI

2009


2/49

1

Cuprins

L1.Algoritmi pentru codarea sursei i compresie ....................................................................... 3

1.1.Codarea binara surselor de informaie ............................................................................. 3

1.2. Algoritmul Huffman dinamic ............................................................................................. 6

1.3.Algoritmi de compresie de tip LZ ..................................................................................... 10

L2.Coduri simple corectoare de o eroare .................................................................................... 15

2.1 Codul Hamming ................................................................................................................ 15

2.2 Codul ciclic .................................................................................................................... 20

L3.Coduri ciclice corectoare de erori multiple ....................................................................... 28

3.1 Codul BCH ........................................ ................................................ ......... 28

3.2 Codul Reed-Solomon .................................................................................. 35

L4.Coduri convoluionale ..................................................... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 41

Bibliografie .................................................................................................................................... 48


3/49

2


4/49

3

L1. Algoritmi pentru codarea sursei i compresie

1.1. Codarea binara surselor de informaie

Lucrarea de fa i propune explicitarea algoritmilor de calcul pentru a coda binar surse deinformaie ntlnite n practic.

Codarea binara surselor de informaie are dublu rol, de mrire a eficienei sursei de informaie(i implicit de micorare a costului transmisiei prin scderea timpului transmisiei); de adaptare a surseide informaie la canalul transmisiune (canal binar, n majoritate).

Din punct de vedere al codrii, la o sursde informaie intereseaznumrul de simboluri N i

probabilitile lor de apariie pi , Ni ,1 . Doar pe utilizator l intereseazce reprezintfiecare mesaj nparte (literde alfabet, nivel al intensitii pixelilor dintr-o imagine, valori ale unor mrimi fizice cevariazarbitrar1).

Codarea este operaia prin care fiecrui simbol al sursei, si, i se aloco succesiune binarunic:

si lii2i

1i r...,r,r = ci (1.1.1)

unde ci reprezint cuvntul de cod asociat simbolului (mesajului) sursei, iar jir , cu Ni ,1 , biii

componeni ai cuvntului de cod (pot lua valori binare 1 sau 0). Suportul fizic al valorilor binareeste, de asemenea, mai puin important pentru codare. Acest suport poate fi un semnal electric, optic,acustic, etc.

n expresia (1.1.1) li reprezint lungimea cuvntului de cod ci (numr de simboluri binare).Lungimea medie a cuvintelor de cod este datde relaia:

i

N

1ii lpL

(1.1.2)

Ieirea codorului, pentru canalul de transmisie, reprezint o surs de informaie numitsecundar. Aceast surs poate genera simbolurile 0 i 1. Entropia (informaia medie pe simbol),entropia maxim, precum i eficiena sursei primare, sunt date de relaiile:

i2

N

1ii p

1logpH(S)

;

Nlog(S)H 2max ;

(S)H

H(S)

maxS .

(1.1.3)

Entropia sursei secundare este egalcu informaia medie pe un cuvnt raportatla lungimeamedie a cuvntului:

L

H(S)H(X) (1.1.4)

Atribuirea literelor de alfabet jir pentru a forma cuvntul de cod ci trebuie s conduc la

ndeplinirea condiiilor:- codul sfie instantaneu (nici un cuvnt nu este prefixul altuia);

1Dei, aparent, astfel de surse de informaie nu au un numr finit de simboluri, prin eantionare i cuantizare, oricesursde informaie poate fi redusla una cu numr finit de simboluri.


5/49

4

- codarea s conduc la o eficien maxim posibil. Aceast condiie se realizeazfolosind cuvinte de lungime variabil, mai mare pentru simboluri de probabilitate de emisie (a sursei

primare) mai mic. Codarea cu cuvinte de lungime variabileste mai complicat, dar conduce la osurssecundarcu eficienmai buni la o ieftinire a transmisiei, lungimea medie a cuvintelor decod fiind mai mic. Codarea cu cuvinte de lungime constanteste mai simpldar cuvintele avndaceeai lungime ofermaleabilitate la prelucrri ulterioare.

Codarea cu cuvinte de lungime constant se mai numete i codare cu cod bloc. Cuvintelecodului bloc sunt secvene binare diferite, de aceeai lungime L. tiind cnumrul de secvene diferitece pot fi constituite cu L cifre binare este 2L, rezultcnumrul simbolurilor sursei trebuie sfie maimic dect 2L, sau:

(S)HNlogL max2 > L 1 (1.1.5)

Inecuaia a doua din (1.1.5) se datoreazcriteriului de eficienminim posibil(sub restricia decod bloc).

Realizarea condiiilor mai sus precizate se face prin codare dup algoritmul Huffman (static).Acesta presupune:

1. Ordonarea probabilitilor sursei (primare) n ordine descresctoare;2. Simbolurile cu probabilitile cele mai mici (ultimele dou1 n ordonare) se reunesc

formnd un nou simbol cu probabilitatea sumei celor dou, dup care se reordoneazprobabilitile,obinndu-se o surscu N-1 simboluri;

3. Procesul continupncnd rmn 2 simboluri. Acestora li se atribuie valorile 0 i 1;4. Mergnd pe cale invers, se disociaz simbolurile compuse n simboluri din care s-au

compus, atribuind arbitrar, la fiecare disociere, valorile 0 i 1 pentru a gsi cuvintele de cod pentru ceidoi componeni. De reinut c doar un singur simbol se disociaz la fiecare pas, lungimeacomponenilor si crescnd cu 1, celelalte simboluri pstrndu-i lungimea i structura cuvntului decod.

Observaie: -atribuirea simbolurilor binare celor dou simboluri compuse este arbitrar, codurileobinute vor fi diferite, dar de aceeai eficien. De asemenea, ordinea simbolurilor de egal

probabilitate poate fi aleasarbitrar, diferitele moduri de atribuire conducnd la coduri diferite, darde aceeai eficien. ns, n vederea posibilitii de a confrunta rezultatele, se vor respecta regulile: -0 se atribuie totdeauna simbolului de jos (ultimul n ordonare); -ordinea simbolurilor egal

probabile este ordinea n care s-au citit, cu simbolul compus totdeauna ultimul.

Programul pe calculator, asociat acestei lucrri, permite codarea surselor de informaie prinalgoritm Huffman static.

Precizarea sursei de informaie se poate face simplu, introducnd valorile probabilitilor sursei

i numrul lor. Probabilitile trebuie sndeplineasccondiia:

1pN

1ii

; 1p0 i ; N1,i (1.1.6)

Probabilitile pot fi introduse indirect, prin numere ntregi, pozitive ki, calculatorul urmnd sfactransformarea:

N

1ki

ii

k

kp

(1.1.7)

1Algoritmul se poate aplica i pentru obinerea codurilor nebinare (avnd un alfabet cu m simboluri). n acest caz segrupeazcte m simboluri.


6/49

5

ceea ce asigurndeplinirea relaiei (1.1.6).Sursa de informaie poate fi i un text scris (n caractere ASCII), cu cel puin 3 caractere diferite.

Calculatorul va nelege csimbolurile sursei (caracterele prezente n text) au probabiliti precizateprin ponderea lor n text (numr de prezene ale caracterului respectiv raportat la ntregul numr decaractere ale textului).

Programul permite i o a treia sursde informaie. Simbolurile acesteia reprezintintervale de

lungime egal, i n numr finit, de pe axreal. n acest caz datele vor consta n valorile eantioanelorunui semnal discret ( Fig.1.1.1) , mrginit n timp cu suportul finit precizat ca datde intrare M. Tot cadat de intrare calculatorul va cere i q-cuanta. Avnd aceste mrimi q (cuanta), M (numrul deeantioane) i b(i) (valorile eantioanelor), pentru gsirea simbolurilor sursei i implicit a numrului lor

N, calculatorul va proceda astfel: va cuta eantioanele de valoare minimi maxim: min; max;

va calcula 1]2

minmax[

N unde [ ] semnificpartea ntreag;

Fig.1.1.1 Sursde informaie semnal discret

va calcula 1]minmax

[

q

N unde [ ] semnificpartea ntreag;

va atribui sursei de informaie primare simbolurile: [ min, min + q ); [min+q, min+2q); ...;[min+(N-1)q,min+Nq)

va calcula probabilitatea simbolurilor ca fiind egale cu fraciunea din numruleantioanelor M, ce au valori cuprinse n intervalele ce definesc simbolurile. Este posibildesigur srmnsimboluri cu probabilitate 0.

n toate cele 3 cazuri se vor calcula i se vor putea vizualiza:a) probabilitile sursei primare;

b) datele asociate sursei i codrii:- entropia sursei primare H(S);- entropia maxim a sursei primare Hmax(S);- eficiena sursei primare S;- entropia sursei secundare (eficiena codrii) H(X);- lungimea medie a cuvintelor de cod L;- redundana sursei primare R(S)=Hmax(S)-H(S);- redundana relativa sursei primare S=1-S;- redundana sursei secundare X=1-H(X).

c)

cuvintele de cod;d) graful codrii;

Nq

b 1b 2 =maxim

b 3

b(4)=minim

b M

q


7/49

6

e) schema algoritmului Huffman (numai pentru cazul codrii cu cuvinte de lungimevariabil);

f) n cazul sursei semnal discret se pot vedea i graficul semnalului precum ivalorile eantioanelor.

Desfurarea lucrrii

a). Rulai programul cobsinf.exe selectnd opiunea Demonstraie. Selectai pe rnd cele trei feluri desurse de informaie (tablou, text i semnal discret), i pentru fiecare surssolicitai o codare bloc i ocodare prin algoritmul Huffman static. Urmrii aplicarea algoritmului.

b). Alctuii surse de informaie de forma celor prezentate i codai-le bloc i prin algoritmul Huffmanstatic, calculnd n fiecare caz entropia sursei, eficiena sursei, lungimea medie a cuvintelor coduluiobinut, precum i eficiena codrii. Pornii pentru nceput cu surse tablou mai simple, apoi mriinumrul de simboluri. Utilizai ulterior i surse text sau semnal discret.c) La sfritul lucrrii de laborator se va efectua test asupra cunotinelor acumulate. Durata acestuiaeste aproximativ constant i independent de numrul de studeni ce efectueaz simultan testul(calculatorul poate testa pn la 4 studeni simultan n sensul c afieazpe rnd date pentru cei

4n studeni i apoi ntreabpe rnd, n aceeai ordine studenii, timpii de afiare i de chestionarerezervai fiecrui student sunt constani i nu influeneazpe cei rezervai altuia). Rezultatul testului seva concretiza printr-o not, calculatautomat de calculator.

1.2. Algoritmul Huffman dinamic

Compresia este procesul de minimizare a spaiului ocupat sau a timpului necesar transmiteriiunei anumite cantiti de informaie.

Metodele de compresie pot fi mprite n: Metode de compresie cu pierdere; Metode de compresie frpierdere.

Metodele de compresie cu pierdere de informaie sunt folosite n special n transmitereasemnalului audio i video, unde pierderea de informaie are ca rezultat o scdere a calitii sunetului,respectiv imaginii.

Compresia de date fr pierdere, prezent n programele de arhivare, n sistemele detransmisiune a datelor, a evoluat de-a lungul timpului pornind de la algoritmi simpli (suprimareazerourilor, codarea pe iruri) i ajungnd la algoritmii compleci folosii n prezent.

Metodele de compresie fr pierderi au la baz ideea c n general cantitatea de informaieprelucrat(transmis, depozitat) conine o anumitredundance se datoreaz: Distribuiei caracterelor (unele caractere au o frecvende apariie mult mai mare dect altele);

Repetrii consecutive a unor caractere; Distribuiei grupurilor de caractere (unele grupuri sunt mult mai frecvente dect altele i n plusexistgrupuri care nu apar deloc);

Distribuiei poziiei (unele caractere sau grupuri ocuppoziii prefereniale, predictibile n anumiteblocuri de date).

Avnd n vedere toate aceste tipuri se poate nelege de ce o anumit tehnic de compresiepoate da un rezultat bun pentru un anumit tip de surse, pentru altele nsrezultatul fiind dezastruos. nstudiul compresiei se urmrete obinerea unui algoritm care sofere o compresie ct mai bunpentrutipuri de surse ct mai diferite.

Aprecierea cantitativa compresiei realizate se face utilizndfactorul de compresie, definit ca:

uc

c

nFn

(1.2.1)


8/49

7

unde nueste lungimea n bii a mesajului iniial i nclungimea de compresie.

Algoritmul Huffman dinamic

Algoritmii de tip Huffman static au dezavantajul cnecesitcunoaterea prealabila statisticiisursei. Acest dezavantaj poate fi nlturat utiliznd un algoritm dinamic.

Algoritmul Huffman dinamic este un algoritm de compresie. Mesajele au fost deja codate nprealabil, dar neeficient, cu un cod bloc, de lungime nbii/cuvnt. Ideea de bazn aceastcodare estefolosirea pentru codarea unui simbolsi+1din mesaj a unui graf de codare, ce este un arbore care crete,dintr-un punct iniial (numit surs) i care este construit pe baza primilor isimboluri din mesaj. Duptransmiterea simboluluisi+1se va revizui arborele de codare n vederea codrii simboluluisi+2.

Codarea presupune la fiecare pas transmiterea codului aferent simbolului de intrare imodificarea corespunztoare a grafului i a codului. Dac n mesajul transmis este un simbol nou,adicun simbol care n-a mai aprut n mesaj, se transmite mai nti codul frunzgoali apoi cei nbiiafereni simbolului nou aprut. Frunza goalare semnificaia curmeazun nou simbol. Frunza goalse codificca un mesaj oarecare, dar ponderea sa ntodeauna va rmne nul.

Exemplu:n continuare se prezintevoluia arborelui (grafului) asociat codului n timpul codrii mesajului Mi =aaabccc:

Obs:Semnificaia notaiilor este:

-pentru nod:

- x: numr de ordine (crete de la stnga spre dreapta i de jos n sus pe linii);- p: ponderea cumulatdin nodurile aferente.

- pentru frunz(nod terminal):

- x: numr de ordine;- p: pondere (numr de apariii ale respectivului simbol);- y: simbolul.

Frunza goal, notatcu "0", este de pondere 0.- pentru ramur: - spre stnga codare cu zero;

- spre dreapta codare (atribuire) cu unu.

1. Mi = a

2. Mi = aa

px

x yp

1

0 1

10

1 2

3

a

Codurile sunt: 0 - 0a - 1

Mesajul transmis este: a

2

0 2

10

1 2

3

a


Mesajul transmis este: a1


9/49

8

3. Mi = aaa

4. Mi = aaab

5. Mi = aaabc

6. Mi = aaabcc

Deoarece ponderea nodului c este mai mare dect ponderea nodului b se va face interschimbareantre noduri, realizndu-se o rearanjare a arborelui:

3

0 3

10

1 2

3

a


Mesajul transmis este: a11

Codurile sunt: 0 - 00a - 1b - 01

Mesajul transmis este: a110b

4

1 3

10

3 4

5

a

0 1

10

1 2 b

Codurile sunt: 0 - 000a - 1b - 01c - 001

Mesajul transmis este: a110b00c

5

2 3

10

5 6

7

a

1 1

10

3 4 b

0 1

10

1 2 c


Mesajul transmis este: a110b00c001

6

3 3

10

5 6

7

a

2 1

10

3 4 b

0 210

1 2 c


10/49

9

7. Mi = aaabccc

n urma rearanjrii arborelui se obine:

Dacse presupune csimbolurile mesajului de la intrare au fost codate n prealabil cu un codbloc, cu n=8 bii/cuvnt vom avea lungimea mesajului iniial:Considernd caracterele n mesajul iniial codate pe 8 bii, lungimea acestuia este:

nu=78=56 bii (1.2.2)

Mesajul comprimat (a110b00c00101) are:

nc=83+10=34 bii (1.2.3)

Rezultun factor de compresie:

u

c

nF 1,7n


b - 001c - 01


6

3 3

10

5 6

7

a

1 2

10

3 4 c

0 1

10

1 2 b


b - 001c - 01Mesajul transmis este: a110b00c00101

7

4 3

10

5 6

7

a

1 3

10

3 4 c

0 1

10

1 2 b



7

3

0

5

7

a 4

1

6

1 3

10

3 4 c

0 1

10

1 2 b


11/49

10

Desfurarea lucrrii:

a) Se lanseazexecutabilul dHuffman.exe din directorul Huffman Dinamic, dup care se introduceparola TTI. Rulai programul, selectnd opiunea Demonstraie, pentru codare i decodare.b) Se verific, cu programul, exemplul luat n aceastlucrare, selectnd pe rnd compresia, respectivdecompresia prezentate.

c) Pentru compresie i decompresie se alege cte un exemplu oarecare asemntor cu cel prezentat nlucrare. Se realizeazcompresia/decompresia, dupcare, cu programul, se verificrezultatele obinute.d) La sfritul lucrrii de laborator se va efectua un test asupra cunotinelor acumulate. Rezultatultestului se va concretiza printr-o not, calculatautomat de calculator.

1.3. Algoritmi de compresie de tip LZ

Cu toate calgoritmii de compresie Huffman, static sau dinamic, sunt cei mai performani (dinpunct de vedere al factorului de compresie) relativ la sursele frmemorie, aceastconcluzie nu estevalabili pentru sursele cu memorie, surse frecvent ntlnite n practic.

Algoritmii de compresie de tip LZ fac parte din categoria tehnicilor de dicionar adaptive. Eleservesc (n special) la compresia fiierelor de tip text, fiiere ce se caracterizeaz prin repetareafrecventa unor subiruri.

Ideea de bazn algoritmii LZ este nlocuirea unor subiruri ale mesajului cu cuvinte de cod,astfel nct, la o nouapariie a unui subir sse transmitdoar codul asociat lui.

Algoritmul LZ 77Mesajul de intrare este trecut printr-un buffer de lungime N. Bufferul este divizat n dou

blocuri distincte numite Lempel i Ziv, ca n Fig. 1.3.1.

Fig. 1.3.1. Bufferfereastrutilizat n algoritmul LZ77

Mesajul de ieire constntr-o succesiune de triplete de forma P, L, A. Compresia decurgeastfel:

-se ncarcprimele NZcaractere din mesajul de intrare n blocul Ziv;-se transmite la ieire tripletul 0, 0, x, unde x reprezintprimul caracter (liter) din mesajul de

intrare (aflat pe poziia 1 n blocul Ziv);se deplaseazcu o poziie mesajul de intrare n blocul Ziv, astfel nct x ajunge acum n poziia

NL. Din acest moment:-se cautn blocul Lempel un subir, S, care este identic cu cel mai lung subir, S, care ncepe

n poziia 1 a blocului Ziv i este coninut n ntregime n blocul Ziv. Subirul S trebuie neaprat snceapn blocul Lempel, dar poate ssew sfreascn blocul Ziv. Dacun astfel de subir, S, exist,atunci se va transmite tripletul P, L, A, unde P = poziia de la care ncepe subirul S; L = lungimeasubirurilor S i S; A = litera ce succede subirul S n mesajul de intrare.

Dac nu exist nici un subir S care s coincid cu cel mai scurt subir S, atunci se vatransmite tripletul 0, 0, x, unde x are aceeai semnificaie ca i mai sus;

-se deplaseazmesajul de intrare pncnd, dupcaz, A sau x ajung pe poziia NLi procesulde cutare se reia pncnd tot mesajul a trecut prin blocul Ziv.

Lempel ZivIeiremesaj

Intraremesaj

1 2 NL 1 2 NZ


12/49

11

Decompresia presupune, n principal, aceleai etape. Utiliznd tripleii recepionai, se adaugsubiruri n blocul Ziv mesajului deja decomprimat, subiruri aflate deja n blocul Lempel urmnd ca,mai apoi, toate sfie deplasate n blocul Lempel.

Observaie:este posibil sse renune la cel de-al doilea zero din tripletul 0, 0, x, el fiind redundant.Cei trei componeni ai tripletului P, L, A sunt codai binar bloc, separat. Astfel, codul pentru

P are lungimea:

kP= log2(NL+1) (1.3.1)

(trebuie codat i 0 din situaia 0, 0, x sau 0,x), iar pentru L:

kL= log2(NZ1) (1.3.2)

considernd doar varianta 0, x. Caracterele de tipul A pot fi codate, de exemplu, ASCII.Din relaiile (1.3.1) i (1.3.2) rezultc, pentru o buncompresie, NL+1 i NZ1 trebuie sfie

puteri ntregi ale lui 2. n relaia (1.3.2) s-a luat NZ1 i nu doar NZ deoarece, n situaia extrem a

lungimii maxime pentru subirul S, NZ va fi egal cu lungimea subirului S plus unu; acest unurezervliterei A un loc n blocul Ziv.

Exemplu Fie parametrii NL =7 i NZ =4, iar mesajul de intrare aaababacacab. Aplicareaalgoritmului LZ 77 asupra acestui mesaj de intrare este ilustratn Fig. 1.3.2 a).

Mesajul comprimat este, aadar: 0a72b63c73b, sau n binar:000a11110b11011c11111b. Fig. 1.3.2. b) prezintun exemplu de decompresie.

1 2 3 4 5 6 7 1 2 3 4 P L Aa a a b 0 a

a a a b a 7 2 ba a a b a b a c 6 3 c

a a b a b a c a c a b 7 3 ba) compresia mesajului aaababacacab

1 2 3 4 5 6 7 1 2 3 4 P L Aa 0 a

a a a a b 7 3 ba a a a b a a c 3 2 c

a a a b a a c b a c 4 2 c

b a a c b a c a c b c 3 3 cb) decompresia mesajului 0aa73b32c42c33cFig. 1.3.2. Exemplu de aplicare a algoritmul LZ77

Algoritmul LZ78Spre deosebire de varianta anterioar, la LZ78 blocul Lempel este un dicionar n continu

cretere. De asemenea, nu existteoretic nici o limitare a blocului Ziv.Algoritmul LZ78 este, n esen, urmtorul:-se iniializeazdicionarul (blocul Lempel) cu un ir nul;-se ncarcmesajul de intrare n blocul Ziv;-se transmite n clar primul caracter i se introduce i n dicionar la poziia 1. Cele doupoziii

ale dicionarului (notate cu 0 i 1) sunt, n acest moment codate prin 0 i 1. Din acest moment:-se cautn dicionar un subir, S, identic cu cel mai lung subir, S, din blocul Ziv. Bineneles,S ncepe din prima poziie a blocului Ziv. Dacexistun astfel de subir, S, atunci se transmite codul


13/49

12

aferent urmat de caracterul A ce urmeazlui S n mesajul de intrare. n plus, dicionarul se mbogetecu o poziie, poziie unde se trece subirul SA. Dac nici mcar primul caracter, x, din Ziv nu seregsete n dicionar, atunci se transmite 0x, unde 0 semnificsubirul din prima poziie, codat princuvntul de cod 000.

Observaie:Atunci cnd dicionarul ajunge la un numr de elemente egal cu 2k, tuturor codurilor

elementelor anterioare li se adaugcai prefix 0, iar ultimul subir va fi codat prin 100.

Exemplu:n Fig. 1.3.3 a) se prezintun exemplu de compresie utiliznd algoritmul LZ78. Mesajuluide intrare este cel din exemplul anterior, aaababacacab. Mesajul comprimat rezultat estea1a0b1b1c6a3, sau n binar a1a0b01c110a011. n Fig. 1.3.3 b) se prezint un exemplu dedecompresie, utiliznd acelai algoritm. Mesajul comprimat (de intrare) este a1b3b5a3a. Rezultatuldecompresiei este aababcabcaaba.

b) compresia mesajului aaababacacab;

b) decompresia mesajului a1b3b5a3a

Fig. 1.3.3 Exemplu de aplicare a algoritmul LZ78.

Decompresia presupune urmtorul algoritm:-se citete primul caracter (codul ASCII aferent); acest caracter se introduce n dicionar la poziia 1 ise genereazi la ieire; n continuare procedura este:-se citeta codul poziiei la care se gsete subirul transmis. Acest cod conine:

k = sup(log2n) bii (1.3.3)

unde sup(x) reprezintaproximarea prin adaos a lui x, iar n dimensiunea momentana dicionarului;-se citete din dicionar subirul S aflat la poziia cititanterior i se genereazla ieire;

Blocul Ziv

a a a b a b a c a c a b aa a b a b a c a c a b 1a

b a b a c a c a b 0ba b a c a c a b 1ba c a c a b 1c

a c a b 6ab 3

Mesajulde ieire0

1 a2 aa3 b4 ab5 c6 ac7 aca8

Blocul Lempel(dicionarul)

Mesaj decomprimat

a aa a b 1b

a a b a b c 3b

a a b a b c a b c a 5a

a a b a b c a b c a a b a 3a

Mesajcomprimat0

1 a2 b3 ab4 c5 abc6 abca

7

Blocul Lempel(dicionarul)


14/49

13

-se citete din mesajul recepionat urmtorul caracter, A (n cod ASCII), i se genereazi acesta laieire. DacA este un nou caracter, atunci se introduce n dicionar la o noupoziie;-se introduce n dicionar subirul SA la urmtoarea poziie;Procesul se repetpnla epuizarea mesajului recepionat.

Algoritmul LZW (LempelZivWelch)

Modificarea esenial adus de algoritmul LZW este faptul c att compresorul ct idecompresorul cunosc simbolurile (caracterele) componente ale mesajului. Cu alte cuvinte, nainte denceperea propriu-zis a compresiei (decompresiei) dicionarul este iniializat cu toate caracterele

posibil a fi emise.(n exemplul urmtor, ilustrat n Figura 3.4a, dicionarul este iniializat cu simbolurilea00, b01, c10.) n acest fel nu se mai trimite informaie despre urmtorul caracter la fiecare pas. Oaltmodificare o constituie existena unui prefix, P, care se memoreazde la un pas la urmtorul.

Algoritmul compresiei este:-se iniializeazdicionarul (aa cum s-a descris anterior);-se citete primul caracter i se memoreazca i prefix, P. Din acest moment:-se citete urmtorul caracter, notat E. Se cautn dicionar subirul PE. Dacacest subir exist, atuncise trece la pasul urmtor, fra emite nimic i fra aduga nimic n dicionar. Singura modificare este

c acum PE devine prefix pentru pasul urmtor. Dac subirul PE nu exist n dicionar, atunci seexecuturmtoarele operaii:

-se trimite la ieire codul aferent subirului P;-se trece pe post de prefix caracterul E (EP);-se adaugn dicionar subirul PE la urmtoarea poziie liber.

Procesul continun acest fel pnla epuizarea ntregului mesaj de intrare.

Observaie:La fel ca i la LZ-78, pe vreme ce dicionarul crete trebuie modificat corespunztor codulbinar loc asociat.

Algoritmul decompresiei este asemntor compresiei. Diferena este csimbolul E nu se citete directde la intrare (ca i la compresie) ci doar dupce s-a decodat codul recepionat. Mesajul decomprimat se

poate citi fie de la E (exceptnd primul simbol, care se citete de la P), fie prin compunerea iruluidecodat.

Exemplu: Fig. 1.3.4. prezint cte un exemplu de compresie i decompresie utiliznd algoritmulLZW. Pentru compresie s-a ales ca mesaj de intrare: aaababacacab, acelai ca i n exempleleanterioare. Mesajul comprimat este: 031052081, sau n binar0011001000101010000010000001. Pentru decompresie s-a ales mesajul 013205, car n binar seexprim: 0001011010000101. Mesajul decomprimat este: ababcaabc.

Desfurarea lucrrii:a) Rulai programul pe calculator, utiliznd opiunea demonstrativ, urmrind aplicarea celor treialgoritmi la compresie i decompresie. Aflai pentru fiecare exemplu i factorul de compresie.

b). Alctuii, utiliznd trei sau patru litere, mesaje de circa 10 litere lungime. Comprimai mesajeleindependent de program i verificai rezultatele cu ajutorul programului. Pentru decompresie utilizaimesajele comprimate de colegi, fr a cunoate originalul. Confruntai rezultatele decomprimrii cucele originale. Calculai n fiecare caz factorul de compresie, considernd corice liter(caracter) sescrie n binar pe 8 bii.c) La sfritul lucrrii de laborator se va efectua test asupra cunotinelor acumulate, prin intermediul

programului pe calculator. Testul const din: 1o compresie i 2o decompresie, a unui mesaj alesaleatoriu de ctre calculator printr-unul dintre cei trei algoritmi (de asemenea ales aleatoriu de

program) i 3 cinci ntrebri teoretice fiecare cu un rspuns corect din cinci propuse, avnd ca temalgoritmii de compresie.


15/49

14

Dicionarul

a 0=00b 1=01c 2=10

Prefix

P

Mesaj deintrare

E

ir cutatn dicionar

PE

irtransmis

Codtransmis

ir adugat

n dicionar

Cod

adugatn dicionar

aaaaba

bbac

accab

aaa

ba

baca

ca

b

aaaa

aabbaab

babac

ca

acca

cabb

a

aaba

bac

a

cab

0=00

3=111=0010=000

5=1012=010

0=0000

8=10001=0001

aa

aabbaab

bacca

ac

cab

3=11

4=1005=1016=110

7=1118=1000

9=1001

10=1010

a) compresia mesajului aaababacacab;

Dicionarula 0=00

b 1=01c 2=10

Prefix

P

Mesaj deintrare

E

ir cutatn dicionar

PE

irrecepionat

decodat

Codrecepionat

ir adugatn dicionar

Codadugat

n dicionar

abaab

caaab

ba

bc

aabc

abbaababc

caaaababc

abab

c

aabc

013

2

05

abba

abc

caaa

3=114=100

5=101

6=1107=111

b) decompresia mesajului 013205;Fig. 1.3.4. Exemplu de aplicare a algoritmului LZW


16/49

15

L2. Coduri simple corectoare de o eroare

2.1. Codul Hamming

2.1.1. Cod Hamming corector de o eroare

Codurile Hamming constiruie prima clasde coduri bloc liniare corectoare de erori i au fost

propuse de R. Hamming n 1950.Codul Hamming este un cod protector. Scopul codrii este acela de a adapta sursa de

informaie la canalul de transmisie. n cazul de fasursa este deja codati se face o codare pentruprotecia informaiei. Acest lucru se realizeaz prin mrirea redundanei (prin creterea suportuluibinar; biilor de informaie adugnduse biii de control). Biii de control au ca scop de a crea legturi,relaii ntre biii de informaie. Aceste relaii folosesc codorului pentru a calcula biii de control ifolosesc decodorului pentru a verifica corectitudinea transmisiei.

Codul Hamming este un cod nesistematic (simbolurile de control sunt intercalate printresimbolurile informaionale, situndu-se pe poziii puteri ale lui 2).

2.1.1.1. Codarea codului Hamminmg corector de o eroare

Particularitatea codului liniar Hamming corector de o eroare const n forma matricii decontrol, H, care are fiecare coloanstructuratprin reprezentarea binara numrului zecimal de ordineal coloanei respective. Din acest motiv, corectorul Z, calculat cu relaia TZ H V , decodat din binarn zecimal, indicnumrul de ordine zecimal al bitului eronat din cuvntul recepionat.Distana minima acestui cod este:

cd 2e 1 3 ,

unde ecreprezintnumrul de erori corectabile.Se considercodul cu parametrii: n=7, numrul de simboluri n cuvnt;

m=3, numrul de simboluri de control n cuvnt; k=4, numrul de simboluri de informaie n cuvnt.Secvena de informaie este:

3 5 6 7i i i i i

i secvena de control:

1 2 4C C C C

astfel nct cuvntul de cod rezultat va fi:

1 2 3 4 5 6 7V C C i C i i i

Codarea nseamncalculul simbolurilor de control C1, C2, i C4cnd se dau simbolurile de informaiei3, i5, i6, i7.

Relaia de codare:

1

2

3

T4

5

6

7

C

C

0 0 0 1 1 1 1 i

H V 0 0 1 1 0 0 1 1 C 0

1 0 1 0 1 0 1 i

i

i

(2.1.1)

undeH reprezintmatricea de control, ce este de dimensiune mn.


17/49

16

Sau n formexplicit:

1 3 5 7C i i i

2 3 6 7C i i i

4 5 6 7C i i i

(2.1.2)

Suma fcndu-se modulo doi.

Exemplul 1:Pentru n=7, k=4, m=3 i secvena de informaie i=1010, gsii cuvntul V de cod.

Rezolvare:

Se observcexist4 simboluri de informaie: i3, i5, i6, i7. Cuvntul de cod,V, se poate scrie sub formliterar: 1 2 3 4 5 6 7V C C i C i i i . Avem aadar 7 simboluri ce alctuiesc cuvntul de cod i 3 bii de control.

Rezultcmatricea de control, H, va conine 3 linii i 7 coloane.Din relaia de codare (2.1.1), rezultrelaiile de calcul a biilor de control:

1 3 5 7C i i i 1 0 0 1

2 3 6 7C i i i 1 1 0 0

4 5 6 7C i i i 0 1 0 1

Rezultcuvntul de cod:V=1011010

2.1.1.2. Decodarea codului Hamminmg corector de o eroare

Avnd cuvntul recepionat

'

V , compus din 7 imboluri:' ' ' ' ' ' ' '

1 2 3 4 5 6 7V C C i C i i i

se poate calcula corectorul codului Hamming cu relaia:

T4

'2

1

z

z H V z

z

(2.1.3)

Matricea de control:

1 i nm,nH h h h L L (2.1.4)

unde, pentru acest caz se observcm=3 i n=7. Coloana hiexprimn cod binar natural numrul deordine al coloanei respective, cu bitul cel mai puin semnificativ n linia m.

Din relaia (2.1.3) rezult:' ' ' '

4 4 5 6 7z C i i i ' ' ' '

2 2 3 6 7z C i i i ' ' ' '

1 1 3 5 7z C i i i

(2.1.5)


18/49

17

Decodarea zecimala corectorului z, indicpoziia erorii, daceste una singur, n cuvntul 'V . Va fieronat simbolul cu indicele r, dat de relaia:

4 2 1r 4z 2z z (2.1.6)

Cuvntul recepuionat se mai poate scrie ca fiind:

'V V ,unde reprezintcuvntul eroare.Relaia (2.1.3) va deveni:

T T' T

rz H V H V H h

unde poziia erorii se calculeazcu relaia (2.1.6).

Obs:n cazul n care existdouerori, sunt cazuri n care nu numai cnu se corecteaznici o eroare,dar se mai eroneazun al treilea simbol, rezultnd la recepie trei simboluri eronate.

Exemplul 2:Decodai cuvntul recepionat V=1001001

Rezolvare:

Cuvntul de cod recepionat se poate scrie ca fiind:

' ' ' ' ' ' ' '1 2 3 4 5 6 7V C C i C i i i

V = 1 0 0 1 0 0 1Relaia (2.1.5) va deveni:

' ' ' '4 4 5 6 7z C i i i 1 0 0 1 0

' ' ' '2 2 3 6 7z C i i i 0 0 0 1 1

' ' ' '1 1 3 5 7z C i i i 1 0 0 1 0

Aadar, poziia eronateste:

4 2 1r 4z 2z z 4 0 2 1 1 0 2

Rezultcuvntul eroare:0100000

Se poate scrie:'

V V 1001001 0100000 1101001

Rezultsecvena de informaie:

3 5 6 7i i i i i 0001

2.1.2. Cod Hamming corector de o eroare i detector de douerori

Condiia necesari suficientpentru ca un cod spoatsimultan corecta maxim terori i a detectamaxim eerori este ca distana minima codului sfie:

d t e 1 1 2 1 4, e>t

2.1.2.1.Codarea codului Hamminmg corector de o eroare i detector de doueroriPentru a nltura dezavantajul codului Hamming corector de o eroare (acela de a erona

suplimentar, la depirea capacitii de corecie a codului, t>1) i de al face mai util n aplicaii


19/49

18

practice, codul a fost modificat n sensul creterii distanei minime de la d=3 la d=4, ceea ce permitedetecia erorilor duble.

Creterea distanei de cod de la 3 la 4 s-a fcut prin adugarea unui simbol de controlsuplimentar, numit simbol de control al paritii, C0, structura cuvntului de cod devenind:

0 1 2 3 4 5 6 7V C C C i C i i i

Matricea de control se modifici are structura:

'

0 0 0 0 1 1 1 1

0 H 0 0 1 1 0 0 1 1H

1 1 0 1 0 1 0 1 0 1

1 1 1 1 1 1 1 1

Relaia de codare va fi:

0

1

2

3' T

4

5

6

7

C

CC0 0 0 0 1 1 1 1

i0 0 1 1 0 0 1 1H V 0

C0 1 0 1 0 1 0 1

i1 1 1 1 1 1 1 1

i

i

(2.1.7)

Sau n formexplicit:

1 3 5 7C i i i

2 3 6 7C i i i

4 5 6 7C i i i

0 1 2 3 4 5 6 7C C C i C i i i

(2.1.8)

Exemplul 3:Fie secvena de informaie i=1010, gsii cuvntul V de cod.

Rezolvare:

Se observcexist4 simboluri de informaie: i3, i5, i6, i7. Cuvntul de cod, V, se poate scrie sub formliterar: 0 1 2 3 4 5 6 7V C C C i C i i i . Avem aadar 8 simboluri ce alctuiesc cuvntul de cod i 4 bii de

control. Rezultcmatricea de control, H, va conine 4 linii i 8 coloane.Din relaia de codare (2.1.8), rezultrelaiile de calcul a biilor de control:

1 3 5 7C i i i 1 0 0 1

2 3 6 7C i i i 1 1 0 0

4 5 6 7C i i i 0 1 0 1

0 1 2 3 4 5 6 7C C C i C i i i 1 0 1 1 0 1 0 0

Rezultcuvntul de cod:V=01011010


20/49

19

2.1.2.2. Decodarea codului Hamminmg corector de o eroare i detector de doueroriAvnd cuvntul recepionat 'V , compus din 8 imboluri:

' ' ' ' ' ' ' ' '0 1 2 3 4 5 6 7V C C C i C i i i

se poate calcula corectorul codului cu relaia:

T

4

2' '

0 1

0

z

z zZ H V

z z

z

(2.1.9)

Unde: z, reprezintcorectorul de la codul Hamming corector de o eroare; z0, reprezintsimbolul binar, 0 sau 1, cu ajutorul cruia se pot detecta erori pare (z0=0).Existpatru cazuri:

Cazul 1:

0

z 0

z 0

nu existerori sau nu existerori detectabile prin cod.

Cazul 2:

0

z 1

z 0

se face detecia erorilor duble.

Cazul 3:

0

z 0

z 1

simbolul C0este eronat.

Cazul 4:

0

z 0

z 1

existo eroare corectabil.Va fi eronat simbolul cu indicele r-1, unde r este dat de relaia:

4 2 1 0r 4z 2z z z (2.1.10)

Exemplul 4:Decodai cuvntul recepionat V=01001010

Rezolvare:

Cuvntul de cod recepionat se poate scrie ca fiind:

' ' ' ' ' ' ' ' '0 1 2 3 4 5 6 7V C C C i C i i i

V = 0 1 0 0 1 0 1 0


21/49

20

Relaia (2.1.5) va deveni:

' ' ' '4 4 5 6 7z C i i i 1 0 1 0 0

' ' ' '2 2 3 6 7z C i i i 0 0 1 0 1

' ' ' '1 1 3 5 7z C i i i 1 0 0 0 1

' ' ' ' ' ' ' '0 0 1 2 3 4 5 6 7z C C C i C i i i 0 1 0 0 1 0 1 0 1

Rezultcavem situaia cazului 4, cnd existo eroare corectabil.Aadar, rezultr:

4 2 1 0r 4z 2z z z 4 0 2 1 1 1 1 4

Deci va fi eronat simbolul cu indicele r-1, adic4-1=3, i3.Rezultcuvntul eroare:

00010000

Se poate scrie: 'V V 01001010 00010000 01011010

Rezultsecvena de informaie:

3 5 6 7i i i i i 1010

Desfurarea lucrrii:

a) Se lanseazexecutabilul Hamming.exe din directorul Hamming, dupcare se introduce parola TTI.Rulai programul, selectnd opiunea Demonstraie, pentru toate cele patru variante prezentate.

b) Se verific, cu programul, toate exemplele luate n aceast lucrare, selectnd pe rnd codurile

prezentate.c) Pentru fiecare cod n parte, se alege cte un exemplu de codare/decodare, asemntor cu celeprezentate n lucrare, cu observaia ca secvena de informaie s conin 11 bii de informaie, lacodare, respectiv cuvntul recepionat s conin 15/16 bii, la decodare. Se realizeazcodarea/decodare, dupcare, cu programul, se verificrezultatele obinute.d) La sfritul lucrrii de laborator se va efectua un test asupra cunotinelor acumulate. Rezultatultestului se va concretiza printr-o not, calculatautomat de calculator.

2.2. Codul ciclic

Codurile ciclice sunt utilizate pentru protejarea informaiei mpotriva perturbaiilor.Codurile ciclice sunt coduri bloc (toate cuvintele au aceeai lungime, codarea i decodarea unuibloc este independentde a celorlalte).

Denumirea de ciclice provine de la proprietatea pe care o au cuvintele de cod i anume dacvi= 1001001 este cuvnt de cod atunci i vj= 0010011 i vk= 1100100 sunt cuvinte de cod . Adicorice permutare ciclica unui cuvnt de cod este un alt cuvnt de cod .

Parametrii codului sunt n (bii) lungimea cuvntului de cod, k numrul de bii de informaie percuvnt, m numrul de bii de control per cuvnt i polinomul generator g(x). Dei poate fi facuti ocodare nesistematicvom considera codul sistematic cei k bii de informaie fiind situai pe poziiilecele mai semnificative, iar cei m bii de control pe poziiile mai puin semnificative.Fiecrui cuvnt de cod i se poate ataa un polinom de grad maxim n-1:

v = vn-1vn-2vn-3......v1v0,


22/49

21

coeficienii vifiind coeficieni binari (din cmpul binar {0,1}).Polinomul asociat cuvntului va fi :

v(x) = vn-1xn-1+ vn-2x

n-2+ vn-3xn-3+ .....+ v1x + v0 (2.2.1)

Ponderea unui cuvnt reprezintnumrul de 1 din cadrul cuvntului.

Polinomul de informaie este :

i(x) = ik-1xk-1+ ik-2x

k-2+ ik-3xk-3+ .....+ i1x + i0 (2.2.2)

de grad k-1.

Pentru orice cuvnt de cod este valabilrelaia :

0xg

xvrest (2.2.3)

Deci cuvintele de cod se aleg astfel nct sfie multiplii ai polinomului g(x) numit polinomulgenerator al carui grad va fi deci m = n-k, (gm= 1):

g(x) = gmxm+ gm-1x

m-1+ gm-2xm-2+ .....+ g1x + g0 (2.2.4)

Operaiile se fac modulo (xn+ 1) .Dac, codul este corector de o singureroare atunci:

n = 2m 1. (2.2.5)

Codurile ciclice corectoare de o eroare, avnd distana de cod (distana Hamming minimntrecuvintele codului) dHmin= 3, sunt capabile scorecteze o eroare sau sdetecteze dou.

Codarea codului ciclic corector de o eroare

Codarea va fi prezentatn doumoduri nesistematicsau sistematic.

Cu relaia v(x) = i(x)g(x) se poate face codarea nesistematic, dar pentru cnu este util npracticnu va fi luatn considerare .

n continuare va fi deci prezentatcodarea sistematicunde corespondena dintre i(x) i v(x)este datprin relaia:

xg

xxirestxxixvm

m (2.2.6)

unde

xgxxi

restm

semnificrestul mpririi polinomului i(x)xmla g(x).

Operaia de adunare din ecuaia (2.2.6) este sum modulo 2 (SAU exclusiv), iar coeficieniipolinoamelor sunt din cmpul binar {0,1}.Matematic codarea poate fi facutpolinomial sau matricial.

a) Polinomial

Codarea va fi prezentatprintr-un exemplu, putnd fi uor generalizat.


23/49

22

Fie g(x) = x3+ x + 1. Deci m = 3 i cu relaia 2m 1 = n rezultcn = 7 de unde k = n m = 4. Vomavea ca atare 4 bii de informaie i = vn-1vn-2vn-3vn-4cu polinomul asociat :

i(x) = vn-1x3+ vn-2x

2+ vn-3x + vn-4 (2.2.7)

i deci i(x)xm= (vn-1x3+ vn-2x

2+ vn-3x3+ vn-1x + vn-4) x

3= vn-1x6+ vn-2x

5+ vn-3x4+ vn-4x

3

Biii de control sunt coeficienii restului mpririi lui i(x)xm/g(x).

vn-1x6+ vn-2x

5+ vn-3x4+ vn-4x

3 x3+ x + 1vn-1x

6 + vn-1x4+ vn-1x

3 vn-1x3+ vn-2x

2+ (vn-3+ vn-1)x + (vn-4+ vn-2+ vn-1)

/ vn-2x5+ (vn-3+ vn-1)x

4+ (vn-4+ vn-1)x3

vn-2x5 + vn-2x

3 + vn-2x2

/ (vn-3+ vn-1)x4+ (vn-4+ vn-2+ vn-1)x

3+ vn-2x2

(vn-3+ vn-1)x4 + (vn-3+ vn-1)x

2+(vn-3+ vn-1)x

/ (vn-4+ vn-2+ vn-1)x3+ (vn-3+ vn-2+ vn-1)x

2+ (vn-3+ vn-1)x(vn-4+ vn-2+ vn-1)x

3 + (vn-4+ vn-2+ vn-1)x + vn-4+ vn-2+ vn-1

(vn-3+ vn-2+ vn-1)x2+ (vn-4+ vn-3+ vn-2)x + vn-4+ vn-2+ vn-1

r(x) = (vn-3+ vn-2+ vn-1)x2+ (vn-4+ vn-3+ vn-2)x + vn-4+ vn-2+ vn-1, (2.2.8)

unde r(x) este restul mpririi .Conform relaiei (2.2.6) se obine :

v(x) = vn-1x6+ vn-2x

5+ vn-3x4+ vn-4x

3+ (vn-3+ vn-2+ vn-1)x2+ (vn-4+ vn-3+ vn-2)x + vn-4 + vn-2+ vn-1

Pentru cn = 7 i v(x) este de forma:

v(x) = v6x6+ v5x

5+ v4x4+ v3x

3+ v2x2+ v1x + v0 (2.2.9)

i innd cont de relaia (2.2.8) simbolurile de control vor fi date de:

v2= v4+ v5+ v6

v1= v3+ v4+ v5v0= v3+ v5+ v6 (2.2.10)Aadar cuvntul de cod va fi v = v6v5v4v3v2v1v0unde primii 4 sunt biii de informaie, iar ultimii 3 ceide control.

b) Codor cicliccu RDR (codarea matricial)

n Fig. 2.2.1 este prezentat un codor ciclic care implementeaz relaia de codare (2.2.6).Secvena de informaie, i(x), intrn codor n primele k tacte, primul bit fiind cel mai semnificativ i,de asemenea, este conectati la ieire. Pentru aceasta, ntreruptorul 1, format din poarta AND-1 este

nchis iar ntreruptorul 2, format din poarta AND-2 este deschis (vezi semnalele de comandP1i P2).n urmtoarele m tacte ntreruptorul 1 este deschis iar ntreruptorul 2 este nchis, astfel csecvena r, generatde RDR, este livratla ieirea v.


24/49

23

a) Codor ciclicRDR ;

b) Semnalele de validare

a porilor AND

Fig. 2.2.1 Codor ciclic cu RDR i semnalele de comand

Obs. Se observ c, n ultimele k tacte, la intrrile sumatorului (care adun intrarea RDR-lui cureacia sa) se regsete acelai semnal, astfel c, n aceste k tacte, n celula Ck se va introduce o

secvennulcare cur registrul pentru un nou cuvnt de cod.

Din funcionarea registrului de deplasare cu reacie rezultrelaia:

Sj= TSj-1+ vn-jU (2.2.11)

unde S reprezint starea registrului, U este o matrice coloan, iar T este matricea caracteristic aregistrului de deplasare cu reacie. Ele sunt de forma:

m

2

1

c

c

c

SM

,

1

0

0

UM

,

1-m210 gggg

1000

0100

0010

T

L

L

MLMMM

L

L

. (2.2.12)

innd cont de observaia fcutmai sus rezultcSn= 0.Considernd acelaexemplu

P1

i(x)v(x)

P1

P2

AND-1

AND-2

gm=1 gm-1 gm-2 .. g1 g0=1

Cm Cm-1 Cm-2 C1

t/Tb

t/Tb

P2

0 1 2 k=n-m n

0 1 2 k=n-m n


25/49

24

Matricea caracteristic, T, este:

011

100

010

T (2.2.13)

Utiliznd relaiile (2.2.11) i (2.2.13) pentru cazul n = 7 vom avea:S7= v6T

6U+ v5T5U + v4T

4U + v3T3U + v2T

2U + v1TU + v0U = 0 (2.2.14)

Efectund calculele rezult:

0

1

0

UT ,

1

0

1

UT 2 ,

1

1

0

UT3 ,

1

1

1

UT 4 ,

0

1

1

UT5 ,

0

0

1

UT6

(2.2.15)

Introducnd (2.2.15) n (2.2.14) i efectund calculele obinem:

v2= v4+ v5+ v6v1= v3+ v4+ v5v0= v4+ v3+ v2= v4+ v3+ v4+ v5+ v6= v3+ v5+ v6

relaii identice cu relaiile (2.2.10) deci cele douproceduri de calcul ne-au dus la aceleai rezultate .Cuvntul de cod va fi v = v6v5v4v3v2v1v0.

Decodarea codului ciclic corector de o eroare

Decodarea codului ciclic cuprinde verificarea corectitudinii cuvntului recepionat:

w(x) = vn-1xn-1+ vn-2x

n-2+ ... + v1x + v0, (2.2.16)

corectarea sau detectarea erorilor, dupdestinaia codului i apoi selecia biilor de informaie.Verificarea presupune calculul restului mpririi lui w(x) la g(x). Dacrestul este 0 se decide:

cuvnt corect recepionat. Dacnu, atunci se decide: cuvnt eronat.(Prima decizie poate fi fals, a douanu!) Pentru codurile detectoare decodarea ia sfrit aici. Pentru codurile corectoare analiza restului

permite determinarea poziiei erorilor. Acest lucru presupune existena unei corespondene biunivocentre resturile posibile i cuvintele eroare corectabile de ctre codul dat.

Daccodul este corector de o eroare, atunci decodarea decurge astfel:

1- se calculeazcorectorul zncu formula:

UTUTvz j1-n

0jj

j1-n

0j

'j

(2.2.17)

unde jreprezintcoeficienii polinomului eroare:

(x) = w(x) + v(x) (2.2.18)

2- dacz = 0 se decide cw(x) este corect w(x) = v(x)- dacz 0 atunci z = TrU, unde r este indicele coeficientului eronat. Comparm z cu TjU i gsim r.

Corecia presupune schimbarea valorii lui vr.Dac codul ciclic corecteaz mai multe erori, atunci decodarea se poate face pe seamacorespondenei amintite anterior.


26/49

25

a) Decodarea polinomialMetoda constn mprirea lui w(x) la g(x). Va rezulta un polinom rest, r(x). Dacacesta este

diferit de 0, cuvntul recepionat este eronat i prin identificarea restului r(x) cu valorile din tabelulcuvinte eroare corectori (vezi Anexe) se determinpoziia erorii i se realizeazcorecia.

Spre exemplu fie : w(x) = x6+ x5+ x3+ x2+ 1. Calculm restw(x) /g(x):

x6+ x5+ x3+ x2+ 1 x3+ x + 1x6+ x4+ x3 x3+ x2+ x + 1

x5+ x4+ x2+ 1x5+ x3+ x2

x4+ x3+ 1x4+ x2+ x

x3+ x2+ x + 1x3+ x + 1

x2

deci conform tabelului din anexeste eronat w2. Schimbnd valoarea bitului w2rezult:

w(x) = x6+ x5+ x3+ 1.

b) Decodor ciclic cu RDR (decodarea matricial)

a) schema;

gm-1

gm-1

gm-2

gm-2

g1

g1

IDENTIFICARE STARE0 0 0 1

IDENTIFICARE STARE0 0 0 1AND AND

AND AND

C1

C1Cm-1

Cm-1

P1P2

P1 P2

Cm

Cm

vn Tb

w

celula 0 celula n-1


27/49

26

b)Semnalele de validare a porilor AND ;Fig. 2.2.2. Decodor ciclic corector de o eroare

n Fig. 2.2.2. este prezentatstructura unui decodor ciclic corector de o eroare. Biii cuvntului

recepionat vor intra n schemunul dupaltul n ordine, ncepnd cu bitul vn-1.Schema de decodare conine un registru de deplasare (blocul nTb este un registru dentrziere cu n celule) cu rol de memorie, care pstreazcuvntul recepionat care intrpas cu pas idou subscheme cu RDR pentru corecie care funcioneaz n contratimp. Procedura de decodaredureaz2n tacte. n primele n tacte n memorie intrcuvntul 1 care prin poarta P1intri n primuldecodor, ieirea acestuia fiind 0 pentru cP2este nchis. n urmtoarele n tacte cuvntul 2 va intra prin

poarta P2 n al doilea decodor care are ieirea 0 deoarece P1 este nchis, n acest timp cuvntul 1prsete memoria trecnd prin sumator i este corectat de primul decodor care identificstarea 00.....1i care are acces la sumator prin P2.

Dupn = 7 tacte starea registrului va fi:

S7= v6T6

U

+ v5T5

U + v4T4

U + v3T3

U + v2T2

U + v1TU + v0U (2.2.19)care nu va mai fi 0 dect n cazul n care nu avem eroare.Daceroarea afecteazbitul vrstarea registrului de deplasare cu reacie dupintrarea ntregului cuvnteste:

S7= v6T6U+ v5T

5U + .... + vrTrU + .... + v1TU + v0U (2.2.20)

Deoarece la emisie S7= 0 i vj= vjpentru j r i vr= vr+ 1 rezult:

S7+ S7= S7= TrU = z (2.2.21)

Pe durata urmtoarelor n = 7 tacte RDR din prima subschemva evolua numai sub aciunea

semnalului de reacie i dupn-r-1 tacte se va ajunge n starea:

S7+n-r-1= Tn-r-1S7= T

n-1U =

0

0

1

(2.2.22)

n acela timp printr-o deplasare cu n-r-1 tacte eroarea care se afla n celula r va ajunge n

celula n-1. Detectorul va sesiza starea S7+n-r-1fixi prin poarta P2care este nchisva emite semnalulde corecie (blocul IDENTIFICgenereazun 1L) care se nsumeazcu bitul eronat aflat n celula n-1,astfel la ieirea sumatorului final se va obine cuvntul corectat.

0

0

n-1

n-1

n

n

2n

2n

t / Tb

t / Tb

P2

P1

..

..

..

..


28/49

27

Desfurarea lucrrii:

a) Rulai programul de pe calculator alegnd butonul Demonstraie de la codul ciclic i se urmreteo codare i o decodare.

b) Alegeiv un polinom generator i secvena de informaie i efectuai o codare, apoi alegndpolinomul generator i biii recepionai o decodare. Verificai apoi rezultatul cu ajutorul calculatorului.c) La sfritul lucrrii de laborator se efectueaz testul de verificare a cunotinelor acumulate prin

intermediul calculatorului. Testul constn a rspunde la 5 ntrebri teoretice, fiecare avnd un rspunscorect din cele cinci propuse, i efectuarea unei codri i a unei decodri pornind de la polinomulgenerator i secvena de informaie respectiv secvena recepionatgenerate aleator de calculator.


29/49

28

L3. Coduri ciclice corectoare de erori multiple

3.1 Codul BCH

Codurile BCH fac parte din categoria codurilor ciclice.Cuvintele de cod BCH vor avea deci structura ca i cele de cod ciclic:

v = vn-1vn-2... v1v0 vjGF(2q, p(x)) j = 0 n-1 (3.1.1)

unde coeficienii ujsunt coeficieni binari (fac parte din cmpul binar 0, 1).Polinomul corespunztor acestui cuvnt fiind:

v(x) = vn-1xn-1+ vn-2x

n-2+ ... + v1x + v0 (3.1.2)

adicun polinom de grad n - 1.Polinomul de informaie este:

i(x) = ik-1xk-1+ ik-2xk-2+ ... + i1x + i0 (3.1.3)

care este un polinom de gradul k - 1.Cuvintele de cod se aleg astfel nct sfie multiplii ai polinomului generator g(x) i deci acesta

va trebui sa fie un polinom de gradul m = n k:

g(x) = gmxm+ gm-1x

m-1+ ... + g1x + g0 (3.1.4)

Coeficienii polinomului g(x) sunt de asemenea coeficieni binari.Deoarece polinomul trebuie s aibgradul m rezult c gm= 1, iar g0 trebuie s fie i el egal cu 1

pentru caltfel putem da factor pe x i gradul polinomului va fi mai mic dect k.Polinomul g(x) este deci de forma:

g(x) = xm+ gm-1xm-1+ ... + g1x + 1 (3.1.5)

Cuvintele de cod sunt elemente ale cmpului Galois GF(2q) generat de un polinom primitiv p(x) degrad q (sunt clase de resturi modulo p(x)), cmp obinut aa cum este prezentat n Anexa.

Codarea BCH

Codarea codurilor BCH poate fi fcutn doumoduri:

a) Cu relaia

v(x) =i(x)g(x) (3.1.6)

care conduce la obinerea unui cod nesistematic (relaie mai puin utilizat).

b) Pentru obinerea unei structuri sistematice, la care informaia s se gseasc nemodificat pepoziiile cele mai semnificative se folosete relaia:

v(x) = i(x)xm+ rest (i(x)xm/g(x)) (3.1.7)

Aceastrelaie se mai poate scrie:


30/49

29

v(x) =q(x)g(x) = vn-1xn-1+ vn-2x

n-2+ ... + v1x + v0 (3.1.8)

deci se obine un cuvnt de cod ciclic care este multiplu a lui g(x) i este format din simbolurile deinformaie aflate pe poziiile cele mai semnificative (primele k) i m simboluri de control determinatede restul mpririi lui i(x)xmla g(x).Relaia (3.1.8) poate fi adussub forma HvT= 0.

0

v

v

v

hh...h00...00

00...hhh...h0

00...0hh...hh

0

1

1-n

m1-m0

m1-m2-m0

m1-m10

M

M (3.1.9)

Acesta este de forma HvT= 0 deci l putem determina pe H prin identificare ca fiind:

m1-m0

m1-m2-m0

m1-m10

hh...h00...00

00...hhh...h0

00...0hh...hh

HM

(3.1.10)

Pentru a corecta t erori independente g(x) trebuie sndeplineasc anumite condiii. tiim c

v(x) trebuie sfie multiplu al lui g(x) i cg(x) trebuie sfie divizor a lui xn+ 1 = 0.Pentru aceasta alegem un numr de r rdcini ale lui xn+ 1 = 0 pe care le notm cu i=

iGF(2q).Aceste rdcini isunt elemente primitive ale extensiei de ordinul q al cmpului Galois binar GF(2

q).Acest ordin poate fi determinat cu relaia:

n = 2q 1 (3.1.11)de aici rezultnd q i extensia n care se lucreazGF(2q).Pe g(x) l vom determina ca cel mai mic multiplu comun al polinoamelor minimale a rdcinilor i.

g(x) = c.m.m.m.c.m1(x),... mr(x) (3.1.12)Iar dac toate aceste r polinoame sunt relativ prime ntre ele atunci:

r

1ii

xmg(x) (3.1.13)

Expresia polinomului minimal care este definit ca polinomul mi(x) ireductibil de grad minim pentrucare mi(i) = 0 este:

1-q2i2iii x...xxxm (3.1.14)

Dei n calculul lui mi(x) folosim coeficieni GF(2

q) coeficienii lui mi(x) vor fi binari, fapt careiese n evideni din calculul acestor coeficieni n cazul exemplului 1 prezentat mai jos.Pentru corecia unui numr de maxim t erori se impune alegerea unui numr de r = 2t rdcini i

GF(2q

) ceea ce determinobinerea unui cuvnt de cod avnd distana minimd 2t + 1.n cazul codurilor ciclice binare, daceste o rdcini 2, 22, ... 2(q-1)sunt tot rdcini i

deci pentru a forma polinomul generator este suficient slum rdcinile impare:


31/49

30

1= , 3= 3, ... , 2t-1=

2t-1.

Structura matricii de control H n cazul codurilor BCH se determindeci impunnd ca v(x) saibrdcini pe 1= , 3=

3, ... , 2t-1= 2t-1.

Faptul cieste rdcina cuvntului de cod v(x) se exprimprin v(i) = 0 sau mai explicit cu relaia:

0vv...vv 0i01i11-ni1-ni cu i = 1, 3, ..., 2t-1 (3.1.15)Pentru fiecare i putem interpreta aceastrelaie ca pe un produs scalar al cuvntului format prin puterilelui isau (i) i cuvntul de cod:

0

v

v

v

0

1

1-n

0i1i1-ni

M

L (3.1.16)

nlocuind cu valorile corespunztoare pentru i (i = 1, 3, ..., 2t-1) obinem:

0

0

0

v

v

v

0

1

1-n

01-2t1-n1t2

031-n3

011-n

MM

L

M

L

L

(3.1.17)

Deci matricea de control H n cazul codurilor BCH este de forma:

01-2t21-2t1-n1-2t

0361-n3

0121-n

H

L

M

L

L

(3.1.18)

Aceastmatrice este formatdin elementele GF(2q) i are t linii i n coloane. Fiecare element

poate fi exprimat printr-un cuvnt binar din q bii i deci vom putea scrie matricea H i sub formabinardispunnd vertical cuvintele binare care nlocuiesc puterile lui . Forma binara matricii H vaavea astfel qt linii i tot n coloane.

Exemplul 1:Proiectarea unui cod BCH de lungime n = 15 i corectnd 2 erori cu determinarea polinomului

generator i a relaiilor de codare.

n = 2q 1 = 15 q = 4 extensia GF(24)

Elementele lui GF(2q) sunt clase de resturi modulo p(x) un polinom primitiv de gradul q = 4.Un polinom p(x) este primitiv daceste ireductibil i binomul xn+ 1 pe care p(x) l divide are cel

puin gradul n = 2q 1. Fie acest polinom primitiv p(x) = x4+ x + 1. Putem sconstatm cx4+ x + 1divide pe x15+ 1 (n = 2q 1 = 24 1 = 15), dar nu divide nici un xn+ 1 cu 1 n 15 deci este primitiv.

Se tie cpentru orice cmp Galois n= 1, deci la noi 15= 1.Cmpul GF(24) generat de p(x) = x4+ x + 1 obinut printr-o rdcinprimitiva lui x4+ x + 1 curelaia 4 = + 1 este cel dat n Anexa:


32/49

31

Pentru t = 2 se aleg rdcinile 1= si 3= 3, suntem n cazul binar i alegem doar rdcinile

impare pnla ordinul 2t-1 = 4-1 = 3).Polinoamele minimale vor fi conform relaiei (3.1.14):

m1(x) = (x + )(x + 2)(x + 4)(x + 8) = x4+ x3(1 + 2+ 2+ 1 + + ) + x2(1+

+ 2+ 1+ + 2+ 3+ 2+ 3++ 3+ 3+ + 2) + x(1 + 3+ + 2+ 3+ 1 + 2+ 3+ 1 +

+ 3) + 15= x4+ x + 1

m3(x) = (x + 3)(x + 6)(x + 12)(x + 24) = x4+ x3(24+ 12+ 6+ 3) + x2(36+

30+ 18+ 27+ 15+ 9) + x(42+ 39+ 33+ 21) + 45= x4+ x3+ x2+ x + 1

n aceste dourelaii puterile lui mai mari dect 15 s-au exprimat n funcie de15, iar suma s-a efectuat modulo doi.Cele doupolinoame fiind prime ntre ele i folosind relaia (3.1.13), g(x ) se obine:

g(x) = m1(x)m3(x) = (x4+ x + 1)( x4+ x3+ x2+ x + 1) = x8+ x7+ x6+ x5+ x4+ x5+

x

4

+ x

3

+ x

2

+ x + x

4

+ x

3

+ x

2

+ x + 1 = x

8

+ x

7

+ x

6

+ x

4

+ 1 m = 8 simboluri de control k = 15 - 8 = 7 simboluri de informaie, adic g = 111010001.Cuvntul de cod va fi:

v = v14v13v12v11v10v9v8v7v6v5v4v3v2v1v0

unde primii 7 sunt biii de informaie i ultimii 8 cei de control.Matricea de control H va avea 2 linii (t = 2) i 15 coloane (n = 15):

11

H 36912151821242730333639421234567891011121314

Lund puterile lui modulo 15 i innd cont c15= 1 cu ajutorul tabelului cmpului GF(24) obinemexprimarea binara lui H:

100011000110001 000110001100011

001010010100101011110111101111100010011010111010011010111100001001101011110000100110101111

H

adicqt = 42 = 8 linii i n = 15 coloane.Folosind relaia (3.1.9) se pot obine relaiile de codare.

Pentru o secveninformaionali = 0000001 cuvntul de cod sistematic se poate determina cu relaia(3.1.7):

i(x) = 1xmi(x) = x8i(x)xm/g(x) = x8/ x8+ x7+ x6+ x4+ 1

rest(i(x)xm/g(x)) = x7+ x6+ x4+ 1v(x) = x8+ x7+ x6+ x4+ 1adicv = 000000111010001


33/49

32

Decodarea BCH

n cazul codurilor ciclice binare pentru a putea corecta erori este suficient s determinmpoziia acestora din expresia sindromului. Modul n care poziia erorilor poate fi gsit cu ajutorulsindromului rezultdin prezentarea urmtoare.Un cod ciclic corector de t erori are cuvinte de cod care au un numr r = 2t de rdcini iGF(2

q),

i=i

:

v(i)= v(i) = 0 (3.1.19)

La recepie trebuie sverificm legea de codare datde relaia (3.1.15). n cazul n care avem

erori de tip aditiv putem exprima aceastlege sub forma:

r(i) = u(i) + e(i) = e(i) = e(i) = Si (3.1.20)

unde e(i) este eroarea i Sieste sindromul, iar i = 1, 3, ..., 2t-1 n cazul codurilor binare.

Pentru a vedea cum putem gsi poziia erorii cu ajutorul sindromului lum un mic exemplu:Presupunem un cuvnt oarecare care are erori pe doupoziii de exemplu 1 i 4 deci e(x)=x4+x.

innd cont de relaia (3.1.20) vom avea sindromul:

Si= e(i) = (i)1+ (i)4= (1)i + (4)i= i

2i1 XX

Expresia care indicpoziia erorii s-a notat cu Xk- locatorul erorii:

Xk= j, k = 1, ... t i j = 0, ... n-1 (3.1.21)

Deci avem atia locatori cte erori (n numr de t), iar erorile pot aprea pe orice poziie n

cadrul cuvntului (de la 0 la n-1).Deci putem exprima sindromul Sisub forma:

t

1k

iki XS

(3.1.22)

Aceast relaie ne indicun sistem de ecuaii neliniare care are ca necunoscute pe Xk (adic

locatorii).Pentru realizarea decodrii va fi prezentat algoritmul Peterson cu cutare Chien care constn:

1Calcularea sindromului erorii

1-2t...3,,1icuXrSt

1k

ik

ii

2Cu ajutorul locatorilor putem forma un polinom al erorilor care are ca rdcini locatorii:

t1-t

1t

t

1kk ...xxXxx

(3.1.23)

Dacpunem condiia ca Xksfie rdcina lui (x) obinem:

0...XX t1-t

k1tk (3.1.24)


34/49

33

Dacnmulim (3.1.24) cu ikX i nsumm n funcie de k:

0X...XXt

1k

t

1k

ikt

1-itk1

t

1k

itk

(3.1.25)

innd cont de (3.1.22) relaia (3.1.25) devine:

0S...SS it1-it1it (3.1.26)

Aceastecuaie este un sistem liniar de t ecuaii cu t necunoscute care se poate rezolva aplicndregula lui Cramer.Pentru codurile BCH folosind i relaia 2

k2k SS expresiile coeficienilor in funcie de Sipentru un

numr de 1, 2 sau 3 erori sunt:

Tabelul 3.1.1t i1 1= S12 1= S1

21

313

S

SS

3 1= S1

23

31

5321

SS

SSS

3 21331 SSS

3Cutarea poziiei eronate.Cunoscnd iputem determina poziia erorii.Dacmprim relaia (3.1.24) cu t

kX rezultrelaia:

1Xt

1i

i-ki

(3.1.27)

i dndu-ne poziia eronat.Numrul maxim de erori corectabile este t eroarea putndu-se gsi pe oricare din cele n poziii

ale cuvntului.n cazul unei cutri Chien se ncepe cutarea simbolului eronat de la rn-1. Pentru o poziie

oarecare n-j innd cont de (3.1.21) vom avea Xk= n-j

11

11

t

1i

jini

t

1i

jini-i

t

1i

j-ni-i

i (3.1.28)

Deoarece n= 1 obinem ecuaia de cutare Chien:


35/49

34

1,...njcu1t

1i

jii

(3.1.29)

lui j = 1 corespunzndu-i simbolul rn-1, iar lui j = n simbolul r0.Deci conform ecuaiei (3.1.29) eroarea apare cnd suma respectiveste egalcu 1.

Exemplul 2:

Presupunem crecepionm un cuvnt BCH cu n = 15 i k = 7 i cavem t = 2 erori.

r =110101011010011r(x) = x14+ x13+ x11+ x9+ x7+ x6+ x4+ x1+ 1

Calculm sindromul. Pentru t = 2 avem de calculat pnla S3inclusiv (2t-1 = 22-1 = 3):

S1= r() = 14+ 13+ 11+ 9+ 7+ 6+ 4+ + 1=

= 1 + 3

+ 1 + 2

+ 3

+ + 2

+ 3

+ + 3

+ 1 + ++ 3 + 2+ 3+ 1 + + + 1 = 2+ + 1 = 10

S3= r(3) = 42+ 39+ 33+ 27+ 21+ 18+ 12+ 3

+ 1= 12+ 9+ 3+ 12+ 6+ 3+ 12+ 3+ 1 = 9++ 6+ 12+3 +1 = + 3+ 2+ 3+ 1 + + 2+ 3++ 3+ 1 = 0

Din tabelul 3.1.1 avem pentru t = 2:

1= S1= 10

21

313

S

SS

=

20= 5

n calculele anterioare am utilizat valorile pentru puterile lui din tabelul 1 i puterile caredepesc 15le-am exprimat in funcie de aceasta innd cont c15= 1.Folosim relaia de cutare (3.1.29) i avem:

j = 1 111+ 2

21= 10+ 52= + 2+ 3+ 1 + + 3= 1 + 2= 8j = 2 1

12+ 222= 102+ 54= 8

j = 3 113+ 2

23= 103+ 56= 4

j = 4 114

+ 224

= 10

4

+ 5

8

= 2

j = 5 115+ 2

25= 105+ 510= 0j = 6 1

16+ 226= 106+ 512= 5

j = 7 117+ 2

27= 107+ 514= 10j = 8 1

18+ 228= 108+ 516= 2

j = 9 119+ 2

29= 109+ 518= 5

j = 10 1110+ 2

210= 1010+ 520= 1 deci este eronat simbolul n - j = 15 10 = 5 (r5)j = 11 1

111+ 2211= 1011+ 522= 4

j = 12 1112+ 2

212= 1012+ 524= j = 13 1

113+ 2213= 1013+ 526= 10

j = 14 1114

+ 2214

= 10

14

+ 5

28

= j = 15 1115+ 2

215= 1015+ 530= 1 deci este eronat simbolul n - j = 15 15 = 0 (r0)


36/49

35

Cuvntul decodat va fi deci 110101011110010.Secvena de informaie de la ieirea decodorului va fi i = 1101010.

Desfurarea lucrrii:

a) Rulai programul pe calculator, utiliznd opiunea demonstrativatt pentru algoritmul de codare cti pentru cel de decodare. Se urmrete pas cu pas algoritmul de codare existnd posibilitatea de a

alege un cod corector de t = 1, 2, sau 3 erori. Urmrii cu atenie la fiecare pas mesajele calculatoruluicare va vor ghida n rularea corecta programului. De asemenea se urmrete pas cu pas algoritmul dedecodare.

b) Realizai o codare a unui cuvnt n cazul unui cod corector de t = 1, 2, sau 3 erori alegnd irul debii de informaie de lungimea corespunztoare. Pentru cazul t = 2 efectuai apoi decodarea unuicuvntului de cod. Verificai apoi calculele cu ajutorul programului de pe calculator.c) La sfritul lucrrii de laborator se va efectua cu ajutorul programului un test asupra cunotineloracumulate. Testul cuprinde 5 ntrebri teoretice fiecare cu un rspuns corect din cinci propuse, o codarei o decodare a unui mesaj pe care calculatorul l genereazn mod aleator.

3.2 Codul Reed-Solomon

Codurile Reed-Solomon (RS) fac parte din categoria codurilor ciclice, ns sunt codurinebinare. Spre deosebire de celelalte coduri ciclice, alfabetul codului RS nu este cmpul binar 0, 1,ci un cmp finit de ordin superior, numit cmp Galois i care va fi descris n Anexa. n acest fel,cuvintele codului RS nu sunt secvene (succesiuni) de bii, ci de caractere. Aceste caractere pot fireprezentate, la rndul lor, prin secvene binare, nssunt indivizibile din punct de vedere al codrii idecodrii Reed-Solomon.

Structural, cuvintele de cod RS au aceeai alctuire ca i cele de cod ciclic:

v = vn-1vn-2... v1v0 vjGF(2q, p(x)) j = 0n-1 (3.2.1)

unde: v cuvntul de cod, format din n caractere;vn-1vn-2... vk caracterele de informaie, n numr de k;vk-1vk-2... v0 caracterele de control, n numr de m;q ordinul cmpului;p(x) polinomul generator al cmpului GF.

Relaia de codare are aceeai formca i la codurile ciclice:

v(x) = i(x)xm+ rest (i(x)xm/g(x)) (3.2.2)

unde g(x) este polinomul generator al codului, al crui construcie este prezentatmai jos, iar

i(x) = vn-1xk-1+ vn-2x

k-2+ ... + vk+1x + vk (3.2.3)

este polinomul de informaie.Prin relaia de codare (3.2.2) se obine polinomul ataat cuvntului de cod, polinom ai crui

coeficieni sunt tocmai caracterele ce alctuiesc cuvntul de cod dat de (3.2.1). Relaia (3.2.2) indic,deasemenea, cv(x) este un multiplu al lui g(x).

Codul RS, avnd parametrii n, k i m, construit duprelaia (3.2.2), este capabil scorecteze unnumr ecde caractere eronate, unde:

2ec= m = n-k (3.2.4)


37/49

36

La decodare, spre deosebire de codurile ciclice, ntr-un cuvnt de cod RS recepionat, nvederea coreciei, este necesaratt localizarea erorii, ct i stabilirea valorii ei.Polinomul generator, g(x), al codului

Pentru a se corecta t erori dintr-un cuvnt este necesar a se preciza poziia fiecreia precum ivaloarea ei. Dacne referim la un cuvnt de lungime n, unde:

n = 2q

1 (3.2.5)

atunci informaia necesarpentru a preciza un caracter eronat ntre cele n este:

ip1= -log2(1/n) (3.2.6)

Pentru a include i varianta cuvnt freroare, considerm c n acest caz se eroneaz unal n+1lea caracter, fictiv, astfel nct informaia necesarpentru a preciza poziia unui caracter eronat(dintre n+1 caractere) este:

ip1= log2(n+1) (3.2.7)

Aceastinformaie poate fi coninutde un caracter din GF(2q). Deasemenea i valoarea erorii, , poatesfie orice caracter din GF(2q):

w = v + (3.2.8)

unde: w caracterul recepionat GF(2q);v caracterul emis GF(2q);-valoarea erorii GF(2q)\{0}.

Incluznd i cazul eronare a caracterului fictiv, rezultcpoate lua orice valoare din GF(2q), adic

2

q

valori posibile. Informaia necesarpentru a preciza valoarea ei este identiccu cea datde (3.2.7).n concluzie, pentru fiecare eroare ce se dorete a fi corectateste necesaro informaie egalcu 2q bii, adic dou caractere din GF(2q). La t erori sunt necesare 2t caractere (cantitate deinformaie).Obs. n fapt condiia anterioar este una suficient, cea necesar implic mai puin informaiedeoarece nu se poate erona un caracter de douori. De exemplu n cazul a douerori:

1nlog1)(nlog2

n1)(nlog

C

1logi 2222

1n2p2

(3.2.9)

iar pentru n suficient de mare ip22ip11.

Cele 2t caractere de informaie necesare soluionrii problemei coreciei se afldin 2t ecuaii,care nseamntot attea legturi (proprieti) pentru cuvntul receptionat. Aceste 2t proprieti pentrucuvintele de cod RS sunt generate prin relaia de codare (3.2.2). Prin aceast relaie v(x) devinemultiplul lui g(x), ceea ce nseamncrdcinile lui g vor fi i rdcini pentru v. Rezultnecesitatea cag saib2t rdcini. Aceste rdcini pot fi oricare dintre cele 2qelemente ale cmpului GF(2q). Vomalege pentru g rdcinile , 2, 3, ... 2t, datoritsimplitii i simetriei:

g(x) = (x + )(x + 2) ... (x + 2t) = xm+ gm-1xm-1+ ... + g1x + g0 (3.2.10)

Aadar cuvntul de cod RS, v, rezultat prin codarea cu ajutorul relaiei (3.2.2), n care g este datde (3.2.10), are proprietatea celementele , 2, 3, ... 2tsunt rdcini pentru polinomul ataat, v(x).


38/49

37

Codarea codului Reed Solomon

Codarea se poate face utiliznd relaia (3.2.2).Spre exemplu n cazul codului RS cu n = 7, k = 5, t = 1 avnd polinomul generator:

g(x) = (x + )(x + 2) = x2+ 4x + 3= x2+ 5x + 4 (3.2.11)

Ecuaia mpririi este:

i(x)x2= (2x4+ 5x3+ x2+ x + 5)(x2+ 5x + 4) + x + 1 (3.2.12)unde: -i(x)x2este dempritul (i = [2 1 7 5 4] i(x) = 2x4+ x3 + 7x2+ 5x + 4);

-2x4+ 5x3+ x2+ x + 5 este ctul;-g(x) = x2+ 5x + 4 este mpritorul, iar- x + 1 este restul.

mprirea polinomului i(x)xm= i(x)x2la g(x), cerutpentru codare de relaia (3.2.2), este prezentatmai jos:

2x6+ x5+ 7x4+ 5x3+ 4x2 x2+ 5x + 4

2x6+ 6x5+ 5x4 2x4+ 5x3 + x2+ x + 5/ 5x5+ 4x4+ 5x3+ 4x2

5x5+ 2x4+ x3/ 2x4+ 6x3+ 4x2

x4+ 5x3+ 4x2/ x3

x3+ 5x2+ 4x/ 5x2+ 4x

5x

2

+ 2x + 1/ x + 1

Cuvntul de cod, conform relaiei (3.2.2) rezult:

v(x) = i(x)x2+ x + 1 = 2x6+ x5+ 7x4+ 5x3+ 4x2+ x + 1 (3.2.13)Decodarea codului Reed-Solomon

Decodarea codului RS poate fi fcutatt n timp ct i n frecven

Decodarea codului RS-corector de erori multipleDecodarea va fi sistematizat sub forma unor pai algoritmici. La fiecare pas se va prezentaoperaia necesar a fi executat, scopul urmrit ct i argumentrile necesare. Fie aadar codul RScorector de t erori.

Pasul I

Conform relaiei (3.2.10) g(x) este un polinom de grad k = 2t > 2. Prin construcie, cuvintele decod RS au proprietatea cpolinoamele ataate lor sunt divizibile cu g(x), adicelementele cmpuluiGF(22) , 2, , 2tsunt rdcini att pentru g(x) ct i pentru orice cuvnt de cod v(x):

g(j) = 0

v(j) = 0 j = 12t (3.2.14)


39/49

38

Aceste proprieti constituie i punctul de plecare n decodare. Presupunnd cw este un cuvntrecepionat:

w = v + sau w(x) = v(x) + (x) (3.2.15)vom calcula 2t coeficieni, numii coeficieni sindrom, Sj, n forma:

Sj= w(j) = v(j) + (j) = (j) j=12t (3.2.16)

Evident cdacnu existerori Sj = 0. n acest caz se trece la pasul VI. Evident concluzia poate fieronat. Un exemplu n argumentarea acestei afirmaii este situaia: = cuvnt de cod. Dar n acest caznumrul erorilor depete puterea de corecie de t erori.

Pasul II

Dacexist erori n limitele corectabile (numrul erorilor este mai mic sau egal cu t) atunci existcoeficieni sindrom diferii de zero. Fie cuvntul eroare n forma:

t

1i

kr ii xx (3.2.17)

unde:

iriY (3.2.18)

reprezintvaloarea erorii ri{0, 1, 2, n-1}, iar:

ikiX (3.2.19)

reprezintlocatorul erorii ki{0, 1, 2, , n-1}. Cu aceste notaii coeficienii sindrom au expresiile:

t

1i

t

1i

jii

kjij XYYS

i , j = 12t (3.2.20)

Ecuaiile (3.2.20) reprezintun sistem de 2t ecuaii cu 2t necunoscute: t locatori ai erorilor Xii

t valori pentru respectivele erori Yi.Rezolvarea acestui sistem de ecuaii se va face n mai multe etape. La pasul prezent se vor

calcula coeficienii polinomului (x) ai crui rdcini sunt locatorii erorilor:

t

1it1t

1t1

ti x...xxXxx (3.2.21)

Pentru cXi , 1i t este o rdcina lui (x) putem scrie:

0X...XX ti1t1t

i1ti

, i = 1t (3.2.22)nmulind ecuaiile (3.2.22) pe rnd cu Xi

kYii sumndu-le obinem ecuaia:

0XY

XY...XYXY

t

1i

kii

t

1i

t

1i

1kii1

1ktii1

t

1i

ktii

t

t

(3.2.23)


40/49

39

sau, innd cont de (3.2.20) pentru k lund valorile 1, 2, ..., t:

St+k+ 1St+k-1++ t-1Sk-1+ tSk=0 , k = 1t (3.2.24)

Ecuaiile (3.2.24) reprezint un sistem de t ecuaii cu t necunoscute (coeficienii i) a cruirezolvare constituie obiectivul acestui pas algoritmic. Ecuaiile (3.2.24) pot fi puse sub forma

compact:As= Bs (3.2.25)

unde:

t22t12t

2t1t

11tt

s

S...SS

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

S...SS

S...SS

A ;

t

...

2

1

;

2t

2t

1t

s

S

...

S

S

B (3.2.26)

Calculnd inversa matricii Asgsim soluia sistemului (3.2.24) n forma:

sBA-1s (3.2.27)

Obs: Toate calculele trebuiesc fcute n cmpul GF(2), att coeficienii sindrom, Sj, cti coeficienii fiind elemente ale respectivului cmp.

n rezolvarea ecuaiei (3.2.25) pot aprea trei situaii:1 rangul matricii As este e < t i este egal cu al matricii [AsBs]. n acest caz numrul de erori este e i

din rezolvarea ec (3.2.25) rezultun numr e de coeficieni I nenuli Rezolvarea ecuaiei (3.2.25)presupune restrngerea sistemului (10.24) la un numr e < t de ecuaii cu e necunoscute,rezolvabil.

2 rangul matricii As este t. n acest caz existAs-1 iar ecuaia (3.2.25) are soluie datprin relaia(3.2.27).Se vor gsi t erori n acest caz.

3 rangul matricii As este e`


41/49

40

Xr= r (3.2.31)

n (3.2.28)i utiliznd identitatea n=1 obinem:

t

1j

rjj

t

1j

rjjnj

t

1j

rj)(nj

t

1j

jrkj 1

Pasul IV

Dispunnd de poziiile erorilor dispunem implicit de numrul lor. Reinem cproblema aresoluie doar dace < t. Cunoscnd aadar e locatori ai erorilor n forma ikiX , i = 1e, din sistemulde ecuaii (3.2.20) se rein e ecuaii n vederea aflrii valorilor Yipentru cele e erori. Acest sistem estecompatibil unic determinat. Rezolvarea sa conduce la aflarea celor e valori necesare Yi.

Pasul V

Cunoscnd att poziiile erorilor Xi= i, i = 1e, ct i valorile lor iriY , i=1e putem face

corecia caracterelor eronate:

iYwv ii kk , i =1e (3.2.32)

Pasul VI

Se face selecia caracterelor de informaie i livrarea lor la ieire.

Desfurarea lucrrii:

a) Rulai programul pe calculator, utiliznd opiunea demonstrativatt pentru algoritmul de codare cti pentru cel de decodare. Se urmrete pas cu pas algoritmul de codare existnd posibilitatea de a

alege un cod corector de t = 1, sau 2 erori. Urmrii cu atenie la fiecare pas mesajele calculatoruluicare va vor ghida n rularea corecta programului. De asemenea se urmrete pas cu pas algoritmul dedecodare.

b) Realizai o codare a unui cuvnt n cazul unui cod corector de t = 1, sau 2 erori alegnd irul decaractere de informaie de lungimea corespunztoare. Pentru cazul t = 1 i 2 efectuai apoi decodareaunui cuvntului de cod. Verificai apoi calculele cu ajutorul programului de pe calculator.


42/49

41

L4. Coduri convoluionale

Codurile convoluionale au fost introduse n 1954 de P. Elias i reprezinto clasde coduricorectoare avnd o mare aplicabilitate practic.

n cazul codurilor convoluionale, fiecare bloc de n simboluri binare de la ieirea codoruluidepinde att de blocul de ksimboluri binare prezent la intrarea sa, la momentul considerat, ct i de m

blocuri precedente. n consecincodurile convoluionale introduc un efect de memorie de ordinul m.CantitateaK=m+1 se numete lungimea de constrngere a codului.

Codorul este constituit dintr-un sistem de m registre de ntrziere, fiecare avnd o capacitate dekbii, care memoreazcele mblocuri de ksimboluri de informaie, dintr-o mulime de funcii liniare,ce genereazblocurile de nsimboluri de la ieire i dintr-un convertor paralel-serie. MrimeaR=k/nsenumete randamentul codului.

Un cod convoluional de randamentR este o aplicaie de la mulimea matricilor (binare) cu unnumr de klinii i numr infinit de coloanectre mulimea matricilor (binare) cu un numr de nlinii inumr infinit de coloane, unden > k:

nk MMC : (4.1)

Astfel, prin transformarea C, fiecrei matrici kMI , de forma :

LL

LLLLLL

LL

LL

jkkkk

j

j

iiii

iiii

iiii

210

22212

1

02

211101

I , k1,s,0,j1,0 jsi (4.2)

i se ataeazo matrice nMV , de forma:

LL

LLLLLL

LL

LLLLLL

LL

LL

jnnnn

jkkkk

j

j

aaaa

aaaa

aaaa

aaaa

210

210

2221202

1211101

V , n1,s,0,j1,0 jsa (4.3)

Matricea I conine practic biii de informaie, n ordinea KK ii 110k0201 ii , iar matricea V

secvena codat: KK aa 110n0201 aa . Dac js jsa i pentru oricejpozitiv i pentru orice ks 1 ,atunci codul se numete sistematic. Fcnd apel la o reprezentare polinomial, matricile Ii Vse potscrie ca :

0sssk

0s

s2s

0s

s1s

Di

Di

Di

DM

I ,

0s

s

0s

ssk

0s

s2s

0s

s1s

Da

Da

Da

Da

D

sn

M

MV (4.4)


43/49

42

Cu aceste notaii, relaia de codare,poate fi scrisastfel :

DDD IGV (4.5)

unde G(D) se numete matricea generatoare a codului i are forma:

DgDgDg

DgDgDg

nknn

k

L

LLLL

L

11

11211

DG (4.6)

n funcie de felul polinoamelor gebneratoaregjs(D), codurile convoluionale pot fi clasificate ca i:a) Coduri sistematice sau nesistematice. Dac primele k linii din G(D) formeaz matricea

unitate de ordinulk,Ik, atunci codurile sunt sistematice. n acest caz biii din I se vor regsi printre biiidin V. Astfel, dacceleksimboluri de informaie, prezente sunt efectiv emise, adicse gsesc n modexplicit n blocul de n simboluri de la ieirea codorului peprimele k poziii, codul se numete codsistematic. Pentru codurile nesistematice, biii din Vsunt combinaii liniare ale biilor din I, neexistnd

bii de informaie i de control ca i n cazul precedent.b) Coduri recursive sau nerecursive. Dac toate polinoamele generatoare care compun G(D)

sunt finite, atunci codul rezultat este nerecursiv. n caz contrar polinoamele generatoare gjs(D) pot fiscrise sub forma:

)(

)()(

Db

DaDg

js

jsjs (4.7)

unde polinoamele ajsi bjssunt finite. Deci, dacexistcel puin un polinom bjs(D)1, atunci codul esterecursiv.

Lungimea de constrngere este unul dintre parametri importani ai codurilor convoluionale. Oaltdefiniie a sa este datn relaia de mai jos:

DbDagradK sjsjsj

,,,

,max1 (4.8)

Pentru a ilustra codurile convoluionale nerecursive i nesistematice, n Fig. 4.1. seprezint un exemplu de codor convoluional de randament R=1/2 i de lungime deconstrngere K=(m+1)=3. Intrarea sa esteconstituitdin blocurile de k=1simbol i ieireasa de blocurile de n=2simboluri.

Fig. 4.1. Exemplu de codor convoluional nerecursiv, nesistematic (R= 1/2, K= 3).

ik ik-1 ik-2D D2ka

1ka

V


44/49

43

i+ D DD

+

a0 a1 a2 aM-1 aM

b1 b2 bM-1 bM

i

c

Relaiile de calcul ale secvenelor de la ieire sunt:

2

0

11

jjjkk gia ,

2

0

22

jjjkk gia (4.9)

Cele dousecvene generatoare sunt:

1,1,1,,1,0,1,,

22

21

20

2

12

11

10

1

gggg

gggg (4.10)

Observm c ieirile codorului fiind egale cu o combinaie liniara simbolurilor deinformaie, codul este liniar. Codurile convoluionale sunt de asemenea definite pornind dela polinoamele lor generatoare exprimate n funcie de variabila D (ntrziere) echivalentcu variabila Z-1 a transformatei Z. Considernd tot exemplul din Fig. 4.1, polinoamelegeneratoare ale acestui cod au expresiile:

222

21

20

22

21

2

1

1

1

0

11

)(

)(

DgDggDGg

DgDggDGg

(2.11)

i:

22

21

1

1

DDDG

DDG

(2.12)

rezultnd matricea generatoare G=[1+D2, 1+D+D2].n general polinoamele generatoare ale codorului se exprimn octal i astfel, pentru

cazul din Fig. 4.1, avem:

octal)7(n[1,1,1]

octal)5(n[1,0,1]2

1

G

G (2.13)

n Fig.4.2 a) se prezint schema general a unui codor recursiv sistematic, RSC (RecursiveSystematic Code), iar n figura Fig. 4.2 b) un caz particular al acesteia.

a) b)Fig. 4.2. Cod convoluional recursiv sistematic: a) schema general, b) exemplu (R=1/2,K=3).

n exemplul considerat matricea generatoare este de forma:

2

2

11

,1DD

DG (2.14)

i

i

c

+ DD

+


45/49

44

n figura urmtoare sunt prezentate douexemple decodoare sistematice i nerecursive, NRSC (Non-Recursive Systematic Code), considerndu-se randamentulR=1/2 i lungimea de constrngereK=3:

a) b)Fig. 4.3 Coduri convoluionale sistematic i nerecursiv,R=1/2,K=3, G=1+D+D2.

Diagrame de stri

Diagrama de stri este o reprezentare a funcionrii unui codor convoluional, ncare timpul nu apare n mod explicit.

n Fig.4.4 s-a reprezentat diagrama de stri asociatcodorului convoluional din Fig.4.1. Diagrama de stri permite evaluarea funciei de transfer a codorului, care va fi utilizatpentru calculul performanelor codului.

Fig. 4.4: Diagrama de stri a codorului din Fig. 4.1.

Diagramele de stri corespunztoare codurilor convoluionale din Fig.4.2 b) i Fig.4.3 a) i b) suntprezentate n Fig.4.5.

Fig. 4.5 Diagramele de stare pentru codoarele convoluionale: a) RSC; b) i c) NRSC.

i

DDi

C

00

10

1101

11

01

1000

00

10 01

11

21 , kk aa ik=1

21 , kk aa

ik=0

00

10 01

11

00

00

01 01

11 11

10

10

a)

00

10 01

11

00

00

01

01

11

11

10

10

b)

i

DDi

C

00

10 01

11

00

01

01

00

11

10

11

10

c)


46/49

45

Diagrama tr ll s

Fiecare bloc de n= 2 simboluri de la ieirea acestui codor depinde de blocul de k =1 simbol prezent la intrarea sa dar i de m= 2 blocuri de ksimboluri coninute n memoriasa. Aceste mk= 2 simboluri definesc starea codorului. Se noteazcu S0= (00), S1= (01),

S2 = (10) i S3 = (11), cele patru stri posibile ale codorului din Fig. 4.1. Oricare ar fistarea iniiala codorului, dupm+1=3 ntrzieri la intrarea codorului, toate strile au fostatinse.

Funcionarea codorului poate fi explicat innd seama doar de strile sale i detranziiile dintre acestea,numite ramuri (ramificaii, brae). Diagrama trellisastfel obinuteste reprezentat n Fig. 4.6, pentru codorul convoluional din Fig. 4.1, presupunndipoteza cstarea sa iniialera S0= (00).

Fig. 4.6. Trellis-ul codorului convoluional din Fig. 4.1.

Ramurile reprezentate prin linii punctate corespund prezenei unui simbol deinformaie egal cu 1, la intrarea codorului, i ramurile reprezentate prin linii pline, unuisimbol de informaie egal cu 0. Fiecrei ramuri i s-a asociat valoarea cuplului binardisponibil la ieirea codorului.

Dupm+1 ntrzieri, oricare ar fi starea iniiala codorului, trellis-ul se repet. Dinfiecare nod pleac2kramuri (n cazul de fasunt douramuri) i n fiecare nod converg 2kramuri.

Pornind de la starea S0=(00) n momentul t=0, de exemplu, vedem cexistpatru cicare permit atingerea striiS0=(00) n momentul t=4.

00 00 00 00 calea 100 11 01 11 calea 211 10 10 11 calea 311 01 11 00 calea 4

00 00 00 00

00 0011 11 11 11

11 11

01 01 01

01 01

10 10 10

10 10

t=0 t=1 t=2 t=3 t=4

00

01

10

11

21 , kk aa

ik=1

21 , kk aa

ik=0


47/49

46

Codarea codului convoluional

Folosind o codare convoluional, se codeaz urmtoarea secvende informaie: i=100111,considernd polinomul generator al codului: g(D)=1+D2.n acest scop se folosete Fig. 4.7.

i: 1 0 0 1 1 1v: 11 00 01 11 11 10 01 01

Fig. 4.7. Utilizarea diagramei trellis n cazul codrii secvenei de informaie i=100111, considernd diagrama de stri dinFig. 4.5. c).

Cuvntul de cod obinut este v=11 00 01 11 11 10 01 01. Trellis-ul codorului convoluional senchide la zero, astfel, datoritacestui fapt au aprut dougrupe suplimentare de bii.

Calea pe trellis care ne genereazcuvntul de cod, v, este cea marcatcu rou.

Decodarea codului convoluional, algoritmul Viterbi cu decizie hard

Pentru prezentarea acestui algoritm se considerun canal binar simetric (frmemorie), intrareadecodorului fiind alctuitdintr-o secvende simboluri binare.

n fiecare moment douramuri, aparinnd la douci diferite, converg spre fiecare nod al trellis-lui (Fig.4.6). Din aceste douci una este mai probabil, altfel spus, se gsete la cea mai micdistan

Hamming fa de secvena recepionat, dect cealalt cale. Distana fiind o funcional aditiv, nfiecare nod se pstreazcalea cea mai probabilnumitcale supravieuitoare. Dacse obin doucicu aceeai distanHamming, doar o singurcale este pastrat, alegndu-se n mod arbitrar una dincele douci posibile.

n figura urmtoare se prezintun exemplu de decodare pentru codorul reprezentat n Fig. 4.3.b), cu diagrama de stri reprezentatn Fig. 4.5. c). Calea rezultanteste marcatcu culoare roie.

00

10

01

11

00 00 00 00 00 00 00 00

10 1010 1010 10 10 10 10

01 01 01 01 01 01 01 01

11 11 11 11 11 11 11 11

0/00 0/00 0/00 0/00 0/00 0/00 0/00 0/00

0/00 0/00 0/00 0/00 0/00 0/00 0/00

1/11 1/111/111/11 1/11 1/111/111/11

1/11 1/11 1/11 1/11 1/11 1/11 1/11

0/01 0/01 0/01 0/01 0/01 0/01

0/01 0/01 0/01 0/01 0/01 0/01

1/10 1/10 1/10 1/10 1/10 1/10

1/10 1/10 1/10 1/10 1/10 1/10


48/49

47

w: 10 10 01 11 11 10 01 01

Tact:0 1 2 3 4 5 6 7 8v: 11 00 01 11 11 10 01 01i: 1 0 0 1 1 1 (0) (0)

Fig. 4.8. Utilizarea diagramei trellis n cazul decodrii secvenei w=A7E5H, considernd diagrama de stri din Fig. 4.5. c).

Desfurarea lucrrii:

a) Rulai programul pe calculator, utiliznd opiunea demonstrativatt pentru algoritmul de codare cti pentru cel de decodare.

b) Realizai o codare i o decodare, folosind algoritmul de decodare Viterbi. Verificai apoi calculele cuajutorul programului de pe calculator.

1

00

10

0

Indrumator TIC

Documents

Transcript of Indrumator TIC