class Digiproc::Strategies::Radix2Strategy

O(n*lgn) FFT algorithm Requires that the number of datapoints be a power of 2 if it isn't the calculation will zero pad to the closest power of 2 above the current data size The size of the outputted DFT will be the size of the zero-padded dataset. Zero-padding causes the “sample locations” of the DFT to be at different locations than if it was not zero padded, but The resolution of the DFT will INCREASE due to zero padding

Constants

E
PI

Attributes

data[R]

Public Class Methods

new(data = nil) click to toggle source

Initialize Arg

data (Optional)

Array (defaults to nil)

# File lib/strategies/fft/radix2_strategy.rb, line 20
def initialize(data = nil)
    @data = data
    zero_fill if not data.nil?
end

Public Instance Methods

calculate(data = @data) click to toggle source

Input arg

data (Optional)

Array (defaults to @data)

# File lib/strategies/fft/radix2_strategy.rb, line 28
def calculate(data = @data)
    recursive_fft(data)
end
data=(data) click to toggle source

@data writer, and zero fills array to obtain a size of the closest power of 2 above current size

# File lib/strategies/fft/radix2_strategy.rb, line 34
def data=(data)
    @data = data
    zero_fill
end

Private Instance Methods

closest_pow_of_2(num) click to toggle source
# File lib/strategies/fft/radix2_strategy.rb, line 81
def closest_pow_of_2(num)
    2 ** Math.log(num,2).ceil
end
get_even(arr) click to toggle source
# File lib/strategies/fft/radix2_strategy.rb, line 59
def get_even(arr)
    even = []
    arr.each_with_index { |a, i| even << a.dup if i % 2 == 0 }
    even
end
get_odd(arr) click to toggle source
# File lib/strategies/fft/radix2_strategy.rb, line 65
def get_odd(arr)
    odd = []
    arr.each_with_index { |a, i| odd << a.dup if i % 2 == 1 }
    odd
end
power_of_two?(num) click to toggle source
# File lib/strategies/fft/radix2_strategy.rb, line 76
def power_of_two?(num)
    lg = Math.log(num,2)
    lg.round.to_f == lg 
end
recursive_fft(arr) click to toggle source
# File lib/strategies/fft/radix2_strategy.rb, line 41
def recursive_fft(arr)
    n = arr.length
    return arr if n == 1
    w_n = E ** ((-2 * PI * Complex(0,1)) / n)
    w = 1
    a0 = get_even(arr)
    a1 = get_odd(arr)
    y0 = recursive_fft(a0)
    y1 = recursive_fft(a1)
    y = Array.new(n, 0)
    for k in 0...(n/2) do
        y[k] = (y0[k] + w * y1[k])
        y[k + n/2] = (y0[k] - w * y1[k])
        w = w * w_n
    end
    y
end
zero_fill() click to toggle source
# File lib/strategies/fft/radix2_strategy.rb, line 71
def zero_fill
    len = self.data.length
    @data = @data.concat Array.new(closest_pow_of_2(len) - len, 0)
end