Algoritmo de redundancia para leer el flujo de bits ruidoso

Question

Estoy leyendo un flujo de bits con pérdida y necesito una manera de recuperar la mayor cantidad posible de datos utilizables. Puede haber 1 en lugar de 0 y 0 en lugar de 1, pero la precisión probablemente sea superior al 80%.

Una bonificación sería si el algoritmo pudiera compensar la falta/demasiados bits también.

La fuente que estoy leyendo es analógica con ruido (micrófono a través de FFT), y el tiempo de lectura puede variar según la velocidad de la computadora.

Recuerdo haber leído acerca de los algoritmos utilizados en CD-ROM's haciendo esto en 3? capas, así que supongo que usar varias capas es una buena opción. Sin embargo, no recuerdo los detalles, así que si alguien puede compartir algunas ideas, ¡sería genial! :)

Editar: datos de la muestra Agregado

 
Best case data: 
in: 0000010101000010110100101101100111000000100100101101100111000000100100001100000010000101110101001101100111000101110000001001111011001100110000001001100111011110110101011100111011000100110000001000010111 
out: 0010101000010110100101101100111000000100100101101100111000000100100001100000010000101110101001101100111000101110000001001111011001100110000001001100111011110110101011100111011000100110000001000010111011 

Bade case (timing is off, samples are missing): 
out: 00101010000101101001011011001110000001001001011011001110000001001000011000000100001011101010011011001 
in: 00111101001011111110010010111111011110000010010000111000011101001101111110000110111011110111111111101 

Edit2: soy capaz el fin de controlar los datos que se envían. Actualmente, intenta implementar una comprobación XOR simple (aunque no será suficiente).

Answer 1

Necesita usar forward error correction. Una verificación de paridad XOR solo detectará cuando se produzca un error. Un algoritmo simple de corrección de errores sería enviar cada fragmento de datos varias veces (al menos 3) y tomar una decisión mayoritaria.

La elección del algoritmo depende de varios factores:

• utilización del canal (si usted tiene un montón de tiempo libre, que no necesita una codificación eficiente)
• Tipos de errores: son los puntos malos azar espaciados o hacer que por lo general se producen en una fila
• Procesamiento de tiempo: código de complejidad es limitada si la transmisión de datos tiene que ser rápido

Answer 2

Hay muchas posibilidades, ver: http://en.wikipedia.org/wiki/Error_detection_and_correction

Esto le puede ayudar con los bits modificados, pero puede no ser adecuado para comprobar cada vez que tenga todos los bits.

Al final, probablemente tomará mucho más que unas pocas líneas de código simple.

Answer 3

Si he entendido bien, tiene dos necesidades:

1. Modula una señal en el sonido y luego lo demodula.
2. Aplica la corrección de errores ya que el canal no es confiable.

La modulación y demodulación es una aplicación conocida, con several ways para modular la información.

Número dos, la corrección de errores también es conocida y tiene varias posibilidades. Cuál de ellas es aplicable depende de la tasa de error y si tiene operación dúplex para que pueda solicitar reenvíos. Si tiene una calidad decente y puede solicitar reenvíos, vale la pena explorar un enfoque como el que está utilizando TCP.

De lo contrario, tendrá que ir a los algoritmos de detección de errores y corrección de errores, como el utilizado en los CDROM.

Editar después del comentario

Tener la modulación/demodulación hecho y no hay posibilidades de reenvío se estrecha el problema. Si tiene problemas de sincronización, aún así le recomendaría que lea los métodos de modulación (de) existentes, ya que hay formas de volver a sincronizar automáticamente con el emisor y aumentar la relación señal/ruido.

Hasta el problema central; Corrección de errores tendrá que agregar bits de paridad a su flujo de salida para poder detectar los errores. Comenzando con el artículo de corrección de errores hacia adelante @Justin sugiere, un esquema que parece bastante simple, pero aún poderoso es el esquema Hamming(7,4).