Studiul Si Implementarea Unor Algoritmi Utilizati Pentru Detectia Si Corectia Erorilor

1. Introducere

Teoria transmiterii informației constituie un cadru în care se pot formula criterii de proiectare și obținere a unor soluții pentru sistemele numerice de prelucrare a semnalelor, soluții cu un înalt grad de aplicabilitate.

Acest domeniu se ocupă mai ales cu studiul algebric al fenomunului de transmitere a informației.

A transmite o informație este echivalent cu a face o comunicare despre ceva care

nu este cunoscut.

Informația recepționată într-un punct este utilă numai dacă este corectă și transmisă oportun. Pe timpul transmisiei la distanță, corectitudinea informației depinde în mare măsură de perturbațiile care acționează permanent asupra canalului de comunicație. Pentru ca receptorul să poată stabili corectitudinea informației recepționate are nevoie de un criteriu pe baza căruia să verifice și valideze informația primită. Un astfel de criteriu se poate stabili numai prin utilizarea codurilor detectoare de erori. Acesta este motivul pentru care codurile corecoare și detectoare de erori reprezintă pentru orice sistem informatic, care realizează teleprelucrarea sau teletransmisia datelor, un instrument practic de lucru.

Folosirea rațională a codurilor detectoare și corectoare de erori este cu atât mai necesară cu cât la perturbațiile naturale, care duc la distorsionarea semnalelor, se adaugă perturbațiile intenționate, provocate în mod intenționat de adversar, și care pot afecta considerabil informația utilă.

Teoria codurilor corectoare se afla într-un stadiu avansat de dezvoltare. De la prima lucrare a lui Hamming, elaborată în anul 1950, care a propus cele mai simple coduri corectoare , au apărut numeroase studii dintre care amintim pe cele a lui Peterson, Wosenkraft, Dadaev , Gallage și alții.

Pentru a micșora probabilitatea erorii se utilizează o serie de procedee, cum ar fi : sporirea puterii instalațiilor de emisie , perfecționarea liniilor magistrale de telecomunicații , reducerea intensității factorilor perturbatori, etc.

În concluzie Teoria Transmiterii Informației cuprinde totalitatea mijloacelor și

metodelor de transmisie eficientã și de protejare a informației împotriva perturbatiițor.

2. MEMORIU TEHNIC

2.1 SURSE DE INFORMAȚIE

Procedeul transmiterii informației este prezentat în figura 2.1.

În transmiterea informației la distanță este necesară o sursă de informație S care generează și transmite informația și un destinatar D care o recepționează.

Mediul fizic și toate echipamentele care realizează transmiterea informației se numește canal de transmisie. În unele cazuri informația este stocată și rolul canalului de transmisie este luat de mediul de stocare.

Informația pentru a putea fi transmisă (sau stocată) trebuie concretizată într-o mărime fizică cum ar fi: curent, tensiune sau undă electomagnetică. Această mărime fizică poartă denumirea de semnal.

Prin semnal se întelege orice manifestare fizică capabilă de a se propaga printr-un mediu. Ca urmare definția de mai sus exclude semnalele ce perturbă semnalul purtaror de informație, semnale ce poartă numele de zgomot.

În general, prin sursã de informații se va întelege mecanismul prin care se alege

într-un mod imprevizibil de destinatar, un anumit mesaj ce urmeazã a fi transmis.

Aceasta înseamnã cã sursa de informații potențial poate livra o mulțime de mesaje, dar la un moment dat ea va alege un anumit mesaj pe care-l va transmite, destinatarul necunoscând ce mesaj a ales sursa și l-a transmis.

Când informația ce urmează a fi transmisă este compatibilă cu canalul, respectiv mediul de stocare, ea poate fi transmisă direct. În majoritatea cazurilor înaintea transmiterii informației au loc anumite prelucrări de informație.

Există două tipuri de surse de informație:

Surse de informație analogice – semnalul de ieșire are o valoare continuă. Aceste surse se pot transforma în surse discrete prin tehnici de eșantionare și conversie.

Exemple de surse continue sunt: semnalul vocal, semnalul de televiziune, etc;

2. Surse de informație digitale – valorile semnalelor de ieșire sunt cuprinse într-un set finit. Ca exemplu sunt cele două simboluri utilizate în transmisiuni: ”0” și “1”. Principalul avantaj al acestor sisteme este imunitatea sporită la perturbații, datorită posibilității regenerării semnalului. Acesta având doar două valori permite refacerea cu ușurință a unui semnal avariat sever.

Prin canal de transmisiuni se înțelege în general, orice mediu fizic prin care se

poate propaga informația (cablul telefonic, cablu telegrafic, cablu coaxial, canal radio,

canal TV).

Figura 2.1 Schema bloc a unui sistem de transmitere digitală (numerică) a informației

Unde semnificația blocurilor din figură este:

S – sursă;

D – destinatar;

E,D – (encriptor)criptare/decriptare a sursei;

, – bloc de codare/decodare a canalului;

, – bloc de codare/decodare a sursei;

i – informație;

v – structură codată;

n – zgomot;

r – semnalul recepționat;

î – informație estimată;

Secvanța de biți este reprezentată de o secvență de semnal binar. Această secvență poartă numele de semnal în bandă de bază.

Blocul de codare a sursei este folosit în vederea adaptării naturii diferite a sursei la natura canalului/mediului de stocare și pentru asigurarea unei durate minime a transmisiunii, respectiv spațiului de stocare, prin compresia sursei.

Blocul de codare al canalului realizează protecția informației la efectele nedorite determinate de zgomotul din canalul sau mediul de stocare, protecția la erori.

Toate canalele de transmisiuni sunt perturbate de anumite zgomote astfel încât

semnalul de la ieșirea canalului r, este o sumã în general, dintre semnalul i transmis de

emițãtor și zgomotul n.

Modulația este utilizată pentru înlăturarea dificultaților de propagare, pentru realizarea transmisiunilor multiple și pentru reducerea efectelor perturbațiilor.

2.2 CODAREA PENTRU CANALE CU PERURBAȚII

Se va considera o sursă de entropie maximă, sursă la care toate simbolurile generate, numite simboluri de informație, au aceiași probabilitate. Înainte de a transmite aceste simboluri pe canalul cu perturbații se adaugă o anumită redundanță, de obicei prin adăugarea unor anumite simboluri numite și simboluri de control care au menirea să indice utilizatorului prezența erorilor sau chiar să îi dea posibilitatea să le corecteze.

În acest sens vorbim de coduri detectoare de erori și coduri corectoare de erori.

Figura 2.2 Sistem de transmisie cu legatură inversă

În cazul detecției de erori sistemul necesită un canal de întoarcere prin care să se facă anunțarea emițătorului că s-au detectat erori și că este necesară o retransmisie (ARQ – automatic repeat request). Acest sistem de retransmisie este larg utilizat în legătură cu sursele cu debit controlabil. La canalele cu perturbații mai mari pentru a evita repetări prea frecvente se folosește un sistem de corecție automată a erorilor, rămânând ca cererea de repetare să se facă numai când numărul erorilor depășește posibilitatea de corecție.

În cazul surselor cu debit necontrolabil sau atunci când informația este înmagazinată în diferite tipuri de memorii susceptibile de a se degrada este necesar să se utilizeze un sistem de corecție automată de erori.

2.2.1 Clasificarea codurilor corectoare sau detectoare de erori

Coduri bloc – în cazul în care prelucrările necesare obținerii proprietăților de detecție sau corecție se fac în blocuri de n simboluri. Șirurile de n simboluri se numesc cuvinte. Dacă acestor cuvinte le corespunde un mesaj generat de o sursă primară spunem că avem cuvinte cu sens;

Coduri convolutionale – în cazul în care prelucrarea simbolurilor generate de sursă nu se face pe blocuri, ci în mod continuu. Aceste coduri se mai numesc și recurente;

Coduri grup – sunt cele în care cuvintele sunt considerate ca fiind elemente într-un spațiu vectorial;

Coduri ciclice – sunt cele în care codurile în care cuvintele sunt considerate ca fiind elemente într-o algebră.

2.2.2 Teorema lui Shannon pentru canale cu perturbații

În cazul transmiterii, respectiv stocării, informației prin canale sau medii cu

perturbații, semnalele recepționate pot fi alterate datorită zgomotului, fapt ce impune luarea unor măsuri de protecție pentru reducerea acestor efecte nedorite.

Teorema lui Shannon este o teorema de existență ce afirmă urmăoarele:

Dacă avem o sursă de informație în timp real cu un debit de informație biți/secundă și un canal cu perturbații de capacitate C (<C) există un cod de lungime n

astfel încât probabilitatea unei erori de decodare să fie:

(2.2)

unde:

n este lungimea cuvintelor de cod;

e() este o funcție pozitivă de , complet determinată de caracteristica canalului, numită exponent al erorii și are forma :

Figura 2.2.3 Graficul exponentului erorii e()

2.3 CODURI BLOC LINIARE

Codurile bloc liniare au fost primele coduri corectoare, detectoare de erori.Ele au fost studiate și elaborate la scurt timp după apariția teroremei canalelor cu perturbații (teorema a II a lui Shannon).

Codurile bloc liniare sunt o clasă de coduri cu verificarea parității ce pot fi cararcterizate prin notațiile n, m și k :

unde

n reprezintă numărul simbolurilor din cuvântul de cod,

m reprezintă numărul de simboluri de informație,

k reprezintă numărul simbolurilor de control care mai sunt numite și simboluri redundante.

Astfel se formează cuvântul de cod v de lungime n în care :

Codorul transformă un bloc de m digiți, reprezentând mesajul, într-un bloc mai lung format din n digiți reprezentând cuvântul de cod constituit dintr-un alfabet dat de elemente.

Când cuvântul cod este constituit din două elemente (0 și 1) codul va fi un cod binar compus din digiți binari.

Din mulțimea codurilor bloc interes deosebit în aplicații practice prezintă structurile liniare.

Codurile corectoare în care pentru simbolurile informaționale și cele de control se fixează poziții distincte se numesc coduri separabile.

În codurile bloc separabile procesul codificării constă în determinarea simbolurilor de control și în dipunerea lor în pozițiile dinainte cunoscute ale combinației de cod. Aceste coduri sunt cele mai utilizate în practică.

Codurile separabile se împart în coduri nesistematice și coduri sistematice, la care simbolurile informaționale și cele de control ocupă aceleași poziții la toate combinațiile de cod.

Un cod bloc este liniar dacă și numai dacă suma modulo-2 a două cuvinte de cod este tot un cuvânt de cod.

Dintre cele mai cunoscute coduri sistematice bloc liniare amintim: coduri Hamming, coduri derivate din matricea Hadamard, coduri iterative, coduri MacDonald și coduri Reed-Muller .

2.4 CODURI CICLICE. DEFINIRE ȘI REPREZENTARE

Codurile ciclice sunt o subclasă importantă a codurilor bloc liniare reprezentând clasa celor mai utilizate coduri pentru detecția erorilor, atât independente, cât și a pachetelor de erori.

Primele cercetări în legătură cu codurile ciclice pot fi socotite lucrările lui Huffman din anul 1956.

Rezultate fundamentale în domeniu codurilor ciclice au obținut Bose și Ray-Chaudhuri în anul 1960 și, independent de ei, Hocquenghem în anul 1959, care au legat problema construirii codurilor ciclice de problema găsirii unui polinom generator g(x) peste un câmp finit ce admite ca rădăcini o mulțime de elemente date din extensite ca rădăcini o mulțime de elemente date din extensia câmpului finit.

Ele s-au impus în practică datorită simplității implementării cu registre de deplasare cu reacție (RDR); structura algebrică a acestor coduri a permis găsirea a numeroși algoritmi practici de decodare.

Codurile ciclice sunt coduri bloc liniare în care cele n simboluri de informație care formează un cuvânt sunt considerate ca fiind coeficienții unui polinom de grad n-1 și anume:

(2.3)

unde care este mulțimea simbolurilor elementare.

Cuvântul de cod fiind indentificat ca un polinom, asupra lui se pot efectua operații matematice mai complexe decât în cazul codurilor bloc unde cuvintele de cod erau identificate ca vectori:

(2.4)

Codul se numește ciclic pentru că , după cum se v-a vedea în cele ce urmează, dacă : (2.5)

este un cuvânt de cod atunci orice permutare ciclică a lui v este tot un cuvânt de cod :

(2.6)

Un subspațiu V Vn se numește ciclic dacă orice vector se poate obține din alt vector prin deplasare ciclică (de la stânga la dreapta) a componentelor acestuia. De asemenea subspațiul V Vn conține numai n vectori față de vectori conținuți în Vn, unde Q este numărul de simboluri elementare din mulțimea A. Un cod ce conține numai secvențe dintr-un spațiu ciclic se numește cod ciclic.

Peterson a demonstrat proprietatea fundamantală a codurilor ciclice , și anume că orice cod ciclic format din secvențe ce se pot reprezenta prin polinoame de gradul n -1 este un ideal în algebra claselor de resturi de polinoame modulo (). Idealul de polinoame reprezintă o submulțime a unui inel prin selectarea acelor polinoame care se bucură de proprietatea că sunt divizibile printr-un polinom dat G(x), denumit generatorul idealului.

De unde rezultă că proprietățile idealului vor fi și proprietățile codurilor ciclice.

Operațiile de adunare, înmulțire și împarțire a polinoamelor se efectuează ca în algebra clasică cu deosebirea că adunarea și înmulțirea elementelor A se face modulo Q.

Practica actulă utilizează coduri binare (Q = 2) de aceea expunerea se va limita la această categorie.

În cazul codurilor binare, mulțimea claselor de resturi modulo are elemente. Din această algebră, alegem o submulțime formată din elemente cărora le atribuim un sens (mulțimea cuvintelor de cod) care sunt multiplii ai polinomului generator g(x). Aceste cuvinte trebuie alese astfel încât să poată fi distinse de celălalte cuvinte care au sens.

Pentru orice polinom generator g(x) există un polinom h(x) astfel încât are loc relația:

(2.7)

deci g(x) se alege dintre divizorii lui p(x) de unde:

(2.8)

O structură de cod polinomial-ciclic constituie o mulțime de secvențe reprezentate sub formă polinomială, înzestrate cu proprietatea că se divid toate prin același polinom. Această proprietate este folosită drept criteriu de dețectie a erorilor.

Codul ciclic este determinat în mod univoc de polinomul generator g(x), aceasta nefiind singura determinare posibilă. Ca și în cazul codurilor liniare, pentru codurile ciclice se poate construi atât matricea generatoare G, cât și matricea de control H

2.5 CIRCUITE PENTRU CODARE ȘI DECODARE

După cum s-a amintit în subcapitoul anterior, de definire și reprezentare a codurilor ciclice, aceste coduri pot fi implementate ușor prin registre de deplasare cu reacție.

Dispozitivele de codificare ce materializează algoritmii acestor coduri au o construcție și funcționare simpă fiind realizate pe baza unor registre de deplasare și a unor circuite de tip SAU EXCLUSIV, care sunt de fapt sumatoare modulo-2.

Aceste sumatoare modulo-2 pot fi interioare sau exterioare, o prezentare mai amănunțită a acestora se va face mai jos.

Registru de deplasare cu reacție cu sumatoare modulo-2 exterioare

Un registru de deplasare cu reacție este un circuit secvențial liniar care poate funcționa fără semnal aplicat din exterior, numai pe baza semnalului de reacție. Având polinomul generator:

unde gi{0,1} (2.9)

unde gk este întotdeauna ”1”.

Schema unui astfel de registru este prezentată mai jos :

Figura 2.5.1 Schema bloc a unui RDR cu sumatoare modulo-2 exterioare

Urmărind schema registrului și notând cu sti starea celulei Ci la momentul i , funcționarea registrului este descrisă de ecuațiile :

(2.10)

Acest registru poate fi scri și sub formă matricială :

(2.11)

unde :

, , (2.12)

iar matricea caracteristică a registrului este :

(2.13)

Dacă starea inițială a registrului este S0 0, stările succesive sunt .

Numărul stărilor fiind finit , în mod obligatoriu registrul trebuie să ajungă în starea inițială, după un anumit număr de pași notat cu n, numit și perioadă a RDR. Pentru ca fiecare stare a RDR să fie precedată de o stare unică, este necesar să existe T-1, ceea ce impune ca g0 să fie 1.Numărul total de stări nenule este .

În continuare se definește polinomul caracteristic al matricei T ca fiind :

(2.14)

ceea ce ne arată că polinomul caracteristic al matricei T este polinomul generator g(x), el determinând în mod unic RDR.

Matricea caracteristică T este o rădăcină a polinomului generator g(T)=0.

Perioada matricei caracteristice T, sau lungimea este cel mai mic întreg pentru care :

(2.15)

Convenim să alegem ca și stare inițială a registrului starea :

(2.16)

De unde rezultă că cele n stări ale sistemului pot fi scrise :

(2.17)

Dacă introducem notația , și dacă T este o rădăcină a polinomului generator rezultă că și este o rădăcină a lui g(x) deci putem scrie :

(2.18)

Din teoria claselor de resturi modulo g(x) de gradul k se știe că este maxim dacă g(x) este primitiv (T se numește element primitiv al câmpului GF(2k) generat de g(x) de grad k, primitiv), de unde rezultă că RDR generează toate stările nenule într-un singur ciclu dacă g(x) este primitiv.

Registru de deplasare cu reacție cu sumatoare modulo-2 interioare

Schema bloc a unui astfel de registru este prezentată mai jos :

Figura 2.5.2 Schema bloc a unui RDR cu sumatoare modulo-2 interioare

Singura diferență față de registrele de deplasare cu reacție prezentate anterior este matricea caracteristică, care are formula :

(2.19)

Întreaga discuție facută pentru registru de deplasare cu reacție cu sumatoare modulo-2 exterioare este valabilă și în cazul registrelor de deplasare cu reacție cu sumatoare modulo-2 interioare.

2.5.1 Codor cu RDR pentru coduri ciclice sistematice

Codarea pentru coduri ciclice sistematice poate fi făcută cu registre de deplasare cu reacție cu sumatoare interioare sau exterioare.

Codor cu sumatoare modulo-2 exterioare

Figura 2.5.3 Schema bloc a unui codor ciclic sistematic cu RDR cu sumatoare exterioare

Funcționarea acestei scheme este descrisă în tabelul următor :

Tabelul 2.5.1 Funcționarea codorului ciclic realizat cu RDR cu sumatoare exterioare

La intrare vor fi simbolurile informațioanle iar la ieșire secvența codată .

Introducerea semnalului de intrare duce la modificarea ecuației de funcționare a registrului, și anume :

(2.20)

Se observă că s-au introdus sumatorul modulo-2 S2 și comutatorul k.

Biții unei succesiuni binare sosesc la intrarea registrului într-o anumită cadență numită tact. Comutatorul k este pe poziția 1 timp de m tacte cât se introduc în registru simbolurile de informație, după care trece pe poziția 2 timp de k tacte. În acest timp registrul RDR va efectua împărțirea rezultând astfel simbolurile de control.

La ieșire se va obține cuvântul de cod ciclic în structura sistematică :

(2.21)

Pe durata ultimelor k tacte, comutatorul este pe poziția 2, ieșirea lui S2 va fi pe 0, pentru că cele două intrări ale sale sunt comune. De unde rezultă că la finalul celor n tacte starea registrului va fi 0.

Astfel se poate exprima :

(2.22)

relație care poate fi scrisă si sub forma unui produs matricial :

(2.23)

Se observă că această relație este de forma de unde rezultă că matricea de control este de forma :

(2.24)

în care :

, iar T este cunoscută. (2.25)

Codor cu sumatoare modulo-2 interioare

Figura 2.5.4 Schema bloc a codorului ciclic sistematic cu RDR cu sumatoare modulo-2 interioare

Se observă apariția sumatorului modulo-2 S și a porții P.

Sumatorul permite introducerea simbolurilor de informație pe durata primelor m tacte.

Poarta P este deschisă pe durata primelor m tacte și blocată pe durata ultimelor k tacte.

Comutatorul k este pe poziția 1 pe durata primelor m tacte si pe poziția 2 pe durata ultimelor k tacte.

Această schemă funcționează pe baza relației :

(2.26)

unde :

iar (2.27)

După intoducerea simbolurilor de informație, la sfârșitul celor m tacte, în celulele RDR va fi încărcat restul împărțirii , de unde rezultă că după k tacte registrul va fi în starea Sn =0.

Identic cu cazul anterior a RDR cu sumatoare interioare Sn =0 se poate pune și sub forma matricială , doar că de data asta matricile T și U sunt date de relațiile prezentate mai sus respectiv (2.12) si (2.13)

2.5.2 Decodor ciclic pentru detecția erorilor

Condiția de detecție a erorii este ca sindromul s(x) , ce constituie restul împărțirii lui r(x) la g(x) să fie diferit de zero, de unde rezultă că decodorul va trebui să efectueze această împărțire. Registrul de deplasare cu reacție asigură împărțirea , de unde rezultă că vor putea fi folosiți și la decodare. Starea RDR-ului la sfârșitul celor n tacte este zero, deci în cazul detecției erorii este suficientă testarea stării RDR de la decodare identic cu cel la codare.

Decodor ciclic pentru detecția erorii realizat cu RDR cu sumatoare exterioare

Figura 2.5.5 Decodor ciclic pentru detecția erorii realizat cu RDR cu sumatoare exterioare

Decodor ciclic pentru detecția erorii realizat cu RDR cu sumatoare interioare

Figura 2.5.6 Schema bloc a unui decodor ciclic pentru detecția realizat cu RDR cu sumatoare interioare

2.5.3 Decodor ciclic pentru corecția erorilor

După cum s-a observat detecția erorii este posibilă la sfârșitul recepționării întregului cuvânt, după cele n tacte. Pentru corectarea erorii este necesară aflarea poziției pe care a apărut eroarea.

Este posibilă determinarea poziției eronate din expresia sindromului determinat la momentul n, găsindu-se anumite stări ale registrului sindrom (RS) atunci când simbolul eronat se găsește în ultima celulă a unui registru de memorie (RM) în care se încarcă serial cuvântul recepționat (r). Corecția se face însumând un 1 pe poziția determinată ca eronată. În timp corecția se desfășoară pe dutata (n +1,2n) , de unde rezultă că pentru corecția codurilor ciclice sunt necesare 2 tacte. Pentru a nu avea pauze în transmisie se utilizează două decodoare identice.

Figura 2.5.7 Schema bloc generală a unui decodor ciclic pentru corecția la erori

unde :

RM – registru de memorie;

RDR (SR) – registru sindrom;

D – detector a unei stări fixe a RS atunci când simbolul eronat este în ultima celulă a RM;

C – celulă de corecție;

Funcționarea schemei este prezentată mai jos.

Pe durata (1,n) : P1 este deschisă iar P1* este blocată.

P2 este blocată iar P2* este deschisă.

ceea ce asigură introducerea cuvântului recepționat în RM și în primul decodor.

Pe durata (n+1,2n) : P1 este blocată iar P1* este deschisă.

P2 este deschisă iar P2* este blocată.

Ceea ce detrmină posibilitatea corecției simbolului eronat în celula de corecție C, atunci când detectorul D indică o anumită stare fixă a RS; în același timp se recepționează următorul cuvânt care se încarcă simultan în RM , devenit disponibil pe măsură ce corectează cuvântul anterior încarcat , și în decodorul al doilea.

2.6 CODUL BCH

Codul Bose-Chaudhuri-Hocquenghem (BCH) este o generalizare a codului Hamming pentru cazul erorilor multiple independente.

Cuvintele, în cazul codului BCH se reprezintă polinomial.

Pentru o secvență formată din n simboluri, polinomul corespunzător este de grad n-1 sau mai mic:

(2.28)

Din definirea coduilor ciclice rezultă că pentru un polinom informațional i(x) de gradul m-1, cuvintele de cod se aleg astfel încât să fie multiplu al unui polinom de gradul k=n-m, numit polinom generator al codului.

(2.29)

(2.30)

. (2.31)

Mulțimea tuturor combinațiilor distincte ce se pot forma cu n simboluri (cuvinte de cod și cuvinte fară sens) formează o algebră. Această mulțime este formată din mulțimea claselor de resturi modulo, un polinom c(x) de grad n, cu coeficienți în GF(2).

Polinomul c(x) se alege .

În cazul codurilor binare, mulțimea claselor de resturi modulo are elemente. Din această algebră alegem o submulțime formată dinelemente cărora le atribuim sens (mulțimea cuvintelor de cod).

2.6.1 Codarea algebrică a codului BCH

Cuvântul de cod în cazul codului BCH conduce la obținerea unui cod nesistematic , în structura nemodificată nu regăsim informația nemodificată.

Astfel putem scrie:

(2.32)

De unde deducem că v(x) este format din mulțimea combinațiilor liniare a vectorilor linie ai matricei generatoare G (sau v este subspațiul linie a lui G: v=iG), unde:

(2.33)

Pentru obținerea unei structuri sistematice, la care imformația să se găsească nemodificată, pe pozițiile cele mai semnificative, se procedează în felul următor:

(2.34)

(2.35)

Unde q(x) reprezintă un polinom cât, iar r(x) reprezintă un polinom rest de grad k-1. Împarțirea polinoamelor se efectuează ca în algebra clasică, cu deosebirea că adunarea și înmulțirea coeficienților se face modulo-2. Se mai ține seama de faptul că în modulo-2 adunarea și scăderea sunt operații echivalente.

(2.36)

Această relație de codare este folosită în obținerea unui cod ciclic sistematic. Ea poate fi prelucrată pentru obținerea unei relații de tipul

(2.37)

Produsul poate fi scris analog cu produsul scalar a doi vectori :

(2.38)

Sistemul de mai sus poate fi scris și sub forma :

(2.39)

Legea de codare a codurilor ciclice ne spune că v(x) trebuie să fie multiplu a lui g(x), care la rândul său trebuie să fie divizor a lui după cum spune releția:

(2.40)

Pentru a afla forma lui g(x) corector de un numar maxim de t erori vom folosi teoria câmpurilor finite (câmpuri Galois și extensii ale câmpurilor Galois).

În continuare vom prezenta pașii ce duc la realizarea aceste cerințe:

Se va alege un număr de r rădăcini ale lui pe care le notăm cu.

Aceste rădăcin sunt elemente primitive ale extensiei de ordin k a câmpului Galois binar, ordin ce este determinat de relația , unde k este extensia în care se lucrează (ordinul extensiei câmpului GF(2k)) și nu este numărul caracterelor de control.

Extensia este generată de un polinom primitiv p(x). Acest polinom are gradul k

Tabelul 2.6.1 Polinoamele primitive până la gradul k=5

Se calculează polinomul minimal a lui i , mi(x) ireductibil de grad minim pentru care mi(i) =0, polinom care se definește în felul următor :

(2.41)

Gradul orcărui polinom minimal este mai mic sau cel mult egal cu k.

Se determină g(x) conform următoarei formule:

(2.42)

Se pot determina tabele ce conțin polinoamele generatoare pentru diferite lungimi ale cuvintelor de cod si corectoare de una sau mai multe erori:

Tabelul 2.6.2 Polinoamele generatoare pentru coduri BCH până la n=31

Se observă că coeficienții polinomului generator sunt dați în octal de unde rezultă ca va fi nevoie de o transformare în binar.

Gradul orcărui polinom generator g(x) este egal cu numărul simbolurilor de control k și este mai mic sau cel mult egal cu k*t.

Numărul de termeni nenuli ai lui g(x) este egal cu distanța de cod .

Pentru corecția a unui număr de t erori se impune alegerea unui număr r=2t rădăcini i ceea ce determină obținerea unui cuvânt de cod având distanța minimă .

În cazul codurilor binare ciclice, dacă este o rădăcină și 2, 2*2, … 2(2k-1) sunt tot rădăcini de unde rezultă că în formarea polinomului generator este suficientă selectarea rădăcinilor impare :

(2.43)

Codarea propriuzisă poate fi facută în două moduri:

În cazul codurilor nesistematice utilizând relația :

(2.44)

Iar în cazul codurilor sistematice utilizând relația :

(2.45)

Prin utilizarea formulei prezentate mai sus. În această formulă se impune ca v(x) să aibă rădăcini pe 1= , 3=3 ,…, 2t-1=2t-1 de unde rezultă:

obținând astfel :

(2.46)

, matrice care are dimensiunea

2.6.2 Calculul sindromului și detecția erorilor

În ipoteza erorilor de tip aditiv, caz în care r(x) este divizibil cu g(x) la recepție se obține:

Se va verfica legea de codare:

în care:

r(x) – cuvântul recepționat;

e(x) – cuvântul eroare;

s(x) – sindromul erorii;

Din formula de mai sus putem trage următoarele concluzii :

Sindromul erorii nu depinde de cuvântul ce a fost transmis, respectiv v(x) ci doar de cuvântul eroare e(x);

Dacă sindromul s(x) este egal cu zero rezultă că nu sunt erori sau că acestea nu sunt detectabile;

Dacă sindromul este egal cu zero se va face detecție de erori;

Sindromul este un polinom de grad celmult k-1;

Evaluarea eficienței unui cod detector de erori se face cu ajutorul capacitații de detecție a erorilor, definită de relația:

(2.47)

unde Nen reprezintă numărul total posibil de erori nedetectabile, iar Nte reprezintă numărul total de erori posibile.

Nen este determinat de acele combinații de erori care conduc la un alt cuvânt de cod, deci pentru care cuvântul eroare este un multiplu M a lui g(x) : .

Fie un pachet de erori de lungime p, situat între pozițiile i și j : p=i-j

(2.48)

În continuare vom analiza cele trei cazuri ce pot apărea cu referire la lungimea pachetului p față de gradul k al polinomului generator :

Cazul în care p este mai mic decat k

În această situație e(x) nu poate fi un multiplu a lui g(x) de unde rezultă că numărul total posibil de erori nedetectabile este egal cu zero, Nen =0. Prin urmare vor fi detectate toate pachetele de erori cu lungime mai mică decât gradul polinomului. Deci capacitatea de detecție a erorilor este egală cu unitatea:.

Cazul în care p este egal cu k

În această situație există o singură combinație de erori ce poate corespunde polinomului generator , rezultând astfel Nen =1.

Astfel,

, (2.49)

De unde rezultă :

(2.50)

Cazul în care p este mai mare decât k

În această situație nu vor fi detectate acele erori care sunt multiplii lui g(x).

(2.51)

unde m(x) este un polinom de grad cel mult p-k.

Astfel se determină :

(2.52)

(2.53)

(2.54)

Observație:

Vom obține o creștere a capacității de detecție pe măsură ce mărim gradul polinomului generator g(x).

2.6.3 Decodarea algebrică a codurilor BCH

Cel mai utilizat procedeu în decodarea codurilor ciclice este algoritmul Peterson cu căutare Chien.

Un cod ciclic corector de t erori are ca și cuvinte de cod vi ce admit ca rădăcini un număr de r = 2t rădăcini i GF(2k) , i=i :

(2.55)

În cazul codurilor binare ciclice, dacă este o rădăcină și 2, 2*2, … 2(2k-1) sunt tot rădăcini rezultă că în formarea polinomului generator este suficientă selectarea rădăcinilor impare

(2.56)

La recepție se verifică legea de codare

(2.57)

Pentru erori de tip aditiv această lege se exprimă în felul următor :

(2.58)

Pentru cele 2t rădăcini , expresia sindromului este :

(2.59)

În cazul erorilor binare, pentru corecția erorii este suficientă determinarea poziției acestora din expresia sindromului.

Presupunem un cuvânt eroare cu două erori pe pozițiile 2 și 4 : ,

expresia sindromului se calculează ca fiind :

(2.60)

unde Xk este expresia care definește locul erorii, denumită și locatorul erorii..

De unde rezultă că sindromul poate și exprimat de :

(2.61)

Astfel se vede că determinarea pozițiilor erorilor este rezolvarea unui sistem de ecuații neliniare cu necunoscuta Xk.

În continuare se prezintă algoritmul Peterson cu căutare Chien, acesta fiind unul dintre cei mai eficienți algoritmi de căutare. Prezentarea algoritmului se face în trei pași :

Calcularea sindromului erorii

Găsirea polinomului erorilor

Căutarea pozițiilor eronate

Se va calcula sindromul erorii cu ajutorul formulelor :

(2.62)

cu . (2.63)

Se va calcula polinomul erorilor (x). Acesta are ca rădăcini locatorii erorilor Xk

(2.64)

Coeficienții vor fi determinați în funcție de sindroamele calculate anterior.

În următorul tabel sunt date expresiile coeficienților în funcție de sindroamele calculate anterior pentru cazul în care avem una, două sau trei erori t=1,2,3.

Tabelul 2.6.3 Coeficienții polinoamelor erorilor pentru codul BCH cu t=1,2,3.

Locatorii Xk sunt rădăcini ale polinomului erorilor, de unde rezultă :

(2.65)

Dacă în relația de mai sus înlocuim pe x cu Xk obținem :

(2.66)

Înmulțind relația de mai sus cu Xki și însumând după indicele k, avem :

(2.67)

Astfel putem scrie. (2.68)

Se observă că ecuația de mai sus reprezintă un sistem de t ecuații cu t necunoscute. Rezolvarea acestui sistem se face aplicând regula lui Cramer.

Se calculează determinantul:

(2.69)

Dacă D0 atunci sistemul va avea o singură soluție unică dată de:

(2.70)

unde Di,j sunt determinanții caracteristici , obținuți prin înlocuirea coloanei j cu coloana formată din termenii liberi ai sistemului.

Observție

Dacă D=0 se presupune că în cuvântul recepționat avem mai puțin de t erori. Se caută un întreg e cât mai mare dar e t, astfel încât De0. În acest caz există posibilitatea apariției unei erori. Dacă nu există acest întreg rezultă că transmisia s-a efectuat fară erori. În cazul în care transmisia s-a efectuat fără erori Si=0

Căutarea Chien pentru determinarea pozițiilor eronate.

Algoritmul de căutare Chien ajută la punerea în evidență a poziției eronate .

În cazul unei poziții eronate Xk polinomul erorilor are forma :

(2.71)

Dacă împărțim aceasta relație la Xkt vom obține ecuația de căutare Chien :

(2.72)

unde i arată numărul poziției eronate. Numărul maxim de poziții eronate este t.

În algoritmul Chien căutarea simbolului eronat începe cu rn-1 caz în care Xk se înlocuiește cu (n-1) :

(2.73)

Simbolul rn-j va interveni în ecuația de cautare Chien sub forma :

(2.74)

De unde rezultă că ecuația Chien va fi de forma (2.75)

unde indicelui j=1 îi corespunde rn-1 iar lui j=n îi corespunde r0 (recepția se face începând cu rn-1).

Valoarea lui j pentru care este satisfăcută relația de mai sus va da pe Xk :

(2.76)

2.7 CODUL REED – SOLOMON

2.7.1 Definirea codurilor Reed-Solomon

Codurile Reed-Solomon sunt coduri clicle nebinare cu coeficienți în câmpul Galois.

Una dintre cele mai importante proprietăți ale codurilor Reed-Solomon este aceea că distanța minimă a unui cod RS(n,m) este n-m+1.Codurile de acest tip se mai numesc și “coduri separabile cu distanță minimă”

Un cuvânt Reed-Solomon de lungime n se poate exprima ca fiind :

(2.77)

sau

(2.78)

unde prima formulă reprezintă exprimarea vectorială a cuvântului iar a doua exprimarea polinomială și caracterele vi sunt elemente ale câmpului Galois GF(2k), deci poate fi exprimat în k biți.

Elementelor câmpului Galois li se pot asocia exprimări zecimale :

(2.79)

unde este un element primitiv al câmpului Galois GF(2k).

În continuare vom prezenta parametrii codurilor Reed-Solomon corectoare de erori .

Numărul de erori t pe care un cod le poate corecta;

Lungimea n a cuvântului este dată de relația :

(2.80)

unde k reprezintă extensia câmpului Galois GF(2k);

Numărul de caractere informaționale m si numărul caracterelor de control între care există relația :

(2.81)

Numărul caracterelor de control se determină cu ajutorul formulei :

(2.82)

Distanța de cod care este dată de relația :

(2.83)

2.7.2 Codarea în domeniu timp

La fel ca și în cazul codurilor BCH avem un polinom generator definit ca fiind cel mai mic multiplu comun asociat unui număr de 2t elemente consecutive ale câmpului Galois GF(2k) .

Codarea, ca și în cazul celorlalte coduri ciclice, se face prin relația :

(2.84)

Algoritmul de codare presupune formarea cuvintelor de cod v(x) astfel încât v(x) să fie divizibil cu g(x), deci cele două polinoame să aibă aceleași 2t rădăcini conform relației :

(2.85)

unde p este un întreg arbitrar ce se alege de obicei 0 sau 1.

Prin codare se poate obține un cod sistematic sau nesistematic. Codarea sistematică duce la obținerea unui cuvânt de cod la care pe primele poziții (cele mai semnificative) se află simbolurile de informație, iar pe ultimele poziții, caracterele de control.

2.7.3 Codarea în domeniu frecvență

Codarea în domeniu frecvență se obține utilizând transformata Fourier în câmpuri Galois.

Transformata Fourier discretă (TFD) a vectorului v

(2.86)

este un vector V de lungime n cu simboluri Vk GF(2k).

Aceste simboluri sunt date de relația de mai jos unde este un element primitiv a câmpului Galois GF(2k) :

(2.87)

Polinomul asociat unui cuvânt de lungime n în domeniul frecvență este :

(2.88)

Transformata Fourier discretă inversă (TFDI) se definește ca fiind:

(2.89)

de unde rezultă că :

(2.90)

Cuvântul de cod trebuie să fie divizibil cu poliniomul generator, de unde rezultă că cele două polinoame au aceleași rădăcini :

(2.91)

(2.92)

2.7.4 Decodarea algebrică a codurilor Reed-Solomon

Cei mai eficienți algoritmi de decodare, în cazul codurilor Reed-Solomon, sunt Peterson cu căutare Chien și Berlekamp – Massey

Pentru exemplificarea ambelor modalități de abordare a codurilor, primul va fi prezentat în domeniu timp iar al doilea în domeniu frecvență.

I. Algoritmul Peterson cu căutare Chien

1. Se va calcula sindromul erorii:

(2.93)

unde Xk – locatorii erorilor

Yk – valorile erorilor.

Se observă că spre deosebire de codul BCH s-au introdus și valorile erorilor care, adunate la valorile eronate, permit corectarea erorii.

2. Pentru determinarea coeficienților polinomului erorilor (x) în funcție de siondroamele Si calculate la pasul anterior folosim relația :

(2.94)

Tabelul coeficienților i =f(Si) pentru coduri Reed-Solomon este prezentat mai jos:

Tabelul 2.7.1 Coeficienții i =f(Si) pentru coduri Reed-Solomon

3. Determinarea locatorilor erorilor Xk (prin căutare Chien) este identică cu determinarea în cazul codurilor BCH :

(2.95)

4. Calculul valorii erorii Yk se face pornind de la relația

(2.96)

Această ecuație reprezintă un sistem liniar de t ecuații cu t necunoscute :

(2.97)

Folosind regul lui Cramer soluția se determină cu relațiile :

, (2.98)

unde Dij sunt determinanții caracteristici ai sistemului iar :

(2.99)

În continuare vom prezenta un tabel cu expresiile valorilor erorilor pentru codurile RS corectoare de una sau două erori.

Tabelul 2.7.2 Coeficienții Yk pentru coduri Reed-Solomon

5. Corecția unui caracter eronat , fie acesta rn-j , a cărui poziție Xk a fost determinată prin pașii anteriori se realizează cu ajutorul formulei :

(2.100)

II. Algoritmul Berlekamp-Massey

Acest algoritm se va implementa în domeniu frecvență pentru coduri puternic corectoare de erori.. Implementarea se va face în acest domeniu datorită vitezei mari de procesare.

În comparație cu domeniu timp, în domeniu frecvență se lucrează cu vectori de lungime mai mică (respectiv 2t) pe când în domeniu timp lungimea vectorului este n.

Se va considera recepția unui cuvânt afectat de t erori de tip aditiv :

(2.101)

unde eroarea e este diferită de zero pe pozițiile eronate și zero în rest.

La pasul următor se va aplica transformata discretă Fourier (TFD) cuvântului recepționat, obținându-se astfel :

(2.102)

unde datorită faptului că primele 2t componente ale vectorului V fiind nule rezultă :

, (2.103)

relația care ne arată că se pot determina ușor cele 2t componente ale cuvântului eroare din cuvântul transpus în frecvență.

Acest algoritm generează celălalte n-2t componente ale cuvântului eroare prin evoluția liberă a unui registru de deplasare cu reacție inițializat cu primele 2t componente ale acestuia.

Se va determina polinomul locatorilor erorilor (x) care e polinomul registrului de deplasare cu reacție initializat cu primele 2t componente Sk :

(2.104)

Se vor analiza cele două cazuri :

Dacă i este poziție eronată atunci -t este o rădăcină a polinomului locator după cum urmează :

(2.105)

Componentele vectorului eroare în timp sunt :

(2.106)

Dacă i nu este poziție eronată atunci -t nu este rădăcină a polinomului locator, deci :

(2.107)

Componentele vectorului eroare în timp sunt :

(2.108)

de unde rezultă că :

, (2.109)

deci trebuie să fie multiplu al polinomului :

(2.110)

sau :

, (2.111)

ecuație a cărui dezvoltare duce la sistemul de ecuații :

(2.112)

Acest sistem de ecuații poate fi dezvoltat în două subsisteme :

Un sistem cu t coeficienți Ei și având ca necunoscute coeficienții polinomului locator k :

(2.113)

Un sistem care determină celălalte n-2t componente ale vectorului eroare în domeniu frecvență, obținute prin evoluția liberă a unui registru de deplasare cu reacție :

(2.114)

Evoluția liberă a acestui registru, pentru cuvinte de cod de o lungime mare, face ca timpii de calcul sa fie foarte mari.

În continuare vom prezenta pașii care duc la înlăturarea acestui deficient :

Se va rescrie relația sub forma :

(2.115)

Evaluând relația în indicele -t, indicele i exprimă poziția erorii, se obține o nedeterminare care poate fi înlăturată prin derivare :

(2.116)

Prin înlocuire va rezulta :

(2.117)

de unde avem :

(2.118)

deci tocmai componentele vectorului eroare în domeniu timp.

Calculul polinoamelor (x) și (x) se face pe baza teoremei Berlekamp și Massay și este prezentat mai jos :

În orice câmp fie v0,v1, … ,v2t-1 iar A(x) și B(x) două polinoame. În condițiile inițiale , șirul următor de 2t iterații :

(2.119)

unde

(2.120)

La inițializare

(2.121)

La calculul discrepanței

(2.122)

3. MEMORIU JUSTIFICATIV

3.1 Codul BCH

Caracterizarea unui cuvânt de cod BCH se face prin lungimea blocului n și lungimea blocului de informație m.

Codarea

Din relația rezultă extensia câmpului Galois binar GF(2k). Deoarece programul este realizat pe caz particular (lungimea cuvântului de cod este egală cu 15) se va folosi câmpul Galois GF(24).

În funcție de n, m și extensia câmpului Galois se alege numărul de erori corectabile t și polinomul generator. În cazul în care codul este definit ca BCH(m,n) avem :

BCH(15,11) – codul poate corecta o eroare

BCH(15,7) – codul poate corecta două erori

BCH(15,5) – codul poate corecta trei erori

Se presupune cunoscut mesajul

Se calculează numărul caracterelor de control

unde k’=n-m

Cuvântul de cod se calculează cu formula

Decodarea

La recepție se face verificarea cuvântului de cod și corecția erorilor dacă acestea există. Verificarea se face cu ajutorul sindroamelor

Se calculează sindroamele cu formula

Daca sindroamele sunt zero atunci recepția cuvântului s-a facut fară erori sau nu s-a putut detecta eroarea

Se calculează coeficienții i din tabel din anexa

Se face cautarea pozițiilor eronate cu ajutorul algoritmului de căutare Chien după formula

Când unul dintre termeni este egal cu 1 atunci poziția ce o indică acel termen este cea eronată. Vectorul eroare va avea pe poziția respectivă valoarea 1 iar pe restul 0.

Cuvântul decodat va fi

3.1.1 Descrierea programului ce implementează codul BCH

Programul conține clasele: CAboutDlg, CBCHApp, CChildView, CCodare, CDecodare, CMainFrame, POLINOM.

Clasa CCodare

Este utilizată de dialogul (fereastra) de codare a unei secvențe informaționale. CCodare oferă posibilitatea de verificare a validității datelor introduse de către utilizator prin metoda OnCodeaza, care va activa variabila allOk (publică), folosită, la randul ei, la activarea codării efective în clasa apelantă.

Clasa CDecodare

Este utilizată de dialogul (fereastra) de decodare a unei secvențe recepționate.

CDecodare oferă posibilitatea de verificare a validității datelor introduse de către utilizator prin metoda OnDecodeaza, care va activa variabila allOk (publică), folosită, la randul ei, la activarea decodarii efective în clasa apelantă.

Clasa CChildView

Este clasa de afișare. Această clasă instanțiază dialogurile folosite pentru codare/decodare și, în funcție de variabilele de stare allOk, efectuează codarea, respectiv decodarea. Afișarea modală și preluarea parametrilor este facută cu metodele OnFunctiiCodarebch, respectiv OnFunctiiDecodarebch, metode care tratează mesajele generate la selecția modului de lucru (codare/decodare). Codarea și decodarea propriuzise se realizează tot cu ajutorul acestei clase, în interiorul metodei OnPaint.

Metoda OnFunctiiCodarebch

transfer inițial de parametri spre dialog;

apelul dialogului modal CCodare;

stabilește o variabilă de optiune – activarea codarii;

impune redesenarea view-ului;

Metoda OnFunctiiDecodarebch

transfer inițial de parametri spre dialog;

apelul dialogului modal CDecodare;

stabilește o variabilă de opțiune – activarea decodarii;

impune redesenarea view-ului;

Metoda OnPaint este metoda cu ajutorul căreia se face codarea și decodarea propriuzisă.

Codarea

Din dialogul de codare se preiau parametrii codului și datele introduse;

Se calculează polinomul generator în formă polinomială ;

Transformarea din octal în polinomial a polinomului generator se face prin apelarea metodei f_forma_polinom_oct;

Se afișează polinomul generator în formă polinomială și octală;

Se afișează secvența informațională i ;

Se realizează transformarea din formă binară în formă polinomială prin apelarea metodei f_forma _polinom_bin ;

Se afișează polinomul informațional i(x);

După realizarea acestor pași se trece la codarea efectivă:

Prin apelarea metodei f_mul_i_xk se realizează multiplicarea lui i(x) cu ;

Se afișează ;

Se apelează metoda f_impartire care va efectua operația ;

Se afișează restul împărțirii sub formă polinomială;

Se apelează motoda f_construire_v care va construi polinomul v(x) ;

Se afișează polinomul v(x);

Se afișează secvența codată și în binar;

Decodarea

Din dialogul de decodare se preiau parametrii codului și datele introduse;

Preluarea datelor se face în forma binară;

Transformarea din binar în polinomial a secvenței de decodat se face prin apelarea metodei f_forma_polinom_bin;

Se afișează secvența de date în formă polinomială și binară;

Prin metoda f_sindrom va realiza în pasul urmator calcului sindroamelor;

Se face afișarea sindroamelor;

Se vor calcula coeficienții polinomului erorilor, σ, cu ajutorul metodei f_calc_sigma;

Urmează căutarea Chien, într-o buclă repetitivă, prin apelul metodei f_chien, și corectarea informației eronate, dacă este cazul;

În cazul detecției unei erori se face afișarea poziției acesteia;

Se face afișarea informației decodate, cu corectarea eventualelor erori detectate.

În continuare vom prezenta diagrama UML corespunzătoare aplicatiei BCH.

Figura 3.1 Diagrama UML a aplicației BCH

3.1.2 Exemplu de codare si decodare folosind BCH

Fie un cod BCH (15,7). Din tabel se determină t = 2 iar g = 721. Deci n = 15, m = 7.

Se determină extensia câmpului binar GF(2k) din 2k = 15 +1, deci k = 4.

Polinomul generator în formă polinomiala va fi :

Pentru secvența informațională

cuvântul de cod va fi :

Deci în formă vectorială v se va scrie :

Presupunem că s-a recepționat vectorul :

Calculăm sindroamele :

Coeficienții i se calculează după formulele din tabelul 4 și se obține :

În continuare trecem la căutarea pozițiilor eronate cu ajutorul algoritmului de căutare Chien.

j =1

j =2

j =3

j =4

j =5

j =6

j =7

j =8

j =9

j =10

j =11

j =12

j =13

j =14

j =15

Se va face corecția cuvântului recepționat

De unde rezultă că cuvântul util transmis este

3.2 Codul Reed-Solomon

Codurile Reed-Solomon sunt coduri BCH în care biții sunt înlocuiți cu caractere.

Codarea

Din relația rezultă extensia câmpului Galois binar GF(2k). Deoarece programul este realizat pe caz particular (lungimea cuvântului de cod este egală cu 15) se va folosi câmpul Galois GF(24) și se calculează polinomul generator.

În cazul în care codul este definit ca RS(m,n) avem :

1. RS(15,13) – codul poate corecta o eroare

2. RS(15,11) – codul poate corecta două erori

3. RS(15,9) – codul poate corecta trei erori

RS(15,7) – codul poate corecta patru erori

RS(15,5) – codul poate corecta cinci erori

Se calculează caracterele de control conform relației

unde t este numărul de erori corectabile

Se alege o secvență informațională

Se calculează unde k’=2t

Cuvântul de cod se calculează cu formula

Decodarea

La recepție se face verificarea cuvântului de cod și corecția erorilor dacă acestea există.Verificarea se face cu ajutorul sindroamelor.

Se calculează sindroamele cu formula

Se calculează coeficienții i .

Se face cautarea pozițiilor eronate cu ajutorul algoritmului de căutare Chien după formula

Când unul dintre termeni este egal cu 1 atunci poziția ce o indică acel termen este cea eronată.

Vectorul eroare va avea pe poziția respectivă valoarea 1 iar pe restul 0

Se calculează valorile erorilor.

Se face corecția erorilor prin :

3.2.1 Descrierea aplicației ce implementează codul RS

În continuare vom descrie structura aplicației care implementează codurile ReedSolomon corectoare de 1,2,3,4 sau 5 erori.

Programul conține clasele: Clasa CcodeazaDlg, Clasa CdecodeazaDlg, Clasa CreedSolomonDoc, Clasa CreedSolomonView.

Clasa CCodeazaDlg

Această clasă este derivată din clasa CDialog și se ocupă cu afișarea și gestionarea ferestrei de dialog reprezentată de resursa IDD_CODARE.

Funcțiile principale ale clasei sunt:

Metoda OnInitDialog

Este apelată la inițializarea clasei

Realizează inițializarea variabilelor

Metoda OnSelchangeNrErori

Este apelată in momentul schimbării de numărului de erori

Reactualizează datelele despre cod afișate.

Metoda OnChangeSecventa

Este apelată la modificarea secvenței introduse de utilizator

Reactualizează datele despre secvența introdusă

Metoda OnCodeaza

Este apelată în momentul apăsării butonului IDC_CODEAZA.

Realizează verificarea apariției caracterelor ilegale în secvența introdusă și semnalizează necesitatea codării acesteia.

Metoda OnDecodare

Este apelată în momentul apasării butonului IDC_DECODARE.

Semnalizează necesitatea dezactivării ferestrei

Clasa CDecodeazaDlg

Această clasă este derivată din clasa CDialog și se ocupă cu afișarea și gestionarea ferestrei de dialog reprezentată de resursa IDD_DECODARE.

Funcțiile principale ale clasei sunt:

Metoda OnInitDialog

Este apelată la inițializarea clasei

Realizează inițializarea variabilelor

Metoda OnSelchangeNrErori

Este apelată in momentul schimbării de numărului de erori

Reactualizează datelele despre cod afișate.

Metoda OnChangeSecventaCodata

Este apelată la modificarea secvenței codate introduse de utilizator

Reactualizează datele despre secvența introdusă.

Metoda OnDecodeaza

Este apelată în momentul apăsării butonului IDC_DECODEAZA

Realizează verificarea apariției caracterelor ilegale în secvența introdusă și semnalizează necesitatea decodării acesteia.

Metoda OnDecodare

Este apelată în momentul apasării butonului IDC_CODARE

Semnalizează necesitatea dezactivării ferestrei

Clasa CReedSolomonDoc

Această clasă este derivată din clasa CDocument și conține toate variabilele și funcțiile matematice necesare codării/decodării.

Funcțiile clasei sunt:

Metoda ConstruiesteGF

Realizează generarea cămpului GF(24)

Metoda CosntruiestepPolGen

Construiește polinomul generator în funcție de numărul de erori selectat de utilizator

Meoda Suma, Dif, Inm, Imp, Putere

Relizează operațiile suma, diferență, înmulțire, împărțire, ridicare la putere cu elemente ale cămpului GF(24)

Metoda AddPol, DifPol, InmPol, ImpPol

Realizează operațiile suma, diferență, înmulțire, împărțire cu polinoame cu coeficienți în GF(24)

Metoda Grad

Găsește gradul unui polinom dintr-un vector de lungime dată

Metoda CalcValoare

Calculează rezultatul unei funcții pentru o valoare dată

Metoda CalcDeterminant

Calculează determinantul prin metoda permutărilor

Clasa CReedSolomonView

Această clasă este derivată din clasa CScrollView și se ocupă cu afișarea datelor în fereastra principală.

Metodele principale ale acestei clase sunt:

Metoda OnOptiuniCodeaza

Este apelată în momentul în care utilizatorul selectează opțiunea Codează din meniul Opțiuni sau apasă butonul ‘C’ sau butonul ‘Codare>> ’ din fereastra de dialog

Are rolul de a afișa fereastra de dialog IDD_CODARE si a ascunde fereastra de dialog IDD_DECODARE

Metoda OnOptiuniCodeaza

Este apelată în momentul în care utilizatorul selectează opțiunea Decodează din meniul Opțiuni sau apasă butonul ‘D’ sau butonul ‘Decodare >>’ din fereastra de dialog

Are rolul de a afișa fereastra de dialog IDD_DECODARE si a ascunde fereastra de dialog IDD_CODARE

Metoda OnSchimbareCodare

Este apelată în momentul în care utilizatorul face o schimbare a numărului erorilor în fereastra de codare

Realizează generarea elementelor câmpului GF(24) și a polinomului generator

Metoda OnSchimbareDecodare

Este apelată în momentul în care utilizatorul face o schimbare a numărului erorilor în fereastra de decodare

Realizează generarea elementelor câmpului GF(24) și a polinomului generator

Metoda OnDraw

Este apelată când datele afișate în fereastra principală trebuie reactualizate

Aici se face afișarea pașilor codării și decodării.

Metoda TransfPolInCar

Transformă un polinom cu coeficienți în GF(24) într-un șir de caractere care va fi afișat în fereastră

Metoda Codare

Realizează codarea Reed-Solomon

Metoda de codare este următoarea:

Se înmulțeste polinomul informațional cu polinomul

Se împarte polinomul obținut la polinomul generator

Restul obținut de la împarțirea anterioară se adună cu polinomul obținut la pasul 1

Rezultatul de la pasul trei este polinomul codat

Metoda Decodare

Realizează decodarea Reed-Solomon după algoritmul Peterson cu căutare Chien

Metoda de decodare este următoarea:

Se calculează sindromul erorii. Dacă acesta este nul rezultă că nu există erori, secvența decodată fiind primele m caractere din secvența codată. Dacă nu este nul se trece la pasul următor.

Se calculează sindroamele erorilor

Se calculează polinomul erorilor

Se calculează pozițiile erorilor

Se calculează valorile erorilor

Se adună la secvența recepționată valorile erorilor. Primele m caractere reprezintă secvența decodată

În continuare vom prezenta diagrama UML corespunzătoare aplicatiei ReedSolomon.

Figura 3.2 Diagrama UML a aplicației ReedSolomon

3.2.2 Exemplu de codare si decodare folosind Reed-Solomon

Fie un cod RS (15,11). Din tabel se determină t = 2 iar g =( 1e74b). Deci n = 15, m = 11.

Se determină extensia câmpului binar GF(2k) din 2k = 15 +1, deci k = 4.

Polinomul generator în formă polinomiala va fi :

Pentru secvența informațională

Se calculează unde k’=2*2 și se împarte la g(x) obținându-se :

Se împarte la g(x) și se obține câtul :

și restul :

În forma vectorială polinomială v se va scrie :

În forma vectorială v se va scrie :

Presupunem că s-a recepționat vectorul :

Calculăm sindromul , prin împărțirea lui r(x) la g(x) pentru a vedea dacă există erori :

Sindromul nu este nul de unde rezultă că există erori.

Se calculează sindroamele :

Coeficienții i se calculează după formulele din tabel și se obține :

În continuare trecem la căutarea pozițiilor eronate cu ajutorul algoritmului de căutare Chien. Pentru :

j =1

j =2

j =3

j =4

j =5

j =6

j =7

j =8

j =9

j =10

j =11

j =12

j =13

j =14

j =15

Se va face calculul valorii erorii valorile luându-se din tabelul din anexă:

Se va face corecția erorilor prin formula :

Iar secvența decodată este :

4. CAIET DE SARCINI

Acest capitol se ocupă de necesitățile hard și soft de instalare a aplicației.

Utlizatorul poate folosi programele atașate lucrării pentru a realiza codarea respectiv decodarea unor mesaje prin codare BCH cu BCH.exe sau Reed-Solomon cu ReedSolomon.exe

Pentru rularea corectă a acestor programe este necesar un calculator personal având minim următoarea configurație :

Intel 586

32 RAM

minim 20M spatiu necesar pe HDD

Programele se poate rula de sub platformele :

Win’95,Win’98,Win’ NT,Windows 2000 sau Windows XP.

Pentru a introduce elemente noi în program sau pentru a modifica structura acestuia este necesar mediul de programare Visual C++.

Modificările se vor face deschizând proiectele ReedSolomon.dsw sau BCH.dsw din programul VisualC++.

.

5. INSTRUCTIUNI DE EXPLOATARE ȘI ÎNTREȚINERE

Instrucțiuni de instalare și utilizare a aplicației BCH.exe

La rularea programului v-a apărea o fereastră prin care programul interoghează utilizatorul dacă dorește o operație de codare, respectiv decodare.Tot în această fereastră vor fi afișați pașii de codare(decodare). În continuare această fereastră o vom numi fereastră principală.

Prin alegerea unei opțiuni, din cele două, v-a apărea altă fereastră în care se introduc datele de codare, respectiv decodare.

Codarea

În fereastra de codare se oferă posibilitatea de a alege un cod BCH corector de 1,3 sau 3 erori, după care se alege o secvență informațională. Pentru ajutarea utilizatorului, în partea de jos a ferestrei este afișat numărul de caractere introduse. Dacă dorim, această secvență poate fi generată aleator.

Secvența se va introduce în binar.

După alegerea secvenței informaționale programul va afișa rezolvarea propriuzisă.

Figura 5.1 Fereastra principală împreună cu rezultatele unei codări

Polinomul generator va fi afișat atât în forma octală cât și în formă polinomială.

În cazul în care datele sunt introduse eronat programul va genera mesaj de eroare. Dacă nu sunt introduse numere binare va aparea o fereastră cu mesajul “Trebuie să introduceti date

binare!” iar dacă se va tasta un număr diferit de caractere va aparea o fereastră ce afișează numărul de caractere ce trebuie introdus.

Decodarea

În fereastra de decodare se oferă posibilitatea de decodare a secvenței codate anterior, alegerea unei secvențe de catre utilizator și de asemenea posibilitatea eronarii unor poziții la alegere.

Dacă la partea de codare s-a ales un cod BCH corector de o eroare sau două în momenul alegerii selectării operației de decodare se va selecta implicit aceiași variantă de cod.

Decodarea se va face pentru codul BCH corector de 1 sau 2 erori.

Figura 5.1 Fereastra principală împreună cu rezultatele unei decodări

Atât în cazul codarii cât și al decodarii dacă nu sunt date introduse și se activează butonul de codare/decodare programul va semnala mesaj de eroare.

5.2 Instrucțiuni de instalare și utilizare a aplicației ReedSolomon.exe

Programul urmărește prezentarea codului Reed-Solomon corector de 1,2,3,4 sau 5 erori erori. El este implementat sub mediul de programare Visual C++ și a fost implementat doar pentru studiu de laborator.

Se va copia executabilul ReedSolomon.exe și se va porni prin poziționarea pe el și apăsarea tastei <ENTER>, sau prin dublu click cu mouse-ul pe el..

La rularea programului v-a apărea o fereastră principală prin care programul interoghează utilizatorul dacă dorește o operație de codare, respectiv decodare.

Selectarea codării sau a decodării se poate face din meniul de opțiuni, pin alegerea unei variante “Codeaza” respectiv “Decodeza”, sau prin apăsarea butonului “C”sau a butonului “D”.

Tot în această fereastră principală vor fi afișați pașii de codare(decodare).

Prin alegerea unei opțiuni va apărea o altă fereastră care oferă posibilitatea introducerii datelor de codare, respectiv decodare. Prin “date de codare” se întelege caractere de la “0” până la “9” și de la “a” la “f”.

Pentru ajutarea utlizatorului s-a facut o coresponedență astfel încât:

caracterul “a” reprezintă numărul “10”

caracterul ”b” reprezintă numărul “11”

caracterul ”c” reprezintă numărul “12”

caracterul “d” reprezintă numărul “13”

caracterul “e” reprezintă numărul “14”

caracterul “f” reprezintă numărul “15”.

Din fereastra de codare se poate trece în fereastra de decodare prin apăsarea butonului “Decodare >>”. În același mod se poate trece din fereastra de decodare în fereastra de codare prin apăsarea butonului ”Codare >>”.Această trecere se poate face deasemenea cu ajutorul butoanelor “C”și “D” sau prin alegerea din meniul “Opțiuni”a variantei dorite.

Ieșirea din program se poate face din meniul “Opțiuni” alegând varianta “Iesire” sau apăsând butonul poziționat ân dreapta sus a programului.

Codarea

În fereastra de codare se oferă posibilitatea de a alege un cod Reed-Solomon corector de 2,3,4 sau 5 erori, după care se se va introduce o secvență informațională. Pentru ajutarea utilizatorului este afișat numarul de caractere introduse în paralel cu numărul de caractere care trebuie introduse. Tot în această fereastră se afișează, în funcție de numărul de erori care este ales de către utilizator, lungimea cuvantului de cod, numărul simbolurilor de informație R(n,m) și coeficienții polinomului generator.

Aceste date vor fi afișate în acest moment și în ferestra principală.

Figura 5.3 Fereastra principală împreună cu rezultatele unei codări

După alegerea secvenței informaționale programul va afișa rezolvarea propriuzisă. Afișarea se face în fereastra principală.

Secvența codată va fi afișată în fereastra secundară și va mai fi afișată în formă polinomială în fereastra principală .

În cazul în care se va introduce o secvență care nu are numărul de caractere corect nu se va activa butonul de codare “Codeaza”din fereastra secundară.

În cazul în care se va introduce o secvență ce conține caractere ilegale programul va semnala următorul mesaj de eroare “In secvență există caractere ilegale”.

Decodarea

În fereastra de decodare se va face alegerea unei secvențe de catre uitlizator (sau preluarea din fereastra de codare a datelor codate anterior) și de asemenea posibilitatea eronării unor poziții la alegere. Eronarea acestor poziții se face în funcție de numărul de erori corectabile ale codului. Pentru a nu genera date eronate nu se vor introduce un număr mai mare de erori decât este selectat de către utilizator.

Figura 5.1 Fereastra principală împreună cu rezultatele unei codări decodări

Secvența decodată va fi afișată atât în fereastra principală (în formă polinomială) cât și în fereastea de decodare.

Pașii decodării și ai corecției vor fi afișați în fereastra principală.

6. BIBLIOGRAFIE

Spataru Al. Teoria Transmiterii Informatiei; Editura Didactica si Pedagogica, Bucuresti – 1989

Creanga I., Simovici Teoria Codurilor; Editura Didactica si Pedagogica, Bucuresti – 1975

Angheloiu I. Teoria Codurilor; Editura Militara, Bucuresti – 1973

Borda M. Teoria Transmiterii Informatiei; Editura Dacia – 1999

Ionescu D. Codificare si Coduri; Editura Tehnica, Bucuresti –1987

D. Dan Alin Potorac Teoria Transmiterii Informatiei, Curs