Optimizing FFT code for 12 bit processing on microcontroller

Question

I want to port the following FFT code on a microcontoller having a very little floating point capability. I want to perform FFT of the output from 12 bit ADC. Since my values are all 12 bit numbers it is wasteful of storage and processing power (I do not need very accurate FFT output) if I do every thing in double as the following code does.

How do I modify this C code so that it works only for 12 bit numbers and do not do any floating point arithmatic. This way I can save lots of storage space and do very litlle arithmatics.

#define PI  M_PI    /* pi to machine precision, defined in math.h */
#define TWOPI   (2.0*PI)


void four1(double data[], int nn, int isign)
{
    int n, mmax, m, j, istep, i;
    double wtemp, wr, wpr, wpi, wi, theta;
    double tempr, tempi;

    n = nn << 1;
    j = 1;
    for (i = 1; i < n; i += 2) {
    if (j > i) {
        tempr = data[j];     data[j] = data[i];     data[i] = tempr;
        tempr = data[j+1]; data[j+1] = data[i+1]; data[i+1] = tempr;
    }
    m = n >> 1;
    while (m >= 2 && j > m) {
        j -= m;
        m >>= 1;
    }
    j += m;
    }
    mmax = 2;
    while (n > mmax) {
    istep = 2*mmax;
    theta = TWOPI/(isign*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*data[j]   - wi*data[j+1];
        tempi = wr*data[j+1] + wi*data[j];
        data[j]   = data[i]   - tempr;
        data[j+1] = data[i+1] - tempi;
        data[i] += tempr;
        data[i+1] += tempi;
        }
        wr = (wtemp = wr)*wpr - wi*wpi + wr;
        wi = wi*wpr + wtemp*wpi + wi;
    }
    mmax = istep;
    }
}

Answer 1

12-bit is not a native data type on your platform, so the best you can do without loss of precision is 16-bit per sample, in Q15 format.

I don't know the Stellaris line well, but from what I gathered on the TI website, these are either Cortex M3 (LM3xxx) or Cortex M4 (LM4xxx).

The Cortex M4 embeds a floating point unit; so there won't be as much benefit in terms of run-time from converting your code to fixed point as you think. The immediate thing is to switch to 32-bit floats. The next thing is to check your compiler settings and have a quick look at the disassembled generated code to check that it actually generates floating point instructions rather than using emulation. With gcc, you'll probably have to use compilation flags like -mcpu=cortex-m4 -mfloat-abi=hard -mfpu=fpv4-sp-d16 (which are the flags I use with another Cortex-M4 product). There's a good chance you'll get better performance from using a vendor-supplied function rather than your own code. Try arm_cfft_radix4_f32 in the CMSIS DSP library. This should solve your performance problems.

If you use a M3 part instead, and/or are really short on RAM for your samples, you'll have to switch to fixed point (Q15 format). Again, you don't have to write code for that, just grab the CMSIS DSP library provided by TI and use the functions arm_rfft_q15 (for real input) or arm_cfft_radix4_q15 (for complex input, if the input size is a power of 4).

Answer 2

As you probably know, C does not provide any special support for fixed-point implementations. This means that you would need to do everything by yourself: doing the appropriate scaling, checking for underflow and overflow, etc. This is definitely possible but it's a lot of work and you might encounter numerical issues resulting in large errors if the variable scaling is not done properly. But there is definitely a lot of literature to help you with this task (just search for "fixed-point FFT").

Having said all that, you still might want to try a simpler route. I'm not sure about the floating point capabilities of your microcontroller, but you could try the shortest floating point format (instead of double). Another great improvement would be to use pre-calculated tables for the sine and cosine values. I would try such simple strategies first and see if the computational complexity can be sufficiently reduced or if you really need to go for a fixed-point solution.