UNIVERSAD POLITECNICA SALESIANA jortizcm@[Link], esalinasv1@[Link].
ec
Reed Solomon
Jose Ortiz jortizcm@[Link],
Erik Salinas esalinasv1@[Link]
Abstract: The following paper shows how to b
obtain the Reed Solomon and yours codes Tamaño de n=2 -1 Símbolos
bloque
I. Introduccion
Tamaño de n – k = 2t Símbolos
Reed-Solomon es un código cíclico no binario y
paridad
constituye una subclase de los códigos BCH.
Los códigos cíclicos son una subclase de los Tamaño de k Símbolos
códigos de bloque estándar de detección y mensaje
corrección de
errores que protege la información contra
Distancia mínima dmin >= 2t Símbolos
errores en los datos transmitidos sobre un canal
de comunicaciones. Este tipo de código +1
pertenece a
la categoría FEC (Forward Error Correction), es Errores a corregir t Símbolos
decir, corrige los datos alterados en el receptor y
para ello utiliza unos bits adicionales que
permiten esta recuperación a posteriori.
Este tipo de códigos emplea algo de todo lo
visto hasta ahora para llevar a cabo la detección
y corrección de errores.
II. Desarrollo
a. Reed solomon
Un popular Reed-Solomon código RS (255,223)
Un código Reed Solomon es una subclase de los
con 8-bit de los símbolos. Cada palabra de
códigos BCH(Bose-Chaudhuri-Hocquenqhem)
código contiene 255 bytes palabra clave, de los
y códigos lineales de bloque. Un código Reed-
cuales 223 bytes son datos y 32 bytes son
Solomon se especifica como RS ( n, k ), con s
paridad. Para que este código: n = 255, k =
símbolos bits. Esto significa que el codificador
toma k símbolos de datos de s bits cada uno, y 223, s = 8, 2t = 32, t = 16
añade símbolos de paridad para hacer El decodificador puede corregir 16
un n símbolo de palabra clave. Existen nk errores en el símbolo de la palabra clave: es
símbolos de paridad de los bits de s cada uno. decir, errores de hasta 16 bytes en cualquier
Un decodificador Reed-Solomon puede corregir lugar de la palabra código se pueden corregir
hasta t símbolos que contienen errores en una automáticamente. Dado un tamaño del símbolo
palabra código, donde 2t = nk. Es útil cuando s, la longitud máxima de palabra clave (n) de un
los errores ocurren en ráfagas, como en los
código Reed-Solomon es n = 2 s
– 1. Por
sistemas de grabación de discos compactos
ejemplo, la longitud máxima de un código de
digitales. Un código RS que corrige t errores
símbolos de 8 bits (s = 8) es de 255 bytes.
tiene los siguientes parámetros: Un polinomio
generador no binario se define
UNIVERSAD POLITECNICA SALESIANA jortizcm@[Link], esalinasv1@[Link]
b.Técnicas de Detección y Corrección de Errores
CODIGOS POR BLOQUES LINEALES
• Casi todos los códigos de bloque
utilizado hoy en día pertenecen a un
subgrupo llamado bloque de códigos
lineales.
• Un código de bloque lineal es un
código en el que el OR exclusivo
(adición módulo-2) de dos palabras de
código válidas crea otra palabra de
código válida
DETECCION DE RRORES
Para detectar o corregir errores se necesita
agregar cierta redundancia a los bits de
información.
CODIGOS DE DETECCION DE ERRORES
• Cada bloque de k bits es codificado
con un bloque de (k+r) bits
denominado palabra código
(codeword). PRINCIPIOS DE DETCCION DE ERRORES
• La palabra código es la que se transmite. • El algoritmo suma r bits al bloque de
datos de m bits.
• En el receptor varias cosas pueden
pasar: • Los k bits en la señal original se
transmiten en la palabra código de
– Si no hay errores, la salida de
(k+r) bits.
decodificador es igual al
código original.
• dLeafidniestacnocmiao d eel
– Para ciertos errores, el
decodificador puede detectar nHúammemroindge, db(ivts1,evn2)losse
y corregir los mismos. cuales v1 y v2 difieren.
– Para ciertos patrones de • La distancia mínima para una palabra
errores, el decodificador có digo que consiste de w1,w2, …ws
puede detectar el error pero donde s = 2n .
no corregirlo.
dmin = mini j [d(wi,wj)]
– Para ciertos errores el
• Por ejemplo, si v1 = 011011 y v2 =
decodificador no puede
110001 d(v1,v2) = 3
detectar el error y produce una
señal de salida que difiere de • La función de la forma vc = f(vd)
la original. donde vd es un vector de data de m
bits y vc la palabra código.
CODIFICACION POR BLOQUES
• El radio de redundancia (ie
redundancia) es r/k.
UNIVERSAD POLITECNICA SALESIANA jortizcm@[Link], esalinasv1@[Link]
• La tasa del código es k/(k+r) y mide la • El radio de redundancia (ie
cantidad adicional de ancho de banda redundancia) es (n-k)/k.
que se necesita.
• La tasa del código es k/n y mide la
BIT DE PARIEDAD cantidad adicional de ancho de banda
que se necesita.
• Sumar un bit al final de un bloque de
data.
• De forma tal que, el carácter tiene: III. Conclusiones
– Un número par de unos El uso de Códigos de Detección de errores es
(paridad par). de suma importancia para el tratamiento de
información, cualquiera que sea su uso.
– Un número impar de unos
(paridad impar).
• Ventajas: IV. Referencias
– Simple 1) [Link]
• Desventajas: ven/6037/[Link]#Detección%20y
– Un número par de errores no %20corr ección%20de%20errores
se pueden detectar.
2) [Link]
• Ejemplos (paridad par): ntenido/codifico/[Link]
– Data = 1110011
3) [Link]
– Transmite (A)= 11100111
4)
– Llega = 11100101
– Calculo en el receptor (B) =
11100100
– |Distancia A-B| = 2
FEC PRINCIPIOS
• El algoritmo FEC suma (n-k) bits al
bloque de datos de k bits.
• Los k bits en la señal original se
transmiten en la palabra código de n
bits.
• La distancia de Hamming, d(v1,v2) se
define como el número de bit en los
cuales v1 y v2 difieren.
• Por ejemplo, si v1 = 011011 y v2 =
110001 d(v1,v2) = 3
• La función de la forma vc = f(vd)
donde vd es un vector de data de k bits
y vc la palabra código.
• Dentro de un bloque de código (n,k) hay
K n
p2 osibcó[Link] códigos
válidos de 2
