MMC CD t5 04 Codigos Rs 2p

Códigos Reed Solomon (RS)
Variante no binaria de los códigos BCH

Códigos definidos sobre sı́mbolos de GF(pm )
k → n sı́mbolos Reed Solomon (m-tuplas de bits)
Longitud del código n = pm − 1
Son códigos de distancia mı́nima dmin = n − k + 1
Valor máximo posible (lı́mite de Singleton)
Diseño del código para corregir t errores
Obtención del polinomio generador g(x) agrupando 2t raı́ces
g(x) = (x − α) · (x − α2 ) · · · (x − α2t )
Coeficientes de g(x) en GF(2m ) (no binarios)

Sı́mbolos Reed Solomon
No hay raı́ces inútiles: mı́nima redundancia
MMC (UC3M) Comunicaciones Digitales Codificación de Canal 1 / 10
Codificación
Mensaje a codificar
Bloque de k sı́mbolos RS (m-tuplas de bits)
Representación polinómica b(x)
Grado k − 1
Coeficientes en GF(2m ) (no binarios)
Palabra codificada
Bloque de n sı́mbolos RS
Representación polinómica c(x)
Grado n − 1
Coeficientes en GF(2m ) (no binarios)
Codificación
c(x) = b(x) · g(x)

Ejemplo - Código RS(5, 7) - t = 1 error
Sı́mbolos sobre GF(23 )

(n = 2m − 1, m = 3) Polinomio generador
αj Polinomio Tupla
α−∞ = 0 0 000
α0 1 001
g(x) =(x − α) · (x − α2 )
α1 α 010
α2 α2 100
=x2 + (α2 + α) · x + (α + 1)
α3 α+1 011
α4 α2 + α 110
2
=x2 + α4 · x + α3
α5 α +α+1 111
α6 α2 + 1 101
Palabra mensaje b = 110 001 011 010 101

b(x) =(α2 + α) · x4 + 1 · x3 + (α + 1) · x2 + α · x + (α2 + 1) · 1
=α4 · x4 + x3 + α3 · x2 + α · x + α6
Codificación c = 110 011 110 000 111 101 100
c(x) = m(x) · g(x) = α4 · x6 + α3 · x5 + α4 · x4 + α5 · x2 + α6 · x + α2
Lı́mite de singleton
Máxima distancia mı́nima para un cósigo C(k, n)
dmin ≤ n − k + 1
Para códigos RS
dmin = 2t + 1 = grado(g(x)) + 1
Redundancia del código
n − k = grado(g(x)) = dmin − 1
Distancia mı́nima
dmin = n − k + 1

Decodificación de códigos Reed Solomon
Decodificación similar a códigos BCH binarios

Decodificación en cuatro pasos
Obtención del sı́ndrome
Obtención del polinomio localizador de errores Λ(x)
Encontrar las raı́ces de Λ(x)
Obtención del polinomio de error e(x)
Implementaciones algorı́tmicas
Algoritmo de Peterson-Gorenstein-Zierler
Complejidad escala con t2
Algoritmo de Berlekamp-Massey
Complejidad escala con t
Algoritmo de Forney para magnitudes de error
Obtención del sı́ndrome

Construcción del código: 2t raı́ces consecutivas
g(αa ) = g(αa+1 ) = · · · = g(αa+2t−1 ) = 0
Representación de la palabra codificada: c(x) = m(x) · g(x)
Para las palabras código
c(αa ) = c(αa+1 ) = · · · = c(αa+2t−1 ) = 0
Representación polinómica de la palabra recibida
n
n−1 n−2
r(x) = r[0] · x + r[1] · x + · · · + r[n − 1] · 1 = r[i] · xn−i
i=1
!
Sı́ndrome j (para la raı́z αj )

n n
j j n−i
sj = r(α ) = r[i] · (α ) = e[i] · (αj )n−i = αbj
i=1 i=1
! !
Polinomio de sı́ndrome
s(x) = sa · x + sa+1 · x2 + · · · + sa+2t−1 · x2t

Polinomio localizador de error
Polinomio cuyas raices identifican las posiciones de los

errores
Posiciones de los errores: i1 , i2 , ·iv con (v ≤ t)
Polinomio localizador de error
v
Λ(x) = 1 − αij · x = Λv · xv + Λv−1 · xv−1 + · · · Λ1 · x + 1
j=1
" # $
Polinomio de error: magnitud de los errores
e(x) = ei1 · xi1 + ei2 · xi2 + · · · + eit · xit

Cálculo de los coeficientes de los polinomios
Algoritmo de Peterson-Gorensten-Zierler (solución matricial)
Algoritmo de Berlekamp-Massey (solución iterativa)
Algoritmo de Forney (solución iterativa)
Algoritmo de Peterson-Gorenstein-Zierler
Sistema matricial de ecuaciones
s1 s2 s3 · · · st Λt st+1
Λt−1 st+2
     
Λt−2 st+3
 s2 s3 s4 · · · st+1     
.. .. ... .. ..
. . . .
     
 s3 s4 s5 · · · st+2     
Λ1 s2t
 · = 
st st+1 st+2 · · · s2t−1

 .. ..     
 . .     
i1 i2 i3 iv
α α α ··· α ei1 s1
2 2 2 2
ei2 s2
     
(αi1 ) (αi2 ) (αi3 ) · · · (αiv )

.. .. .. .. .. .. ..
. . . . . . .
v v v v
     
eiv sv
     
 · = 
(αi1 ) (αi2 ) (αi3 ) · · · (αiv )

     

Algoritmo de Berlekamp-Massey
Cálculo más eficiente del polinomio localizador Λ(x)

Algoritmo con t iteraciones
1 Inicialización: k = 0, Λ(0) (x) = 1, T (0) (x) = 1, L(0) = 0
L
2 (k) (k−1)
k = k + 1 y Z = sk − Λi sk−1
i=1
!
3 Si Z (k) = 0, ir a 7
4 Λ(k) (x) = Λ(k−1) (x) + Z (k) · [T (k) (x)]
5 Si 2L ≥ k, ir a 7
6 L = k − L y T (k) (x) = Λ(k−1) (x)/Z (k)
7 T (k) (x) = x · T (k) (x)
8 Si k < t volver a 2
Algoritmo de Forney
Cálculo de los coeficientes del polinomio de error e(x)

Más eficiente que la solución matricial
Obtención mediante división de polinomios
αik · Ω(α−ik )
eik =
Λ" (α−ik )
Polinomio Ω(x)
Ω(x) = Λ(x) · [1 + s(x)]
Polinomio Λ" (x)

Derivada de Λ(x)

MMC CD t5 04 Codigos Rs 2p

Cargado por

Copyright:

Formatos disponibles

MMC CD t5 04 Codigos Rs 2p

Cargado por

Información del documento

Descripción original:

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

MMC CD t5 04 Codigos Rs 2p

Cargado por

Copyright:

Formatos disponibles

Códigos Reed Solomon (RS)

Variante no binaria de los códigos BCH

Coeficientes de g(x) en GF(2m ) (no binarios)

MMC (UC3M) Comunicaciones Digitales Codificación de Canal 1 / 10

MMC (UC3M) Comunicaciones Digitales Codificación de Canal 2 / 10

Sı́mbolos sobre GF(23 )

Palabra mensaje b = 110 001 011 010 101

Máxima distancia mı́nima para un cósigo C(k, n)

Redundancia del código

MMC (UC3M) Comunicaciones Digitales Codificación de Canal 4 / 10

Decodificación similar a códigos BCH binarios

MMC (UC3M) Comunicaciones Digitales Codificación de Canal 5 / 10

Obtención del sı́ndrome

Sı́ndrome j (para la raı́z αj )

MMC (UC3M) Comunicaciones Digitales Codificación de Canal 6 / 10

Polinomio cuyas raices identifican las posiciones de los

Polinomio de error: magnitud de los errores

e(x) = ei1 · xi1 + ei2 · xi2 + · · · + eit · xit

Sistema matricial de ecuaciones

st st+1 st+2 · · · s2t−1

(αi1 ) (αi2 ) (αi3 ) · · · (αiv )

(αi1 ) (αi2 ) (αi3 ) · · · (αiv )

MMC (UC3M) Comunicaciones Digitales Codificación de Canal 8 / 10

Cálculo más eficiente del polinomio localizador Λ(x)

MMC (UC3M) Comunicaciones Digitales Codificación de Canal 9 / 10

Cálculo de los coeficientes del polinomio de error e(x)

Ω(x) = Λ(x) · [1 + s(x)]

Polinomio Λ" (x)

MMC (UC3M) Comunicaciones Digitales Codificación de Canal 10 / 10

También podría gustarte