Рид Соломон Декодирование - Коррекция ошибок - Расчет синдромов

Question

Я реализую декодирование Рида Соломона для декодирования QR-кодов с использованием C++. Я реализовал основную часть декодирования и обнаружения ошибок до сих пор. Я придерживался Руководства ISO/IEC 18004: 2006. Как я видел в Приложении B: шаги декодирования ошибок, Синдромы S (i) рассчитываются как S (i) = R (a^i). Предположим, что мы имеем High Error Correction Level, поэтому у нас есть 9 кодов данных и 17 кодовых слов с исправлением ошибок, которые дают нам в общей сложности 26 кодовых слов, когда мы находимся в QR-кодах версии 1. Итак, я предполагаю, что показан многочлен R (x) в Pg.76 стандарта ISO/IEC 18004: 2006 будет представлена ​​последовательность из Кодов слов и кодов ошибок с правильной мощностью x соответственно. Таким образом, S (i) = R (a^j), где i = 0 ... 15 и j = 0 ... 25 для высокого уровня коррекции ошибок. Но когда я запускаю свой код, и поскольку у меня есть целая матрица QR Code без ошибок, я ожидаю, что все синдромы будут равны нулю, я беру в результате ненулевые синдромы. Я понял что-то неправильно в расчете Синдрома при Арифметике поля Галуа через Рид Соломон Декодирование?

Answer 1

После просмотра ссылок на QR-код, для версии 1, уровень H, с 9 байтами данных и 17 байтами исправления ошибок, с использованием генераторного полинома g (x) = (x-1) (xa) (xa^2). .. (xa^(16)), вы должны использовать синдромы S (i) = R (a^i) для i = 0 до 16. В случае без ошибок все 17 синдромов должны быть равны нулю.

Там приличная вики статья для исправления ошибок Рида-Соломона:

http://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction

вики статья содержит ссылку на Nasa технологий краткое RSECC учебник:

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

Ссылка на C исходный код для консольной программы, демонстрирующий методы RSECC для 8-битного поля (пользователь выбирает из 29 возможных полей). Я использую компиляторы Microsoft или Visual Studio для ее компиляции и Windows для ее запуска, но он должен работать на большинстве систем.

Примечание. Я обновил демо-программу ecc, чтобы обрабатывать стирания в дополнение к ошибкам, на всякий случай, когда это может быть полезно. Также добавлен код для вычисления значения ошибки полинома Omega в случае, если метод Евклида не используется. Ссылка такая же, как и раньше:

http://rcgldr.net/misc/eccdemo8.zip

---

Обновление на основе вопросов в комментариях:

Мой вопрос, о котором GF (2^8):

GF(2^8) is based on 9 bit polynomial 
     x^8 + x^4 + x^3 + x^2 + 1 = hex 11d 
     primitive is x + 0 (hex 2) 

При поиске ссылок QR-кода используются разные генераторные полиномы в зависимости от уровня коррекции: L (низкий), M (средний), Q (качество), H (высокий).

Вопрос о декодировании с использованием матриц. В работе Sklar показано декодирование с использованием линейных уравнений и инверсии матрицы. Эта процедура должна принять максимальный случай ошибки t, который будет равен полу (e/2), где e - количество байтов коррекции ошибок (также называемых байтами четности или избыточными байтами). Если детерминант равен нулю, попробуйте t -1 ошибок, если это ноль, попробуйте t -2 ошибки и т. Д., Пока детерминант не равен нулю или t не будет сведен к нулю.

Методы декодирования Euclid или Berlekamp Massey автоматически определят количество ошибок.

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

---

Update # 2

Я сделал краткий обзор документа ISO.

Генерирующий многочлен (x - 1) (x - 2) (x - 2^2) ..., поэтому проверяемые синдромы S (0) - S (n - 1), как вы упомянули ранее , а в случае нулевых ошибок все синдромы S (0) - S (n-1) должны быть равны нулю.

Документ ISO использует термин кодовые слова для обозначения байтов (или символов), но в большинстве статей ecc термин кодовое слово относится к массиву байтов, включая байты с байтами данных и ошибок, и часто называются байты исправления ошибок байты четности, избыточные байты или байты остатка. Поэтому имейте это в виду, если читаете другие статьи ecc.

В документе ISO упоминаются «стирания» и «ошибки», которые являются терминологией RSECC. «Erasures» ссылаются на плохие (или потенциально плохие) байты данных в известных местах, обнаруженных вне RSECC. «Ошибки» относятся к плохим байтам, которые не обнаружены вне RSECC, и определяются только во время декодирования RSECC. Затем в документе отмечается, что не существует некорректных шаблонов бит данных, что подразумевает отсутствие обнаружения «стирания». Затем он добавляет к путанице, показывая уравнение, которое включает в себя стирание и количество ошибок.

Если вам интересно, файл PDF Nasa на RSECC объясняет обработку стирания, начиная со страницы 86, но я не думаю, что это относится к QR-кодам.

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

Возвращаясь к документу ISO, он использует P отметить номер или исправление ошибок байт, используемые для защиты misdecode, в отличие от используемого для коррекции. Это показано в таблице 9 на странице 38. Для версии 1, которая, кажется, что вы используете, переосмысливая:

error correction level 
| number of data bytes 
| | number of ecc bytes used for correction 
| | | number of ecc bytes used for misdecode protection (p) 
| | | | correction capability 
L 19 4 3 2/26 ~ 07.69% 
M 16 8 2 4/26 ~ 15.38% 
Q 13 12 1 6/26 ~ 23.08% 
H 9 16 1 8/26 ~ 30.77% 

Учитывая, что эта таблица показывает, что ожидаемая возможность коррекции выполняется без использования подчисток , то даже если бы были обнаружены стирания, они не нужны.

С GF (2^8) имеется 255 (не 256) возможных мест ошибок, которые могут быть сгенерированы декодированием RSECC, но в версии 1 имеется только 26 действительных местоположений. Любое генерируемое местоположение за пределами 26 действительных местоположений будет обнаружением ошибки, которую невозможно исправить. Таким образом, для L уровень 3 p байт переводится как коэффициент неправильной коррекции на 1/(2^24), а диапазон местоположения умножает это на (26/255)^2 на вероятность вероятности 6.20E-10. Для H уровень, 1 p Баланс переводится как коэффициент неправильной коррекции (1/2^8) и диапазон местоположения (26/255)^8 для вероятности ~ 4.56E-11.

Обратите внимание, что для версии 2, р = 0 для уровней М, Q, Н, опираясь на диапазон местонахождения (44/255)^(8, или 11, или 14) для miscorrection вероятности 7.87E-7, 4.04E-9, 2.07E-11.