Use 1D fast Fourier transform to compute the frequency components of a signal.
Accelerate’s vDSP module provides functions to perform 1D fast Fourier transforms (FFTs) on vectors of data, such as audio signals. The following shows an input signal (at left), and its frequency domain equivalent (at right) after transforming the signal with a forward FFT.
You can inspect the frequency-domain data of a forward FFT to compute the individual sine wave components of a composite wave. The technique described in this article is applicable in many digital signal processing applications; for example, finding the dominant frequencies in a dual-tone multi-frequency (DTMF) signal or removing noise from a signal.
In this article you'll learn how to create a composite sine wave, perform a forward FFT, inspect the result to find its components, and perfom an inverse FFT to recreate the original signal.
Create the Composite Signal
Start by creating an array to generate a signal. You’ll need to populate an array of single-precision values using the sums of a series of sine waves. You define the frequencies as the number of cycles per
n. The highest measureable frequency, known as the Nyquist frequency, is the element with index
n/2, which is
1023 in a zero-based array.
The following creates the array,
signal, containing 10 component sine waves:
The following image is a visualization of composite sine waves in
Convert Real Data to Interleaved Complex Data
To prepare the real values in
signal for use with the FFT functions in vDSP, convert them to an array of complex numbers (represented by
DSPComplex structures). Define the real components as the even values in
signal, and the imaginary components as the odd values in
Convert Interleaved Complex Data to a Split Complex Vector
The FFT function,
v, accepts split complex vectors for input and output. Use
v to copy the contents of the interleaved representation of
signal to a split complex vector.
Because each complex value stores two real values, the length of the
DSPSplit structure is half that of
Create the FFT Setup
Create a setup object that contains a precalculated weights array of complex exponentials required to perform the FFT operations. The vaues in the weights array simplify the FFT calculation. Creating this setup object can be expensive, so do it only once; for example, when starting your app. After creating the setup object, you can reuse it later, as needed.
The following code creates a setup object suitable for performing forward and inverse 1D FFTs on a signal containing
You can use this setup object for similarly sized smaller FFTs. However, using a weights array built for an FFT that processes a large number of elements can degrade performance for an FFT that processes a significantly smaller number of elements.
When you no longer need the setup object, be sure to deallocate its assigned memory. The following code shows how to use the
v function to destroy the setup object:
Perform the Forward FFT
v function to perform an out-of-place forward 1D FFT on the signal data, creating the frequency domain representation of the signal:
forward contains the DC components of the forward FFT, and
forward contains the Nyquist components of the forward FFT.
Compute Component Frequencies in Frequency Domain
The Nyquist components of the forward FFT contains a series of high-magnitude items, rendered as vertical lines in the graph below:
These high-magnitude items correspond exaclty to the frequencies you specified in the
Recreate the Original Signal
Use an inverse FFT to recreate a signal in the time-domain from the frequency domain-data returned by the forward FFT:
The process for generating an array of real values from the complex result of the inverse FFT is the opposite of the conversion steps described in Convert Interleaved Complex Data to a Split Complex Vector. Use
v to copy the contents of the split complex FFT result to an interleaved complex vector:
map to populate the final array of single-precision values. Because the forward transform has a scaling factor of 2 and the inverse transform has a scaling factor of the number of items, divide each result by
2 * n:
recreated is approximately equal to