4.7. Объем вычислений и памяти

Объем вычислений. Из (4.1.1) следует, что можно вычислить в результате умножения .матрицы размером , составленной из степеней W, на -мерный вектор исходных данных. Число арифметических операций (т. е. комплексных умножений с последующим сложением или вычитанием) в этом случае примерно . Такой метод вычисления коэффициентов ДПФ будем называть «прямым методом». Использование БПФ приводит к итерациям, и общее число требуемых арифметических операций станет равным примерно .

Из приведенных выше рассуждений видно, что общее число арифметических операций, требуемых для вычислений по прямому методу и по алгоритму БПФ, пропорционально и N соответственно. Следовательно, по мере возрастания N повышается экономичность БПФ по сравнению с прямым методом. Это видно из рис. 4.6, на котором и — время выполнения вычислений по прямому методу и по алгоритму БПФ соответственно. Из рис. 4.6 получаем, что и , откуда следует, что и примерно пропорциональны и N соответственно.

Приведенное время вычислений было получено на ЭВМ с -разрядной сеткой (NOVA 1200) и при программировании на языке BASIC. Вычисление всех 8192 коэффициентов ДПФ с помощью БПФ на ЭВМ занимает 5 с, а прямым методом — 0,5 ч [1].

Рис. 4.6. Сравнение времени при прямом вычислении ДПФ и при вычислении с помощью алгоритма БПФ

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

Ошибки округления. Алгоритм БПФ значительно уменьшает ошибку округления, связанную с арифметическими операциями. По сравнению с прямым методом алгоритм БПФ снижает ошибку округления в раз [1, 9].