CDIGOS DE DETECCIN DE ERROR CRC Y HAMMING
Pilatasig Aynuca Alexis Fabian [email protected]
Socasi Elvis Patricio [email protected]
Ingeniera Mecatrnica, 6to. Nivel, Universidad de las Fuerzas
Armadas ESPE Extensin Latacunga, Mrquez de Maenza S/N Latacunga,
Ecuador.23 de Abril de 2015
RESUMEN: Conforme a la gran cantidad de problemas al momento de
enviar o receptar un mensaje, se han determinado varias tcnicas a
utilizar para la deteccin de errores, en el presente documento se
analizara una de las tcnicas ms utilizadas para la solucin de estos
problemas. El cdigo Hamming y El cdigo CRC son cdigos que tiene
como funcin detectar y corregir los errores que se hayan producido
durante la transicin de un mensaje con lo cual el receptor puede
analizar y determinar, de una forma confiable, si los bits
receptados corresponden realmente a los del emisor.
PALABRAS CLAVE: cdigo haming, cdigo CRC, Deteccin de
errores.
1 INTRODUCCIN
El cdigo Hamming tiende a ser un cdigo que permite analizar,
localizar y corregir errores, cuando el cdigo detecta que se ha
producido dos errores, el cdigo realiza un procedimiento mediante
unas tablas las cuales trabajan con bits de redundancia las mismas
se deben introducir a lo largo de la palabra, con la finalidad que
cuando produzca errores lo podamos realizar la respectiva
correccin
Cdigos de redundancia cclica (CRC) es un cdigo que detecta y
corrige de errores en la informacin de las telecomunicaciones.Los
cdigos CRC
La aplicacin del cdigo CRC se realiza mediante divisiones a
nmeros binarios, estos cdigos se utiliza para analizar los hardware
de las computadoras donde se puede encontrar errores de datos del
dispositivo
2. CARACTERSTICAS GENERALES
2.1 HAMMING
El cdigo Hamming es un cdigo de que permite detectar y corregir
errores.permite detectar errores hasta en dos bit y corregir un
bitPara la corregir los errores utiliza el mtodo de paridad
2.2 CRC
Su implementacin es sencilla y de fcil entendimiento.Adems puede
detectar errores causados por el ruido.
3. DESARROLLO 3.1 CDIGO HAMMINGPor lo general el cdigo Hamming
tiene una nomenclatura que contiene dos nmeros los cuales se
encuentran dentro de un parntesis, el primer nmero representa el
total de bits, mientras el segundo representa el nmero de bits que
contiene la informacin
En los cdigos Hamming se encuentra el termino paridad el cual
contiene bits que contienen una potencia de 2, dependientes del el
orden de la tabla por lo tanto los restantes irn con los datos.
Visualizar en la presente imagen 1. [1]
Tabla 1. Tabla de paridad del cdigo
Hammingp1p2d1p3d2d3d4p4d5d6d7
Palabra de dato (sin pariedad)0110101
P1101011
P2001001
P30110
P40101
Palabra de dato (con pariedad)10001100101
3.2 Cdigo CRC
El cdigo CRC o tambin llamada comprobacin de redundancia cclica
es una funcin diseada para detectar los cambios en la transmisin de
datos de un transmisor a un receptor.
Son tambin considerados como cdigos polinomiales.
El objetivo de este mtodo es aadir r bits al mensaje de K bits,
de tal forma que la resultante a transmitir sea K+r bits y sea
divisible para un polinomio generador G(x).
El receptor verifica si T(x) es divisible para G(x), y si no lo
es significa que existe un error en la transmisin de
informacin.
4. PROCEDIMIENTO DE CODIFICACIN Y DECODIFICACIN
4.1 HAMMING
4.1.1 CODIFICACIN
Para la forma mecnica las posiciones se colocan en la primera
fila de la parte superior de la tabla teniendo como referencia el
0001, los bits de paridad se expresara 0.
a. Los bits de paridad que son representados con la letra P sern
colocados en la primera columna de la tabla para a continuacin sean
calculados b. en el caso de P1, el bit menos significativo de la
paridad (1) debe bajarse por lo tanto las posiciones serian 0011,
0101, 0111,1001, 1011. A continuaciones calculamos la paridad,
cuando la paridad es par los trminos de 1 deben ser par caso
contrario se procede a completar y agregar un 1c. En el caso de P2.
Tenemos que descender el bit de la posicin cuyo valor de segundo
bit sea 1 por lo tanto tendremos 0011, 0110, 0111,1010, 1011, etc.
El mismo procedimiento se realizara para los casos de P3 y P4.
Debemos tomar en cuenta que el bit de paridad se deber colocar
en la celda adecuada. Como es: (p1, p1), (p2, p2) esto depender de
la posicin en la cual se encuentre la paridad. Por ltimo
descendemos la palabra con la cual se empiece a trabajar con la
finalidad de ocupar la ltima fila. Y obtendremos el cdigo
cifrado.
El cdigo Haming se puede utilizar de manera directa recibiendo
el cdigo final y analizando la paridad directamente en las filas de
p1, p2, p3, p4. [2]
4.1.2 DECODIFICACIN
En este procedimiento se realizara similar al de codificacin con
la diferencia que extraeremos los bits de paridad, al momento de
comparar deben ser iguales por ende no existir error, pero si es lo
contrario significa que existe un error el cual podremos
corregir
a. Se debe escribir el cdigo que se recibe en los bits de datos
de igual manera que en la anterior en aquellas celdas con el ltimo
bit 1. [1]b. Calcularemos las paridades p1, p2, p3, p4 con el mismo
procedimiento que se realiz en la codificacin c. Comparamos todas
las paridades por ejemplo: comparamos p1 con p1.d. El cdigo de
haming representa a los errores los errores uno y con cero a los
aciertos y se descifra desde la parte inferior hacia la parte
superior, estos valores sern transformados a decimal con la
finalidad de que nos indique la ubicacin del error, pero se debe
tener en cuenta que el cdigo recibido se lo debe contar desde el
1er bit
4.2 CODIGO CRC
4.2.1. TRANSMISION
Para la transmisin se utiliza un polinomio generador G(x) que es
predeterminado de grado r, y es el mismo tanto en el emisor y como
en el receptor. El generador tiene r+1 bits de longitud.
La base para el clculo de del cdigo es la siguiente:
(1)
Es el desplazamiento de los bits de datos hacia la
izquierda,.
Es la adiccin de r bits 0s al final del bit de datos. Por
ejemplo:
y entonces
Este polinomio se vuelve a dividir para el polinomio generador.
Si el residuo de la divisin es cero se enva el dato, si el cociente
es diferente de cero se corrige el error y se enva los datos
[4].
4.2.2. RECEPCION
El receptor recibe el mensaje del emisor y debe dividirlo para
el polinomio generador. Si el residuo es cero, el mensaje ha
llegado correctamente. Si el residuo es diferente de cero, el
mensaje a llegado con error y hay que pedir una retransmisin del
mensaje. [4].
4.2.3. EJEMPLO
Se requiere transmitir 10011011. Polinomio generador .
Mensaje: 10011011. Polinomio generador: 1001 (r=3) Se aade 3
bits 0 al final del mensaje: 10011011000 Se divide entre G.
10011011000100110011000101000001011 1001 001000 1001 00010
Se transmite 10011011010
5. RESULTADOS
El cdigo Hammig nos brinda un mtodo para analizar el resultado
denominado mtodo haming el cual es realizar una tabla en la cual se
encuentre los valores de paridad que podrn ser comparados entre los
errneos y los originales. Cuando son diferente se ubica el nmero
uno, por otro lado cuando son iguales se ubica el cero. Se descifra
desde la parte inferior de la columna final hacia la parte superior
de la misma columna, para posteriormente transformar a numero
decimal con la finalidad de que nos indique en qu lugar se realiz
el cambio en el dato original, tomando en cuenta un conteo de
izquierda a derecha iniciando desde el primer bit
El cdigo CRC es un mtodo muy interesante para detectar errores
en el envi de informacin ya que el mensaje del emisor debe ser
dividido para el polinomio generador. Si el residuo es cero, el
mensaje ha llegado correctamente. Si el residuo es diferente de
cero, el mensaje a llegado con error y hay que pedir una
retransmisin del mensaje.
6. CONCLUSIONES
Sin importar el tipo de informacin que se desea transmitir desde
un transmisor a un receptor, siempre hay la posibilidad de que se
presenten errores en la transmisin de datos, es decir la informacin
que sale del transmisor es diferente a la que llega al receptor, la
causa ms importante de errores es la transmisin de ruido elctrico,
que es la variacin de voltaje o corriente y que siempre estn
presentes en los sistemas electrnicos, para esto existe los cdigos
de deteccin d de errores.
Mediante el anlisis de este documento se puede concluir lo
siguiente:
El cdigo Hamming nos permite corregir cualquier error que
contenga un solo bit, tiene la caracterstica de detectar los
errores en 2 bits
El cdigo Hamming es utilizado en diversos campos de la ingeniera
con la finalidad de corregir errores en el momento de recibir un
mensaje Los cdigos con bits de paridad tienen la caracterstica de
detectar los errores en un solo bit pero no tienen a
corregirlos.
El cdigo CRC es un mtodo muy interesante para detectar errores
en el envi de informacin ya que el mensaje del emisor debe ser
dividido para el polinomio generador. Si el residuo es cero, el
mensaje ha llegado correctamente. Si el residuo es diferente de
cero, el mensaje a llegado con error y hay que pedir una
retransmisin del mensaje
7. REFERENCIAS
[1] Comunicaciones digitales, Bateman, Andy, Marcombo, Fecha de
Publicacin: 2007,cap. 3, pg. 46,
47.http://ezp1.espe.edu.ec:2050/lib/espesp/docDetail.action?docID=10165675&p00=hammi
ng
[2] Introduccin a la informtica (4a. ed.), Prieto Espinosa,
Alberto Lloris Ruiz, Antonio Torres Cantero, Juan Carlos ,
McGraw-Hill Espaa, 2006, cap. 4,
pg.56,58,59.http://ezp1.espe.edu.ec:2050/lib/espesp/docDetail.action?docID=10693150&p00=codigo%20hamming
[3] Esencias de ingeniera de comunicaciones digitales: un
enfoque terico prctico, Snchez Lpez, Rafael, Instituto Politcnico
Nacional, 2009, cap. 4, pg.
48,51.http://ezp1.espe.edu.ec:2050/lib/espesp/docDetail.action?docID=10411436&p00=codigo%20crc
[4] Kurose, J, Redes de Computadores y Internet, 3ra. Ed., Uma
Abordagem Top-Down, pp. 340, 2006
.
