Comprobacion de Redundancia Ciclica

7/27/2019 Comprobacion de Redundancia Ciclica

http://slidepdf.com/reader/full/comprobacion-de-redundancia-ciclica 1/6

1CRC

COMPROBACION DE

REDUNDANCIA CICLICAMientras que los controles de paridad son útiles para velocidades de datos bajas y

mensajes asíncronos donde los espacios entre bytes sucesivos, a veces grandes, hacen la

recopilación de datos en un bloque imposible, para asegurar la fiabilidad de los datos es

necesario un esquema de detección de errores mucho más robusto. La comprobación de

redundancia cíclica o CRC es uno de esos mecanismos y requiere que los datos estén

divididos en bloques, por lo que se denomina un código de bloque.

¿Qué es un CRC?

Los CRC son una función “hash” que detecta cambios accidentales en los datos

informáticos, estos códigos son utilizados en las redes de telecomunicaciones digitales y

dispositivos de almacenamiento tales como unidades de disco duro. Esta técnica fue

inventada por W. Wesley Peterson en 1961 y desarrollada por el CCITT (Comité Consultatif

International Télégraphique et Téléphonique). Los CRC son muy simples de implementar en

hardware y pueden ser fácilmente analizados matemáticamente. Es una de las mejores

técnicas en la detección de errores de transmisión comúnmente utilizadas.

Función Hash: una función hash (o un algoritmo hash) es una función que produce unasalida de longitud fija para cualquier valor de entrada. La probabilidad de que dos

entradas diferentes produzcan una misma salida es muy baja.

El perro Funcion Hash ARFTGYHUJIJD

El perronegro

camina soloFuncion Hash DTYHJIUTREDS

El perro negro Funcion Hash FTREDSYUIJHG



2CRC

Funcionamiento

Dado un bloque o mensaje de k-bits, el transmisor genera una secuencia de bits,

denominada secuencia de comprobación de la trama (FCS, Frame Check Sequence), detal manera que la trama resultante, con n bits, sea divisible por algún número

predeterminado. El receptor dividirá la trama recibida entre ese número y si no hay residuo

en la división, supondrá que no ha habido errores.

El objetivo es que la división , donde P es el patrón de (este es el divisor

elegido), no tenga residuo alguno. Es evidente que:

Es decir, multiplicar D por en realidad equivale a desplazar hacia la izquierda bits,

añadiendo ceros al resultado. Finalmente, en la obtención de T, al sumar F lo que estamos

haciendo es, en realidad, concatenar D y F. El objetivo es hacer T divisible entre P.

Supóngase que se divide entre P:

Hay un cociente y un residuo, el residuo será siempre al menos un bit más corto que el

divisor, ya que la división es módulo 2. La secuencia de comprobación de la trama, o FCS,

será igual al resto de la división. Entonces:

El patrón P se elige con un bit más que la longitud de la FCS deseada. El patrón elegido en

particular, dependerá del tipo de errores que se espera sufrir. Como mínimo, el bit más

significativo y el menos significativo de P deben ser 1.

Hay un método conciso para detectar la presencia de uno o más errores. Un error

provocará que se invierta un bit. Esto es equivalente a calcular la función XOR entre el bit y

1. Por tanto, los errores en una trama de n bits se pueden representar mediante una

palabra de n bits, teniendo 1 en aquellas posiciones que coincidan con un error. La trama

Tr resultante se puede expresar como:

F=FCS de n-k bits

T=Trama Resultante

M=Bloque de k



3CRC

Donde:

T= trama transmitida.

E= patrón de errores con 1 en las posiciones donde haya un error.

Tr= trama recibida.

Si ha habido un error (E≠0), el receptor fallará en la detección si, y solamente si, Tr es

divisible entre P, lo que es equivalente a que E sea divisible entre P. Intuitivamente, esto

parece que es un evento improbable.

Polinomios Generadores: Una segunda forma de ver el proceso de CRC es expresar todos

los valores como polinomios de una variable X, con coeficientes binarios. Los coeficientes

corresponderán con los bits del número en binario. Así, si:

, se tendrá que

, se tiene que

De nuevo, las operaciones se realizan en aritmética módulo 2. El procedimiento de CRC se

puede describir de la siguiente manera:

Un error E(X) no se detectará solamente si es divisible entre P(X). Es más, se puede

demostrar que si todos los patrones de error son equiprobables, entonces, para una ráfaga

de errores con longitud r+1, la probabilidad de que no se detecte un error es ⁄ , y para

ráfagas mayores, la probabilidad es ⁄ , donde r es la longitud de la FCS.

Una comprobación de redundancia cíclica también se aplica a los dispositivos de

almacenamiento como discos duros. En este caso, los bits de control se asignan a cada

bloque en el disco duro. Cuando un archivo corrupto o incompleto es leído por el

ordenador, se informa del error de redundancia cíclica. Este puede ser de otro dispositivo

de almacenamiento o desde CD o DVD. Las razones más comunes para los errores son

fallas del sistema, archivos incompletos o corruptos, o archivos con gran cantidad de

errores.



4CRC

Los diseños polinomios para un CRC dependen de la longitud del bloque a proteger, las

características de protección contra errores, los recursos para la implementación del CRC

y el rendimiento deseado.

Es frecuente utilizar alguna de las cuatro definiciones siguientes para P(X):

Nombre Común rGenerador

Polinomio Hex

CRC-12 12 80F

CRC-16 16 800F

CRC-CCITT 16 1021

CRC-32 32

04C1 1DB7

Implementación por Hardware

Para implementar un circuito de hardware para el cálculo de la suma de comprobación

CRC, se reduce el proceso de división polinomios de sus elementos esenciales.

El procedimiento CRC se puede representar, y de hecho implementar, con un circuito

divisor formado por compuertas XOR y un registro de desplazamiento. El registro de

desplazamiento es una cadena de elementos de memoria de 1 bit. Cada elemento tiene

una línea de salida que contendrá el valor actualmente almacenado, además de una

línea de entrada.

A instantes discretos de tiempo, establecidos por una señal de reloj, el valor almacenado

en el elemento de memoria se reemplaza por el valor que se encuentre en la línea de

entrada. Todo el registro utiliza una señal de reloj común, que provoca un desplazamiento

de un bit a lo largo de todo el registro.

El circuito de para la implementación por hardware de un CRC puede ser descrito de

manera informal como sigue:

1. El registro contendrá bits, igual a la longitud de la FCS.

2. Hay compuertas XOR.

3. La presencia o ausencia de una compuerta corresponderá con la presencia o

ausencia del término correspondiente en el polinomio divisor, P(X), excluyendo a los

términos 1 y



5CRC

La siguiente figura nos muestra una arquitectura genérica para la realización de un código

de CRC mediante un registro de desplazamiento para el polinomio:

∑

Arquitectura genérica de una CRC para implementar la división entre

Donde , y todos los otros son iguales a 0 o 1. Es habitual mostrar el registro

del procedimiento CRC con desplazamientos hacia la derecha, lo cual es contrario a la

división binaria. Debido a que los números binarios se representan habitualmente con el bit

más significativo a la izquierda, es más apropiado usar un registro de desplazamiento a laizquierda como el aquí usado.

El mismo circuito se utiliza tanto para la creación y de verificación de la CRC. Cuando la

creación de la FCS, el circuito acepta los bits de la trama sin procesar y luego una

secuencia de ceros. La longitud de la secuencia es la misma que la longitud de la FCS. El

contenido del registro de desplazamiento será el FCS para anexar. Al comprobar la FCS, el

circuito acepta los bits de la trama recibida. El contenido del registro de desplazamiento

debe ser cero o de lo contrario hay errores.



6CRC

BibliografíaBlack, R. (18 de Febrero de 1994). Bluebook. Obtenido de University of Cambridge

Computer Laboratory Systems Research Group:

http://www.cl.cam.ac.uk/research/srg/bluebook/21/crc/crc.html

Houghton, A. (1996). The Engineer's Error Coding Handbook. Sheffield (UK): CHAPMAN &

HALL.

Martin Stigge, H. P.-P. (24 de 05 de 2006). Humboldt University Berlin. Obtenido de Reversing

CRC – Theory and Practice: http://sar.informatik.hu-

berlin.de/research/publications/SAR-PR-2006-05/SAR-PR-2006-05_.pdf

Documents

Comprobacion de Redundancia Ciclica