This module shows how padding a sequence to make it have length a
power of 2 affects the resulting DFT of the sequence. An
implementation of full mixed-radix FFT can compute the DFT of a
sequence of arbitrary length. The algorithm becomes less efficient,
though, when the sequence length has large prime factors. When the
sequence length is a prime number, FFT is no better than computing the
DFT by matrix multiplication, which takes
The user begins by choosing a number of basic mesh points n,
the length of the initial sequence. The user then selects whether
values for the basic mesh points will be taken from a source function
or generated randomly. When points come from a function, the user may
choose a specific function f from the menu provided; the point
values are
The upper graph shows the full sequence of 64 values with blue dots, and the lower graph shows (the first half of) the power spectrum of the DFT of that sequence with red dots. When mesh point values are taken from a source function, green dots in the upper graph show all 64 discrete samples from the function, and green dots in the lower graph show the power spectrum of the DFT of that sequence for comparison. The blue and red dots may obscure the green dots, particularly in the upper graph, where the first n point values always coincide.
The power spectrum of a sequence of complex values is computed by multiplying each value by its complex conjugate. For a sequence of real values, the power spectrum of the DFT is symmetric, so only the first half of the power spectrum need be displayed. The power spectrum represents the amount of energy present at each frequency. The tick labels on the horizontal axis show the wave numbers of selected frequencies; higher wave numbers correspond to higher frequencies. As the tick labels on the vertical axis suggest, the values of the power spectrum are shown on a log base 2 scale, with all values less than 2−6 lying on the horizontal axis.
Reference: Michael T. Heath, Scientific Computing, An Introductory Survey, 2nd edition, McGraw-Hill, New York, 2002. See Section 12.2.1 and Computer Problem 12.4 on page 509.
Developers: Evan VanderZee and Michael Heath