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ó és divideix en parts. Dins de cada paquet introduïm bytes d'informació redundant(X). Aixó permet al receptor poder recupera 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

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'un 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 peti, 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 i 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 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 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 i 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?

S'utilitza aquest codi:

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

Vegeu També

• Detecció d'errors
• Teoria de la informació