Добрый день!

Использую декодирование кода Рида-Соломона по следующему алгоритму.
1. Определяется полином локаторов стираний (в данном случае код с выколотыми проверочными байтами, поэтому этот полином постоянный).
2. Определяются модифицированные синдромы, которые уже соответствуют ошибкам.
3. Алгоритмом Берлекэмпа определяются корни полинома локаторов ошибок, и далее - локаторы ошибок.
4. Определяются ошибки.

В моем случае код должен исправлять 2 ошибки.
Когда допущена 1 или 2 ошибки, все исправляется.
Если ошибок больше двух, то полином локаторов ошибок так же имеет степень 2 (как будто произошло 2 ошибки), но, естественно, позиции ошибок вычисляются неверно.
Вроде как на 3-м этапе должен делаться вывод, что ошибок больше 2. Насколько я понимаю, этим условием является то, что степень полинома локаторов больше 2. Но почему-то такого не получается.

Может быть, кто-то сможет помочь, вывести на верную мысль?

P.S. Посмотрел в коде без стираний: там при превышении кол-ва ошибок степень полинома локаторов тоже перестает расти, но зато корней этого полинома всегда получается меньше, чем степень полинома. А в случае со стираниями оба корня все-таки находятся.

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

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

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

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

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

Да, точно. Спасибо!

Да, и никак невозможно будет определить то ли действительно это кодовое слово передавалось то ли ошибок слишком много и на самом деле другое слово передавалось.

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

Качество декодирования сообщений обычно определяется циклическим кодом с избыточностью (CRC). Правильный выбор полинома CRC позволяет свести к нулю вероятность пропуска сколь угодно ошибок в сообщении заданной длины. (В файловых системах тоже используется активно.)

Наверное к нулю всё же не позволяет, тем более при любом сигнал/шум.

И, к слову, исправлять две ошибки по Берлекемпу давно вышло из моды.
Используется прямое решение ключевого уравнения.
В принципе, и для трех ошибок это возможно, но уже заметно сложнее, так что легче
сделать Б-ма. А для двух ошибок - однозначно лучше прямое решение.

Асимптотически возможно, сам проверял, даже при низком С/Ш. В последнем случае велика вероятность, что как расчитанный полином по принятому сообщению, так и принятый CRC код будут иметь ошибки (много ошибок), и в случае независимых и одинаково распределенных ошибок вероятность их совпадения будет стремиться к нулю при увеличении длины кода. А несовпадение расчитанного с принятым CRC кодом говорит об ошибке декодировния сообщения.

Буду признателен, если кто-нибудь оценит скорость работы получившегося декодера.
Если брать код (40,36,2), то максимально декодер укладывается примерно в 4500 тактов (исправляя при этом две ошибки).
Это 125 такта на один информационный байт.

Результаты можно считать удовлетворительными?
Процессор - Мультикор NVCom.

Уточните, сколько на что тратится.

2900 - синдром, учитывающий ошибки и стирания
320 - синдром только ошибок
80 - полином локаторов
640 - определение корней
420 - определение ошибок и исправление

И еще, простаивание конвейера здесь неучтено, поскольку отладчик не позволяет это сделать.
Поэтому в действительности результат будет немного побольше.

Я проверяю, правильно ли декодер исправил ошибки, пересчетом синдрома исправленного пакета. Если 0, значит декодер отработал верно. Алгоритм Берлекама-Месси в большинстве случаев не отлавливает ситуацию с более, чем t ошибками.

Может, кто-нибудь подскажет поэлегантнее способ, чем пересчет синдрома? Реализуемый в аппаратуре способ...

А есть ли смысл это делать?
Если ошибки могут быть исправлены - они исправляются; если не могут - не исправляются.
Если случайно получилось так, что ошибки привели к допустимой кодовой комбинации - здесь ничего не поможет.

Да Например, в DVB-H приемнике мне нужно со 100%-й точностью знать, исправилось 8 ошибок или нет

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

Я повторюсь, но я пересчитываю синдром исправленного пакета, что позволяет отловить ситуацию, было ли больше 8 ошибок (что в подавляющем большинстве случаев не способен сделать алгоритм Берлекэмпа – Месси). В приемнике DVB-T/H действительно стоит декодер Витерби, но только перед декодером Рида-Соломона (следовательно, в передатчике наоборот). Т.о. Р-С отлавливает ошибки, которые не смог отловить Витерби. Вот только пересчет синдрома - это дополнительные N тактов работы декодера... Я в свое время нашел еще пару способов отловить проблемную ситуацию, но они не рациональны с точки зрения аппаратной реализации

Если я все же правильно Вас понял, напишу свои соображения.
В процессе декодирования Р-С по признакам, которые обсуждались в этой теме выше, можно определить, не превышает ли количество ошибок корректирующую способность кода. То есть, если вы сами делаете декодер, то ситуацию с большим кол-вом ошибок можно отловить в процессе декодирования, а дополнительная проверка исправленного кода по новому синдрому - это лишняя работа. А вот что действительно важно в описанном случае, причем проверка синдрома не поможет - это такая комбинация ошибок, когда информационные и проверочные символы случайно искажаются "согласованно" и полученное искаженное кодовое слово никак не отличается от правильной комбинации. В этом случае, кстати полезно использовать предложенный способ:

То есть в информацию можно дополнительно вставлять CRC. В итоге получается тройная вложенная схема: сверточный код - Рид-Соломон - CRC.

Видимо, вы не совсем точно представляете ситуацию. Я делаю приемник DVB-T/H, это означает, что я не могу ничего (например, CRC) вставлять в принятые пакеты. Я также не могу измерить точно сигнал/шум - только приблизительно и до Витерби. И мне все равно нельзя выключать приемник, если бы даже этот сигнал/шум был ниже какого-то предела. Мне просто нужно помечать абсолютно каждый пакет как корректный или нет. Поэтому все предложенные выше методы, в т.ч. с пом. алгоритма Берлекэмпа-Месси и по количеству локаторов (процедура Ченя) не подходят.
Так что пересчет синдрома - это не лишняя работа, а пока что единственный приемлемый способ, который я знаю, для необходимой мне проверки. А насчет "согласованного искажения" - мне кажется, что в моем случае RS(204, 188, 8) это практически невозможная ситуация.
Тем не менее, спасибо за участие и желание помочь

Это заблуждение, всё зависит от сигнал/шум.