class STFTSpectrogram::FFT::FFTComputation

Implementation of the Fast Fourier Transform algorithm

Public Instance Methods

perform(data) click to toggle source

Performs FFT on data Expects data in complex format - even indexes contain real numbers odd indexes contain imaginary numbers

# File lib/stft/fft.rb, line 10
def perform(data)
  unless pow2? data.length
    raise ArgumentError, 'Data array for FFT has to be power of 2 long'
  end
  data = reindex(data)
  danielson_lanzcos(data)
end

Private Instance Methods

danielson_lanzcos(data) click to toggle source

The Danielson-Lanczos part of the algorithm

# File lib/stft/fft.rb, line 37
def danielson_lanzcos(data)
  mmax = 2
  n = data.length
  while n > mmax

    istep = mmax * 2
    theta = -(2.0 * Math::PI / mmax.to_f)
    wtemp = Math.sin(theta / 2.0)
    wpr = -2.0 * wtemp * wtemp
    wpi = Math.sin(theta)
    wr = 1.0
    wi = 0.0
    (1..mmax - 1).step(2) do |m|
      (m..n).step(istep) do |i|
        j = i + mmax
        tempr = wr * data[j - 1] - wi * data[j]
        tempi = wr * data[j] + wi * data[j - 1]
        data[j - 1] = data[i - 1] - tempr
        data[j] = data[i] - tempi
        data[i - 1] += tempr
        data[i] += tempi
      end
      wtemp = wr
      wr += wr * wpr - wi * wpi
      wi += wi * wpr + wtemp * wpi
    end
    mmax = istep
  end
  data
end
pow2?(num) click to toggle source

Returns true is num is a power of 2

# File lib/stft/fft.rb, line 69
def pow2?(num)
  num.to_s(2).count('1') == 1
end
reindex(data) click to toggle source

Reindexing part of the algorithm Data are shifted in preparation for the Danielson-Lanczos

# File lib/stft/fft.rb, line 21
def reindex(data)
  j = 1
  (1..data.length - 1).step(2) do |i|
    data[j], data[i] = data[i], data[j] if j > i
    data[j - 1], data[i - 1] = data[i - 1], data[j - 1] if j > i
    m = data.length / 2
    while m >= 2 && j > m
      j -= m
      m /= 2
    end
    j += m
  end
  data
end