7.2. ДЕКОДЕР ПИТЕРСОНА ГОРЕНСТЕЙНА—ЦИРЛЕРА

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

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

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

где величина ошибки (в двоичном случае — 1). Мы не знаем ни ни в действительности мы даже не знаем числа Для исправления ошибок нужно вычислить все эти числа. Чтобы получить компоненту синдрома надо найти значения полученного многочлена в точке а:

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

В этих обозначениях запишется в виде

Аналогично можно вычислить значения принятого многочлена при всех степенях а, входящих в определение Для определим синдромы равенствами

Тогда получим следующую систему из уравнении относительно неизвестных локаторов неизвестных величин ошибок

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

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

Рассмотрим многочлен от х:

известный под названием многочлена локаторов ошибок и определяемый как многочлен, корнями которого являются обратные к локаторам ошибок величины для Итак,

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

Умножим обе части равенства, определяющего этот многочлен, на и положим Тогда левая часть обратится в нуль, и мы получим

или

Это равенство выполняется при каждом I и при каждом Просуммируем эти равенства по от 1 до Для каждого это дает

или

Каждая сумма в левой части последнего равенства является компонентой синдрома, так что уравнение приводится к виду

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

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

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

Теорема 7.2.1. Матрица Вандермопда, определяемая как произвольная матрица вида

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

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

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

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

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

Отсюда следует, что определитель исходной матрицы Вандермонда равен

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

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

Теорема 7.2.2. Матрица компонент синдрома

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

Доказательство. Пусть для и пусть А — матрица Вандермонда

с элементами диагональная матрица

с элементами где если в противном случае. Тогда произведение матриц будет иметь элементы

которые совпадают с элементами матрицы Таким образом, следовательно, определитель матрицы удовлетворяет соотношению

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

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

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

По теореме 7.2.1 определитель последней матрицы не равен нулю, если произошло ошибок, поскольку различны и не равны нулю.

Алгоритм декодирования представлен на рис. 7.1. Здесь мы предположили, что произвольно, хотя все рассуждения проводились для частного случая Рассуждения остаются теми же для произвольного

Рис. 7.1. (см. скан) Декодер Питерсона-Горепстейна-Цирлора.

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

Для вычисления по схеме Гор пер а требуется только умножений и сложений.

В качестве примера процедуры декодирования рассмотрим декодирование -кода БЧХ, исправляющего три ошибки и имеющего порождающий многочлен

Для примера будем считать принятый многочлен равным Ясно, что если бы произошло не более трех ошибок, то кодовое слово должно было бы быть нулевым и но декодер не может сделать такого заключения. Выполним все шаги алгоритма декодирования. Сначала вычислим компоненты синдрома, используя арифметику в поле :

Пусть тогда

Определитель равен нулю; следовательно, полагаем Тогда

Определитель не равен нулю; следовательно, произошло две ошибки. Далее,

и

следовательно,

Используя процедуру Ченя, получаем разложение

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