Download - Indrumator TIC
-
7/26/2019 Indrumator TIC
1/49
TEORIA INFORMAIEI I A CODRII
ndrumtor de lucrri la laborator
Horia BALTA Maria KOVACI
2009
-
7/26/2019 Indrumator TIC
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
-
7/26/2019 Indrumator TIC
3/49
2
-
7/26/2019 Indrumator TIC
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.
-
7/26/2019 Indrumator 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 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.
-
7/26/2019 Indrumator TIC
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/26/2019 Indrumator 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 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)
-
7/26/2019 Indrumator TIC
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
Codurile sunt: 0 - 0a - 1
Mesajul transmis este: a1
-
7/26/2019 Indrumator 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
Codurile sunt: 0 - 0a - 1
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
Codurile sunt: 0 - 000a - 1b - 01c - 001
Mesajul transmis este: a110b00c001
6
3 3
10
5 6
7
a
2 1
10
3 4 b
0 210
1 2 c
-
7/26/2019 Indrumator TIC
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
Codurile sunt: 0 - 000a - 1
b - 001c - 01
Mesajul transmis este: a110b00c001
6
3 3
10
5 6
7
a
1 2
10
3 4 c
0 1
10
1 2 b
Codurile sunt: 0 - 000a - 1
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
Codurile sunt: 0 - 100a - 0b - 101c - 11
Mesajul transmis este: a110b00c00101
7
3
0
5
7
a 4
1
6
1 3
10
3 4 c
0 1
10
1 2 b
-
7/26/2019 Indrumator TIC
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
-
7/26/2019 Indrumator 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 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
-
7/26/2019 Indrumator TIC
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)
-
7/26/2019 Indrumator TIC
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.
-
7/26/2019 Indrumator TIC
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
-
7/26/2019 Indrumator 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 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.
-
7/26/2019 Indrumator TIC
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)
-
7/26/2019 Indrumator TIC
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
-
7/26/2019 Indrumator 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 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
-
7/26/2019 Indrumator 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, 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
-
7/26/2019 Indrumator 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
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,
-
7/26/2019 Indrumator TIC
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.
-
7/26/2019 Indrumator TIC
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.
-
7/26/2019 Indrumator TIC
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
-
7/26/2019 Indrumator 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 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.
-
7/26/2019 Indrumator TIC
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
-
7/26/2019 Indrumator 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 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
..
..
..
..
-
7/26/2019 Indrumator 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 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.
-
7/26/2019 Indrumator 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-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:
-
7/26/2019 Indrumator 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)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:
-
7/26/2019 Indrumator TIC
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:
-
7/26/2019 Indrumator TIC
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
-
7/26/2019 Indrumator 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 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)
-
7/26/2019 Indrumator TIC
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:
-
7/26/2019 Indrumator 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 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)
-
7/26/2019 Indrumator 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 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)
-
7/26/2019 Indrumator TIC
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).
-
7/26/2019 Indrumator 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)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)
-
7/26/2019 Indrumator TIC
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)
-
7/26/2019 Indrumator 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 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`
-
7/26/2019 Indrumator 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 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.
-
7/26/2019 Indrumator TIC
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)
-
7/26/2019 Indrumator TIC
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
-
7/26/2019 Indrumator 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 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
+
-
7/26/2019 Indrumator TIC
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)
-
7/26/2019 Indrumator TIC
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
-
7/26/2019 Indrumator TIC
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
-
7/26/2019 Indrumator TIC
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