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