7.2. Алгоритмы БПФ с вещественными весовыми коэффициентами

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

В связи с этим представляет определенный интерес построение алгоритмов БПФ с весовыми коэффициентами из поля вещественных чисел. Как будет показано ниже, алгоритмы БПФ данного класса имеют более сложные структуры, однако являются более эффективными (по числу арифметических операций) в сравнении с алгоритмами БПФ по основаниям 2, 4, 8, 16 и требуют значительно меньший объем коэффициентов (порядка вещественных слов). Кроме того, данные алгоритмы наиболее адаптированы в случае обработки вещественной входной последовательности.

Пусть тогда матрица ДПФ согласно (3.3) может быть факторизована в виде (транспонированная форма)

где

Представим матрицу в виде где Приведенное соотношение для получается из тригонометрического тождества

Тогда

так как по теореме сдвига где Кроме того, из (7.4) следует, что элементы вектора являются нечетными элементами входного вектора т.е.

Операцию можно представить в матричном виде

Подставляя полученное соотношение в (7.4), получаем

где

В случае, если матрица факторизуется аналогично. Окончательно в случае получаем

Алгоритм впервые предложен Рейдером и Бреннером [4]. Различные варианты синтеза алгоритма Рейдера-Бреннера приведены в Число нетривиальных вещественных операций алгоритма равно (табл. 7.1)

Согласно (7.7) алгоритм требует меньше умножений, чем любой из алгоритмов БПФ по основаниям 2, 4, 8, 16. Кроме того, как было сказано выше, алгоритм требует меньший объем ПЗУ коэффициентов.

На рис. 7.6 приведен граф первой части алгоритма

Вторая часть по структуре аналогична алгоритму БПФ, приведенному на рис. 7.2 с учетом замены коэффициентов на

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

В [8] Чу и Темес предложили модификацию алгоритма свободную от указанного недостатка. В предложенном ими алгоритме коэффициенты типа заменены на Матричная интерпретация одного из вариантов таких алгоритмов БПФ имеет вид

Рис. 7,6. Предварительные этапы взвешивания в алгоритме БПФ типа Рейдера-Бреннера

В матрице коэффициент За счет этого необходимо отдельно вычислять составляющие спектра

При дальнейшей факторизации по аналогии с (7.8) для и т.д. приводят к алгоритму, по структуре подобному (7.6) с учетом замены матриц на на

Число нетривиальных арифметических операций для данного алгоритма равно (табл. 7.1)

т.е. алгоритм Чу-Темеса имеет несколько худшие показатели вычислительной эффективности.

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

Приведем пример определения матриц

При указанном представлении матрица факторизуется в виде, аналогичном (7.5) или (7.8), причем для приведенных матриц типа (7.9) весовые коэффициенты соответственно равны

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

где Далее

Рис. 7.7. Алгоритм Тыртышникова

не разбивается на две матрицы как в алгоритмах БПФ по основанию 2, а факторизуется целиком как матрица сдвинутого ДПФ [10]

где в общем случае

(матрица определена в (7.6)).

Продолжая далее аналогичную факторизацию для матриц получаем окончательное выражение для где

Подставляя (7.12) в и проводя аналогичную факторизацию для получаем полное выражение для

На рис. 7.7 приведен пример реализации алгоритма для случая Число нетривиальных вещественных операций равно (табл. 7.1)

Согласно (7.14) алгоритм (7.13) имеет меньше сложений, чем алгоритм