库利－图基快速傅里叶变换算法（Cooley-Tukey算法）

论坛 > 库利－图基快速傅里叶变换算法（Cooley-Tukey算法）

作者内容

三叔

三叔于 2017-1-20 03:26 写道:

库利－图基快速傅里叶变换算法（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年就已经提出的算法（此算法在历史上数次以各种形式被再次提出）。

库利－图基算法最有名的应用，是将序列长为N的DFT分割为唡个长为N/2的子序列的DFT，因此这一应用只适用於序列长度为2的幂的DFT计算，即基2-FFT。实际上，如同高斯和库利与图基都指出的那样，库利－图基算法也可以用於序列长度N为任意因数分解形式的DFT，即混合基FFT，而且还可以应用於其他诸如分裂基FFT等变种。儘管库利－图基算法的基本思路是採用递归的方法进行计算，大多数传统的算法实现都将显示的递归算法改写为非递归的形式。另外，因为库利－图基算法是将DFT分解为较小长度的多个DFT，因此它可以同任一种其他的DFT算法联合使用。

allsignalprocessing.com/

Algorithms: The Fast Fourier Transform ( FFT)

楼主

三叔

三叔于 2017-1-20 03:28 写道:

离散傅里叶变换（Discrete Fourier Transform，缩写为DFT），是傅里叶变换在时域和频域上都呈离散的形式，将信号的时域采样变换为其DTFT的频域采样。在形式上，变换两端（时域和频域上）的序列是有限长的，而实际上这两组序列都应当被认为是离散周期信号的主值序列。即使对有限长的离散信号作DFT，也应当将其看作其周期延拓的变换。在实际应用中通常采用快速傅里叶变换计算DFT。

第 1 楼

三叔

三叔于 2017-1-20 03:29 写道:

对于N点序列{\displaystyle \left\{x[n]\right\}_{0\leq n<N}}

，它的离散傅里叶变换（DFT）为

{\displaystyle {\hat {x}}[k]=\sum _{n=0}^{N-1}e^{-i{\frac {2\pi }{N}}nk}x[n]\qquad k=0,1,\ldots ,N-1.}

其中{\displaystyle e}

是自然对数的底数，{\displaystyle i}

是虚数单位。通常以符号{\displaystyle {\mathcal {F}}}

表示这一变换，即

{\displaystyle {\hat {x}}={\mathcal {F}}x}

离散傅里叶变换的逆变换（IDFT）为：

{\displaystyle x\left[n\right]={1 \over N}\sum _{k=0}^{N-1}e^{i{\frac {2\pi }{N}}nk}{\hat {x}}[k]\qquad n=0,1,\ldots ,N-1.}

可以记为：

{\displaystyle x={\mathcal {F}}^{-1}{\hat {x}}}

实际上，DFT和IDFT变换式中和式前面的归一化系数并不重要。在上面的定义中，DFT和IDFT前的系数分别为1和1/N。有时会将这两个系数都改成{\displaystyle 1/{\sqrt {N}}}

。

第 2 楼

三叔

三叔于 2017-1-20 03:31 写道:

欧拉公式（英语：Euler's formula，又称尤拉公式）是在複分析领域的公式，将三角函数与複数指数函数相关联，因其提出者莱昂哈德·欧拉而得名。尤拉公式提出，对任意实数 {\displaystyle x}

，都存在

{\displaystyle e^{ix}=\cos x+i\sin x}

其中 {\displaystyle e}

是自然对数的底数，{\displaystyle i}

是虚数单位，而 {\displaystyle \cos }

和 {\displaystyle \sin }

则是馀弦、正弦对应的三角函数，参数 {\displaystyle x}

则以弧度为单位。这一複数指数函数有时还写作 {\displaystyle \operatorname {cis} (x)}

（英语：cosine plus i sine，余弦加 i 正弦）。由於该公式在 {\displaystyle x}

为複数时仍然成立，所以也有人将这一更通用的版本称为尤拉公式。

第 3 楼

三叔

三叔于 2017-1-20 03:33 写道:

代码:








module fft_mod

  implicit none

  integer,       parameter :: dp=selected_real_kind(15,300)

  real(kind=dp), parameter :: pi=3.141592653589793238460_dp

contains

 

  ! 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

 

end program test

第 4 楼

三叔

三叔于 2017-1-20 03:35 写道:

代码:






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;

}

第 5 楼

不喜请拉黑

不喜请拉黑 于 2017-1-20 03:58 写道:

不懂，帮顶顶顶顶

第 6 楼

三叔

三叔于 2017-1-20 05:54 写道:

blogs.zynaptiq.com/ber...ft-a-pied/

Mastering The Fourier Transform in One Day

一天征服傅里叶变换

read.pudn.com/download...BC%8D1.pdf

第 7 楼

三叔

三叔于 2017-1-20 05:56 写道:

傅里叶分析之掐死教程（完整版）更新于2014.06.06

zhuanlan.zhihu.com/p/19763358

第 8 楼

三叔

三叔于 2017-1-20 08:18 写道:

离散余弦变换（英语：DCT for Discrete Cosine Transform）是与傅里叶变换相关的一种变换，类似于离散傅里叶变换，但是只使用实数。离散余弦变换相当于一个长度大概是它两倍的离散傅里叶变换，这个离散傅里叶变换是对一个实偶函数进行的（因为一个实偶函数的傅里叶变换仍然是一个实偶函数），在有些变形里面需要将输入或者输出的位置移动半个单位（DCT有8种标准类型，其中4种是常见的）。

最常用的一种离散余弦变换的类型是下面给出的第二种类型，通常我们所说的离散余弦变换指的就是这种。它的逆，也就是下面给出的第三种类型，通常相应的被称为"反离散余弦变换"，"逆离散余弦变换"或者"IDCT"。

有两个相关的变换，一个是离散正弦变换，它相当于一个长度大概是它两倍的实奇函数的离散傅里叶变换；另一个是改进的离散余弦变换，它相当于对交叠的数据进行离散余弦变换。

第 9 楼