¿Cuál es una alternativa más rápida a un CRC?

27

Estoy haciendo una transmisión de datos desde un dsPIC a una PC y estoy haciendo un CRC de 8 bits a cada bloque de 512 bytes para asegurarme de que no haya errores. Con mi código CRC habilitado obtengo aproximadamente 33 KB / s, sin él obtengo 67 KB / s.

¿Cuáles son algunos algoritmos alternativos de detección de errores para verificar que serían más rápidos?

FigBug
fuente
55
¿Cómo se implementa el CRC? Bitwise? Luego cambie a un método basado en tablas. Bytewise? Considere el intercambio de espacio, complejidad y tiempo involucrado en aumentar el tamaño de la tabla a, digamos, 16 bits (que operaría en dos bytes a la vez, pero tomaría 64 KB de almacenamiento de la tabla).
Aidan Cully
Solo tengo 16 KB en RAM y 128 KB de ROM, por lo que una tabla de 64 KB no es una opción.
FigBug
1
Entonces, ¿estás usando una tabla de 256 bytes? o CRC bit a bit? Si está haciendo bit a bit, bytewise (con una tabla de 256 bytes) sería 8 veces más rápido.
Aidan Cully
Bitwise actualmente, probaré una tabla de 256
FigBug
1
¿67 kb / sa 33 kb / s? No estoy seguro de lo que implica su otro procesamiento, pero eso parece un poco de sobrecarga, incluso para un PIC. ¿Quizás hay otros problemas que impiden su desempeño?
Rei Miyasaka

Respuestas:

41

Si bien puede haber opciones más rápidas que CRC, si las usa, es probable que termine sacrificando cierto grado de capacidad de detección de errores. Dependiendo de cuáles sean sus requisitos de detección de errores, una alternativa puede ser utilizar el código CRC optimizado para su aplicación.

Para una comparación de CRC con otras opciones, vea la excelente respuesta de Martin Thompson .

Una opción para ayudar con esto es pycrc, que es una herramienta (escrita en python 1 ) que puede generar código fuente C para docenas de combinaciones de algoritmo y modelo crc . Esto le permite optimizar la velocidad y el tamaño para su propia aplicación seleccionando y comparando diferentes combinaciones. 1: Requiere Python 2.6 o posterior.

Es compatible con el crc-8 modelo , pero también es compatible crc-5, crc-16y crc-32entre otros. En cuanto a los algoritmos , es compatible bit-by-bit, bit-by-bit-fasty table-driven.

Por ejemplo (descargando el archivo):

$ wget --quiet http://sourceforge.net/projects/pycrc/files/pycrc/pycrc-0.8/pycrc-0.8.tar.gz/download
$ tar -xf pycrc-0.8.tar.gz
$ cd pycrc-0.8
$ ./pycrc.py --model=crc-8 --algorithm=bit-by-bit      --generate c -o crc8-byb.c
$ ./pycrc.py --model=crc-8 --algorithm=bit-by-bit-fast --generate c -o crc8-bybf.c
$ ./pycrc.py --model=crc-8 --algorithm=table-driven    --generate c -o crc8-table.c
$ ./pycrc.py --model=crc-16 --algorithm=table-driven   --generate c -o crc16-table.c
$ wc *.c
   72   256  1790 crc8-byb.c
   54   190  1392 crc8-bybf.c
   66   433  2966 crc8-table.c
  101   515  4094 crc16-table.c
  293  1394 10242 total

Incluso puede hacer cosas extravagantes, como especificar el uso de búsquedas de doble mordisco (con una tabla de búsqueda de 16 bytes) en lugar de una búsqueda de un solo byte, con una tabla de búsqueda de 256 bytes.

Por ejemplo (clonando el repositorio git):

$ git clone http://github.com/tpircher/pycrc.git
$ cd pycrc
$ git branch
* master
$ git describe
v0.8-3-g7a041cd
$ ./pycrc.py --model=crc-8 --algorithm=table-driven --table-idx-width=4 --generate c -o crc8-table4.c
$ wc crc8-table4.c
  53  211 1562 crc8-table4.c

Dadas sus limitaciones de memoria y velocidad, esta opción puede ser el mejor compromiso entre la velocidad y el tamaño del código. Sin embargo, la única forma de estar seguro sería compararlo.


El repositorio pycrc git está en github , al igual que su rastreador de problemas , pero también se puede descargar desde sourceforge .

Mark Booth
fuente
No creo que la mayoría de las personas que escriben cosas para el PIC estén usando C, pero esto podría funcionar si es así.
Billy ONeal
44
@ Billy - ¿En serio? Creo que no me he encontrado a nadie para el desarrollo de PIC en el mercado que no estaba usando C. Yo desde luego no tienen la paciencia para ensamblador estos días y bien estructurado C puede terminar bastante compacto.
Mark Booth
Estoy usando un dsPIC y estoy usando C.
FigBug
@FigBug - Gracias, me alegra que te guste mi respuesta. Si ejecuta algunas pruebas de referencia, no dude en editar mi respuesta con sus resultados. Me encantaría saber cuánta diferencia hace cada uno de los algoritmos en términos de rendimiento de la aplicación y huella de memoria.
Mark Booth
1
Otro voto para pyCrc aquí. usarlo en varios proyectos con diferentes restricciones y es simplemente genial.
Vicky
11

La paridad simple de un bit (básicamente XORing de los datos una y otra vez) es lo más rápido posible. Sin embargo, se pierde gran parte de la comprobación de errores de un CRC.

En pseudocódigo:

char checksum = 0;
for each (char c in buffer)
{
    checksum ^= c;
    SendToPC(c);
}
SendToPc(checksum);
Billy ONeal
fuente
1
Investigué esto hace un tiempo. yo creo que en lugar de sumar xor realmente funciona un poco mejor. (normalmente, suma todo, y luego transmitir complemento de la suma como la suma de comprobación del 2 En el receptor, la suma de todo, incluyendo que la suma de control recibida El resultado es 0 si todo es bueno, y no 0 en caso contrario...)
quickly_now
1
@quickly: No creo que haya una diferencia significativa entre esos dos; ninguno de los métodos proporciona una garantía tan buena de que las cosas no se hayan corrompido. Si agregar es más rápido en la arquitectura de destino, utilícelo en su lugar.
Billy ONeal
77
Recordé: la principal diferencia entre ADD y XOR es que hay menos detectabilidad de errores de múltiples bits. En el caso de una secuencia de bytes, los errores en la misma posición de bit se cancelan usando XOR. Cuando se usa ADD, la propagación de bits a través de un byte de suma de verificación significa que este caso es más detectable. (Sin embargo, es probable que los errores de varios bits en diferentes bits distribuidos a través de la secuencia de bytes sean menos detectables, dependiendo de las circunstancias en ese momento). Cualquier arreglo de suma de verificación como este es TERRIBLE para errores de múltiples bits, por lo que es un argumento bastante menor.
rapid_now
XOR es mucho menos útil que CRC.
3
@ Thorbjørn: Creo que lo reconocí en mi respuesta. :)
Billy ONeal
10

Un documento realmente bueno que compara el rendimiento de varias sumas de verificación y CRC en un contexto integrado:

La efectividad de las sumas de verificación para redes integradas

Algunas citas de las conclusiones (basadas en sus estudios de probabilidades de error no detectadas):

Cuando los errores de ráfaga dominan

XOR, la suma de complemento de dos y las sumas de verificación CRC proporcionan un mejor rendimiento de detección de errores que las sumas de suma de complemento, Fletcher y Adler.

En otras aplicaciones

un polinomio CRC "bueno", siempre que sea posible, debe usarse con fines de detección de errores

Si el costo de cálculo es muy limitado

(como en su caso), use (en orden de efectividad):

Otras citas

La suma de verificación de Fletcher tiene un costo computacional más bajo que la suma de verificación de Adler y, contrariamente a la creencia popular, también es más efectiva en la mayoría de las situaciones.

y

En general, no hay ninguna razón para continuar la práctica común de usar una suma de verificación XOR en nuevos diseños, porque tiene el mismo costo computacional del software que una suma de verificación basada en la suma, pero solo es aproximadamente la mitad de efectiva para detectar errores.

Martin Thompson
fuente
1
Como beneficio adicional, una suma de verificación Fletcher es muy fácil de implementar.
RubberDuck
6

La suma de comprobación de Adler debería ser suficiente para comprobar las distorsiones de transmisión. Es utilizado por la biblioteca de compresión Zlib, y fue adoptado por el Java 3D Mobile Graphics Standard para proporcionar una verificación de integridad de datos rápida pero efectiva.

Desde la página de wikipedia :

Se obtiene una suma de comprobación Adler-32 calculando dos sumas de comprobación de 16 bits A y B y concatenando sus bits en un entero de 32 bits. A es la suma de todos los bytes en la cadena más uno, y B es la suma de los valores individuales de A de cada paso.

Al comienzo de una ejecución de Adler-32, A se inicializa a 1, B a 0. Las sumas se realizan en el módulo 65521 (el número primo más grande menor que 2 ^ 16 o 65536). Los bytes se almacenan en orden de red (big endian), B ocupa los dos bytes más significativos.

La función puede expresarse como

 A = 1 + D1 + D2 + ... + Dn (mod 65521)
 B = (1 + D1) + (1 + D1 + D2) + ... + (1 + D1 + D2 + ... + Dn) (mod 65521)
   = n×D1 + (n-1)×D2 + (n-2)×D3 + ... + Dn + n (mod 65521)

 Adler-32(D) = B × 65536 + A

donde D es la cadena de bytes para la cual se debe calcular la suma de verificación, y n es la longitud de D.

Gnawme
fuente
Tenga en cuenta que Adler32 es casi inútil para series cortas de datos. Hasta aproximadamente 180 bytes, produce numerosas colisiones.
greyfade
+1: un punto medio razonable entre un CRC y una paridad de bits simple.
Billy ONeal
@greyfade: FigBug mencionó el uso de bloques de 512 bytes, por lo que esto no debería ser un problema para el OP. Sin embargo, es bueno tenerlo en cuenta para las personas con otros requisitos.
Mark Booth
5

No conozco nada que sea tan efectivo en la detección de errores como un CRC y más rápido; si lo hubiera, la gente lo estaría usando en su lugar.

Podría intentar una suma de comprobación simple, pero es mucho menos probable que detecte errores.

Bob Murphy
fuente
2
Estoy dispuesto a renunciar a la efectividad de la velocidad.
FigBug
3

Bueno, la lógica de la suma de comprobación en sí es buena y las personas pueden ayudar con algoritmos más rápidos.

Si desea mejorar la velocidad de su componente, es posible que deba considerar cambiar su técnica general para separar el componente de transferencia del componente de validación.

Si los tiene como dos elementos independientes (en subprocesos diferentes), puede obtener su velocidad de transferencia completa y solo reenviar paquetes fallidos.

El algoritmo se vería así:

  • El servidor se divide en tamaños de paquetes conocidos (por ejemplo, fragmentos de 1K). Los pone en una cola de "ser enviado".
  • Cada paquete se envía con una ID de 16 o 32 bits Y su suma de verificación.
  • El cliente recibe cada paquete y lo pone en una cola para ser procesado.
  • En un subproceso separado que el cliente toma de un paquete a la vez, realiza la validación.
    • En caso de éxito, lo agrega a la colección final de paquetes (en orden de identificación) siendo
    • En caso de error, informa la ID fallida al servidor, que pone en cola ese paquete para reenviarlo.
  • Una vez que haya recibido y validado los paquetes y tenga los ID en la secuencia correcta (comenzando en 1), puede comenzar a escribirlos en el disco (o hacer lo que sea necesario).

Esto le permitirá transmitir a la velocidad más alta posible y si juega con el tamaño de su paquete, puede calcular la tasa de falla óptima VS la tasa de validación / reenvío.

Robin Vessey
fuente
2

Las sumas de control son tradicionales

(reducir # '+ transmisión)

XOR como se indicó anteriormente también funcionaría

(reducir # 'flujo XOR)

Un esquema un poco más elaborado (más lento) es la verificación de paridad estándar para conexiones en serie.

En este nivel, estás cambiando la corrección por velocidad. Estos ocasionalmente fallarán.

En el siguiente nivel más sofisticado, puede usar algunas cosas de tipo crc / hash.

Otro diseño sería aumentar el tamaño del bloque utilizado para la secuencia.

Debe tener una estimación de la tasa de error real para ajustar la selección de su algoritmo y los parámetros para el tamaño del bloque.

Paul Nathan
fuente