Use 1D fast Fourier transform to compute the frequency components of a signal.

Framework

- Accelerate

## Overview

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 `signal`

:

### 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 `signal`

:

### 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 `signal`

.

### 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 `n`

elements:

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

Use the `v`

function to perform an out-of-place forward 1D FFT on the signal data, creating the frequency domain representation of the signal:

On return, `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 `frequencies`

array:

### 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:

Use `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`

:

On return, `recreated`

is approximately equal to `signal`

.