📄 fft.html
字号:
<HTML><HEAD><TITLE>Newmat09 - fast Fourier transform</TITLE></HEAD><BODY><H2>Fast Fourier transform</H2><A HREF="trigtran.html"> next</A> - <A HREF="trigtran.html"> skip</A> - <A HREF="refer.html"> up</A> - <A HREF="index.html"> start</A><P><PRE> FFT(X, Y, F, G); // F=X and G=Y are OK</PRE>where <TT>X</TT>, <TT>Y</TT>, <TT>F</TT>, <TT>G</TT> are column vectors.<TT>X</TT> and <TT>Y</TT> are the real and imaginaryinput vectors; <TT>F</TT> and <TT>G</TT> are the real and imaginaryoutput vectors. Thelengths of <TT>X</TT> and <TT>Y</TT> must be equal and should be theproduct of numbers less than about 10 for fast execution.<P>The formula is<PRE> n-1 h[k] = SUM z[j] exp (-2 pi i jk/n) j=0</PRE>where <TT>z[j]</TT> is stored complex and stored in <TT>X(j+1)</TT>and <TT>Y(j+1)</TT>. Likewise<TT>h[k]</TT> is complex and stored in <TT>F(k+1)</TT> and <TT>G(k+1)</TT>.The fast Fourieralgorithm takes order n log(n) operations (for <I>good</I> values of n)rather than n**2 that straight evaluation would take.<P>I use the method of Carl de Boor (1980), <I>Siam J Sci Stat Comput</I>, pp173-8. The sines and cosines are calculated explicitly. This givesbetter accuracy, at an expense of being a little slower than isotherwise possible.<P>Related functions<PRE> FFTI(F, G, X, Y); // X=F and Y=G are OK RealFFT(X, F, G); RealFFTI(F, G, X);</PRE><TT>FFTI</TT> is the inverse transform for <TT>FFT</TT>.<TT>RealFFT</TT> is for the case when theinput vector is real, that is <TT>Y = 0</TT>. I assume the length of <TT>X</TT>,denoted by n, is even. The program sets the lengths of <TT>F</TT>and <TT>G</TT> to n/2 + 1. <TT>RealFFTI</TT> is the inverse of <TT>RealFFT</TT>.<P>See also the section on fast <A HREF="trigtran.html">trigonometric transforms</A>.<P><A HREF="trigtran.html"> next</A> - <A HREF="trigtran.html"> skip</A> - <A HREF="refer.html"> up</A> - <A HREF="index.html"> start</A><P></BODY></HTML>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -