Reed-Solomon

De Viquipèdia
Dreceres ràpides: navegació, cerca

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.

Reed-Solomon Original[modifica | modifica el codi]

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[modifica | modifica el codi]

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

m= (m0,m1,m2,...mαq-2) la qual identificarem amb el polinomi

\mathbf{m(x)} = \left( m_0+m_1x,m_2x^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 Cq:

Vector-> V=(m(α0),m(α1),m(α2),...,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 Cq2d'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:

RSq(N)={(m(α0),m(α1),m(α2),...,m(αq-2))∈ Cqq-1}

Definició Actual[modifica | modifica el codi]

La definició inicial de 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 Cq un cos finit, un element primitiu α∈Cq 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.


On s'utilitza?[modifica | modifica el codi]

S'utilitza aquest codi:

  • DVB (Digital Video Broadcasting).
  • TDT.
  • En sistemes d'emmagatzematge com el DVD.
  • DAB+ (Digital Audio Broadcasting plus).


Vegeu També[modifica | modifica el codi]