Fourier Transform Example in Ruby

This is a simple tool for calculating and plotting (in ASCII) the frequency domain of a 
generated signal. The implementation of the Fourier Transform written in Ruby and should
be clear and consise enough for anyone to understand. Included are two algorithms, the 
Discrete Fourier Transform (DFT) and the Fast Fourier Transform (FFT).

[FFT] Sample rate: 44.1kHz / Buffer size: 128 samples / Input: generated 880.0Hz square wave

      Found fundamental peak frequency of 689.06Hz +/- 172.27 (off by 190.94Hz)

        .                                                             - 0.9
        ..                                                            
        ..                                                            - 0.8
        ..                                                            
        ..                                                            - 0.7
        ..                                                            
        ..                                                            - 0.6
        ..                                                            
        ..                                                            - 0.5
        ..                                                            
      ....    .                                                       - 0.4
      ....    .                                                       
      ....    .                                                       - 0.3
      ....    .                                                       
      ....    .                                                       - 0.3
      ....   ..    .    .    .                                        
      ....   ..    .    .    .                                        - 0.2
      .....  ...  ..    .    .    .    .    .    .    ..    .    .    
      .....  ...  ..    .    .    .    .    .    .    ..    .    .    - 0.1
      ................................................................
      ----------------------------------------------------------------- 0.0
      ^ *       ^         ^         ^         ^         ^         ^    
      0kHz     3kHz      7kHz      10kHz     14kHz     17kHz     21kHz      


The speed of the algorithms as tested on my Macbook Pro:

DFT: O(N^2)

  N = 1024:  4.55 seconds
      2048: 16.71

The DFT gets very slow and is only included as an example of the implementation and
testing that the FFT results match.
  

FFT: O(N log N)

  N = 1024:  0.03 seconds
      2048:  0.06 
      4096:  0.13
      .. 
     16384:  0.64 

The FFT can almost run at realtime in ruby against a 44kHz signal.

Ruby 1.9 is 30-50% faster than Ruby 1.8.7 in my tests with DFT and FFT.

Usage: ruby fourier_transform.rb -n buffersize -f frequency [-r samplerate] [-w sine|triangle|square|saw] [--plot] [--benchmark]

    -n, --buffersize N               Specify buffer size of N samples
    -f, --frequency FREQUENCY        Specify the frequency of the generated signal in Hz
    -r, --samplerate SAMPLERATE      Specify the sample rate of the generated signal
    -w, --waveform WAVEFORM          Specify the shape of the waveform. sine (default), triangle, square, or saw
        --dft                        Perform a Discrete Fourier Transform (slower)
        --plot                       Plot a graph of the Fourier Transform
        --benchmark                  Benchmark DFT vs FFT
    -h, --help                       Show this message


@corban                                                    weare.buildingsky.net
________________________________________________________________________________

       Copyright (c) 2009 Corban Brook, released under the MIT license