FFT in C with floating point
FFT (see CoffeeBreak 1, 2) is very old algorithm, may be more than 40 years old. Therefore a lot of C source codes are spread around the world. First of all, let's try it normally in C with floating point.

(1) What's FFT??

Any complicated wave can be decomposed to simple sine waves... This theory, Fourier Transform, is discovered by French mathematician Joseph Fourier. DFT(Discrete Fourier Transform) is to do it in digital and FFT(Fast Fourier Transform) is to speed it up.


(2) Speed up by decreasing multiplications

FFT is the algorithm that factorizes ab+ac to a(b+c) to decrease its multiplications. The number of complex multiplications becomes (N/2)log2(N) whereas it's N^2 in DFT. The following table shows number of multiplications.
Points DFT FFT ratio(%)
4 16 4 25.0
16 256 32 12.5
64 4,096 192 4.69
256 65,536 1,024 1.56
1024 1,048,576 5,120 0.49
4096 16,777,216 24,576 0.15
(We pick up 1024-point in this class)
(1) Describe floating point FFT
  • 1024-point FFT runs on VC++.
  • Variables are defined as double.
(2) Execute floating point FFT
  • Read input and trigonometric funcions.
  • FFT shows 6kHz in the spectrum.
(3) Inspect the Result of FFT
  • Magnitude of spectrum is 500.
  • Result of FFT becomes much bigger.

Back


Top Page