Performing Fast Fourier Transforms


Introduction

The calculator can be used for solving Fourier Transforms. Below is information on this process with the appropriate keystrokes to use.

Fast Fourier transforms

A physical process can be described in two distinct ways:
  • The change of a quantity, h, as a function of time t - h(t)
  • The change of an amplitude, H, as a function of frequency f - H(f)
For many situations, it helps to consider h(t) of H(f) as two different representations of the same function. Fourier transforms are used to switch between these representations, or domains.
The calculator can perform discrete Fourier transforms, whereby a sequence of discretely sampled data can be transformed into the "other" domain. The calculator performs "Fast" Fourier transforms, which make use of computational efficiencies that require the number of rows and number of columns in the sample are set to be an integral power of 2.
Fast Fourier transforms are most commonly used in analyzing one-dimensional signals or two-dimensional images. The calculator commands can handle both cases. In the first case the data should be entered as a vector of N elements, where N is an integral power of 2 (2, 4, 8, 16, 32, …). In the second case, the data should be entered as a matrix of M rows by N columns, where both M and N are integral powers of 2.
The "forward" transformation (FFT) maps an array of MxN real or complex numbers (hk) in the time domain to an array of MxN real or complex numbers (Hn) in the frequency domain (see Figure 1):
Figure 1: Forward Transformation (FFT)
The "inverse" transformation (IFFT) maps an array of MxN real or complex numbers (Hn) in the frequency domain to an array of MxN real or complex numbers (hk) in the time domain (see Figure 2):
Figure 2: Inverse Transformation (IFFT)

Preparing an array for Fast Fourier transforms

  1. Put the array of the data on the stack.
  2. If necessary, add zeros to the array so that all dimensions are equal to an integral power of 2.

Using a Fast Fourier transform

  1. Enter the array of data to be transformed (or its name) onto the stack. Make sure its dimensions are integral powers of 2.
  2. Press Left-Shift (only on the HP 49g series and 48g II), MTH, FFT, then FFT to transform the data from the time domain to the frequency domain or Press Left-Shift (only on the HP 49g series and 48g II), MTH, FFT, then IFFT to transform the data from the frequency domain to the time domain.

Example

Using FFT and IFFT for forward and inverse fast Fourier transforms.
This example uses the elements of a random vector to represent a sampled signal.
  1. Create a 16-element random vector on the stack: enter {16} RANM.
  2. Compute the one-dimensional discrete Fourier transform of this signal: execute FFT. The elements of the resulting vector represent the frequency components of the original signal.
  3. Reconstruct the original signal by computing the one-dimensional inverse discrete Fourier transform: execute IFFT. The result is the same as the original signal, subject to small rounding errors.
Compute two-dimensional Fourier transforms using matrices as arguments. For instance, use a random 16x16 matrix in the above example: {16 16} RANM