Главная > Разное > Методы синтеза быстрых алгоритмов свертки и спектрального анализа сигналов
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

11.4. Алгоритмы ТЧП типа Рейдера-Бреннера

Как было показано в предыдущих двух разделах, возможно построение ТЧП в поле простое Мерсенна) размерностью Для такого ТЧП были синтезированы быстрые алгоритмы. Однако данные алгоритмы используют комплексную арифметику в конечном поле. Для алгоритмов БПФ Рейдер и Бреннер [7] предложили другой класс алгоритмов, использующих чисто вещественные или чисто мнимые коэффициенты. Основным недостатком таких алгоритмов является чрезвычайная чувствительность вычислений к погрешностям квантования весовых коэффициентов. Для теоретико-числовых конструкций данный недостаток полностью отпадает, так как все вычисления выполняются точно. Следовательно, метод Рейдера-Бреннера целесообразно распространить на соответствующие структуры ТЧП.

Итак, пусть задана пара ТЧП (11.18) в комплексном конечном поле Сформируем из входной последовательности две новых

Пусть спектры ТЧП размерности соответственно от и Тогда можно показать [8], что

Для того, что (11.28) совпадала со структурой Рейдера-Бреннера, необходимо, чтобы коэффициенты были чисто вещественными или чисто мнимыми. Определим условия, которые необходимы для этого.

Пусть Тогда из условия получаем систему уравнений

решение которой дает

где

Рис. 11.5. Граф алгоритма БПФ типа Рейдера-Бреннера для ТЧП в

Из (11.29) следует, что коэффициент будет чисто вещественным или чисто мнимым, если

Пусть в задан элемент степени которого образуют мультипликативную группу Элементы могут быть выбраны, например согласно (11.19). доказано следующее свойство:

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

Таким образом, для корней где выбираются согласно (11.19), структура типа Рейдера-Бреннера может быть построена согласно (11.28).

Рассмотрим пример. Пусть Тогда для получаем следующие численные значения: На рис. 11.5 изображен граф ТПЧ Рейдера-Бреннера для таких значений

Число арифметических операций для данного алгоритма ТПЧ определяется с учетом того, что умножения на тривиальные, и, кроме того, умножения на считаются как циклический сдвиг Тогда

<< Предыдущий параграф Следующий параграф >>
Оглавление