10.5. Декодирование более чем t ошибок

Хотя алгоритмы 10.33 и 10.48 могут быть применены для исправления некоторых конфигураций искажений, приводящих иногда к отказу от декодирования, мы в этом разделе ограничимся лишь случаем простейшего алгоритма 10.15. Читатель, желающий распространить результаты этого раздела на БЧХ-коды общего типа и найти алгоритмы совместного декодирования стираний и ошибок, может осуществить это непосредственно, хотя такая процедура будет весьма скучной и приведет к более слабым результатам.

Если в слове -ичного БЧХ-кода с исправлением ошибок будет искажено не более символов, то алгоритм 10.15 позволит правильно локализовать и исправить эти ошибки. Шаг 10.152 этого алгоритма завершается определением с помощью алгоритма 7.4 многочлена локаторов и многочлена значений ошибок. В этом случае многочлен имеет различных взаимных корней, являющихся корнями степени из единицы. Декодер определяет эти взаимные корни на шаге 10.153 рассматриваемой процедуры декодирования. На шаге 10.154 декодер находит

Если произошло не более ошибок, то каждое задает величину ошибки с локатором X

Если же произошло больше чем ошибок, то возможны многие другие исходы. Возможно (хотя и очень маловероятно), что алгоритм 7.4 завершится вычислением правильных многочлена локаторов и многочлена значений ошибок, хотя Возможно также, что алгоритм 7.4 завершится допустимым многочленом локаторов ошибок и допустимым многочленом значений ошибок, соответствующими некоторому вектору ошибок с весом В этих случаях декодер без труда завершает шаги 10.153 и 10.154 процедуры декодирования и неправильно «исправляет» происшедшие по его мнению ошибки Хотя в этой ситуации декодер ошибается, порицать его за эту ошибку нельзя, так как для полученного слова неправильно найденный вектор ошибок является более вероятным, чем фактический вектор ошибок с большим весом.

Более вероятными, чем рассмотренные ситуации, являются другие две возможности, приводящие к отказу от декодирования на шаге 10.153 или шаге 10.154. Алгоритм 7 4 может завершиться недопустимым многочленом не имеющим различных корней — корней степени из единицы В этом случае на шаге 10.153 происходит отказ от декодирования Но даже если все корпи различные корни степени из единицы, то многочлен может быть недопустимым хотя величины вычисляемые декодером на шаге 10.154, должны лежать в поле локаторов, содержащем корни степени из единицы над они могут не лежать в символов . В случаях подобных отказов от декодирования (на шаге 10 153 или 10 154) декодер обнаруживает искажение более чем символов

Во многих случаях декодер может обнаружить недопустимость многочленов с помощью предварительных вычислений сразу после шага 10 152 и, таким образом, избежать сравнительно машинных вычислений в процедуре Ченя на шаге 10.153 Например, то не может быть допустимым многочленом юкаторов не -удлиненного БЧХ-кода. Хотя это свойство позволяет обнаружить очень малую часть возможных недопустимых многочленов зато оно требует никаких дополнительных вычислений

В качестве второго «теста допустимости» декодер может использовать четность числа неприводимых делителей многочлена над (см теоремы 6.68 или 6.69 и 6 695) Если число неприводимых делителей многочлена не сравнимо с по то недопустим Эвристически можно полагать, что недопустимый

многочлен локаторов ошибок равновероятно может иметь как четное, так и нечетное число неприводимых делителей. Поэтому правило проверки допустимости, основанное на теореме Щтикельбергера, позволяет распознать примерно половину из недопустимых многочленов локаторов ошибок. Для двоичных БЧХ-кодов с это утверждение действительно справедливо; а для частного случая двоичных БЧХ-кодов с исправлением двух ошибок слабая модификация этого теста допустимости позволяет распознать все недопустимые многочлены локаторов ошибок и приводит к полному алгоритму декодирования по максимуму правдоподобия (алгоритм 16.481).

В качестве третьего теста допустимости декодер может использовать классы вычетов Умножая соответствующие комбинации этих классов, декодер может определить класс вычетов для некоторого Рассматриваемый многочлен локаторов ошибок допустим тогда и только тогда, когда Хотя это правило проверки допустимости пригодно для всех недопустимых многочленов локаторов ошибок, оно не позволяет определить недопустимость многочлена значений ошибок, в результате чего на шаге 10.486 декодер определит «значения ошибок», лежащие в

Для определения допустимости обоих многочленов и для введения корректирующих мер в случае недопустимости любого из них введем между шагами 10.152 и 10.153 алгоритма декодирования 10.15 дополнительный шаг.

10.1525. Дополнительный шаг. Вычислить производящую функцию определенную равенством

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

Если многочлен допустим, то где - различные корни степени из единицы, и делит В этом случае

и

Если то для Обратно, если для то для всех к, так как

(доказательство индукцией по Так как для всех 0, то где Следовательно,

или Значит, делит Согласно теоремам 7.42 и 7.411, многочлены взаимно просты. Следовательно, делит Мы доказали следующую теорему:

10.53. Теорема. Взаимные корни многочлена являются различными корнями степени из единицы тогда и только тогда, когда для

Таким образом, успех или отказ на шаге 10.153 можно предвосхитить с помощью анализа некоторых коэффициентов функции на шаге 10.1525. Проводя дальнейший анализ этих коэффициентов, можно предвосхитить успех или отказ процедуры декодирования на шаге 10.154.

10.54. Теорема. Если различны и

то

тогда и только тогда, когда

Доказательство. Если то разложение в ряд дроби имеет вид

где

и для всех

В поле, содержащем также справедливо равенство

Если , то для всех

Обратно, если то для выполняются оба условия

Единственное решение первой системы линейных уравнений имеет вид

где определяется условиями и

Единственное решение второй (идентичной) системы уравнений имеет аналогичный вид с заменой У, на для

Теоремы 10.53 и 10.54 показывают, что вычисление функции позволяет предсказать успех или отказ от процедуры

декодирования на шагах 10.153 и 10.154. Так как успех шага 10.153 нельзя гарантировать до вычисления коэффициентов то необходимо оценить время, требующееся для их вычисления. На самом деле для вычисления нужных коэффициентов требуется примерно такая же работа, как и для отыскания с помощью процедуры Ченя соответствующих корней степени из единицы. В этом смысле использование процедуры Ченя на шаге 10.153 дает всего дополнительных вычислений. Однако правило 10.1525 обладает двумя важными преимуществами:

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

(2) Иногда удается использовать дополнительные корректирующие соображения.

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

В общем случае введем следующее обозначение:

10.55. Определение.

(Заметим, что первый коэффициент совпадает с величиной определенной в алгоритме 7.4.) Полагая

получим, что

В поло характеристики

Это тождество приводит к следующему утверладению:

10.56. Теорема

В частном случае Отсюда получаем, что

и

так что