Detección de errores Crc

Deteccion de errores Crc

Deteccion de errores Crc : Multi-millones de consejos para hacer su vida mas facil.

UN dolor GUIA PARA el ERROR de CRC ALGORITMOS de DETECCION

===================================================================
Este articulo ha sido colocado en la web por SPLat Controles de decisiones
de la SPLat gama de microPLCs utilizan para OEM.
SPLat es el mundo & #39 mas costo-efectiva microPLC.
a partir De off-the-shelf productos que ahorran mas de lo que cuestan, a
personalizado por el usuario de los controladores programables, SPLat es un sorprendente nuevo
forma de hacer controles electronicos para maquinas en las cantidades de
1 a 50,000 p.una.

Para retirar SPLat copia y pega la siguiente URL en su navegador
la ubicacion o la direccion de la ventana:
http://splatco.com
===================================================================
Articulo reproducido con permiso del propietario del copyright. ¡A disfrutar!
===================================================================

UN dolor GUIA PARA el ERROR de CRC ALGORITMOS de DETECCION
==================================================
'Todo lo que usted queria saber sobre el CRC de los algoritmos, pero tenian miedo
a preguntar por miedo a que los errores en su comprension podria ser detectado.'

Version : 3.
Fecha : 19 de agosto de 1993.
Autor : Ross N. Williams.
Net : [email protected].
FTP : ftp.adelaide.edu.au/pub/rocksoft/crc_v3.txt
Empresa : Rocksoft^tm Pty Ltd.
Caracol : 16 Lerwick Avenue, Hazelwood Parque 5066, Australia.
Fax : 61 8 373-4911 (c/- Entrenudo Systems Pty Ltd).
Telefono : 61 8 379-9217 (10am a 10pm de Adelaida, Australia del tiempo).
Nota : 'Rocksoft' es una marca registrada de Rocksoft Pty Ltd, Australia.
Estado : Copyright (C) Ross Williams, 1993. Sin embargo, el permiso es
concedida a hacer y distribuir copias literales de este
documento siempre que este bloque de informacion y derechos de autor
aviso esta incluido. Tambien, el codigo de C modulos incluidos
en este documento son totalmente dominio publico.
Gracias : Gracias a Jean-loup Gailly ([email protected]) y Mark Adler
([email protected]) que tanto la prueba de leer este documento
y recogio muchas de las liendres, asi como algunos de los grandes de grasa errores.

Tabla de Contenido
& & & & & & & & -
Resumen
1. Introduccion: la Deteccion de Errores
2. La Necesidad De Complejidad
3. La Idea Basica Detras de la CRC Algoritmos
4. Polynomical Aritmetica
5. Aritmetica binaria con Lleva
6. Totalmente Trabajado Ejemplo
7. La eleccion de Un Poli
8. Un Sencillo CRC Aplicacion
9. Una Tabla Impulsada por la Aplicacion
10. Un poco Alterados basada en tablas de Aplicacion
11. 'Refleja' basada en tablas Implementaciones
12. 'Invertido' Polys
13. Los Valores inicial y Final
14. La definicion de Algoritmos Absolutamente
15. Parametros del Modelo Para el CRC Algoritmos
16. Un Catalogo de Conjuntos de Parametros para los Estandares de
17. Una Implementacion del Algoritmo del Modelo
18. Rollo de Su Propia basada en tablas de Aplicacion
19. Generacion de Una Tabla de Busqueda
20. Resumen
21. Correcciones
A. Glosario
B. Referencias
C. Referencias que he Detectado, Pero que todavia & #39 t sin Embargo, Videntes

Resumen
& & & &
Este documento se explica el Crc (Codigos de Redundancia Ciclica) y su
basada en tablas implementaciones en total, detalles precisos. Gran parte de la
la literatura en el Ccr, y en particular sobre la mesa-impulsado
implementaciones, es un poco oscuro (o al menos asi parece a mi).
Este documento es un intento de proporcionar una clara y simple sin sentido
explicacion de CRCs y absolutamente de concretar todos los detalles de la
el funcionamiento de su alta velocidad de implementaciones. Ademas de esto,
este documento presenta un modelo con parametros CRC algoritmo llamado el
'Rocksoft^tm Modelo CRC Algoritmo'. El modelo de algoritmo puede ser
parametros a comportarse como la mayoria de la CRC implementaciones en todo,
y por lo tanto actua como una buena referencia para la descripcion de algoritmos particulares.
Una baja velocidad de la implementacion del modelo CRC algoritmo se proporciona en
el lenguaje de programacion C. Por ultimo hay una seccion que da de dos formas
de alta velocidad, mesa impulsada implementaciones, y proporcionar un programa
que genera CRC tablas de busqueda.

1. Introduccion: la Deteccion de Errores
& & & & & & & & & & & & & & & &
El objetivo de un error de deteccion de la tecnica es permitir que el receptor de un
mensaje transmitido a traves de un ruidoso (error introducir) canal
determinar si el mensaje ha sido dañado. Para ello, la
transmisor de construcciones de un valor (llamado una suma de comprobacion) que es una funcion
del mensaje, y lo anexa al mensaje. El receptor puede
utilizar la misma funcion para calcular la suma de comprobacion de la
mensaje y compararla con la anexa de la suma de comprobacion para ver si la
mensaje fue recibido correctamente. Por ejemplo, si elegimos un checksum
funcion que fue simplemente la suma de los bytes del mensaje mod 256
(es decir, el modulo de 256), entonces podria ir algo como lo siguiente. Todos los numeros
estan en decimal.

Mensaje : 6 23 4
Mensaje con la suma de comprobacion : 6 23 4 33
Mensaje despues de la transmision : 6 27 4 33

En el ejemplo anterior, el segundo byte del mensaje fue dañado de 23 a
27 por el canal de comunicaciones. Sin embargo, el receptor puede detectar
esto mediante la comparacion de la transmision de la suma de comprobacion (33) con el equipo
la suma de comprobacion de 37 (6 27 4). Si la suma de comprobacion en si esta dañado, un
correctamente el mensaje transmitido puede ser identificado incorrectamente como un
dañada. Sin embargo, este es un seguro del lado del fracaso. Un peligroso del lado
fallo se produce cuando el mensaje y/o de la suma de comprobacion es dañado en un
manera que resulta en una transmision que es internamente consistente.
por Desgracia, esta posibilidad es completamente inevitable y la mejor
que se puede hacer es minimizar su probabilidad mediante el aumento de la
cantidad de informacion en la suma de comprobacion (por ejemplo, ampliacion de la suma de comprobacion de
un byte para dos bytes).

Otro de deteccion de errores que existen tecnicas que implican la realizacion de complejas
las transformaciones en el mensaje para inyectarlo con redundantes
la informacion. Sin embargo, este documento se refiere solo a los CRC de los algoritmos,
que caen dentro de la clase de error de los algoritmos de deteccion que salen de la
los datos intactos y anexar una suma de comprobacion en la final. es decir:

2. La Necesidad De Complejidad
& & & & & & & & & & & & &
En el ejemplo de suma de comprobacion en la seccion anterior, vimos como un
mensaje dañado se detecto mediante un algoritmo de suma de comprobacion que simplemente
suma los bytes del mensaje mod 256:

Mensaje : 6 23 4
Mensaje con la suma de comprobacion : 6 23 4 33
Mensaje despues de la transmision : 6 27 4 33

Un problema con este algoritmo es que es demasiado simple. Si un numero de
al azar corrupciones ocurrir, hay un 1 en 256 posibilidades de que
no ser detectados. Por ejemplo:

Mensaje : 6 23 4
Mensaje con la suma de comprobacion : 6 23 4 33
Mensaje despues de la transmision : 8 20 5 33

Para fortalecer la suma de comprobacion, se podria cambiar a partir de 8 bits registro
16-bit de registro (es decir, la suma de los bytes mod 65536 lugar de mod 256) por lo que
como aparentemente a reducir la probabilidad de fallo de 1/256 a
1/65536. Mientras que, basicamente, es una buena idea, no en este caso porque
la formula utilizada no es lo suficientemente 'al azar' con una simple suma
formula, cada entrante de bytes afecta aproximadamente solo un byte de la
suma de registro no importa cuan amplia es. Por ejemplo, en el segundo
ejemplo de arriba, el resumen del registro podria ser un Megabyte de ancho, y la
error, todavia no se detectan. Este problema solo puede ser resuelto por
sustitucion de la simple suma de formula con una mas sofisticada formula
que hace que cada entrante de bytes a tener un efecto en toda la
suma de verificacion registro.

por Lo tanto, vemos que, al menos, dos aspectos son necesarios para formar un fuerte
la suma de comprobacion de la funcion:

ANCHO: UN registro de ancho lo suficientemente amplia como para proporcionar un bajo a-priori
probabilidad de fallo (por ejemplo, de 32 bits da un 1/2^32 oportunidad
de la falla).

el CAOS: UNA formula que da a cada uno de los bytes de entrada el potencial de cambiar
cualquier numero de bits en el registro.

Nota: El termino 'suma de verificacion' se presume fue utilizada para describir los primeros
suma de las formulas, pero ahora ha tomado un significado mas general
que abarca mas sofisticados algoritmos tales como el CRC. La
CRC algoritmos para ser descrito satisfacer la segunda condicion muy bien,
y puede ser configurado para funcionar con una variedad de suma de comprobacion de ancho.

3. La Idea Basica Detras de la CRC Algoritmos
& & & & & & & & & & & & & & & & & & & -
¿Donde podemos ir en la busqueda de una funcion mas compleja de lo que
suma? Todo tipo de regimenes de primavera a la mente. Hemos sido capaces de construir
tablas utilizando los digitos de pi, o hash de cada entrante de bytes con todos los
bytes en el registro. Incluso podriamos mantener un gran libro de telefono
en linea, y el uso de cada uno de los entrantes bytes combinado con el registro bytes
indice de un numero de telefono nuevo, que seria el siguiente valor del registro.
Las posibilidades son ilimitadas.

sin Embargo, no necesitamos ir tan lejos, el proximo aritmetica paso
basta. Mientras que la adicion esta claro que no es lo suficientemente fuerte como para formar un
en efectivo de la suma de comprobacion, resulta que la division es, mientras que la
divisor es casi tan amplia como la suma de comprobacion de registro.

La idea basica de la convencion de los algoritmos es simplemente para tratar el mensaje como un
enorme numero binario, se divide por otra fija numero binario,
y para hacer el resto de esta division de la suma de comprobacion. En
la recepcion del mensaje, el receptor puede realizar la misma division y
comparar el resto con el 'checksum' (transmitido resto).

Ejemplo: Supongamos que el mensaje consistia en que los dos bytes (6,23) como
en el ejemplo anterior. Estos pueden ser considerados como hexadecimal
numero de 0617 que puede ser considerado para ser el numero binario
0000-0110-0001-0111. Supongamos que utilizamos una suma de comprobacion de registro de un byte
amplia y el uso constante de un divisor de 1001, entonces la suma de comprobacion es el
resto despues de 0000-0110-0001-0111 se divide por 1001. Mientras que en este
caso, este calculo, obviamente, se puede realizar utilizando comun
jardin de la variedad de registros de 32 bits, en el caso general, esto es complicado. Por lo que
en cambio, nosotros & #39 ll hacer la division mediante una buena & -#39 ol largo de la division que usted
han aprendido en la escuela (¿recuerdas?). Excepto que esta vez, & #39 s en binario:

...0000010101101 = 00AD = 173 = COCIENTE
& _ & & & & &
9= 1001 ) 0000011000010111 = 0617 = 1559 = DIVIDENDO
DIVISOR 0000.,,....,.,,,
& & .,,....,.,,,
0000,,....,.,,,
0000,,....,.,,,
& & ,,....,.,,,
0001,....,.,,,
0000,....,.,,,
& & ,....,.,,,
0011....,.,,,
0000....,.,,,
& & ....,.,,,
0110...,.,,,
0000...,.,,,
& & ...,.,,,
1100..,.,,,
1001..,.,,,
====..,.,,,
0110.,.,,,
0000.,.,,,
& & .,.,,,
1100,.,,,
1001,.,,,
====,.,,,
0111.,,,
0000.,,,
& & .,,,
1110,,,
1001,,,
====,,,
1011,,
1001,,
====,,
0101,
0000,
& &
1011
1001
====
0010 = 02 = 2 = RESTO

En decimal esto es '1559 dividido por 9 173 con un resto de 2'.

a Pesar de que el efecto de cada uno de los bits del mensaje de entrada en el cociente
no es del todo significativa, los 4 bits restantes se inicio sobre el
bastante durante el calculo, y si mas bytes que se han añadido a
el mensaje (dividendo) & #39 s valor podria cambiar radicalmente nuevo muy
rapidamente. Esta es la razon por la division de obras, donde ademas de no & #39 t.

En caso de que usted & #39 re preguntando, utilizando 4 bits de la suma de comprobacion de la transmision
mensaje seria como este (en hexadecimal): 06172 (donde el 0617
es el mensaje y la 2 es la suma de comprobacion). El receptor dividiria
0617 por 9 y ver si el resto fue de 2.

4. Polynomical Aritmetica
& & & & & & & & & & & & -
Mientras que la division esquema descrito en la seccion anterior es muy
muy similar a la de la suma de comprobacion de los sistemas denominados de CRC de los planes, el CRC
esquemas de hecho son un poco extrañas, y tenemos la necesidad de profundizar en algunos
numero extraño de sistemas para entender de ellos.

La palabra que escuchamos todo el tiempo cuando se trata con el CRC algoritmos
es la palabra 'polinomio'. Un determinado algoritmo CRC se dice ser
el uso de un determinado polinomio, y el CRC de los algoritmos en general se dice
para ser operativo utilizando el polinomio de la aritmetica. ¿Que significa esto?

en Lugar de el divisor, el dividendo (mensaje), cociente y resto
(como se describe en la seccion anterior) que es vista como positiva
los numeros enteros, que son vistos como los polinomios con coeficientes binarios.
Esto se hace mediante el tratamiento de cada numero como un poco de cadena cuyos bits
los coeficientes de un polinomio. Por ejemplo, el numero ordinario 23
(decimal) 17 (hex) y 10111 binario y por lo que corresponde a la
polinomio:

1*x^4 0*x^3 1*x^2 1*x^1 1*x^0

o, mas simplemente:

x^4 x^2 x^1 x^0

el Uso de esta tecnica, el mensaje, y el divisor puede ser representado
como polinomios y podemos hacer todos nuestros aritmetica al igual que antes, excepto
que ahora es & #39 s todo desordenado con Xs. Por ejemplo, supongamos que deseamos
para multiplicar 1101 por 1011. Podemos hacer esto simplemente multiplicando el
polinomios:

(x^3 x^2 x^0)(x^3 x^1 x^0)
= (x^6 x^4 x^3
x^5 x^3 x^2
x^3 x^1 x^0) = x^6 x^5 x^4 3*x^3 x^2 x^1 x^0

En este punto, para llegar a la respuesta correcta, tenemos que pretender que x es 2
y propagar binario lleva desde el 3*x^3 rendimiento

x^7 x^3 x^2 x^1 x^0

& #39 s como aritmetica ordinaria, salvo que la base es un resumen
y puesto en todos los calculos de forma explicita en lugar de ser
existe de forma implicita. Entonces, ¿que & #39 s el punto?

El punto es que SI decimos que NO tenemos & #39 T sabe lo que es x, PODEMOS & #39 T
realizar la lleva. Nosotros no & #39 t saber que 3*x^3 es el mismo que x^4 x^3
porque no & #39 t sabes que x es 2. En este verdadero polinomio aritmetico
la relacion entre todos los coeficientes es desconocido y por lo que el
los coeficientes de cada potencia de forma eficaz inflexible
los coeficientes de x^2 son efectivamente de un tipo diferente a
los coeficientes de x^3.

Con los coeficientes de cada potencia muy bien aislado, matematicos
se acerco con todo tipo de diferentes tipos de polinomio aritmetica
simplemente cambiando las reglas acerca de como los coeficientes de trabajo. De estos
esquemas, uno en particular es relevante aqui, y que es un polinomio
la aritmetica donde los coeficientes se calculan MOD 2 y no hay
llevar todos los coeficientes deben ser 0 o 1 y no lleva son
calcula. Esto se llama 'polinomio aritmetico mod 2'. Por lo tanto,
volviendo al ejemplo anterior:

(x^3 x^2 x^0)(x^3 x^1 x^0)
= (x^6 x^4 x^3
x^5 x^3 x^2
x^3 x^1 x^0)
y = x^6 x^5 x^4 3*x^3 x^2 x^1 x^0

Debajo de la otra aritmetica, la 3*x^3 termino se propagan con la
llevar el mecanismo mediante el conocimiento de que x=2. En 'polinomio
la aritmetica mod 2', no & #39 t sabe lo que es x, no hay la lleva, y
todos los coeficientes se han calculado los mod 2. Por lo tanto, el resultado
es:

y = x^6 x^5 x^4 x^3 x^2 x^1 x^0

Como Knuth [Knuth81] dice: (p.400):

'El lector debe notar la similitud entre el polinomio
la aritmetica y de varios aritmetica de precision (Seccion 4.3.1), donde
la base b se sustituye por x. La principal diferencia es que el
coeficiente de u_k de x^k en el polinomio aritmetico tiene poco o nada
en relacion a sus vecinos los coeficientes de x^{k-1} [y x^{k 1}], por lo que
la idea de la 'realizacion' de un lugar a otro esta ausente. De hecho
polinomio aritmetico modulo b es esencialmente identica a multiples
la precision de la aritmetica con base b, a excepcion de que todo lleva son
suprimido.'

por Lo tanto polynomical aritmetica mod 2 es solo la aritmetica binaria mod 2 con
no lleva. Mientras que los polinomios de proporcionar matematicas utiles maquinaria en
mas enfoques analiticos para el CRC y la correccion de error de los algoritmos, para
los efectos de la exposicion, no proporcionan una idea adicional y algunos
gravamen y han sido descartados en el resto de este documento
en favor de la manipulacion directa de la aritmetica sistema con el que
son isomorfos: aritmetica binaria sin llevar.

5. Aritmetica binaria con Lleva
& & & & & & & & & & & & & & & & & &
Haber prescindido de polinomios, podemos centrarnos en el real aritmetica
problema, que es que toda la aritmetica realiza durante el CRC
los calculos se realizan en binario con el que no lleva. A menudo esto es
se llama polinomio aritmetico, pero como he declarado el resto de este
documento de un polinomio de la zona libre de nosotros & #39 ll tiene que llamar a CRC aritmetica
en su lugar. Como esta aritmetica es una parte clave de la convencion, calculos, tenemos & #39 d
mejor acostumbrarse a el. Aqui vamos:

la Adicion de dos numeros en el CRC de la aritmetica es la misma que la adicion de numeros en
normal aritmetica binaria excepto que no se llevan. Esto significa que
cada par de bits correspondientes de determinar el correspondiente bit de salida
sin hacer referencia alguna a otras posiciones de bits. Por ejemplo:

10011011
11001010
& & & &
01010001
& & & &

solo Hay cuatro casos para cada posicion de bit:

0 0=0
0 1=1
1 0=1
1 1=0 (sin llevar)

la Resta es identico:

10011011
-11001010
& & & &
01010001
& & & &

con

0-0=0
0-1=1 (wraparound)
1-0=1
1-1=0

De hecho, tanto la adicion y la sustraccion en el CRC de la aritmetica es equivalente a
para la operacion XOR, y la operacion XOR es su propia inversa. Este
reduce eficazmente las operaciones de primer nivel de energia
(suma, resta) a una sola operacion, que es su propia inversa.
Esta es una forma muy conveniente de la propiedad de la media aritmetica.

Por el colapso de la suma y la resta, la media aritmetica se descarta cualquier
la nocion de magnitud por encima de la potencia de su mas alta y un bit. Mientras que
parece claro que 1010 es mayor que 10, no es el caso
1010 puede considerarse como el mayor de 1001. Para ver esto, observe
que se puede obtener de 1010 a 1001 por tanto la suma y resta de la
cantidad:

1010 = 1010 0011
1010 = 1010 - 0011

Esto hace que el sinsentido de cualquier nocion de orden.

despues de Haber definido ademas, podemos pasar a la multiplicacion y la division.
la Multiplicacion es absolutamente sencillo, siendo la suma de los
primer numero, cambio de conformidad con el segundo numero.

1101
x 1011
& &
1101
1101.
0000..
1101...
& & & -
1111111 Nota: La suma de los usos de la CRC, ademas
& & & -

Division es un poco mas complicada ya que tenemos que saber cuando 'un numero
a otro numero'. Para ello, invocamos a la debil definicion de
magnitud definida anteriormente: que X es mayor que o igual a Y fib
la posicion de la mas alta 1 bit de X es igual o mayor que el
la posicion de la mas alta 1 bit de Y. Aqui & #39 s trabajado en la division de
(muescas de [Tanenbaum81]).

1100001010
& & & & &
10011 ) 11010110110000
10011,,.,,....
& & -,,.,,....
10011,.,,....
10011,.,,....
& & -,.,,....
00001.,,....
00000.,,....
& & -.,,....
00010,,....
00000,,....
& & -,,....
00101,....
00000,....
& & -,....
01011....
00000....
& & -....
10110...
10011...
& & -...
01010..
00000..
& & -..
10100.
10011.
& & -.
01110
00000
& & -
1110 = Resto

& #39 s realmente es. Antes de continuar, sin embargo, & #39 s digno de nuestra
mientras jugaba con esta aritmetica un poco para acostumbrarse a ella.

& #39 ve ya jugo con la suma y la resta, dandose cuenta de que
son la misma cosa. Aqui, sin embargo, debemos tener en cuenta que en este
la aritmetica 0=A y-0=A. Esta obvia la propiedad es muy util
mas tarde.

En el trato con el CRC de la multiplicacion y la division, & #39 s vale la pena conseguir un
siento por los conceptos de MULTIPLO y DIVISIBLE.

Si un numero a es multiplo de B, entonces lo que esto significa en el CRC
la aritmetica es que es posible construir Una desde cero mediante el cifrado xor
en los distintos turnos de B. Por ejemplo, si Una se 0111010110 y B fue de 11,
podriamos construir Un de B como sigue:

0111010110
= .......11.
....11....
...11.....
.11.......

sin Embargo, si Una es 0111010111, no es posible construir fuera de
varios turnos de B (que se puede ver por que? - ver mas adelante) por lo que se dice
no es divisible por B en el CRC de la aritmetica.

Asi vemos que el CRC de la aritmetica es principalmente acerca de cifrado xor particular
valores en diversas cambio de compensaciones.

6. Totalmente Trabajado Ejemplo
& & & & & & & & & & & & -
despues de Haber definido el CRC de la aritmetica, ahora podemos marco de un calculo del CRC como
simplemente una division, debido a que & #39 s todo lo que es! Esta seccion llena en el
los detalles y da un ejemplo.

Para realizar un calculo del CRC, tenemos que elegir un divisor. En matematicas
marketing hablan el divisor es llamado el 'polinomio generador' o
simplemente la 'polinomio', y es un parametro clave de cualquier algoritmo CRC.
probablemente seria mas amigable para llamar el divisor algo mas,
pero el poli de hablar es tan profundamente arraigada en el campo que seria
ahora ser confuso para evitarlo. Como solucion de compromiso, se hara referencia a la
polinomio CRC como el 'poli'. Solo pensar de este numero como una especie de
parrot. 'Hola poli!'

Usted puede elegir cualquier poli y venir para arriba con un algoritmo CRC. Sin embargo,
algunos de los poligonos son mejores que otros, y por lo tanto es conveniente seguir con el
trato de una prueba. Una seccion posterior se refiere a este tema.

El ancho (posicion de la mas alta 1 bit) de la poli es muy
importante como la que domina la totalidad de calculo. Normalmente, los anchos de
16 o 32 son elegidos a fin de simplificar la aplicacion de la moderna
las computadoras. El ancho de un poli es el numero de bits de la posicion de la
de bits mas alta. Por ejemplo, el ancho de 10011 es de 4, no 5. Para la
efectos del ejemplo, se eligio un poli de 10011 (de ancho W de 4).

despues de Haber elegido un poli, se puede proceder con el calculo. Esto es
simplemente una division (en el CRC de la aritmetica) de los mensaje por parte de la poli. La
unico truco es que W bits cero se anexa al mensaje antes de que el
el CRC se calcula. Asi tenemos que:

mensaje Original de : 1101011011
Poli : 10011
Mensaje despues de anexar W ceros : 11010110110000

Ahora nos basta con dividir la aumentada mensaje por el poli utilizando CRC
la aritmetica. Esta es la misma division que antes de:

1100001010 = Cociente (a nadie le importa el cociente)
& & & & &
10011 ) 11010110110000 = Aumentada mensaje (1101011011 0000)
=Poly 10011,,.,,....
& & -,,.,,....
10011,.,,....
10011,.,,....
& & -,.,,....
00001.,,....
00000.,,....
& & -.,,....
00010,,....
00000,,....
& & -,,....
00101,....
00000,....
& & -,....
01011....
00000....
& & -....
10110...
10011...
& & -...
01010..
00000..
& & -..
10100.
10011.
& & -.
01110
00000
& & -
1110 = Resto = LA suma de comprobacion!!!!

La division de los rendimientos de un cociente, que nos tiramos, y un resto,
que se calcula como la suma de comprobacion. Esto termina el calculo.

Normalmente, la suma de comprobacion, a continuacion, adjunta al mensaje y el resultado
transmision sexual. En este caso, la transmision seria: 11010110111110.

En el otro extremo, el receptor puede hacer una de dos cosas:

un. Separar el mensaje y la suma de comprobacion. Calcular la suma de comprobacion para
el mensaje (despues de anexar W ceros) y comparar los dos
las sumas de comprobacion.

b. Suma de comprobacion de la totalidad del lote (sin anexar ceros) y ver si
sale como cero!!!

Estas dos opciones son equivalentes. Sin embargo, en la siguiente seccion, se
sera suponiendo que la opcion b porque es marginalmente matematicamente
limpiador.

Un resumen de la operacion de la clase de CRC algoritmos:

1. Elija un ancho W, y un poli G (de ancho W).
2. Anexar W bits cero para el mensaje. Llamar a este M & #39 .
3. Dividir M & #39 por G uso de CRC de la aritmetica. El resto es la suma de comprobacion.

& #39 s todo lo que hay en el.

7. La eleccion de Un Poli
& & & & & & & & &
la Eleccion de un poli es algo de un arte negro y el lector es referido
a [Tanenbaum81] (p.130-132), que tiene una muy clara la discusion de este
el tema. Esta seccion simplemente tiene el objetivo de poner el miedo de la muerte a nadie
que tanto como los juguetes con la idea de hacer sus propias poli. Si usted
no & #39 t la atencion acerca de por que uno de poli podria ser mejor que el otro y solo
¿quieres conocer de alta velocidad implementaciones, elija uno de los
aritmeticamente sonido de poligonos que se enumeran al final de esta seccion y saltar
a la siguiente seccion.

en Primer lugar tenga en cuenta que el mensaje transmitido T es un multiplo de la poli.
Para ver esto, observe que 1) el ultimo de W bits de T es el resto despues de
la division de la aumentada (por ceros recordar) un mensaje por el poli, y 2)
ademas es el mismo que resta por lo que añadir el resto empuja la
valor hasta el siguiente multiplo. Ahora tenga en cuenta que si la transmision
mensaje esta dañado en la transmision de lo que vamos a recibir T E, donde E
es un vector de error (y es CRC adicion (es decir, XOR)). Tras la recepcion de
este mensaje, el receptor divide a T E por G. Como T mod G es 0, (T E)
mod G = E mod G. por Lo tanto, la capacidad de la poli nos decidimos coger
clases particulares de errores sera determinado por el conjunto de los multiplos
de G, para cualquier tipo de corrupcion E que es un multiplo de G para no ser detectadas.
Nuestra tarea, entonces, es encontrar clases de G cuya multiplos mira como poco
como el tipo de ruido de linea (que sera la creacion de la corrupcion) como
es posible. Asi que vamos a & #39 s examinar los tipos de ruido en la linea que podemos esperar.

SOLO los ERRORES de BIT: UN bit de error significa E=1000...0000. Podemos
asegurese de que esta clase de error siempre es detectada por asegurarse de que
G tiene al menos dos bits a 1. Cualquier multiplo de G sera
construido utilizando cambiando y añadiendo y es imposible
la construccion de un valor con un solo bit por el cambio de una adicion de un unico
valor con mas de un conjunto de bits, como los dos bits siempre
persisten.

DOS ERRORES de BITS: detectar todos los errores de forma 100...000100...000
(es decir, Correo contiene dos bits 1) elegir un G que no tiene multiplos
que son 11, 101, 1001, 10001, 100001, etc. No esta claro para mi como
uno la pasa haciendo esto (yo no & #39 t tiene la pura matematicas de fondo),
pero Tanenbaum nos asegura que tal G no existen, y la cites G con 1 bits
(15,14,1), se convirtio en un ejemplo de G que gano & #39 t dividir nada
a menos de 1...1 donde ... es 32767 ceros.

los ERRORES CON UN NUMERO IMPAR DE BITS: podemos coger todas las corrupciones donde
E tiene un numero impar de bits mediante la eleccion de un G que tiene un numero par de
bits. Para ver esto, observe que 1) CRC multiplicacion es simplemente el cifrado xor
el valor de la constante en un registro en varios desplazamientos, 2) el cifrado xor es simplemente
un bit-flip operacion, y 3) si usted XOR un valor con un numero par de
bits en un registro, la rareza de que el numero de bits 1 en la
registro permanece invariable. Ejemplo: a Partir de E=111, intento
voltear los tres bits a cero por la aplicacion repetida de cifrado xor en
11 en uno de los dos desplazamientos (es decir, 'E=E XOR 011' y 'E=E XOR 110')
Esto es casi isomorfo a los 'vasos de vidrio' partido de puzzle donde
reto a alguien a voltear tres vasos por los repetidos
aplicacion de la operacion de un tiron cualquiera de los dos. La mayoria de los populares
CRC polys contienen un numero par de bits 1. (Nota: Tanenbaum estados
mas especificamente que todos los errores con un numero impar de bits puede ser
atrapado haciendo G un multiplo de 11).

RAFAGA de ERRORES: UNA rafaga de error se ve como E=000...000111...11110000...00.
Que es, E se compone de todos los ceros excepto para una carrera de 1s en algun lugar
en el interior. Esto puede ser reformulado E=(10000...00)(1111111...111) donde
hay z ceros en la parte IZQUIERDA y n en la parte DERECHA. A
captura de los errores de este tipo, se establece el bit mas bajo de G a 1.
de este modo se garantiza que la IZQUIERDA no puede ser un factor de G. Entonces, tan largo como
G es mas amplia que la de la DERECHA, el error sera detectado. Ver Tanenbaum para un
explicacion mas clara de este I & #39 m un poco difusa. Nota:
Tanenbaum afirma que la probabilidad de que una rafaga de mayor longitud
que W llegar a traves de es (0.5)^W.

con la Que concluye la seccion sobre el fino arte de la seleccion de poligonos.

Algunos de los populares de poligonos son:
16 bits: (16,12,5,0) [X25 estandar]
(16,15,2,0) ['CRC-16']
32 bits: (32,26,23,22,16,12,11,10,8,7,5,4,2,1,0) [Ethernet]

8. Un Sencillo CRC Aplicacion
& & & & & & & & & & & & & & & & & & & -
& #39 s la final de la teoria de ahora le damos la vuelta a las implementaciones. Para empezar
con examinamos un absolutamente recta hacia abajo-el-medio aburrido
sencillo de baja velocidad de la aplicacion que no & #39 t utilizar cualquier velocidad
trucos. Nosotros & #39 ll luego transformar ese programa progessively hasta que
terminar con la compacta basada en tablas