Audio Processing C++ - FFT

Question

I'm probably going to ask this incorrectly and make myself look very stupid but here goes:

I'm trying to do some audio manipulate and processing on a .wav file. Now, I am able to read all of the data (including the header) but need the data to be in frequency, and, in order to this I need to use an FFT.

I searched the internet high and low and found one, and the example was taken out of the "Numerical Recipes in C" book, however, I amended it to use vectors instead of arrays. Ok so here's the problem:

I have been given (as an example to use) a series of numbers and a sampling rate:

X = {50, 206, -100, -65, -50, -6, 100, -135}

Sampling Rate : 8000 Number of Samples: 8

And should therefore answer this:

  0Hz     A=0       D=1.57079633
  1000Hz     A=50      D=1.57079633
  2000HZ     A=100     D=0
  3000HZ     A=100     D=0
  4000HZ     A=0       D=3.14159265

The code that I re-wrote compiles, however, when trying to input these numbers into the equation (function) I get a Segmentation fault.. Is there something wrong with my code, or is the sampling rate too high? (The algorithm doesn't segment when using a much, much smaller sampling rate). Here is the code:

#include <iostream>
#include <math.h>
#include <vector>
using namespace std;

#define SWAP(a,b) tempr=(a);(a)=(b);(b)=tempr;
#define pi 3.14159

void ComplexFFT(vector<float> &realData, vector<float> &actualData, unsigned long sample_num, unsigned int sample_rate, int sign)
{
    unsigned long n, mmax, m, j, istep, i;
    double wtemp,wr,wpr,wpi,wi,theta,tempr,tempi;

    // CHECK TO SEE IF VECTOR IS EMPTY;

    actualData.resize(2*sample_rate, 0);

    for(n=0; (n < sample_rate); n++)
    {
        if(n < sample_num)
        {
            actualData[2*n] = realData[n];
        }else{
            actualData[2*n] = 0;
            actualData[2*n+1] = 0;
        }
    }

    // Binary Inversion
    n = sample_rate << 1;
    j = 0;

    for(i=0; (i< n /2); i+=2)
    {
        if(j > i)
        {
            SWAP(actualData[j], actualData[i]);
            SWAP(actualData[j+1], actualData[i+1]);
            if((j/2)<(n/4))
            {
                SWAP(actualData[(n-(i+2))], actualData[(n-(j+2))]);
                SWAP(actualData[(n-(i+2))+1], actualData[(n-(j+2))+1]);
            }
        }
        m = n >> 1;
         while (m >= 2 && j >= m) {
          j -= m;
          m >>= 1;
         }
         j += m;
     }
     mmax=2;

     while(n > mmax) {

        istep = mmax << 1;
        theta = sign * (2*pi/mmax);
        wtemp = sin(0.5*theta);
        wpr = -2.0*wtemp*wtemp;
        wpi = sin(theta);
        wr = 1.0;
        wi = 0.0;

        for(m=1; (m < mmax); m+=2) {
            for(i=m; (i <= n); i += istep)
            {
                j = i*mmax;
                tempr = wr*actualData[j-1]-wi*actualData[j];
                tempi = wr*actualData[j]+wi*actualData[j-1];

                actualData[j-1] = actualData[i-1] - tempr;
                actualData[j] = actualData[i]-tempi;
                actualData[i-1] += tempr;
                actualData[i] += tempi;
            }
            wr = (wtemp=wr)*wpr-wi*wpi+wr;
            wi = wi*wpr+wtemp*wpi+wi;
        }
        mmax = istep;
    }

    // determine if the fundamental frequency
    int fundemental_frequency = 0;
    for(i=2; (i <= sample_rate); i+=2)
    {
        if((pow(actualData[i], 2)+pow(actualData[i+1], 2)) > pow(actualData[fundemental_frequency], 2)+pow(actualData[fundemental_frequency+1], 2)) {
            fundemental_frequency = i;
        }

    }
}
int main(int argc, char *argv[]) {

    vector<float> numbers;
    vector<float> realNumbers;

    numbers.push_back(50);
    numbers.push_back(206);
    numbers.push_back(-100);
    numbers.push_back(-65);
    numbers.push_back(-50);
    numbers.push_back(-6);
    numbers.push_back(100);
    numbers.push_back(-135);

    ComplexFFT(numbers, realNumbers, 8, 8000, 0);

    for(int i=0; (i < realNumbers.size()); i++)
    {
        cout << realNumbers[i] << "\n";
    }
}

The other thing, (I know this sounds stupid) but I don't really know what is expected of the "int sign" That is being passed through the ComplexFFT function, this is where I could be going wrong.

Does anyone have any suggestions or solutions to this problem?

Thank you :)

Answer 1

I think the problem lies in errors in how you translated the algorithm.

• Did you mean to initialize j to 1 rather than 0?

• for(i = 0; (i < n/2); i += 2) should probably be for (i = 1; i < n; i += 2).

• Your SWAPs should probably be

  SWAP(actualData[j - 1], actualData[i - 1]);
  SWAP(actualData[j], actualData[i]);
  

• What are the following SWAPs for? I don't think they're needed.

  if((j/2)<(n/4))
  {
      SWAP(actualData[(n-(i+2))], actualData[(n-(j+2))]);
      SWAP(actualData[(n-(i+2))+1], actualData[(n-(j+2))+1]);
  }
  

• The j >= m in while (m >= 2 && j >= m) should probably be j > m if you intended to do bit reversal.

• In the code implementing the Danielson-Lanczos section, are you sure j = i*mmax; was not supposed to be an addition, i.e. j = i + mmax;?

---

Apart from that, there are a lot of things you can do to simplify your code.

Using your SWAP macro should be discouraged when you can just use std::swap... I was going to suggest std::swap_ranges, but then I realized you only need to swap the real parts, since your data is all reals (your time-series imaginary parts are all 0):

std::swap(actualData[j - 1], actualData[i - 1]);

You can simplify the entire thing using std::complex, too.

Answer 2

The FFT in Numerical Recipes in C uses the Cooley-Tukey Algorithm, so in answer to your question at the end, the int sign being passed allows the same routine to be used to compute both the forward (sign=-1) and inverse (sign=1) FFT. This seems to be consistent with the way you are using sign when you define theta = sign * (2*pi/mmax).

Answer 3

I reckon its down to the re-sizing of your vector.

One possibility: Maybe re-sizing will create temp objects on the stack before moving them back to heap i think.