CDIGO DE DETECCION DE ERROR HAMMING Y CRC
Guevara [email protected]
[email protected]
Ingeniera Mecatrnica, 6to. Nivel, Universidad de las Fuerzas
Armadas ESPE Extensin Latacunga, Mrquez de Maenza, Latacunga
Ecuador.23 de Abril del 2015
RESUMEN: En la vida diaria en la transmisin de informacin,
existen errores de transmisin que se deben a diversos factores,
como el ruido trmico, ruido impulsivo y ruido de intermodulacin.
Dependiendo del medio de transmisin y el tipo de codificacin
empleado se pueden presentar otros tipos de anomalas como ruido de
redondeo y atenuacin.Para estos problemas se ha diseado dos
estrategias diferentes para identificar y corregir estos tipos de
errores como son el de Hamming y CRC.
PALABRAS CLAVE: Deteccin de error, codificacin, transmisin,
Hamming y CRC.
1. INTRODUCCION
Este documento contiene informacin del cdigo Hamming, el cual es
un cdigo detector y corrector de errores que lleva el nombre de su
inventor, Richard Hamming. Se especifica la codificacin y
decodificacin de errores de dos bits. Tambin hablaremos acerca del
cdigo de redundancia cclica (CRC) el mismo que nos permitir
verificar en dispositivos hardware si la informacin esta corrupta
(daada).
2. CARACTERISTICAS GENERALES
2.1. HAMMING
La mayor ventaja de este cdigo es que detecta todos los errores
de dos bits y corrige un bit de error.
2.2. CRC Son muy utilizados en la prctica para la deteccin de
errores en largas secuencias de datos.[1]
Est basado en la divisin binaria.
3. DESARROLLO
3.1 CODIGO HAMMING
El cdigo hamming se genera a partir de una distancia mnima de 3,
ya que una distancia de 1 o 2 es inconveniente para poder generar
un cdigo para detectar un error.
Para la nomenclatura de este cdigo se utiliza dos nmeros en
parntesis, el 1er nmero indica el nmero de bits totales y el 2do el
nmero de bits que llevan la informacin.
Los bits de paridad se ubican en potencia 2 segn 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 posicin de bits
3.1.1 CODIFICACIN DEL CDIGO HAMMING
En la tabla de la Imagen 1. Se colocan de forma mecnica la
primera fila las posiciones empezando desde 0001, los bits de
paridad se sitan en las posiciones que se han numerado hacindolas
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 sera el 1, cuyas posiciones respectivas son 0011, 0101,
0111, etc., despus de esto se calcula la paridad.
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 cdigo cifrado.
3.1.2 DECODIFICACIN DEL CDIGO HAMMING
La etapa de decodificacin en el receptor tiene dos fases, la
primera obligatoria (deteccin) y la segunda opcional
(correccin).
3.1.2.1 CDIGO DE DETECCIN DE ERRORES EN UN SOLO BIT.
Esta fase detecta cuando existe un solo bit daado, una vez
recibido el mensaje, se genera una nueva palabra de cdigo
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 cdigo de correccin de errores.
3.1.2.2 CDIGO DE CORRECCIN DE ERRORES EN UN SOLO BIT.
En esta fase, se compara la secuencia recibida con la palabra de
cdigo 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 posicin del bit daado, se sustituye por el valor
opuesto y concluye esta fase.Por ejemplo, suponga que se desea
enviar desde el emisor la palabra de cdigo 0 1 0 0 1 0 1, en la
transmisin ocurre una falla y al receptor llega la secuencia 0 1 0
0 1 0 0, se debe destacar que el bit daado es el ltimo de esta
secuencia.
Al realizar el nuevo clculo sobre la palabra de cdigo 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 cdigo (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 posicin
del bit daado, el cual debera reemplazarse por el valor opuesto (1
en este caso) para realizar la correccin.
3.2 CODIGO CRC
Los cdigos de redundancia cclica (CRC) son un potente sistema
muy usado en comunicaciones y en dispositivos de hardware para
detectar si la informacin esta corrupta (daada).Tambin se los
conoce como cdigos polinmicos, usan un polinomio generador G(x) de
grado r con n bits de datos binarios (coeficiente del polinomio de
orden n-1).
En estos bits de datos se le aaden 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 transmisin.
Los polinomios generadores ms usados son:
CRC-12: Usado para transmitir flujos de 6 bits, junto a otros 12
de redundancia.
CRC-16: Usado para flujos de 8 bits, con 6 de redundancia. Usado
en USA principalmente.
CRC-CCITT:Usado para flujos de 8 bits, con 16 de redundancia.
Usado en Europa, principalmente.
CRC-32:Da una proteccin extra sobre la que dan los CRC de 16
bits, que suelen dar la suficiente. Se emplea por el comit de
estndares de redes locales (IEEE-802) y en algunas aplicaciones del
Departamento de Defensa de USA.[3]
Dos aplicaciones importantes de los cdigos 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 cdigo CRC, de modo que los errores
que estn 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 verificacin en un cdigo CRC. Los cdigos
CRC para ambas aplicaciones fueron seleccionados debido a sus
propiedades de deteccin de errores rfaga. Adems de los errores de
bit simple, pueden detectar errores de mltiples bits que estn
agrupados en forma contigua. En el interior del bloque o del
disco.
4. CONCLUSIONES
El cdigo de deteccin de error Hamming detecta y/o corregir los
errores dependiendo de la complejidad que estructura el cdigo.
Con el cdigo CRC podemos detectar donde ocurri el error y as
poder realizar la correccin de errores fcilmente.
REFERENCIAS
[1] J. F. Kakerly, Diseo Digital: Principios y Practicas,
Pearson Educacin, 2001. [2] R. Blake, Sistemas electrnicos de
comunicaciones, Mexico: Gale Virtual Reference Library, 2004. [3]
J. R. Hernndez, http://www.emezeta.com/, 4 Febrero 2006. [En lnea].
Available:
http://www.emezeta.com/articulos/codigos-de-redundancia-ciclica.
[ltimo acceso: 21 Abril 2015].
