Difference between revisions of "Discrete Fourier transform"

Latest revision as of 14:49, 23 March 2008

The DFT has no restrictions on array size (n) and is hard to get wrong. It is a very expensive transform that takes O*n² operations.

'Complex Forward transform
For i = 0 To n - 1
   arg = -(2 * PI * i) / n
   For k = 0 To n - 1
       cosarg = Cos(k * arg)
       sinarg = Sin(k * arg)
       dataOutR(i) = dataOutR(i) + (dataInR(k) * cosarg - dataInI(k) * sinarg)
       dataOutI(i) = dataOutI(i) + (dataInR(k) * sinarg + dataInI(k) * cosarg)
   Next k
   dataOutR(i) = dataOutR(i) / n
   dataOutI(i) = dataOutI(i) / n
Next i

'Real Forward transform
For i = 0 To n - 1
   arg = -(2 * PI * i) / n
   For k = 0 To n - 1
       dataOutR(i) = dataOutR(i) + (dataInR(k) * Cos(k * arg) + (dataInR(k) * Sin(k * arg))
   Next k
   dataOutR(i) = dataOutR(i) / n
Next i

'Complex Reverse transform
For i = 0 To n - 1
   arg = (2 * PI * i) / n
   For k = 0 To n - 1
       cosarg = Cos(k * arg)
       sinarg = Sin(k * arg)
       dataOutR(i) = dataOutR(i) + (dataInR(k) * cosarg - dataInI(k) * sinarg)
       dataOutI(i) = dataOutI(i) + (dataInR(k) * sinarg + dataInI(k) * cosarg)
   Next k
Next i

'Real Reverse transform
For i = 0 To n - 1
   arg = (2 * PI * i) / n
   For k = 0 To n - 1
       dataOutR(i) = dataOutR(i) + (dataInR(k) * Cos(k * arg) + (dataInR(k) * Sin(k * arg))
   Next k
Next i