Задача кодирования / исправления ошибок

Question

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

Если кто-то использует коррекцию ошибок REED SOLOMON с байтами 4 «четность», прикрепленные к концу 4 «данных» байтов, таких как DDDDPPPP, и вы в конечном итоге с DDDEPPP (где e - ошибка), а байт паритета был отброшен Я не верю, что есть способ восстановить первоначальное сообщение (хотя правильно меня, если я ошибаюсь) ...

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

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

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

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

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

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

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

Answer 1

В отсутствие «хорошей» алгебраической структуры я подозреваю, что будет трудно найти краткую схему, которая заставляет вас полностью до 10 ** 4 кодовых слова, поскольку информационно-теоретически не хватает. (Ниже приведен GF (5) для 5 ** 5 = 3125.) К счастью, проблема достаточно мала, что вы можете попробовать жадный метод Code Shannon (найти кодовое слово, которое не конфликтует с одним уже выбранным, Добавьте его в комплект).

---

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

Редактировать: BMM6O продвинул утверждение о том, что вторая часть моего решения неверна. Я не согласен.

Давайте просмотрим возможности для случая, когда MSBS 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] имеют неверные MS и предполагают, что это x [5], x [6], x [7].

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

Если x [3] отброшен, и x [4] поврежден, то у нас есть неправильная оценка в 3, а шесть правильных оценок.

Если x [5] отброшен, и x [4] поврежден, то у нас неверная оценка в 5 и шесть правильных оценок.

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

Answer 2

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

Так выглядит как код Reed-Solomon, действительно отвечает, и вы действительно можете получить восстановление из одного стирания и одну ошибку в 8,4 кода.

Answer 3

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

Answer 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, поэтому он может исправить любые однобайтовые ошибки.

Answer 5

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

Answer 6

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

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

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

Answer 7

На самом деле, как сказал Крыстин, когда вы исправите код RS, как сообщение, так и байты «Паритета» будут исправлены, если у вас есть V + 2E <(NK), где V - количество стираний (вы знаете позицию ) и E - количество ошибок. Это означает, что если у вас есть только ошибки, вы можете исправить ошибки (NK) / 2 или (NK-1) стирания (о двойном количестве ошибок) или смесь обоих (см. Статья Blahut: Transform Techniques для кодов управления ошибками а также Универсальный декодер народно-соломона).

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

Ограниченный V + 2e <(Nk) является оптимальным, вы не можете сделать лучше (именно поэтому Reed-Solomon называется оптимальным кодом исправления ошибок). На самом деле можно выйти за рамки этого предела, используя подходы BruteForce, до определенного момента (вы можете получить 1 или 2 символа для каждого 8 символов), используя Список декодирования, Но это все еще домен в его младенчестве, я не знаю о какой-либо практической реализации, которая работает.