Diferència entre revisions de la pàgina «Reed-Solomon»

Sense canvi de mida ,  fa 1 any
Canvis menors, neteja, replaced: de I → d'I AWB
m (Aplicant la plantilla {{ISBN}} per evitar l'enllaç màgic d'ISBN)
(Canvis menors, neteja, replaced: de I → d'I AWB)
'''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 [[byte]]s 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.
 
== Reed-Solomon Original ==
 
=== Definició Original ===
La idea és que a partir d'una informació, creem un polinomi. Inicialment fixem un cos finit C<sub>q</sub>, un element primitiu α∈C<sub>q</sub> i finalment un enter 1≤N≤q-1. Considerem la paraula
 
'''m'''= (m<sub>0</sub>,m<sub>1</sub>,m<sub>2</sub>,...m<sub>α<sup>q-2</sup></sub>) la qual identificarem amb el polinomi
: <math>\mathbf{m(x)} = \left( m_0+m_1x,m_2x^2+ ...+m_{N-1}x^{N-1} \right)</math>
 
 
A partir d'aquí, es tracta de codificar '''m''' pel vector que conté les avaluacions de m(x)en cadascun dels elements C<sub>q</sub>:
 
== Definició Actual ==
La definició inicial de 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<sub>q</sub> un cos finit, un element primitiu α∈C<sub>q</sub> 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
 
D'aquesta manera és molt més fàcil i més eficient.
 
 
== Aplicacions ==
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 &nbsp;mm a la superfície del disc. Aquest codi és tan fort que la majoria dels errors en la reproducció de [[CD-ROM|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).<ref>{{Ref-publicació|cognom=Immink, K. A. S.|nom=|article=|publicació="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}}|url=|data=|pàgines=}}</ref>
* [[Teoria de la informació]]
 
== Referències ==
{{Referències}}
{{Commonscat}}
356.486

modificacions