Comprobacion de Redundancia Ciclica

El perro


Funcion Hash


ARFTGYHUJIJD









El perro negro camina solo


Funcion Hash


DTYHJIUTREDS









El perro negro


Funcion Hash


FTREDSYUIJHG









CRCCRC66
CRC
CRC
6
6
comprobacion de Redundancia ciclica
Mientras 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 una salida de longitud fija para cualquier valor de entrada. La probabilidad de que dos entradas diferentes produzcan una misma salida es muy baja.









Funcionamiento
Dado un bloque o mensaje de k-bits, el transmisor genera una secuencia de (n-k) bits, denominada secuencia de comprobación de la trama (FCS, Frame Check Sequence), de tal 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.
M=Bloque de k bitsM=Bloque de k bitsF=FCS de n-k bitsF=FCS de n-k bits
M=Bloque de k bits
M=Bloque de k bits
F=FCS de n-k bits
F=FCS de n-k bits
T=Trama ResultanteT=Trama Resultante
T=Trama Resultante
T=Trama Resultante

El objetivo es que la división T/P, donde P es el patrón de n-k+1 (este es el divisor elegido), no tenga residuo alguno. Es evidente que:
T=2n-kD+F
Es decir, multiplicar D por 2n-k en realidad equivale a desplazar hacia la izquierda n-k 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 2n-kD entre P:
2n-kDP=Q+RP
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:
T=2n-kD+R
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:
Tr=T E
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:
D=110011, se tendrá que DX=X5+X4+X+1
P=11001, se tiene que PX=X4+X3+1
De nuevo, las operaciones se realizan en aritmética módulo 2. El procedimiento de CRC se puede describir de la siguiente manera:

Xn-kD(X)P(X)=QX+R(X)P(X)
TX=Xn-kDX+R(X)

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 12r-1, y para ráfagas mayores, la probabilidad es 12r, 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.
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
r
Generador


Polinomio
Hex
CRC-12
12
X12+X11+X3+X2+X+1
80F
CRC-16
16
X16+X15+X2+1
800F
CRC-CCITT
16
X16+X12+X5+1
1021
CRC-32
32
X32+X26+X23+X22+X16+
X12+X11+X8+X7+X5+X4+
X2X+1
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:
El registro contendrá n-k bits, igual a la longitud de la FCS.

Hay n-k compuertas XOR.

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 Xn-k

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:
PX=i=0n-kAiXi

Arquitectura genérica de una CRC para implementar la división entre
(1+A1X+A2X2+…+An-1Xn-k-1+Xn-k)

Donde A=An-k=1, y todos los otros Ai 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 la izquierda 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.





Bibliografía
Black, 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








El perro negro

Funcion Hash

FTREDSYUIJHG
El perro negro camina solo

Funcion Hash

DTYHJIUTREDS
El perro

Funcion Hash

ARFTGYHUJIJD