Interactive Educational Modules in
Scientific Computing

Padding Sequences

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 O(n2). Since the FFT is most efficient for computing the DFT of sequences that have length 2k for some integer k, it makes sense to try adding extra values to a shorter sequence to make a new sequence that has length a power of 2. This module demonstrates several options for choosing the extra padding values that extend a short sequence.

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 f(0), f(1/64), f(2/64), …, f((n−1)/64). For randomly generated points, clicking Change Values generates a new set of point values, each in the range [−1.5, 1.5]. Last, the user selects the padding method that determines how extra values will be chosen to extend the basic sequence to a sequence of length 64. The Zeros method gives all additional points the value 0. The Constant Extension method gives all additional points the same value as the last point in the basic sequence. Linear to Zero chooses values from a linear interpolation between the last point value and 0. Linear Periodic uses instead a linear interpolation between the last point value and the first point value. For both options that involve linear interpolation, the right endpoint of the linear function is considered to be beyond the last point value of the sequence, at an imagined 65th point. Thus, the periodic option avoids an artificial constant interval of length 1/64 in the continuous linear interpolation of the values on the interval [0, 1].

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