DLL Stream FFT (Finally some progress)

[Youlean]

I was reading excellent article by KG about FFT and I decided to recreate everything in green so I can better understand what is going on inside FFT algorithm. My goal is to make DLL stream FFT, but first I must done it using green.

What is not clear to me is this part of the article:

If we do complex math we can multiply by sine and cosine in a single step. Result will be a complex number – real part will be the magnitude of cosine part and imaginary part will be the magnitude of sine part. We can still calculate the magnitude and phase in very same way. If we do this for every harmonic in the spectrum and plot the complex outputs into graph (3D graph – x = frequency y=real z=imaginary) we have in fact preformed Fourier Transform and we now have the frequency-domain representation of our signal.

So, I don't know how to get magnitude and phase and how actually to perform FFT on all frequencies...
Here is my progress so far...

[Tronic]

this post can help you to port to dll?
see the DWB ruby code
viewtopic.php?f=4&t=1510&hilit=fft#p6433

[Youlean]

this post can help you to port to dll?
see the DWB ruby code
viewtopic.php?f=4&t=1510&hilit=fft#p6433

The problem is that I don't understand that much Ruby code, but if you can explain me some parts I could probably do it...
Can you comment the code so I can better understand it? I will add question mark for what is not clear to me...

Code: Select all

def fft doinverse = true
      src = self
      # raise ArgumentError.new "Expected array input but was '#{src.class}'" unless src.kind_of? Array
      n = src.length
      nlog2 = Math.log( n ) / Math.log( 2 )
      raise ArgumentError.new "Input array size must be a power of two but was '#{n}'" unless nlog2.floor - nlog2 == 0.0
      n2 = n / 2
      phi = Math::PI / n2
      if doinverse
         phi = -phi
      else
         src.collect!{|c| c /= n.to_f}
      end

      # build a sine/cosine table
      wt = Array.new n2
      wt.each_index { |i| wt[i] = Complex(Math.cos(i * phi), Math.sin(i * phi)) } ???Is this building 2 dimensional array?

      # bit reordering ?? What is this doing?
      n1 = n - 1
      j = 0
      1.upto(n1) do |i|
         m = n2
         while j >= m
            j -= m
            m /= 2
         end
         j += m
         src[i],src[j] = src[j],src[i] if j > i
      end

      # 1d(N) Ueberlagerungen ???
      mm = 1
      begin
         m = mm
         mm *= 2
         0.upto(m - 1) do |k|
            w = wt[ k * n2 ]
            k.step(n1, mm) do |i|
               j = i + m
               src[j] = src[i] - (temp = w * src[j])
               src[i] += temp
            end
         end
         n2 /= 2
      end while mm != n
      src
   end
end

//usage
real = []
imag = []

@in.fft(false).each {|i| real.push i.real; imag.push i.imag}
output 0, real; output 1, imag

[Tronic]

???Is this building 2 dimensional array?
yes, you can manage it like an 2D array, but you have to think it as an associative array "real:part + immaginary:part"
and you can use the <complex> stdlib class in c++

?? What is this doing?
butterfly algorithm....
http://www.katjaas.nl/bitreversal/bitreversal.html

Ueberlagerungen ???
this calculate the overlapped pieces for the windows

[Robertocrarswell]

Thank you for all great information.

[Youlean]

Ok, thanks. Sorry for late response..

I still dont understand what this peace of code is doing.
Is this building sine and cosine of whole array size (one sine cycle in, for example 1024 array) and then getting their complex number (2 arrays are added to get one complex number) and then storing that numbers on each index in wave table array?

wt.each_index { |i| wt[i] = Complex(Math.cos(i * phi), Math.sin(i * phi))

[tulamide]

wt.each_index { |i| wt[i] = Complex(Math.cos(i * phi), Math.sin(i * phi))

Complex is a number construct in Ruby. It looks like this: a+bi, for example 0.3+0i for 0.3
If you call Complex with two parameters, the first one will be the real part and the second the imaginary part. So this array will have i entries with each entry being a complex number.

If you later need to split the complex into its parts, you just call .real and .imag

Code: Select all

a = Complex(1, 0.53)
b = a.real # = 1
c = a.imag # = 0.53

In the code this is done at the end

Code: Select all

    //usage
    real = []
    imag = []

    @in.fft(false).each {|i| real.push i.real; imag.push i.imag}
    output 0, real; output 1, imag

this is going through the array and splitting each complex into real and imag, adding them to their own array.

[Youlean]

Ok, I think that I start to getting it... Can someone put this ruby fft into flowstone ruby so I can debug my code in dll more easily?
I think that I was someware ruby fft module but can not find it...

[martinvicanek]

Not sure how far you got, Youlean, but if you are trying to understand FFT and ruby does not (yet) feel comfortable then I'd recommend Numerical Recipes. The second edition is free and chapter 12 has it all on FFT, including C-code (or Fortran, if you prefer ).

[Youlean]

Not sure how far you got, Youlean, but if you are trying to understand FFT and ruby does not (yet) feel comfortable then I'd recommend Numerical Recipes. The second edition is free and chapter 12 has it all on FFT, including C-code (or Fortran, if you prefer ).

Well, I made DFT working so far. Thanks for the tip. I found many C algorithms but I can get it work.
I have tried this algorithms for example.
The strange thing is that DFT version works OK, but FFT not, it just return me values like they are on input and this is really strange because I tried 3 other FFT algorithms that are doing same thing...