códigos de corrección de errores destinados a CPUs lentas que transmiten a CPUs rápidas

Question

Estoy buscando un código de corrección de errores directo que sea relativamente fácil/rápido de codificar en un microcontrolador; La decodificación se realizará en una PC, por lo que puede ser más complicado.

No sé mucho sobre los códigos de corrección de errores y, a excepción de los simples códigos de Hamming, todos parecen ser más complicados de lo que puedo manejar.

¿Alguna recomendación?

edición: Voy a cortar las cosas a corto y aceptar la respuesta de Carl ... supongo que había dos cosas que no he mencionado:

(1) que hago no es estrictamente necesario la corrección de errores, es una ventaja para mí, y pensé que podría haber algún algoritmo de corrección de errores que fuera un beneficio razonable a un costo mínimo. Los códigos de Hamming son probablemente los adecuados y hasta parecen ser demasiado costosos para mi aplicación de codificación.

(2) La mayor ventaja que la corrección de errores en sí es la capacidad de resincronizar correctamente a los paquetes que siguen a un error. (Si me desincronizo durante mucho tiempo, eso es malo). Así que creo que es mejor si mantengo las cosas simples.

Answer 1

El problema con los códigos de corrección de errores es que le permiten recuperarse de un bit o quizás de 2 bits de errores, pero generalmente no detectan ni reparan el daño mayor.

Por lo tanto, mi recomendación sería dividir sus flujos de datos en bloques (1 KB, 10 KB, ... 1 MB como máximo) y calcular una suma de comprobación para cada bloque. Luego, cuando los datos lleguen a la otra CPU, puede determinar si es correcta y solicitar la retransmisión de ese bloque si no es así. Entonces, la computadora receptora reconocería y esperaría al siguiente bloque, o reconocería negativamente y esperaría un nuevo envío.

Sí, estamos implementando un subconjunto de TCP/IP aquí. Pero hay una razón por la cual este protocolo fue tan exitoso: ¡Funciona!

Para una suma de comprobación, recomendaría CRC-32. Requiere una tabla de (creo) 256 números de 32 bits y algunos cálculos bastante fáciles (indexación de matrices, OR y XOR, en su mayoría), por lo que es bastante fácil de computar para una CPU "tonta".

Answer 2

No he entendido bien la cantidad de sobrecarga que puede pagar. En su comentario, dice que un código de detección/corrección de errores de 16 bits es correcto, pero no especifica qué tan grande de un bloque está pensando en adjuntarlo. Para ser significativo, probablemente debería expresar la sobrecarga permisible como un porcentaje. 16 bits de corrección de errores para 64 bits de datos es muy diferente de 16 bits de corrección de errores de un kilobyte de datos.

Si puede pagar algo así como un 15-20% de gastos generales, puede usar un código convolucional con decodificador Viterbi. Esto es altamente asimétrico: el codificador convolucional es bastante simple (básicamente un registro de desplazamiento, con derivaciones de salida que conducen a XOR). Una muy grande podría usar un registro de 16 bits con una media docena de XOR's.

Afortunadamente usted tiene una computadora más resistente para manejar la decodificación, porque un decodificador de Viterbi puede ser una bestia temible. Especialmente cuando usa un codificador más grande para reducir la sobrecarga, el tamaño del decodificador explota. El tamaño del decodificador es exponencial con respecto al tamaño del grupo de códigos.

Se mencionaron los códigos turbo.Estos pueden hacer un mejor uso del ancho de banda disponible que los códigos convolucionales con decodificadores Viterbi, pero usan un codificador considerablemente más complejo: un mínimo de dos codificadores convolucionales de un tipo específico (codificadores convolucionales sistemáticos recursivos). Como tales, tampoco parecen ajustarse a sus especificaciones.

Answer 3

Sugiero utilizar una forma de paquete de corrección de errores de envío. Si tiene que enviar seis paquetes de igual longitud, envíe a cada uno de ellos con suficiente información para identificarlo como "paquete 1 de 6", "2 de 6", etc. junto con un paquete más cuyo primer byte de carga es el xor de el primer byte de carga útil de los paquetes 1-6, cuyo segundo byte de carga útil es el xor del segundo byte del paquete 1-6, etc. El código que recibe seis paquetes de los siete totales podrá reconstruir el que falta. Como una pequeña mejora, use un paquete de "paridad" para los paquetes "pares" y otro para los "impares". Si lo hace, el sistema podrá recuperarse de cualquier error de ráfaga que no sea más largo que un paquete.