Strainu onLine

Descriere: Un subiect ceva mai dificil de înţeles.
Materie: Informatică, Matematică
Referat făcut la liceu.

Download (toate referatele sunt distribuite sub Licenţa CC-BY 3.0)

Mai jos aveţi la dispoziţie o variantă text a referatului. Vă rugăm să reţineţi că această variantă nu are nici un fel de formatare sau poze. Unele caractere pot să nu fie arătate corect. Pentru varianta integrală vă rugăm să downloadaţi referatul.

MATEMATICA ÎN…

Telecomunicaţii, transfer de date
Un studiu asupra teoriei de corectare a erorilor

Teoria codurilor de corectare a erorilor apare din următoarea problemă: „Ce înseamnă un drum bun de a trimite un mesaj pe un canal de difuzare?”.
Cercetările în acest sens (pentru rezolvarea problemei) capătă forme diverse în domenii (aparent) diferite, cum ar fi: comunicaţiile şi tehnologia informaţiei.
Una dintre cele mai spectaculoase aplicaţii este acum atât de familiar-ul compact-disc care utilizează codurile Reed-Solomon pentru a transmite sunetul clar şi fără eroare în ciuda prafului şi a zgârieturilor.
Încă de la începuturile comunicaţiilorau apărut erori şi de aici nevoia de a le rezolva. Din experienţa de fiecare zi ştim că vocea umană este destul de puternică să acopere pârâitul unei linii telefonice pe de o parte, iar pe de cealaltă parte poţi recupera mesajul transmis de la celălalt capăt al firului chiar dacă nu poţi auzi toate cuvintele- până la jumătate din ele –şi, la o adică, poţi cere să fie repetate.
De la apariţia transmisiei electronice sub formă de radio sau telegraf, oamenii au transmismesaje utilizând alte simboluri, de exemplu liniile şi punctele alfabetului Morse. Problema cheie a fost (şi rămâne) descoperirea unor căi ingenioase de a introduce redundenţa în transmisie astfel încât, chiar dacă este bruiată, cel care recepţionează să poată reface mare parte din mesaj, sau măcar să aibă posibilitatea de a cere retransmiterea mesajului.
Iată un exemplu rapid şi simplu: calculatoarele sunt utilizatoare de informaţii în binar (1 şi 0).
Să presupunem că vrem să trimitem un mesaj în: 1( însemnând DA ); şi 0 (însemnând NU) pe un „canal” (e.g. o linie telefonicâ, un transmiţător radio, sau un laser.)
Problema este că acest canal poate fi bruiat (din cauza zgârieturilor sau al altor cauze ) altfel spus apare posibilitatea ca 1 să apară în loc de 0 şi invers; ce facem?
Prima idee este să trimitem mesajul de două ori; astfel: dacă vrem ca cel de la celălalt capăt să înţeleagă 1 trimitem „cuvântul cod 11”. Dacă receptorul primeşte un mesaj de tipul „01” atunci el ştie că a apărut o eroare şi cere retransmiterea , atunci când este posibil.
Aşa că acest „cod cu repetiţie” care pe 1 îl recodifică în 11 şi pe 0 în 00 ne ajută să detectăm unele erori, nu toate. Pentru unele aplicatii acest sistem este suficient de bun.
Oricum, dacă primeşti un „01” stii că a survenit ogreşeală, der oare a fost selectată prima intrare de la un „1” sau a doua intrare de la un „0”? Nu prea avem cum să ne dăm seama deoarece „01” este la fel de aproape ,echidistant, am putea spune, şi de „00” şi de „11”.
Să încercăm acum să transmitem „000” şi „111” în loc de 0 respectiv 1.
In acest caz, dacă survine o singură eroare şi primeşti un „101”, poţi reface şirul (corect) trimis ca fiind „1” conform aşa numitului „vot majoritar”. Deci acest cod, nu numai că poate fi detectat, ba poate fi corectată eroarea , deoarece „101” este mai apropiat de „111” şi la mai mare distanţă de „000”.
Noţiunea de distanţă este „cheia” în încercările de a corecta eroarea. In încercarea de a construi un „COD” mergem pe ideia de a construi „cuvinte – cod” care să facă posibilă păstrarea echidistanţei faţă de fiecare din ele fără a prelungi mesajul mai mult decât ar fi necesar.

Scurt istoric

Istoria teoriei codurilor este strâns legată de dezvoltarea tehnologiei în linii şi puncte (motivul fiind codul Morse). Oricum nu se oate vorbi de o teorie a codurilor până în jurul anilor ‘40. Practic, codurile pentru corectare de erori au devenit o necesitate, numai după apariţia tehnologiei calculului digital.
Codurile pentru corectare de erori au fost iniţial descoperite sub formă abstractă în 1945, când Claude Shannon a demonstrat o teoremă (demonstrtă mai târziu) care spune există moduri de a codifica un mesaj , astfel încât, să poată fi transmis în siguranţă în condiţiile unui canal bruiat, demonstrând că nu te poţi încrede în „capacitatea” unui canal încercând să prea multă informaţie prea repede.
Prima construcţie a unui cod decorectare de erori, o dă matematicianul Richard Hamming de la laboratoarele „Bell”.
La puţin timp, Marcel Golay generalizează construcţia lui Hamming şi construieşte coduri corectoare de erori per cuvânt care utilizează p simboluri, pentru p- prim.

Elemente de bază

O definiţie formală a unui cod de corectare de erori poate fi: un cod de lungime n este o submulţime a tuturor şirurilor (vectorilor) posibile de n simboluri care are proprietatea că oricare două numere ale submulţimii (i.e. cuvinte cod) ele difera in cel putin d pozitii, minimul distantei codului. Dacă, numărul cuvintelor-cheie este M, atunci spunem că este un cod (n; M; d). Astfel, un cod (0; 1) se numeşte cod binar, iar un cod (00; 11) este un cod binar de lungime 2, cu două cuvinte-cheie şi distanţa minimă 2. Analog (000; 111) este un cod de lungime 3 cu distanţa minimă 3.
Căutăm un n cât mai mic (pentru viteză), M cât mai mare (pentru eficienţă) şi un d mare. Aceste obiective vin de cele mai multe ori în dicordanţă, de aceea o mare parte din teoria codurilor construieşte coduri care să echilibreze diferenţele între cele trei numere şi în acelaşi timp să fie uşor de folosit.
Aşa că, dacă un mesaj este transmis,atunci numărul erorilor este exact distanţa Hamming dintre vectorului primit şi vectorul original. Pentru a putea detecta erorile, vectorul primit nu trebuie să se suprapumă peste un alt mesaj. De aceea o MARE distanţă minimă este foarte importantă; dacă numărul erorilor este mai mic decât d, atunci putem cel puţin detecta tipul de eroare. Astfel, dacă numărul de erori este strict mai mic decât d/2 atunci vectorul receptat este cel mai apropiat de original.

Decodare

După ce am trimis un mesaj utilizând un cod, trebuie să decodăm vectorul primit la celălalt capăt. Intuitiv vom căuta mesajul cel mai apropiat de vectorul primit. Dacă avem un canal de transmisie cu o acurateţe de cel puţin 50% pentru fiecare bit trimis, atunci cel mai bun rezultat este cel care diferă de vectorul primit în cât mai puţine locuri, adică cel aflat la cea mai mică distanţă Hamming de el.

Construcţia unui cod

Codul cu dublă repetiţie are distanţa minimă 2 aşa că detectează o singură eroare. Evident există loc pentru improvizaţii. Dacă dorim să detectăm oeroare când transmitem mesajul „100” nu avem nevoie să transmitem întregul mesaj de două ori. Putem detecta eroarea dacă transmitem un „bi de paritate” după cum urmează.:transmitem un 0 sau 1 astfel încât mesajul primit să conţină un număr par de „1”.
În acest mod impunem o paritate mesajului. Dacă apare o singură eroare (să spunem că apare 1101 în loc de 1001) se va schimba numărul de 1-uri. Astfel, când vom introduce programul de verificare a parităţii pentru vectorul primit, adăugând apoi toate coordonatele, vom putea detecta eroarea.
O generalizare a acestui proces o putem scoate din codurile Hamming. Hamming a studiat problema încercând să găsească o cale de a corecta eficient o singură eroare.
Strategia lui Hamming a fost să impună paritatea pe porţiuni intercalate din vector astfel încât să acopere la maximum reducerea sprijinului.
În referatele următoare ne vom ocupa mai pe larg de: sistemul Hamming, de teorema lui Shennon dar mai ales de aplicaţiile codurilor Reed-Solomon, cu precădere în funcţionarea C.D. player-elor.

BIBLIOGRAFIA
Barg, Alexander „At the dawn of the theory of codes”, The Mathemetical Intelligencer, Vol. 15 (1993), No. 1, pp.20-26.
Conway, J.H., and N.J.A.S. Sloane, „ Sphere Packings, Lattices, and Groups”, editia a II-a, Springer-Verlag, 1993.
Hoeve H., J. Timmerman and L.B. Vries, „Error Correction and Concealement in the Compact Disc System”, Philips Thecnical Review, Vol. 40 (1980), No.6, pp.166-172.