7.4. Вычисление ДПФ

В разд. 7.2.3 (было показано, что ДПФ и ОДПФ могут быть вычислены с помощью одного алгоритма. Таким образом, имея схему вычисления одного из преобразований, второе можно вычислить, прибегая лишь к простой перетасовке данных. Следовательно, достаточно рассмотреть построение основной схемы вычислений

Для оценки ДПФ на оснований этого алгоритма необходимо заменить переменные следующим образом. На входё следует положить

и на выходе

Чтобы использовать этот же алгоритм для выполнения ОДПФ, обрабатываемые данные должны быть перетасованы следующим образом:

и для получения заданной последовательности во временной области нужно сделать замену

Нетрудно, конечно, получить схему вычислений, позволяющую найти значений ; по N значениям а в соответствии с формулой (7.16). Пример такой структурной схемы показан на

Фиг. 7.9. Блок-схема непосредственного вычисления ДПФ.

фиг. 7.9. Составить соответствующую программу по этой структурной схеме настолько просто, что факт многократного повторения одинаковых операций остается незамеченным. Эти «лишние» операции появляются по следующим причинам. В выражение (7.16) входят произведения общего вида

Весовая функция является периодической с периодом Для заданного при изменении от нуля до произведение также будет меняться «периодически, причем число этих периодов равно к. Более того, даже в пределах одного периода произведения могут образовывать комплексно-сопряженные пары. Следовательно, табулируя промежуточные результаты, можно существенно уменьшить число умножений, необходимых для вычисления значений последовательности А (я).

Алгоритмы, позволяющие достигнуть этого сокращения вычислительной нагрузки, известны под общим названием «быстрое преобразование Фурье» Следует подчеркнуть, что это не «новое» преобразование, а всего лишь способ выполнения ДПФ.

Еще одно более незначительное увеличение эффективности алгоритма может быть достигнуто в том случае, когда обрабатываемые данные являются действительными величинами. Это обусловлено тем, что ДПФ действительных чисел обладает комплексно-сопряженной симметрией. Следовательно, достаточно вычислять лишь одну половину спектра. Подробно этот вопрос рассматривается в разд. 7.9.

ДПФ применяется в настоящее время столь широко [2], что, кроме универсальных ЦВМ, для его выполнения используются специально разработанные цифровые устройства. Они делятся обычно на две категории: это либо периферийное устройство для выполнения БПФ, соединенное с универсальной ЦВМ, либо специализированная ЦВМ для обработки и анализа в частотной области. Эта техника достаточно хорошо разработана; в статье [3] перечислено около 200 машин, которые могут выполнять БПФ.

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