9.5. ДЕКОДИРОВАНИЕ ВО ВРЕМЕННОЙ ОБЛАСТИ

В § 9.1 было показано, что задача декодирования кодов БЧХ может быть сформулирована как задача спектрального оценивания. Декодер состоит из преобразователя Фурье (вычислителя синдрома), авторегресснонного спектрального анализатора

(алгоритма Берлекэмпа Месси) и обратного преобразователя Фурье. Задание декодера такими блоками облегчает его исследование, однако практическая реализация декодера может существенно отличаться от этой схемы.

В настоящем параграфе мы покажем, как преобразовать" вычислительный алгоритм, чтобы избежать преобразования потока данных. Это позволит исключить из декодера оба преобразования Фурье. Главная идея такого преобразования основывается на том, что рекурсия в алгоритме Берлекэмпа-Месси линейна но обоим входным многочленам (хотя нелинейна но невязке). Во временной области рекуррентные уравнения имеют свои аналоги, которые можно найти аналитически с помощью преобразования Фурье. Это дает систему уравнений декодирования, связывающих непосредственно поступающие данные, и исправление ошибок производится без преобразований Фурье.

Чтобы исключить из вычислений преобразование Фурье, применим это преобразование ко веем величинам, входящим в формулировку теоремы 7.4.1. Преобразование вектора обозначающее вектор локаторов ошибок во временной области, обозначим через Преобразование вектора В обозначим соответственно через Алгоритм Берлекэмпа-Месси превращается во временной области в рекуррентный процесс, который описывается следующей теоремой

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

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

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

Рис. 9.6. Временной декодер для двоичного кода БЧХ.

формулировке теоремы 7.4.1, за исключением уравнения для невязки

в котором вместо вектора стоит вектор Но для для Следовательно,

и алгоритм во временной области формулируется аналогично теореме 7.4.1.

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

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

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

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

воспользоваться преобразованием Фурье, а нужна некоторая перестройка.

Теорема 9.5.2. Пусть принятое зашумленное слово кода БЧХ. При заданном во временной области векторе локаторов ошибок К решением множества рекуррентных уравнений

является

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

Так как для для выписанные выше уравнения эквивалентны следующим:

Эта эквивалентность и доказывает теорему.

На рис. 9.7 изображен временной декодер для нолей характеристики 2. Левая часть блок-схемы соответствует теореме 9.5.1, а правая — теореме 9.5.2. В процессе проведения итераций в левой части формируется преобразование Фурье многочлена локаторов ошибок. При каждой итерации в правой части принятое слово преобразуется таким образом, что одна компонента спектра принятого слова переходит в компоненту спектра вектора ошибок. Таким образом, после выполнения последней итерации принятое слово преобразуется в вектор ошибок.

Привлекательность декодера во временной области объясняется двумя причинами.

1. Вычисления проводятся в один этап, а процедура Ченя и рроцедура вычисления синдрома отсутствуют. Это приводит к более экономной конструкции, особенно при аппаратурной кеализации отдельных блоков декодера.

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

Рис. 9.7. (см. скан) Временной декодер.

использующий прямое преобразование Фурье и общепринятый алгоритм Берлекэмпа-Месси.

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

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