Какой алгоритм для чрезвычайно высоких ошибок, не связанных с пакетной обработкой?

Question

У меня есть двоичный поток с очень высокой частотой ошибок. Частота появления ошибок составляет 50%, что означает, что каждый бит имеет 50% шанс перевернуться. Ошибка не возникает в пакетах и ​​является полностью случайной, поэтому коды Рида-Соломона не будут работать хорошо.

Какую схему или алгоритм следует применить к потоку? Мне наплевать на накладные расходы.

Это все теоретически, поэтому нет смысла спрашивать, могу ли я просто уменьшить ошибку потока.

EDIT

Не говорите, что это невозможно, самый первый ответ говорит, что это возможно с помощью теоремы о кодировании шумного канала.

Answer 1

Если частота ошибок составляет 50%, то это в основном случайный шум, не так ли? Я имею в виду, подумайте только о попытке передать один бит. Если вы отправите поток бесконечный правильного бита, с вероятностью ошибки 50% вы получите половину 1 с и половину 0, независимо от того, равен ли правильный бит 1 или 0.

Если это на самом деле меньше 50% (например, 50% битов будет «случайным», а не «перевернутым»), тогда вы можете просто повторить данные - передать каждый бит 128 раз и обработать, что вы получите больше каждые 100 полученных битов. Это простое в коде, чрезвычайно неэффективное, совсем не математическое решение:)

Answer 2

Что ж, суть исправления ошибок Рида-Соломона состоит в том, что большинство реальных ошибок происходит в пакетах, поэтому вы чередуете и удаляете чередование данных. Если ваши ошибки абсолютно случайны, то есть распределены по Пуассону, то просто добавьте избыточность в поток простым, математически эффективным способом. Одна вещь, на которую вы могли бы взглянуть, - это какая-то скрытая марковская модель, такая как решетчатый код. Это в основном просто математически эффективный способ добавления избыточности.

Кроме того, обратите внимание на теорему о канальном кодировании с шумом . Строго говоря, это не относится к цифровым данным, но если источником этих битов является какой-то аналоговый процесс или если вы могли бы смоделировать ваши биты , как если бы были результатом какого-то аналогового процесса, это могло бы дать вам некоторое представление о том, что вы могли бы сделать лучше всего. Это помешает вам тратить время, пытаясь добиться большего, чем математически возможно.

Answer 3

Когда канал приближается к 50% реальной скорости шума, больше нет возможности передавать какую-либо информацию вообще. К ответу Джона Скита: если частота ошибок составляет менее 50% шума, вы можете получить данные, выполнив более длинные пакеты предполагаемых данных с избыточностью и статистически глядя на результат с некоторой степенью уверенности в исходном значении. Необходимая длина пакета и уровни достоверности для данной длины будут затем получены на основе характеристики шума. Однако поймите, что вы делаете здесь, эффективно снижая скорость передачи данных, чтобы улучшить чистое соотношение сигнал / шум передаваемого потока.

В вашем вопросе вы могли бы исключить это как вариант, но лучшая схема кодирования могла бы основываться на относительном существовании (или отсутствии) самого потока данных. Другими словами, чтобы передать двоичный файл .... отправьте переменный поток 1/0. Чтобы отправить ноль, ничего не отправлять или, возможно, отправить постоянный уровень. Идея состоит в том, что отправка (и получение) чего-либо представляет одно состояние, а отправка (и получение) ничего не представляет другое состояние. Это будет эффективно напоминать тип биполярного кодирования данных.

Answer 4

Теорема о кодировании с шумным каналом говорит, что вы действительно можете достичь пропускной способности Шеннона для канала. не говорит, что канал имеет ненулевую емкость!

Если вы рандомизируете 100% битов в канале, 50% из них останутся неизменными, поэтому вы переворачиваете случайные 50% битов. Должно быть очевидно, что вы не можете отправлять данные по такому каналу - его емкость по Шеннону равна нулю.

Answer 5

Если частота ваших ошибок составляет 50%, поток битов является случайным и не имеет корреляции с исходным потоком битов. Это похоже на то, что вы делаете XOR потока с совершенно случайным потоком битов, а результат совершенно случайный. И с этим ничего не поделаешь.

Частота смены кадров должна быть ниже 50%, чтобы любая схема работала. Конечно, это может быть более 50%, но затем вы можете сначала инвертировать поток, а затем обработать его, как если бы уровень ошибок был ниже 50%.

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

Answer 6

Если точно 50% битов перевернуто в любой данной передаче, а не каждый бит перевернут с вероятностью 50%, вы можете отправить бит информации, отправив передачу двух битов - отправьте 0 как 00 и 1 как 01. Если первый бит принятого кодового слова равен 1, то другой бит отменяется.

Answer 7

Вы смотрели на турбокоды?

- MarkusQ

Doh! Я неправильно понял, что 50% рандомизированы, а не 50% перевернуты.