fft.zip_acrossnck_fft_fft 算法_fft4g.c_快速傅里叶变换

General Purpose FFT (Fast Fourier/Cosine/Sine Transform) Package Description: A package to calculate Discrete Fourier/Cosine/Sine Transforms of 1-dimensional sequences of length 2^N. Files: fft4g.c : FFT Package in C - Fast Version I (radix 4,2) fft4g.f : FFT Package in Fortran - Fast Version I (radix 4,2) fft4g_h.c : FFT Package in C - Simple Version I (radix 4,2) fft8g.c : FFT Package in C - Fast Version II (radix 8,4,2) fft8g.f : FFT Package in Fortran - Fast Version II (radix 8,4,2) fft8g_h.c : FFT Package in C - Simple Version II (radix 8,4,2) fftsg.c : FFT Package in C - Fast Version III (Split-Radix) fftsg.f : FFT Package in Fortran - Fast Version III (Split-Radix) fftsg_h.c : FFT Package in C - Simple Version III (Split-Radix) readme.txt : Readme File sample1/ : Test Directory Makefile : for gcc, cc Makefile.f77: for Fortran testxg.c : Test Program for "fft*g.c" testxg.f : Test Program for "fft*g.f" testxg_h.c : Test Program for "fft*g_h.c" sample2/ : Benchmark Directory Makefile : for gcc, cc Makefile.pth: POSIX Thread version pi_fft.c : PI(= 3.1415926535897932384626...) Calculation Program for a Benchmark Test for "fft*g.c" Difference of the Files: C and Fortran versions are equal and the same routines are in each version. "fft4g*.*" are optimized for most machines. "fft8g*.*" are fast on the UltraSPARC. "fftsg*.*" are optimized for the machines that have the multi-level (L1,L2,etc) cache. The simple versions "fft*g_h.c" use no work area, but the fast versions "fft*g.*" use work areas. The fast versions "fft*g.*" have the same specification. Routines in the Package: cdft: Complex Discrete Fourier Transform rdft: Real Discrete Fourier Transform ddct: Discrete Cosine Transform ddst: Discrete Sine Transform dfct: Cosine Transform of RDFT (Real Symmetric DFT) dfst: Sine Transform of RDFT (Real Anti-symmetric DFT) Usage: Please refer to the comments in the "fft**.*" file which you want to use. Brief explanations are in the block comments of each package. The examples are also given in the test programs. Method: -------- cdft -------- fft4g*.*, fft8g*.*: A method of in-place, radix 2^M, Sande-Tukey (decimation in frequency). Index of the butterfly loop is in bit reverse order to keep continuous memory access. fftsg*.*: A method of in-place, Split-Radix, recursive fast algorithm. -------- rdft -------- A method with a following butterfly operation appended to "cdft". In forward transform : A[k] = sum_j=0^n-1 a[j]*W(n)^(j*k), 0<=k<=n/2, W(n) = exp(2*pi*i/n), this routine makes an array x[] : x[j] = a[2*j] + i*a[2*j+1], 0<=j<n/2 and calls "cdft" of length n/2 : X[k] = sum_j=0^n/2-1 x[j] * W(n/2)^(j*k), 0<=k<n. The result A[k] are : A[k] = X[k] - (1+i*W(n)^k)/2 * (X[k]-conjg(X[n/2-k])), A[n/2-k] = X[n/2-k] + conjg((1+i*W(n)^k)/2 * (X[k]-conjg(X[n/2-k]))), 0<=k<=n/2 (notes: conjg() is a complex conjugate, X[n/2]=X[0]). -------- ddct -------- A method with a following butterfly operation appended to "rdft". In backward transform : C[k] = sum_j=0^n-1 a[j]*cos(pi*j*(k+1/2)/n), 0<=k<n, this routine makes an array r[] : r[0] = a[0], r[j] = Re((a[j] - i*a[n-j]) * W(4*n)^j*(1+i)/2), r[n-j] = Im((a[j] - i*a[n-j]) * W(4*n)^j*(1+i)/2), 0<j<=n/2 and calls "rdft" of length n : A[k] = sum_j=0^n-1 r[j]*W(n)^(j*k), 0<=k<=n/2, W(n) = exp(2*pi*i/n). The result C[k] are : C[2*k] = Re(A[k] * (1-i)), C[2*k-1] = -Im(A[k] * (1-i)). -------- ddst -------- A method with a following butterfly operation appended to "rdft". In backward transform : S[k] = sum_j=1^n A[j]*sin(pi*j*(k+1/2)/n), 0<=k<n, this routine makes an array r[] : r[0] = a[0], r[j] = Im((a[n-j] - i*a[j]) * W(4*n)^j*(1+i)/2), r[n-j] = Re((a[n-j] - i*a[j]) * W(4*n)^j*(1+i)/2), 0<j<=n/2 and calls "rdft" of length n : A[k] = sum_j=0^n-1 r[j]*W(n)^(j*k), 0<=k<=n/2, W(n) = exp(2*pi*i/n). The result S[k] are : S[2*k] = Re(A[k] * (1+i)), S[2*k-1] = -Im(A[k] * (1+i)). -------- dfct -------- A method to split into "dfct" and "ddct" of half length. The transform : C[k] = sum_j=0^n a[j]*cos(pi*j*k/n), 0<=k<=n is divided into : C[2*k] = sum'_j=0^n/2 (a[j]+a[n-j])*cos(pi*j*k/(n/2)), C[2*k+1] = sum_j=0^n/2-1 (a[j]-a[n-j])*cos(pi*j*(k+1/2)/(n/2)) (sum' is a summation whose last term multiplies 1/2). This routine uses "ddct" recursively. To keep the in-place operation, the data in fft*g_h.* are sorted in bit reversal order. -------- dfst -------- A method to split into "dfst" and "ddst" of half length. The transform : S[k] = sum_j=1^n-1 a[j]*sin(pi*j*k/n), 0<k<n is divided into : S[2*k] = sum_j=1^n/2-1 (a[j]-a[n-j])*sin(pi*j*k/(n/2)), S[2*k+1] = sum'_j=1^n/2 (a[j]+a[n-j])*sin(pi*j*(k+1/2)/(n/2)) (sum' is a summation whose last term multiplies 1/2). This routine uses "ddst" recursively. To keep the in-place operation, the data in fft*g_h.* are sorted in bit reversal order. Reference: * Masatake MORI, Makoto NATORI, Tatuo TORII: Suchikeisan, Iwanamikouzajyouhoukagaku18, Iwanami, 1982 (Japanese) * Henri J. Nussbaumer: Fast Fourier Transform and Convolution Algorithms, Springer Verlag, 1982 * C. S. Burrus, Notes on the FFT (with large FFT paper list) http://www-dsp.rice.edu/research/fft/fftnote.asc Copyright: Copyright(C) 1996-2001 Takuya OOURA email: ooura@mmm.t.u-tokyo.ac.jp download: http://momonga.t.u-tokyo.ac.jp/~ooura/fft.html You may use, copy, modify this code for any purpose and without fee. You may distribute this ORIGINAL package. History: ... Dec. 1995 : Edit the General Purpose FFT Mar. 1996 : Change the specification Jun. 1996 : Change the method of trigonometric function table Sep. 1996 : Modify the documents Feb. 1997 : Change the butterfly loops Dec. 1997 : Modify the documents Dec. 1997 : Add "fft4g.*" Jul. 1998 : Fix some bugs in the documents Jul. 1998 : Add "fft8g.*" and delete "fft4f.*" Jul. 1998 : Add a benchmark program "pi_fft.c" Jul. 1999 : Add a simple version "fft*g_h.c" Jul. 1999 : Add a Split-Radix FFT package "fftsg*.c" Sep. 1999 : Reduce the memory operation (minor optimization) Oct. 1999 : Change the butterfly structure of "fftsg*.c" Oct. 1999 : Save the code size Sep. 2001 : Add "fftsg.f" Sep. 2001 : Add Pthread & Win32thread routines to "fftsg*.c" Dec. 2006 : Fix a minor bug in "fftsg.f"