UNIVERSISDAD DE LAS FUERZAS ARMAS- ESPELESCOLA CARLOS

Ingeniería Automotriz, Quinto Nivel “A”, Escuela Politécnica del Ejército Extensión Latacunga, Márquez de Maeza S/N Latacunga, Ecuador.

Email: davidescola18@hotmail.es

Fecha de presentación: 04 de septiembre de 2013

RESUMEN: Los algoritmos se diferencian en su forma de procesar el mensaje es decir se puede tomar la información por byts o de bit en bit lo que determina su velocidad1

Palabras Claves: Códigos de detección de errores, código Hamming, código CRC

Códigos de Detección de Errores

La detección y corrección de errores es una importante práctica para el mantenimiento e integridad de los datos a través de diferentes procedimientos y dispositivos como medios de almacenamiento confiables.2

La comunicación entrevarias computadoras produce continuamente un movimiento de datos, generalmente por canales no diseñados para este propósito (línea telefónica), y que introducen un ruido externo que produce errores en la transmisión. Por lo tanto, debemos asegurarnos que si dicho movimiento causa errores, éstos puedan ser detectados. El método para detectar y corregir errores es incluir en los bloques de datos transmitidos bits adicionales denominados redundancia

Código Hamming

En  informática, el código de Hamming es un código detector y corrector de errores que lleva el nombre de su inventor, Richard Hamming. Se pueden detectar errores en un bit y corregirlos, sin embargo no se distingue entre errores de dos bits y de un bit (para lo que se usa codigo Hamming . Esto representa una mejora respecto a los códigos con bit de prioridad, que pueden detectar errores en sólo un bit, pero no pueden corregirlo.

Si se añaden junto al mensaje más bits detectores-correctores de error y si esos bits se pueden ordenar de modo que diferentes bits de error producen diferentes resultados, entonces los bits erróneos podrían ser identificados. En un conjunto de siete bits, hay sólo siete posibles

1 (LLORIS-PRIETO-PARRILA, 2006)2 (THOMAS, 2000)

errores de bit, por lo que con tres bits de control de error se podría especificar, además de que ocurrió un error, en qué bit fue.

El algoritmo de Hamming (7.4) puede corregir cualquier error de un solo bit, pero cuando hay errores en más de un bit, la palabra transmitida se confunde con otra con error en un sólo bit, siendo corregida, pero de forma incorrecta, es decir que la palabra que se corrige es otra distinta a la original, y el mensaje final será incorrecto sin saberlo. Para poder detectar errores de dos bits, se debe añadir un bit más, y el código se llama Hamming extendido. El procedimiento para esto se explica al final.

El algoritmo es el siguiente:

1. Todos los bits cuya posición es potencia de dos se utilizan como bits de paridad (posiciones 1, 2, 4, 8, 16, 32, 64, 128,etc.).

2. Los bits del resto de posiciones son utilizados como bits de datos (posiciones 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17, etc.).

3. Cada bit de paridad se obtiene calculando la paridad de alguno de los bits de datos. La posición del bit de paridad determina la secuencia de los bits que alternativamente comprueba y salta, a partir de éste, tal y como se explica a continuación.

Posición 1: salta 0, comprueba 1, salta 1, comprueba 1, etc.

Posición 2: salta 1, comprueba 2, salta 2, comprueba 2, etc.

Posición 4: salta 3, comprueba 4, salta 4, comprueba 4, etc.

Posición 8: salta 7, comprueba 8, salta 8, comprueba 8, etc.

Posición 16: salta 15, comprueba 16, salta 16, comprueba 16, etc.

Regla general para la posición n es: salta n-1 bits, comprueba n bits, salta n bits, comprueba n bits. Y así sucesivamente.

En otras palabras, el bit de paridad de la posición 2k  comprueba los bits en las posiciones que tengan al bit k en su representación binaria. Dicho a la inversa, el bit 4, chequea los bits 4, 5, 6, 7, al ser estos los de su representación binaria: 4=1002, 5=1012, 6=1102 y 7=1112.

Por el contrario, el mismo bit de paridad no comprueba el bit 8, debido a que en su representación binaria el bit número 3 (2^3=4) es igual a 0 (8=10002). Así, por ejemplo, para los primeros términos se tiene:

En la Posición 1 (2^0 = 1), comprobaríamos los bits: 1, 3, 5, 7, 9, 11, 13...

En la Posición 2 (2^1 = 2), los bits: 2, 3, 6, 7, 10, 11, 14, 15...

En la Posición 4 (2^2 = 4), los bits: 4, 5, 6, 7, 12, 13, 14, 15, 20, 21, 22, 23...

En la Posición 8 (2^3 = 8) tendríamos: 8, 9, 10, 11, 12, 13, 14, 15, 24-31...

Siguiendo el algoritmo hasta completar la nueva cadena.

Consideremos la palabra de datos de 7 bits "0110101". Para ver cómo se generan y utilizan los códigos Hamming para detectar un error, observe las tablas siguientes. Se utiliza la d para indicar los bits de datos y la p para los de paridad.

En primer lugar los bits de datos se insertan en las posiciones apropiadas y los bits de paridad calculados en cada caso usando la paridad par.

Tabla 1 Cálculo de los bits de paridad en el código Hamming

P1 = D1 exor D2 exor D4 exor D5 exor D7P2 = D1 exor D3 exor D4 exor D6 exor D7P3 = D2 exor D3 exor D4P4 = D5 exor D6 exor D7

La nueva palabra de datos (con los bits de paridad) es ahora "10001100101". Consideremos ahora que el bit de la derecha, por error, cambia de 1 a 0. La nueva palabra de datos será ahora "10001100100".

Sin errores

Tabla 2 Comprobación de los bits de paridad (con primer bit de la derecha sin cambiar)

Con errores

Tabla 3 Comprobación de los bits de paridad (con primer bit de la derecha cambiado)

Si se analiza en la tabla 3 la paridad que se debe obtener a la derecha tras la llegada del mensaje sin errores debe ser siempre 0 (por cada fila), pero en el momento en que ocurre un error esta paridad cambia a 1, de allí el nombre de la columna "prueba de paridad 1". Se observa que en la fila en que el cambio no afectó la paridad es cero y llega sin errores.

El paso final es evaluar los bits de paridad (recuerde que el fallo se encuentra en d7). El valor entero que representan los bits de paridad es 11 (si no hubieran ocurrido errores este valor seria 0), lo que significa que el bit décimo primero de la palabra de datos (bits de paridad incluidos) es el erróneo y necesita ser cambiado.

Tabla 4

Cambiando el bit décimo primero 10001100100 se obtiene de nuevo 10001100101. Eliminando los bits de patrón de la paridad no se tienen en cuenta los bits de paridad. Si el error se produjera en uno de ellos, en la comprobación sólo se detectaría un error, justo el correspondiente al bit de paridad causante del mismo.

Código Cíclico o CRC

El CRC es un código de detección de error cuyo cálculo es una larga división de computación en el que se descarta el cociente y el resto se convierte en el resultado, con la importante diferencia de que la aritmética que usamos conforma que el cálculo utilizado es el arrastre de un campo, en este caso los bits. El tamaño del resto es siempre menor que la longitud del divisor, que, por lo tanto, determina el tamaño del resultado. La definición de un CRC especifica el divisor que se utilizará, entre otras cosas. Aunque un CRC se puede construir utilizando cualquier tipo de regla finita, todos los CRC de uso común emplean una base

finita binaria, esta base consta de dos elementos, generalmente el 0 y 1.

El concepto de CRC consiste en tratar a las secuencias binarias como polinomios binarios, denotando polinomios cuyos coeficientes se correspondan con la secuencia binaria. Por ejemplo, la secuencia binaria 0110101001 se puede representar como un polinomio, como se muestra a continuación:

0*X9 + 1*X8 + 1*X7 + 0*X6 + 1*X5 + 0*X4 + 1*X3 + 0*X2 + 0*X1 + 1*X0

siendo

X8 + X7 + X5 + X3 + X0

o

X8 + X7 + X5 + X3 + 1

Debemos ahora especificar la clave para efectuar la división. La selección de esta clave es esencial para la capacidad de respuesta del código frente a los diversos tipos de errores. El CCITT especifica algunas claves, que como se van a emplear para dividir un polinomio serán también polinomios, denominados polinomio generador. En el CRC denominado CRC-16 correspondiente a la norma CCITT V.41, se utiliza el siguiente polinomio generador:

G(x) = x16 + x12 + x5 + x0

donde x0= 1.

El procedimiento es el siguiente: se toma el polinomio de datos P(x) y se multiplica por xk

donde k es el exponente más alto de G(x), este polinomio así construido se divide por G(x) y se obtiene un polinomio resto R(x),llamado BCS (Block Character Sequence), luego se procede a enviar el polinomio T(x) construido así:

T(x) = xk P(x) + R(x)

En el extremo receptor se procederá a extraer lo que suponemos es xk P(x), lo dividimos por G(x) y calculamos un polinomio resto que si coincide con el R(x) recibido indicará que no hay errores.

La longitud de P(x) es variable,algunos autores hablan de 4 bytes para CRC-16 y otros dicen que se aplica a la trama ó bloque ó paquete.

La operación de división empleada en CRC se denomina de módulo 2. Esta división es diferente de la que estamos acostumbrados y funciona así:

• La restas durante la división (o sea la obtención del resto parcial ó final) no son aritméticas sino módulo 2, lo que significa una operación XOR entre los dígitos binarios que se están restando( 1 y 0 da 1, 0 y 1 da 1, 0 y 0 dá 0, 1 y 1 dá 0).

• Sí el primer bit del resto parcial es 1 y queda uno ó más bits del dividendo se baja el primer bit de la izquierda no usado y se hace el XOR. En caso contrario se bajan bits de la izquierda

del dividendo hasta que este resto con los bits bajados esté encabezado por un 1 y tenga la misma longitud del divisor. De no lograrse el resto con todos los bits bajados será el resto final de la división

Ejemplo:

Determine el BSC(Block Character Sequence), para los siguientes polinomios generadores de datos y CRC.

datos P(x) = x7 + x5 + x4 + x2 + x1 + x0

ó 10110111

CRC G(x) = x5 + x4 + x1 + x0

ó 110011

Solución

Primero P(x) es multiplicado por el número de bits en el código CRC, 5.

x5(x7 + x5 + x4 + x2 + x1 + x0) = x12 + x10 + x9 + x7 + x6 + x5= 1011011100000

Al dividir este polinomio por G(x) obtenemos R(x) ó BCS que resulta:

Resto 01001 significa R(x) = 0x4 + 1x3 + 0x2 + 0x + 1

Se transmite entoces T(x) = xkP(x) + R(x) o sea 1011011101001

BibliografíaLLORIS-PRIETO-PARRILA. (2006). SISTEMAS DIGITALES. ARAVACA(MADRID): Concepcion Fernadez Madrid.

RONALD, T. (2000). SISTEMAS DIGITALES PRINCIPIOS Y APLICACIONES . Prentice Hall.

THOMAS, F. (2000). FUNDAMENTOS DE SISTEMAS DIGITALES . Pearson education .

VALLEJO, A. M. (2013, septiembre 02). UN Virtual. Retrieved from http://es.kioskea.net/contents/59-verificacion-de-errores