Loading LOADSUB ALL FROM "FFT.HTS"
or LOADSUB Cfft FROM "MATHLIB.HTS"
or LOADSUB FROM "MATHLIB.HTS"
Usage INTEGER Logn
COMPLEX A(*),C(*)
CALL Cfft(Logn,A(*),C(*))
Description
Cfft calculates the discrete Fourier transform of the sequence in the array A and stores the result in the array C. Logn is the base-2 log of the number of points in the sequences. The arrays A and C must contain at least 2Logn elements; if they have more than this number of elements, the extra elements are ignored and unmodified. The number of elements denoted by each permitted value of Logn is shown in the table below:
Logn No. Elements (2Logn)
2 4
3 8
4 16
5 32
6 64
7 128
8 256
9 512
10 1024
11 2048
12 4096
13 8192
14 16384
If the values in A are taken to be values of a continuous complex signal, a(t), sampled at constant intervals of T (time, distance, or whatever units apply), and if the signal sampled contained no terms at or above the frequency 1/2T, then the coefficients in the array C are the coefficients of the complex Fourier series that describes a(t). A(t) can be reconstructed from the elements of C through the following formula:
where
The first N/2 elements in the array C represent k = {0,1,...,N/2-1} and the last N/2 elements in C represent k = {-N/2,-(N/2-1),...,-1}.
If the signal a(t) contains components at or above the frequency 1/2T, the situation is complicated by aliasing, which is explained in most signal processing textbooks.
Some of the more common operations done using discrete Fourier transforms, such as convolution, correlation, and filtering, are available as separate CSUBs; see the entries for Autocorrelate, Convolve, Correlate, Filter, Rfilter, and Power_Spectrum for details on their use. The inverse of Cfft is computed by the Icfft subroutine. A discrete Fourier transform for real sequences is done by the Fft subroutine. Fft is approximately twice as fast as Cfft for a given real sequence and uses half the storage.
Errors
Cfft causes an HTBasic error if its arguments are not of the types shown in the USAGE section, above, if Logn is not between 2 and 15, inclusive, or if the size of A or C is smaller than 2Logn.
Examples
The manual entry for the Fft routine contains two examples that explain some of the uses and limitations of the discrete Fourier transform. Although the programs in the examples use the real discrete Fourier transform calculated by the Fft subroutine, the principles explained there are valid for the complex discrete Fourier transform also.
See Also
Convolve, Correlate, Fft, Filter, Icfft, Power_spectrum, Rfilter
Note
Some discrete Fourier transforms view the input array as a series of multipliers of Dirac delta operators. The values output from such transforms are the same as those output by Cfft except that each value is multiplied by N.
|