Кодирование / проблема Коррекции ошибок
Математически выполнимо закодировать и подписать 4-байтовое сообщение в 8 байтов и если один из 8 байтов полностью отбрасывается, и другой неправ восстановить первоначальное 4-байтовое сообщение? Не было бы никакого способа ретранслировать, ни будет местоположение отброшенного байта быть известным.
Если Вы используете коррекцию ошибок Reed Solomon с 4 байтами "четности", прикрепляемыми на в конец 4 байтов "данных", таких как DDDDPPPP, и Вы заканчиваете с DDDEPPP (где E является ошибкой), и байт контроля четности был отброшен, я не полагаю, что существует способ восстановить первоначальное сообщение (хотя исправляют меня, если я неправ)...
Что относительно того, чтобы умножиться (или выполнить другую математическую операцию) первоначальное 4-байтовое сообщение константой, затем использующие свойства обратной математической операции для определения, какой байт был отброшен. Или, наложите некоторые ограничения на структуру сообщения, таким образом, любой байт должен быть нечетным, и другие должны быть ровными.
С другой стороны, вместо байтов, это могли также быть 4 десятичных цифры, закодированные некоторым способом в 8 десятичных цифр, где ошибки могли быть обнаружены и исправлены при тех же упомянутых выше обстоятельствах - никакая повторная передача и местоположение отброшенного байта не известны.
Я ищу любые сумасшедшие идеи, которые любой мог бы иметь... Какие-либо идеи там?
Править:
Это может быть немного изобретено, но ситуация, что я пытаюсь решить, является той, где у Вас есть, скажем, неисправный принтер, который распечатывает важные числа на форму, которые затем отправляются по почте прочь в фирму по обработке, которая использует OCR для чтения форм. OCR не будет прекрасным, но он должен быть рядом только с цифрами для чтения. Неисправный принтер мог быть большей проблемой, где он может отбросить целое число, но нет никакого способа знать, какой он отбросит, но они будут всегда выходить в правильном порядке, не будет никаких подкачанных цифр.
Форма могла быть изменена так, чтобы она всегда печатала пространство между начальными четырьмя числами и числами коррекции ошибок, т.е. 1234 5678, так, чтобы можно было бы знать, была ли начальная цифра 1234 года отброшена, или 5 678 цифр коррекции ошибок были отброшены, если это делает проблему легче решить. Я думаю несколько подобный тому, как они проверяют номера кредитных карт с помощью алгоритма, но в четырех блоках цифры.
Хотелось бы надеяться, это предоставляет некоторое разъяснение относительно того, что я ищу...
6 ответов
В отсутствие "хорошей" алгебраической структуры, я подозреваю, что будет трудно найти краткую схему, которая дала бы вам полный путь до 10 ** 4 кодовых слов, поскольку теоретически информации не так много провисания. (В приведенном ниже примере можно использовать GF (5) для 5 ** 5 = 3125.) К счастью, проблема достаточно мала, чтобы вы могли попробовать жадный метод построения кода Шеннона (найти кодовое слово, которое не конфликтует с уже выбранным, добавить в набор).
Кодировать до 35 бит как полином f четвертой степени над GF (128). Вычислите многочлен в восьми заранее определенных точках x0, ..., x7 и закодируйте как 0f (x0) 1f (x1) 0f (x2) 1f (x3) 0f (x4) 1f (x5) 0f (x6) 1f (x7), где чередующиеся нули и единицы хранятся в MSB.
При декодировании сначала посмотрите на MSB. Если MSB не соответствует модулю индекса 2, то этот байт поврежден и / или был сдвинут влево в результате удаления. Предположите, что это хорошо, и сдвиньте его назад вправо (возможно, накопив несколько различных возможных значений в одной точке). Теперь у нас есть не менее семи вычислений многочлена f четвертой степени в известных точках, из которых не более одного повреждено. Теперь мы можем попробовать все возможности коррупции.
РЕДАКТИРОВАТЬ: bmm6o выдвинул утверждение, что вторая часть моего решения неверна. Я не согласен.
Давайте рассмотрим возможности для случая, когда MSB равны 0101101. Предположим, X - это массив отправленных байтов, а Y - массив полученных байтов. С одной стороны, Y [0], Y [1], Y [2], Y [3] имеют правильные старшие биты и считаются X [0], X [1], X [2], X [3] . С другой стороны, Y [4], Y [5], Y [6] имеют неправильные старшие биты и считаются X [5], X [6], X [7].
Если опустить X [4], то мы получим семь правильных оценок f.
Если X [3] отброшен, а X [4] поврежден, то у нас есть неправильная оценка в 3 и шесть правильных оценок.
Если X [5] отброшен, а X [4] поврежден, то мы имеем неправильную оценку в 5 и шесть правильных оценок.
Есть и другие возможности помимо этих, но у нас никогда не бывает меньше шести правильных оценок, которых достаточно для восстановления f.
Думаю, вам нужно изучить, что коды стирания могут предложить вам. Я сам не знаю никаких границ, но, возможно, какой-то код MDS мог бы этого достичь.
РЕДАКТИРОВАТЬ: После быстрого поиска я нашел библиотеку RSCode , и в примере говорится, что
In general, with E errors, and K erasures, you will need
* 2E + K bytes of parity to be able to correct the codeword
* back to recover the original message data.
Похоже, код Рида-Соломона действительно является ответом, и вы действительно можете получить восстановление после одного стирания и одной ошибки в коде 8,4.
Коды четности работают до тех пор, пока два разных байта данных не затронуты ошибкой или потерей, и пока ошибка не равна ни одному байту данных, а байт четности потерян, имхо.
В случае десятичных цифр, при условии, что первая цифра нечетная, вторая цифра четная, третья нечетная и т. Д. - с двумя цифрами вы получите 00-99, которые могут быть представлены тремя нечетными / четными / нечетными цифрами. (Всего 125 комбинаций) - 00 = 101, 01 = 103, 20 = 181, 99 = 789 и т. Д. Таким образом, один кодирует два набора десятичных цифр в 6 общих цифр, затем последние две цифры означают вещи о первых наборах из 2 цифр. цифры или какая-то контрольная сумма ... Предполагаю, что предпоследняя цифра могла быть своего рода нечетным / четным индикатором каждого из первых двухзначных исходных сообщений (1 = четные первые 2 цифры, 3 = нечетные первые две цифры) и следуйте образцу нечетности. Тогда последняя цифра может быть единицей суммы отдельных цифр, таким образом, если цифра отсутствует, она будет сразу очевидна и может быть исправлена, если последняя цифра верна. Хотя, если бы одна из последних двух цифр была опущена, все бы испортилось ...
Это выглядит теоретически возможным, если мы предположим, что 1 битовая ошибка в неправильном байте. Нам нужно 3 бита для идентификации отброшенного байта и 3 бита для определения неправильного байта и 3 бита для определения неправильного бита. У нас в 3 раза больше лишних битов.
Но если нам нужно идентифицировать какое-либо количество битовых ошибок в неправильном байте, мы получаем 30 битов. Даже это кажется возможным с 32 битами, хотя 32 для меня слишком близко.
Но я не знаю, как правильно кодировать, чтобы получить это. Попробуйте турбокод?
Коды с исправлением ошибок, как правило, могут обрабатывать стирания, но в литературе предполагается, что положение стирания известно. В большинстве случаев стирание вносится демодулятором, когда нет уверенности в том, что правильные данные могут быть получены из канала. Например, если сигнал явно не равен 0 или 1, устройство может указать, что данные были потеряны, вместо того, чтобы рисковать введением ошибки. Поскольку стирание по сути является ошибкой с известной позицией, их гораздо легче исправить.
Я не уверен, в какой у вас ситуации, когда вы можете потерять одно значение, но при этом можете быть уверены, что остальные значения будут доставлены в правильном порядке, но это не та ситуация, к которой относится классическая теория кодирования.
Алгоритмист предлагает выше следующее: если вы можете ограничить себя всего 7 битами информации, вы можете заполнить 8-й бит каждого байта чередующимися 0 и 1, что позволит вам узнать расположение недостающего байта. . То есть поместите 0 в старший бит байтов 0, 2, 4, 6 и 1 в старшие биты остальных.На принимающей стороне, если вы получаете только 7 байтов, недостающий будет удален между байтами, чьи старшие биты совпадают. К сожалению, это не совсем так: если стирание и ошибка смежны, вы не можете сразу узнать, какой байт был отброшен. Например, старшие биты 0101101 могут быть результатом отбрасывания 4-го байта, или ошибки в 4-м байте и отбрасывания 3-го, или ошибки в 4-м байте и отбрасывания 5-го.
Вы можете использовать линейный код:
1 0 0 0 0 1 1 1
0 1 0 0 1 0 1 1
0 0 1 0 1 1 0 1
0 0 0 1 1 1 1 0
(т.е. вы будете отправлять такие данные, как (a, b, c, d, b + c + d, a + c + d, a + b + d, a + b + c) (где сложение реализовано с помощью XOR, поскольку a, b, c, d являются элементами GF (128))). Это линейный код с расстоянием 4, поэтому он может исправить однобайтовую ошибку. Вы можете декодировать с помощью синдромного декодирования , и поскольку код самодуальный, матрица H будет такой же, как указано выше.
В случае, когда есть отброшенный байт, вы можете использовать описанную выше технику, чтобы определить, какой именно байт. Как только вы это определили, вы, по сути, декодируете другой код - «проколотый» код, созданный отбрасыванием данного байта. Поскольку проколотый код остается линейным, для определения ошибки можно использовать синдромное декодирование. Вам нужно будет вычислить матрицу проверки на четность для каждого из сокращенных кодов, но вы можете сделать это заранее. Сокращенный код имеет расстояние 3, поэтому он может исправить любые однобайтовые ошибки.