Can I calculate FFT without using floating point numbers?

8 posts / 0 new
Last post
Author
Message
#1
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Can I calculate FFT without using floating point numbers?

I have 8 or 10 bits samples coming from an Analog Digital Converter. They are unsigned integers.
I want to perform FFTs using an 8 bit AVR on blocks of 128 to 1024 samples.

Question: Can I evaluate those FFTs without using floating point variables, just signed or unsigned integers, to speed up calculations?

FFT algorithm in C: http://www.codeproject.com/KB/recipes/howtofft.aspx

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

ChaN has a fixed point fft library written in assembler.
http://elm-chan.org/works/akilcd/report_e.html

Quote:
The FFT operations are done in 16-bit fixed-point. These 128 point FFT processes, applying window, butterfly operations and scalar output, could be executed in real-time (within 7.3 msec). The sampling frequency is 9.6 kHz

"Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it"

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Hmmm--a Google search on 'FFT "integer only" ' gives some interesting hits. Several mention CORDIC which has been brought up here before.

You can put lipstick on a pig, but it is still a pig.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

In my application i started with ChaN's fixed-point FFT implementation, but changed to another algorithm due to arithmetical reasons (incorrect results, i believe). Now i'm using an optimized Hartley algorithm to perform a floating-point-based 128 bin FFT on an array of ADC values. The FFT is done within about 23ms on a 12 MHz ATmega32.

Einstein was right: "Two things are unlimited: the universe and the human stupidity. But i'm not quite sure about the former..."

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

There is a pc app called fixfft that might be port-able to an avr c compiler

Imagecraft compiler user

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

In the old days of 16 bit arithmetic you would subtract the DC component to get zero mean (this was called floating the buffer) and do an integer FFT. If overflows did occur you just divide everything by another power of two. That gives 16 bit precision in the AC frequencies, since there is no longer a DC component.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Here's a website having several algorithms in several languages : www.jjj.de/fft/fftpage.html

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I did a couple projects with integer FFT. First one based on the code from www.jjj.de, and second is my own improved algorithm. 8-bit version about ~32msec with 512 FFT, arduino Uno board AtMega328p 16Mhz.
http://fftarduino.blogspot.com/2011/02/color-organ-spectrum-analyzer-on.html

http://musicalnoterecognition.blogspot.com/2011/09/arduino-musical-note-recognition.html#comment-form