库利-图基快速傅里叶变换算法(Cooley-Tukey算法)[1]是最常见的快速傅里叶变换算法。这一方法以分治法为策略递归地将长度为N = N1N2的DFT分解为长度分别为N1和N2的唡个较短序列的DFT,以及与旋转因子的複数乘法。这种方法以及FFT的基本思路在1965年J. W. Cooley和J. W. Tukey合作发表An algorithm for the machine calculation of complex Fourier series之後开始为人所知。但後来发现,实际上这唡位作者只是重新发明了高斯在1805年就已经提出的算法(此算法在历史上数次以各种形式被再次提出)。
! In place Cooley-Tukey FFT
recursive subroutine fft(x)
complex(kind=dp), dimension(:), intent(inout) :: x
complex(kind=dp) :: t
integer :: N
integer :: i
complex(kind=dp), dimension(:), allocatable :: even, odd
N=size(x)
if(N .le. 1) return
allocate(odd((N+1)/2))
allocate(even(N/2))
! divide
odd =x(1:N:2)
even=x(2:N:2)
! conquer
call fft(odd)
call fft(even)
! combine
do i=1,N/2
t=exp(cmplx(0.0_dp,-2.0_dp*pi*real(i-1,dp)/real(N,dp),kind=dp))*even(i)
x(i) = odd(i) + t
x(i+N/2) = odd(i) - t
end do
deallocate(odd)
deallocate(even)
end subroutine fft
end module fft_mod
program test
use fft_mod
implicit none
complex(kind=dp), dimension(8) :: data = (/1.0, 1.0, 1.0, 1.0, 0.0,
0.0, 0.0, 0.0/)
integer :: i
call fft(data)
do i=1,8
write(*,'("(", F20.15, ",", F20.15, "i )")') data(i)
end do
private double[] dft(double[] data)
{
int n = data.Length;
int m = n;// I use m = n / 2d;
double[] real = new double[n];
double[] imag = new double[n];
double[] result = new double[m];
double pi_div = 2.0 * Math.PI / n;
for (int w = 0; w < m; w++)
{
double a = w * pi_div;
for (int t = 0; t < n; t++)
{
real[w] += data[t] * Math.Cos(a * t);
imag[w] += data[t] * Math.Sin(a * t);
}
result[w] = Math.Sqrt(real[w] * real[w] + imag[w] * imag[w]) / n;
}
return result;
}
离散余弦变换(英语:DCT for Discrete Cosine Transform)是与傅里叶变换相关的一种变换,类似于离散傅里叶变换,但是只使用实数。离散余弦变换相当于一个长度大概是它两倍的离散傅里叶变换,这个离散傅里叶变换是对一个实偶函数进行的(因为一个实偶函数的傅里叶变换仍然是一个实偶函数),在有些变形里面需要将输入或者输出的位置移动半个单位(DCT有8种标准类型,其中4种是常见的)。