Re: FFT and DFT

in article 4415D32C.3B47ECE5@xxxxxxxxxxx, Mike Fontenot at
mlfasf@xxxxxxxxxxx wrote on 3/13/06 2:16 PM:

laguiche2004@xxxxxxxx wrote:

I use the function cvDFT (OpenCV library) in Visual C++. But i don't
find the same Matlab 's result with the function fft2. Why?

for the vector [0 0 1], Matlab return [1, -0.5+0.866i, -0.5-0.866i],
and with the function cvDFT in OpenCV i have [1, 1, -0.5-0.86i] for the
same vector.


I haven't used either package, but the fft requires that the number
of samples be a power of 2, whereas the dft doesn't restrict the
number of samples. Your input has three samples, so you have to
use the dft, not the fft. It may be that the fft program accepts
your input, and pads a zero on the end to get four samples...but the
spectrum of the resulting signal is different than for just the
original three samples (because the dft and fft basically consider the
samples to be one period of a periodic stream).

Mike Fontenot
The "Fast" Fourier transform is fast (faster than simply implementing the
definition of the discrete FT) when the number of samples can be factored
(i.e., the number is not a prime). The details of the FFT algorithm exploit
the factored form of the number, and the greatest speed gain occurs when the
number is a power of 2. More or less, a power of two can be factored "the
most." Some implementations of the FFT may be limited to powers of 2, but
complete implementations of the algorithm do not.

As another poster points out, some implementations may cheat by "padding"
the end of the sample vector with enough 0s to make the augmented number of
samples a power of 2.

.

Relevant Pages

  • Re: FFT for N Not a Power of 2
    ... remove the largest number of observations that are a power of 2, ... There are FFT algorithms that work for any N, including prime numbers, but ... with floor rising near the two tones. ... had to ensure that the length of the window and periods of each of the ...
    (sci.optics)
  • Re: Why is more power required for BASS?
    ... Beware of FFT - that shows energy, not power. ... a steady 1V RMS 1 kHz tone may display ...
    (rec.audio.pro)
  • Re: Windowed FFT power and amplitude spectrum
    ... PS: You can find a nice explenation about coherent power gain on this page: ... > Here is another fascinating question on FFT spectrum!! ... > windowing is applied to the time series before FFT is applied. ... > multiplied by a scaling factor but I am not sure how this scaling factor ...
    (comp.dsp)
  • Re: zero padding radix - 2 FFT
    ... FFT with an odd size. ... Zero padding the FFT to the next power of two ... Now zero pad to the next power of two. ...
    (comp.dsp)
  • Re: what is the frequncy spectrum of a clock signal?
    ... I plotted the FFT of the signal in MATLAB but I didn't get ... power should be concentrated at the fundamental frequency (ie the ... fundamental frequency and not the base freq. ... Is there a non-zero DC offset to your clock signal? ...
    (comp.dsp)