ГЛАВА 9. АЛГОРИТМЫ, ОСНОВАННЫЕ НА СПЕКТРАЛЬНЫХ МЕТОДАХ

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

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

9.1. СПЕКТРАЛЬНЫЕ МЕТОДЫ ДЕКОДИРОВАНИЯ

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

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

информация. Координаты синдрома для зашумленного слова кода БЧХ задаются следующими равенствами:

Очевидно, что компоненты синдрома вычисляются как компонент преобразования Фурье принятого вектора. Компоненты преобразования Фурье зашумленного кодового слова равны компоненты синдрома представляют собой компонент этого спектра от до Но, согласно построению кодов БЧХ, спектральные компоненты, расположенные в проверочных частотах (при равны нулю: для Следовательно,

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

Предположим, что произошло ошибок с локаторами при Многочлен локаторов ошибок равен

Обратное преобразование Фурье вектора А вычисляется как значения многочлена в точках Ясно, что равно нулю тогда и только тогда, когда представляет собой позицию ошибки. Таким образом, определяется как такой многочлен, для которого во временной области при всех Следовательно, для всех таким образом, по теореме о свертке свертка в частотной области равна нулю:

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

Поскольку эти уравнения можно переписать в виде

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

содержит только известные компоненты синдрома и неизвестных компонент вектора Как мы видели в гл. 7, такую систему всегда можно разрешить относительно например с помощью алгоритма Берлекэмпа-Месси.

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

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

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

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

Рис. 9.1. (см. скан) Частотный декодер.

преобразованию Фурье. Процедура Ченя аналогична обратному преобразованию Фурье. Первая является -точечным преобразованием вектора с ненулевыми компонентами и -значным выходным вектором, а вторая представляет собой -точечное преобразование вектора с ненулевыми компонентами и значным выходом. Алгоритм Форни заменяется рекуррентным продолжением. Четвертая схема представляется более простой из-за простоты реализации отдельпых блоков декодера.

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

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

Рис. 9.2. (см. скан) Некоторые схемы кодера/декодера для кодов БЧХ.

также следующее упрощение: запишем принятый многочлен в виде

где порождающий многочлен кода БЧХ, а синдромный многочлен. Синдромный многочлен можно вычислить с помощью цени деления на Тогда

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

Существует и другой алгоритм декодирования, основанный на алгоритме Евклида и совершенно отличный от описанного в § 7.7. Этот метод, ориентированный на частотную область, будет онисан в данном параграфе.

В поле имеет место разложение

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

Теорема 9.1.1. Многочлен ошибок и многочлен локаторов удовлетворяют равенству

Доказательство. Многочлены и не имеют общих корней, так как по определению тогда и только тогда, когда Каждый элемент а должен быть корнем либо либо Следовательно,

для некоторого многочлена взаимно простого с Тогда

что и требовалось доказать.

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

то, согласно следствию 7.7.2,

определяет многочлен вычисляемый в процессе выполнения алгоритма Евклида.

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

Рассмотрим код БЧХ, корнями порождающего многочлена которого являются элементы (Если использовать в качестве примитивного элемента поля то это обычные корни с показателями от 1 до Построим алгоритм декодирования для такого кода БЧХ. Нам надо показать, что если произошло не более ошибок, то итерации алгоритма Евклида зависят только от старших коэффициентов многочлена Остальные коэффициенты могут выбираться произвольно.

Теорема 9.1.2. Пусть заданы для

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

разрешимо относительно степени или меньше.

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

условиям теоремы. Выпишем последний шаг алгоритма Евклида в форме, приведенной в доказательстве следствия 7.7.2:

Отсюда видно, что Вместе с тем в прямой форме последнее равенство имеет вид

что приводит к требованию

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

где В этом алгоритме степень частного равна он сам многочлен-частное зависит от только через коэффициенты Для

Рис. 9.3. (см. скан) Декодер для кодов БЧХ, основанный на алгоритме Евклида.

вычисления воспользуемся следующей итеративной процедурой при

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

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

до Эти старшие фрагменты многочленов являются именно теми многочленами, которые необходимы для выполнения итерационных шагов алгоритма Евклида при построении рассматриваемого ряда многочленов-частных. Так как

то можно записать

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

Этого диапазона достаточно для вычисления и продолжения итерации.