D704 Complex Fast Fourier Transform

Subroutine CFFT computes the finite Fourier transform of a complex periodic sequence, whose period n must be a power of 2. The expressions which may be computed are either the forward transform $A$_m = ∑ _k=0^n-1a_kexp( {-i 2πkmn}),(m=0,1,...,n-1),

or the unscaled inverse transform $\alpha$_k = ∑ _m=0^n-1A_mexp( {i 2πmkn}),(k=0,1,...,n-1),

where $a$_k and $A$_m are complex numbers. If the $A$_m in (2) have the values defined by (1), then $a$_k=α_k/n, (k=0,1,...,n-1) . To ensure optimum use of storage, the same array is used for input and output, and all intermediate calculations are carried out in this array.

Structure:

SUBROUTINE subprogram
User Entry Names: CFFT

Usage:

    CALL CFFT(A,M)

A

( COMPLEX) Array of length not less than n.

M

( INTEGER) On entry, the absolute value of M determines the value of n through the relation $n=2|M|$ . If M is negative, expression (1) is evaluated. If M is non-negative, expression (2) is evaluated. Unchanged on exit.

On entry, $A(k+1)=a$_k, (k=0,1,...,n-1) .
On exit, $A(m+1)=A$_m, (m=0,1,...,n-1) , as defined by (1).
$M\ge 0:$
On entry, $A(m+1)=A$_m, (m=0,1,...,n-1) .
On exit, $A(k+1)=a$_k, (k=0,1,...,n-1) , as defined by (2).

Method:

The method is based on an algorithm of Cooley, Lewis and Welch (see References), with the following modifications which reduce the overhead time for small values of M: multiplications by $exp(im\pi )$

are replaced by addition or subtraction, and terms of the form $exp(i2\pi /m),(m=2,4,...,n)$ , are computed recursively using only square roots and divisions.

References:

1. G. Dahlquist and Å. Björck, Numerical methods (Prentice-Hall, Englewood Cliffs, 1974) 416.
2. L.R. Rabiner and B. Gold, Theory and application of digital signal processing (Prentice-Hall, Englewood Cliffs, 1975) 332.

Interpolation, Approximations, Linear Fitting

E100