Coduri Reed Muller. Erorile Canalului Discret Si Masuri de Protectie Impotriva Lor

CAPITOLUL 1

TEORIA INFORMAȚIEI.

MĂRIMI ȘI NOȚIUNI SPECIFICE TRANSMISIEI INFORMAȚIEI

Se cuvine să facem de la început o precizare privind natura zgomotelor care însoțesc transmisiile, acestea provenind într-un mod asemănător modului în care se generează semnalele utile. Din acest motiv este necesar să tratăm unitar perturbațiile și semnalele utile. Despre primele știm că dacă s-ar comporta într-un mod determinist, ar putea fi eliminate în mod integral. Evoluția lor este dictată de legi probabilistice. Acest caracter aleator este însă propriu și semnalul util, pentru că o evoluție deterministă a sa ar însemna cunoașterea sa la punctul de recepție și de aici ar decurge inutilitatea transmisiei. Tocmai caracterul aleator al evoluției semnalului util este responsabil de necesitatea transmisiei unei informații.

După cum se vede au fost introduse câteva noțiuni pe care le precizăm în continuare. Deoarece atât perturbația cât și semnalul util, au aceeași natură și uneori aceiași proveniență, ambele se pot considera ca fiind semnale, adică manifestări concrete fizice capabile să se propage printr-un mediu numit canal. Noțiunea de semnal este utilizată uneori restrâns, pentru a denumi semnalul util, acela care va spune ceva receptorului.

O formă particulară a semnalului, extrasă dintr-un ansamblu, constituie un mesaj, atunci când ansamblul urmează a se transimte unui corespondent.

Perturbația este un semnal care, în procesul de transmisie sau de prelucrare, modifică în mod aleator semnalul util.

O noțiune des utilizată este aceea de Informație. Ca să înțelegem această noțiune, să ne imaginăm un ansamblu de N mesaje diferite, fiecare mesaj fiind ales pentru transmisie în mod echiprobabil. Evident probabilitatea emisiei oricărui mesaj este 1/N. Atunci când se transmite un mesaj, adică se alege un anumit semnal

din ansablul de N mesaje, această concretizare, această realizare, dă informația. Informația este cu atât mai mare cu cât este mai imprevizibilă realizarea evenimentului constituit de transmiterea acelui semnal, deci cu cât este mai mică probabilitatea respectivului mesaj. Informația depinde deci de probabilitatea realizării unei anumite situații și prin definiție este:

,

în care i este informația, iar p este probabilitatea realizării evenimentului considerat.

Informația este generată de o sursă de informație, aceasta fiind un mecanism prin care se alege, din ansamblul de semnale, tocmai acela care se va transmite acum, această alegere fiind întâmplătoare și necunoscută celui care va primi semnalul. Destinatarul, corespondentul, este locul final unde trebuie să ajungă mesajul transmis, astfel ca să ducă informația.

Trecerea prin canal este însoțită de perturbații. Pentru diminuarea efectelor acestora, se utilizează diverse procedee de prelucrare a semnalelor, la intrare și la ieșire din canal. Aceste prelucrări sunt modulația/demodulația, codarea/decodarea. Modulația este constituită de transformările la care este supus un semnal, pentru a-l face să treacă printr-un canal, singur sau împreună cu altele de același gen. Demodularea este constituită de procesele inverse ce au loc la recepție, cu scopul obținerii unui semnal, cât mai asemănător celui emis de sursa de informație. Codarea este prelucrarea la care se supune semnalul pentru a i se mări eficiența transmiterii, în primul rând fiind vorba de semnale numerice. Decodarea este procesul invers codării, efectuat la recepție.

Eficiența transmisiei se estimează în telecomunicații printr-o comparație între semnalul emis, generat de sursa de informație și semnalul oferit de recepție utilizatorului. Se utilizează trei criterii de apreciere a fidelității transmisiei și anume: eroarea medie pătratică, raportul semnal/zgomot și probabilitatea deciziei false. Primul criteriu de fidelitate se scrie:

,

unde este eroarea, diferența dintre x(t), semnalul generat de sursă și y(t), semnalul oferit utilizatorului. Bara de deasupra simbolizează medierea în timp a mărimii. Evident o transmisie este cu atât mai bună, cu cât criteriul de fidelitate, eroarea medie pătratică, este mai mică. Cel de al doilea criteriu se scrie:

,

în care n(t) este zgomotul perturbator, care nu se mai separă de semnalul util, x(t). Conform acestui criteriu, un raport semnal/zgomot, mare, indică o transmisie de mare fidelitate. Al treilea criteriu, probabilitatea deciziei false, se referă la transmisiile numerice și exprimă probabilitatea de a se remite utilizatorului un cuvânt care de fapt nu a fost transmis, invertirea fiind făcută ca urmare a zgomotelor din canal. O transmisie de mare fidelitate înseamnă o mică probabilitate a deciziei false.

Acum putem desena o schemă de transmisie care să conțină elementele anunțate mai sus. Aici vedem sursa de informație S, modulatorul M, codorul C, canalul P, decodorul C’, demodulatorul M’ și utilizatorul U.

mesaj semnal perturbații semnal mesaj

Fig.1.1.

În schema din figura 1.1. se mai pot introduce elemente care să faciliteze transmisii multiple, a mai multor semnale prin același canal.

1.2. NEDETERMINARE ȘI INFORMAȚIE

Considerăm un ansamblu de mesaje din care urmează a executa transmisia, pe care o vom denumi experiment. Pe măsură ce se face transmisia, zicem că experimentul se realizează într-o formă sau alta, într-o concretizare sau alta. Înaintea realizării, deci înaintea transmisiei, neștiind care din mesaje se va scoate din ansamblul considerat, avem o incertitudine. Aceasta se va risipi imediat ce s-a executat alegerea mesajului. Incertitudinea, sau nedeterminarea, existentă înaintea realizării aleatoare a unui eveniment, este funcție de acel eveniment, mai precis este funcție de probabilitatea lui apriori. Odată cu înlăturarea incertitudinii, obținem o informație despre ansamblul din care s-a extras mesajul. Cele două mărimi, informația obținută și nedeterminarea anterioară, sunt echivalente.

Considerăm mesajul emis (t), unul din mai multe posibile a fi omise, precum și probabilitatea sa de a fi selectat la emisie, p(xi). Inceritudinea inițială, înainte de emisie, este funcția F(p(xi)), egală cu informația i(xi) adusă de apariția mesajului (t). La trecerea prin canal, semnalul(t) se alterează și la recepție sosește (t),

dependent de (t). În urma observării semnalului (t), dispare o parte din incertitudinea existentă înainte de observarea lui (t), astfel încât nedeterminarea aposteriori, de după observare, F(p(/)), este, de regulă, mai mică decât nedeterminarea apriori asupra lui (t). Nedeterminarea aposteriori este aceeași funcție de F de probabilitatea mesajului (t), condiționată însă de realizarea concretă în forma (t). Cantitatea de incertitudine dispărută în urma observării semnalului (t), este egală cu cantitatea de informație adusă de (t) despre (t). Deci:

,

Funcția F(.), prin care se exprimă incertitudinea, poate fi de mai multe feluri. Este necesar să atribuim acestei funcțiicalitatea de aditivitate, în cazul în care mesajul considerat este o succesiune de două sau mai multe semnale elementare,

,

între care se stabilește o relație de intersecție, mesajul necesitând prezența atât a lui, cât și a lui. Evident, probabilitatea mesajului va fi:

,

ceea ce implică următoarea expresie pentru funcția F de incertitudine:

.

Dorim ca această incertitudine să fie o sumă de incertitudini parțiale, fiecare dependență de semnalul elementar corespunzător, adică:

,

de aici decurge funcția logaritm care satisface relația de mai sus. În consecință:

.

Baza logaritmilor prezintă interes puțin, fiind necesar să fie aceiași în calculele comparative. În teoria transmisiunii informației se lucrează cu logaritmi în baza 2.

Utilizând ultima relație, cantitatea de informație obținută asupra lui, prin observarea semnalului, devine:

și se poate calcula cunoscând probabilitatea aposteriori a evenimentului, condiționat de recepționarea semnalului .

1.3. SURSE DE INFORMAȚIE

O sursă de informație este un mecanism matematic sau tehnic care poate alege și emite un mesaj dintr-un ansamblu de mesaje posibile, alegerea făcându-se aleator. Sursa de informație se caracterizează prin setul de mesaje posibil a fi selectate, denumite simboluri sau litere, ansamblul fiind în acest ultim caz denumit alfabet. Sursa se mai caracterizează printr-un al doilea set de mărimi, care reprezintă statistic sursa, fiind înșiruirea probabilităților cu care se emite fiecare simbol

.

Aici cu am notat simbolul al i-lea și cu probabilitatea ca acest simbol să se emită. Evident există egalitatea:

,

în care ν este indicele ultimului simbol, adică numărul de litere din alfabetul sursei.

O înșiruire de mai multe simboluri constituie un cuvânt sau caracter, iar totalitatea cuvintelor formează o limbă, în care sursa poate emite.

Dacă probabilitatea de emisie a unui simbol, nu depinde în nici un fel de literele anterior emise, zicem că sursa este fără memorie. Dacă există o asemenea dependență, atunci sursa este cu memorie.

Dacă unele simboluri se pot emite numai dacă anterior s-a emis un anumit simbol, zicem că sursa are constrângeri fixe. Sursa care debitează în cod Morse este o sursă cu constrângeri fixe, deoarece pauza dintre literele alfabetului se poate genera, numai dacă anterior s-a generat un punct sau o linie. O asemenea pauză nu

se generează după o altă pauză. Dacă constrângerile sunt aleatorii, sursa devine cu memorie.

Sursa staționară este acea sursă la care originea timpului nu influențează setul de probabilități care o definesc. O categorie deosebită de sursă este sursa ergodică, aceasta fiind sursa care generează numai șiruri tipice. Noțiunea de șir tipic se înțelege, dacă vom considera că sursa emite succesiuni lungi, fiecare de câte n simboluri. Fie componența unui asemenea șir următoarea: simboluri , simboluri , simboluri … simboluri … . Evident Dacă este probabilitatea de a se genera simbolul , atunci un șir de n simboluri este tipic dacă:

ceea ce înseamnă că frecvența oricărui simbol în șirul tipic emis, , tinde spre probabilitatea simbolului respectiv, atunci când n tinde la infinit.

La aceleași valori ale probabilităților se ajunge, dacă se consideră funcționarea simultană a n surse cu caracteristici identice și dacă se observă starea acestui ansamblu de surse la un moment dat. Din acest n surse, vor emite, în momentul analizei, simbolul . Acceptând ipoteza de ergidicitate, înseamnă a pune semnul egal între probabilitățile simbolurilor emise de un ansamblu mare de surse, observate la un moment dat (probabilități scoase dintr-un ansamblu statistic) și probabilitățile acelorași simboluri obținute de oricare sursă la o funcționare de durată (probabilități scoase din funcționarea temporară). O primă și deosebit de utilă consecință a ergodicității, este aceea că medierile statistice, făcute pentru un ansamblu mare de procese întâmplătoare, sunt egale cu medierile temporare, făcute pentru o singură funcționare de lungă durată, deoarece putem dispune de o realizare concretă a unui proces, dar nu vom avea niciodată un ansamblu mare de procese similare pe care să le putem studia.

Sursele de informație întâlnite în tehnică se bucură de proprietatea de ergodicitate.

În funcționarea de lungă durată, informația adusă de manifestarea simbolului va fi:

,

iar valoarea medie pe ansamblu a acestei informații, denumită informație medie pe simbol, sau

entropia sursei, va fi:

.

Valoarea maximă a acestei mărimi se obține dacă probabilitățile simbolurilor sunt egale. La un set oarecare de probabilități, diferite unele de altele, sursa emite o informație medie pe simbol mai mică, conținând ceea ce se numește redundanță.

.

Funcționarea unei surse se face în timp, fiecare simbol fiind prezent la ieșirea din sursă un interval de timp τ. Legat de acest proces, definim debitul de informație al sursei, drept raport între entropia sursei și durata emisiei unui simbol.

O sursă deosebit de simplă este sursa binară, ale cărei simboluri se consebit de utilă consecință a ergodicității, este aceea că medierile statistice, făcute pentru un ansamblu mare de procese întâmplătoare, sunt egale cu medierile temporare, făcute pentru o singură funcționare de lungă durată, deoarece putem dispune de o realizare concretă a unui proces, dar nu vom avea niciodată un ansamblu mare de procese similare pe care să le putem studia.

Sursele de informație întâlnite în tehnică se bucură de proprietatea de ergodicitate.

În funcționarea de lungă durată, informația adusă de manifestarea simbolului va fi:

,

iar valoarea medie pe ansamblu a acestei informații, denumită informație medie pe simbol, sau

entropia sursei, va fi:

.

Valoarea maximă a acestei mărimi se obține dacă probabilitățile simbolurilor sunt egale. La un set oarecare de probabilități, diferite unele de altele, sursa emite o informație medie pe simbol mai mică, conținând ceea ce se numește redundanță.

.

Funcționarea unei surse se face în timp, fiecare simbol fiind prezent la ieșirea din sursă un interval de timp τ. Legat de acest proces, definim debitul de informație al sursei, drept raport între entropia sursei și durata emisiei unui simbol.

O sursă deosebit de simplă este sursa binară, ale cărei simboluri se consideră a fi 0 respectiv 1, iar statistica sa este precizată prin p(0)=i-p(i), probabilitatea de apariție a unuia din cele două simboluri.

Entropia acestei surse este:

,

și depinde de p conform graficului din figura 1.2.

Pentru valorile p=0 sau p=1, ceea ce înseamnă emisia certă a unui simbol, generată de sursă, este nulă, deoarece nu este nici o nedeterminare înainte de apariția acelui simbol, despre care știm că va apare și deci nu ne elimină nici o incertitudine. Valoarea maximă a entropiei se obține pentru p=0,5, când cele două simboluri sunt echiprobabile și este egală cu –log 0,5. Se vede că luând baza logaritmilor 2, această valoare maximă a entropiei sursei binare, este egală cu unu și este acceptată drept unitate de informație, purtând denumirea de bit.

CANALE

Canalul este mediul prin care se transmite mesajul de la emițător la utilizator. Dacă mesajele trecute prin canal sunt discrete, canalul se numește discret.

Un canal se caracterizează prin următoarele mărimi:

Alfabetul de intrare, X, care este constituit din totalitatea simbolurilor ce pot fi aduse la intrarea în canal și pe care acesta le acceptă, notate generic ;

Alfabetul de ieșire, Y, constituit din totalitatea simbolurilor ce se obțin la ieșirea din canal, notate generic . În general cele două alfabete nu sunt identice, putând avea simboluri comune;

Matricea de transfer, sau matricea probabilităților condiționate ale câmpului de la ieșire de câmpul de la intrare, care arată statistica transformării semnalelor de la intrare în semnalele de la ieșire și notate generic .

Cunoscând aceste elemente, se deduc mai multe mărimi, prin care se poate face o evaluare a canalului, a performanțelor sale, a transferului informației de la intrare spre ieșire.

Probabilități și entropii în canal

Vom scrie probabilitățile sursei care debitează în canal, sub forma unei matrice linie:

,

admițând că alfabetul de intrare al canalului este , având deci n litere.

În mod asemănător vom scrie probabilitățile simbolurilor de la ieșire, sub forma unei matrice linie:

,

admițând că alfabetul de ieșire este , având deci m litere.

Vom scrie probabilitățile de apariție a simbolurilor de ieșire condiționate de simbolurile de intrare, sub forma unei matrici dreptunghiulare cu n linii și m coloane de forma:

.

Matricea de probabilități [P(Y/X)] se obține cu relația:

[P(Y)]=[P(X)][P(Y/X)],

fiind deci dependentă de caracteristica canalului, [P(Y/X)] și de modul în care este utilizat canalul de către sursa de informație, [P(X)].

În urma realizării unui anumit simbol la ieșire, spre exemplu, având setul de probabilități caracteristic alfabetului de la intrare, se pot calcula toate probabilitățile aposteriori ale semnalelor de la intrare condiționate de semnalul de la ieșire, utilizând formula lui Bayes:

.

Acest calcul se poate face pentru orice semnal de la ieșire, astfel încât se va putea scrie matricea [P(X/Y)] a probabilităților simbolurilor de intrare, aposteriori condiționate de ieșire, sub forma unei matrice dreptunghiulare cu m linii și n coloane:

.

Această matrice este obținută prin calcul, spre deosebire de matricea [P(Y/X)] care se poate obține experimental.

Cele patru matrice de probabilități prin care am descris statistic canalul, vor da naștere la entropii. Matricea de probabilități [P(X)] dă naștere entropiei H(X) a câmpului de la intrare conform relației:

.

Matricea de probabilități [P(Y)] determină entropia câmpului de la ieșire, H(Y):

.

Cunoscând semnalele de la ieșirea din canal, nu putem afirma, datorită probabilităților din canal, că s-a anulat incertitudinea asupra semnalelor de la intrare. Rămâne o incertitudine, o nedeterminare și după ce s-a recepționat semnalul la ieșirea din canal. Valoarea medie a acestei incertitudini, luată peste întreg câmpul de la ieșire și pentru întreg câmpul de la intrare, se numește echivocație, fiind o măsură a echivocului ce mai există asupra câmpului de la intrare, când se cunoaște câmpul de la ieșire. Se notează cu H(X/Y) fiind o entropie condiționată și se calculează cu relația:

.

Sau, ținând cont că produsul a două probailități este probabilitatea ansamblului celor două variabile:

.

Cunoscând semnalele de la intrare, adică statistica sursei, [P(X)], nu putem cunoaște cu certitudine câmpul de la ieșire, din cauza probabilităților din canal. Vom rămâne totdeauna cu o incertitudine care ne dă ceea ce se numește eroarea mediei a canalului, aceasta fiind deci o măsură a nedeterminării câmpului de la ieșire când se cunoaște câmpul de la intrare. Este o entropie condiționată și se calculează cu relația:

sau

.

Dacă zgomotele sunt nule, atât eroarea medie cât și echivocația sunt nule. Urmărind intrarea în canal, putem spune cu certitudine ce iese din canal și invers, supraveghind ieșirea, vom ști cert care a fost semnalul introdus. Anularea celor două entropii condiționate, H(Y/X) și H(X/Y) se datorează probabilitățior care au, sau valoare 1 sau valoare 0. Din același motiv H(X)=H(Y).

Dacă canalul este dominat de zgomote foarte puternice, astfel încât probabilitățile semnalelor de la ieșire nu mai depind de cele de la intrare, devenind deci independente, adică:

respectiv ,

atunci se va obține:

H(Y/X)=H(Y) și H(X/Y)=H(X),

ceea ce înseamnă că, eroarea medie pe care o facem în estimarea ieșirii, este egală cu incertitudinea ieșirii, deci nu știm nimic despre ieșire când observăm intrarea, respectiv echivocația pe care o avem observând ieșirea, este tot atât de mare, cât incertitudinea intrării, ceea ce înseamnă că nu știm nimic despre intrare.

În cazul real, când zgomotele există, dar nu sunt atât de puternice, încât din canalul recepționat să nu se poată deduce nimic asupra semnalului de la intrare, entropiile condiționate vor avea valori intermediare celor două situații extreme, ceea ce se scrie:

0≤H(X/Y)≤H(X) respectiv 0≤H(Y/X)≤H(Y).

Transinformația

Dacă analizăm o pereche de simboluri oarecare, unul fiind prezent la intrare, iar celălalt la ieșire, , vom obține cu ajutorul lui o informație asupra lui , egală cu . Din cauza zgomotelor din canal informația proprie, , este mai mare decât informația mutuală, , ceea ce înseamnă că informația adusă de despre , nu are valoarea maximă posibilă, fiind diferența celor două mărimi de mai sus. Mediind pentru toate perechile de variabile posibile, se obține informația trecută prin canal. Adică:

.

Ultima relație se mai poate scrie:

.

Se poate observa că, scoțând în afara sumei, executate după j, atât pe p() cât și logaritmul său, se obține în prima sumă dublă entropia H(X). A doua sumă, este echivocația cu semn minus. În consecință:

I(X;Y)=H(X)-H(X/Y),

Adică transformația este diferența dintre entropia sursei care debitează în canal și echivocația.

Vom introduce formula lui Bayes pentru și vom obține:

,

ceea ce se mai poate scrie:

.

În relația de mai sus, prima sumă dublă este H(Y), obținută ușor dacă se trece în afara sumei pe domeniul i probabilitatea p() și logaritmul său. A doua dublă sumă, este eroarea medie cu semnul minus. În consecință:

I(X;Y)=H(Y)-H(Y/X).

Despre transinformație putem deci afirma că este nedeterminarea ansamblului de la intrare minus echivocul asupra acestui ansamblu atunci când se cunoaște ieșirea, altfel spus este diferența dintre nedeterminarea inițială a intrării și nedeterminarea rămasă asupra intrării, când se cunoaște ieșirea. Aceeași transformație, conform relației de mai sus este diferența dintre nedeterminarea inițială a ieșirii și nedeterminarea rămasă asupra ieșirii cînd am urmărit intrarea. Informația va crește dacă echivocația scade, adică dacă eroarea medie scade, ceea ce se întâmlă când canalul are zgomote slabe. În cazul absenței acestora, deoarece probabilitățile devin unele egale cu 1 și altele egale cu 0, H(X/Y) devine nulă, ca și H(Y/X), iar informația obține valoarea maximă, egală cu nedeterminarea sursei H(X).

Valoarea minimă a informației este obținută atunci când sunt zgomote atât de puternice, încât probabilitățile condiționate , devin necondiționate și deci entropiile condiționate devin egale cu cele necondiționate.

H(X/Y)=H(X) ; H(Y/X)=H(Y).

În acest caz rezultă că informația este nulă, adică din observarea ieșirii nu putem deduce nimic asupra utilizării intrării.

Concluzia ce se poate trage este deci că informația trecută prin canal, atunci când se consideră variabil canalul cu parametrii săi de transfer, are o valoare cuprinsă între zero și entropia sursei.

Capacitatea canalului

Ne propunem să apreciem valoarea maximă a informației, de data aceasta nu prin variația parametrilor canalului, ci prin variația modului de utilizare a acestuia de către sursa de informație. Valoarea maximă astfel obținută, va fi dependentă de parametrii canalului și numai de aceștia și poartă denumirea de capacitate a canalului. Calculul informației maxime se face ușor doar pentru canalul în parametrii căruia sunt anumite simetrii. Orice canal funcționează la capacitatea sa, dacă sursa de informație, care debitează în canal, este caracterizată de un anumit set de probabilități. Dacă canalul nu funcționează la capacitatea sa, apare o redundanță, definită ca diferența dintre capacitatea canalului și transinformația:

.

Un canal deosebit de simplu este canalul binar simetric care are matricea de transfer:

,

dependentă de o singură probabilitate p. Se vede că un canal binar simetric are alfabetul de intrare, ca și pe cel de ieșire, compus doar din două simboluri, iar probabilitățile condiționate situate pe cele două linii sunt aceleași.

Pentru acest canal, care are dublă simetrie, mai întâi pe orice linie se găsește set de probabilități și apoi pe orice coloană se găsește același set de probabilități, se poate calcula capacitatea. Observăm mai întâi că eroarea medie se scrie, desfășurând sumele:

=>

=>

și considerând:

;

se va obține:

.

Din această relație rezultă că eroarea medie este independentă de modul de utilizare al canalului, de probabilitățile P(X). În acest caz, transinformația dată conform relației :

I(X;Y)=H(Y)-H(Y/X),

va avea un maxim dacă H(Y) are valoare maximă. Entropia ieșirii va fi maximă și egală cu 1 bit, atunci când . În consecință capacitatea, , a canalului binar simetric va fi:

= .

Se poate demonstra că informația trecută prin canal atinge capacitatea acestuia, dacă sursa care debitează în canal are probabilități egale.

Din această ultimă relație se vede că capacitatea canalului binar simetric este dependentă numai de zgomotul p din canal. Această dependență este prezentată în figura 1.3. Dacă p=0,5, ceea ce înseamnă că la orice semnal intrat în canal, se obține echiprobabil orice simbol de ieșire, capacitatea canalului este nulă, prin aceasta ne mai trecând nici un fel de informație. Faptul acesta se datoreză independenței semnalului de ieșire de cel de intrare căci, dacă p=0,5 :

,

ceea ce înseamnă că ieșirea, independentă de intrare, nu ne poate spune nimic despre intrare.

1.5. CODURI

Ne punem problema transportului informației unei surse de informație printr-un canal și constatăm că în general, alfabetul sursei nu este identic cu alfabetul de la intrarea canalului. Această neadaptare face imposibilă conectarea sursei direct la canal. Este nevoie de o conversie a sursei, într-un mod care să o facă acceptată de canal.

Vom intercala între sursă și canal un convertor, cu scopul de a transforma orice simbol generat de sursă, într-o succesiune de simboluri acceptate de canal. Acest convertor se numește cod, procesul se numește codare și reprezintă o funcție definită pe mulțimea simbolurilor sursei de informație cu valori în mulțimea cuvintelor codului, .

Acceptăm în codarea descrisă, că fiecărui simbol din sursă îi corespunde o succesiune de simboluri de la ieșirea codului și că nu sunt două sau mai multe simboluri din sursă, cărora să le corespundă o aceeași succesiune de cod. Cu alte cuvinte funcția este injectivă. În caz contrar nu se va putea recunoaște în cuvântul codului simbolul codat, ceea ce ar face imposibil procesul invers, la ieșirea din canal.

O a doua misiune a procesului de codare, este aceea de a transforma sursa de informație primară, cu redundanță mare, într-o sursă cu redundanță mai mică.

Deoarece canalele cele mai simple sunt și cele mai frecvente și ele sunt binare, în cele ce urmează ne vom preocupa de codurile binare, care transformă orice simbol al sursei într-un șir de simboluri binare.

Dacă un cod satisface condiția ca, oricărei succesiuni de simboluri din sursă să-i corespundă o sucesiune diferită de cuvinte de cod, atunci codul se numește unic decodabil.

Dacă un cod este unic decodabil și nu are nevoie, pentru conversie inversă, decât de prezența cuvântului de cod, fără să mai fie necesară o parte din următorul cuvânt de cod, codul se numește instantaneu. Codul binar cu cuvintele 10; 100; 1000; nu este instantaneu, deși are cuvinte unic decodabile, deoarece, după sosirea la recepție a simbolurilor 10, nu se poate decoda, deoarece nu știm dacă va sosi 1, ceea ce înseamnă că 10 este un cuvânt, sau va sosi 0, ceea ce înseamnă că 10 nu

este decât începutul, prefixul cuvântului. De aici decurge condiția: prefixele cuvintelor de cod să nu fie cuvinte de cod. Codul 01; 001; 001 este instantaneu, nici un cuvânt de cod nefiind prefixul altui cuvânt de cod. Codurile instantanee se mai numesc și ireductibile.

Eficiența codării

În procesul de codare, fiecărui simbol al sursei îi corespunde un cuvânt de cod. Procedeul de codare care indică corespondența ce se face între mulțimea și mulțimea poate fi realizat în mai multe feluri, utilizând aceleași simboluri ale codului. Va fi deci interesantă o analiză a procedeelor de codare, care să ne permită o alegere după un criteriu de optimizare. Vom accepta drept criteriu, costul transmisiei, pe care-l dorim minim, ceea ce înseamnă un minim pentru durata de transmisie, deci un minim pentru numărul de simboluri introduse în canal.

Pentru a face această apreciere, definim lungimea unui cuvânt de cod, , drept numărul simbolurilor de cod care compun. Dacă este probailitatea emisiei simbolului, , atunci:

,

este lungimea medie a cuvintelor de cod, rezultată ca mediere a lungimilor , acestea având aceleași probabilități ca și simbolurile sursei cărora le sunt atașate cuvintele de cod .

Costul transmisiei va fi proporțional cu L și deci minimizarea acestei mărimi se va urmări în continuare. Informația medie pe simbol a sursei este egală cu informația medie pe cuvânt de cod :

,

deoarece și au aceleași probabilități.

Informația medie pe simbol a codului este:

,

unde s-a presupus un cod binar.

Deoarece L simboluri de cod componente ale cuvântului de cod vor avea o informație de L ori mai mare decât informația medie pe simbol a codului, rezultă că informația medie pe simbol a sursei de informație, este de L ori mai mare decât informația medie pe simbol a codului:

H(S)=LH(X).

Valoarea medie a entropiei H(X) este log 2 și se obține în cazul în care simbolurile și sunt echiprobabile. Se poate deci scrie:

≥.

Relația de mai sus arată că lungimea medie a cuvintelor de cod nu poate fi mai mică decât entropia sursei raportată la log 2. Dacă baza logaritmilor este 2, atunci această ultimă relație se va scrie:

L≥.

Eficiența codării se va aprecia pe baza lungimii medii L, în comparație cu entropia sursei H(S).

.

Codurile care au eficiența egală cu unitatea se numesc absolut optimale. Pentru astfel de coduri, entropia simbolurilor de cod este maximă (egală cu 1 bit pentru codul binar). În acest caz . Probabilitatea unui cuvânt de cod, atunci când și sunt independente, va fi:

,

deoarece cuvântul de cod este intersecșia a simboluri de cod, fiecare cu probabilitatea . Însumând pentru toate valorile lui i se obține:

.

Această ultimă relație, necesară pentru ca un cod să fie absolut optimal, nu este suficientă, deoarece nu se referă decât la lungimea cuvintelor de cod și nu la conținutul lor. Relația ne arată doar că cu acele simboluri de cod și cu acele lungimi se poate construi un cod absolut optim.

Se pune întrebarea dacă putem atinge valoarea maximă a eficienței și în ce condiții. La această întrebare răspunde prima teoremă a lui Shannon sau, așa cum este cunoscută în literatură, teorema codării canalelor fără zgomot, denumire derivată din scopul urmărit și anume acela de a coda sursa de informație, pentru a putea traversa neinfluențate de zgomot. Ca să ajungem la această teoremă ne întoarcem la relația:

,

și o rescriem ținând cont că este un număr întreg și că, în general, nu este o putere întreagă a lui doi. În acest caz, real va fi cu ceva mai mare decât acela care rezultă din relația de mai sus, această depășire constituind redundanța. Depășirea nu va fi mai mare ca i, adică:

≤ <.

Amplificăm cu și însumăm pentru toate valorile lui i obținând:

≤<

H(S)≤L≤H(S)+i.

Această ultimă relație ne arată că lungimea medie a cuvintelor de cod este limitată inferior la entropia sursei H(S). Ne arată acum că se poate considera ca limită superioară a acestei lungimi medii, evident pentru coduri binare, valoarea entropiei sursei plus un bit.

Considerând extensia sursei S, adică o sursă care debitează succesiuni de t simboluri din sursa S, constatăm că informația medie pe succesiune, dacă H(S) este informația medie pe simbolul sursei S, va fi tH(S), de t ori mai mare. Dacă vom

coda fiecare succesiune posibilă cu un cod binar, vom obține cuvinte de cod a căror lungime medie va fi ; pentru acest vom putea rescrie relația :

H(S)≤L≤H(S)+i

ținând cont de valoarea entropiei sursei extinse:

tH(S)≤≤tH(S)+i.

Divizăm cu t și facem ca t să crească nelimitat și găsim:

H(S)≤ < .

Pentru t mare, se vede că:

=H(S) sau =tH(S).

Deoarece un simbol din sursa S poartă în medie H(S) biți de informație, rezultă că t simboluri vor avea tH(S) biți, codabili cu un cuvânt de lungime medie egală cu simboluri binare. Eficiența codării se va calcula cu relația:

,

punând la numărător informația medie pe succesiunea de simboluri din sursa S, adică tH(S) și la numitor lungimea cu care se codează succesiunea, , obținându-se evident unu, aceasta constituind prima teoremă a lui Shannon, care se anunță astfel:

O codare (binară) se poate face cu eficiență maximă egală cu unitatea, dacă se supune codării extensia de ordin mare a sursei de informație.

Metode de codare binară

Fie sursa S cu simbolurile și probabilitățile {}, cu . O vom coda cu un cod binar constituit din simbolurile 1 și 0. Împărțim sursa S în două mulțimi, respectiv , fiecare cuprinzând un număr de simboluri din cele n ale sursei S, astfel ca suma probabilităților simbolurilor din mulțimea să fie egală cu suma probabilităților din mulțimea . Evident există egalitatea:

.

Se divide iarăși, în câte două submulțimi, atât mulțimea cât și mulțimea , obținându-se submulțimile , , ,, în fiecare din ele intrând simboluri a căror probabilitate, însumată în domeniul submulțimii respective, satisface egalitatea:

.

În continuare se procedează similar împărțind submulțimile în două submulțimi de probabilitate egală, până când în ultima divizare a rămas un singur simbol. Se observă că fiecare submulțime are suma probabilitaților simbolurilor componente egală cu o putere a lui 2. Puterea este egală cu numărul indicilor submulțimii luat cu semn schimbat. Submulțimea care conține un singur simbol ( cu probabilitatea ) are un număr de indici și deci:

.

Însumând relația de mai sus, prntru domeniul de variație a lui i, se obține:

,

adică tocmai egalitatea obținută anterior. De aici rezultă că reprezintă lungimile unui cod instantaneu absolut optimal.

Din felul în care s-a determinat , prin divizarea în submulțimi de egală probabilitate, decurge metoda de codare binară. Pentru ilustrare se prezintă în tabelul T.1.2 o codare binară Shannon-Fano iar în figura 1.4. graful arborescent corespunzător. Sursa are 13 simboluri și o entropie:

bit / simbol.

Dacă sursa de maximă entropie, ar avea:

bit / simbol.

Lungimea medie a cuvintelor de cod este:

simbol binar / simbol sursă.

și probabilitățile , aceste probabilități fiind ordonate în sens necrescător, adică . Sursa care conține simbolurile , cu Se vede că lungimea medie a cuvintelor de cod este egală cu entropia sursei, deci eficiența codării este maximă, egală cu 1. Calculăm entropia simbolurilor de cod, H(X), pentru care ne vor fi necesare p(0) și p(1).

Fie numărul de zerouri din cuvântul de cod aferent simbolului și numărul de unuri din același cuvânt de cod. Evident . Probabilitatea emiterii unui zero, ca urmare a codării, va fi:

.

Probabilitatea emiterii unui unu va fi:

.

Considerând probabilitățile condiționate și rezultă că și . Numitorul probabilităților de mai sus este lungimea medie L. În consecință:

.

Pentru cazul concret al codului construit se obține:

[

],

confirmând astfel calitatea absolută optimală a codării. Prin codare, sursa primară cu eficiența:

,

a fost transformată în sursa secundară, cu simbolurile 0 și 1, de eficiență maximă.

În cazurile practice nu totdeauna este posibil a se împărți simbolurile sursei în două grupe de egală probabilitate. Metoda de codare Shannon-Fano se poate folosi, cu observația că codul obținut este instantaneu, dar nu și absolut optimal. Aplicăm metoda Shannon-Fano divizând sursa în două submultimi de probabilități cât mai apropiate. Divizarea următoare se face de asemenea în submulțimi de probabilitate apropiată. În fiecare divizare se atribuie unei mulțimi simbolul 0 și celeilalte mulțimi simbolul 1. Când s-a terminat divizarea, obținându-se în ultima diviziune un unic simbol, codarea este terminată, cuvântul de cod, pentru un simbol, fiind succesiunea indicilor subsursei care-l conține.

Codarea optimală presupune găsirea codului cu lungimea medie a cuvintelor, cea mai mică pentru sursa dată. Metoda Shannon-Fano permite obținerea unui cod instantaneu absolut optimal, dar numai pentru cazul cu totul particular când probabilitatea fiecărui simbol al sursei se poate exprima printr-o putere întreagă a lui i / 2. În realitate se găsesc multe cazuri în care această cerință nu este realizată și deci metoda nu se poate aplica.

Observând un cod optimal, se pot anunța următoarele proprietăți ale lui:

Cuvintele scurte din cod sunt atașate simbolurilor cu probabilitățile cele mai mari și invers. Această proprietate se scrie în forma a două șiruri de numere care se condiționează reciproc:

Într-un cod optimal, lungimile cuvintelor de cod corespunzătoare celor două simboluri care au cele mai mici probabilități sunt egale.

Utilizând cele două proprietăți ale codurilor binare optimale, în 1959 Huffman prezintă o metodă de sinteză a codurilor binare oprimale. Pentru expunerea metodei, anunțăm inițial modul de realizare a unei surse reduse.

Fie sursa S cu simbolurile probabilitățile este prima reducție a sursei S, obținută din S, prin înlocuirea ultimelor două simboluri, cu un alt simbol, care are probabilitatea egală cu suma probabilităților ultimelor două simboluri din sursa originală S.

Simbolurile sursei reduse pot fi acum ordonate în sensul necrescător al probabilităților simbolurilor. Înlocuind ultimele două simboluri, cu un simbol având probabilitatea egală cu suma probabilităților celor două simboluri înlocuite, se poate obține a două reducție, , a sursei originale S. În continuare se poate repeta operația de reducere până se obține o reducție care conține numai două simboluri. În tabelul T.1.3. se prezintă o sursă originală S cu 7 simboluri și reducțiile ce se pot construi.

Pentru ultima reducție care conține două simboluri, se poate ușor preciza codul binar, acesta având cuvintele și , oricare soluție fiind un cod unic decodabil.

Codul binar pentru penultima reducție, se obține păstrând cuvântul de cod pentru simbolul comun reducției ultime și penultime și construind două cuvinte de cod pentru cele două simboluri care au fost reunite în ultima reducție. Făcând uz de proprietatea a 2-a a codurilor binare optimale, cele două cuvinte de cod, construite pentru penultima reducție, vor avea aceeași lungime și vor fi diferite prin ultimul simbol, ceea ce înseamnă că se pot construi adăugând 0 respectiv 1 simbolului din ultima reducție. În acest fel un cuvânt de cod din ultima reducție, s-a descompus în două cuvinte de cod în penultima reducție. În mod asemănător se continuă până la sursa originală, mergând din reducție în reducție. Codul obținut în acest mod este un cod instantaneu și optimal.

Pentru o aceeași sursă S se pot construi mai multe coduri, dacă în procesul de obținere a reducțiilor sursei S se pot considera mai multe variante de creare a reducțiilor, ceea ce evident se întâmplă dacă apar probabilități egale într-o reducție.

Mai multe coduri se obțin și ca urmare a alocării arbitrare a simbolurilor 0 respectiv 1, atunci când se trece de la o reducție superioară la cea inferioară.

În asemenea cazuri se obțin coduri cu aceeași lungime medie a cuvintelor de cod, deci la fel de eficiente. Codarea cu metoda Huffman se poate face în același mod și pentru coduri cu mai mult de două simboluri.

Pentru sursa din tabelul T.1.3. se obține următoarea structură a cuvintelor de cod .

Pentru această sursă calculăm:

Entropia sursei:

bit /simbol.

Entropia maximă posibilă:

Eficiența sursei:

Lungimea medie a cuvintelor de cod:

simbol binar / simbol sursă.

Probabilitățile simbolurior 0 și 1:

[]* *

respectiv .

Entropia codului:

bit/simbol.

Eficiența codării:

.

Se poate constata o eficiență a codării apropiată de unitate. De asemenea se vede că sursa originală cu eficiența 0,8685, după codare, se transformă într-o sursă secundară cu eficiență mult mărită. În acest mod prin codare se obține atât adaptarea sursei canal, cât și o reducere a redundanței sursei.

ERORILE CANALULUI DISCRET ȘI MĂSURI DE PROTECȚIE ÎMPOTRIVA LOR

Să ne amintim matricea de transfer a canalului binar, în care există probabilități diferite de zero în toate cele patru poziții. O asemenea matrice ne conduce la eroare medie, respectiv echivocație, diferite de zero. Altfel spus, printr-un asemenea canal se recepționează semnale uneori eronate.

Erorile introduse de canalul discret pot fi de două tipuri, erori individuale, dacă apar răzlețe și necorelate unele cu altele și erori grupate în pachete de erori, dacă apar în grupuri de lungime oarecare. S-a constatat că erorile individuale, caz limită al erorilor în pachete de lungime unitară, apar mai rar decât erorile pachete. Pentru un canal de tip dat, pachetele de erori au de obicei lungime dată. Aici prin lungimea pachetului de erori înțelegem numărul de simboluri cuprinse între primul eronat și ultimul eronat aparținând pachetului. Facem precizarea că în interiorul unui pachet de erori, simbolurile intermediare pot să fie sau să nu fie eronate. Lungimea pachetului de erori depinde și de viteza de transmisie din canal.

Regula de decizie după probabilitatea aposteriori maximă și regula de decizie după distanța Hamming minimă

Prin canalul binar se transmit succesiuni de simboluri binare, numite la emisie cuvinte de cod, iar la recepție cuvinte recepționate. În general cuvântul emis nu este identic cu cel recepționat, diferența provenind din canal și numindu-se cuvântul eroare. Un cuvânt de cod oarecare, , aparține mulțimii cuvintelor de cod v, oricare putând fi emis. Cuvântul recepționat, , poate fi identic cu sau va diferi de acesta, astfel încât:

,

unde prin am notat cuvântul eroare, compus din zero-uri și un-uri, aparținând mulțimii cuvintelor eroare, E.

Cele trei mărimi, , și , sunt vectori n dimensionali sau matrice linie cu n coloane.

Se pune problema ca, pe baza cuvântului recepționat, , să determinăm cuvântul de cod emis, , cunoscând statistic canalul de transmisie și mulțimea cuvintelor de cod emisibile. Următorul raționament ne va permite să luăm o decizie asupra lui . Aceasta poate proveni din sau din sau din etc. La recepția lui , regula de decizie pe care o vom construi, ne va conduce la afirmarea emisiei unui anumit cuvânt de cod, să zicem . Știm că uneori vom greși. Regula de decizie trebuie să ne conducă la cea mai rară eroare. Altfel spus, regula de decizie trebuie să fie astfel aleasă, încât probabilitatea aposteriori ca să se fi introdus în condiția recepționării lui , să fie mai mare ca orice probabilitate, de a se fi introdus , atunci când s-a recepționat . O astfel de regulă de decizie este denumită maxim aposteriori, pentru că decide în conformitate cu maximul unei probabilități aposteriori și ne conduc la cea mai mică eroare medie.

Deoarece:

,

atunci când nu se cunoaște și se acceptă echiprobabilitatea emisiei cuvintelor de cod, regula deciziei maxim aposteriori se transformă în regula de decizie a probabilității maxime, conform căreia s-a emis acel care are cea mai mare probabilitate, , de a se transforma în , adică:

> decizie: s-a emis .

Două cuvinte de aceeași lungime, n, constituite din simboluri binare, se deosebesc în câteva poziții. Denumim distanță Hamming dintre cuvintele și

și o notăm , numărul de poziții în care cele două secvențe, și , sunt diferite.

Distanța Hamming ne poate ajuta la stabilirea unui criteriu de decizie. Acceptăm că orice simbol binar se eronează, la trecerea prin canal, cu probabilitatea p. În acest caz, probabilitatea condiționată , de a se recepționa atunci când s-a emis , este produsul probabilităților de transformare a fiecărui simbol component din în simbolul respectiv din și se va scrie :

.

Probabilitatea de a se recepționa atunci când s-a emis ,va fi:

.

Aici n este numărul de simboluri din .

Regula de decizie a probabilității maxime ne conduce la decizia emisie lui dacă:

>,

ceea ce, considerând relațiile în care au intrat distanțele Hamming precum și faptul că p<<1, ne conduce la a afirma că s-a emis , dacă:

<.

Aceasta este regula de decizie după valoarea minimă a distanței Hamming. Conform acestei reguli, s-a emis acel cuvânt de cod, față de care cuvântul recepționat este cel mai apropiat, distanța estimată fiind o distanță Hamming.

Din regula de decizie după distanța Hamming, decurg două urmări importante și anume:

Între cuvintele de cod, emisibile, trebuie să fie o distanță Hamming mai mare ca 1, pentru ca cuvântul eronat recepționat , să nu semene cu un alt cuvânt emisibil, , mai mult decât cu cuvântul din care provine,

. Asta înseamnă că nu toate cuvintele compuse din n simboluri binare vor fi cuvinte de cod.

Cu cât distanța Hammig între cuvintele de cod va fi mai mare, fără ca să se facă o decizie falsă, deoarece îndepărtându-se de emis, nu se apropie prea mult de un alt cuvânt .

Se poate demonstra că, dacă D este cea mai mică distanță Hamming dintre orice pereche de cuvinte de cod, pentru a sesiza prezența a e erori în cuvântul recepționat, este necesar ca D≥e+i. pentru a corecta e erori, adică pentru a decide corect asupra provenienței cuvântului recepționat cu e erori oarecare, este necesar ca D≥2e+i

1.6.2 Clasificarea codurilor

Vom clasifica codurile binare protectoare la zgomotele din canal după lungime, efect și erori sesizate.

Codurile, care permit la recepție sesizarea prezenței erorilor, se numesc coduri detectoare de erori. Aceste coduri permit afirmarea cu certitudine a prezenței erorilor, fără să se poată face o localizare a acestora. Dacă codul permite localizarea erorilor, atunci vorbim despre un cod corector de erori, deoarece după localizare se pot converti simbolurile, localizate ca eronate, în simbolurile corecte. Dacă cantitatea de erori se menține în limitele performanțelor codului, corecția se execută cu certitudine. Procedura de corecție este mai complicată decât cea de detecție, find necesare suplimentar și informații care să permită localizarea erorilor, nu numai afirmarea prezenței acestora. Alegerea între codul corector de erori și codul detector de erori, se face ținând cont că, orice detecție de eroare este urmată de repetarea transmisiei și aceasta presupune un canal retur, prin care emițătorul este informat despre necesitatea repetării.

Transformarea informației cu scopul protejării la trecerea prin canal se numește codare, asemănător transformării simbolurilor unei surse oarecare în cuvinte binare. De data aceasta se transformă cuvântul de informație, secvență binară de lungime k, în cuvânt de cod, tot succesiune binară dar de lungime n, mai mare decât k. Dacă codarea se face pentru a se obține blocuri de câte n simboluri și în fiecare bloc se face prelucrări fără referire la alte blocuri, vorbim despre codări bloc iar succesiunea de n simboluri se numește cuvânt. Dacă prelucrarea se face continuu, vorbim despre coduri convoluționale. Noi vom studia codurile grup și codurile ciclice, ambele coduri bloc, precum și codurile convoluționale.

Shannon, analizând posibilitatea decodării corecte a cuvintelor recepționate, a ajuns la concluzia că există posibilitatea de a se coda o sursă de informație, cu un cod care să poată fi codat cu eroare oricât de mică, dacă se codează extensia n a sursei primare și dacă canalul are capacitatea nu mai mică decât entropia sursei, n fiind cât mai mare. Aceasta este a două teoremă a lui Shannon, denumită teorema codării canalelor cu zgomot, care afirmă posiblitatea codării fără să indice metoda de codare.

Oricum, pentru ca eroarea de decodare să fie mică, este necesar ca n să fie mare, ceea ce înseamnă o schemă concretă deosebit de complicată.

CODURI SIMPLE DETECTOARE SAU CORECTOARE DE ERORI

În cele ce urmează se prezintă câteva coduri capabile să corecteze sau să detecteze erori, caracterizate prin simplitate și comoditate în exploatare.

Transmisia pe două canale pentru corecția pachetelor de erori

Sistemul de transmisie ce va fi descris, utilizează două canale, prin care informația circulă într-un singur sens, de la emisie spre recepție. Se presupune că în ambele canale apar simultan erori grupate în pachete, cu lungime ce nu depășește l biți. O asemenea presupunere este îndreptățită în cazul a două căi de transmisie multiplă cu separarea căilor în fază, când pe același traseu fizic, se emit două semnale, iar zgomotul afectează simultan ambele căi. Lungimea maximă a pachetelor de erori, l, este luată în considerare în construcția schemei de transmisie, care, în acest fel, se adaptează condițiilor de zgomot.

În figura 1.5. se prezintă schema bloc a sistemului de transmisie. Aici se vede sursa de semnale binare, S, un registru de deplasare cu l celule, RDl, ambele plasate la emisie. În canalul 1 debitează sursa S cu o întârziere de l tacte, datorită registrului de deplasare RDl, iar în canalul 2 debitează aceeași sursă, fără întârziere. La recepție este plasat un registru de deplasare în canalul 2, RD, acesta executând o întârziere cu l tacte a semnalului emis din sursa S.

În punctele a și b, dacă nu sunt erori la trecerea prin canale, se obțin semnale de aceeași formă. Prin comutatorul k se transmit prin utilizatorul R, semnalele din punctul a. Schema receptorului mai conține un comparator C, care sesizează diferența între semnalele din punctele a și b, ce ar putea să apară atunci când canalul introduce erori. Deoarece erorile din canalul 1 pătrund imediat în a, iar erorile din canalul 2, ajung în punctul b numai după l tacte, cât durează traversarea registrului de deplasare, comparatorul C indică dispozitivului de comandă DC prima neconcordanță, iar acesta comută cheia k în poziția b. În acest punct mai sosesc încă l simboluri corecte, acestea fiind stocate în registrul de deplasare de la recepție, RD. După ce s-au scurs l simboluri, cheia k este comutată înapoi în punctul a, deoarece, așa cum am presupus, pachetul de erori are lungimea maximă l și deci acestea s-au scurs deja prin punctul a, iar punctul b începe să fie parcurs de erorile care au traversat registrul de deplasare RD.

În primele l tacte, după ce comparatorul C a sesizat prima neconcordanță, erorile ce apar în a conduc la alte neconcordanțe sesizate de C, dar neluate în considerație de DC. În următoarele tacte, comparatorul C va sesiza neconcordanțe

datorită erorilor care acum trec prin b, dar nici dedata aceasta DC nu le consideră. După ce s-au scurs în total 2l tacte, cheia k rămâne în punctul a și orice neconcordanță, sesizată de comparatorul C, pune în funcțiune dispozitivul DC. Se vede din cele expuse, că este necesar ca între pachetele de erori de lungime maximă l, să fie un interval de siguranță de lungime minimă l.

Cod cu repetiție detector de erori

Codul cu repetiție conține cuvinte de cod cu lungimea n=2k, k fiind numărul simbolurilor de informație. Codarea acestui cod constă în completarea secvenței de informație cu o secvență de control de aceeași lungime. Structura secvenței de control este identică cu acelei de informație, dacă ponderea acesteia este un număr par și este complementul bit cu bital secvenței de informație dacă ponderea acesteia este un număr impar. Cele două jumătăți ale cuvântului de cod sunt corelate. Absența acestei corelații la recepție indică prezența erorilor.

Pentru a calcula capacitatea de detecție, vom exprima mai întâi numărul erorilor nedetectate. Dacă se emite un cuvânt oarecare, și se recepționează un alt cuvânt emisibil, erorile nu vor fi detectate. Numărul acestor cazuri este cu unu mai mic decât numărul cuvintelor emisibile, adică . Numărul total de cuvinte cu erori ce se pot recepționa, este cu unu mai mic decât numărul cuvintelor ce se pot construi din n simboluri, pentru că la un cuvânt emis, se poate recepționa oricare cuvânt de n simboluri.

Deci, capacitatea de detecție va fi:

.

Probabilitatea deciziei false se va calcula știind că o asemenea decizie se ia dacă, după introducerea unor erori în prima jumătate a cuvântului de cod, se vor introduce erori în mod corespunzător și în a doua jumătate, astfel ca între cele două jumătăți să existe corelația care stă la baza codării.

Dacă numărul de erori din prima jumătate este impar, atunci se va schimba paritatea din această jumătate. Corelarea celei de a doua jumătăți, impune ca aici să

se schimbe toți biți din pozițiile corespunzătoare celor neeronate în prima jumătate. În acest fel a doua jumătate va fi corelată cu prima jumătate eronată.

Probabilitatea totală a acestor situații, , este:

,

în care i aparține mulțimii numerelor pozitive impare nu mai mare ca și K. Se vede că însumarea s-a făcut pentru toate erorile impare din prima jumătate a cuvântului transmis.

Dacă numărul de erori din prima jumătate este par, atunci nu se schimbă paritatea din această jumătate. Corelarea celei de a doua jumătăți, impune ca aici să se schimbe simbolurile din pozițiile corespunzătoare simbolurilor eronate în prima jumătate.

Probabilitatea deciziei false a tuturor situațiilor de acest gen, , va fi:

,

în care j aparține mulțimii numerelor pozitive pare nu mai mare decât K.

Probabilitatea deciziei false, , va fi suma celor două decizii false parțiale:

.

Dacă codul are K >3, deoarece p<<1, cu o bună aproximație se poate aprecia probabilitatea deciziei false cu expresia:

,

care ține cont numai de cuvintele eronate cu patru erori.

Cod cu pondere constantă detector de erori

Cunoscut și sub numele de cod M din N, codul cu pondere constantă are cuvinte de cod de lungime N, compuse din M unuri și N-M zerouri aranjate oricum. Se vede de aici că din cele cuvinte de N biți, doar sunt cuvinte de cod și .

Posibilitatea detecției erorilor derivă, din inegalitatea >. O succintă analiză ne arată că, un număr impar de erori, are drept urmare schimbarea numărului de unuri, deci modificarea ponderii cuvântului recepționat. Ponderea cuvântului se va schimba și în cazul unor erori în număr par, dacă mai mult de jumătate din erori sunt de un tip și mai puțin de jumătate sunt de alt tip. În cazul erorilor în număr par, dacă jumătate sunt zerouri transformate în unuri, iar cealaltă jumătate sunt unuri transformate în zerouri, numărul de unuri din cuvânt nu se schimbă și deci erorile se detectează, detecția erorilor fiind posibilă numai dacă ponderea cuvântului recepționat este diferită de M.

La emisia unui cuvânt de cod, recepția va primi unul din cele cuvinte posibile, ceea ce înseamnă că sunt în total cuvinte eronate și unul corect. Din totalul de cuvinte emisibile, s-a emis unul, ceea ce înseamnă că oricare din celelalte cuvinte emisibile, dacă sosește la recepție va fi cuvânt eronat, dar eroarea nu va fi detectată, cuvântul având ponderea M. În consecință numărul cuvintelor eronate va fi , ceea ce permite a se scrie următoarea relație, pentru capacitatea de detecție a cuvintelor eronate:

,

fiind deci raportul dintre numărul cuvintelor eronate detectate dintre numărul cuvintelor eronate.

O altă mărime care caracterizează codul detector de erori, este probabilitatea deciziei false, . O decizie falsă se ia, dacă sunt erori în număr par și jumătate din ele sunt zerouri transformate în unuri. Pentru două erori în cuvânt, o eroare va fi de tipul 1→0 și una de tipul 0→1. Numărul total de cuvinte astfel eronate este M(N-M) pentru că sunt M unuri care suferă prima transformare și N-M zerouri care suferă a doua transformare.

Probabilitatea unui cuvânt astfel eronat este:

.

Pentru patru erori, două de un tip și două de celălalt tip, numărul cuvintelor astfel eronate va fi :

și fiecare cuvânt are probabilitatea :

.

În caz general, probabilitatea deciziilor false va fi suma probabilităților erorilor nedetectate, adică:

,

în care este cel mai mic număr dintre M și N-M, iar p este rata erorilor din canal.

CAPITOLUL 2

CODURI GRUP

Codurile grup sunt coduri care conțin cuvinte de cod compuse din n componente, fiind astfel un cod bloc, iar mulțimea cuvintelor de cod este o mulțime vectorială, fiecare cuvânt fiind un vector. Spațiul vectorial are o structură de grup fiind o mulțime înzestrată cu o lege de compoziție internă. Componenetele cuvântului de cod, fiind vorba de transmisii binare, sunt elementele notate 0;1 și aparțin câmpului binar GF(2). Legile de compoziție ale câmpului GF(2) sunt suma modulo doi și multiplicarea, definite astfel:

Rostul codurilor grup este acela de a facilita transmisia simbolurilor unor surse de informație.

SUBMULȚIMI ÎN SPAȚIUL VECTORIAL

Notăm cu W mulțimea vectorilor compuși din n elemente binare și o considerăm ca reuniune a două subspații vectoriale W=VUF. Subspațiul vectorial V este mulțimea tuturor cuvintelor binare de lungime n, care se pun în corespondență biunivocă cu simbolurile unei surse de informație, ce urmează a se transmite. Considerăm astfel că fiecare cuvânt are sens, adică este purtător al unui mesaj și îl numim cuvânt de cod.

Orice cuvânt binar cu n componente, neaparținând mulțimii V, nu reprezintă un simbol din sursa de informație, nu are sens, nu transmite mesaj. Necesitatea

existenței submulțimii F, compusă din cuvinte fără sens, decurge din necesitatea de a putea detecta erori în cuvântul recepționat deoarece, procesul de detecție pune în evidență erorile, atunci când cuvântul recepționat, , nu aparține submulțimii V.

Dacă mulțimea V conține de cod, atunci o putem utiliza, pentru a transmite o sursă de informație cu simboluri. Informația medie pe simbol maximă a acestei surse, este:

bit / simbol,

ceea ce înseamnă că fiecare cuvânt de cod poartă o informație de k biți. Având în vedere că orice cuvânt de cod aparține mulțimii W compusă din vectori, informația maximă pe care ar putea-o conține un cuvânt de cod ar fi:

bit / cuvânt.

Se vede că n >k și în consecință, prin divizarea mulțimii W în cele două submulțimi V și F, cuvintele de cod transportă doar k biți de informație, din n biți câți ar putea transporta, având deci redundanță. Eficiența transmisiei va fi raportul dintre k și n. Introducerea redundanței, ca urmare a existenței subspațiului F, urmărește asigurarea unei transmisii cu protecție față de zgomotele din canalul de transmisie. Efectul zgomotelor asupra cuvântului de cod , poate fi considerat ca acțiune a legii de compoziție a câmpului vectorial, în urma căreia din se obține cuvântul recepționat :

.

Vectorul n dimensional se numește cuvânt eroare, aparține grupului W și nu aparține subgrupului V. Convenim să notăm E mulțimea tuturor cuvintelor eroare , generate de canalul de transmisie, pe care dorim să le detectăm și / sau să le corectăm, fără să includem în E acele cuvinte eroare, pe care considerăm că nu le putem trata prin intermediul codului grup pe care-l studiem.

Dacă:

atunci:

sumele făcându-se modulo doi.

2.2. Matricea de control

Procesul de detecție și corecție a erorilor presupune tratarea într-un anumit mod a semnalului recepționat, astfel încât să se corecteze efectul canalului de transmisie. Putem face corecția considerând o mulțime Z, numită mulțimea corectorilor și care conține vectori m dimensionali, capabili să corecteze erorile introduse de canal. Între mulțimea cuvintelor recepționabile, W, și mulțimea corectorilor, Z, se stabilește o relație unidirecțională, o aplicație definită pe W cu valori în Z, astfel încât, pentru orice cuvânt recepționat, să putem defini un corector . Având în vedere caracterul vectorial al câmpurilor W și Z, în care vectorii pot fi reprezentați prin matrice, aplicația va fi un produs matricial între o matrice H, numită matrice de control și cuvântul recepționat transpus, adică:

.

Matricea H urmează să fie compusă din n coloane, m linii, cu elemente din câmpul binar, astfel încât corectorul să aibă m componente binare, aranjate pe coloană. În urma efectuării produsului de mai sus, vom obține un corector pentru oricare , în particular și pentru cuvintele de cod . Având în vedere scopul introducerii mulțimii Z, acela de detecta și corecta erori de transmisie, convenim să construim astfel această mulțime, încât, ori de câte ori aplicația de mai sus se efectuează asupra unui cuvânt de cod , să se obțină același corector . Mai mult chiar, convenim că acest corector să aibă toate componentele nule, adică:

.

Dacă la recepția unui cuvânt, , constatăm că , vom deduce că în nu sunt erori și invers, dacă , vom constata că în sunt erori. Astfel, aplicația:

,

servește la detecția erorilor.

Considerând relația :

,

care stabilește modalitatea de transformare a vectorului de cod în vectorul recepționat cu ajutorul cuvântului eroare , aplicând obținem:

.

În relația de mai sus am ținut cont că . Această ultimă relație prezintă un interes deosebit, deoarece ne arată că aplicația definită pe domeniul W cu valori în Z, executată asupra cuvintelor recepționate, compuse din cuvântul de cod emis și oricare cuvânt eroare din mulțimea E, conduce la un același corector Z ca și execuția aplicației, asupra cuvântului eroare , care a afectat transmisia cuvântului de cod. De aici se întrevede o posibilitate de găsire a cuvântului de eroare, calculând corectorul pe baza lui , iar din aceasta vom deduce cuvântul eroare , deoarece această aplicație asupra lui are ca rezultat corectorul . Pentru aceasta este necesar ca aplicația :

,

definită pe mulțimea E cu valori în Z să fie injectivă, adică oricare să provină dintr-un singur .

Din cele prezentate rezultă că matricea H poate servi la detecția erorilor, caz în care și / sau la localizarea acestora deacă orice are corespondent propriu în mulțimea Z.

Condiții impuse matricei de control pentru a detecta sau corecta erori

Stabilim condiția pe care să o satisfacă matricea de control H, pentru a se detecta prezența erorilor. În acest scop considerăm pe H compus din coloane:

,

iar pe de forma:

,

în care am inclus t componente de valoare 1, restul componentelor fiind nule. Se constată că :

,

adică corectorul Z este suma a t coloane din H, acelea cu indicii egali cu indicii componentelor nenule din cuvântul eroare. Pentru a detecta prezența unui cuvânt eroare cu t erori, este suficient ca suma a t coloane oarecare din H să fie nenulă.

Stabilim condiția pe care trebuie să o îndeplinească matricea H, pentru a putea corecta cuvinte eroare compuse din t sau mai puține erori. În acest caz, rescriind H și pentru două cuvinte eroare diferite, se va obține:

;

,

iar condiția de injectivitate înseamnă:

sau ,

adică:

.

Cu alte cuvinte, pentru ca o matrice de control H să poată fi folosită la corecția a t erori, este necesar ca suma a oricăror 2t coloane din matrice să fie diferită de zero. Din cele două condiții de a corecta respectiv de a detecta erori, rezultă suplimentar că o matrice de control capabilă să corecteze t erori, este capabilă să detecteze 2t erori, dar nu ambele procese deodată.

Denumim pondere a unui cuvânt de cod, numărul componentelor sale diferite de zero. Fie două cuvinte de cod și . Deoarece V are o structură de grup, rezultă că este un vector aparținând lui V și este deci cuvânt de cod.

Pe de altă parte, suma dă un cuvânt a cărui pondere este egală cu distanța Hamming dintre și .

Denumim distanță Hamming a codului, cea mai mică distanță Hamming dintre oricare două cuvinte de cod. Se vede că distanța Hamming a codului este egală cu ponderea cea mai mică a cuvintelor de cod, exceptând cuvântul cu toate componentele nule.

Dacă distanța Hamming a codului este 2t+1, atunci există un cuvânt de cod, , cu 2t+1 unuri și în rest zerouri. Aplicația pentru corector, pentru acest cuvânt de cod, se scrie:

,

ceea ce înseamnă, că suma a 2t+1 coloane din matricea H este zero. Dacă matricea H poate corecta t erori, rezultă că suma a 2t coloane este diferită de zero și că deci nu există nici un vector cuvânt de cod, care să conducă la o relație de forma celei de mai sus ca o sumă din 2t coloane, ceea ce înseamnă că un cod capabil să corecteze t erori are distanța Hamming cel puțin egală cu 2t+1.

Construcția matricei de control pentru a detecta un număr impar de erori

Ne propunem să aflăm structura unei matrice de control capabilă să detecteze cuvinte eroare cu 2r+1, , erori. Scriem:

,

în care am considerat că fiecare coloană din H se termină cu un simbol 1.

Relația:

,

se va scrie acum, considerând t=2r+1:

.

Această sumă de coloane va conține în ultima linie un număr impar de 1-uri, a căror sumă nu poate fi zero, ceea ce înseamnă că se satisface condiția detectării erorii, indiferent de conținutul coloanelor , … din matricea H. Acestea pot fi chiar nule, ceea ce înseamnă că matricea de control, pentru detecția unui număr impar de erori, este un șir de 1-uri: H=[1 1 1 1…1].

O asemenea matrice are dimensiunea m=1, ceea ce înseamnă că în mulțimea Z a corectorilor vor fi numai 2 elemente: corectorul Z=0 și corectorul Z=1. Primul va indica absența erorilor în număr impar, iar al doilea prezența acestora. Produsul , atunci când pentru H se utilizează matricea de mai sus, implică un număr par de 1-uri în V. Din acest motiv, procedeul de detecție a unui cuvânt eroare, compus din număr impar de 1-uri, se mai numește detecție de control de paritate. Este evident că din cele n simboluri ale cuvântului de cod, pentru a constitui paritate, este suficient să controlăm un singur simbol, toți ceilalți putând avea orice valoare. Aceste n-1 simboluri binare vor lua valori arbitrare, precizate de utilizatorul transmisiei, deci vor fi simboluri de informație. Simbolul al n-lea, cel de control, va fi nepurtător de informație și de o astfel de valoare, încât să realizeze un număr par de 1-uri în cuvântul de cod.

Construcția matricei de control pentru a detecta două erori

Am stabilit în paragraful anterior, că adăugarea unui simbol de control, la cele n-1 simboluri de informație, poate verifica existența unui număr impar de erori. Tot așa de bine putem spune că verifică și existența unui număr par de erori, în acest caz numărul de 1-uri din cuvântul recepționat fiind par.

Admitem că cei n-1 biți ai cuvântului transmis sunt constituiți astfel, încât se poate corecta o eroare, satisfăcându-se condiția pentru cuvântul cu n-1 biți și o matrice de control . Dacă adăugăm un bit, cel de al n-lea, obținem un cuvânt de cod pentru care se poate asigura corectarea unei erori și detecția a două erori. În

acest scop vom construi matricea de control H, din matricea de control a codului corector de o eroare , prin adăugarea unei coloane nule și a unei linii compuse numai din 1-uri. În acest caz, condiția se va scrie:

.

Aici am notat cu coloana din poziția i a matricei corectoare de o eroare.

La recepția unui cuvânt, se va face produsul pentru a se obține corectorul . Acesta are un aspect asemănător:

.

Constatăm că la emisie:

,

reprezintă condiția pentru un cuvânt de cod cu n-1 simboluri, iar la recepție:

,

este corectorul acestui cuvânt de cod. O eroare în cuvântul recepționat, poziționată de la la , se va detecta și corecta prin intermediul corectorului , conform ipotezei.

Constatăm că la emisie:

,

ceea ce înseamnă că face paritate în cuvântul de cod, iar la recepție:

,

că ultimul simbol din corectorul , simbolul C, va avea valoarea 0 dacă este paritate în cuvântul recepționat, deci dacă numărul de erori nu este impar, respectiv va avea valoarea 1, dacă numărul de erori este impar. Adică:

; nu sunt erori

; este o eroare corectabilă prin

; este o eroare în poziția

; sunt detectate două erori.

Cele de mai sus presupun o matrice capabilă să corecteze o eroare.

GENERAREA CUVINTELOR DE COD

Cuvântul de cod, , satisface relația , ceea ce înseamnă că, din cele n componente ale vectorului , m componente sunt determinate prin această relație și restul de n-m=k componente sunt independente și pot lua orice valori, altfel spus pot fi fixate de utilizatorul transmisiei, din acest motiv aceste k simboluri se numesc simboluri de informație. În funcție de valoarea acestora și de structura matricei de control vor obține valori celelalte m simboluri. Ne convingem de aceasta considerând matricea de control:

,

care, după transformări elementare se poate aduce la forma:

.

Facem produsul în care pentru V considerăm două elemente:

prima fiind o succesiune de control, iar a doua de informație, și obținem:

.

Matricea de control H oferă componentele matricei Q și deci, luând arbitrar secvența i, rezultă valorile secvenței . Cu alte cuvinte dacă se dă secvența de

informație i, având matricea de control, matricea Q, cu relația de mai sus se determină secvența de control, G, conform relației:

.

Din această relație rezultă că matricea G trebuie să aibă n coloane și k linii. Evident, metoda aceasta de obținere a cuvintelor de cod, este o altă formă de exprimare a procedeului de codare descris de relația:

.

Cu alte cuvinte, între matricea H și matricea G există o corespondență pe care o vom determina.

Scriem relația cu considerarea ultimei relații obținute și vom obține:

.

Această relație se îndeplinește pentru orice i, dacă:

,

ceea ce înseamnă că G are structura dependentă de H:

implică .

Din cele de mai sus deducem că putem executa codarea, având nevoie de una din matricile G sau H.

Facem observația că G se compune din k cuvinte de cod așezate în linie, acelea care s-ar obține înmulțind pe G cu secvența de informație compuse din k-1 zero-uri și un singur 1. Aceasta formează baza matricei G. Celelalte cuvinte de cod, se obțin înmulțind pe G cu secvențe de informație, care au mai mulți 1-uri în compunerea lor. Considerând o asemenea secvență ca sumă a două secvențe de informație fiecare având doar un singur 1, rezultă:

,

ceea ce înseamnă că din cele k linii independente ale lui G se vor obține, combinându-le în toate modurile posibile, celelalte cuvinte de cod.

CAPITOLUL 3

CODURI REED-MULLER

În categoria codurilor grup corectoare de erori, sunt cuprinse și codurile Reed-Muller a căror codare și decodare se poate face cu scheme relativ simple. Particularitățile acestor coduri derivă din structura matricii generatoare cu ajutorul cărora se definesc.

3.1. Descrierea codului Reed-Muller

Un cod Reed-Muller este definit prin doi parametrii, t și r, din care se obțin toate proprietățile și caracteristicile sale.

Lungimea cuvintelor de cod, n, este o putere întragă a lui doi.

cu tN.

Numărul simbolurilor de informație, k, satisface relația:

cu r < t și rN.

Numărul erorilor independente, a, corectate de un cod Reed-Muller este definit prin:

,

ceea ce presupune existența unei distanțe Hamming a codului, de valoare:

.

Codul Reed-Muller utilizează, pentru codare și decodare, matricea generatoare. Construcția acestei matrice și algoritmul de decodare, descrise în cele ce urmează, pun în evidență relațiile de mai sus.

. Codarea codului Reed-Muller

Codarea codului Reed-Muller se face utilizând relația:

V=iG,

în care V este cuvântul de cod, i este secvența de informație, iar G este matricea generatoare. Această matrice are coloane și este organizată în r secțiuni. Prima secțiune conține t+1 linii, sau vectori de bază, construiți în felul următor:

Prima linie are unuri

A doua linie are simboluri egale cu 0, urmate de simboluri egale cu 1.

A treia linie are simboluri egale cu 0, urmate de simboluri egale cu 0 și apoi simboluri egale cu 0. Se continuă în acest fel.

Linia a j-a va avea la început simboluri egale cu 0, urmată de tot atâtea simboluri de 1 ș.a.m.d.

Ultima linie din secțiunea de bază se va constitui cu 0 și 1 succesiv, 0101…, ceea ce înseamnă că va avea la început simboluri egale cu 1 deci:

,

ceea ce înseamnă că ultima linie va fi a t+1 .

Notăm aceste linii cu .

A doua secțiune a matricei generatoare se compune din linii ce rezultă ca produs a două linii oarecare din liniile primei secțiuni. Se fac toate produsele posibile fără însă să se utilizeze linia . Liniile astfel obținute se notează cu doi indici, aceștia fiind, fiecare în parte, indicii liniilor care au contribuit la construcția liniei cu doi indici. Dacă:

,

cu i, j{1,2,…t}. Atunci produsul va avea structura:

… .

Se poate arăta că secțiunea a doua va avea linii cu doi indici.

A treia secțiune a matricei generatoare se compune din linii, cu trei indici fiecare, construite prin înmulțirea a trei linii diferite din prima secțiune de bază. Se fac toate produsele posibile după un procedeu similar, fără a se utiliza linia . În

secțiunea a treia vor fi linii cu trei indici.

În mod asemănător se construiesc toate celelalte secțiuni până la secțiunea a r-a. Această secțiune va conține deci linii compuse fiecare din r linii diferite ale primei secțiuni din G. În mod necesar r<t.

Numărul total de linii din G este egal cu suma:

și, pentru a se putea aplica relația matriceală de codare V=iG, trebuie ca numărul liniilor din G să fie egal cu numărul k al simbolurilor secvenței de informații i.

Parametrul r<t din codul Reed-Muller, se alege din condiția cerută capacității de corecție. Dacă r=t, în matricea generatoare se vor scrie linii. Aceasta înseamnă că k=n și deci toate simbolurile cuvântului de cod sunt simboluri de informație. Un asemenea cod nu protejează transmisia față de zgomotele din canal.

Dacă r=t-1, în matricea generatoare se scriu mai puține linii. Aceasta va avea acum linii, lipsind, față de cazul prezentat anterior, linia cu t indici. Se vede că acum n=k+1, ceea ce înseamnă un cod capabil să detecteze o eroare.

Pentru a corecta erori trebuie ca n>k+1. Codurile Reed-Muller, utilizate în practică, au r<t-1, diferența t-r indicând, așa cum vom vedea și în continuare, capacitatea de corecție a codului.

Aplicație:

Să scriem matricea generatoare a unui cod Reed-Muller care are ca parametrii t= 4 și r= 2 și să executăm codarea unui cuvânt de cod. Matricea generatoare are aspectul:

Pentru un cod Reed-Muller cu parametrii t=4, r=2, capabil să corecteze 3 erori, matricea generatoare ar fi avut numai primele cinci linii din (), adică numai liniile de bază, cu un singur indice.

Conform relației de codare v = iG, cuvântul de cod va fi combinație liniară a liniilor matricei generatoare G. Combinația liniară se face dependent de structura simbolurilor de informație din secvența i, astfel încât cuvântul de cod va fi diferit pentru fiecare secvență de informație diferită.

Pentru comoditatea calculului, vom nota cele k simboluri din secvența de informație, cu indici având aceleași valori ca indicii liniilor matricei generatoare, modul de execuție a produsului matricial iG explicând posibilitatea și oportunitatea unei asemenea notații. De asemenea vom împărți secvența de informație în secțiuni, fiecare secțiune cuprinzând simboluri cu același număr de indici. Pentru t=4 și r=2 secvența de informație va avea aspectul:

fiecare simbol putând lua valori în câmpul 0 , 1.

Produsul ν = iG ne duce la următoarele relații:

a1=i0 a6=i0+i3+i1+i31

a2=i0+i1 a7=i0+i3+i2+i32

a3=i0+i2 a8=i0+i3+i2+i1+i32+i31+i21

a4=i0+i2+i1+i21 a9=i0+i4

a5=i0+i3 a10=i0+i4+i1+i41

a11=i0+i4+i2+i42 a14= i0+i4+i3+i1+i43+i41+i31

a12= i0+i4+i2+i1+i42+i41+i21 a15= i0+i4+i3+i2+i43+i42+i32

a13= i0+i4+i3+i43 a16= i0+i4+i3+i2+i1+i43+i42+i41+i32+i31i21

În consecință, cuvântul de cod va fi succesiunea:

V=a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12 a13 a14 a15 a16

O realizare tehnică a codării codului Reed-Muller, va conține sumatoare modulo doi, acționate la intrare cu secvența i. Se poate construi această schemă combinațională într-un singur etaj, având sumatoare distincte pentru fiecare simbol al cuvântului de cod. Schema combinațională se poate construi și în mai multe etaje deoarece, așa cum se poate vedea din relațiile de codare, un simbol din cuvântul de cod poate fi utilizat la construcția unui alt simbol din cuvântul de cod, având componența necesară. Pentru exemplificare, considerând expresiile simbolurilor a14 , a13 , a6 , a5 , se constată că:

a14=a13+a6+a5+i41

ceea ce înseamnă, pentru generarea simbolului a14 , utilizarea unui sumator cu patru intrări în locul unuia cu șapte intrări. Structura etejată a schemei de codare duce însă la reducerea vitezei, neesențial însă dacă transmisia se face în serie.

3.3. Decodarea codului Reed-Muller

Când este dată o matrice generatoare G, orice secvență, de informație i cu dimensiunea k se poate coda, fiind transpusă într-un cuvânt cod de dimensiune n. O secvență anumită i are drept corespondentă o secvență anumită V. Aceasta înseamnă că între i și V există o relație biunivocă, ceea ce permite să se afirme că, pe baza lui V, se poate determina acel i care l-a generat prin procesul de codare. Fără o asemenea posibilitate procedura de codare nu are sens.

Analizând relațiile de mai sus, constatăm că putem construi relații de decodare. Spre exemplu, pentru i0 , i4 și i21 se pot scrie următoarele relații cu ajutorul cărora se pot calcula, cunoscând simbolurile cuvântului de cod

i0=a1; i4=a1+a9; i21=a1+a2+a3+a4

Mai constatăm că, pentru un simbol de informație putem scrie mai multe relații de calcul. Spre exemplu pentru i21 se pot scrie relațiile:

i21=a1+a2+a3+ a4; i21=a5+a6+a7+ a8; i21=a13+a14+a15+ a16

Această posibilitate, de a putea calcula un simbol de informație cu mai multe relații, permite a se corecta erori, utilizând procedeul de decodare cu logică majoritară, sau cu logică de prag cum se mai numește, în locul simbolurilor cuvântului de cod introducând simbolurile cuvântului recepționat, diferit de cel de cod emis.

Presupunem că un simbol de informație se poate calcula din simbolurile cuvântului de cod, prin α relații diferite, fiecare simbol al cuvântului de cod participând doar în una din aceste relații de calcul. Dacă un un cuvânt de cod suferă la transmisie o modificare, prin care unele simboluri sunt eronate, astfel încât distanța Hamming între cuvântul de cod original și cuvântul recepționat este β < α/2, atunci din α relații de calcul pentru un simbol oarecare, doar β relații vor fi afectate fiecare de o singură eroare, iar α – β > β relații de calcul nu vor conține erori, oferind astfel valoarea corectă a simbolului căutat. De aici rezultă că în majoritate relațiile de calcul dau valoarea corectă a simbolului de informație, dacă numărul de erori nu depășește jumătatea numărului relațiilor de control.

Considerând spre exemplu relațiile scrise pentru i21 constatăm că o eroare poate fi corectată, deoarece intervine doar într-o relație, aceasta oferind pentru i21 valoare eronată. Două relații vor da însă valoarea corectă, având în compunerea lor simboluri corecte.

Codul Reed-Muller cu parametrii t și r, permite a se scrie pentru fiecare simbol de informație din ultima secțiune a secvenței de informație un număr de relații de control, independente, iar pentru simbolurile de informație cu indici identici cu cei ai liniilor din celelalte secțiuni, se pot scrie mai mult decât relații de control. Din acest motiv numărul de erori ce se pot corecta este , cu unu mai mic decât jumătatea numărului minim de relații de control. Scrierea relațiilor de control se face analizând matricea generatoare, mai întâi pentru simbolurile din ultima secțiune, apoi cele din penultima secțiune și în final pentru cele din prima

secțiune. Această ordine de scriere este obligatorie, atunci când se caută erorile, deoarece în calculul efectuat pentru simboluri de informație cu mai puțin de r indici, deci din secțiuni diferite de ultima, vor intra, pe lângă simbolurile cuvântului recepționat și simbolurile, anterior calculate, ale secvenței de informație căutate. Pentru simbolul i1 spre exemplu se vor scrie următoarele relații:

i1=a1+a2; i1=a3+a4+i21; i1=a5+a6+i31; i1=a7+a8+i31+i21

în care intră două simboluri cu doi indici, i21 și i31 , ale căror valori trebuiesc cunoscute.

Realizarea tehnică a decodorului unui cod Reed- Muller, ar trebui să conțină o schemă combinațională, prin care se execută sumele modulo doi corespunzătoare relațiilor de control și o schemă care precizează valoarea majoritară a simbolului, rezultată din însumările efectuate prin aceste relații.

Aplicație:

Vom considera codul Reed-Muller corector de trei erori cu t=4 și r=1.

Matricea generatoare are n=16 coloane și k=5 linii așa cum se vede mai jos:

Relațiile de calcul pentru cuvântul de cod sunt date de V=i+G, cu i=i0 i4 i3 i2 i1 și rezultă:

a1=i0 a9=i0+i4

a2=i0+i1 a10=i0+i4+i1

a3=i0+i2 a11=i0+i4+i2

a4=i0+i2+i1 a12= i0+i4+i2+i1

a5=i0+i3 a13= i0+i4+i3

a6=i0+i3+i1 a14= i0+i4+i3+i1

a7=i0+i3+i2 a15= i0+i4+i3+i2

a8=i0+i3+i2+i1 a16= i0+i4+i3+i2+i1

Cu schema combinațională din figura 2.3. se poate executa comandarea celor cinci simboluri de informație.

Se poate observa că cele 16 simboluri ale cuvântului de cod, se constituie ca o secvență, paralel, cu ajutorul a 15 sumatoare modulo doi, fiecare cu două intrări, atunci când secvența de inrormație este adusă în paralel la intrări.

Pentru decodarea codului Reed-Muller cu t=4 și r=1, analizând ecuațiile de codare, vom scrie relațiile de control, câte șapte pentru fiecare simbol de informație. A opta relație de control nu mai este necesară, deoarece atât din din 8 relații, cât și din 7 relații, se pot corecta, cu logică majoritară, același număr de trei erori. Pentru simbolul de informație i0 , relațiile de control utilizează valorile corectate ale simbolurilor de informație i1 , i2 , i3 , i4 , ceea ce presupune un calcul în cascadă.

CAPITOLUL 4

4. APLICATIE PRACTICA

Programul este o aplicație consolă – fără interfață grafică și neinteractiv – pentru sisteme Windows pe 32 biți dezvoltat sub Microsoft Visual C++ 6. Datorită limbajului orientat pe obiect (C++), programul conține clase reutilizabile pentru construirea altor aplicații, iar implementarea curentă construiește un cod Huffman pe baza unei surse de date (un fișier binar oarecare) și un cod Reed-Muller corector de 3 erori (t = 4, r = 1). Se aplică o codificare Huffman, apoi Reed-Muller urmată emularea canalului perturbat prin generarea de erori aleatoare (dar cel mult la capacitatea de corectare a codului). Codul perturbat este decodat R-M și apoi Huffman, iar apoi sursa originală este comparată cu rezultatul. Fiecare etapă a prelucrării este stocată într-un fișier astfel:

input.txt – sursa originală

huffman.txt – rezultatul codificării Huffman a sursei

rm.txt – rezultatul codificării Reed-Muller

rm-err.txt – cod Reed-Muller cu erori aleatoare

rm-decoded.txt – decodarea R-M cu erori corectate

output.txt – ieșirea, care trebuie să fie identică cu sursa originală

În continuare se prezintă ieșirea standard (consola) programului pentru o sursă de intrare cu 100 simboluri și 7 simboluri distincte.

Size=100

Symbols=7

Avg. code length: 2.47

Source entropy: 2.43815

Maximum entropy: 2.80735

Source efficiency: 0.868487

Code efficiency: 0.987105

Zero probability: 0.443667

One probability: 0.556333

Code entropy: 0.686787

Symbol Freq. Prob. Code

–––––––––––––––––

61 a 30 30 11

62 b 25 25 10

63 c 20 20 00

64 d 10 10 010

65 e 8 8 0111

66 f 5 5 01101

67 g 2 2 01100

Generated Reed-Muller matrix:

t=4 r=1

n=16 k=5

errc=3

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1

0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1

0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

Encoding (Huffman) … 100 symbols

Encoding (Reed-Muller) … 50 symbols

Generating random errors … 50 symbols

Decoding (Reed-Muller) … 50 symbols

Decoding (Huffman) … 100 symbols

Comparing input and output files … OK

Deoarece aproape toate aplicațiile curente de telecomunicații utilizează pachete de octeți – datorită abundenței de circuite existente – s-a considerat că simbolurile posibile ale codificării Huffman sunt aceștia, rezultând un număr maxim de 256 simboluri. Aceste simboluri sunt implementate în program prin clasa

HuffmanSymbol, care încapsulează pe lângă valoarea acestuia și frecvența apariției și poziția în arborele generator. Clasa care conține acest arbore și realizează atât codificarea cât și decodificarea este HuffmanCode.

Arborele Huffman este un arbore binar, care conține noduri (cu descendenți) și frunze (fără descendenți). Nodurile sunt auxiliare și conțin referințe la descendenți, precum și suma recursivă a frecvențelor tuturor descendenților. Astfel, nodul rădăcină va conține numărul total al simbolurilor. Deoarece arborele este binar, fiecare nod poate avea maxim doi descendenți direcți. Relațiile de descendență sunt de fapt cele care generează codul, atribuindu-se convențional valoarea 0 uneia și 1 celeilalte descendențe ale unui nod. Pentru exemplul dat, arborele Huffman este prezentat în figura următoare:

Codificarea se face cel mai ușor dacă există un tablou conținând referințe la fiecare instanță a HuffmanSymbol care reprezintă un simbol (o frunză în arbore). Aceasta permite evitarea unei căutări recursive în arbore pentru fiecare simbol de la intrare. Decodificarea este întotdeauna facilă utilizând un astfel de arbore: se pleacă de la rădăcină și se parcurge arborele la stânga (dacă bitul de intrare este 0) sau la dreapta (dacă este 1) până se ajunge la o frunză, apoi se scrie la ieșire simbolul decodat și se revine la rădăcină. Codul Huffman este el însuși detector de erori – dacă la terminarea biților de intrare am rămas pe un nod, atunci este există cel puțin o eroare.

Clasa HuffmanCode conține și metode pentru calculul unor parametri ai sursei și codului: lungimea medie a cuvântului de cod, entropia sursei, eficiența codului etc.

Codarea și decodarea Reed-Muller se face prin intermediul clasei ReedMullerMatrix. Aceasta calculează matricea generatoare pe baza parametrilor de intrare (t și r), ceea ce durează și consumă timp procesor, deoarece algoritmul

este destul de complicat. Majoritatea aplicațiilor unui astfel de cod nu generează matricea, ci folosesc una „prefabricată”.

Toate celelalte clase și funcții sunt auxiliare pentru acestea, sunt generice și pot fi reutilizate în aplicații de altă natură.

Buffer implementează un container pentru obiecte arbitrare referite prin pointeri. Dimensiunea acestuia este ajustată automat în funcție de necesități. Există metode pentru adăugare, ștergere și sortare, ultima dacă este furnizat un pointer către o funcție care să aplice un criteriu de sortare. Este folosită de ReedMullerMatrix.

BitStack, BitVector și BitMatrix sunt clase care manipulează câmpuri de biți. Prima este o stivă redimensionabilă folosită la codarea Huffman, celelalte sunt un vector fix și respectiv o matrice fixă a căror elemente sunt biți.

Clasele generice a căror nume se termină cu Stream implementează fluxuri și sunt organizate într-o ierarhie. InputStream și OutputStream sunt clase abstracte, deoarece au funcții pur virtuale – cele a căror declarație se termină cu = 0, de exemplu

virtual int read() = 0;

Aceste clase nu pot fi instanțiate direct și nu au constructori, dar pot fi derivate. FileInputStream și FileOutputStream sunt derivate ale acestora care implementează intrări/ieșiri cu fișiere la nivel de octet. BitInputStream și BitOutputStream sunt construite peste un InputStream (OutputStream) sau subclase ale acestora și operează la nivel de bit. Deoarece un flux de biți (de ex. codul Huffman) conține un număr arbitrar de biți și nu un multiplu de 8, se folosește o metodă de completare (padding) la sfârșitul fluxului. Ultimul octet din flux nu va conține informație utilă, ci numărul biților semnificativi din penultimul.

ANEXĂ