Cod Reed-Solomon

De la Wikipedia, enciclopedia liberă.
Salt la navigare Salt la căutare

În teoria codurilor , codul Reed-Solomon este un tip de cod liniar (ciclic) non-binar de detectare și corectare a erorilor inventat de Irving S. Reed și Gustave Solomon .

Este folosit pentru a corecta erorile de flux în mai multe aplicații importante de comunicații digitale și stocare de date . Utilizările sale variază de la electronice de larg consum la comunicații în spațiul profund.

Se bazează pe supra - eșantionarea unui polinom construit din datele de transmis. Prin urmare, polinomul este calculat în mai multe puncte decât ar fi suficient pentru a-l identifica în mod unic; valoarea acestor puncte este transmisă sau înregistrată. La recepție sau citire, este posibilă reconstituirea polinomului original și, în consecință, a datelor, chiar și în prezența erorilor.

Istorie

Codul a fost inventat în 1960 de Irving S. Reed și Gustave Solomon , care la acea vreme lucra la laboratorul Lincoln al Massachusetts Institute of Technology (MIT). Lucrarea a fost publicată în articolul coduri polinomiale pe unele câmpuri finite (Coduri polinomiale peste anumite câmpuri finite). [1]

Dar în 1960, tehnologia digitală nu era suficient de avansată pentru a realiza acest concept. Aplicarea codurilor Reed-Solomon a fost posibilă în 1969 , datorită muncii lui Elwyn Berlekamp și James Massey , care au inventat un algoritm eficient de decodare .

În 1977, codurile Reed-Solomon au fost aplicate admirabil în programul spațial Voyager , sub formă de coduri înlănțuite pentru controlul erorilor .

Teoria de bază

Ideea cheie din spatele codului Reed-Solomon este de a vedea datele care trebuie „protejate” ca un polinom . Algebra liniară spune că un număr k de puncte distincte determină în mod unic un polinom de grad cel mult k -1.

Polinomul este apoi „codificat” prin calcularea mai multor puncte ale sale, iar valorile acestor puncte sunt cele transmise de fapt. În timpul transmisiei, unele dintre aceste puncte pot fi corupte. Din acest motiv se transmit k + n puncte, n fiind datele adăugate pentru protecția informațiilor. Receptorul analizează punctele primite și determină polinomul de grad k -1 care aproxima cel mai bine succesiunea punctelor primite. Atâta timp cât „nu prea multe” puncte sunt primite corupte, receptorul poate reconstrui ceea ce a fost polinomul original și apoi poate decoda datele. Cu toate acestea, în cazul unui număr excesiv de erori, decodificatorul reconstruiește un polinom „similar” cu cel de pornire. Deci algoritmul arată o dependență slabă de numărul de erori, nu există un număr de erori dincolo de care reconstrucția eșuează, dar algoritmul reconstituie întotdeauna un polinom probabil, probabilitatea polinomului reconstituit depinde de numărul de erori primite.

Operațiune

În timpul transmiterii oricărui semnal analog sau digital, numeroși factori externi, cum ar fi zgomotul electric , interferențele , liniile de pe suprafața CD / DVD-ului, abraziuni sau pete pe codurile de bare, creează o serie de erori care pot compromite transmiterea sau citirea corectă a datele .

Funcționarea codului Reed-Solomon poate fi rezumată în următoarele acțiuni:

  • Emiterea datelor
  • Codificare Reed-Solomon
  • Transmiterea datelor (cu posibile erori)
  • Decodare Reed-Solomon ( detectarea și corectarea erorilor )
  • Recepția corectă a datelor

De exemplu, la arderea CD-urilor audio, secvența mostrelor ( PCM pe 16 biți) este împărțită în blocuri de 24 octeți cărora li se aplică un cod de corecție Reed-Solomon de 4 octeți care permite corectarea a 4 erori în poziții cunoscute sau 2 erori în poziții necunoscute pentru fiecare bloc. Ulterior, 112 blocuri adiacente sunt grupate și schimbate între ele, astfel încât două blocuri succesive din fluxul de date să nu fie niciodată aproape unul de altul. Acest aranjament ( intercalare ) servește pentru a se asigura că erorile consecutive de pe CD (datorate zgârieturilor sau amprentelor digitale) în faza de citire sunt împrăștiate de-a lungul fluxului de date reconstruit, crescând astfel șansele de corectare. [2]

Aplicații

Codul Reed-Solomon este utilizat în tehnologiile de comunicații și informații pentru codificarea și decodarea datelor.

Instrumentul este, de asemenea, utilizat în unele aplicații pentru dispozitive cu funcții de scanare , cum ar fi nintendo e-Reader sau telefoane mobile și smartphone-uri .

Stocare a datelor

În electronica de larg consum, codul este utilizat pentru a corecta erorile de decodare cauzate de defecte în mediile de stocare precum DAT , CD , DVD , disc Blu-ray și standarde RAID .

Codul Reed-Solomon este, de asemenea, utilizat în codurile de bare Postbar sau codurile de bare bidimensionale, cum ar fi Codul Aztec , Codul QR , [3] Matricea de date , MaxiCode și PDF-417 , pentru restaurarea datelor în cazul în care o parte din codul a fost deteriorat, permițând o citire corectă.

Transmiterea datelor

În domeniul telecomunicațiilor, codul Reed-Solomon este utilizat pentru transmiterea și recepția datelor în comunicațiile prin satelit ; în conexiuni în bandă largă și wireless, cum ar fi DSL sau WiMAX ; în sistemele de transmisie ATSC și Digital Video Broadcasting ; în transmisia radio în codificare DAB + [4] și pentru a ocoli natura nesigură a datelor transmise pe canalele de comunicație BEC .

Prima aplicație importantă în domeniul comunicațiilor prin satelit a fost cea utilizată pentru decodarea imaginilor digitale trimise de sonda spațială Voyager .

În cadrul Comitetului consultativ pentru sistemele de date spațiale și sistemele de specificații ale protocolului de comunicații spațiale , sunt utilizate diferite aplicații pentru estimarea și eliminarea erorilor ( FEC ).

Alte versiuni ale codului sunt utilizate în misiunile spațiale Mars Pathfinder , Galileo , Mars Exploration Rover și Cassini , care operează între aproximativ 1 și 1,5 decibeli din limita capacității canalului .

Notă

  1. ^ Irving S. Reed , Gustave Solomon . Coduri polinomiale asupra anumitor câmpuri finite . Journal of the Society for Industrial and Applied Mathematics ( SIAM ), iunie 1960. Vol. 8 (2), pp 300-304. DOI 10.1137 / 0108018
  2. ^ Kees Immink, Reed - Solomon Codes and the Compact Disc , în Reed - Solomon Codes and their Applications , Wiley-IEEE Press, 1994.
  3. ^(EN) Specificația conturului codului QR Denso-Wave. Accesat la 30 iulie 2010
  4. ^ Sergio Cimmino, Dab, radio digital: revoluția care așteaptă Italia , Ci Siamo, 30 ianuarie 2019.

Bibliografie

Elemente conexe

Alte proiecte

linkuri externe

Adus de la „ https://it.wikipedia.org/w/index.php?title=Codice_Reed-Solomon&oldid=104459420 ”