Reply by Erik de Castro Lopo●May 10, 20052005-05-10
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
Reply by Rune Allnor●May 10, 20052005-05-10
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
Reply by robert bristow-johnson●May 10, 20052005-05-10
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."
Reply by reseter●May 10, 20052005-05-10
I think you can check any book about digital signal processing.
Reply by ALIMAR●May 9, 20052005-05-09
As you Know Matlab FFT function is built in.
Anybody knows what algorithm has been implemented in it?
I mean with details.