Embed Size (px)
DESCRIPTION
Hamming CRC
Citation preview
1
CÓDIGO DE DETECCION DE ERROR HAMMING Y CRC
Guevara [email protected]
Edison [email protected]
Ingeniería Mecatrónica, 6to. Nivel, Universidad de las Fuerzas Armadas ESPE – Extensión Latacunga, Márquez de Maenza, Latacunga – Ecuador.
23 de Abril del 2015
RESUMEN: En la vida diaria en la transmisión de información, existen errores de transmisión que se deben a diversos factores, como el ruido térmico, ruido impulsivo y ruido de intermodulación. Dependiendo del medio de transmisión y el tipo de codificación empleado se pueden presentar otros tipos de anomalías como ruido de redondeo y atenuación.Para estos problemas se ha diseñado dos estrategias diferentes para identificar y corregir estos tipos de errores como son el de Hamming y CRC.
PALABRAS CLAVE: Detección de error, codificación, transmisión, Hamming y CRC.
1. INTRODUCCION
Este documento contiene información del código Hamming, el cual es un código detector y corrector de errores que lleva el nombre de su inventor, Richard Hamming. Se especifica la codificación y decodificación de errores de dos bits. También hablaremos acerca del código de redundancia cíclica (CRC) el mismo que nos permitirá verificar en dispositivos hardware si la información esta corrupta (dañada).
2. CARACTERISTICAS GENERALES
2.1. HAMMING
La mayor ventaja de este código es que detecta todos los errores de dos bits y corrige un bit de error.
2.2. CRC Son muy utilizados en la práctica
para la detección de errores en largas secuencias de datos.[1]
Está basado en la división binaria.
3. DESARROLLO
3.1 CODIGO HAMMING
El código hamming se genera a partir de una distancia mínima de 3, ya que una distancia de 1 o 2 es inconveniente para poder generar un código para detectar un error.
Para la nomenclatura de este código se utiliza dos números en paréntesis, el 1er número indica el número de bits totales y el 2do el número de bits que llevan la información.
Los bits de paridad se ubican en potencia 2 según el orden de la tabla y el resto van con los datos, todo esto se puede apreciar en la imagen 1. [2]
Figura. 1. “Tabla de posición de bits”
3.1.1 CODIFICACIÓN DEL CÓDIGO HAMMING
En la tabla de la Imagen 1. Se colocan de forma
mecánica la primera fila las posiciones empezando desde 0001, los bits de paridad se sitúan en las posiciones que se han numerado haciéndolas corresponder con las potencias.
En la primera columna se ubican las potencias de forma ascendente p1, p2, p3, p4.
La primera potencia p1 se baja el bit menos significativo de paridad que sería el 1, cuyas posiciones respectivas son 0011, 0101, 0111, etc., después de esto se calcula la paridad.
2
La siguiente potencia p2 se bajan los bits que cuyas posiciones del segundo bit sean 1 ejemplo: 0011, 0110, 0111, 1010, etc. igualmente calculamos la paridad.
Para concluir se debe bajar la palabra original para llenar la última fila, y de esta manera tendremos el código cifrado.
3.1.2 DECODIFICACIÓN DEL CÓDIGO HAMMING
La etapa de decodificación en el receptor tiene dos fases, la primera obligatoria (detección) y la segunda opcional (corrección).
3.1.2.1 CÓDIGO DE DETECCIÓN DE ERRORES EN UN SOLO BIT.
Esta fase detecta cuando existe un solo bit dañado, una vez recibido el mensaje, se genera una nueva palabra de código recalculando sobre las posiciones de los bits de paridad, y se compara con la secuencia recibida. Si son iguales, significa que no hubo errores; en caso contrario, se detecta la existencia de un error y se procede a utilizar el código de corrección de errores.
3.1.2.2 CÓDIGO DE CORRECCIÓN DE ERRORES EN UN SOLO BIT.
En esta fase, se compara la secuencia recibida con la palabra de código calculada en la etapa anterior, y se suman las posiciones de los bits de paridad que difieran entre ellas. El resultado de esta suma determina la posición del bit dañado, se sustituye por el valor opuesto y concluye esta fase.Por ejemplo, suponga que se desea enviar desde el emisor la palabra de código 0 1 0 0 1 0 1, en la transmisión ocurre una falla y al receptor llega la secuencia 0 1 0 0 1 0 0, se debe destacar que el bit dañado es el último de esta secuencia.
Al realizar el nuevo cálculo sobre la palabra de código 0 1 0 0, se obtienen los valores presentados Luego, se compara la secuencia recibida (0 1 0 0 1 0 0) con la nueva palabra de código (1 0 0 1 1 0 0). Como se puede observar, los valores de los bits de paridad 1, 2 y 3 no coinciden. Esto implica que, al sumar las posiciones que ocupan estos bits de paridad, 1 + 2 + 4 = 7, se obtiene la posición del bit dañado, el cual debería reemplazarse por el valor opuesto (1 en este caso) para realizar la corrección.
3.2 CODIGO CRC
Los códigos de redundancia cíclica (CRC) son un potente sistema muy usado en comunicaciones y en dispositivos de hardware para detectar si la información esta corrupta (dañada).También se los conoce como códigos polinómicos, usan un polinomio generador G(x) de grado r con n bits de datos binarios (coeficiente del polinomio de orden n-1).
Datos :10111Polinomio : x 4+x3+x2+x1+ x0
En estos bits de datos se le añaden r bits de redundancia, de forma que el polinomio resultante sea divisible por el polinomio generador. El receptor verifica si el polinomio recibido es divisible por G(x). Si no lo es, habrá un error en la transmisión. Los polinomios generadores más usados son:
CRC-12: x12+x11+x3+x2+ x+1Usado para transmitir flujos de 6 bits, junto a otros 12 de redundancia.
CRC-16: x16+ x15+x2+1Usado para flujos de 8 bits, con 6 de redundancia. Usado en USA principalmente.
CRC-CCITT:x16+ x12+x5+1Usado para flujos de 8 bits, con 16 de redundancia. Usado en Europa, principalmente.
CRC-32:
x32+x26+x23+x22+x16+x12+ x11+ x10+x8+x7+x5+x4+ x2+x+1Da una protección extra sobre la que dan los CRC de 16 bits, que suelen dar la suficiente. Se emplea por el comité de estándares de redes locales (IEEE-802) y en algunas aplicaciones del Departamento de Defensa de USA.[3]
Dos aplicaciones importantes de los códigos CRC se encuentran en las unidades controladoras de disco y en las redes de datos. En una unidad unidad de disco, cada bloque de datos (por lo regular de 512 bytes) está protegido mediante un código CRC, de modo que los errores que están en el interior de un bloque pueden detectarse, y en algunas unidades, corregirse. En una red de datos, cada paquete de datos termina con bits de verificación en un código CRC. Los códigos CRC para ambas aplicaciones fueron seleccionados debido a sus propiedades de detección de errores ráfaga. Además de los errores de bit simple, pueden detectar errores de múltiples bits que estén agrupados en forma contigua. En el interior del bloque o del disco.
4. CONCLUSIONES
El código de detección de error Hamming detecta y/o corregir los errores dependiendo de la complejidad que estructura el código.
Con el código CRC podemos detectar donde ocurrió el error y así poder realizar la corrección de errores fácilmente.
3
5. REFERENCIAS
[1] J. F. Kakerly, Diseño Digital: Principios y Practicas, Pearson Educación, 2001.
[2] R. Blake, Sistemas electrónicos de comunicaciones, Mexico: Gale Virtual Reference Library, 2004.
[3] J. R. Hernández, «http://www.emezeta.com/,» 4 Febrero 2006. [En línea]. Available: http://www.emezeta.com/articulos/codigos-de-redundancia-ciclica. [Último acceso: 21 Abril 2015].
