Добрый день!

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

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

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

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

Сообщение отредактировал andrex - Jun 8 2009, 11:17

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

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

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

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

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

Сообщение отредактировал SKov - Jun 8 2009, 12:43

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

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

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

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

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

Сообщение отредактировал petrov - Jun 8 2009, 13:38

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

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

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

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

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

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

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

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

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

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