or TIC

8/8/2019 or TIC

1/49

TEORIA INFORMAIEI I A CODRII

ndrumtor de lucrri la laborator

Horia BALTA Maria KOVACI

2009

8/8/2019 or TIC

2/49

1

Cuprins

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

1.1.Codarea binar a 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

8/8/2019 or TIC

3/49

2

8/8/2019 or TIC

4/49

3

L1. Algoritmi pentru codarea sursei i compresie

1.1. Codarea binar a surselor de informaie

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

Codarea binar a 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 surs de informaie intereseaz numrul de simboluri N i

probabilitile lor de apariie pi , Ni ,1 . Doar pe utilizator l intereseaz ce reprezint fiecare mesaj n parte (liter de alfabet, nivel al intensitii pixelilor dintr-o imagine, valori ale unor mrimi fizice cevariaz arbitrar1).

Codarea este operaia prin care fiecrui simbol al sursei, si, i se aloc o succesiune binar unic:

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 dat de 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 egal cu informaia medie pe un cuvnt raportat la 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 s fie instantaneu (nici un cuvnt nu este prefixul altuia);

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

8/8/2019 or TIC

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 variabil este mai complicat, dar conduce la osurs secundar cu eficien mai buni la o ieftinire a transmisiei, lungimea medie a cuvintelor decod fiind mai mic. Codarea cu cuvinte de lungime constant este mai simpl dar cuvintele avndaceeai lungime ofer maleabilitate 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 c numrul de secvene diferitece pot fi constituite cu L cifre binare este 2L, rezult c numrul simbolurilor sursei trebuie s fie maimic dect 2L, sau:

(S)HNlogL max2 > L 1 (1.1.5)

Inecuaia a doua din (1.1.5) se datoreaz criteriului de eficien minim 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 reordoneaz probabilitile,obinndu-se o surs cu N-1 simboluri;

3. Procesul continu pn cnd 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 s ndeplineasc condiia:

1pN

1ii

; 1p0 i ; N1,i (1.1.6)

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

N

1ki

ii

k

kp

(1.1.7)

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

8/8/2019 or TIC

6/49

5

ceea ce asigur ndeplinirea 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 c simbolurile 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 surs de informaie. Simbolurile acesteia reprezint intervale de

lungime egal, i n numr finit, de pe ax real. n acest caz datele vor consta n valorile eantioanelorunui semnal discret ( Fig.1.1.1) , mrginit n timp cu suportul finit precizat ca dat de 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 [ ] semnific partea ntreag;

Fig.1.1.1 Surs de informaie semnal discret

va calcula 1]minmax

[

q

N unde [ ] semnific partea 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 s rmn simboluri 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 relativ a 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

8/8/2019 or TIC

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 surs solicitai 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 ulteriori 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 afieaz pe rnd date pentru cei

4n studeni i apoi ntreab pe rnd, n aceeai ordine studenii, timpii de afiare i de chestionarerezervai fiecrui student sunt constani i nu influeneaz pe cei rezervai altuia). Rezultatul testului seva concretiza printr-o not, calculat automat 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 fr pierdere.

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 anumit redundan ce se datoreaz: Distribuiei caracterelor (unele caractere au o frecven de 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 plusexist grupuri care nu apar deloc);

Distribuiei poziiei (unele caractere sau grupuri ocup poziii 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 ns rezultatul fiind dezastruos. nstudiul compresiei se urmrete obinerea unui algoritm care s ofere o compresie ct mai bun pentrutipuri de surse ct mai diferite.

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

uc

c

nFn

(1.2.1)

8/8/2019 or TIC

8/49

7

unde nu este lungimea n bii a mesajului iniial i nc lungimea de compresie.

Algoritmul Huffman dinamic

Algoritmii de tip Huffman static au dezavantajul c necesit cunoaterea prealabil a 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 baz n aceast codare 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 primilori simboluri 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,adic un simbol care n-a mai aprut n mesaj, se transmite mai nti codul frunz goali apoi cei n biiafereni simbolului nou aprut. Frunza goal are semnificaia c urmeaz un nou simbol. Frunza goalse codific ca un mesaj oarecare, dar ponderea sa ntodeauna va rmne nul.

Exemplu:n continuare se prezint evoluia 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 dreaptai 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

8/8/2019 or TIC

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

8/8/2019 or TIC

10/49

9

7. Mi = aaabccc

n urma rearanjrii arborelui se obine:

Dac se presupune c simbolurile 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)

Rezult un 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

8/8/2019 or TIC

11/49

10

Desfurarea lucrrii:

a) Se lanseaz executabilul 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 aceast lucrare, selectnd pe rnd compresia, respectivdecompresia prezentate.

c) Pentru compresie i decompresie se alege cte un exemplu oarecare asemntor cu cel prezentat nlucrare. Se realizeaz compresia/decompresia, dup care, cu programul, se verific rezultatele obinute.d) La sfritul lucrrii de laborator se va efectua un test asupra cunotinelor acumulate. Rezultatultestului se va concretiza printr-o not, calculat automat de calculator.

1.3. Algoritmi de compresie de tip LZ

Cu toate c algoritmii de compresie Huffman, static sau dinamic, sunt cei mai performani (dinpunct de vedere al factorului de compresie) relativ la sursele fr memorie, aceast concluzie 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 repetareafrecvent a unor subiruri.

Ideea de baz n algoritmii LZ este nlocuirea unor subiruri ale mesajului cu cuvinte de cod,astfel nct, la o nou apariie a unui subir s se transmit doar 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. Bufferfereastr utilizat n algoritmul LZ77

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

-se ncarc primele NZ caractere din mesajul de intrare n blocul Ziv;-se transmite la ieire tripletul 0, 0, x, unde x reprezint primul caracter (liter) din mesajul de

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

NL. Din acest moment:-se caut n 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 snceap n blocul Lempel, dar poate s sew sfreasc n blocul Ziv. Dac un astfel de subir, S, exist,atunci se va transmite tripletul P, L, A, unde P = pozi ia 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 deplaseaz mesajul de intrare pn cnd, dup caz, A sau x ajung pe poziia NLi procesulde cutare se reia pn cnd tot mesajul a trecut prin blocul Ziv.

Lempel ZivIeiremesaj

Intraremesaj

1 2 NL 1 2 NZ

8/8/2019 or TIC

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 s fie 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 (NZ 1) (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) rezult c, pentru o bun compresie, NL+1 i NZ1 trebuie s fie

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 unurezerv literei A un loc n blocul Ziv.

Exemplu Fie parametrii NL =7i 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 exist teoretic nici o limitare a blocului Ziv.Algoritmul LZ78 este, n esen, urmtorul:-se iniializeaz dicionarul (blocul Lempel) cu un ir nul;-se ncarc mesajul de intrare n blocul Ziv;-se transmite n clar primul caracteri se introduce i n dicionar la poziia 1. Cele dou poziii

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

8/8/2019 or TIC

13/49

12

aferent urmat de caracterul A ce urmeaz lui 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 semnific subirul 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(log2 n) bii (1.3.3)

unde sup(x) reprezint aproximarea prin adaos a lui x, iar n dimensiunea momentan a dicionarului;-se citete din dicionar subirul S aflat la poziia citit anteriori se genereaz la 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)

8/8/2019 or TIC

14/49

13

-se citete din mesajul recepionat urmtorul caracter, A (n cod ASCII), i se genereazi acesta laieire. Dac A este un nou caracter, atunci se introduce n dicionar la o nou poziie;-se introduce n dicionar subirul SA la urmtoarea poziie;Procesul se repet pn la 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. Oalt modificare o constituie existena unui prefix, P, care se memoreaz de la un pas la urmtorul.

Algoritmul compresiei este:-se iniializeaz dicionarul (aa cum s-a descris anterior);-se citete primul caracteri se memoreaz ca i prefix, P. Din acest moment:-se citete urmtorul caracter, notat E. Se caut n dicionar subirul PE. Dac acest subir exist, atuncise trece la pasul urmtor, fr a emite nimic i fr a aduga nimic n dicionar. Singura modificare este

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

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

Procesul continu n acest fel pn la 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 c simbolul E nu se citete directde la intrare (ca i la compresie) ci doar dup ce 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 algoritmul LZW. 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 c orice 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.

8/8/2019 or TIC

15/49

14

Dicionarul

a 0=00 b 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

8/8/2019 or TIC

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 clas de 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 fa sursa 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 coloan structurat prin reprezentarea binar a numrului zecimal de ordineal coloanei respective. Din acest motiv, corectorul Z, calculat cu relaia TZ H V , decodat din binarn zecimal, indic numrul de ordine zecimal al bitului eronat din cuvntul recepionat.Distana minim a acestui cod este:

cd 2e 1 3 ,

unde ec reprezint numrul de erori corectabile.Se consider codul 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 nseamn calculul simbolurilor de control C1, C2, i C4 cnd se dau simbolurile de informaiei3, i5, i6, i7.

Relaia de codare:

1

2

3T

4

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)

undeHreprezint matricea de control, ce este de dimensiune mn.

8/8/2019 or TIC

17/49

16

Sau n form explicit:

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 observ c exist 4 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.

Rezult c matricea de control, H, va conine 3 linii i 7 coloane.Din relaia de codare (2.1.1), rezult relaiile 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

Rezult cuvntul 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 observ c m=3 i n=7. Coloana hi exprim n 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)

8/8/2019 or TIC

18/49

17

Decodarea zecimal a corectorului z, indic poziia erorii, dac este 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 calculeaz cu 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 eronat este:

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

Rezult cuvntul eroare:0100000

Se poate scrie:'

V V 1001001 0100000 1101001

Rezult secvena de informaie:

3 5 6 7i i i i i 0001

2.1.2. Cod Hamming corector de o eroare i detector de dou erori

Condiia necesari suficient pentru ca un cod s poat simultan corecta maxim terori i a detectamaxim e erori este ca distana minim a codului s fie:

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

8/8/2019 or TIC

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 form explicit:

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 observ c exist 4 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. Rezult c matricea de control, H, va conine 4 linii i 8 coloane.Din relaia de codare (2.1.8), rezult relaiile 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

Rezult cuvntul de cod:V=01011010

8/8/2019 or TIC

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, reprezint corectorul de la codul Hamming corector de o eroare; z0, reprezint simbolul binar, 0 sau 1, cu ajutorul cruia se pot detecta erori pare (z0=0).Exist patru cazuri:

Cazul 1:

0

z 0

z 0

nu exist erori sau nu exist erori detectabile prin cod.

Cazul 2:

0

z 1

z 0

se face detecia erorilor duble.

Cazul 3:

0

z 0

z 1

simbolul C0 este eronat.

Cazul 4:

0

z 0

z 1

exist o 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

8/8/2019 or TIC

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

Rezult c avem situaia cazului 4, cnd exist o eroare corectabil.Aadar, rezult r:

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, adic 4-1=3, i3.Rezult cuvntul eroare:

00010000

Se poate scrie: 'V V 01001010 00010000 01011010

Rezult secvena de informaie:

3 5 6 7i i i i i 1010

Desfurarea lucrrii:

a) Se lanseaz executabilul Hamming.exe din directorul Hamming, dup care 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 cele prezentate 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, dup care, cu programul, se verific rezultatele obinute.d) La sfritul lucrrii de laborator se va efectua un test asupra cunotinelor acumulate. Rezultatultestului se va concretiza printr-o not, calculat automat 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 independent de 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 ciclic a 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 nesistematic vom 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,

8/8/2019 or TIC

22/49

21

coeficienii vi fiind 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 reprezint numrul 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 valabil relaia :

0xg

xvrest (2.2.3)

Deci cuvintele de cod se aleg astfel nct s fie 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 singur eroare atunci:

n = 2m 1. (2.2.5)

Codurile ciclice corectoare de o eroare, avnd distana de cod (distana Hamming minim ntrecuvintele codului) dHmin = 3, sunt capabile s corecteze o eroare sau s detecteze dou.

Codarea codului ciclic corector de o eroare

Codarea va fi prezentat n dou moduri nesistematic sau sistematic.

Cu relaia v(x) = i(x)g(x) se poate face codarea nesistematic, dar pentru c nu este util npractic nu va fi luat n considerare .

n continuare va fi deci prezentat codarea sistematic unde corespondena dintre i(x) i v(x)este dat prin relaia:

xg

xxirestxxixvm

m (2.2.6)

unde

xgxxi

restm

semnific restul mpririi polinomului i(x)xm la 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 facut polinomial sau matricial.

a) Polinomial

Codarea va fi prezentat printr-un exemplu, putnd fi uor generalizat.

8/8/2019 or TIC

23/49

22

Fie g(x) = x3 + x + 1. Deci m = 3 i cu relaia 2m 1 = n rezult c n = 7 de unde k = n m = 4. Vomavea ca atare 4 bii de informaie i = vn-1vn-2vn-3vn-4 cu 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 c n = 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 = v6v5v4v3v2v1v0 unde 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), intr n 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 comand P1i P2).n urmtoarele m tacte ntreruptorul 1 este deschis iar ntreruptorul 2 este nchis, astfel csecvena r, generat de RDR, este livrat la ieirea v.

8/8/2019 or TIC

24/49

23

a) Codor ciclicRDR ;

b) Semnalele de validare

a porilor AND

Fig. 2.2.1 Codor ciclic cu RDRi 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 rezult relaia:

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 fcut mai sus rezult c Sn = 0.Considernd acela exemplu

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

8/8/2019 or TIC

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 dou proceduri de calcul ne-au dus la aceleai rezultate .Cuvntul de cod va fi v = v6v5v4v3v2v1v0.

Decodarea codului ciclic corector de o eroareDecodarea 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, dup destinaia codului i apoi selecia biilor de informaie.Verificarea presupune calculul restului mpririi lui w(x) la g(x). Dac restul este 0 se decide:

cuvnt corect recepionat. Dac nu, 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.

Dac codul este corector de o eroare, atunci decodarea decurge astfel:

1- se calculeaz corectorul zn cu formula:

UTUTvz j1-n

0jj

j1-n

0j

'j

(2.2.17)

unde j reprezint coeficienii polinomului eroare:

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

2- dac z = 0 se decide c w(x) este corect w(x) = v(x)- dac z 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.

8/8/2019 or TIC

26/49

25

a) Decodarea polinomialMetoda const n mprirea lui w(x) la g(x). Va rezulta un polinom rest, r(x). Dac acesta este

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

Spre exemplu fie : w(x) = x6 + x5 + x3 + x2 + 1. Calculm rest w(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 anex este eronat w2. Schimbnd valoarea bitului w2 rezult :

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

8/8/2019 or TIC

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 prezentat structura unui decodor ciclic corector de o eroare. Biii cuvntului

recepionat vor intra n schem unul dup altul 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 pstreaz cuvntul recepionat care intr pas cu pas idou subscheme cu RDR pentru corecie care funcioneaz n contratimp. Procedura de decodaredureaz 2n tacte. n primele n tacte n memorie intr cuvntul 1 care prin poarta P1 intri n primuldecodor, ieirea acestuia fiind 0 pentru c P2 este 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 sumatori este corectat de primul decodor care identific starea 00.....1i care are acces la sumator prin P2.

Dup n = 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.Dac eroarea afecteaz bitul vrstarea registrului de deplasare cu reacie dup intrarea ntregului cuvnteste:

S7 = v6T6U+ v5T

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

Deoarece la emisie S7 = 0 i vj = vj pentru j ri vr= vr+ 1 rezult:

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

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

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

S7+n-r-1 = Tn-r-1 S7 = 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-1 fixi prin poarta P2 care este nchis va emite semnalulde corecie (blocul IDENTIFIC genereaz un 1L) care se nsumeaz cu 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

..

..

..

..

8/8/2019 or TIC

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 generatori 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 const n 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 polinomulgeneratori secvena de informaie respectiv secvena recepionat generate aleator de calculator.

8/8/2019 or TIC

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-1 vn-2 ... v1 v0 vj GF(2q, p(x)) j = 0 n-1 (3.1.1)

unde coeficienii uj sunt coeficieni binari (fac parte din cmpul binar0, 1).Polinomul corespunztor acestui cuvnt fiind:

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

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

adic un 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 s fie 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 aib gradul m rezult c gm = 1, iar g0 trebuie s fie i el egal cu 1

pentru c altfel 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 fcut n dou moduri:

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)

Aceast relaie se mai poate scrie:

8/8/2019 or TIC

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)xm la g(x).Relaia (3.1.8) poate fi adus sub 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 s ndeplineasc anumite condiii. tiim c

v(x) trebuie s fie multiplu al lui g(x) i c g(x) trebuie s fie 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 =

i GF(2q).Aceste rdcini i sunt 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 lucreaz GF(2q).Pe g(x) l vom determina ca cel mai mic multiplu comun al polinoamelor minimale a rdcinilori.

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 determin obinerea unui cuvnt de cod avnd distana minim d 2t + 1.n cazul codurilor ciclice binare, dac este o rdcini 2, 22, ... 2(q-1) sunt tot rdcini i

deci pentru a forma polinomul generator este suficient s lum rdcinile impare:

8/8/2019 or TIC

31/49

30

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

2t-1.

Structura matricii de control H n cazul codurilor BCH se determin deci impunnd ca v(x) saib rdcini pe 1 = , 3 =

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

Faptul ci este rdcin a cuvntului de cod v(x) se exprim prin 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 aceast relaie ca pe un produs scalar al cuvntului format prin puterilelui i sau (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)

Aceast matrice este format din 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 formabinar dispunnd vertical cuvintele binare care nlocuiesc puterile lui . Forma binar a 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

generatori 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 dac este 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 s constatm c x4 + 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 c pentru orice cmp Galois n = 1, deci la noi 15 = 1.Cmpul GF(24) generat de p(x) = x4 + x + 1 obinut printr-o rdcin primitiv a lui x4 + x + 1 curelaia 4 = + 1 este cel dat n Anexa:

8/8/2019 or TIC

32/49

31

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

impare pn la 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 dou relaii puterile lui mai mari dect 15 s-au exprimat n funcie de15, iar suma s-a efectuat modulo doi.Cele dou polinoame 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 binar a lui H:

100011000110001 000110001100011

001010010100101011110111101111100010011010111010011010111100001001101011110000100110101111

H

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

Pentru o secven informaional i = 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 + 1 v(x) = x8 + x7 + x6 + x4 + 1adic v = 000000111010001

8/8/2019 or TIC

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 rezult din prezentarea urmtoare.Un cod ciclic corector de t erori are cuvinte de cod care au un numr r = 2t de rdcini i GF(2

q),

i=i

:

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

La recepie trebuie s verificm legea de codare dat de relaia (3.1.15). n cazul n care avem

erori de tip aditiv putem exprima aceast lege sub forma:

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

unde e(i) este eroarea i Si este 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 dou poziii 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 indic poziia 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 Si sub forma:

t

1k

iki XS

(3.1.22)

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

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

1 Calcularea sindromului erorii

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

1k

ik

ii

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

t1-t

1t

t

1kk ...xxXxx

(3.1.23)

Dac punem condiia ca Xks fie rdcin a lui (x) obinem:

0...XX t1-t

k1tk (3.1.24)

8/8/2019 or TIC

34/49

33

Dac nmulim (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)

Aceast ecuaie 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 coeficienilori n funcie de Si pentru 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

3 Cutarea poziiei eronate.Cunoscnd i putem determina poziia erorii.Dac mprim relaia (3.1.24) cu t

kX rezult relaia:

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:

8/8/2019 or TIC

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 respectiv este egal cu 1.

Exemplul 2:

Presupunem c recepionm un cuvnt BCH cu n = 15 i k = 7 i c avem t = 2 erori.

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

Calculm sindromul. Pentru t = 2 avem de calculat pn la S3 inclusiv (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 15 le-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)

8/8/2019 or TIC

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 demonstrativ att 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 corect a 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 genereaz n 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, ns sunt 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 vj GF(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 form ca 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 prezentat mai 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, c v(x) este un multiplu al lui g(x).

Codul RS, avnd parametrii n, ki m, construit dup relaia (3.2.2), este capabil s corecteze unnumr ec de caractere eronate, unde:

2ec = m = n-k (3.2.4)

8/8/2019 or TIC

37/49

36

La decodare, spre deosebire de codurile ciclice, ntr-un cuvnt de cod RS recepionat, nvederea coreciei, este necesar att 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. Dac ne referim la un cuvnt de lungime n, unde:

n = 2q

1 (3.2.5)

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

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

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

ip1 = log2(n+1) (3.2.7)

Aceast informaie poate fi coninut de un caracter din GF(2q). Deasemenea i valoarea erorii, , poates fie 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, rezult c poate lua orice valoare din GF(2q), adic

2q

valori posibile. Informaia necesar pentru a preciza valoarea ei este identic cu cea dat de (3.2.7).n concluzie, pentru fiecare eroare ce se dorete a fi corectat este necesar o 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 ip22ip1 1.

Cele 2t caractere de informaie necesare soluionrii problemei coreciei se afl din 2t ecuaii,care nseamn tot 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 nseamn c rdcinile lui g vor fi i rdcini pentru v. Rezult necesitatea cag s aib 2t rdcini. Aceste rdcini pot fi oricare dintre cele 2q elemente ale cmpului GF(2q). Vomalege pentru g rdcinile , 2, 3, ... 2t, datorit simplitii 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 c elementele , 2, 3, ... 2t sunt rdcini pentru polinomul ataat, v(x).

8/8/2019 or TIC

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)x2 este 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)x2 la g(x), cerut pentru 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 fcut att 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 c polinoamele ataate lor sunt divizibile cu g(x), adic elementele cmpuluiGF(22) , 2, , 2t sunt 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)

8/8/2019 or TIC

39/49

38

Aceste proprieti constituie i punctul de plecare n decodare. Presupunnd c w 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 c dac nu exist erori 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

Dac exist 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)

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

ikiX (3.2.19)

reprezint locatorul 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) reprezint un 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 c Xi , 1 i t este o rdcin a 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)

8/8/2019 or TIC

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 As gsim 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) rezult un 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 exist As-1 iar ecuaia (3.2.25) are soluie dat prin relaia(3.2.27).Se vor gsi t erori n acest caz.

3 rangul matricii As este e`

8/8/2019 or TIC

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 c problema aresoluie doar dac e < 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 Yi pentru 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 demonstrativ att 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 corect a 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.

8/8/2019 or TIC

42/49

41

L4. Coduri convoluionale

Codurile convoluionale au fost introduse n 1954 de P. Elias i reprezint o clas de 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 consecin codurile 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 memoreaz cele m blocuri de ksimboluri de informaie, dintr-o mulime de funcii liniare,ce genereaz blocurile de n simboluri de la ieire i dintr-un convertor paralel-serie. MrimeaR=k/n senumete 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 n linii inumr infinit de coloane, unde n > 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 ataeaz o 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 oricej pozitiv i pentru orice ks 1 ,atunci codul se numete sistematic. Fcnd apel la o reprezentare polinomial, matricile Ii V se 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)

8/8/2019 or TIC

43/49

42

Cu aceste notaii, relaia de codare,poate fi scris astfel :

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 ordinul k,Ik, atunci codurile sunt sistematice. n acest caz biii din I se vor regsi printre biiidin V. Astfel, dac celeksimboluri de informaie, prezente sunt efectiv emise, adic se gsesc n modexplicit n blocul de n simboluri de la ieirea codorului peprimele kpoziii, codul se numete codsistematic. Pentru codurile nesistematice, biii din V sunt 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 bjs sunt finite. Deci, dac exist cel puin un polinom bjs(D)1, atunci codul esterecursiv.

Lungimea de constrngere este unul dintre parametri importani ai codurilor convoluionale. Oalt definiie a sa este dat n 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 esteconstituit din 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

8/8/2019 or TIC

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 dou secvene 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 liniar a 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 exprim n 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,1

DDDG (2.14)

i

i

c

+ DD

+

8/8/2019 or TIC

45/49

44

n figura urmtoare sunt prezentate dou exemple 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 asociat codorului 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)

8/8/2019 or TIC

46/49

45

Diagrama trellis

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

S2 = (10) i S3 = (11), cele patru stri posibile ale codorului din Fig. 4.1. Oricare ar fistarea iniial a 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 c starea sa iniial era 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.

Dup m+1 ntrzieri, oricare ar fi starea iniial a codorului, trellis-ul se repet. Dinfiecare nod pleac 2k ramuri (n cazul de fa sunt dou ramuri) i n fiecare nod converg 2kramuri.

Pornind de la starea S0=(00) n momentul t=0, de exemplu, vedem c exist patru cicare permit atingerea strii S0=(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

8/8/2019 or TIC

47/49

46

Codarea codului convoluional

Folosind o codare convoluional, se codeaz urmtoarea secven de 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, datorit acestui fapt au aprut dou grupe suplimentare de bii.

Calea pe trellis care ne genereaz cuvntul de cod, v, este cea marcat cu rou.

Decodarea codului convoluional, algoritmul Viterbi cu decizie hard

Pentru prezentarea acestui algoritm se consider un canal binar simetric (fr memorie), intrareadecodorului fiind alctuit dintr-o secven de simboluri binare.

n fiecare moment dou ramuri, aparinnd la dou ci diferite, converg spre fiecare nod al trellis-lui (Fig.4.6). Din aceste dou ci una este mai probabil, altfel spus, se gsete la cea mai mic distan

Hamming fa de secvena recepionat, dect cealalt cale. Distana fiind o funcional aditiv, nfiecare nod se pstreaz calea cea mai probabil numit cale supravieuitoare. Dac se obin dou cicu aceeai distan Hamming, doar o singur cale este pastrat, alegndu-se n mod arbitrar una dincele dou ci posibile.

n figura urmtoare se prezint un exemplu de decodare pentru codorul reprezentat n Fig. 4.3.b), cu diagrama de stri reprezentat n Fig. 4.5. c). Calea rezultant este marcat cu 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

8/8/2019 or TIC

48/49

47

w: 10 10 01 11 11 10 01 01

Tact:0 1 2 3

or TIC

Documents

Transcript of or TIC