Каков процесс достижения исправления ошибок в двоичных данных?

Question

Я читал и исследовал исправление ошибок в двоичных данных, но я не могу понять, как это сделать. Я прочитал https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction, и это связанные статьи, и у меня есть понимание вовлеченной математики, но я хочу полностью понять весь процесс.

Может ли кто-нибудь объяснить мне или связать меня с объяснением, которое скажет мне, шаг за шагом, как я получаю двоичное представление, скажем, строки «Привет, как дела?» (01001000011001010110110001101100011011110010110000100000011010000110111101110111001000000110000101110010011001010010000001111001011011110111010100111111) к блобу двоичного кода с достаточной информацией об исправлении ошибок для восстановления до 1 из 10 искаженных битов, а затем интерпретировать результат и определить, какие биты ошибочны? Я могу понять обе строки кода или математику, поэтому любая помощь будет приветствоваться. Спасибо!

Answer 1

Из статьи wiki систематический процесс кодирования рассматривает сообщение как многочлен с конечными коэффициентами поля, добавляет необходимое количество нулей (умножается на x^t), делит на генераторный многочлен, а затем вычитает остаток из тех добавлены обнуленные байты. Это означает, что многочлен закодированного сообщения является точным кратным генераторному многочлену.

Если исходный закодированный полином сообщения вычисляется в корнях генераторного многочлена (a^1, a^2, ...), результатом является множество нулей. Если полученное кодированное сообщение с ошибками оценивается в корнях генераторного полинома, исходные термины выпадают, а результатом является набор «синдромов», которые являются функцией местоположений ошибок и значений ошибок. Затем в статье wiki объясняется ключевое уравнение между полиномом локатора ошибок (лямбда) и «синдромами».

В статье wiki объясняются 4 метода, которые можно использовать, чтобы преобразовать синдромы в места ошибок и значения ошибок, но Berlekamp-Massey и Euclid являются двумя основными используемыми методами.

Как указано в статье wiki, для исправления ошибки для каждой ошибки требуются два критерия четности (поскольку для каждой ошибки указаны местоположение неизвестной ошибки, местоположение ошибки и значение ошибки). Для обработки ошибок 10%, тогда 20% сообщения должно быть четным. Если сообщение имеет 30 байт, то 20 байтов четности добавляются для создания 50-байтового кодированного сообщения, из которых может быть исправлено до 10 байтов.

вики статья содержит ссылку на эту страницу учебника НАСА:

http://ntrs.nasa.gov/archive/nasa/casi.ntrs.nasa.gov/19900019023_1990019023.pdf

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

http://rcgldr.net/misc/ecc.pdf

Там какие-то вещи в моем учебнике, что вам не нужно будет, как решения квадратного или кубического уравнения (наследие вещь, оставленная, что я не снимал), и он отсутствует материал как расширенный Евклид или Berlekamp Massey расшифровывает, но этого достаточно, чтобы начать.