Matlab FFT function

As you Know Matlab FFT function is built in.
Anybody knows what algorithm has been implemented in it?
I mean with details.

I think you can check any book about digital signal processing.

in article 1115698065.510477.87350@z14g2000cwz.googlegroups.com, reseter at
fangzheng1980@gmail.com wrote on 05/10/2005 00:07:

> I think you can check any book about digital signal processing.

but there are many ways of doing an FFT.  even if you were to restrict it to
powers of 2 (which isn't the case for MATLAB).  i think the OP wants to know
which particular one of those many methods that is intrinsic to MATLAB.
it's probably a decimation-in-time or decimation-in-frequency algorithm.
both have various rearrangements as can be seen in Oppenheim & Schafer.

the other thing to point out is that the MATLAB FFT is off by 1 in its
indices because they still just don't get it in Natick Mass.


�help fft

 FFT Discrete Fourier transform.
    FFT(X) is the discrete Fourier transform (DFT) of vector X.  If the
    length of X is a power of two, a fast radix-2 fast-Fourier
    transform algorithm is used.  If the length of X is not a
    power of two, a slower non-power-of-two algorithm is employed.
    For matrices, the FFT operation is applied to each column.
    For N-D arrays, the FFT operation operates on the first
    non-singleton dimension.
 
    FFT(X,N) is the N-point FFT, padded with zeros if X has less
    than N points and truncated if it has more.
 
    FFT(X,[],DIM) or FFT(X,N,DIM) applies the FFT operation across the
    dimension DIM.
    
    For length N input vector x, the DFT is a length N vector X,
    with elements
                     N
       X(k) =       sum  x(n)*exp(-j*2*pi*(k-1)*(n-1)/N), 1 <= k <= N.
                    n=1
    The inverse DFT (computed by IFFT) is given by
                     N
       x(n) = (1/N) sum  X(k)*exp( j*2*pi*(k-1)*(n-1)/N), 1 <= n <= N.
                    k=1
 
    The relationship between the DFT and the Fourier coefficients a and b in
                N/2
    x(n) = a0 + sum
a(k)*cos(2*pi*k*t(n)/(N*dt))+b(k)*sin(2*pi*k*t(n)/(N*dt))
                k=1
    is
       a0 = 2*X(1)/N, a(k) = 2*real(X(k+1))/N, b(k) = 2*imag(X(k+1))/N,
    where x is a length N discrete signal sampled at times t with spacing
dt.
 
    See also IFFT, FFT2, IFFT2, FFTSHIFT.


-- 

r b-j                  rbj@audioimagination.com

"Imagination is more important than knowledge."

ALIMAR wrote:
> As you Know Matlab FFT function is built in.
> Anybody knows what algorithm has been implemented in it?
> I mean with details.

According to the rumour, matlab uses the FFTW library.
Check out the documentation for the library to find 
details.

Rune

Rune Allnor wrote:
> 
> ALIMAR wrote:
> > As you Know Matlab FFT function is built in.
> > Anybody knows what algorithm has been implemented in it?
> > I mean with details.
> 
> According to the rumour, matlab uses the FFTW library.

More than a rumor:

    http://www.mathworks.com/access/helpdesk/help/techdoc/ref/fftw.html

If they do they must have licensed the right to do so
from MIT:

    http://www.fftw.org/doc/License-and-Copyright.html

Erik
-- 
+-----------------------------------------------------------+
  Erik de Castro Lopo  nospam@mega-nerd.com (Yes it's valid)
+-----------------------------------------------------------+
"The object-oriented model makes it easy to build up programs by
accretion. What this often means, in practice, is that it provides
a structured way to write spaghetti code." -- Paul Graham