Кодирование/исправление ошибок

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

Если вы используете коррекцию ошибок Рида Соломона с 4-дюймовыми байтами с четностью, указанными в конце байтов данных "4", такими как DDDDPPPP, и вы закончите с DDDEPPP (где E - ошибка) и байт четности был отброшен, я не верю, что есть способ восстановить исходное сообщение (хотя поправьте меня, если я ошибаюсь)...

Как насчет умножения (или выполнения другой математической операции) начального 4-байтового сообщения константой, а затем использования свойств обратной математической операции для определения того, какой байт был отброшен. Или наложите некоторые ограничения на структуру сообщения, поэтому каждый другой байт должен быть нечетным, а остальные должны быть четными.

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

Я ищу любые сумасшедшие идеи, которые могли бы иметь любые идеи?

EDIT:

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

Форма может быть изменена таким образом, чтобы она всегда печатала пробел между начальными четырьмя числами и номерами исправлений ошибок, то есть 1234 5678, так что можно было бы узнать, была ли сброшена начальная цифра 1234 или была сброшена цифра исправления ошибки 5678, если это облегчает задачу. Я думаю несколько похоже на то, как они проверяют номера кредитных карт с помощью алгоритма, но в четырехзначных кусках.

Надеюсь, это дает некоторые разъяснения относительно того, что я ищу...

Ответ 1

В отсутствие "приятной" алгебраической структуры, я подозреваю, что будет трудно найти краткую схему, которая поможет вам до 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 не соответствует индексу mod 2, то этот байт поврежден и/или он сдвиг слева от удаления. Предположим, что это хорошо и сдвиньте его вправо (возможно, накапливая несколько разных возможных значений в точке). Теперь мы имеем по крайней мере семь оценок квартичного многочлена f в известных точках, из которых не более одного коррумпировано. Теперь мы можем попробовать все возможности для коррупции.

EDIT: bmm6o выдвинул требование о том, что вторая часть моего решения неверна. Я не согласен.

Давайте рассмотрим возможности для случая, когда MSB являются 0101101. Предположим, что X - массив отправленных байтов, а Y - массив полученных байтов. С одной стороны, Y [0], Y [1], Y [2], Y [3] имеют правильные MSB и считаются X [0], X [1], X [2], X [3], С другой стороны, Y [4], Y [5], Y [6] имеют неправильные MSB и считаются X [5], X [6], X [7].

Если X [4] опущено, то мы имеем семь правильных оценок f.

Если X [3] опущен и X [4] поврежден, то мы имеем неверную оценку в 3 и шесть правильных оценок.

Если X [5] опущен и X [4] поврежден, то мы имеем неверную оценку в 5 и шесть правильных оценок.

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

Ответ 2

Думаю, вам нужно будет изучить, что коды стирания могут предложить вам. Я не знаю границ, но, возможно, какой-то код MDS может это сделать.

EDIT: после быстрого поиска я нашел RSCode и в example говорится, что

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.

Ответ 3

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

Ответ 4

Коды коррекции ошибок могут, в общем случае, выполнять ручные стирания, но в литературе считается, что положение стирания известно. В большинстве случаев стирание будет вводиться демодулятором, если есть низкая уверенность в том, что правильные данные могут быть получены из канала. Например, если сигнал явно не равен 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, поэтому он может исправлять любые однобайтовые ошибки.

Ответ 5

В случае десятичных цифр, считая, что один идет с первой цифрой нечетной, второй цифрой, третьей цифрой нечетной и т.д. - с двумя цифрами, вы получаете 00-99, который может быть представлен в 3 нечетных/четных/нечетных цифрах (125 полных комбинаций) - 00 = 101, 01 = 103, 20 = 181, 99 = 789 и т.д. Таким образом, каждый кодирует два набора десятичных цифр на 6 полных цифр, тогда последние две цифры означают вещи о первых наборах из 2 цифр или контрольной суммы какого-то рода... Следующая, последняя цифра, я полагаю, может быть своего рода нечетным/четным индикатором на каждом из начальных 2-значных начальных сообщений (1 = даже первые 2 цифры, 3 = нечетные первые два цифры) и следуйте схеме нечетности. Тогда последняя цифра может быть одним местом суммы отдельных цифр, таким образом, если цифра отсутствует, это будет сразу же очевидно и может быть исправлено при условии, что последняя цифра верна. Хотя, это отбросило бы вещи, если бы одна из двух последних цифр была отброшена...

Ответ 6

По-видимому, теоретически возможно, если мы допустим ошибку 1 бит в неправильном байте. Нам нужно 3 бита, чтобы идентифицировать сброшенный байт и 3 бита, чтобы идентифицировать неправильный байт и 3 бита, чтобы идентифицировать неправильный бит. У нас в 3 раза больше лишних бит.

Но если нам нужно идентифицировать любое количество ошибок в ошибочном байте, оно достигает 30 бит. Даже это кажется возможным с 32 бит, хотя 32 слишком близко для моего комфорта.

Но я не знаю, как горячо кодировать, чтобы получить это. Попробуйте турбокод?

Ответ 7

Фактически, как сказал Кристиан, когда вы исправляете код RS, и сообщение И байты четности будут исправлены, если у вас есть v + 2e < (n-k), где v - количество стираний (вы знаете позицию), а e - количество ошибок. Это означает, что если у вас есть только ошибки, вы можете исправить ошибки до (nk)/2 или (nk-1) (примерно вдвое больше числа ошибок) или их сочетание (см. Статья Блаху: методы преобразования для кодов управления ошибками и Универсальный декодер Рида-Соломона).

Что еще приятнее, так это то, что вы можете проверить, что исправление было успешным: проверяя, что полином полинома синдрома содержит только 0 коэффициентов, вы знаете, что байты с сообщением + четности являются правильными. Вы можете сделать это раньше, чтобы проверить, нуждается ли сообщение в коррекции, а также вы можете выполнить проверку после декодирования, чтобы проверить, что и сообщение, и байты четности были полностью восстановлены.

Оценка v + 2e < (n-k) является оптимальным, вы не можете сделать лучше (почему Рид-Соломон называется оптимальным кодом коррекции ошибок). Фактически, можно выйти за пределы этого предела, используя подходы bruteforce, вплоть до определенной точки (вы можете получить 1 или 2 символа для каждого 8 символов), используя декодирование списка, но он все еще является доменом в раннем детстве, я не знаю никакой практической реализации, которая работает.