I need help figuring out this FFT method

Question

I am trying to get the frequencies from a sound wave using fft. I have found an FFT method, but I am having trouble understanding what it wants me to put in, how to get information out of it, and how to use what I get out of it. I have tried entering the value at index of the buffer as y, with the buffer position as x, but I get weird results. int m seems to be something to do with samples, but I have no clue how to choose what I want to input there. But it effects how much is stored into the x and y double. Luckily dir, is rather easy to understand, it's basically acting like a bool for whether you FFT forward or not.

public static void FFT(short dir, int m, double[] x, double[] y)
    {
        int n, i, i1, j, k, i2, l, l1, l2;
        double c1, c2, tx, ty, t1, t2, u1, u2, z;

        // Calculate the number of points 

        n = 1;

        for (i = 0; i < m; i++)
            n *= 2;

        // Do the bit reversal 

        i2 = n >> 1;
        j = 0;
        for (i = 0; i < n - 1; i++)
        {
            if (i < j)
            {
                tx = x[i];
                ty = y[i];
                x[i] = x[j];
                y[i] = y[j];
                x[j] = tx;
                y[j] = ty;
            }
            k = i2;

            while (k <= j)
            {
                j -= k;
                k >>= 1;
            }

            j += k;
        }

        // Compute the FFT 

        c1 = -1.0;
        c2 = 0.0;
        l2 = 1;

        for (l = 0; l < m; l++)
        {
            l1 = l2;
            l2 <<= 1;
            u1 = 1.0;
            u2 = 0.0;

            for (j = 0; j < l1; j++)
            {
                for (i = j; i < n; i += l2)
                {
                    i1 = i + l1;
                    t1 = u1 * x[i1] - u2 * y[i1];
                    t2 = u1 * y[i1] + u2 * x[i1];
                    x[i1] = x[i] - t1;
                    y[i1] = y[i] - t2;
                    x[i] += t1;
                    y[i] += t2;
                }

                z = u1 * c1 - u2 * c2;
                u2 = u1 * c2 + u2 * c1;
                u1 = z;
            }

            c2 = Math.Sqrt((1.0 - c1) / 2.0);

            if (dir == 1)
                c2 = -c2;

            c1 = Math.Sqrt((1.0 + c1) / 2.0);
        }

        // Scaling for forward transform 

        if (dir == 1)
        {
            for (i = 0; i < n; i++)
            {
                x[i] /= n;
                y[i] /= n;
            }
        }

See [this answer](https://stackoverflow.com/a/7675171/253056) for an outline of what you need to do with the FFT inputs and outputs. — Paul R, Feb 14 '18 at 08:13
see [How to compute Discrete Fourier Transform?](https://stackoverflow.com/a/26355569/2521214) and all the sub-links. Also beware that you will obtain Niquist frequencies not the actual frequencies of your signal so you need to take in mind aliasing will be present. Also using non power of 2 datasets creates big problems with the frequency acquisition if used FFT instead of DFT ... — Spektre, Feb 14 '18 at 08:46

Mike Mat · Answer 1 · 2018-02-14T17:44:12.023

1

My guess is:

m: Log2 of the data length
x: real part of input data
y: imaginary part of input data (array of 0s if the signal consists of only real numbers)

I have not tested so please let me know if it works.

edited Feb 14 '18 at 17:44

answered Feb 13 '18 at 23:08

Mike Mat

632
7
15

real part? imaginary part? – Kuroyuki Feb 13 '18 at 23:34
2

If your input is not an array of complex numbers, I think you can simply supply an array of 0s for the argument `y`. – Mike Mat Feb 14 '18 at 01:38
Int m Seems to be really weird. If I enter in anything higher than 10 I don't get any changes in the input arrays. But, from 1 to 10 I get changes. And the odd things is that the 0s change too. – Kuroyuki Feb 15 '18 at 21:08
Is the result like you expected when `int m` is in the range? If not, please update the question so that we can check again for the right parameters. As for the strange behavior of `int m`, it shouldn't be so difficult to debug it to find out what is going on. – Mike Mat Feb 19 '18 at 05:57

I need help figuring out this FFT method

1 Answers1