Les traigo un trabajo sobre CRC aplicado a la Informática, espero que les sirva!
Este apartado trata del código detector-corrector de errores polinómico (también conocido como código de redundancia cíclica CRC). El método de redundancia cíclica (CRC Cyclic Redundancy Check) es otra técnica muy usada para detección de errores. Trabaja al nivel de mensaje, agregando varios caracteres de control al final, siendo lo más común 2 o 4 bytes de control.
Se divide la secuencia de bits a enviar, por un numero binario predeterminado. El resto de la división se adiciona a él mensaje como secuencia de control.
Por una regla aritmética simple, si el divisor es un numero de 16 bits, podemos tener la certeza que el resto siempre podrá almacenares en dos bytes, de donde, agregando 2 caracteres a nuestro mensaje tendremos el método implementado.
El extremo receptor realiza el mismo cálculo que el emisor y compara el resultado obtenido con la secuencia de control recibida. Si no coinciden, equivale a una indicación de error.
Los códigos polinómicos se basan en el tratamiento de series de bits como si fueran representaciones de polinomios, con coeficientes de valor 0 y 1 únicamente. Una trama de k bits se ve como una lista de coeficientes de un polinomio con k términos, cubriendo un rango desde xk-1 hasta x0. A este tipo de polinomio se le conoce como polinomio de grado k-1. El bit de orden mas alto (el más a la izquierda) es el coeficiente del término xk-1; el siguiente bit es el coeficiente del término xk-2, y así sucesivamente. Por ejemplo, el código 110001 tiene 6 bits y, por consiguiente, representa a un polinomio de tres términos, que contienen los siguientes coeficientes 1, 1, 0, 0, 0 y 0, es decir: x5 +x4 + x0.
De acuerdo con las teorías de las reglas de la teoría del campo algebraico, la aritmética del polinomio se realiza en módulo 2. No hay términos de acarreo para la suma ni de préstamo para la resta; las dos operaciones son idénticas al OR EXCLUSIVO. Por ejemplo:
Aritmética binaria efectuada en módulo 2.
La división larga se realiza de la misma manera que en el caso binario, con excepción de la resta que se efectúa en módulo 2, como en el caso anterior. Se dice que el divisor "cabe en" el dividendo, si tiene tantos bits como este último.
Cuando se emplea el método del código polinómico, el emisor y el receptor deberán estar de acuerdo respecto a un polinomio generador, G(x), en forma anticipada. Los bits de orden superior e inferior del generador deben ser 1. Para calcular el código de redundancia de alguna trama con m bits, correspondiente al polinomio M(x), la trama deberá ser más grande que el polinomio generador. La idea básica consiste en incluir un código de redundancia al final de la trama, de tal manera que, el polinomio representado por la trama con el código de redundancia sea divisible por G(x). Cuando el receptor recibe la trama de suma comprobada, intenta dividirla entre G(x). Si existe un resto, habrá ocurrido un error de transmisión.
El algoritmo para calcular la redundancia es el siguiente:
1. Sea r el grado de G(x). Agregar r bits a cero al extremo de orden inferior de la trama, de tal manera que ahora contenga m + r bits, y corresponda al polinomio xrM(x).
1. Dividir la serie de bits correspondientes a xrM(x) entre la serie de bits correspondientes a G(x), empleando la división en módulo 2.
1. Restar el resto (que siempre tiene r o menos bits) de la serie de bits correspondientes a xrM(x), empleando la resta en módulo 2. El resultado es la trama lista para trasmitir. Llámese T(x) a este polinomio.
En la siguiente figura se ilustra el cálculo para la trama 1101011011 y G(x) = x4+x+1
Cálculo de la Redundancia Cíclica.
Un código polinómico con r bits de redundancia, podrá detectar todas las ráfagas de errores de longitud <= r. Una ráfaga de error de longitud k puede representarse por la expresión xi(xk-1+...+1), donde i determina qué tan lejos del extremo derecho de la trama recibida, queda localizada la ráfaga. Si G(x) contiene un termino x0, no tendrá a xi como factor, por lo cual, si el grado de la expresión entre paréntesis es menor que el grado de G(x), el resto nunca podrá ser cero.
También se puede demostrar que, cuando ocurre una ráfaga de error mayor que r + 1 bits, o bien, que ocurren varias ráfagas cortas, la probabilidad de que una trama mala pase inadvertida es de ½ r, suponiendo que todos los conjuntos de bits son semejantes.
Tres polinomios se han convertido en normas internacionales:
CRC-12 = x12 + x11 + x3 + x2 + x1 + 1
CRC-16 = x16 + x15 + x2 + 1
CRC-CCITT = x16 + x12 + x5 + 1
Los tres contienen el término x + 1 como factor primo. El CRC-12 se utiliza cuando la longitud del carácter es de 6 bits; en tanto que los otros dos se emplean para caracteres de 8 bits. Un código de redundancia de 16 bits, como las normas CRC-16 o CRC-CCITT, captura todos los errores simples y dobles, todos los errores con un número impar de bits, todos los errores de ráfagas con longitudes de 16 o menos bits, 99.997% de los errores de ráfagas de 17 bits y 99.998% de los errores de ráfagas de longitudes de 18 bits o mayores.
Este apartado trata del código detector-corrector de errores polinómico (también conocido como código de redundancia cíclica CRC). El método de redundancia cíclica (CRC Cyclic Redundancy Check) es otra técnica muy usada para detección de errores. Trabaja al nivel de mensaje, agregando varios caracteres de control al final, siendo lo más común 2 o 4 bytes de control.
Se divide la secuencia de bits a enviar, por un numero binario predeterminado. El resto de la división se adiciona a él mensaje como secuencia de control.
Por una regla aritmética simple, si el divisor es un numero de 16 bits, podemos tener la certeza que el resto siempre podrá almacenares en dos bytes, de donde, agregando 2 caracteres a nuestro mensaje tendremos el método implementado.
El extremo receptor realiza el mismo cálculo que el emisor y compara el resultado obtenido con la secuencia de control recibida. Si no coinciden, equivale a una indicación de error.
Los códigos polinómicos se basan en el tratamiento de series de bits como si fueran representaciones de polinomios, con coeficientes de valor 0 y 1 únicamente. Una trama de k bits se ve como una lista de coeficientes de un polinomio con k términos, cubriendo un rango desde xk-1 hasta x0. A este tipo de polinomio se le conoce como polinomio de grado k-1. El bit de orden mas alto (el más a la izquierda) es el coeficiente del término xk-1; el siguiente bit es el coeficiente del término xk-2, y así sucesivamente. Por ejemplo, el código 110001 tiene 6 bits y, por consiguiente, representa a un polinomio de tres términos, que contienen los siguientes coeficientes 1, 1, 0, 0, 0 y 0, es decir: x5 +x4 + x0.
De acuerdo con las teorías de las reglas de la teoría del campo algebraico, la aritmética del polinomio se realiza en módulo 2. No hay términos de acarreo para la suma ni de préstamo para la resta; las dos operaciones son idénticas al OR EXCLUSIVO. Por ejemplo:
Aritmética binaria efectuada en módulo 2.
La división larga se realiza de la misma manera que en el caso binario, con excepción de la resta que se efectúa en módulo 2, como en el caso anterior. Se dice que el divisor "cabe en" el dividendo, si tiene tantos bits como este último.
Cuando se emplea el método del código polinómico, el emisor y el receptor deberán estar de acuerdo respecto a un polinomio generador, G(x), en forma anticipada. Los bits de orden superior e inferior del generador deben ser 1. Para calcular el código de redundancia de alguna trama con m bits, correspondiente al polinomio M(x), la trama deberá ser más grande que el polinomio generador. La idea básica consiste en incluir un código de redundancia al final de la trama, de tal manera que, el polinomio representado por la trama con el código de redundancia sea divisible por G(x). Cuando el receptor recibe la trama de suma comprobada, intenta dividirla entre G(x). Si existe un resto, habrá ocurrido un error de transmisión.
El algoritmo para calcular la redundancia es el siguiente:
1. Sea r el grado de G(x). Agregar r bits a cero al extremo de orden inferior de la trama, de tal manera que ahora contenga m + r bits, y corresponda al polinomio xrM(x).
1. Dividir la serie de bits correspondientes a xrM(x) entre la serie de bits correspondientes a G(x), empleando la división en módulo 2.
1. Restar el resto (que siempre tiene r o menos bits) de la serie de bits correspondientes a xrM(x), empleando la resta en módulo 2. El resultado es la trama lista para trasmitir. Llámese T(x) a este polinomio.
En la siguiente figura se ilustra el cálculo para la trama 1101011011 y G(x) = x4+x+1
Cálculo de la Redundancia Cíclica.
Un código polinómico con r bits de redundancia, podrá detectar todas las ráfagas de errores de longitud <= r. Una ráfaga de error de longitud k puede representarse por la expresión xi(xk-1+...+1), donde i determina qué tan lejos del extremo derecho de la trama recibida, queda localizada la ráfaga. Si G(x) contiene un termino x0, no tendrá a xi como factor, por lo cual, si el grado de la expresión entre paréntesis es menor que el grado de G(x), el resto nunca podrá ser cero.
También se puede demostrar que, cuando ocurre una ráfaga de error mayor que r + 1 bits, o bien, que ocurren varias ráfagas cortas, la probabilidad de que una trama mala pase inadvertida es de ½ r, suponiendo que todos los conjuntos de bits son semejantes.
Tres polinomios se han convertido en normas internacionales:
CRC-12 = x12 + x11 + x3 + x2 + x1 + 1
CRC-16 = x16 + x15 + x2 + 1
CRC-CCITT = x16 + x12 + x5 + 1
Los tres contienen el término x + 1 como factor primo. El CRC-12 se utiliza cuando la longitud del carácter es de 6 bits; en tanto que los otros dos se emplean para caracteres de 8 bits. Un código de redundancia de 16 bits, como las normas CRC-16 o CRC-CCITT, captura todos los errores simples y dobles, todos los errores con un número impar de bits, todos los errores de ráfagas con longitudes de 16 o menos bits, 99.997% de los errores de ráfagas de 17 bits y 99.998% de los errores de ráfagas de longitudes de 18 bits o mayores.