10.6. Особенности аппаратурной реализации БПФ с основанием 2

Перейдем теперь к вопросам аппаратурной реализации БПФ. Следует отметить, что между быстродействием и гибкостью устройства существует известное противоречие. То, что вычислительная машина А может выполнить БПФ в 10 раз быстрее вычислительной машины В, вовсе не означает, что она лучше, так как повышение скорости выполнения БПФ путем специализации структуры машины может привести к уменьшению скорости выполнения других алгоритмов, а общие характеристики машины при этом значительно ухудшаются. Рассмотрим в качестве примера блок- схему устройства, предназначенного для выполнения алгоритмов с основанием 2, и будем пока считать, что оно содержит не более одного ЗУ с произвольным доступом и одного арифметического устройства (АУ), а также устройство управления (фиг. 10.18).

Фиг. 10.18. Упрощенная блок-схема устройства БПФ.

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

1. Комплексная форма записи

             прореживание  по  времени;                     (10.20)

            прореживание  по  частоте.                     (10.21)

Отметим, что формулы (10.20) совпадают с (10.4) и приведены здесь для удобства.

2.. Упрощенная комплексная форма

Чтобы показать последовательность выполнения алгоритма БПФ на вычислительной машине, избавимся в формулах (10.20) и (10.21) от различных индексов. Введем обозначения

Тогда соотношения (10.20) и (10.21) можно записать в виде

         прореживание по времени;                                          (10.22)

 прореживание по частоте                                                  (10.23)

3. Действительная форма

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

     прореживание по времени;          (10.24)

 прореживание по частоте.         (10.25)

Исходя ив блок-схемы фиг. 10.18 и приведенных формул, например из формулы (10.24), можно определить число машинных циклов, необходимых для выполнения базовой операции БПФ с прореживанием по времени. Предположим, что одно слово, хранящееся в ЗУ, содержит только действительную (или мнимую) часть комплексного числа, а в АУ имеется только один умножитель и один сумматор действительных чисел. Тогда для расчетов по формулам (10.24) потребуются шесть циклов обращения к ЗУ для вызова  и  и  и еще четыре цикла для записи результатов . Кроме того, нужно будет выполнить четыре умножения и шесть сложений (или вычитаний). В число дополнительных операций, не фигурирующих в формулах типа (10.24), входят в основном вспомогательные циклы обращения к ЗУ и действия над адресами. Так как эти операции тесно связаны со структурой ЦВМ, то в данном разделе они рассматриваться не будут. Отметим, между прочим, что с вычислительной точки  зрения  нет принципиального различия между вариантами БПФ с прореживанием по частоте и по времени.

Теперь можно перейти к более сложной модификации основной блок-схемы. Представим себе ЦВМ, в которой каждое слово состоит из двух частей, причем одна из них используется для хранения действительной части комплексного числа, а другая — для хранения мнимой части того же числа. Представим также, что в АУ имеются два умножителя и два сумматора. Тогда при соответствующем управлении число машинных циклов можно сократить вдвое.

Если ЦВМ позволяет за один машинный цикл обрабатывать комплексное число, то полное число циклов можно сократить еще больше. Из формул (10.22), (10.23) видно, что нужно выполнить всего два комплексных сложения и одно комплексное умножение. Три возможных варианта блок-схемы, приведенной на фиг. 10.18, сопоставлены в табл. 10.1. В последнем столбце приводится суммарное число циклов, причем циклам обращения к ЗУ и циклам сложения придается единичный вес, а циклам умножения — тройной.

Таблица 10.1