Class: SPCore::FFT

Inherits:
Object
  • Object
show all
Defined in:
lib/spcore/transforms/fft.rb

Overview

Author:

  • James Tunnell

Class Method Summary collapse

Class Method Details

.forward(input, force_radix_2_size = true) ⇒ Object

Forward Radix-2 FFT transform using decimation-in-time. Operates on an array of real values, representing a time domain signal. Ported from unlicensed MATLAB code which was posted to the MathWorks file exchange by Dinesh Dileep Gaurav. See www.mathworks.com/matlabcentral/fileexchange/17778.

Parameters:

  • input (Array) —

    An array of numeric values. If size is not an exact radix-2 number, then zeros will be appended until it is, unless force_radix_2_size is set false.

  • force_radix_2_size (defaults to: true) —

    If true, any input that does not have an exact power-of-two size will be appended with zeros until it does. Set true by default.

Raises:

  • (ArgumentError) —

    if input size is not an exact radix-2 number and force_radix_2_size is false.



24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
 
# File 'lib/spcore/transforms/fft.rb', line 24

def self.forward input, force_radix_2_size = true
  size = input.size
  power_of_two = Math::log2(size)
  if power_of_two.floor != power_of_two # input size is not an even power of two
    if force_radix_2_size
      new_size = 2**(power_of_two.to_i() + 1)
      input += Array.new(new_size - size, 0.0)
      
      size = input.size
      power_of_two = Math::log2(size)
    else
      raise ArgumentError, "input.size #{size} is not a radix-2 number"
    end
  end
  power_of_two = power_of_two.to_i
  x = bit_reverse_order input, power_of_two
  
  phase = Array.new(size/2){|n|
    Complex(Math::cos(TWO_PI*n/size), -Math::sin(TWO_PI*n/size))
  }
  for a in 1..power_of_two
    l = 2**a
    phase_level = []

    0.step(size/2, size/l) do |i|
      phase_level << phase[i]
    end
    
    ks = []
    0.step(size-l, l) do |k|
      ks << k
    end

    ks.each do |k|
      for n in 0...l/2
        idx1 = n+k
        idx2 = n+k + (l/2)
        
        first  = x[idx1]
        second = x[idx2] * phase_level[n]
        x[idx1] = first + second
        x[idx2] = first - second
      end
    end
  end
  return x
end

.inverse(input) ⇒ Object

Inverse Radix-2 FFT transform. Operates on an array of complex values, as one would obtain from the forward FFT transform. Ported from unlicensed MATLAB code which was posted to the MathWorks file exchange by Dinesh Dileep Gaurav. See www.mathworks.com/matlabcentral/fileexchange/17778.

Parameters:

  • input (Array) —

    An array of complex values. Must have a radix-2 size (2, 4, 8, 16, 32, …).

Raises:

  • (ArgumentError) —

    if input size is not an exact power-of-two.



80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
 
# File 'lib/spcore/transforms/fft.rb', line 80

def self.inverse input
  size = input.size
  power_of_two = Math::log2(size)
  raise ArgumentError, "input.size #{size} is not power of 2" if power_of_two.floor != power_of_two
  power_of_two = power_of_two.to_i
  x = bit_reverse_order input, power_of_two
  
  phase = Array.new(size/2){|n|
    Complex(Math::cos(TWO_PI*n/size), -Math::sin(TWO_PI*n/size))
  }
  for a in 1..power_of_two
    l = 2**a
    phase_level = []

    0.step(size/2, size/l) do |i|
      phase_level << phase[i]
    end
    
    ks = []
    0.step(size-l, l) do |k|
      ks << k
    end

    ks.each do |k|
      for n in 0...l/2
        idx1 = n+k
        idx2 = n+k + (l/2)
        
        first  = x[idx1]
        second = x[idx2] * phase_level[n]
        x[idx1] = (first + second)
        x[idx2] = (first - second)
      end
    end
  end
  
  return x.map {|val| val / size }
end

.power_of_two?(size) ⇒ Boolean

Returns:

  • (Boolean) 


6
7
8
9
 
# File 'lib/spcore/transforms/fft.rb', line 6

def self.power_of_two? size
  log2size = Math::log2(size)
  return log2size.floor == log2size
end