CÓDIGOS DE DETECCIÓN DE ERROR HAMMING Y CRC

Barona Iváne-mail: isa_barona1@yahoo.com

Aroca Katherinee-mail: katherine223@live.com.ar

Ingeniería Mecatrónica , 5to “B” Universidad de las Fuerzas Armadas ESPE – Extensión Latacunga

Fecha de presentación: 24/04/2015

RESUMEN: El presente documento describe los tipos de cógidos de detección de error Hamming y CRC.

De estas clases de códigos de detección de error se analizan sus respectivas definiciones y características. Además se detallan sus procedimientos para su uso en los sistemas digitales. Para aplicar la teoría aprendida se presentan ejemplos de aplicación.

PALABRAS CLAVE: CRC , módulo 2, paridad , polinomio.

1. INTRODUCCIÓN

En sistemas digitales la transmisión de datos de un lugar a otro es muy común e importante. Como ejemplos tenemos el uso de memorias externas para almacenar y recuperar datos, la transferencia de datos entre dos computadoras por medio de líneas telefónicas, transferencia bluetooth, etc.

Normalmente en la transmisión de datos se suelen producir errores que hacen que estos no lleguen de forma correcta entre el emisor y el receptor. La razón principal de estos problemas es el llamado “ruido eléctrico”, que produce fluctuaciones en el voltaje y la corriente. [1]

El ruido alterá el nivel lógico de la señal y esto produce errores en la llegada deseada de bits, pues no será interpretados correctamente. Tenemos almacenado un 1 pero a la hora de ser leído es un 0, y viceversa. [1]

Los equipos actuales logran enviar en cierto casos millones de bits por segundo y un error en 1 bit podría causar graves problemas. Es por eso que se emplean métodos de detección (y en muchos casos correción) de errores. Entre estos tenemos el método Hamming y el Método CRC. [1]

2. CÓDIGO DE DETECCIÓN DE ERROR HAMMING

Al utilizar un solo bit de paridad se puede detectar un error de un bit en un código. Pero mucho mejor sería lograr corregir ese error. El código Hamming permite detectar un error en un grupo de

bits y además corregirlo. Esto lo logra incluyendo mas de un bit de paridad en un grupo de bits.

El siguiente código brinda un método de corrección para un único bit erróneo.

2.1 NÚMERO DE BITS DE PARIDAD

Si el número de bits de datos se designa por d , el número de bits de paridad , p, se determina por la relación:

2p≥d+ p+1 (1)

2.2 COLOCACIÓN DE LOS BITS DE PARIDAD EN EL CÓDIGO.

Considerando a los bits del código a desarrollar en el siguiente orden:

bit1 , bit 2, bit 3, bit 4, bit 5, bit 6, bit 7, etc.

Para asignar los bits de paridad tomamos las posiciones que corresponden a las potencias de dos en sentido ascendente (1, 2, 4, 8, …), de esta manera:

P1 ,P2 , D1 , P3 ,D2 , D3 ,D4

El símbolo Pn tendrá un determinado bit de

paridad y Dn será el lugar que contiene cada uno de los bits de datos.

2.3 ASIGNACIÓN DE LOS VALORES DE LOS BITS DE PARIDAD

Esta parte radica en asignar correcta y pertinentemente un valor de 1 o de 0 a los bits de paridad.

Primero se expresa en binario el número correspondiente a cada posición de los bits (decimal a binario), como se muestra en la Tabla 1. Luego indicamos las posiciones de los bits de paridad y datos.

1

Como podemos observar el número binario de posición del bit de paridad P1 tiene un 1 como su dígito más a la derecha. Este bit de paridad comprueba las posiciones de todos los bits, incluyéndose a si mismo, que tiene 1s en esa misma posición en el correspondiente número de posición en binario. Es decir el bit P1 de paridad, comprueba las posiciones de los bit 1, 3, 5 y 7. [1]

El número de posición en binario para el bit de paridad P2 tiene un 1 en su posición intermedia.Es por eso que este bit comprueba todas las posiciones de bit, incluyéndose a sí mismo, que tienen un 1 en esa idéntica posición. Por tanto el bit de paridad comprueba las posiciones de bit 2, 3, 6 y 7. [1]

El número de posición en binario para el bit de paridad P3 tiene un 1 como su bit más a la izquierda. Este bit comprueba entonces todas las posiciones de bit, incluyéndose a sí mismo, que tienen un 1 en esa idéntica posición. Por tanto el bit de paridad P3 comprueba las posiciones de bit 4, 5, 6 y 7. [1]

Tabla 1. Posiciones de los bits para un código de corrección de errores de 7 bits.

2.4 CÓMO DETECTAR Y CORREGIR UN ERROR CON EL CÓGIDO HAMMING

Los bits de paridad junto con sus respectivos bits deben comprobarse dependiendo de la paridad utilizada. Este es un previo acuerdo entre el emisor y receptor.

Por cada bit de paridad se realiza una comprobación al código.

Si existe un error al finalizar las comprobaciones, se descubrirá el bit con el error.

Los pasos son los siguiente:

1) Empezar con el grupo de bits de P12) Si el grupo tiene la paridad correcta. El 0

indica correcta y 1 que es incorrecta.3) Se repite el paso número 2 para cada

conjunto de paridad (P1 ,P2 ,P3,…)4) La primera comprobación de paridad genera

el bit menos significativo. 5) Todos los resultados de las comprobaciones

forman un número binario el cual indica la posición en decimal del bit erróneo. Cuando todas las comprobaciones son correctas

significa que el código receptado no contiene errores. [1]

EJEMPLO 1

Determinar el código Hamming para los bits de datos 10110 utilizando paridad impar.

SOLUCIÓN:

Paso 1. Determinar el número de bits de paridad necesario. En este caso, el número de bits de datos, d, es cinco. Utilizaremos un p=4. Reemplazamos estos datos en la Ec. (1).

2p=24=16d+ p+1=5+4+1=10

Cuatro bits de paridad son suficientes, pues se cumple la inecuación.

Número totalde bitsdecódigo=5+4=9

Paso 2. Construir una tabla de posiciones de los bits, Tabla 2, y escribir los bits de datos. Los bits de paridad se estipulan en los pasos siguientes. Observe que P4 se halla en la posición de bit 8.

Paso 3. Determinar los bits de paridad como sigue:

El bit P1 comprueba las posiciones de bit 1, 3, 5, 7 y 9, y debe ser igual a 1 para que haya un número impar de 1s (3) en este grupo.

El bit P2 comprueba las posiciones de bit 2, 3, 6 y 7, y debe ser igual a 0 para que haya un número impar de 1s (3) en este grupo.

El bit P3 comprueba las posiciones de bit 4, 5, 6 y 7, y debe ser igual a 1 para que haya un número impar de 1s (3) en este grupo.

El bit P4 comprueba las posiciones de bit 8 y 9, y debe ser igual a 1 para que haya un número impar de 1s (1) en este grupo.

Paso 4. Estos bits de paridad se introducen en la Tabla 2, y el código combinado resultante es 101101110.

Tabla 2. Posiciones de los bits para un código de corrección de errores de 9 bits.

2

Designación de bitPosición de bit

# posición en binario

P11001

P22010

P33011

P44100

P55101

P66110

P77111

Bits de datos (Dn)Bits de paridad (Pn)

Designación de bitPosición de bit

# posición en binario

P110001

P220010

P330011

P440100

P550101

P660110

P770111

P881000

P791001

Bits de datos (Dn) 1 0 1 1 0

Bits de paridad

(Pn) 1 0 1 1

Ahora suponiendo que el código Hamming encontrado se envía y se recibe el siguiente código 101101010.

Se lo debe corregir, sabiendo que emplea cuatro bits de paridad y el tipo de paridad es impar.

SOLUCIÓN:

Primeramente se construye una tabla para las posiciones de bits, como la tabla 3.

Primera comprobación de paridad:

Como sabemos el bit P1 comprueba las posiciones 1, 3, 5, 7 y 9. En este grupo hay dos 1s.

La comprobación de paridad es incorrecta. Entonces: 1 (LSB)

Segunda comprobación de paridad:

P2 analiza las posiciones 2, 3, 6 y 7. En este grupo hay dos 1s.

La comprobación de paridad es incorrecta.

Entonces: 1

Tercera comprobación de paridad:

P3 verifica las posiciones 4, 5, 6 y 7.En este grupo hay un 1.

La comprobación de paridad es incorrecta. Entonces: 1

Cuarta comprobación de paridad:

El bit P4 comprueba las posiciones 8 y 9. En este grupo hay un 1.

La comprobación de paridad es correcta. Entonces: 0 (MSB)

Resultado: Se puede ver que el código encontrado es el 0111, que es el 7 en binario.Esto quiere decir que 1 bit situado en la posiciones 7 es erróneo. Y podemos corregir el código, quedando 101101110.

Tabla 3. Corrección de un código Hamming de 9 bits.

3. CÓDIGO DE ERRORES POR CHEQUEO REDUNDANTE CÍCLICO (CRC)

3.1 CONCEPTO

El CRC o código polinomial es un método que detecta y corrige errores producidos en su gran mayoría por causas físicas, ya sean independientes o en paquetes de una gran secuencia de datos. [2]

3.2 CARACTERÍSTICAS Por su estructura algebraica es más fácil

encontrar métodos para la decodificación. [3] Son muy seguras al momento de detectar

errores generados debido al ruido producido en las señales portadoras de información emisor y receptor, por lo que su utilidad dentro de las telecomunicaciones se hace indispensable. [3]

Su implementación es muy simple pues solo necesitan registros de desplazamiento y conexiones de realimentación. [4]

Dentro de este método se utiliza una base finita binaria la que está constituida en su mayoría de 0 y 1. [3]

Se fundamenta de forma unánime en la división binaria. [4]

3.3 FUNCIONAMIENTOEl código CRC se basa esencialmente en el

tratamiento de secuencias de bits como representación de coeficientes de un polinomio, los mismos que están constituidos por 0 y 1. [3]

Un conjunto de k bits es considerado como una lista de coeficientes de un polinomio con k términos que inician desde xz−1 hasta x0. Este polinomio es considerado de grado z−1. Se afirma también que el polinomio con mayor orden es que más a la izquierda se encuentra así es el xz−1, y el siguiente

es el xz−2. [5]

Ejemplo 1

El número binario 110001 posee 6 bits, por lo tanto representará a un polinomio de seis términos con coeficientes 1, 1, 0, 0, 0 y 1 es decir como la Ec. (2) [6]

x5+ x4+x0(2)

Para realizar la aritmética polinomial se utiliza la operación de módulo 2 es decir no existen reglas de acarreo tanto para la suma como la resta. [6]

3.4 MODO DE EMPLEO DEL CÓDIGO CRC

Para emplear este código se hace necesario que el emisor y el receptor generen por adelantado un polinomio generador, G(x), los bits del mismo de orden mayor y menor deben ser 1. La suma de verificación para un conjunto de m bits, M(x) tiene que ser más larga que el del generador. El objetivo de esto es que la suma de verificación sea incluida al final del conjunto de bits tal que el polinomio representado por la suma sea divisible para el polinomio de generación. Así al momento que el receptor reciba el conjunto con la suma de verificación al intentar dividirla entre G(x) y

3

Designación de bitPosición de bit

# posición en binario

P110001

P220010

P330011

P440100

P550101

P660110

P770111

P881000

P791001

Código recibido 1 0 1 1 0 1 0 1 0

haya residuo indicará que existe un error en la transmisión. [6]

3.5 ALGORITMO PARA EL CÁLCULO DE LA SUMA DE VERIFICACIÓN

a. El grado de G(x ) es r. Implementar r bits al final del conjunto, m+r bits ahora

corresponderá al polinomio xrM (x)b. Dividir la cadena de bits de G(x ) para

xrM (x)c. Restar el residuo a la cadena de bits

oportuno a xrM (x) empleando la resta de módulo 2. El resultado de esto es el conjunto con suma de verificación que va a transmitirse. Este polinomio lo consideraremos como T (x),

d. Para realizar la comprobación, T (x) debe ser divisible entre G(x ), y si el resto es nulo no va a producirse ningún error al transferir los datos. [7]

Ejemplo 2

Para el conjunto 101100111 teniendo el generador G ( x )=x2+x+1 podemos observar en la Fig.1 como se realiza el cálculo de la suma de verificación.

Resolución

G ( x )=x2+x+1→´ 111´ . (r=2)

M (x )=x7+x5+ x2+x1+1→´ 10100111´

xrM ( x )=x9+x7+x4+ x3+x2→´ 1010011100 ´

Figura 1. Cálculo de la suma de verificación. Fuente: Google libros, 2015, [7]

Para verificar que no haya ningún error al transmitir los datos dividimos T (x) para G(x ) como se muestra en la Fig.2.

Figura 2. Cálculo de la verificación.Fuente: Google libros, 2015,

[7]

3.6 APLICACIONES En general este código de errores se lo

utiliza principalmente en telecomunicaciones, dispositivos de almacenamiento y en redes digitales. [3]

Básicamente lo podemos hallar en una unidad de disco principalmente de 512 bytes, donde cada uno de los bloques de datos esta protegido por un CRC, dentro de estos los errores pueden ser detectados y corregidos en ciertas unidades. [8]

El cógido CRC se lo encuentra también dentro de las redes de datos en las cuales cada conjunto de datos terminan con bits de comprobación del código por chequeo redundante. [8]

4. CONCLUSIONES

El código Hamming proporciona un método de detección y corrección de error de 1 solo bit.

El código Hamming utiliza varios bits de paridad para realizar varias comprobaciones y así lograr detectar donde se encuentra el bit erróneo.

La Ec (1), demuestra que para cada número binario de datos debe existir un número mínimo de bits de paridad.

El código CRC es muy utilizado dentro de las telecomunicaciones debido a que detectan errores causados por el ruido, al momento de transferir datos de emisor a receptor.

Debido a que se basa en operaciones aritméticas se hace fácil su uso.

Para el código CRC se utiliza una base finita binaria la cual está constituida de forma generalizada por 0 y 1.

El código CRC está basado principalmente en la división binaria y para su resolución se utilizan métodos como la resta de módulo en donde no se toman en cuenta los acarreos de las operaciones de suma y resta binaria.

4

El código CRC se encuentra de manera común en redes de datos y unidades de disco.

5. RECOMENDACIONES

Realizar las investigaciones correspondientes a división binaria y operación de módulo 2 para poder resolver la verificación de suma y las demás operaciones planteadas en la resolución del código CRC.

Buscar fuentes de consulta fiables para evitar posibles confusiones al momento de investigar el código Hamming y CRC.

Los errores de tranmisión se pueden producir con mas frecuencia si dicho proceso se lo realiza en un lugar donde el ruido eléctrico se eleve, por lo tanto, para una mayor seguridad evitar esos lugares.

6. REFERENCIAS

[1] T. L. Floyd, Fundamentos de Sistemas Digitales, vol. 9 Edicion, Madrid: Prentice Hall, 2006, pp. 247-249.

[2] M. d. P. A. Ramos, «https://books.google.com.ec/books?id=4zjxk81LgKIC&pg=PA30&dq=CODIGO+CRC&hl=es&sa=X&ei=ByM4VZ7uHa7nsATYwoGIDg&ved=0CCEQ6AEwAQ#v=onepage&q=CODIGO%20CRC&f=false,» 2010. [En línea]. [Último acceso: 22 04 2015].

[3] Varios, «http://es.wikipedia.org/wiki/Verificaci%C3%B3n_por_redundancia_c%C3%ADclica,» 01 04 2015. [En línea]. [Último acceso: 22 04 2015].

[4] E. Mandado, «https://books.google.com.ec/books?id=V7JpKkZaEYMC&pg=PA24&dq=CODIGO+de+deteccion+de+error+CRC&hl=es&sa=X&ei=2yU4VdqgD9e1sQThtYGABg&ved=0CCEQ6AEwAQ#v=onepage&q=CODIGO%20de%20deteccion%20de%20error%20CRC&f=false,» 2007. [En línea]. [Último acceso: 22 04 2015].

[5] J. Í. Griera, «https://books.google.com.ec/books?id=QAxAJEBgUWYC&dq=CODIGO+CRC+EJEMPLOS&hl=es&source=gbs_navlinks_s,» 2009. [En línea]. [Último acceso: 22 04 2015].

5

[6] A. S. Tanenbaum, «https://books.google.com.ec/books?id=WWD-4oF9hjEC&dq=CODIGO+CRC+EJEMPLOS&hl=es&source=gbs_navlinks_s,» 2003. [En línea]. [Último acceso: 22 04 2015].

[7] P. Gil, «https://books.google.com.ec/books?id=On6y2SEaWyMC&pg=PA107&dq=CODIGO+de+deteccion+de+error+CRC&hl=es&sa=X&ei=PCY4VYKMJLG0sASasIGwBw&ved=0CEwQ6AEwCDgK#v=onepage&q=CODIGO%20de%20deteccion%20de%20error%20CRC&f=false,» 01 09 2010. [En línea]. [Último acceso: 22 04 2015].

[8] J. F. Wakerly, «https://books.google.com.ec/books?id=moZli0LrjngC&pg=PA65&dq=CODIGO+CRC&hl=es&sa=X&ei=ByM4VZ7uHa7nsATYwoGIDg&ved=0CBsQ6AEwAA#v=onepage&q=CODIGO%20CRC&f=false,» 2001. [En línea]. [Último acceso: 22 04 2015].

6