5.3. Методы декодирования кодов БЧХ

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

Декодер получает, ьонечно, только и его задачей является нахождение вектора с минимальным весом Хемминга, который может привести к наблюдаемому вектору Этот вектор должен быть выбран из множества 2 возможных кандидатов (по одному для каждого с). Существует ряд методов декодирования как во временной, так и частотной области. В стандартных методах декодирование обычно осуществляется во временной области. Однако в последнее время было предложено несколько подходов к

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

5.3.1. Декодирование в частотной области

Для декодирования в частотной области вначале нужно вычислить преобразования Фурье принятого вектора Это преобразование выражается через преобразования кодового вектора и вектора ошибки:

Из определения кода БЧХ ясно, что преобразование С каждого кодового слова содержит последовательных нулей. Таким образом, из (5.11) можно получить известных значений Обычно они называются синдромами и обозначаются т. е.

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

Предположим теперь, что число ошибок Определим многочлен локаторов ошибок формулой (5.6), где индексы соответствуют положениям ошибок при Тогда во временной области при так что для всех и

(заметим, что при Система уравнений (5.13) является «ключом» решения задачи декодирования и обычно называется ключевым уравнением. Поскольку 21 последовательных компонентов известны, то из уравнений (5.13) можно получить уравнений для неизвестных коэффициентов Эти уравнения являются линейными, и решать их можно с помощью обычной техники обращения матриц. Их можно также решить, используя одну из итерационных процедур, которые будут приведены в разд. 5.4. После того как многочлен найден, неизвестные компоненты можно найти из (5.13). Наконец, после нахождения обратное преобразование Фурье дает оценку комбинации ошибок и выходной вектор декодера

Рис. 5.1. Декодер для декодирования кодов БЧХ в частотной области

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

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

Начальное преобразование Фурье, определяющее синдромы, может быть просто реализовано. Заметим, что 21 символов синдрома для кода, порождающий многочлен которого имеет корни определяются по формуле

Записывая символ синдрома в виде

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

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

Рис. 5.2. Схема устройства для вычисления

Рис. 5.3. Регистр сдвига с обратными связями для реккурентного продолжения преобразования Фурье вектора ошибок

требуют сравнительно длительных объяснений, так что их изложение отложено до разд. 5.4.

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

Заключительное обратное преобразование Фурье может быть вычислено по схеме, аналогичной изображенной на рис. 5.2, в которой, однако, содержится не 21, а подобных устройств. Вообще говоря, декодер БЧХ, работающий в частотной области, не менее сложен, чем декодер, работающий во временной области, что объясняется сложностью устройства, осуществляющего заключительное обратное преобразование Фурье. В некоторых случаях сложность этого последнего устройства можно существенно уменьшить, используя методы быстрого преобразования Фурье (БПФ). Для того чтобы БПФ можно было применять, нужно выбирать коды, обладающие некоторыми специальными свойствами. Недавние исследования показали, что при этом объем вычислений становится меньшим, чем при декодировании во временной области.

5.3.2. Декодирование во временной области

Декодирование во временной области применялось шире, чем декодирование в частотной области. Однако во многих отношениях эти два метода очень похожи. Структурная схема декодера, работающего во временной области, показана на рис. 5.4. Аналогично декодеру, изображенному на рис. 5.1, здесь имеются устройство для вычисления преобразования (задающее синдром), буфер (для хранения ) и устройство для решения ключевого уравнения, находящее многочлен локаторов ошибок Декодер во временной области осуществляет также вычисление многочлена значений ошибок (для недвоичных кодов), который порождается одновременно с решением ключевого уравнения. Устройство, осуществляющее «процедуру Ченя», находит положение ошибэк для известного многочлена (находя величины, обратные корням). Для нахождения в двоичном случае больше ничего не нужно. Однако при недвоичном кодировании следует еще найти величины

Рис. 5.4. Декодер для декодирования кодов БЧХ во временной области

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

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

Определив многочлен локаторов ошибок по формуле (5.6), произведение можно записать в виде

Многочлен как раз является многочленом значений ошибок, о котором говорилось ранее. Заметим, что если степень многочлена локаторов ошибок равна то степень многочлена значений ошибок меньше

Фактически известно лишь вплоть до коэффициента при так что через известные компоненты синдрома равенство (5.19) можно записать в виде

Равенство (5.20) определяет в точности то же множество уравнений, что и (5.13), и в дальнейшем также будет называться

ключевым уравнением. Причина этого становится ясной, если заметить, что степень не превышает поэтому из (5.20) вытекает равенство

где -члены со степенями от до (т. е. ). После нахождения многочлен можно определить по формуле (5.20).

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

Положим

так что

Тогда

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

Рис. 5.5. Блок-схема процедуры Ченя для нахождения положения ошибок

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

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

Аналогично, беря значение формальной производной в той же точке получаем

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

В наиболее часто встречающемся случае, это выражение имеет вид

Вычисления согласно (5.28) почти аналогичны вычислениям, проводимым для процедуре Ченя, и для вычисления можно использовать схемы на рис. 5.5. Затем можно вычислить значение ошибки с помощью схемы, изображенной на рис. 5.6. Фактически вычисление для некоторых кодов оказывается проще вычисления функции в процедуре Ченя (см. рис. 5.5). Для кодов, определенных над полем характеристики 2, коэффициенты при нечетных степенях 2 обращаются в 0, так что имеет вид

Рис. 5.6. Блок-схема вычисления значений ошибок