Reed-Solomon

Reed-Solomon és un algorisme de correcció d'errors. Aquest codi està dintre dels codis anomenats FEC (Forward Error Correction), això vol dir que és el receptor el que s'encarrega de corregir els errors, no pas l'emissor. Per dur a terme aquesta tasca, utilitza bytes de redundància. S'utilitza en transmissions digitals.

Una manera fàcil per definir que fa aquest codi seria: La informació es divideix en parts. Dins de cada paquet introduïm bytes d'informació redundant(X). Això permet al receptor poder recuperar X/2 bytes d'informació útil.

Per exemple, en DVB dividim la informació en 188bytes. A cada paquet de 188 bytes, introduïm 16 bytes d'informació redundant. Això vol dir que el receptor pot recuperar la informació si s'han malmès 8 bytes qualsevols (o menys) del total de 188 bytes.

El codi va ser inventat per Irving S. Reed i Gustave Solomon l'any 1960.

Codis Reed-Solomon

Els codis Reed-Solomon són el codi introduït per Irving S. Reed i Gustave Solomon. El codi Reed-Solomon és una subclasse de codis BCH no binaris. El codificador dels codis Reed-Solomon difereix d'un codificador binari en què opera amb diversos bits en lloc de bits individuals.

Així, bàsicament, els codis Reed-Solomon ajuden a recuperar missatges danyats que s'estan transferint a través d'una xarxa. En els codis Reed-Solomon, tenim:

El codificador de codis Reed-Solomon rep dades i abans de transferir-les a la xarxa sorollosa afegeix alguns bits de paritat amb els nostres bits de dades originals.

D'altra banda, disposem d'un descodificador de codis Reed-Solomon que detecta missatges danyats i els recupera dels errors.^[1]

Paràmetres del codi Reed-Solomon

El codi (n, k) s'utilitza per codificar símbols de m bits.
La longitud del bloc (n) ve donada per símbols de 2m-1.
En els codis Reed-Solomon, la mida del missatge ve donada per (n-2t) on {{{1}}}.
La mida de la comprovació de paritat ve donada pels símbols = (n-k) o 2t.
La distància mínima (a) ve donada per = (2t+1).
La mida del missatge és de k bits.^[2]

Reed-Solomon Original

La versió pensada per Irving S. Reed i Gustave Solomon era molt senzilla. Però tenia un problema, es va comprovar que a la pràctica era ineficient si els valors dels paràmetres eren grans.

Definició Original

La idea és que a partir d'una informació, creem un polinomi. Inicialment fixem un cos finit C_q, un element primitiu α∈C_q i finalment un enter 1≤N≤q-1. Considerem la paraula

m= (m₀,m₁,m₂,...m_α^q-2) la qual identificarem amb el polinomi

\mathbf {m(x)} =\left(m_{0}+m_{1}x,m_{2}x^{2}+...+m_{N-1}x^{N-1}\right)

A partir d'aquí, es tracta de codificar m pel vector que conté les avaluacions de m(x)en cadascun dels elements C_q:

Vector-> V=(m(α⁰),m(α¹),m(α²),...,m(α^q-2))

Si considerem el teorema d'interpolació només existeix un únic polinomi de grau ≤N-1 que passi per N punts donats de C_q²d'abcisses. Qualsevol Ncoordenades de la paraula codificada V són suficients per recuperar la informació inicial m. Llavors, encara que es perdin alguns símbols o s'hagin corromput alguns, la paraula m es podrà recuperar sempre que en quedin com a mínim N símbols correctes.

La finalitat és que, si el nombre d'errors és prou petit, a partir d'aquest métode podrem decodificar la informació rebuda al receptor i alhora corregir-la, recuperant la informació enviada per l'emissor tal com ha estat enviada.

Per tant, finalment definim el codi Reed-Solomon com:

RS_q(N)={(m(α⁰),m(α¹),m(α²),...,m(α^q-2))∈ C_q^q-1}

Definició Actual

La definició inicial d'Irving Reed i Gustave Solomon necessitava moltes interpolacions per tal de poder corregir la informació, ja que per exemple si utilitzem els valors q=16 i N=7, és necessari realitzar 6435 interpolacions, fet que treu eficiència al codi inicial.

Per aquesta raó es va decidir utilitzar un mètode més eficient, mitjançant la Transformada Discreta de Fourier. Considerem C_q un cos finit, un element primitiu α∈C_q i finalment imposem N=q-1. Consideri un altre cop la paraula m i l'avaluació en totes les potències de α, tal com s'ha fet en el cas original. Ara definim una matriu tal i que el nombre de files i columnes van de 0 a N-1. Per exemple: Considerem N=5

C_{\alpha }={\begin{pmatrix}1&1&1&1&1\\1&\alpha &\alpha ^{2}&\alpha ^{3}&\alpha ^{4}\\1&\alpha ^{2}&\alpha ^{4}&\alpha ^{6}&\alpha ^{8}\\1&\alpha ^{3}&\alpha ^{6}&\alpha ^{9}&\alpha ^{12}\\1&\alpha ^{4}&\alpha ^{8}&\alpha ^{12}&\alpha ^{16}\\\end{pmatrix}}

El procés d'avaluació coincideix amb la multiplicació per C_α. Llavors ho podem expressar com:

m=\sum _{i=0}^{N-1}{m_{i}}\alpha ^{ji}

D'aquesta manera és molt més fàcil i més eficient.

Aplicacions

Dispositiu d'emmagatzematge de dades

L'algorisme de correcció d'errors Reed-Solomon és àmpliament utilitzat en sistemes d'emmagatzematge massius per corregir els errors relacionats amb els efectes dels mitjans.

La codificació Reed-Solomon és un component clau del disc compacte. Va ser el primer ús de la codificació correcta de correcció d'errors en un producte de consum massiu, i DAT i DVD utilitzen esquemes similars. En el CD, dues capes de codificació Reed-Solomon separades per un descentrador de 28 voltes produeixen un esquema anomenat Cross-Interleaved Reed-Solomon Coding (CIRC). El primer element d'un decodificador CIRC és un codi interior Reed-Solomon (32,28) relativament feble, reduït per un codi (255,251) i amb símbols de 8 bits. Aquest codi pot corregir fins a 2 errors de bytes per bloc de 32 bytes. Més important encara, marca com esborrar tots els blocs no corregits, és a dir, blocs amb més de 2 errors de bytes. Els blocs descentrats de 28 bytes, amb indicacions d'esborrat, són distribuïts pel descentrenador a diferents blocs del codi extern (28,24). Gràcies al descentrador, un bloc de 28 bytes esborrat del codi intern es converteix en un únic byte esborrat en cada un dels 28 blocs de codi extern. El codi extern corregeix fàcilment aquest aspecte i pot gestionar fins a 4 esborranys per bloqueig.

El resultat és un CIRC que pot corregir completament l'error que arribi fins a 4000 bits o uns 2,5 mm a la superfície del disc. Aquest codi és tan fort que la majoria dels errors en la reproducció de CD són causats, sens dubte, per errors de seguiment que fan que el làser sigui el rastre, no per ràfegues d'errors incorregibles.

Els DVD utilitzen un esquema similar, però amb blocs molt més grans, un codi intern (208,192) i un codi extern (182,172).^[3]

La correcció d'errors de Reed-Solomon també s'utilitza en fitxers de seguretat que normalment es publiquen als fitxers multimèdia que acompanyen a USENET. El servei d'emmagatzematge en línia Wuala (interromput el 2015) també utilitza Reed-Salomon quan es trenquen els fitxers.

Codi de barres

Fins a codis de barres de dues dimensions com PDF-417, MaxiCode, Datamatrix, QR Code, i Aztec Code utilities el Reed–Solomon per permetre millorar la lectura dels codis tot i estar parcialment espatllats. Quan l'escànner de codis de barres no pot reconèixer el símbol del codi, el considerarà un esborrany. Tot i que no és tan comú com en els codis d'una dimensió, també s'utilitza per la simbologia PostBar.

Transmissió de dades

Les formes especialitzades del codi Reed-Solomon (especialment Cauchy-RS i Vandermonde-RS), poden ser usades per superar la poca confiança de la transmissió de dades per sobre els canals de correcció. El procés de codificació assumeix el codi de RS (N, K), que es refereix a N la llargada de la paraula clau en N símbols, on cada un emmagatzema K símbols de dades, que són enviats posteriorment mitjançant un canal de correcció.

Qualsevol combinació de K paraules clau rebuda és suficient per reconstruir la totalitat de N paraules clau. El percentatge de codi generalment s'estableix en 1/2, tret que la probabilitat d'esborrat del canal es pugui modelar adequadament i es considera que és menys. En conclusió, N és generalment 2K, el que significa que almenys la meitat de totes les paraules clau enviades s'han de rebre per tal de reconstruir totes les paraules clau enviades.

Els codis Reed-Solomon també s'utilitzen en els sistemes xDSL i en les especificacions del protocol de comunicacions espacials de CCSDS's com a forma de correcció d'errors avançada.

Transmissió de l'espai

Una aplicació significativa del codo Reed-Solomon és codificar les imatges digitals reenviades per la sonda espacial Voyager.

La Voyager va introduir aquest codi per consolidar els codis de relleu, una pràctica que s'ha estès molt en les profunditats de l'espai i en les comunicacions per satèl·lits, com per exemple la transmissió digital directa.

Els decodificadors Viterbi tendeixen a produir errors en petits brots. Corregir aquests brots seria un dels usos que se li podria donar al codi Reed-Solomon. Versions més modernes del descodificador Viterbi o del Reed-Solomon han estat i són usades per Mars Pathfinder, Galileo, Mars Exploration Rover i les missions de Cassini.

Aquests codis ara han estat reemplaçats per uns de més potents.

Vegeu també

Referències

↑ «Reed Solomon Codes: A Classical Explanation» (en anglès americà). [Consulta: 5 gener 2023].
↑ «reed-solomon codes». [Consulta: 5 gener 2023].
↑ Immink, K. A. S. "Reed–Solomon Codes and the Compact Disc", in Wicker, Stephen B.; Bhargava, Vijay K., Reed–Solomon Codes and Their Applications, IEEE Press, ISBN 978-0-7803-1025-4.

A Wikimedia Commons hi ha contingut multimèdia relatiu a: Reed-Solomon

[1] «Reed Solomon Codes: A Classical Explanation» (en anglès americà). [Consulta: 5 gener 2023].

[2] «reed-solomon codes». [Consulta: 5 gener 2023].

[3] Immink, K. A. S. "Reed–Solomon Codes and the Compact Disc", in Wicker, Stephen B.; Bhargava, Vijay K., Reed–Solomon Codes and Their Applications, IEEE Press, ISBN 978-0-7803-1025-4.

[1]

[2]

[3]