Алгоритм избыточности для чтения шумного битового потока

Question

Я читаю поток с потерями и мне нужен способ восстановить как можно больше полезной информации. Может быть 1 вместо 0 и 0 в ладони 1, но точность, вероятно, превышает 80%.

Бонус был бы, если бы алгоритм мог компенсировать недостающие/слишком много бит.

Источник, который я читаю, является аналогом шума (микрофон через FFT), и время считывания может меняться в зависимости от скорости компьютера.

Я помню, как читал об алгоритмах, используемых на CD-ROM, делая это в 3? слои, поэтому я предполагаю, что использование нескольких слоев - хороший вариант. Однако я не помню деталей, поэтому, если кто-то может поделиться некоторыми идеями, это было бы здорово! :)

Edit: Добавленные выборочные данные

 
Best case data: 
in: 0000010101000010110100101101100111000000100100101101100111000000100100001100000010000101110101001101100111000101110000001001111011001100110000001001100111011110110101011100111011000100110000001000010111 
out: 0010101000010110100101101100111000000100100101101100111000000100100001100000010000101110101001101100111000101110000001001111011001100110000001001100111011110110101011100111011000100110000001000010111011 

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

Edit2: Я могу проверочные данные отправляются. В настоящее время пытается реализовать простую проверку XOR (хотя этого будет недостаточно).

Answer 1

Вам необходимо использовать forward error correction. Проверка четности XOR будет определять только при возникновении ошибки. Простым алгоритмом коррекции ошибок было бы отправить каждый фрагмент данных несколько раз (по крайней мере 3) и принять решение большинства.

Выбор алгоритма зависит от нескольких факторов:

• использования канала (если у вас есть много свободного времени, вам не нужно эффективное кодирование)
• типы ошибок: это плохие биты в случайном порядке разнесены или же они, как правило, происходят в строке
• время обработки: сложность кода ограничено, если передача данных должна быть быстрой

Answer 2

Есть много возможностей, см: http://en.wikipedia.org/wiki/Error_detection_and_correction

Это может помочь вам с измененными битами, но может быть неподходящим для проверки всякий раз, когда у вас есть все биты.

В конце концов, это, вероятно, займет гораздо больше, чем несколько строк простого кода.

Answer 3

Если я вас правильно понимаю, у вас есть две потребности:

1. Модулируйте сигнал в звук, а затем демодулируйте его.
2. Применить исправление ошибок, так как канал ненадежный.

Модуляция и демодуляция - известное приложение, с several ways для модуляции информации.

Номер два, исправление ошибок также хорошо известно и имеет несколько возможностей. Какой из них применим, зависит от частоты ошибок и есть ли у вас дуплексная операция, чтобы вы могли запрашивать повторные попытки. Если у вас есть достойное качество и вы можете запросить повторную попытку, то подход, который использует один TCP, стоит изучить.

В противном случае вам придется перейти к алгоритмам обнаружения ошибок и исправления ошибок, как, например, тот, который используется на CD-ROM.

Редактировать после комментария

, имеющей модуляции/демодуляции сделано и нет возможности RESEND сужает проблему. Если у вас возникли проблемы с синхронизацией, я бы по-прежнему рекомендовал вам ознакомиться с существующими (де) методами модуляции, так как есть способы автоматической повторной синхронизации с отправителем и увеличения отношения сигнал/шум.

К основной проблеме; исправления ошибок вам нужно будет добавить бит четности в выходной поток, чтобы иметь возможность обнаруживать ошибки. Начиная с статьи с прямой коррекцией ошибок @Justin предлагает схему, которая выглядит довольно простой, но все же мощной является схема Hamming(7,4).