Module: Shazamio::FFT

Defined in:
lib/shazamio/fft.rb

Overview

A small, dependency-free FFT used to reimplement numpy's np.fft.rfft for the signature algorithm. Only handles power-of-two sizes, which is all the algorithm ever needs (a 2048-sample window).

This is plain Ruby, so it is meaningfully slower than numpy/FFTW. If you process a lot of audio and have network access to rubygems.org, swap FFT.rfft out for a binding to FFTW (e.g. the fftw3 gem) or Numo::NArray without changing any other file — Algorithm::SignatureGenerator only calls FFT.rfft.

Class Method Summary collapse

Class Method Details

.fft(complex_samples) ⇒ Object

In-place-conceptual iterative Cooley-Tukey FFT (returns a new array).



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
 
# File 'lib/shazamio/fft.rb', line 27

def fft(complex_samples)
  n = complex_samples.length
  return complex_samples.dup if n <= 1

  a = bit_reverse_copy(complex_samples)

  len = 2
  while len <= n
    ang = -2 * Math::PI / len
    wlen = Complex(Math.cos(ang), Math.sin(ang))
    i = 0
    while i < n
      w = Complex(1, 0)
      (len / 2).times do |j|
        u = a[i + j]
        v = a[i + j + len / 2] * w
        a[i + j] = u + v
        a[i + j + len / 2] = u - v
        w *= wlen
      end
      i += len
    end
    len <<= 1
  end

  a
end

.rfft(real_samples) ⇒ Object

Real FFT: takes N real samples, returns N/2+1 complex bins, matching numpy's np.fft.rfft for real input.

Raises:

  • (ArgumentError) 


18
19
20
21
22
23
24
 
# File 'lib/shazamio/fft.rb', line 18

def rfft(real_samples)
  n = real_samples.length
  raise ArgumentError, "size must be a power of two" unless (n & (n - 1)).zero?

  spectrum = fft(real_samples.map { |s| Complex(s, 0) })
  spectrum[0..(n / 2)]
end