Decodor Reed Solomon

Cuprins

Introducere la codurile Reed – Solomon

Probabilitatea de eroare la codurile Reed – Solomon

Performanța codurilor R – S față de zgomotul de tip burst

Câmpuri finite

Adunarea în câmpul extins GF (2m)

Polinomul primitiv folosit la definirea unui câmp

Câmpul extins (23)

Codarea Reed – Solomon

Codarea în formă sistematică

Codarea sistematică cu un registru de deplasare cu (n-k) stări

Decodarea Reed – Solomon

Calculul sindroamelor

Algoritmul Berlekamp – Massey

Algoritmul Euclidian

Algoritmul Chien Search

Algoritmul Forney

Aplicații ale codurilor Reed – Solomon

2.1.1 Întrețeserea

2.1.2 Întrețeserea încrucișată

2.1.3 Coduri Reed – Solomon întrețesute încrucișate

2.1.4 Coduri produs

2.1.5 Acoperirea erorilor

2.1.6 Interpolarea

2.1.7 Reducerea volumului audio la zero

2.1.8 Duplicarea

2.2 Sistemele de telecomunicații

2.3 Controlul erorilor pentru sisteme cu reacție

3. Design RTL Verilog al decocorului Reed – Solomon (15, 5)

3.1 Arhitectură și funcționare

3.2 Blocurile componente ale design-ului

3.2.1 Blocul SYNDROME

3.2.2 Blocul BMAlg

3.2.3 Blocul BMUnitar

3.2.4 Blocul CHIENSearch

3.2.5 Blocul FORNEYAlg

3.3 Cazuri de funcționare ale decodorului

3.4 Configurarea Design-ului Hardware pe FPGA

3.4.1 Footprint-ul PCB al plăcuței

3.4.2 Diagrama bloc funcțională

3.4.3 Sursa de curent

3.4.4 Interfața USB 2.0

3.4.5 Perifericele plăcuței

3.4.6 Conectori de expansiune

3.4.7 Suportul FrontPanel

3.4.8 Rezultatele configurării codului RTL sintetizat pe FPGA

3.5 Mediu de verificare hardware

3.5.1 Introducere – conceptul de verificare hardware si implementarea lui

3.5.2 Mediul de verificare pentru deocodorul Reed-Solomon

bibliografie

Pagini 66

=== decodor ===

Cuprins

Introducere la codurile Reed – Solomon

Probabilitatea de eroare la codurile Reed – Solomon

Performanța codurilor R – S față de zgomotul de tip burst

Câmpuri finite

Adunarea în câmpul extins GF (2m)

Polinomul primitiv folosit la definirea unui câmp

Câmpul extins (23)

Codarea Reed – Solomon

Codarea în formă sistematică

Codarea sistematică cu un registru de deplasare cu (n-k) stări

Decodarea Reed – Solomon

Calculul sindroamelor

Algoritmul Berlekamp – Massey

Algoritmul Euclidian

Algoritmul Chien Search

Algoritmul Forney

Aplicații ale codurilor Reed – Solomon

2.1.1 Întrețeserea

2.1.2 Întrețeserea încrucișată

2.1.3 Coduri Reed – Solomon întrețesute încrucișate

2.1.4 Coduri produs

2.1.5 Acoperirea erorilor

2.1.6 Interpolarea

2.1.7 Reducerea volumului audio la zero

2.1.8 Duplicarea

2.2 Sistemele de telecomunicații

2.3 Controlul erorilor pentru sisteme cu reacție

3. Design RTL Verilog al decocorului Reed – Solomon (15, 5)

3.1 Arhitectură și funcționare

3.2 Blocurile componente ale design-ului

3.2.1 Blocul SYNDROME

3.2.2 Blocul BMAlg

3.2.3 Blocul BMUnitar

3.2.4 Blocul CHIENSearch

3.2.5 Blocul FORNEYAlg

3.3 Cazuri de funcționare ale decodorului

3.4 Configurarea Design-ului Hardware pe FPGA

3.4.1 Footprint-ul PCB al plăcuței

3.4.2 Diagrama bloc funcțională

3.4.3 Sursa de curent

3.4.4 Interfața USB 2.0

3.4.5 Perifericele plăcuței

3.4.6 Conectori de expansiune

3.4.7 Suportul FrontPanel

3.4.8 Rezultatele configurării codului RTL sintetizat pe FPGA

3.5 Mediu de verificare hardware

3.5.1 Introducere – conceptul de verificare hardware si implementarea lui

3.5.2 Mediul de verificare pentru deocodorul Reed-Solomon

1. Introducere la codurile Reed-Solomon

În 1960, Irving Reed și Gus Solomon au publicat un articol în Jurnalul Societǎții pentru Matematici Industriale și Aplicate. Acest articol descria o nouǎ clasǎ de coduri corectoare de erori denumite acum coduri Reed-Solomon (R-S). Aceste coduri au o mare putere și utilitate, fiind întǎlnite astǎzi în multe aplicații pentru comunicații digitale si stocare de date, cum ar fi:

dispozitive pentru stocare de date: Compact Disc (CD), DVD, etc;

comunicații mobile sau wireless: telefoane celulare, link-uri pentru microunde, etc;

comunicații prin satelit;

televiziune digitală;

modem-uri de mare viteză: ADSL, VDSL, etc;

Codurile Reed-Solomon sunt coduri ciclice non-binare compuse din simboluri de câte m biți, unde m este orice întreg pozitiv cu o valoare mai mare decât 2. Codurile R-S (n, k) pe simboluri de m biți există pentru n și k pentru care:

0< k < n < 2m + 2 (1)

unde k este numărul de simboluri de date codate, care conțin informația, și n este numărul total de simboluri de cod din blocul rezultat după codarea Reed – Solomon. Pentru cel mai convențional cod R-S (n, k),

(n, k) = (2m – 1, 2m – 1 – 2t) (2)

unde t este numărul de simboluri corectabile de către cod, și n – k = 2t este numărul de simboluri de paritate.

Codurile Reed – Solomon ating cea mai mare distanță de cod minimă pentru orice cod liniar cu aceeași lungime de bloc la intrarea și ieșirea codorului. Pentru coduri non-binare distanța dintre două cuvinte de cod este definită ca fiind numărul de simboluri pentru care cuvintele diferă. Pentru coduri Reed – Solomon, distanța de cod minimă este dată de relația:

dmin = n – k + 1 (3)

Codul este capabil să corecteze orice combinație de t sau mai puține erori, unde t poate fi exprimat ca:

t = [(dmin – 1) / 2] = [(n – k) / 2] (4)

unde [x] reprezintă cel mai mare întreg care nu îl depășește pe x. Ecuația (4) arată că pentru codurile R- S, corectarea a t erori de simbol nu cere mai mult de 2t simboluri de paritate. Această ecuație dă urmatorul raționament intuitiv: se poate spune că decodorul poate folosi n – k simboluri redundante, adică de două ori numărul de erori corectabile. Pentru fiecare eroare, un simbol redundant este utilizat pentru a localiza eroarea, și un alt simbol redundant este folosit pentru a găsi valoarea corectă.

Capacitatea de corecție doar a locațiilor erorilor, ρ, a codului este:

ρ = dmin – 1 = n – k (5)

Capacitatea de corectie simultană atât a erorilor cât și doar a locațiilor care conțin erori poate fi exprimată după cum urmează:

2α + γ < dmin < n – k

unde α este numărul de erori de simbol care pot fi corectate și γ este numărul de locații de erori care pot fi detectate. Un avantaj al codurilor non-binare precum Reed – Solomon poate fi observat din următoarea comparație: să considerăm un cod binar (n, k) = (7, 3). Întregul spațiu de combinații de câte 7 biți conține 2n = 27 = 128 de combinații, dintre care 2k = 23 = 8 (1/16 dintre combinații) sunt cuvinte de cod. În continuare să considerăm un cod non-binar (n, k) = (7, 3) în care fiecare simbol este format din m = 3 biți. Spațiul de combinații de cate n x m biți posibile ajunge la 2nm = 221 = 2.097.152 combinații dintre care 2km = 29 = 512 (1/4096 dintre combinații) sunt cuvinte de cod. În cazul simbolurilor binare pe m biți doar o mică fracțiune (2km din numărul mare de 2nm) din combinațiile posibile sunt cuvinte de cod. Această fracțiune scade când m crește. Important este că atunci când o mică fracțiune din spațiul de combinații de n x m biți este utilizată pentru cuvinte de cod, se poate crea o distanță dmin mare.

Orice cod liniar este capabil să corecteze n – k locații de erori, dacă respectivele locații se regăsesc printre simbolurile de paritate. Totuși codurile R-S au proprietatea remarcabilă că pot corecta orice set de n – k locații de erori în cadrul blocului. Codurile R-S pot fi proiectate să aibă orice redundanță. Totuși complexitatea unei implementări de mare viteză crește odată cu redundanța. Așadar cele mai atractive coduri Reed-Solomon au rata de cod mare (redundanță scăzută).

1.1 Probabilitatea de eroare la codurile Reed – Solomon

Codurile Reed – Solomon sunt utile în mod deosebit pentru corectarea erorilor grupate (burst); deci sunt eficace pentru canalele cu memorie. De asemenea, pot fi folosite eficient pentru canalele unde setul de simboluri de intrare e mare. O caracteristică importantă a codurilor R-S este că doar 2 simboluri informaționale pot fi adăugate unui cod R-S de lungime n fără a-i reduce distanța minimă. Acest cod R-S extins are lungimea n + 2 și același număr de simboluri de paritate ca și codul original. Probabilitatea de eroare de simbol la decodarea R-S, PE , în funcție de probabilitatea de eroare de simbol a canalului, p, poate fi scrisă după cum urmează:

PE (7)

unde t este numărul de simboluri corectabile de către cod, simbolurile fiind fiecare alcătuite din cate m biți.

Probabilitatea de eroare de bit poate fi mărginită superior de probabilitatea de eroare de simbol pentru anumite tipuri de modulații. Pentru modulația MFSK cu M = 2m ,

relația dintre probabilatea de eroare de bit, PB și cea de simbol, PE este după cum urmează:

(8)

Figura 1 ilustrează probabilitatea de eroare de bit față de probabilitatea de eroare de simbol de pe canal, p, schițată în funcție de ecuațiile (7) și (8) pentru diverse coduri Reed – Solomon ortogonale corectoare de t erori cu n = 31 (31 de simboluri de 5 biți pe cod bloc).

Figura 1: probabilitatea de eroare de bit în funcție de probabilitatea de eroare de simbol pe canal

Figura 2 ilustrează probabilitatea de eroare de bit, PB față de Eb / N0 (raportul semnal – zgomot) pentru un sistem care folosește modulația MFSK asemenea celui descris mai sus și demodulare necoerentă pe un canal AWGN. Pentru codurile R-S, probabilitatea de eroare este o funcție de lungimea de bloc, n, care descrește exponențial, iar complexitatea de decodare este proporțională cu o putere mică a lui n. Codurile R-S sunt uneori folosite într-un aranjament concatenat. Într-un asemenea sistem, un decodor convoluțional intern asigură mai întâi un oarecare control asupra erorilor acționând asupra ieșirilor unui demodulator cu decizie software; decodorul convoluțional prezintă apoi datele cu decizie hardware decodorului Reed-Solomon extern care reduce în continuare probabilitatea de eroare.

Figura 2: probabilitatea de eroare de bit în funcție de raportul semnal/zgomot

1.2 Performanța codurilor R-S față de zgomotul de tip burst

Să considerăm un cod R-S cu (n, k) = (255, 247) în care fiecare simbol este format din m = 8 biți (simbolurile pot fi astfel denumite bytes). Întrucât n – k = 8, ecuația (4) ne indică faptul că acest cod poate corecta oricare 4 simboluri eronate dintr-un bloc de 255 de simboluri. Presupunem prezența unui zgomot de tip burst, care cuprinde 25 de biți și afectează un bloc de date în cadrul trasmisiei, după cum arată figura 3.

Figura 3: exemplu de transmisie afectată de burst

Subliniem că zgomotul de 25 de biți trebuie sa afecteze exact 4 simboluri de date. Decodorul Reed-Solomon pentru codul (255, 247) va corecta oricare 4 simboluri eronate indiferent de proporția în care au fost afectați biții din interiorul simbolului. Cu alte cuvinte, atunci când decodorul corectează un byte, înlocuiește byte-ul incorect cu cel corect, chiar dacă eroarea a fost cauzată de un singur bit corupt sau de 8 biți corupți. Acest lucru îi dă codului R-S un avantaj enorm din punctul de vedere al zgomotului de tip burst față de codurile binare, permițând chiar intercalarea codurilor binare. În acest exemplu, dacă zgomotul de 25 de biți ar fi fost distribuit în mod arbitrar și nu contiguu, mai mult decât 4 simboluri ar fi fost afectate, ceea ce bineînțeles ar fi depășit capacitatea de corecție a codului R-S (255, 247).

Pentru ca un cod să combată cu succes efectele zgomotului, durata zgomotului trebuie să reprezinte un procent relativ mic din cuvântul de cod. Pentru a asigura acest lucru în majoritatea timpului, zgomotul recepționat ar trebui sa fie mediat pe o perioadă mare de timp, reducând efectul unei porțiuni nenorocoase. Astfel codurile corectoare de erori devin eficiente pe măsură ce lungimea codului bloc crește, făcând codurile R-S o alegere atractivă de fiecare dată când se doresc lungimi mari de cod bloc. Acest aspect se poate observa și din familia de curbe din figura 4, în care rata de cod este menținută constantă la 7 / 8, în timp ce mărimea blocului crește de la n = 32 simboluri la n = 256 de simboluri. Deci mărimea blocului crește de la 160 de biți la 2048 de biți.

Pe măsură ce redundanța unui cod R-S crește (rata de cod scade), implementarea sa crește în complexitate (mai ales pentru dipozitivele de mare viteză). De asemenea, banda de frecvență trebuie sa crească pentru orice aplicație de comunicații în timp real. Totuși, beneficiul redundanței crescute, ca și beneficiul mărimiii de simbol crescute, constă în îmbunătățirea performanței corectării erorii la nivel de bit, după cum se vede în figura 5, unde lungimea de cod, n este menținută constantă la 64, în timp ce numărul de simboluri de date descrește de la k = 60 la k = 4 (redundanța crește de la 4 simboluri la 60 de simboluri).

Figura 5 reprezintă funcțiile de transfer (probabilitatea de eroare de bit la ieșire față de probabilitatea de eroare de simbol a canalului, la intrare) ale unor decodoare ipotetice. Întrucât nu se vorbește și despre un sistem sau canal de transmisie, se poate ajunge la concluzia că funcția care exprimă dependența performanței de corecție a erorilor de redundanță este monotonă, asigurând astfel, în mod continuu, îmbunătățirea sistemului, chiar pe măsură ce rata de cod ajunge la 0. Totuși acest lucru nu se întâmplă

Figura 4: probabilitatea de eroare de bit la ieșire în funcție de probabilitatea de eroare de bit aleatoare pe canal

pentru codurile care operează într-un sistem de comunicații în timp real. Pe măsură ce rata de cod variază de la minim la maxim (de la 0 la 1), sunt interesante de observat efectele ilustrate în figura 6. Aici, curbele de performanță sunt schițate pentru modulația BPSK și un cod R-S (31, k) pentru diferite tipuri de canal. Figura 6 reflectă un sistem de comunicații în timp real, în care prețul plătit pentru codarea corectoare de erori este extinderea benzii de frecvență cu un factor egal cu inversa ratei de cod. Curbele schițate ilustrează rate de cod optime care minizează raportul semnal – zgomot Eb / N0 impus. Rata de cod optimă este de aproximativ 0.6 – 0.7 pentru un canal gausian, 0.5 pentru un canal cu fading de tip Rician (cu raportul dintre puterea de semnal recepționat direct și cel reflectat, K = 7 dB), și 0.3 pentru un canal cu fading de tip Rayleigh. Care este

Figura 5: probabilitatea de eroare de bit la ieșire în funcție de probabilitatea de eroare de bit aleatoare pe canal pentru n = 64

motivul pentru care apare o degradare a raportului Eb / N0 pentru rate de cod foarte mari (redundanță mică) și rate foarte mici (redundanță mare)? Este ușor de explicat degradarea la rate foarte mari comparată cu rata optimă. Orice cod oferă, în general, un beneficiu prin câștigul de codare; deci, pe măsură ce rata de cod se apropie de unitate (caz în care nu există codare), sistemul va fi mai puternic afectat de erori de transmisie. Degradarea la rate de codare mai mici este mai subtilă deoarece în sistemul de comunicații în timp real care utilizează atât modulație cât și codare, există două mecanisme active. Un mecanism lucrează pentru a îmbunătăți performanța de eroare, iar celălalt lucrează pentru a o degrada. Mecanismul de îmbunătățire este codarea; cu cât redundanța este mai mare, cu atât capacitatea de corectare a erorilor de către cod va fi mai mare. Mecanismul de degradare este reducerea energiei pe simbol de canal (comparativ cu simbolul de date) care reduce redundanța. Energia de simbol redusă cauzează mai multe erori la demodulare. Este posibil ca cel de-al doilea mecanism să câștige, și astfel la rate de codare foarte mici, sistemul se confruntă cu o degradare a performanței de eroare.

Vom demonstra în figura 6 performanța de eroare față de rata de codare, ținând cont de curbele din figura 2. Figurile nu sunt comparabile deoarece modulația din figura 6 este BPSK și MFSK în figura 2. Însă vom verifica faptul că performanța de eroare față de rata de codare, manifestă aceeași dependență cu modulația MFSK precum și cu modulație BPSK. În figura 2, performanța de eroare pe un canal AWGN se îmbunătățește pe măsură ce capacitatea de corectare a simbolurilor, t, crește de la t = 1 la t = 4; cazurile t = 1 și t = 4 corespund codurilor R-S (31, 29) și R-S (31, 23) având rate de codare de 0.94 și respectiv 0.74. Totuși, la t = 8, care corespunde codului R-S (31, 15) cu rata de codare 0.48, performanța de eroare la PB = 10-5 se degradează cu aproximativ 0.5 dB din raportul Eb / N0 comparativ cu cazul în care t = 4. Din figura 2 putem concluziona că dacă am fi schițat performanța de eroare față de rata de codare, curba ar fi avut aceeași formă generală ca în figura 6. A se observa că această manifestare nu poate fi dedusă din figura 1, întrucăt această figură reprezintă funcția de transfer a unui decodor, care nu furnizează nici o informație despre canalul de transmisie și demodulare. Prin urmare, dintre cele două mecanisme active în canal, funcția de transfer din figura 1 prezintă doar beneficiile ieșirii față de intrarea unui decodor fără a expune nimic despre pierderea de energie ca funcție de rata de codare scăzută.

Figura 6: raportul semnal/zgomot necesar pentru PB = 10-5 în funcție de rata de codare

1.3 Câmpuri finite

Pentru a înțelege principiile de codare si decodare a codurilor nonbinare, precum codurile Reed- Solomon, este necesar să pătrundem în zona câmpurilor finite cum sunt câmpurile Galois(GF). Pentru orice număr prim, p, există un câmp Galois notat GF(p) care conține p elemente. GF(p) poate fi extins la un câmp conținând pm elemente, denumit câmp extins al GF(p) și notat GF(pm) unde m este un întreg pozitiv. Câmpul GF(pm) conține ca subset elementele câmpului GF(p). Simbolurile din câmpul extins GF(2m) sunt utilizate în construcția codurilor Reed-Solomon.

Câmpul binar GF(2) este un subcâmp al câmpului extins GF(2m) în aceeași manieră în care mulțimea numerelor reale este un subcâmp al mulțimii numerelor complexe.

Înafară de numerele 0 și 1, există elemente unice adiționale în câmpul extins care vor fi reprezentate cu un nou simbol, α. Fiecare element diferit de 0 din GF(2m) poate fi reprezentat ca o putere a lui α. Un set infinit de elemente, F, este format plecând de la elementele {0,1, α} și generarând elemente adiționale prin multiplicarea progresivă a ultimului element format cu α, ceea ce conduce la următoarea mulțime:

F = {0, 1, α, α2, …., αj, …..} = {0, α0, α1, α2, …., αj, …..} (9)

Pentru a obține setul de elemente finite al câmpului GF(2m) din F, trebuie impusă o condiție pentru F astfel încât să conțină 2m elemente care să nu poată fi multiplicate. Condiția care închide setul de elemente al câmpului față de multiplicare este caracterizată de polinomul ireductibil de mai jos:

α + 1 = 0

sau echivalent

α = 1 = α0 (10)

Folosind această constrângere polinomială, orice element al câmpului care are o putere egală sau mai mare decât 2m – 1 poate fi redus la un element cu o putere mai mică decât 2m – 1, după cum urmează:

α = α α = α (11)

Deci, ecuația (10) poate fi folosită pentru a forma secvența finită F* plecând de la secvența infinită F după cum urmează:

F* = {0, 1, α, α2, …., α, α, α,….}

= {0, α0, α1, α2, …., α, α0, α1, α2, …} (12)

Astfel se poate observa din ecuația (12) că elementele câmpului finit, GF(2m), sunt după cum urmează:

GF(2m) = {0, 1, α, α2, …., α} (13)

1.4 Adunarea în câmpul extins GF(2m)

Fiecare din cele 2m elemente ale câmpului finit, GF(2m), poate fi reprezentat ca polinom distinct de grad m – 1 sau mai mic. Gradul unui polinom este egal cu valoarea celui mai mare exponent al său. Vom reprezenta fiecare din elementele diferite de 0 ale câmpului GF(2m) ca un polinom, ai (X), unde cel puțin unu din cei m coeficienți ai ai (X) este diferit de 0. Pentru i = 0, 1, 2, …., 2m – 2,

α i = ai (X) = ai,0 + ai,1 X + ai,2 X2 + ….+ ai,m-1 Xm-1 (14)

Considerăm cazul în care m = 3, câmpul finit fiind notat GF(23). Figura 7 arată maparea celor 7 elemente { αj } și elementul zero în funcție de elementele de bază {X0, X1, X2} descrise de ecuația (14). Întrucât ecuația (10) arată că α0 = α7 , rezultă că sunt 7 elemente nenule, respectiv un număr total de 8 elemente în acest câmp. Fiecare linie din figura 7 cuprinde o secvență de valori binare care reprezintă coeficienții ai,0 , ai,1 și ai,2 din ecuația (14). Unul din beneficiile folosirii elementelor { αj } ale câmpului extins în locul elementelor binare este notația compactă care facilitează reprezentarea matematică a codării nonbinare și a proceselor de decodare. Adunarea a două elemente din câmpul finit se definește ca suma modulo-2 a fiecăruia din coeficienții polinomiali corespunzători acelorași puteri.

α i + α j = (ai,0 + aj,0 ) + (ai,1 + aj,1 ) X + ….+( ai,m-1 + aj,m-1) Xm-1 (15)

Figura 7: elementele câmpului Galois GF(23)

1.5 Polinomul primitiv folosit la definirea unui câmp

Polinoamele primitive sunt de interes deoarece sunt folosite la definirea câmpurilor finite GF(2m), câmpuri folosite la definirea codurilor R-S. Condiția următoare este necesară și suficientă pentru a garanta că un polinom este primitiv. Un polinom ireductibil f(X) de grad m este primtiv dacă cel mai mic întreg pozitiv n pentru care f(X) divide polinomul Xn + 1 este n = 2m – 1. Amintim că afirmația A divide pe B înseamnă că A împărțit la B va da un cât diferit de zero și un rest nul.

Exemplu:

Ținând cont de definiția polinomului primitiv dată mai sus, să determinăm dacă polinoamele ireductibile de mai jos sunt sau nu primitive.

1 + X + X4

1 + X + X2 + X3 + X4

Soluție

Putem verifica dacă acest polinom este primitiv, determinând dacă divide Xn + 1 = X+ 1 = X15 + 1, dar nu divide Xn + 1 pentru valori ale lui n în intervalul 1 n < 15. Este ușor de verificat că 1 + X + X4 divide X15 + 1 iar după calcule repetate se poate observa că 1 + X + X4 nu va divide Xn + 1 pentru orice n din intervalul 1 n < 15. Deci, 1 + X + X4 este polinom primitiv.

Vom vedea că 1 + X + X2 + X3 + X4 divide X15 + 1. Testând dacă va divide Xn + 1 pentru n mai mic decât 15 duce la observația că divide de asemenea X5 + 1. Deci, acest al doilea polinom nu este primtiv.

1.6 Câmpul extins GF(23)

Să considerăm exemplul unui polinom primitiv și al câmpului finit pe care îl definește. Tabelul 1 conține lista unor polinoame primitive. Îl vom alege pe primul, f(X) = 1 + X + X3 care definește câmpul GF(2m), unde gradul polinomului este m = 3. Deci, există 23 = 8 elemente în câmpul definit de f(X). Acest polinom trebuie să aibă exact 3 rădăcini. Aceste rădăcini se găsesc în câmpul GF(23). Să definim α, un element al câmpului extins GF(23) ca rădăcină a polinomului f(X). Astfel se poate scrie:

f(α) = 0

1 + α + α3 = 0 (16)

α3 = -1 – α

Întrucât într-un câmp binar -1 = 1, α3 poate fi reprezentat după cum urmează:

α3 = 1 + α (17)

Deci , α3 este exprimat ca sumă de termeni ce depind de α și care au ordin mai mic. Plecând de la această relație, se pot exprima toate puterile lui α. Astfel, obținem:

α 4 = α α3 = α (1 + α) (18a)

α 5 = α α4 = α (α + α2) = α2 + α3 (18b)

Din ecuația (17) se obtine:

α 5 = 1 + α + α2 (18c)

Pentru α 6, folosind ecuația (18c) , obținem:

α 6 = α α5 = α (1 + α + α2) = α +α2 + α3 = 1 + α2 (18d)

Iar pentru α 7 folosim ecuația (18d)

α 7 = α α6 = α (1 + α ) = α + α3 = 1 = α0 (18e)

Astfel cele 8 elemente ale câmpului GF(23) sunt:

{0, α0 , α1 , α2 , α3, α4, α5, α6} (19)

Tabel 1

Maparea elementelor câmpului descrisă de ecuația (14) poate fi demonstrată utilizând registrul linear de deplasare cu reacție din figura 8. Circuitul generează 2m – 1 elemente nenule ale câmpului, având conexiunile de reacție corespunzătoare coeficienților polinomului f(X) = 1 + X + X3. Pornind circuitul în orice stare diferită de zero, să zicem 1 0 0, și realizând o deplasare la dreapta la fiecare ciclu de ceas, se poate verifica că fiecare din elementele câmpului din figura 7 (mai puțin elementul nul) vor apare ciclic în stările registrului de deplasare. Două operații aritmetice, adunarea și multiplicarea, pot fi definite pentru acest câmp, GF(23). Adunarea este ilustrată în tabelul 2, iar înmulțirea pentru elementele diferite de 0, în tabelul 3. Regulile adunării respectă operațiile (17) până la (18e) și pot fi verificate observând din figura 7 că suma oricăror 2 elemente poate fi obținută adunând modulo-2 coeficienții de același ordin ale elementelor lor de bază. Regulile înmulțirii din tabelul 3 urmează procedura obișnuită, în care produsul elementelor câmpului este obținut adunând exponenții modulo-(2m – 1) , sau pentru acest caz, modulo-7.

Figura 8: registru de deplasare care generează elementele câmpului GF(23)

Tabel 2

Tabel 3

Mai există o altă modalitate de a defini un polinom primitiv care îi face verificarea relativ ușoară. Pentru ca un polinom ireductibil să fie primitiv este necesar ca cel puțin una din rădăcinile sale sa fie element primitv. Un element primitv este cel care ridicat la exponenți de ordin superior, va genera toate elementele nenule ale câmpului. Câmpul fiind finit, numărul elementelor sale nenule este finit, de asemenea.

Exemplu:

Să găsim cele m = 3 rădăcini ale lui f(X) = 1 + X + X3 și să verificăm că polinomul este primitiv, testând că cel puțin una din rădăcinile sale este element primitv.

Soluție

Rădăcinile vor fi găsite prin eliminare. În mod evident, α0 = 1 nu este rădăcină deoarece f(α0) = 1. Vom folosi tabelul 2 pentru a verifica dacă α1 este rădăcină. Deoarece

f(α1) = 1 + α + α3 = 1 + α0 = 0

α este deci rădăcină.

Acum verificăm daca α2 este rădăcină:

f(α2) = 1 + α2 + α6 = 1 + α0 = 0

Deci și α2 este rădăcină.

Verificăm α3 :

f(α2) = 1 + α3 + α9 = 1 + α3 + α2 = 1 + α5 = α4 0

Așadar α3 nu este rădăcină. Este α4 rădăcină?

f(α4) = 1 + α4 + α12 = f(α2) = 1 + α4 + α5 = 1 + α0 = 0

Da, este rădăcină. Prin urmare, rădăcinile polinomului f(X) = 1 + X + X3 sunt α, α2 și α4. Nu este dificil de verificat că începând cu oricare din aceste rădăcini și generând exponenți de ordin superior va conduce la obținerea tuturor celor 7 elemente nenule ale câmpului. Deci, fiecare dintre rădăcini este un element primitv.

O metodă relativ simplă de a verifica că un polinom este primitiv poate fi descrisă într-o manieră asemănătoare cu acest exemplu. Pentru orice polinom care se dorește a fi testat, se va desena registrul de deplasare având conexiunile de reacție corespunzătoare coeficienților polinomului asemănător cu exemplul din figura 8. Se vor încărca regiștrii circuitului cu orice combinație diferită de zero și se va realiza deplasarea la dreapta la fiecare perioadă de ceas. Dacă circuitul generează fiecare din elementele nenule ale câmpului într-o perioadă, atunci polinomul care definește câmpul GF(2m) este un polinom primitiv.

1.7 Codarea Reed – Solomon

Ecuația (2), repetată mai jos ca ecuația (20) exprimă cea mai convențională formă a codurilor Reed – Solomon în termenii parametrilor n, k, t și orice întreg pozitiv m > 2.

(n, k) = (2m – 1, 2m – 1 – 2t) (20)

unde n – k = 2t este numărul simbolurilor de paritate, iar t, capacitatea de corectare a erorilor de simbol a codului. Polinomul generator pentru codul R-S are următoarea formă:

g(X) = g0 + g1X + g2X2 + …. + g2t-1X2t-1 + X2t (21)

Gradul polinomului generator este egal cu numărul simbolurilor de paritate. Codurile R-S sunt un subset al codurilor Bose, Chaudhuri și Hocquenghem (BCH), aceasta fiind explicația pentru relația dintre gradul polinomului generator și numărul simbolurilor de paritate. Întrucât polinomul generator are gradul 2t, trebuie să existe exact 2t puteri succesive ale lui α care să fie rădăcini ale polinomului. Desemnăm rădăcinile lui g(X) ca fiind α, α2, …., α2t . Nu este obligatoriu să începem cu α; se poate începe cu orice putere a lui α. Considerăm ca exemplu codul R-S (7, 3) corector de 2 erori de simbol. Descriem polinomul generator în termenii celor 2t = n – k = 4 rădăcini, după cum urmează:

g(X) = (X – α) (X – α2) (X – α3) (X – α4)

= (X2 – (α + α2) X + α3) (X2 – (α3 + α4) X + α7)

= (X2 – α4 X + α3) (X2 – α6 X + α0)

= X4 – (α4 + α6) X3 + (α3 + α10+ α0) X2 – (α4 + α9) X + α3

= X4 – α3 X3 + α0X2 – α1 X + α3

Schimbând ordinea puterilor din descrescătoare în crescătoare și înlocuind semnele negative cu semne pozitive, deoarece în câmpul binar -1 = +1, g(X) se poate exprima după cum urmează:

g(X) = α3 + α1 X + α0X2 + α3 X3 + X4 (22)

1.8 Codarea în formă sistematică

Întrucât codurile R-S sunt coduri ciclice, codarea în formă sistematică este analoagă cu procedura de codare binară. Se vor deplasa coeficienții polinomului m(X) corespunzător unui mesaj pe cele mai semnificative k poziții ale registrului cuvântului de cod iar apoi se vor atașa coeficienții polinomului de paritate p(X), plasându-le în cele mai puțin semnificative n – k poziții. Pentru aceasta, vom multiplica m(X) cu Xn-k, manipulând algebric polinomul corespunzător mesajului, astfel încât să poată fi deplasat la dreapta cu n – k poziții. În continuare, împărțim Xn-k m(X) la polinomul generator g(X), obținând o relație de forma:

Xn-k m(X) = q(X) g(X) + p(X) (23)

unde q(X) și p(X) sunt polinoamele cât și rest. Ca și în cazul binar, polinomul rest este polinom de paritate. Ecuația (23) poate fi exprimată și astfel:

p(X) = Xn-k m(X) modulo g(X) (24)

Polinomul rezultant pentru cuvântul de cod, U(X) este:

U(X) = p(X) + Xn-k m(X) (25)

Vom demonstra pașii implicați de ecuațiile (24) și (25), codând următorul mesaj alcătuit din 3 simboluri:

010 110 111

sau

α1 α3 α5

cu un cod R-S (7, 3) al cărui polinom generator este dat în ecuația (22). Mai întâi, vom multiplica polinomul corespunzător mesajului α1 + α3 X + α5X2 cu Xn-k = X4 , conducând la α1 X4 + α3X5 + α5X6 . În continuare vom împărți polinomul rezultat la polinomul generator din ecuația (22), α3 + α1 X + α0X2 + α3 X3 + X4. După efectuarea calculelor în câmp Galois, rezultă următorul polinom rest:

p(X) = α0 + α2 X + α4X2 + α6 X3

Apoi, din ecuația (25), polinomul pentru cuvântul de cod poate fi scris după cum urmează:

U(X) = α0 + α2 X + α4X2 + α6 X3 + α1X4 + α3X5 + α5X6 (26)

1.9 Codarea sistematică cu un registru de deplasare cu (n – k) stări

Folosirea circuitelor pentru a coda o secvență de 3 simboluri în formă sistematică cu un cod R-S (7, 3) descris de g(X) dat în ecuația (22) presupune implementarea unui registru liniar de deplasare cu reacție cum este cel din figura 9. Se poate verifica ușor că termenii de multiplicare din figura 9, luați de la stânga la dreapta, corespund coeficienților polinomului din ecuația (22) (în ordine crescătoare). Procesul de codare este echivalentul nonbinar al codării ciclice. În cazul de față, corespunzător ecuației (20), cuvintele de cod R-S (7, 3) nenule sunt alcătuite din 2m – 1 = 7 simboluri, iar fiecare simbol este format din m = 3 biți.

Figura 9: codor Reed – Solomon (7, 3)

Exemplul considerat fiind nonbinar, fiecare stare a registrului de deplasare memorează un simbol pe 3 biți. În cazul codurilor binare, coeficienții etichetați g1, g2 ș.a.m.d., sunt binari. Totuși, în figura 9, întrucât fiecare coeficient este specificat pe 3 biți, poate lua una din 8 valori posibile.

Operația nonbinară implementată de codorul din figura 9 alcătuiește cuvinte de cod într-o formă sistematică, procedând în același mod ca în cazul binar. Pașii pot fi descriși astfel:

Comutatorul 1 este închis pe durata primilor k cicli de ceas pentru a permite deplasarea simbolurilor din mesaj în registrul de deplasare cu (n – k) stări.

Comutatorul 2 este conectat la intrare pe durata primilor k cicli de ceas, pentru a permite transferul simultan al simbolurilor din mesaj direct către un registru de ieșire (neilustrat în figură).

După transferul celor k simboluri din mesaj către registrul de ieșire, comutatorul 1 este deschis, iar comutatorul 2 își schimbă poziția.

În restul de (n – k) cicli de ceas rămași, simbolurile de paritate conținute de registrul de deplasare sunt transferate, câte unul, la registrul de ieșire.

Numărul total de cicli de ceas este egal cu n, și conținutul registrului de ieșire este polinomul cuvântului de cod p(X) + Xn-k m(X), unde p(X) reprezintă polinomul de paritate, iar m(X) este polinomul mesajului de intrare.

Folosim aceeași secvență de simboluri care a fost aleasă ca mesaj de test mai devreme:

010 110 111

sau

α1 α3 α5

unde simbolul cel mai din dreapta este primul simbol. Pașii operaționali pe durata celor k = 3 deplasări ale circuitului de codare din figura 9, sunt:

După al treilea ciclu de ceas, registrul conține simbolurile de paritate α0 , α2 , α4 , și α6 . Apoi, comutatorul 1 este deschis, comutatorul 2 este conectat la registru, iar simbolurile de paritate conținute de acesta sunt deplasate către ieșire. Astfel, cuvântul de ieșire, U(X), scris în formă polinomială, se exprimă astfel:

U(X) =

U(X) = α0 + α2 X + α4 X2 + α6 X3 + α1 X4 + α3 X5 + α5 X6

= (1 0 0) + (0 0 1)X + (0 1 1)X2 + (1 0 1)X3 + (0 1 0)X4 + (1 1 0)X5 + (1 1 1)X6 (26)

Rădăcinile polinomului generator, g(X), trebuie să fie de asemenea și rădăcinile

cuvântului de cod generat de g(X), deoarece un cuvânt de cod valid are forma:

U(X) = m(X) g(X) (27)

De aceea, atunci când este evaluat un cuvânt de cod arbitrar pentru orice rădăcină a lui g(X), rezultatul trebuie să fie zero. Vom verifica în continuare că polinomul cuvântului de cod verifică această condiție.

U(α) = α0 + α3 + α6 + α9 + α5 + α8 + α11

= α0 + α3 + α6 + α2 + α5 + α1 + α4

= α1 + α0 + α6 + α4

= α3 + α3 = 0

U(α2) = α0 + α4 + α8 + α12 + α9 + α13 + α17

= α0 + α4 + α1 + α5 + α2 + α6 + α3

= α5 + α6 + α0 + α3

= α1 + α1 = 0

U(α3) = α0 + α5 + α10 + α15 + α13 + α18 + α23

= α0 + α5 + α3 + α1 + α6 + α4 + α2

= α4 + α0 + α3 + α2

= α5 + α5 = 0

U(α4) = α0 + α6 + α12 + α18 + α17 + α23 + α29

= α0 + α6 + α5 + α4 + α3 + α2 + α1

= α2 + α0 + α5 + α1

= α6 + α6 = 0

1.10 Decodarea Reed-Solomon

Mesajul codat sistematic anterior folosind codul R-S (7, 3) a devenit cuvânt de cod, caracterizat de polinomul din relația (26). Vom presupune că în timpul transmisiei acest cuvânt de cod devine corupt, încât 2 simboluri sunt recepționate eronat (numărul de erori corespunde capacității maxime de corectarea a codului R-S (7, 3)). Pentru acest cuvânt de cod de 7 simboluri, vectorul eroare, e(X), poate fi descris în formă polinomială astfel:

e(X) = (28)

Pentru acest exemplu, să presupunem cele două erori distribuite astfel:

e(X) = 0 + 0 X + 0 X2 + α2 X3 + α5 X4 + 0 X5 + 0 X6 (29)

= (0 0 0) + (0 0 0) X + (0 0 0) X2 + (0 0 1) X3 + (1 1 1) X4 + (0 0 0) X5 +

= + (0 0 0) X6

Cu alte cuvinte, un simbol de paritate a fost corupt cu o eroare de un bit, iar un simbol de date a fost corupt cu 3 biți de eroare. Cuvântul de cod corupt recepționat, r(X) este reprezentat de suma dintre polinomul cuvântului de cod transmis și polinomul eroare, după cum urmează:

r(X) = U(X) + e(X) (30)

Aplicând ecuația (30), vom aduna U(X) din ecuația (26) la e(X) din ecuația (29)

și va rezulta r(X) astfel:

r(X) = (1 0 0) + (0 0 1) X + (0 1 1) X2 + (1 0 0) X3 + (1 0 1) X4 + (1 1 0) X5 +

+ (1 1 1) X6

= α0 + α2 X + α4 X2 + α0 X3 + α6 X4 + α3 X5 + α5 X6 (31)

În acest exemplu sunt patru necunoscute – două locații de eroare și două valori de eroare. O diferență importantă între decodarea nonbinară și decodarea binară este că în decodarea binară, decodorul are nevoie să găsească doar locațiile de eroare. Informația că există o eroare la o anumită locație dictează faptul că bitul trebuie schimbat din “0” în “1” sau vice versa. Dar aici, simbolurile nonbinare cer cunoașterea nu doar a locațiilor de eroare dar și determinarea valorilor corecte pentru simbolurile de pe locațiile respective. Deoarece există patru necunoscute în acest exemplu, patru ecuații vor fi necesare în rezolvarea lor.

1.11 Calculul sindroamelor

Sindromul este rezultatul unei verificări de paritate realizată pentru cuvântul recepționat, r în scopul de a determina dacă este un membru valid a setului cuvintelor de cod. Dacă într-adevăr r este membru valid, sindromul S are valoarea 0. Orice valoare diferită de 0 a sindromului S indică prezența erorilor. Asemenea cazului binar, sindromul S conține n – k simboluri, {Si} (i = 1,…,n – k). Deci, pentru acest cod R-S (7, 3), există patru simboluri în fiecare vector sindrom; valorile lor pot fi calculate din polinomul cuvântului recepționat, r(X). Calculul este facilitat de structura codului dată de ecuația (27) rescrisă mai jos:

U(X) = m(X) g(X)

Din această structură se poate vedea că polinomul pentru orice cuvânt de cod valid U(X) este multiplu de polinomul generator g(X). De aceea, rădăcinile lui g(X) trebuie să fie și rădăcinile lui U(X). Întrucât r(X) = U(X) + e(X), înseamnă că r(X) evaluat pentru fiecare din rădăcinile lui g(X) ar trebui să dea rezultatul 0 atunci când este un cuvânt de cod valid. Orice erori vor determina ca unul sau mai multe rezultate să fie diferite de 0. Calculul unui simbol de sindrom poate fi descris după cum urmează:

Si = r(X) (X = αi )= r (αi) i = 1, …, n – k (32)

unde r(X) conține cele două erori de simbol postulate după cum arată ecuația (29). Dacă r(X) este un cuvânt de cod valid ar determina simbolurile din sindrom nule. Pentru acest exemplu, cele patru simboluri de sindrom sunt:

S1 = r(α) = α0 + α3 + α6 + α3 + α10 + α8 + α11 =

= α0 + α3 + α6 + α3 + α2 + α1 + α4 =

= α3 (33)

S2 = r(α2) = α0 + α4 + α8 + α6 + α14 + α13 + α17 =

= α0 + α4 + α1 + α6 + α0 + α6 + α3 =

= α5 (34)

S3 = r(α3) = α0 + α5 + α10 + α9 + α18 + α18 + α23 =

= α0 + α5 + α3 + α2 + α4 + α4 + α2 =

= α6 (35)

S4 = r(α4) = α0 + α6 + α12 + α12 + α22 + α23 + α29 =

= α0 + α6 + α5 + α5 + α1 + α2 + α1 =

= 0 (36)

Rezultatele confirmă că acest cuvânt recepționat conține erori deoarece S 0.

O a doua verificare a valorilor sindromului

Pentru exemplul de cod R-S (7, 3) considerat, se cunoaște vectorul eroare, întrucât a fost ales de la început. O proprietate importantă a codului este că vectorul eroare are același sindrom cu vectorul – cuvânt recepționat, fapt verificat în continuare, evaluând polinomul eroare pentru rădăcinile polinomului g(X).

Si = r(X) (X = αi ) = r (αi) i = 1, …, n – k

Si = [U(X) + e(X)] (X = αi ) = U(αi) + e(αi)

Si = r (αi) = U(αi) + e(αi) = 0 + e(αi)

Din ecuația (29),

e(X) = α2 X3 + α5 X4

De aceea,

S1 = e(α1) = α5 + α9

= α5 + α2

= α3

S2 = e(α2) = α8 + α13

= α1 + α6

= α5

S3 = e(α3) = α11 + α17

= α4 + α3

= α6

S4 = e(α4) = α14 + α21

= α0 + α0

= 0

Aceste rezultate confirmă că valorile sindromului sunt aceleași indiferent dacă sunt obținute din evaluarea lui e(X) pentru rădăcinile lui g(X) , sau din evaluarea lui r(X) pentru rădăcinile lui g(X).

Vom defini numărul de localizare a erorii,

βl = α,unde l = 1, 2, 3, …. , v (v = numărul total de erori)

Ținând cont de ecuația (28), vom rescrie cele 2t sindroame înlocuind numărul de localizare a erorii în vectorul – eroare:

S1 = e β1 + e β2 + … + eβv

S2 = e β12 + e β22 + … + eβv2 (37)

…….

S2t = e β12t + e β22t + … + eβv2t

În sistemul de ecuații (37) există 2t necunoscute (t valori de erori și t locații). Aceste 2t ecuații simultane nu pot fi rezolvate într-un mod obișnuit deoarece sunt neliniare (o parte din necunoscute au exponenți). Orice tehnică care rezolvă acest sistem de ecuații este denumită algoritm de decodare Reed – Solomon, rezolvarea acestui sistem constituind cea mai intensă operație din punctul de vedere al calculului în decodarea Reed – Solomon. Cei mai frecvent folosiți algoritmi de decodare sunt:

Algoritmul Berlekamp – Massey : este o metodă de calcul eficientă din punctul de vedere al numărului de operații în câmp Galois.

Algoritmul Euclidian : este metodă mai puțin eficientă, dar tinde să fie folosită mai des în practică deoarece este mai ușor de implementat

Reamintim că toate operațiile implicate în sistemul (36) sunt efectuate în câmp Galois GF(2m).

1.12 Algoritmul Berlekamp – Massey

Dacă s-au recepționat erori, în primul rând trebuie determinate locațiile erorilor. Ecuațiile sindroamele (37) pot fi traduse într-o serie de ecuații liniare, definind astfel polinomul de localizare a erorii:

σ (X) = (1 + β1X) (1 + β2X) ….(1 + βvX) =

= 1 + σ1X + σ2X2 + ….+ σvXv (38)

Rădăcinile lui σ (X) sunt 1/β1, 1/β2, …. , 1/βv. Inversele acestor rădăcini sunt numerele de localizare a erorilor din vectorul – eroare e(X). σ (X) este un polinom necunoscut ai cărui coeficienți trebuie determinați. Algoritmul Berlekamp – Massey constă practic în găsirea coeficienților polinomului de localizare a erorii.

Coeficienții lui σ (X) și numerele de localizare e erorilor sunt legate prin următoarele ecuații:

σ 0 = 1

σ 1 = β1 + β2 + … + βv

σ 2 = β1 β2 + β2 β3 + …. + βv-1 βv (39)

……

σ v = β1 β2 … βv

Acest set de ecuații este cunoscut sub denumirea de funcții simetrice elementare și are legătură cu sistemul de ecuații (37), unde valorile erorilor sunt presupuse a avea magnitudine unitară pentru a păstra ecuațiile simplu de înțeles. Legătura cu sindroamele este:

S1 + σ 1 = 0

S2 + S1 σ 1 = 0

S3 + S2σ 1 + S1σ 2 + σ 3 = 0 (40)

……

Sv+1 + Svσ 1 + … + S2σ v-1 + S1σ v = 0

Aceste ecuații sunt denumite identitățile lui Newton. Algoritmul Berlekamp – Massey este o modalitate iterativă de a determina polinomul de grad minim care satisface identitățile lui Newton. Polinomul de grad minim Φi(X) al unui element αi din GF(2m) este polinomul cu gradul cel mai mic ce are αi ca rădăcină.

Algoritmul Berlekamp – Massey care nu folosește elementul invers la multiplicare presupune 2t iterații, în cadrul fiecărei iterații calculându-se următoarele variabile:

= (41)

L (42)

(X) = (43)

B (44)

(45)

pentru i = 1, 2, …, 2t.

Condițiile inițiale sunt:

B(0)(X) = 1 L0 = 0 ε(0) = 1

Dacă Δi 0 și 2 Li-1 i-1, atunci δ = 1, altfel, δ = 0.

Λ(2t)(X) = Λ(X) este polinomul de localizare a erorii.

1.13 Algoritmul Euclidian

Algoritmul euclidian este o metodă recursivă pentru a găsi Cel Mai Mare Divizor Comun dintre două polinoame sau doi întregi. Un divizor comun g > 0 pentru care fiecare divizor comun al lui a și b îl divide pe g este denumit cel mai mare divizor comun al lui a și b și este notat (a, b). Pentru polinoame, dacă fie a(X) sau b(X) este diferit de zero, divizorul comun g(X) astefl încât fiecare divizor comun al lui a(X) și b(X) să îl dividă pe g(X) se numește cel mai mare divizor comun (c.m.m.d.c) al lui a(X) și b(X) și este notat (a(X), b(X)).

Ideea principală a algoritmului euclidian este faptul că operează cu împărțiri repetate: începând cu două numere, a și b, se împarte a la b pentru a obține un rest. Apoi se împarte b la rest, pentru a obține un nou rest. Se continuă în acest mod, împățind ultimul divizor la cel mai recent rest, până când se obține restul zero. Apoi ultimul rest diferit de zero este cel mai mare divizor comun (a, b).

Algoritmul euclidian pentru decodarea codurilor Reed – Solomon este stabilit cu ajutorul următoarei teoreme: Dacă g = (a, b), atunci există întregi s și t astfel încât:

g = (a, b) = as + bt

Pentru polinoame, dacă g(X) = (a(X), b(X)), atunci există polinoame s(X) și t(X) astfel încât:

g(X) = (a(X), b(X)) = a(X)s(X) + b(X)t(X) (46)

Deci algoritmul euclidian pentru decodarea R-S calculează g(X) = (a(X), b(X)) și de asemenea s(X) și t(X), și este deseori denumit algoritmul euclidian extins.

Revenind la decodarea R-S, putem rescrie ecuația (46) astfel:

Λ(X) = X2t μ(X) + S(X) σ(X) (47)

unde Λ(X) este denumit polinomul de evaluare a erorii și joacă rolul lui g(X) din ecuația (46), X2t joacă rolul lui a(X), μ(X) este un polinom oarecare și joacă rolul lui s(X), polinomul sindrom, S(X) joacă rolul lui b(X), iar polinomul de localizare a erorii, σ(X), pe care vrem să-l determinăm, joacă rolul lui t(X).

Polinomul de evaluare a erorii poate fi scris:

Λ(X) = (S(X) σ(X)) modulo X2t (48)

Polinomul sindrom, S(X) are următoarea formă:

S(X) = S1 + S2 X + S3 X2 + … + S2t X2t-1 (49)

unde S1, S2, …., S2t sunt sindroamele calculate cu relația (32).

Ținând cont de echivalența dintre ecuațiile (46) și (47) , vom explica pașii algoritmului euclidian extins cu ajutorul notațiilor din relația (46).

Algoritmul implică divizări repetate ale polinoamelor până când se obține un polinom rest cu grad mai mic decât t. Pentru a realiza aceste împărțiri, se folosește tehnica împărțirii clasice a polinoamelor.

Primul pas este să împărțim a(X) la b(X) pentru a obține câtul q1(X) și restul r1(X), astfel încât:

a(X) = q1(X) b(X) + r1(X) (50)

Dacă gradul lui r1(X) este mai mic decât t, atunci am găsit soluția cu s(X) = 1, t(X) = q1(X) și g(X) = r1(X). Altfel, se notează q1(X) = t1(X) și se trece la pasul următor.

Al doilea pas este împărțirea lui b(X) la r1(X):

b(X) = q2(X) r1(X) + r2(X) (51)

Gradul lui r2(X) trebuie să fie mai mic decât al lui r1(X),astfel încât acest proces să reducă gradul polinomului rest. Dacă eliminăm r1(X) din ecuațiile (50) și (51), obținem:

q2(X) a(X) = [q1(X) t1(X) + 1] b(X) + r2(X) (52)

Notăm t2(X) = q1(X) t1(X) + 1. Dacă gradul lui r2(X) este mai mic decât t, atunci t(X) = t2(X) , altfel, procedura continuă.

Al treilea pas constă în împărțirea lui r1(X) la r2(X)

r1(X) = q2(X) r2(X) + r3(X)

În continuare, gradul restului trebuie să scadă. Folosim ecuațiile (51) și (52) pentru a elimina r1(X) și r2(X):

[1 + q2(X) q3(X) ] a(X) = [t1(X) + q3(X) t2(X)] b(X) + r3(X)

Dacă gradul lui r3(X) este mai mic decât t, atunci t(X) = t3(X) = t1(X) + q3(X) t2(X).

Metoda continuă în acest mod până când un rest de grad mai mic decât t este găsit, la fiecare pas i = 1, 2,…, făcând notația

ti(X) = ti-2(X) + qi(X) ti-1(X) cu { t0(X) = 1, t-1(X) = 0} (53)

Astfel ultimul ti(X) calculat corespunde polinomului de localizare a erorii σ(X) din relația (47). Rădăcinile polinomului pot fi obținute cu algoritmul Chien Search descris în continuare.

1.14 Algoritmul Chien Search

Următorul pas în decodarea R-S este găsirea rădăcinilor polinomului de localizare a erorii σ(X) determinat, rădăcini care reprezintă inversele numerelor de localizare a erorilor. Întrucât rădăcinile trebuie să fie elemente ale câmpului GF(2m), o căutare exhaustivă, înlocuind fiecare din elementele câmpului finit în polinomul de localizare a erorii σ(X) și verificând condiția σ(αi) = 0 este singura soluție posibilă. Chien Search este un algoritm pentru a realiza această căutare într-o manieră eficientă.

Să presupunem, de exemplu, că v = 3 și că polinomul de localizare a erorii este:

σ(X) = 1 + σ 1 X + σ 2 X2 + σ 3 X3

Evaluăm σ(X) pentru fiecare element diferit de zero din GF(2m) în ordinea:

X = 1, X = α, X = α2, X = α3, ….. , X = α

Astfel ajungem la următoarele relații:

σ(1) = 1 + σ 1 1 + σ 2 12 + σ 3 13

σ(α) = 1 + σ 1 α + σ 2 α 2 + σ 3 α 3

σ(α2) = 1 + σ 1 (α2) + σ 2 (α2) 2 + σ 3 (α2) 3

……

σ(α) = 1 + σ 1 (α) + σ 2 (α) 2 + σ 3 (α) 3

Dacă în substituțiile de mai sus, obținem σ(αi) = 0, atunci exponentul inversei rădăcinii αi este egal cu indexul de localizare a erorii, i.

1.15 Algoritmul Forney

După găsirea polinomului de localizare a erorii și a rădăcinilor sale, mai există un pas în decodarea R-S: determinarea valorilor erorilor. În general, acest lucru se face folosind algoritmul Forney, în care valoarea erorii de la locația βl = α(1 ) pentru codul R-S, este calculată astfel:

e= (54)

unde Λ(X) este polinomul de evaluare a erorii, descris de ecuația (48), iar σ’(X) este derivata în funcție de X a polinomului de localizare a erorii. Derivata oricărui polinom în câmp finit se calculeaza anulând puterile pare și scăzând cu o unitate puterile impare. Astfel se pot ușor calcula valorile erorilor.

Având determinate locațiile și valorile erorilor, putem forma polinomul eroare, e(X) și corecta polinomul recepționat r(X) adunând (prin operația XOR) aceste două polinoame.

2.Aplicații ale codurilor Reed – Solomon

2.1.1 Întrețeserea

Corecția erorilor depinde de abilitatea algoritmului de a folosi eficient datele redundante pentru a reconstrui datele invalide. Când eroarea este prelungită, cum este cazul erorilor de tip burst, cantintăți mari de date informaționale continui, precum și date redundante se pot pierde, iar corecția poate fi dificilă sau imposibilă. Pentru a preveni asta, datele informaționale sunt întrețesute sau dispersate în fluxul de date înaintea stocării sau transmisiei. Dacă are loc o eroare de tip burst, va afecta o secțiune contiguă de date. Totuși, în cadrul redării, fluxul de date este de-întrețesut; deci, datele sunt retransformate în secvența inițială și erorile distribuite în flux. Având acum date valide și redundante printre date afectate, algoritmul poate mai ușor să reconstruiască datele eronate. Figura 10 ilustrează un exemplu de întrețesere și deîntrețesere, cu o eroare de tip burst apărând în cadrul transmisiei sau stocării. După deîntrețesere, erorile au fost dispersate, fiind facilitată corectarea acestora.

Întrețeserea prezintă un avantaj important. Fără întrețesere, cantitatea de date redundante ar fi dictată de mărimea celei mai mari erori de tip burst corectabile. Cu întrețesere, cea mai mare eroare care poate apărea într-un bloc este limitată la mărimea secțiunilor întrețesute. Deci cantitatea de date redundante este determinată nu de mărimea burst-ului, ci de mărimea secțiunii întrețesute. Întrețeserea dispersează eficient datele. De multe ori, suma de verificare a erorilor (checksum) are un rezultat bun dacă există doar o singură eroare de cuvânt într-un bloc. O eroare de tip burst depășește acestă limitare; totui, datele întrețesute și deîntrețesute pot conduce la doar un singur cuvânt eronat într-un bloc dat. Deci întrețeserea crește simțitor capacitatea de corecție a erorilor de tip burst a codurilor bloc. Întrețeserea la nivel de bit atinge aproximativ acelai scop ca și întrețeserea la nivel de bloc; permite controlul erorilor de tip burst scurte sau a erorilor aleatoare.orice proces de întrețesere presupune un buffer destul de mare pentru a menține datele distribuite atât în timpul întrețeserii cât și a deîntrețeserii.

Figura 10: intarzieri de 0, 1, 2 și 3 cuvinte realizeaza întrețeserea și deîntrețeserea pentru dispersarea erorilor, înainte de corecție

2.1.2 Întrețeserea încrucișată

Întrețeserea poate fi neadecvată când erorile de tip burst sunt însoțite de erori aleatoare. Deși burst-ul este dispersat, erorile aleatoare adaugă erori adiționale într-un cuvânt dat, supraîncăcând uneori algoritmul de corectare. O soluție este generarea a 2 coduri de corectare, separate de întrețesere și întârziere. Când codurile de tip bloc sunt aranjate în linii și coloane bidimensional, codul este denumit cod produs (sau cuvânt de cod încrucișat); un cod produs este folosit pentru DVD-uri. Distanța minimă este produsul distanțelor fiecărui cod. Când două coduri bloc sunt separate atât de întrețesere cât și de întârziere, rezultă întrețeserea încrucișată. Cu alte cuvinte, un cod întrețesut încrucișat (CIC) comprimă două (sau mai multe) coduri bloc asamblate cu o structură convoluțională precum cea din figura 11. Metoda este eficientă deoarece sindroamele dintr-un cod pot fi folosite pentru a marca erori care vor fi corectate de celălalt cod. Întrucât locația erorii se cunoaște, capacitatea de corecție este sporită. De exemplu, o eroare aleatoare este corectată de codul întrețesut, iar o eroare de burst este corectată după deîntrețesere. Când ambele coduri sunt corectoare de o singură locație de eroare, codul rezultant este un cod întrețesut încrucișat. În formatul Compact Disc, sunt folosite codurile Reed-Solomon și algoritmul este denumit cod Reed-Solomon Întrețesut Încrucișat.

Un exemplu de codor CIC simplu este ilustrat în figura 12. Unitățile de întârziere produc întrețeserea iar sumatoarle modulo-2 generează coduri corectoare de o singură locație de eroare. Sunt generate 2 cuvinte de paritate (P și Q) iar erorile sunt eficient corectate. Pot fi corectate erori din cadrul a trei cuvinte de cod; 4 cuvinte eronate produc două cuvinte eronate în toate cele patru secvențe generate și corecția este imposibilă. CIC se bucură de performanța ridicată a unui cod convoluțional dar fără propagarea erorii, deoarece orice eroare corectabilă dintr-o secvență întotdeauna se transformă într-un cuvânt eronat în următoarea secvență și poate fi astfel corectată.

Figura 11: codor întrețesut încrucișat. Sindroamele din primul bloc sunt folosite ca markeri de eroare în al doilea bloc. În formatul CD, k2=24, n2=28, k1=28 și n1=32; codurile C1 și C2 sunt coduri Reed-Solomon

Figura 12: un exemplu de codor CIC și secvența sa de ieșire

2.1.3 Coduri Reed – Solomon întrețesute încrucișate

Codul Reed- Solomon Întrețesut(CRSI) este un cod corector de 4 locații de erori sau 2 erori folosit în formatul Compact Disc. CRSI aplică codurile Reed – Solomon în mod secvențial, cu un proces de întrețesere între codarea C2 și C1. Codarea trece datele prin codorul C2, apoi prin codorul C1. Decodarea inversează procesul.

C2 este un cod (28, 24), deci codorul preia 24 de simboluri și furnizează la ieșire 28 de simboluri, dintre care 4 sunt de paritate. C1 este un cod (32, 28); codorul primește la intrare 28 de simboluri și frunizează 32 la ieșire. În ambele cazuri, deoarece sunt folosiți bytes (pe 8 biți), mărimea câmpului Galois este GF(28); calculele sunt bazate pe polinomul primitiv: X8 + X4 + X3 + X2 + 1. Distanța minimă este 5. Maxim 4 simboluri pot fi corectate dacă se cunosc locațiile erorilor, respectiv două, dacă nu se cunosc locațiile erorilor.

Folosind o combinație de întrețesere și paritate pentru a face datele mai robuste față de erorile întâlnite pe parcursul stocării, datele sunt codate înainte de afi plasate pe disc, și decodate apoi la redarea datelor. Algoritmul de codare CRSI este ilustrat în figura 13; similaritatea cu structura generală din figura 11 este evidentă. Folosind acest algoritm de codare, simbolurile din semnalul audio sunt întrețesute încrucișat, iar stările de codare R-S generează P și Q simboluri de paritate.

Codorul CRSI acceptă 24 de simboluri pe 8 biți, adică 12 simboluri de la canalul din stânga și 12 de la canalul din dreapta. În mod interesant, valoarea 12 afost selectată de proiectanți deoarece are ca multiplicatori comuni valorile 2, 3 și 4; acest lucru ar fi permis CD-ului să ofere mai ușor implementări și pe 3 sau 4 canale – potențial care nu a ajuns niciodată să fie fructificat. Un stadiu de întrețesere asistă interpolarea. O întârziere de două simboluri este plasată între eșantioanele pare și impare. Deoarece eșantioanele pare sunt întârziate cu 2 blocuri, interpolarea este posibilă acolo unde apar două blocuri necorectabile. Simbolurile sunt dispersate pentru a separa simborile de ordin par și impar; acest proces asistă ascunderea datelor. Cuvântul de 24 de bytes în paralel este intrarea în codorul C2 care produce patru simboluri de paritate Q. Paritatea Q este proiectată să corecteze un simbol eronat, sau până la patru locații de eroare dintr-un cuvânt. Plasând simbolurile de paritate în centrul blocului, distanța pară/impară este mărită. Acest lucru permite interpolarea în cadrul celei mai mari erori de tip burst posibile.

Figura 13: codorul CRSI

În stadiul de întrețesere încrucișată, 28 de simboluri sunt întârziate cu perioade diferite. Aceste perioade sunt multipli întregi de patru blocuri. Această întrețesere convoluțională stochează un cuvânt C2 în 28 de blocuri diferite, stocate pe o distanță de 109 blocuri. În acest mod, vectorul de date este încrucișat. Întrucât întârzierile sunt lungi și de durată inegală, este facilitată corecția erorilor de tip burst. 28 de simboluri (din 28 de cuvinte C2 diferite) sunt intrarea în codorul C1 care produce cele patru simboluri de paritate P. Paritatea P este proiectată să corecteze erorile de un simbol și să detecteze și marcheze erorile duble și triple pentru corecția de tip Q.

Un stadiu de întrețesere întârzie simbolurile alternate cu un simbol. Această întârziere impară/pară împrăștie simbolurile de ieșire în cadrul a două blocuri de date. În acest fel, erorile aleatoare nu pot corupe mai mult de un simbol într-un cuvânt chiar dacă există două simboluri eronate adiacente într-un bloc. Simbolurile de paritate P și Q sunt inversate pentru a furniza simboluri P și Q nenule cu date nule. Treizeci și două de simboluri de câte 8 biți sunt furnizate de codorul CRSI.

Eroarea procesată trebuie decodată de fiecare dată când se redă conținutul discului pentru a fi deîntrețesute datele, și pentru a realiza detecția și corecția erorilor. Atunci când un decodor Reed-Solomon primește un bloc de date (constând în simbolurile de date inițiale și simbolurile de paritate), folosește datele recepționate pentru a recalcula simbolurile de paritate. Dacă simbolurile de paritate recalculate coincid cu cele recepționate, blocul recepționat se consideră a fi fără erori. Dacă diferă, sindroamele diferență sunt folosite pentru a localiza eroarea. Cuvintele eronate sunt marcate, de exemplu, ca fiind corectabile, necorectabile sau posibil corectabile. Analiza marker-ilor determină dacă erorile vor fi corectate de către cod de corecție sau dacă vor interpolate. Algoritmul de decodare CRSI este ilustrat în figura 14.

Un cadru de treizeci și două de simboluri de 8 biți sunt introduse la intrarea decodorului CRSI: douăzeci și patru de simboluri sunt audio, iar opt sunt de paritate. Simbolurile de ordin impar sunt întârziate cu un simbol. În acest mod, simbolurile de ordin par dintr-un cadru sunt deîntrețesute cu simbolurile de ordin impar în cadrul următor. Simbolurile audio sunt readuse la ordinea lor inițială iar erorile de disc sunt împrăștiate. Acest lucru este în beneficiul corecției C1, mai ales pentru erorile mici, la învecinarea simbolurilor. După această deîntrețesere, simbolurile de paritate sunt inversate.

Folosind patru simboluri de paritate P, decodorul C1 corectează erorile aleatoare și detectează erorile de tip burst. Decodorul C1 poate corecta un simbol eronat dintr-un cadru. Dacă există mai mult de un simbol eronat, cele 28 de simboluri de date sunt marcate cu un marker de locație de eroare și trimise decodorului C2. Simbolurile valide sunt trimise fără a fi procesate. Deîntrețeserea convoluțională dintre decodoare permite decodorului C2 să corecteze erori de tip burst lungi. Cadrul de intrare în decodorul C2 conține simbolurile din decodorul C1 decodate la momente diferite de timp; totuși simbolurile marcate cu marker de locație de eroare sunt împrăștiate. Astfel este asistat decodorul C2 în corectarea erorilor de tip burst. Simbolurile fără marker sunt presupuse a fi corecte și nu sunt procesate.

Primind date precodate și ajutor de la deîntrețesere, C2 poate corecta erorile de tip burst precum și erorile aleatoare pe care 1 nu le-a putut corecta. Folosind patru simboluri de paritate Q, C2 poate detecta și corecta erori de un simbol și corecta până la patru simboluri, precum și orice simboluri corectate greșit de către C1. C2 poate de asemenea corecta erori care pot apărea în procesul de codare. Când C2 nu poate realiza corecția, de exemplu, când mai mult de patru simboluri sunt marcate, cele 24 de simboluri de date sunt marcate interpolate. Dealeatorizarea finală și întârzierea completează decodarea CRSI.

Figura 14: decodorul CRSI

Succesul corecției de erori CRSI depinde în ultimă instanță de implementarea algoritmului. În general, CRSI ar putea asigura corecția a până la 3874 de biți, corespunzător unui defect de lungime de pistă de 2.5 mm. O bună ascundere se poate extinde la 13.282 biți corespunzător unui defect de 8.7 mm și o ascundere periferică se poate extinde la aproximativ 15.500 biți.

Integritatea datelor stocate pe un CD și trecerea printr-un algoritm CRSI poate fi evaluată printr-un număr de contorizări de erori. Folosind o nomenclatură pe doi digiți, primul digit specifică numărul de bytes (simboluri) eronați iar al doilea digit specifică la care decodor au loc (C2 sau C1). Contorizările de trei erori (E11, E21 și E31) sunt măsurate la ieșirea decodorului C1. Contorul E11 specifică frecvența apariției erorilor de un singur simbol (corectabile) pe secundă la decodorul C1. E21 indică frecvența apariției erorilor duble de simbol (corectabile) în decodorul C1. E31 indică frecvența apariției erorilor triple de simbol (corectabile) în decodorul C1. Erorile E11 și E21 sunt corectate în stadiul C1. Erorile E31 nu sunt corectate în stadiul C1, fiind trimise mai departe către stadiul de decodare C2.

Există trei contoare de eroare (E12, E22 și E32) și la decodorul C2. Contorul E12 indică frecvența apariției erorilor de un simbol (corectabile) pe secundă la decodorul C2. O valoare ridicată indicată de E12 nu este problematică deoarece o eroare E31 poate genera până la 30 de erori E12 din cauza întrețeserii. Contorul E22 indică frecvența apariției erorilor de simbol duble în decodorul C2. Erorile E22 sunt cele mai dificil de corectat erori. Contorul E22 indică faptul că sistemul este aproape de a produce o eroare necorectabilă. Un CD-ROM cu 15 erori E22 ar fi inacceptabil chiar dacă erorile sunt corectabile. O valoare mare contorizată de E22 poate indica deteriorări localizate pe disc, provenind dintr-un defect de manufacturare sau din utilizare necorespunzătoare. Contorul E32 indică trei sau mai multe erori (necorectabile) în decodorul C2, sau date care nu pot fi citite, în general. În mod ideal contorul E32 nu ar trebui sa indice o valoare diferită de zero niciodată. Erorile E32 sunt uneori clasificate ca erori de interpolare de zgomot; când au loc erori E32, trebuie realizată interpolarea. Dacă un disc nu conține erori E32, datele conținute sunt redate cu acuratețe.

Rata de eroare de bloc (BER) măsoară numărul de cadre de date care contin cel puțin un caz de simboluri necorectabile la intrarea decodorului C1 (E11, E21 și E31); este deci o măsură atât a erorilor corectabile cât și necorectabile în stadiul de decodare. Erorile care sunt necorectabile în acest stadiu sunt transmise următorului stadiu de decodare. Rata de eroare de bloc este o măsură generală bună a calității datelor de pe disc. BER este spacificată ca rata de erori pe secundă. CD-ul standard fixează un maxim de 220 de erori BER pe secundă mediată pe durata a 10 secunde pentru discurile audio; oricum, un disc bine fabricat va avea un BER mediu mai mic de 10. Un BER ridicat indică deseori o geometrie de pistă săracă care perturbă abilitatea pick-up-ului de a citi datele, rezultând astfel numeroase erori de bit aleatoare. O valoare de BER mare ar putea de asemenea limita durata de viață a CD-ului, pe măsură ce alte zgârâieturi se acumulează crescând numărul total de erori contorizat. Totodată o valoare mare a BER poate determina o redare nereușită a fișierului audio de către unele playere. Rata de bloc pentru CD este de 7350 de blocuri pe secundă; deci, valoarea BER maximă de 220 de contorizări pe secundă indică faptul că 3% dintre cadre conțin un defect. Astfel se definește eroarea limită acceptabilă; o valoare mai mare ar putea conduce la defecte audibile. BER nu furnizează informații despre defecte individuale cuprinse între 100 și 300 μm, deoarece BER pune în corespondență defectele cu mărimea unei piste. BER este adesea cunoscută ca valoarea de o secundă sau ca media de 10 secunde pe disc, precum și ca BER maxim găsită pe durata unui interval de test de 10 secunde.

Semnalele E21 și E22 pot fi combinate pentru a forma un contor de erori de burst(CEB). Acesta contorizează numărul de erori bloc consecutive care depășește un număr limită stabilit. Indică în general un defect fizic mare pe disc, cum ar fi o zgârâietură, care afectează mai mult de un bloc de date. De exemplu, dacă sunt mai mult de 14 erori bloc consecutive iar pragul este menținut la 7 erori bloc, două erori CEB ar fi indicate. Acest contor este deseori catalogat ca număr total pentru un întreg disc. O specificație de control a calității bună nu ar permite apariția erorilor de tip burst (șapte cadre). În practică, CD recent fabricat ar putea avea BER = 5, E11 = 5, E21 = 0 și E31 = 0. Erorile necorectabile E32 nu ar trebui să apară deloc pe un CD nou. Figura 15 ilustrează un exemplu de contorizări de erori măsurate pe un Compact Disc având calitate bună de redare a datelor. Contorizările de eroare sunt măsurate vertical, pe durata a 50 de minute pe disc. După cum s-a menționat mai sus, numărul mare a erorilor E12 nu este problematic. După corecția CRSI a erorilor, discul nu mai are erori în datele de ieșire.

Există multe tipuri de corecție a erorilor pentru multe tipuri de aplicații. Proiectanții trebuie să analizeze corectabilitatea erorilor aleatoare și de tip burst, redundanța, probabilitatea de detecție greșită și lungimile maxime a erorilor de tip burst care pot fi corectate sau acoperite, precum și costul codorului și decodorului. Pentru date audio digitale, erorile care nu pot corectate, sunt acoperite. Totuși, o eroare detectată greșit nu poate fi adeseori acoperită, iar acest lucru poate cauza un defect audibil în ieșirea de date audio. Proiectanții care se ocupă de corecția erorilor trebuie să se asigure că acest lucru nu se întâmplă în cele mai rele condiții normale. Criteriile proiectanților sunt deseori fixate de aplicația particulară; de exemplu, banda digitală este susceptibilă la erori de tip burst cauzate de de amprentele degetelor deoarece substratul transparent le plasează înafara focalizării pick-up-ului optic. Din cauza naturii variate a erorilor – unele predictibile, și unele, precum cele produse de recorder-e și player-e nealiniate, nepredictibile – sistemele de corecție a erorilor trebuie să folosească în ultimă instanță tehnici variate pentru a se projeja de ele. Întâzierea, întrețeserea, paritatea și întrețeserea încrucișată sunt toate folosite pentru a corecta cu succes majoritatea tipurilor de erori găsite în înregistrările audio digitale.

2.1.4 Coduri produs

CRSI este un exemplu de cod întrețesut încrucișat în care două coduri sunt separate de întrețesere convoluțională. În coduri produs bidimensionale, două coduri sunt separate serial de întrețesere bloc. Codul care se codează primul și se decodează ultimul este denumit codul C2 exterior. Codul care se codează al doilea și se decodează primul este denumit codul C1 interior. Codurile produs folosesc deci metoda încricișării a două coduri corectoare de erori. Dacă C2 este un cod bloc (n2, k2) și C1 este un cod bloc (n1, k1) atunci ele determină un cod produs (n1n2, k1k2) având k1k2 simboluri într-un vector. Codul C2 adaugă paritatea P liniilor bloc, iar codul C1 adaugă paritatea Q coloanelor bloc, după cum se vede în figura 16. Fiecare coloană este un cuvânt de cod C1. când se folosesc coduri bloc liniare, cuvintele linie inferioare sunt tot cuvinte de cod C2.

Figura 15: Exemple de contorizări de erori pe un CD de 50 de minute. A: contor de erori E11. B: contor de erori E21. C: contor de erori E31. D: contor de erori BER. E: contor de erori E12. F:contor de eroro E22. G: contro de erori E32 (0 erori)

Datele de verificare din colțul din dreapta jos (intersecția coloanei P cu linia Q) reprezintă o verificare a datelor de verificare și pot fi derivate fie dintr-o coloană sau dintr-o linie de verificare.

Figura 16: Diagrama bloc a unui cod produs ilustrând linia redundantă exterioară P și coloana redundantă interioară Q. O eroare de tip burst este marcată în decodorul C1 și corectată în decodorul C2

În timpul decodării, paritatea Q este folosită de decodorul C1 pentru a corecta erorile de bit aleatoare, iar erorile de tip burst sunt marcate și trimise prin deîntrețesere către decodorul C2. simbolurile sunt trimise prin deîntrețesere astfel încât erorile de tip burst din cuvintele de cod interioare să apară ca erori de un singur simbol în cuvinte de cod diferite. Paritatea P și markerii sunt folosiți de către decodorul C2 pentru a corecta erori din cuvintele interioare.

În multe aplicații audio, codurile corectoare Reed – Solomon sunt deseori utilizate în coduri produs. De exemplu, în DVD, atât codurile interne cât și externe sunt Reed – Solomon definite în câmpul Galois GF(28) și descris de polinomul primitiv x8 + x4 + x3 + x2 + 1. Codurile produs depășesc ca performanță codurile convoluționale în aplicațiile audio moderne; ele necesită mai multă memorie pentru implementare, dar acesta nu este un detriment serios. Codurile produs oferă o performanță bună în corecția erorilor în prezența erorilor aleatoare simultan cu cele de tip burst și sunt larg folosite în medii de înregistrare de mare densitate precum DAT sau DVD.

2.1.5 Acoperirea erorilor

După cum s-a menționat, o detecție de eroare și metodă de corecție teoretic perfecte ar putea fi inventată, în care toate erorile sunt complet înlocuite cu date redundante sau calculate cu acuratețe completă. Totuși, o asemenea schemă nu ar fi practică din cauza surplusului de date. O metodă de corecție a erorilor practică echlibrează aceste limitări cu probabilitatea apariției de erori necorectate, și permite erorilor severe să rămână necorectate. Însă, procesarea ulterioară – un sistem de acoperire a erorilor – compensează acele erori și le face neaudibile. Câteva tehnici de acoperire a erorilor, cum ar fi interpolarea și punerea pe mut, au fost inventate pentru a îndeplini acest deziderat.

În general, sunt două tipuri de erori necorectabile generate de agoritmii de corecție. Unele erori pot fi detectate fără ca algoritmul să le poată corecta. Alte erori nu sunt detectate sau sunt corectate greșit. Primul tip de erori, detectate dar necorectate, pot fi ușor acoperite cu metode de acoperire potrivite. Erorile nedetectate si cele corectate greșit nu pot fi acoperite de cele mai multe ori și ar putea determina un defect audibil la ieșirea audio. Aceste tipuri de erori, deseori cauzate de erori aleatoare și de tip burst simultane, trebuie minimizate. Deci, un sistem de corecție a erorilor tinde să reducă erorile nedetectate prin algoritmul de corecție a erorilor, iar apoi se bazează pe metodele de acoperire a erorilor pentru a rezolva erorile detectate dar necorectate.

2.1.6 Interpolarea

După deîntrețesere, majoritatea erorilor, chiar și erorile de tip burst sunt amestecate cu datele valide. Este deci rezonabilă folosirea tehnicilor în care datele valide sunt folosite pentru a calcula date noi pentru a înlocui datele necorectate sau cele lipsă. Această tehnică funcționează bine, dat fiind că erorile sunt suficient dispersate și că există o oarecare corelație între valorile datelor. Din fericire, datele digitale care comprimă o selecție muzicală pot trece de interpolare fără audibilitate adversă. Deși este neintuitiv, studiile au demonstrat că, în cadrul unor limite, durata unei erori nu afectează excesiv percepția erorii.

În cea mai simplă formă a sa, interpolarea reține valoarea eșnationului anterior și o repetă pentru a acoperi eșantionul lipsă sau necorectat. Aceasta se numește interpolare de ordine zero sau a valorii anterioare. În interpolarea de primă ordine, denumită uneori interpolare de ordine liniară, eșantionul eronat este înlocuit cu un eșantion derivat din valoarea medie a eșantioanelor anterior și ulterior. În multe sisteme audio digitale, se folosește o combinație între interpolarea de ordine zero și cea de primă ordine. Dacă există eșantioane de erori consecutive, cu tot cu întrețesere, atunci se folosește interpolarea valorii anterioare pentru a înlocui erorile consecutive, dar valoarea ultimul eșantion retinut este calculată din valoarea medie a eșantionului reținut și a celui ulterior. Dacă erorile sunt aleatoare, adică eșantioane valide înconjoară erorile, atunci se folosesc calcule de valori medii. Evident, orice calcule de interpolare trebuie realizate suficient de rapid pentru a menține rata de date. În figura 18 sunt prezentate rezultatele unui experiment în valori relative ale zgomotului de interpolare.

2.1.7 Reducerea Volumului Audio la Zero

Reducerea volumului audio la zero este un proces simplu de a egala cu zero valoarea cuvintelor lipsă sau necorectate. Se preferă liniștea față de sunetele imprevizibile care pot rezulta din decodarea datelor incorecte. Reducerea volumului la zero poate fi folosită în cazul erorilor necorectate care ar putea cauza un defect audibil la ieșire. Creșterea momentană în distorsiune cauzată de o reducere a volumului la zero de scurtă durată poate fi imperceptibilă, dar un zgomot ar fi audibil. De asemenea, în cazul unui volum mare de date deteriorate sau al unei funcționări greșite a CD Player-ului, se preferă această măsură pentru ieșire. Pentru a minimiza audibilitatea, algoritmii folosiți în acest sens atenuează gradat amplitudinea semnalului de ieșire înainte de a-l anula, după care refac amplitudinea ulterior. De exemplu, câștigul poate fi

Figura 18: Caracteristicile de zgomot pentru diferite metode de interpolare

ajustat multiplicând eșantioane succesive cu coeficienți de atenuare timp de câteva milisecunde. Bineînțeles, reducerea câștigului trebuie să înceapă înainte de eroarea în sine, pentru a da timp unei ușoare stingeri a semnalului. Acest lucru este ușor de îndeplinit întârziind toate eșantioanele audio pentru puțin timp și activând apoi markerul pentru mut. Anularea de foarte scurtă durată nu poate fi percepută de către urechea umană. Strategiile de acoperire se folosesc atunci când canalele audio sunt procesate independent, de exemplu, reducând la zero doar un canal din două.

Figura 17: Interpolarea este folosită pentru ascunderea erorilor

2.1.8 Duplicarea

Unul din beneficiile înregistrării audio digitale este posibilitatea de a copia înregistrările fără degradarea inevitabilă a duplicării analogice.deși duplicarea digitală audio poate fi fără pierderi, succesul său depinde de succesul corecției de erori. Deși metodele de corecție a erorilor oferă date complet corecte, acoperirea erorilor nu face același lucru. În circumstanțe la limită, tehnicile de ascundere a erorilor introduc erori audibile în datele copiate. Deci, generarea ulterioară a copiilor digitale ar putea conține o acumulare de erori ascunse care nu erau prezente în original. Astfel, erorile trebuie corectate la originea lor. Precauțiile care au în vedere mecanisme impecabile, interfațarea cu jitter scăzut, sunt importante pentru duplicarea audio digitală, în special când se anticipează generarea multor copii. În practică, datele audio digitale pot fi copiate cu mare fidelitate. Când un fișier este copiat și conține bit cu bit aceleași date cu cel original, acesta este o clonă a originalului cu o frecvență implicită de eșantionare. Nici originalul și nici clonele realizate nu au control asupra mediului de stocare sau a condițiilor de redare. Copia va suna la fel cu originalul, dar numai dacă condițiile sale de redare sunt egale cu cele ale originalului. O metodă simplă de a testa acuratețea bit cu bit este încărcarea ambelor fișiere într-o stație audio și sincronizarea exactă cu acuratețea eșantioanelor, inversarea unui fișier și adunarea apoi a acestuia cu celălalt. Un rezultat nul ilustrează o acuratețe bit cu bit, iar un semnal reziduu arată diferența dintre cele două fișiere.

Sistemele de telecomunicații

Se spune că telecomucațiile și codarea sunt o “pereche făcută în rai”. Este cu siguranță cazul codurilor Reed – Solomon. Aceste coduri nu au constituit de la început o alegere evidentă pentru sistemele de telecomunicații, deoarece canalul de comunicații nu introduce de obicei erori de tip burst în datele transmise. S-a aflat totuși mai târziu că atunci când sunt folosite codurile convoluționale și Reed – Solomon în sisteme concatenate, se obțin câștiguri de codare enorme. Un cod convoluțional este folosit ca și cod intern, în timp ce codul Reed – Solomon este folosit pentru a corecta erorile de la ieșirea decodorului convoluțional (Viterbi). Ieșirea decodorului Viterbi se întâmplă să conțină erori de tip burst, furnizând astfel o potrivire perfectă pentru un cod Reed – Solomon. Cea mai renumită aplicație a sistemului concatenat convoluțional / Reed – Solomon a fost în expedițiile Voyager către Uranus și Neptun. Codurile Reed – Solomon au fost folosite în transmiterea de fotografii de pe aceste planete, conținând imagini ale unor lumi care, pentru rezidenții acestei planete, au fost odată mici pete făcute vizibile doar prin folosirea unor telescoape puternice. Figura 19 conține prima fotografie de pe Uranus făcută de pe Voyager, care este de asemenea prima imagine codată Reed- Solomon transmisă vreodată din spațiu.

O altă misiune cunoscută este Galileo, pe Jupiter. Antena de câștig ridicat de la bordul navei nu a funcționat corect, nefiind astfel utilizată. Toate datele colectate trebuiau trimise pe Pământ printr-o antenă de câștig redus determinând o scădere drastică a vitezei cu care nava putea transmite datele. Ingineri din lumea întregă au lucrat pentru a găsi metode de a creste câștigul de codare furnizat de codurile concatenate folosite de Galileo. Mijloacele puternice de a rezolva această problemă presupun folosirea decodării iterative și a algoritmului Viterbi cu ieșire software(AVIS). AVIS permite declararea locațiilor de eroare la intrarea decodorului Reed –Solomon, îmbunătățind considerabil performanța. Un rezultat cheie care se obține este demostrația că sistemul concatenat convoluțional / Reed – Solomon poate oferi transmisii de date sigure dincolo de rate de scurtare. Rata de scurtare este un concept teoretic care se consideră că denotă cea mai bună performanță posibilă pentru un sistem de control a erorilor. S-a demonstrat că pentru un sistem de control al erorilor concatenat, această presupusă barieră poate fi depășită.

Figura 19: Uranus văzut de la o distanță de peste 200 milioane de mile

Controlul erorilor pentru sisteme cu reacție

Wicker și Bartz au examinat numeroase mijloace de a folosi codurile Reed – Solomon in aplicații care permit transmiterea informației de la receptor înapoi la emițător. Asemenea aplicații include sisteme mobile de transmisie a datelor și sisteme de comunicații militare de mare securitate. O dată cu capacitățile lor puternice de corecție a erorilor, codurile Reed – Solomon pot oferi de asemnea detecția simultană a unui mare volum de erori. Cheia stă în diferența dintre o eroare de decodare și un eșec de decodare. Să considerăm decodarea unui cod R-S corector de t erori. Dacă un cuvânt recepționat diferă de un cuvânt incorect în t sau mai puține coordonate, atunci din acel cuvânt va rezulta o eroare de decodare. Acesta este o condiție nedetectabilă care cauzează erori în datele decodate. Pe de altă parte, dacă un cuvânt afectat de zgomot difreă de toate cuvintele de cod în (t + 1) sau mai multe coordonate, atunci decodorul declară un eșec de decodare. Eșecurile de decodare sunt detectabile, încât receptorul poate să ceară o retransmisie a cuvântului problematic. Erorile de decodare sunt, de fapt, destul de rare, iar cererile de retransmisie pot fi folosite pentru a dezvolta sistemele de control al erorilor Reed – Solomon la nivele foarte ridicate de performanță.

Design RTL Verilog al decodorului Reed – Solomon (15, 5)

Arhitectură și funcționare

Schema bloc a design-ului hardware al decodorului Reed – Solomon (15, 5) este prezentată în figura de mai jos:

Figura 20: structura design-ului

Fiecare din aceste blocuri constituie un modul din design, având o funcționalitate bine determinată și implementând câte un pas din algoritmul de decodare. Interconectarea modulelor în vederea realizării controlului logic al fluxului de date generate de către acestea, are loc în modulul denumit top, are reprezintă de fapt decodorul în sine. În acest modul sunt instanțiate toate modulele amintite, iar cu ajutorul semnalelor de ieșire din fiecare din ele care semnalizează finalizarea pasului de decodare executat de blocul respectiv, se face legătura logică între module.

Cele 15 simboluri de câte 4 biți ale cuvântului de la intrare (60 de biți în total pentru un cuvânt) sunt introduse paralel simultan în blocul de calcul al sindroamelor și în regiștrii interni pentru memorare. După ce au fost introduse toate cele 15 simboluri, blocul  ‘Syndrome’  începe să calculeze câte un sindrom pe perioada de ceas, furnizând după 17 perioade de ceas, ieșirea conținând toate cele 10 sindroame pe câte 4 biți fiecare. Calculul unui sindrom se face dupa formula :

Si = c1(αi)14 + c2(αi)13 + c3(αi)12 + c4(αi)11 + c5 (αi)10+ c6 (αi)9+ c7 (αi)8+

c8 (αi)7+ c9 (αi)6+ c10 (αi)5+ c11 (αi)4+ c12 (αi)3+ c13 (αi)2+ c14αi + c15

cu i=1,10

iar c1- c15 sunt simbolurile care compun cuvântul de cod de la intrare

r = [c1 c2 c3 c4 c5 c6 c7 c8 c9 c10 c11 c12 c13 c14 c15]

În continuare, după ce toate cele 10 sindroame au fost furnizate la ieșire, ieșirea acestui bloc este preluată la intrarea blocului BMAlg care implementează algoritmul Berlekamp-Massey. Acest modul este realizat sub forma unui FSM cu 3 stări care se repetă timp de 10 iterații succesive astfel : în cadrul fiecărei iterații, în prima stare se calculează variabila ‘delta’ specifică algoritmului B-M utilizat, in starea a 2-a, în funcție de valoarea obținută în starea anterioară pentru ‘delta’, se determină valoarea unei alte variabile specifice, notată ‘dirac’; în cele din urmă, în starea a 3-a, în funcție de valoarea lui ‘dirac’ determinată în starea anterioară, se calculează celelalte variabile, respectiv coeficienții polinoamelor specifice algoritmului : variabilele ‘L’ și ‘epsilon’ și coeficienții polinoamelor ‘lambda’ și ‘beta’. Se trece apoi la iterația următoare în care, de-a lungul celor 3 stări se vor obține noi valori pentru varibilele și polinoamele specifice algoritmului, iar la finalul celei de-a 10-a iterații, polinomul ‘lambda’ obținut va reprezenta polinomul de localizare a erorii cu grad maxim 5 egal cu numărul maxim de erori corectabile :

lambda(X) = c5X5 + c4X4 + c3X3 + c2X2 + c1X + c0, unde c5 – c1 sunt coeficienții ai căror valori sunt la ieșirea blocului BMAlg.

Inversele rădăcinilor acestui polinom vor da pozițiile erorilor în cadrul cuvântului de 15 simboluri introdus inițial în design cu ajutorul cărora se va construi mai târziu vectorul eroare care va corecta cuvântul de la intrare.

Întrucât coeficientul corespunzător termenului liber al polinomului de localizare a erorii furnizat de algoritmul B-M poate avea orice valoare din câmpul GF(16) iar pentru algoritmii următori din decodor este necesară o formă a polinomului a cărui termen liber să fie egal cu 1, am realizat blocul BMUnitar care împarte fiecare din coeficienții furnizați de blocul anterior la valoarea termenului liber, obținând astfel forma dorită cu termen liber unitar.

Blocul CHIENSearch va da la ieșire rădăcinile polinomului de localizare a erorii, înlocuind fiecare din elementele câmpului GF(16) în forma obținută anterior a polinomului și reținând doar elementele în care polinomul se anulează.

Blocul FORNEYAlg va furniza valorile erorilor ale căror poziții au fost determinate anterior ; se va calcula un polinom de evaluare a erorii, notat în design cu ‘erreval’ :

erreval(X) = [sigma(X) * S(X)] mod x2t, unde sigma(X) este polinomul echivalent cu lambda(X) ai cărui coeficienți sunt calculați de blocul BMUnitar, S(X) este polinomul sindrom care are urmatoarea formă S(x) = S1 + S2X + … + S10X9, iar t pentru decodorul RS(15,5) = (15-5)/2 = 5. Valorile erorilor se determină astfel :

ei = erreval(radi) / sigma’(radi), cu i = 1…max, max = numărul total de poziții de eroare găsite ; radi fiind rădăcinile polinomului de localizare a erorii, sigma’(X), derivata polinomului sigma(X).

Aceste valori găsite ale erorilor sunt memorate în vectorul errvect (de 15 elemente) pe pozițiile corespunzătoare valorilor calculate de algoritmul B-M, restul de elemente ale vectorului fiind 0 . Acest vector de 15 elemente se va aduna în final element cu element la cuvântul recepționat memorat în regiștrii interni, rezultând astfel cuvântul corectat ce va fi furnizat la ieșirea decodorului paralel.

3.2. Blocurile componente ale design-ului

3.2.1 Blocul SYNDROME

Modulul conține instanța ‘syndop’, aceasta reprezentând circuitul combinațional alcătuit din sume, produse, ridicări la putere în câmp Galois care implementează formula de calcul a sindroamelor menționată mai sus. După 15 perioade de ceas în care sunt memorate intern simbolurile cuvântului de cod de la intrare, se incepe calculul sindroamelor, acestea rezultând la ieșire, câte unul la fiecare front de ceas, iar la frontul la care valorile tuturor celor 10 sindroame sunt prezente la ieșirea ‘syndrome’, se asertează semnalul de ieșire ‘compdone’.

Figura de jos ilustrează rezultatele unei simulări în ModelSim a acestui bloc :

Figura 21 : rezultatele simulării pentru blocul Syndrome

– ceasul ‘ck’ este activ pe frontul pozitiv

– semnalul de intrare ‘reset’ este sincron cu ‘ck’

– intrarea ‘enable’(sincrona cu ‘ck’) indică prezența celor 15 simboluri ale cuvântului recepționat pe durata în care se află în ‘1’ ;după ce toate cele 15 simboluri au fost încărcate, ‘enable’ poate rămâne în ‘0’ sau trece în ‘0’ fără a afecta viitoarea funcționare a blocului

– la intrarea pe 60 biți ‘insymbol’(sincrona cu ‘ck’) vor fi încărcate cele 15 simboluri ale cuvântului recepționat ; această intrare este intrare și în decodor (modulul top)

– la ieșirea pe 40 biti ‘syndrome’ vor fi prezente cele 10 sindroame calculate ; această ieșire va intra în blocul BMalg cât și în blocul FORNEYalg

– ieșirea ‘compdone’ se asertează când toate cele 10 sindroame sunt prezente la ieșirea ‘syndrome’ ; acest semnal va constitui semnalul de enable pentru urmatorul bloc, BMalg

Niciunul dintre semnalele de intrare/iesire nu este tristate.

După ce toate cele 15 simboluri ale cuvântului recepționat au fost incărcate în blocul ‘syndrome’, se începe calculul sindroamelor. Pe masură ce fiecare din acestea sunt calculate, sunt plasate la ieșire unul câte unul. Astfel când primul sindrom este gata calculat, este prezent la ieșirea ‘syndrome’ pe cei mai puțin seminificativi 4 biți. Procedura continuă până se completează toate cele 10 sindroame.

3.2.2 Blocul BMAlg

Modulul conține instanțiate modulele combinaționale ‘delta10’ și ‘lambda_sum’ care implementează relațiile de calcul ale polinomului lamba si ale variabilei specifice ‘delta’. Funcționarea acestui modul este explicată mai sus.

Rezultatele unei simulări în ModelSim a blocului în care sunt introduse la intrare sindroamele obținute dintr-un cuvânt de intrare conținând 3 erori sunt ilustrate mai jos. Menționez că funcționarea fiecăruia dintre blocuri a fost verificată confruntând rezultatele numerice de la ieșire cu cele obținute prin rularea funcției Matlab.

Ca și în cazul anterior, în momentul în care rezultatul este furnizat la ieșirea ‘lambda’ (valoarea coeficienților polinomului de localizare a erorii), semnalul de ieșire ‘outready’ va trece din ‘0’ logic în ‘1’ logic.

Figura 22 : rezultatele simulării pentru blocul BMAlg

– ceasul ‘ck’ este activ pe frontul pozitiv

– intarea ‘reset’ este sincronă cu ‘ck’

– intrarea ‘enable’ este sincronă cu ‘ck’ și permite funcționarea blocului, începând cu încărcarea celor 10 sindroame calculate

– intrarea ‘syndrome’ este sincronă cu ‘ck’ și este folosită pentru a prelua sindroamele calculate de blocul ‘sindrome’ de la ieșirea ‘syndrome’ a acestuia

– ieșirea ‘lambda’ va conține valorile coeficienților polinomului de localizare a erorii în ordinea : termenul liber va ocupa cei mai puțin semnificativi 4 biți ai ieșirii, pe următorii 4 biți se va afla coeficientul lui X1 ș.a.m.d. ; această ieșire va intra în blocul următor, BMunitar

– ieșirea ‘outready’ se asertează când s-au finalizat toate cele 10 iterații care compun algoritmul Berlekamp-Massey simultan cu plasarea la ieșirea ‘lambda’ a valorilor coeficienților polinomului de localizare a erorii ; această ieșire va constitui intrarea de enable a blocului BMunitar

Niciunul dintre semnalele de intrare/ieșire nu este tristate.

Celelalte semnale prezente pe formele de undă reprezintă semnale interne din cadrul blocului BMalg : variabilele specifice algoritmului : delta, L, epsilon, dirac, coeficienții polinomului beta , stările prin care trece FSM-ul de-a lungul celor 10 iterații precum și intrări / ieșiri din blocurile combinaționale folosite pentru calculele în câmp Galois ale variabilelor și polinoamelor mai sus amintite.

3.2.3 Blocul BMUnitar

Semnalul de ieșire care se asertează în momentul când coeficienții polinomului de localizare a erorii calculați sunt prezenți la ieșirea ‘coef’ este ‘ready’.

Rezultatele simulării funcționale în ModelSim sunt ilustrate mai jos :

Figura 23 : rezultatele simulării pentru blocul BMUnitar

– ceasul ‘ck’ este activ pe frontul pozitiv

– intrarea ‘reset’ este sincrona cu ‘ck’

– intrarea ‘enable’ este sincronă cu ‘ck’ și permite funcționarea blocului, începând cu încărcarea coeficienților polinomului de localizare a erorii obținuți din blocul BMalg

– intrarea ‘incoef’ este sincronă cu ‘ck’ și e folosită pentru încărcarea coeficienților polinomului de localizare a erorii

– iesirea ‘coef’ va conține valorile noului set de coeficienți în care termenul liber este unitar ; acest semnal va intra în blocul CHIENsearch și în blocul FORNEYalg ;

– ieșirea ‘ready’ se asertează când s-a terminat calculul noului set de coeficienți și aceștia sunt prezenți la ieșirea ‘coef’; această ieșire va constitui intrare de enable pentru următorul bloc, CHIENsearch

Niciunul dintre semnalele de intrare/ieșire nu este tristate.

Se observă că la ieșire se obține un set de coeficienți în care ultimul, cel corespunzător termenului liber este egal cu 1.

3.2.4 Blocul CHIENSearch

Acest modul are instanțiate circuitele combinaționale care realizează calculul valorii polinomului de localizare a erorii pentru fiecare din elementele campului GF(16).

După ce au fost evaluate toate elementele câmpului, se asertează semnalul de ieșire ‘ready’, indicând faptul că la ieșirea ‘rad’ se află în acel moment toate rădăcinile găsite ale polinomului de localizare.

Rezultatele simulării în ModelSim sunt date mai jos:

Figura 24: rezultatele simulării pentru blocul ChienSearch

– intrarea de ceas ‘ck’ este activă pe front pozitiv

– intrarea ‘reset’ este sincronă cu ‘ck’

– intrarea ‘enable’ este sincronă cu ‘ck’ și permite funcționarea blocului, începând cu încărcarea coeficienților furnizați de blocul BMunitar și continuând cu căutarea rădăcinilor pentru polinomul de localizare a erorii

– ieșirea ‘rad’ va conține valorile găsite ale rădăcinilor; această ieșire va intra în blocul următor, FORNEYalg

– iesirea ‘ready’ se asertează după ce toate elementele câmpului GF(16) au fost testate ca posibile rădăcini ale polinomului localizator

Niciunul dintre semnalele de intrare/ieșire nu este tristate.

3.2.5 Blocul FORNEYAlg

Modulul conține instanțiate modulele combinaționale care realizează operațiile în câmp Galois pentru calculul valorilor erorilor în conformitate cu pașii prezentați mai sus, unde s-a explicat funcționarea modulului.

Rezultatele simulării în ModelSim pentru care au fost introduse la intrare valorile sindroamelor, rădăcinilor polinomului de localizare și coeficienții acestuia corespunzătoare unui cuvânt de intrare având 2 erori sunt date mai jos:

Figura 25: rezultatele simulării pentru blocul ForneyAlg

– intrarea de ceas ‘ck’ este activă pe front pozitiv

– intrarea ‘reset’ este sincronă cu ‘ck’

– intrarea ‘enable’ este sincronă cu ‘ck’ și permite funcționarea blocului, începând cu încărcarea simultană a sindroamelor, coeficienților furnizați de blocul BMunitar și a rădăcinilor calculate de blocul CHIENsearch și continuând cu pașii de calcul a valorilor erorilor

– ieșirea ‘err’ va conține valorile calculate ale erorilor; această ieșire va fi folosită pentru a construi vectorul eroare din modulul top, ‘RSDecoder_top’ , vector care se va aduna simbol cu simbol la cuvântul recepționat, rezultatul fiind cuvântul decodat ale cărui simboluri vor fi furnizate la ieșirea decodorului, paralel

– ieșirea ‘ready’ se asertează atunci când valoarea celei de-a 5-a erori (diferită de 0 când exista o a 5-a eroare sau egală cu 0 atunci când nu există o a 5-a eroare) a fost plasată la ieșire ; acest semnal este folosit în modulul top pentru a determina momentul potrivit pentru a începe construirea vectorului de eroare.

Niciunul dintre semnalele de intrare/ieșire nu este tristate.

Cazuri de funcționare ale decodorului

Decodorul Reed – Solomon este proiectat să corecteze maxim 5 erori de simbol dintr-un cuvânt de cod recepționat la intrare. Rezultă astfel 7 cazuri posibile de funcționare :

cuvântul recepționat nu conține erori: în această situație, decodorul nu trebuie să modifice nici un simbol din cuvântul recepționat, ci să furnizeze la ieșire un cuvânt identic cu cel primit

cuvântul recepționat conține o eroare: în această situație, decodorul trebuie să detecteze și corecteze eroarea și să plaseze la ieșire cuvântul de cod corect

cuvântul recepționat conține două erori : decodorul trebuie să localizeze și corecteze erorile, furnizând un cuvânt corect la ieșire

cuvântul recepționat conține trei erori : la fel ca în cazul anterior, decodorul va trebui să detecteze și corecteze erorile și să ofere un cuvânt corect

cuvântul recepționat conține patru erori : comportarea decodorului va fi similară cu cea din cazul anterior

cuvântul recepționat conține cinci erori : acesta este numărul maxim de erori pe care decodorul le poate detecta și corecta și furniza un cuvânt corect la ieșirea sa

cuvântul recepționat conține mai mult de cinci erori : în acest caz, funcționarea decorului nu poate fi a priori cunoscută, cuvântul furnizat la ieșire putând include orice valori pentru simbolurile componente

Fiecare din primele șase cazuri de funcționare este ilustrat in formele de undă obținute cu simulatorul ModelSim XE III 6.2g. Rezultatele ce vor fi prezentate corespund, la fel ca în cazurile de mai sus, unor simulări funcționale, ceea ce înseamna că ceea ce se simulează este codul RTL scris. Totuși, pentru acest proiect au fost realizate și simulări post-sinteză în care ceea ce se simulează este netlist-ul obținut în programul Xilinx ISE 8.2i în urma sintetizării codului RTL. În mod ideal, rezultatele simulării post-sinteză trebuie să fie la fel cu cele ale simulării funcționale. Din acest motiv, codul RTL a fost prelucrat până când această condiție a fost îndeplinită. Astfel, nu mai are sens prezentarea rezultatelor simulărilor post-sinteză, întrucât ele sunt identice cu cele funcționale. Corectitudinea rezultatelor de la ieșirea decodorului a fost verificată cu ajutorul funcției Matlab amintite mai sus care realizeză decodarea Reed – Solomon pentru orice dimensiune a câmpului Galois pentru care este definit decodorul.

0 erori în cuvântul de intrare

Figura 26 : rezultatele simulării pentru cazul în care nu sunt erori în cuvântul de intrare

În acest caz cuvântul recepționat este corect și coincide cu cel de la ieșire : [d c b a 9 3 f d 6 b 2 8 6 f 3] (scriere in baza 16).

o eroare în cuvântul de intrare

Figura 27 : : rezultatele simulării pentru cazul în care există o eroare în cuvântul de intrare

În acest caz eroarea se află pe poziția a 7-a, privind de la cel mai semnificativ simbol spre cel mai puțin semnificativ : simbolul eronat are valoarea ‘c’ (12 în baza 10), valoarea lui corectă fiind ‘3’ și fiind prezentă la ieșire.

două erori în cuvântul de intrare

Figura 28 : rezultatele simulării pentru cazul în care există două erori în cuvântul de intrare

În acest caz cuvântul recepționat conține erori pe prima și ultima poziție, adică pentru primul și ultimul său simbol, cuvântul corect fiind : [8 e 1 6 9 5 0 6 6 4 6 4 2 f e].

trei erori în cuvântul de intrare

Figura 29 : rezultatele simulării pentru cazul în care există trei erori în cuvântul de intrare

În acest caz, cuvântul conține erori pe pozițiile 1, 2 și 9, iar cuvântul corect este : [1 2 0 a c e 5 7 1 8 d 1 8 a 0].

patru erori în cuvântul de intrare

Figura 30 : rezultatele simulării pentru cazul în care există patru erori în cuvântul de intrare

În acest caz erorile se află pe pozițiile 2, 4, 10 și 13, iar valorile corecte ale simbolurilor de pe aceste poziții sunt : 3, b, 6 și 9.

cinci erori în cuvântul de intrare

Figura 31 : rezultatele simulării pentru cazul în care există cinci erori în cuvântul de intrare

În acest ultim caz, cuvântul recepționat conține următoarele simboluri eronate : simbolul cu valoarea ‘a’ de pe poziția 3, simbolul ‘1’ de pe poziția 8, simbolul ‘a’ de pe poziția 9, simbolul ‘2’ de pe poziția 12 și simbolul ‘c’ de pe poziția 15. La ieșire, se pot observa valorile corecte : ‘c’, ‘d’, ‘f’, ‘6’ și respectiv ‘d’.

3.4 Configurarea design-ul hardware pe FPGA

Codul RTL scris a fost configurat pe o plăcuță FPGA Opal Kelly de la Xilinx. XEM3001 este o plăcuță de mici dimensiuni, comparabile cu ale unui card bancar, care include chip-ul FPGA Xilinx Spartan 3. Această plăcuță este un sistem experimental execelent care conferă acces la aproape toți cei 208 pini de intrare / ieșire ai dispozitivului Spartan 3. Interfața sa USB 2.0 oferă download-uri rapide și acces ușor prin software-ul FrontPanel. Un PLL on-board oferă generarea flexibilă de semnal de ceas pentru o variatate de aplicații iar butoanele și LED-urile de pe plăcuță permit interfațarea ușoară atunci când componentele FrontPanel nu sunt potrivite scopului.

3.4.1 Footprint-ul PCB al plăcuței

Un desen mecanic al plăcuței XEM3001 este ilustrat mai jos. (Dimensiunile sunt în mils : 1 mil = 0.001 inch)

Figura 32 : footprint-ul plăcuței Opal Kelly XEM 3001 V2

PCB-ul are dimensiunile 3.5 inch x 2.0 inch (88.9 mm x 50.8 mm) având patru găuri de prindere spațiate ca în figură. Aceste găuri de prindere sunt conectate electric la planul de masă.

Cele trei porturi de acces ale FPGA-ului, JP1, JP2 și JP3 sunt localizate pe o grilă de 0.1 inch astfel încât întreaga plăcuță să poată fi atașată la o plăcuță prototip standard. Header-ul JTAG JP4 se află tot pe această grilă.

3.4.2 Diagrama bloc funcțională

Figura 33 : diagrama bloc funcțională a plăcuței FPGA

3.4.3 Sursa de curent

XEM3001 se alimentează de la sursa de 5V a USB-ului și generează tensiunile de care are nevoie de aici. Pentru aceasta, XEM3001 are regulatoare liniare mici pentru 3.3V, 2.5V și 1.8V. Puterea externă poate fi aplicată la oricare din pinii de 3.3V, JP1, JP2 sau JP3 cât timp jumper-ul J1 este scos. În acest caz, sursa de 5V a USB-ului nu este folosită.

Computerele au deseori porturi USB care nu furnizează curent pe bus. Pentru a opera ca un dispozitiv alimentat pe bus, plăcuța XEM3001 trebuie conectată la un port care furnizează curent pe bus.

3.4.4 Interfața USB 2.0

Plăcuța folosește un microcontroller USB Cypress CY68013 FX2. Astfel plăcuța este recunoscută ca un periferic de tip ‘plug and play’ pe majoritatea PC-urilor. Si mai important, download-urile pe FPGA au loc foarte repede, instrumentele virtuale ale FrontPanel-ului se updat-ează foarte repede, iar transferurile de date sunt mult mai rapide decât pe interfețele pe port paralel întâlnite la majoritatea plăcuțelor FPGA.

3.4.5 Perifericele plăcuței

EEPROM

Un EEPROM serial este atașat microcontroller-ului USB, fără a fi direct accesibil FPGA-ului. Este folosit pentru a stoca codul de butare pentru microcontroller, precum și datele de configurare ale PLL-ului și un șir de caractere pentru identificarea dispozitivului.

Datele de configurare ale PLL-lui sunt încărcate din EEPROM și folosite pentru a reconfigura PLL-ului de fiecare dată când un nou fișier de configurare este încărcat pe FPGA. Deci, imediat ce FPGA-ul a fost configurat, vor fi prezente ceasuri stabile și active la pinii săi. Configurarea PLL stocată poate fi schimbată folosind meniul ‘PLL Configuration’ din FrontPanel.

EEPROM-ul stochează de asemenea un șir de caractere pentru identificarea dispozitivului care poate fi schimbat folosind FrontPanel-ul. Acest șir de caractere are doar un rol cosmetic și este util când mai multe dispozitive XEM sunt conectate la același computer, încât să poată fi selectat dispozitivul dorit.

PLL Cypress CY22150

Un PLL cu ieșiri multiple poate oferi până la 5 ceasuri, trei pentru FPGA și alte două pentru conectorii de expansiune JP2 și JP3. PLL-ul este comandat de semnal de ieșire de 48 MHz din microcontroller-ul USB. PLL poate furniza ceasuri cu frecvență de până la 150 MHz și este configurat prin FrontPanel

LED-urile și Butoanele

Opt LED-uri și patru butoane sunt diaponibile pentru uz general ca intrări sau ieșiri.

3.4.6 Conectorii de expansiune

Trei conectori de expansiune sunt disponibili pentru a conecta plăcuța la diferite dispozitive. Acești conectori oferă alimentare la 3.3V, masă, ieșiri pentru PLL, și 88 de pini ai FPGA-ului pentru intrări / ieșiri generale. Toți conectorii de expnasiune sunt pe o grilă de 0.1 inch astfel încât întregul XEM să poată fi încărcat pe o plăcuță PCB de 0.1 inch standard.

3.4.7 Suportul FrontPanel

Soft-ul FrontPanel crește suportul periferic limitat cu instrumente virtuale cum ar fi LED-uri,

display hexazecimal, butoane, butoane tip întrerupător, ș.a.m.d.Aceste instrumente transformă PC-ul într-o plăcuță cu intrări / ieșiri reconfigurabilă.

3.4.8 Rezultatele configurării codului RTL sintetizat pe FPGA

Figurile de mai jos prezintă rezultatele configurării design-ului realizat pe plăcuța XEM3001 de la Opal Kelly pentru cele șase cazuri de funcționare : cuvântul de intrare conține 0, 1, 2, 3, 4 sau 5 erori. Imaginile ilustrează profilul FrontPanel realizat în cod XML cu ajutorul căruia s-a făcut interfațarea dintre PC și FPGA. În figuri se observă că au fost configurate aceleași cazuri care au fost prezentate mai sus în rezultatele de la simulări și că rezultatele coincid.

Figura 34 : 0 erori în cuvântul de intrare

Figura 35: o eroare pe poziția 9 (de la dreapta la stânga)

Figura 36: două erori pe pozițiile 1 și 15 (de la dreapta la stânga)

Figura 37: trei erori pe pozițiile 7, 14 și 15 (de la dreapta la stânga)

Figura 38: patru erori pe pozițiile 2, 5, 12 și 14 (de la dreapta la stânga)

Figura 39: cinci erori pe pozițiile 1, 4, 7, 8 și 13

3.5 Mediu de verificare hardware

3.5.1 Introducere – conceptul de verificare hardware și implementarea lui

Strategiile de verificare tradiționale implică scrierea unor cazuri de testare directe pentru a exersa toate caracteristicile unui Design sub Testare (DUT = Design Under Test) iar mediul este scris adesea într-un limbaj de descriere hardware sau în ‘C’. Această metodă s-a dovedit a fi incomodă și inadecvată pentru a adresa toate scenariile posibile, presupunând în același timp și foarte mult timp și efort.

O soluție la acestă problemă de productivitate este creșterea nivelului de abstractizare și folosirea unui stimulus aleator cu constrângeri pentru a stimula design-ul. Limbajele de verificare hardware (HVL = Hardware Verification Language) cum ar fi ‘e’ sau Vera folosesc caracteristicile progrămării orientate obiect, tipuri de date complexe, proceduri automatizate configurabile și înțeleg conceptele hardware de timp și concurență.

În figura de mai jos este prezentat un exemplu de mediu de verificare.

Orice mediu de verificare are în centru design-ul verficat (DUT) care se conectează la componentele mediului. Tipul acestor componente și varietatea lor diferă de la un caz la altul, fiind în conformitate cu specificațiile design-ului și, în consecință, necesitățile procesului de verificare.

În exemplul de mai sus apar următoarele componente: monitor, driver, checker și scoreboard.

Monitorul, după cum sugerează și numele, urmărește valorile logice de pe un bus. Această componentă convertește tranzițiile semnalelor de pe interfața design-ului într-un flux de tranzacții. Termenul de tranzacție presupune ridicarea nivelului de abstractizare atunci când este în discuție o secvență de valori binare, acestea primind semnificații precise, cum ar fi: operația de reset, de scriere a unor date la intrarea design-ului, citire a unor date furnizate de design, etc. Monitorul este o componentă pasivă, ceea ce înseamnă că nu afectează în nici un fel modul de funcționare a design-ului.

Driver-ul convertește un flux de tranzacții în activitate la nivel de pini. Un driver poate conține una sau mai multe proceduri prin care semnalele de intrare în design primesc valori corespunzătoare anumitor operații specifice pentru care design-ul a fost proiectat să răspundă.

Checker-ul este componentă care verifică respectarea modului de introducere a datelor în design, respectiv, a modului în care design-ul furnizează date la ieșire. Acest mod de comandă/funcționare poate fi stabilit de un protocol (ex.:I2C, SPI, Wishbone) sau doar de specificațiile de funcționare ale design-ului.

Scoreboard-ul este folosit pentru a determina corectitudinea funcționării design-ului. Această componentă urmărește datele care intră și ies din design și determină dacă acesta răspunde corect la stimulii aplicați. O alternativă la scoreboard poate fi folosirea unui model de referință (golden model) a cărui cod poate fi scris în C sau Verilog, care să furnizeze rezultatul așteptat la ieșirea design-ului. Acest rezultat așteptat va fi comparat cu datele furnizate de design în momentul în care acesta a terminat de procesat datele de la intrare iar rezultatul este prezent la ieșirea sa.

Figura 40: exemplu de structură a unui mediu de verificare

3.5.2 Mediul de verificare pentru decodorul Reed – Solomon

Mediul de verificare realizat a fost scris în System Verilog, un limbaj de verificare hardware care împrumută câteva caracteristici de la limbajul de descriere hardware Verilog dar mai adaugă tipuri de date și caracteristici specifice procesului de verificare.

Structura mediului de verificare implementat este redată mai jos.

Figura 41: structura mediului de verificare pentru decodorul Reed – Solomon

Se observă că in centru se află design-ul, reprezentat în acest caz de codul RTL Verilog scris pentru decodorul Reed-Solomon. În jurul design-ului testat se află componentele mediului de verificare.

Componentele denumite stimulus și driver reprezintă clase SystemVerilog. Nu s-a figurat interfața virtuală folosită, componentă specifică SystemVerilog, care conține declarațiile tuturor semnalelor ce alcătuiesc interfața fizică a design-ului precum și așa-numitele modport-uri corespunzătoare componentelor mediului de verificare (în acest caz, stimulus-ul și driver-ul) în cadrul cărora semnalele declarate primesc și un sens de intrare/ieșire sau intrare și ieșire(inout) în funcție de modul în care comunică respectivele componente de mediu cu semnalele de interfață. Scopul ei este de a face posibil accesul din partea componentelor de verificare la semnalele ce alcătuiesc interfața design-ului. Această interfață virtuală are avantajul că poate fi proprietate a unei clase, fiind astfel folosită în stimulus și driver. Tot nefigurat a rămas și generatorul de ceas, un modul SystemVerilog care asigură generarea unui semnal corect de ceas pentru design pe toată durata simulării.

Componenta de la exterior, stimulus-ul, are rolul, după cum sugerează și numele, de a crea stimuli pentru design. Totuși acest lucru nu se face în mod direct, ci într-un mod aleator cu constrângeri. Mesajul format din 5 simboluri este creat random de către stimulus. Acest mesaj este apoi codat Reed-Solomon, prin cod comportamental SystemVerilog, după care, în mod aleator, se aleg 5 locații de eroare, adică indicii din cadrul vectorului rezultat în urma procesului de codare Reed-Solomon, urmate de alegerea valorilor pentru cele cinci erori în același mod aleator. Se asigură astfel faptul că introducerea de erori în cuvântul de la intarea decodorului nu se face în mod direct, având astfel mult mai sigur șansa de a găsi bug-uri în codul RTL scris.

Driver-ul cuprinde proceduri care realizează operațiile elementare de comandă a design-ului: reset inițial, introducerea cuvântului de cod ce conține erori creat de stimulus și activarea semnalului de enable care permite începerea procesării de către design. Astfel, driver-ul conține instanțiat stimulus-ul, pentru a putea accesa metodele sale.

Modelul de referință este reprezentat de o funcție C care are rolul de furniza un răspuns așteptat cu care va fi comparat răspunsul dat de design. Astfel, funcția C și design-ul primesc același stimul iar rezultatele obținute trebuie, în mod ideal să coincidă. În caz contrar, se trage concluzia că există un bug în design, întrucât functia C, o dată integrată în mediu, se consideră a fi fără erori, pentru a putea oferi un rezultat de referință.

Programul de test apelează procedurile definite în driver asigurând succesiunea corectă și totodată realizează comparația dintre răspunsul oferit de funcția C și cel oferit de codul RTL, afișând mesaje corespunzătoare în consola simulatorului.

Toate componentele menționate mai sus, precum și codul RTL al decodorului sunt interconectate într-un modul, denumit top de verificare, în care se realizează și conectarea interfeței virtuale la pinii design-ului, instanțierea modului generator de ceas și a programului de test.

Bibliografie

1. Scripcariu, Luminița – Sisteme de Comunicații Digitale

2. Sklar, Bernard, Reed – Solomon Codes

3. Kang, Hyeong și Park, In – Cheol, A High Speed and Low Latency Reed – Solomon Decoder based on a Dual-Line Structure

4. Wicker, Stephen și Bhargava, Vijav, Reed – Solomon Codes and their Applications

5. Pohlmann, Ken, Principles of Digital Audio