How to use apple's Accelerate framework in swift in order to compute the FFT of a real signal?

Question

How am I supposed to use the Accelerate framework to compute the FFT of a real signal in Swift on iOS?

Available example on the web

Apple’s Accelerate framework seems to provide functions to compute the FFT of a signal efficiently.

Unfortunately, most of the examples available on the Internet, like Swift-FFT-Example and TempiFFT, crash if tested extensively and call the Objective C API.

The Apple documentation answers many questions, but also leads to some others (Is this piece mandatory? Why do I need this call to convert?).

Threads on Stack Overflow

There are few threads addressing various aspects of the FFT with concrete examples. Notably FFT Using Accelerate In Swift, DFT result in Swift is different than that of MATLAB and FFT Calculating incorrectly - Swift. None of them address directly the question “What is the proper way to do it, starting from 0”?

It took me one day to figure out how to properly do it, so I hope this thread can give a clear explanation of how you are supposed to use Apple's FFT, show what are the pitfalls to avoid, and help developers save precious hours of their time.

Answer 1

TL ; DR : If you need a working implementation to copy past here is a gist.

What is FFT?

The Fast Fourier transform is an algorithm that take a signal in the time domain -- a collection of measurements took at a regular, usual small, interval of time -- and turn it into a signal expressed into the phase domain (a collection of frequency). The ability to express the signal along time lost by the transformation (the transformation is invertible, which means no information is lost by computing the FFT and you can apply a IFFT to get the original signal back), but we get the ability to distinguish between frequencies that the signal contained. This is typically used to display the spectrograms of the music you are listening to on various hardware and youtube videos.

The FFT works with complexe numbers. If you don't know what they are, lets just pretend it is a combination of a radius and an angle. There is one complex number per point on a 2D plane. Real numbers (your usual floats) can be saw as a position on a line (negative on the left, positive on the right).

Nb: FFT(FFT(FFT(FFT(X))) = X (up to a constant depending on your FFT implementation).

How to compute the FFT of a real signal.

Usual you want to compute the FFT of a small window of an audio signal. For sake of the example, we will take a small 1024 samples window. You would also prefer to use a power of two, otherwise things gets a little bit more difficult.

var signal: [Float] // Array of length 1024

First, you need to initialize some constants for the computation.

// The length of the input
length = vDSP_Length(signal.count)
// The power of two of two times the length of the input.
// Do not forget this factor 2.
log2n = vDSP_Length(ceil(log2(Float(length * 2))))
// Create the instance of the FFT class which allow computing FFT of complex vector with length
// up to `length`.
fftSetup = vDSP.FFT(log2n: log2n, radix: .radix2, ofType: DSPSplitComplex.self)!

Following apple's documentation, we first need to create a complex array that will be our input. Dont get mislead by the tutorial. What you usual want is to copy your signal as the real part of the input, and keep the complex part null.

// Input / Output arrays

var forwardInputReal = [Float](signal) // Copy the signal here
var forwardInputImag = [Float](repeating: 0, count: Int(length))
var forwardOutputReal = [Float](repeating: 0, count: Int(length))
var forwardOutputImag = [Float](repeating: 0, count: Int(length))

Be careful, the FFT function do not allow to use the same splitComplex as input and output at the same time. If you experience crashs, this may be the cause. This is why we define both an input and an output.

Now, we have to be careful and "lock" the pointer to this four arrays, as showed in the documentation example. If you simply use &forwardInputReal as argument of your DSPSplitComplex, the pointer may become invalidated at the following line and you will likely experience sporadic crash of your app.

    forwardInputReal.withUnsafeMutableBufferPointer { forwardInputRealPtr in
      forwardInputImag.withUnsafeMutableBufferPointer { forwardInputImagPtr in
        forwardOutputReal.withUnsafeMutableBufferPointer { forwardOutputRealPtr in
          forwardOutputImag.withUnsafeMutableBufferPointer { forwardOutputImagPtr in
            // Input
            let forwardInput = DSPSplitComplex(realp: forwardInputRealPtr.baseAddress!, imagp: forwardInputImagPtr.baseAddress!)
            // Output
            var forwardOutput = DSPSplitComplex(realp: forwardOutputRealPtr.baseAddress!, imagp: forwardOutputImagPtr.baseAddress!)

            // FFT call goes here
          }
        }
      }
    }

Now, the finale line: the call to your fft:

fftSetup.forward(input: forwardInput, output: &forwardOutput)

The result of your FFT is now available in forwardOutputReal and forwardOutputImag.

If you want only the amplitude of each frequency, and you don't care about the real and imaginary part, you can declare alongside the input and output an additional array:

var magnitudes = [Float](repeating: 0, count: Int(length))

add right after your fft compute the amplitude of each "bin" with:

vDSP.absolute(forwardOutput, result: &magnitudes)