REED
SOLOMON
OBJETIVO
Realizar un análisis sobre la teoría de código de Reed Solomon,
sus propiedades y ejemplos de aplicación.
Índice
Códigos de Reed Solomon
• Introducción.
• Características Generales
• Aplicaciones
• Definición
• Codificación RS
• Decodificación RS
• Ejercicios.
Introducción
Al enviar información a través de un canal de comunicación no
confiable y ruidoso se puede presentar errores en la recepción, lo cual
es inadmisible si se desea brindar una comunicación confiable y de
calidad entre un emisor y un receptor, siendo de gran utilidad el uso
de técnicas de codificación para el control de errores. Reed Solomon
es un código usado para la detección y corrección de errores. Estos no
solo son de gran relevancia por su capacidad para corregir largas
ráfagas de errores y de símbolos borrados, sino también porque se
conoce para ellos un algoritmo de decodificación
computacionalmente eficiente llamado el algoritmo de Berlekamp–
Massey.
Características de los Códigos Reed Solomon:
Especialmente útiles en presencia de errores a
ráfagas.
Presenta una redundancia moderada y una gran
capacidad de corrección (se pueden llegar a corregir
hasta 𝑡 símbolos erróneos en un bloque,
simplemente añadiéndole 2𝑡 símbolos adicionales )
Muy utilizados en telecomunicaciones
conjuntamente con otras técnicas que sean mas
robustas frente a errores aislados.
Aplicaciones:
Su primera aplicación significativa fue la codificación de imágenes
digitales en la sonda espacial Voyager. En la actualidad tiene un amplio
rango de aplicaciones en comunicaciones digitales y es usado para
corregir errores en muchos sistemas de comunicación como:
● Wifi, Wimax , CDs y sondas espaciales
● La televisión digital de alta definición.
● Los grabadores y reproductores de discos
compactos de audio y vídeo (DVD).
Definición:
Los códigos de Reed Solomon son códigos de tipo no binario.
Así con un código RS(n, k),a partir de un bloque de datos de
entrada de 𝑛 símbolos, se genera otro de salida de 𝑘 símbolos
que contienen a los 𝑛 anteriores mas 𝑛 − 𝑘 símbolos de
chequeo, y donde cada uno de estos símbolos contiene 𝑚 bits.
• 𝑛 = 2𝑚 − 1
Definición:
Los códigos Reed Solomon se representan como
𝑹𝑺 𝒏, 𝒌
Donde:
• 𝒏: número de símbolos a la salida del codificador (longitud de la
palabra código).
• 𝑲: número de símbolos de información que van a ser codificados.
• 𝒕 = (𝑛 − 𝑘)/2 ∶ número máximo de errores que puede corregir el
código.
Ratio y capacidad de corrección de códigos RS:
Como a partir de un boque de 𝑛 símbolos se genera uno de 𝑘
𝑘
símbolos, se dice que el ratio del código es 𝑟 = , este da una idea de
𝑛
la redundancia. En general, no son códigos de gran redundancia y, sin
embargo su capacidad de corrección de errores es bastante grande.
Su distancia minima esta definida como 𝑑𝑚𝑖𝑛 = 2𝑡 + 1 donde:
𝟐𝒕 = 𝑛 − 𝑘 ∶ número de símbolos de paridad añadidos dentro de los
n símbolos.
Ratio y capacidad de corrección de códigos RS:
Como a partir de un boque de 𝑛 símbolos se genera uno de 𝑘
𝑘
símbolos, se dice que el ratio del código es 𝑟 = , este da una idea de
𝑛
la redundancia. En general, no son códigos de gran redundancia y, sin
embargo su capacidad de corrección de errores es bastante grande.
Su distancia minima esta definida como 𝑑𝑚𝑖𝑛 = 2𝑡 + 1 donde:
𝟐𝒕 = 𝑛 − 𝑘 ∶ número de símbolos de paridad añadidos dentro de los
n símbolos.
Consideraciones RS:
Si los errores no ocurren en forma de ráfagas y están dispersos de
forma mas aleatoria, podrían corromper un mayor numero de
símbolos, por ello los códigos RS son bastante vulnerables, por eso lo
ideal es aplicarlos solo para corregir ráfagas de errores.
En la elección de un determinado código RS se debe tener en cuenta lo
siguiente:
𝑘
• Al disminuir el ratio la redundancia y la complejidad de calculo
,
𝑛
aumentan.
• Al aumentar el ratio, también aumenta la tasa de error final
obtenida.
Codificación Reed Solomon:
La codificación tiene como función principal generar la palabra código,
para esto la codificación sistemática añade 𝑛 − 𝑘 símbolos de paridad
a la palabra original que ingresa al codificador, así ingresan k símbolos
de información y salen n símbolos y esta es la palabra código. Los
símbolos de paridad se los calcula multiplicando la palabra original por
el polinomio 𝑋 𝑛−𝑘 y este resultado se lo divide para el polinomio
generador 𝑔(𝑥), el residuo de esta división es el conjunto de los
símbolos de paridad que se añade a la palabra original.
Codificación Reed Solomon:
El polinomio generador es un polinomio de grado 𝑋 𝑛−𝑘 sobre el
campo de Galois, cuyo valor dependerá del campo sobre el que se esté
trabajando. El polinomio generador 𝑔(𝑥) de manera general se lo
calcula de la siguiente manera:
𝑔 𝑥 = 𝑥 − 𝛼 𝑖 𝑥 − 𝛼 𝑖+1 … . (𝑥 − 𝛼 𝑖+2𝑡 )
Campo de Galois:
Un campo finito de q elementos, todo campo finito siempre tiene un
elemento primitivo, 𝛼, a partir del cual se representan los demás
elementos, como potencia del elemento:
𝑓 =∝ 𝑥−∝1 𝑛1 … 𝑥−∝𝑘 𝑛𝑘
Cada elemento se determina como
𝑞 = 2𝑚
q: tamaño del campo
m: grado del campo
Donde el campo de Galois se representa como 𝐺𝐹(2𝑚 )
Polinomios Primitivo de Galois:
Lista de polinomios primitivos para
3 ≤ 𝑚 ≤ 10
Campo de Galois:
Por ejemplo para un m=3 se tiene GF(8), como m=3, cada elemento
del campo Q tendrá 3 bits, por ejemplo tomando de la lista el
polinomio correspondiente 𝑋 3 + 𝑋 + 1 = 0 se remplaza ∝, entonces :
∝3 =∝+1
Este es el elemento 𝑞𝑖 del campo de Galois
∝3 = [0 1 1]
Así a partir de este se pueden calcular los elementos restantes del
campo
∝4 =∝∗∝3 =∝ ∝ +1 =∝2 +∝→ [1 1 0]
Campo de Galois:
Codificación Reed Solomon:
La palabra de código se genera de 𝑐(𝑥) = 𝑔(𝑥) ∗ 𝑖(𝑥), donde g(x) es el
polinomio generador, 𝑖(𝑥) es el bloque de información, 𝑐(𝑥) es una
palabra de código válida.
El primer paso corresponde a la definición del campo de Galois para la
codificación, el cual estará definido en función de la longitud del
símbolo entiéndase m bits/símbolo, el cual permite conocer el
polinomio reducible del campo de Galois 𝐺𝐹(2𝑚 ). Las bases teóricas
que sustentan este codificador están dadas por el polinomio en su
forma general:
Codificación Reed Solomon:
𝑛−𝑘−1
𝑔 𝑥 = ෑ 𝐺 𝑥 − 𝛼 ℎ𝑥 𝑒𝑚𝑝𝑖𝑒𝑧𝑎 𝑒𝑙 𝑔𝑒𝑛𝑒𝑟𝑎𝑑𝑜+𝑖
𝑖=0
Al expandir el polinomio se obtiene la Ecuación
𝑔 𝑥 = 𝐺𝑛−𝑘−1 𝑥 𝑛−𝑘−1 + 𝐺𝑛−𝑘−2 𝑥 𝑛−𝑘−2 + ⋯ + 𝐺1 𝑥 + 𝐺0
Donde:
N: longitud de la palabra codificada (en símbolos)
K: longitud del mensaje codificado (en símbolos)
M: longitud del símbolo (bits)
Decodificación Reed Solomon:
El proceso de decodificación consiste en tomar la palabra enviada por
el codificador y recuperar la palabra original. Si la palabra que se recibe
tiene errores, el código Reed Solomon se encargara de detectar y
corregir los errores que se produjeron en la transmisión, como este
proceso es el inverso de la codificación ingresaran n símbolos al
decodificador y se obtendrán los k símbolos correspondientes al
mensaje original que se envió.
Calculo del síndrome
La manera más sencilla de calcular el síndrome es evaluar la palabra
codificada 𝑐(𝑥) en cada una de las raíces del polinomio generador
𝑔(𝑥), se necesitan 2𝑡 síndromes para poder detectar y corregir t
errores, con esto se calculará el polinomio síndrome 𝑆(𝑥), que
permitirá determinar si la palabra código recibida tienen errores o no.
El cálculo del polinomio síndrome se lo puede expresar
matemáticamente de la siguiente manera:
𝑆𝑖−1 = 𝑐 𝛼 𝑖 , 𝑖 = 1, 2, 3
𝑆 𝑥 = 𝑆0 + 𝑆1 𝑋 + 𝑆2 𝑋 2 + . . . + 𝑆2𝑡−1 𝑋 2𝑡−1
Calculo del síndrome
Si el polinomio síndrome es distinto de cero, esto indica que existen
errores en la palabra recibida por lo que se deberá iniciar el proceso de
detección y corrección de errores.
Localizador de errores
Encontrar el lugar del símbolo erróneo implica resolver de forma
simultánea ecuaciones con t incógnitas. Existen varios algoritmos
rápidos para hacerlo, los cuales toman ventaja de la estructura
matricial especial de los códigos Reed-Solomon y reducen de gran
forma el esfuerzo computacional requerido.
Detección y Corrección de errores
Para la detección de errores es necesario calcular el polinomio
localizador de errores y el polinomio magnitud de errores, para esto se
pueden usar varios algoritmos como el de Berlekamp, Berlekamp-
Masey, Euclides extendido o Euclides modificado.
Decodificación Reed Solomon:
Corrección de errores
Este paso también implica resolver ecuaciones con t incógnitas para poder encontrar los valores
verdaderos que deberán ser sustituidos en las posiciones correspondientes, para así poder
reproducir el mensaje correcto que se intentó enviar. Esto se hace con el algoritmo de búsqueda de
Chien. Donde 1 ≤ 𝑗 ≤ 𝑡 los 𝑓𝑖 son las incógnitas y 𝑆𝑖 los componentes del síndrome calculado. La
posición en la que están los errores se obtiene de los exponentes de las raíces de un polinomio
𝑓(𝑥)
f(x)= 𝑥𝑡 + 𝑓1 𝑥 𝑡 + … … + 𝑓𝑡−1 𝑥 + 𝑓𝑡
EJERCICIOS
Código RS(7,3). La palabra que ingresa al
codificador es la siguiente: 001 011 111
(1,α𝟑 ,α𝟓 )
m(x)= x 𝟐 + α𝟑 ∗ 𝒙 + α𝟓
𝒏−𝒌
𝒕= = (𝟕 − 𝟑)/𝟐 = 𝟐
𝟐
𝒈 𝒙 = 𝒙 + 𝜶 𝒙 + α𝟐 𝒙 + α𝟑 𝒙 + α 𝟒
𝒈 𝒙 = x 𝟒 + α 𝟑 ∗ x 𝟑 + x 𝟐 + 𝜶 ∗ 𝒙 + α𝟑
Símbolos sobre GF(2^3)
Una vez obtenido el polinomio generador
Campo de Galois
se realiza la división 𝒎(𝒙) ∗ x (𝒏−𝒌) ÷ 𝑔(𝑥)
x 𝟔 + α𝟑 ∗ x 𝟓 + α𝟑 ∗ x 𝟒 ÷ x 𝟒 + α𝟑 ∗ x 𝟑 + x 𝟐 + 𝜶 ∗ 𝒙 + α𝟑
Símbolos sobre GF(2^3)
Campo de Galois
Palabra codificada completa:
𝑐(𝑥) = x 𝟔 + α𝟑 ∗ x 𝟓 + α𝟓 ∗ x 𝟒 + α𝟑 ∗ x 𝟑 + α𝟔 ∗ x 𝟐 + α𝟓 ∗ 𝒙 + 𝟏
Se puede expresar de dos manera en binario o también de forma decimal
Forma binaria
Forma decimal
Decodificación Reed-Solomon
El proceso de decodificación consiste en tomar la palabra enviada por el codificador y recuperar
la palabra original. Si la palabra recibida tiene errores, el código Reed Solomon se encargara de
detector y corregir los errores que se produjeron en la transmisión, como este proceso es el
inverso de la codificación ingresaran n símbolos al decodificador y se obtendrán los k símbolos
correspondientes al mensaje original que se envió.
Cálculo del polinomio síndrome
𝑆𝑖−1 = 𝑟 𝑎𝑖 𝑖 = 1,2,3, … , 2𝑡
𝑆 𝑥 = 𝑆0 + 𝑆1 𝑥 + 𝑆2 𝑥 + ⋯ + 𝑆2𝑡−1 𝑋 2𝑡−1
Palabra codificada
𝑟 𝑥 = x 𝟔 + α𝟑 ∗ x 𝟓 + α𝟓 ∗ x 𝟒 + α𝟑 ∗ x 𝟑 + α 𝟔 ∗ x 𝟐 + α𝟓 ∗ 𝒙 + 𝟏
Cálculo del polinomio síndrome
𝑆0 = 𝑟 𝑎 = x 𝟔 + α𝟑 ∗ α𝟓 + α𝟓 ∗ α𝟒 + α𝟑 ∗ α𝟑 + α𝟔 ∗ α𝟐 + α𝟓 ∗ α + 𝟏
𝑆0 = α𝟔 + α + α𝟐 + α𝟔 + α+ α𝟔 + 𝟏
𝑆0 = α𝟐 + α𝟔 + 𝟏
𝑆0 = 0
𝑆1 = 𝑟 α𝟐 = 0
𝑆2 = 𝑟 α𝟑 = 0
𝑆3 = 𝑟 α𝟒 = 0
Símbolos sobre GF(2^3)
𝑆 𝑥 =0 Campo de Galois
Cálculo del polinomio síndrome
Ahora ingresaremos dos errores y volveremos a calcular el síndrome
Palabra codificada
𝑟 𝑥 = x 𝟔 + α𝟑 ∗ x 𝟓 + α𝟒 ∗ x 𝟒 + 𝟏 ∗ x 𝟑 + α𝟔 ∗ x 𝟐 + α𝟓 ∗ 𝒙 + 𝟏
𝑆0 = 𝑟 α = 0
El polinomio del síndrome es distinto
𝑆1 = 𝑟 α𝟐 = α𝟑 de cero, esto indica que existen
errores en la palabra recibida por lo
𝑆2 = 𝑟 α𝟑 = α𝟐
se deberá iniciar un proceso de
𝑆3 = 𝑟 α𝟒 = 1 detección y corrección de errores.
𝑆 𝑥 = 𝑆3 𝑋 3 + 𝑆2 𝑋 2 + 𝑆1 𝑋 + 𝑆0
Símbolos sobre GF(2^3)
𝑆 𝑥 = 𝑋 3 + α 𝟐 𝑿𝟐 + α 𝟑 𝑿
Campo de Galois
BIBLIOGRAFÍA
[1] Onate, C., & Lupera, P. (2018). Implementaci ˜ on de un Codificador y Decodificador Reed Solomon (204,188) en una
Tarjeta ´ FPGA con el Algoritmo de Euclides Modificado. Journal of Science and Research: Revista Ciencia e
[ K. Ogata, Ingenieria de control Moderna, Pearson.
Investigacion, 3(JIEE2018), 35-42. ´ [Link]
1
] [2] Sandoval Ruiz, Cecilia E.; Fedón, Antonio Codificador y decodificador digital Reed-Solomon programados para hardware reconfigurable
Ingeniería
[ E. Mandado, J. Marcos y Universidad,
and C. Fernández, vol.de11,
"Sistemas núm. 1, enero-junio,
automatización 2007,
y Autómatas pp. 17-312018.
programables," Pontificia Universidad
[Online]. Javeriana Bogotá, Colombia. [obtenido
Available: [Link]
2 content/uploads/2018/02/[Link].
de:] [Link]
]
[ A. Moreno, "slide share," 20 abril 2019. [Online]. Available: [Link] [Accessed 7 abril
3 2019]. [3]
]
[ V. R. Gonzales, "Fundamentos de Robótica," marzo 2002. [Online]. Available: [Link] [Accessed 7
4 Abril 2019].
[4]
]
[ M. Patiño, "Variables Eléctricas," 12 Septiembre 2016. [Online]. Available: [Link] [Accessed 8 Abril
5 2019].
] [5]
