Reed-Solomon

Reed-Solomon és un còdic cíclico no binario i constituïx una subclasse dels còdics BCH. Els còdics cíclicos són una subclasse dels còdics de bloc estàndar de detecció i correcció d'errors que protegix l'informació contra errors en les senyes transmeses sobre un canal de comunicacions. Este tipo de còdic pertany a la categoria FEC (Forward Error Correction), és dir, corrig les senyes alterades en el receptor i per a això utilisa uns bits adicionals que permeten esta recuperació a posteriori.

El còdic va ser inventat per Irving S. Reed i Gustave Solomon (d'ahí el seu nom) en l'any 1960. Este còdic es troba actualment aplicat en àrees com els CD, telefonia mòvil i sondes espacials (la sonda Galileo a Júpiter en 1989, la sonda Magallanes a Venus eixe mateix any o la sonda Ulises al Sol en 1990, per citar alguns eixemples). També és de destacar l'ocupació del còdic Reed-Solomon en les comunicacions per satèlit Digital Video Broadcasting (DVB), en la transmissió digital de televisió ISDB-T, en la ràdio digital DAB+, aixina com en els sistemes xDSL de comunicació per cable, i en els còdics QR.

Característiques

Este còdic es forma sobre la base de grups de bits que es denominen símbols. El còdic Reed-Solomon treballa en els símbols en lloc d'en els bits individuals.

Un símbol és una seqüència de "m" bits individuals que apareixen en série. Un símbol és erròneu quan a lo manco un bit del símbol té error.

---

El còdic Reed-Solomon té les següents característiques:

• Cada símbol està constituït per "m" bits consecutius agrupats.
• Cada paraula-còdic consta de "k" símbols d'informació (en lloc de bits), i "r" símbols de paritat.
• La llongitut de la paraula-còdic és: $n=k+r$ símbols,(llongitut=$nm$ expressada en n.º de bit).
• S'establix la relació: $n=2^m-1$ entre la llongitut de la paraula còdic (n) i el número de símbols ($2^m$).
• És capaç de corregir errors en "t" símbols, a on $t=r/2$.

Reed-Solomon Original

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

Definició Original

L'idea és que a partir d'una informació, vàrem crear un polinomi. Inicialment fixem un cos finito C_q, un element primitiu α∈C_q i finalment un sancer 1≤N≤q-1. Considerem la paraula

m= (m₀,m₁,m₂,...m_α^q-2) la qual identificarem en el polinomi $𝐦\mathbf{(}𝐱\mathbf{)}=(m_0+m_{1}x,m_2{x}^2+\dots +m_{N-1}{x}^{N-1})$

A partir d'ací, es tracta de codificar m pel vector que conté les evaluacions de m(x)en cada u dels elements C_q:

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

Si considerem la teorema d'Interpolació solament existix un únic polinomi de grau ≤N-1 que passe per N punts donats de C_q²d'abscisses. Qualsevol N coordenades de la paraula codificada V són suficients per a recuperar l'informació inicial m. Llavors, encara que es pergues alguns símbols o s'hagen corrompido alguns, la paraula m es podrà recuperar sempre que queden com a mínim N símbols correctes. La finalitat és que, si el número d'errors és suficientment menut, a partir d'este método podrem descodificar l'informació rebuda en el receptor i al mateix temps corregir-la, recuperant l'informació enviada per l'emissor tal i com ha segut enviada. Per lo tant, finalment definim el còdic Reed-Solomon com:

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

Vore també

• Algoritme de Berlekamp-Welch
• Teoria de l'informació
• Còdics detectors i correctors d'error