9.6. ДЕКОДИРОВАНИЕ ЗА ГРАНИЦЕЙ БЧХ

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

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

Согласно теореме 8.2.1, принадлежность всех компонентов конфигурации ошибок полю можно распознать, проверив выполнение условия для всех индексов в спектре этой конфигурации. Если такая проверка указывает на неисправляемую конфигурацию, то вычисления прерываются. Требование, состоящее в том, что степень многочлена равна числу корней многочлена в поле можно проверить с помощью условия периодичности последовательности коэффициентов для всех Таким образом получается второе правило проверки для обнаружения неисправляемой конфигурации ошибок и прекращения декодирования. Это правило основывается на следующей теореме.

Теорема 9.6.1. Предположим, что является ненулевым многочленом наименьшей степени, удовлетворяющим условию а

для Число различных корней многочлена в поле равно степени этого многочлена тогда и только тогда, когда для всех

Доказательство. Предположим, что число различных корней многочлена в поле равно его степени. Тогда делит и существует многочлен такой, что Следовательно, так как

то выполняется равенство таким образом, Отсюда вытекает, что для всех

Обратно, предположим, что для всех Тогда Но по условию представляет собой такой ненулевой многочлен наименьшей степени, что Согласно алгоритму деления

так что

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

Если нарушается хотя бы одно из двух условий, т. е. если для некоторого или Для некоторой) то обнаруживается конфигурация более чем из ошибок.

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

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

1. Двоичные коды БЧХ, у которых проверочные частоты образуют блок длины , но истинное минимальпое расстояние превосходит (Одним из примеров такого кода является код Голея. Другой пример дается (127, 43, 31)-кодом БЧХ, конструктивное расстояние которого равно только 29.)

2. Циклический код, проверочные частоты которого не образуют непрерывного блока.

3. Декодирование некоторых ошибок веса в коде Рида—Соломона или коде БЧХ, исправляющем ошибок.

4. Декодер для альтернантных кодов.

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

Начнем с рассмотрения кода Рида-Соломона над с конструктивным расстоянием Произвольный многочлен степени различными корнями в представляет собой допустимый многочлен локаторов ошибок, если

Такой многочлен наименьшей степени с (если он является единственным) соответствует кодовому слову, находящемуся на наименьшем расстоянии от принятого слова. Если степень этого многочлена не выше то он будет вычислеп алгоритмом Берлекэмпа-Месси. Но даже если произошло больше, чем ошибок, а многочлен наименьшей степени с указанными свойствами является единственным, то принятое слово может быть однозначно декодировано, коль скоро этот многочлен найден. Для кода Рида—Соломона нет необходимости вычислять величины ошибок, так как ошибки всегда лежат в поле Если многочлен наименьшей степени не является единственным, то имеется несколько возможных конфигураций ошибок одного и того же веса, и все они согласуются с принятым словом.

Предположим, что произошло ошибок; тогда, чтобы вычислить достаточно найти две веизвестные компоненты синдрома или две невязки Итак, продолжим аналитически алгоритм Берлекэмпа-Месси на две итерации с двумя неизвестными значениями невязки. Имеем

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

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

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

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

образом. Одним из возможных подходов является построение гистограммы. Например, для уравнения (2) при каждом значении построим гистограмму величины Любая составляющая гистограммы, принимающая значение соответствует возможной конфигурации из ошибок.

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

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

Предположим, что у нас имеется двоичный код БЧХ с конструктивным расстоянием и мы хотим исправлять все однозначно декодируемые конфигурации веса Единственными величинами, которые может измерять декодер, являются компонент синдрома Во всех остальных частотах стоят либо произвольные значения, либо значения, определяемые условиями сопряженности. Итеративный алгоритм в двоичном случае дает

Во временной области он переписывается в виде

и предполагается, что конфигурация ошибок веса или менее не была найдена алгоритмом.

Построим гистограмму величины но всем ненулевым элементам поля Каждая равная компонента этой гистограммы соответствует кандидату на роль конфигурации ошибок. Зная локаторы ошибок, вычислим эту конфигурацию. Если она двоична и единственна, то декодирование завершено успешно.

Рассмотрим двлее двоичный код, у которого проверочные частоты не являются последовательными. Например, проверочными частотами двоичного циклического -кода являются Как можно проверить на ЭВМ, минимальное расстояние кода равно 15. По сравнению с -кодом БЧХ этот код обладает тем преимуществом, что обеспечивает бблыпую скорость, но зато для кода БЧХ известен алгоритм декодирования. Однако ценой незначительного усложнения частотный декодер для кода БЧХ удается

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