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

Question

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

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

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

РЕДАКТИРОВАТЬ

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

Answer 1

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

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

Answer 2

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

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

Answer 3

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

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

Answer 4

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

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

Answer 5

Если ваша частота ошибок составляет 50%, поток битов ЯВЛЯЕТСЯ случайным и не имеет НИКАКОЙ КОРРЕЛЯЦИИ с исходным потоком битов.Это похоже на то, как если бы вы выполняли операцию XOR с совершенно случайным битовым потоком, и результат был бы совершенно случайным.И вы ничего не можете с этим поделать.

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

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

Answer 6

Ты турбокоды смотрел?

-- МаркусКью

Да!Я неправильно понял это как 50% рандомизированных, а не 50% перевернутых.

Answer 7

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