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

Question

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

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

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

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

Редактировать: Добавлены примеры данных

Best case data:
 in: 0000010101000010110100101101100111000000100100101101100111000000100100001100000010000101110101001101100111000101110000001001111011001100110000001001100111011110110101011100111011000100110000001000010111
out: 0010101000010110100101101100111000000100100101101100111000000100100001100000010000101110101001101100111000101110000001001111011001100110000001001100111011110110101011100111011000100110000001000010111011

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

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

Answer 1

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

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

Модуляция и демодуляция - хорошо известное приложение, с несколькими способами для модуляции информации.

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

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

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

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

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

Answer 2

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

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

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

Answer 3

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

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

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