庫利－圖基快速傅裡葉變換算法（Cooley-Tukey算法） (發表於7年前)

三叔 · 上一次由三叔於2046-12-26 9:18am修改，總共修改了11次

庫利－圖基快速傅裡葉變換算法（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等變種。儘管庫利－圖基算法的基本思路是採用递箼澳方法进行紦溷，大多数传蛙嚹算法实现都将显淑R牡莨樗惴ǜ男次塹莨櫚男問健Ａ磽猓蛭飫薊惴ㄊ牆獶FT分解為較小長度的多個DFT，因此它可以同任一種其他的DFT算法聯合使用。

allsignalprocessing.com/

Algorithms: The Fast Fourier Transform ( FFT)

三叔 · 上一次由三叔於2046-12-26 9:18am修改，總共修改了11次

離散傅裡葉變換（Discrete Fourier Transform，縮寫為DFT），是傅裡葉變換在時域和頻域上都呈離散的形式，將信號的時域采樣變換為其DTFT的頻域采樣。在形式上，變換兩端（時域和頻域上）的序列是有限長的，而實際上這兩組序列都應當被認為是離散周期信號的主值序列。即使對有限長的離散信號作DFT，也應當將其看作其周期延拓的變換。在實際應用中通常采用快速傅裡葉變換計算DFT。

三叔 · 上一次由三叔於2046-12-26 9:18am修改，總共修改了11次

對於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}}}

。

三叔 · 上一次由三叔於2046-12-26 9:18am修改，總共修改了11次

歐拉公式（英語：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}

為複數時仍然成立，所以也有人將這一更通用的版本稱為尤拉公式。

三叔 · 上一次由三叔於2046-12-26 9:18am修改，總共修改了11次

代碼:








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

三叔 · 上一次由三叔於2046-12-26 9:18am修改，總共修改了11次

代碼:






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;

}

被禁止的用戶

不懂，幫頂頂頂頂

三叔 · 上一次由三叔於2046-12-26 9:18am修改，總共修改了11次

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

Mastering The Fourier Transform in One Day

一天征服傅裡葉變換

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

三叔 · 上一次由三叔於2046-12-26 9:18am修改，總共修改了11次

傅裡葉分析之掐死教程（完整版）更新於2014.06.06

zhuanlan.zhihu.com/p/19763358

三叔 · 上一次由三叔於2046-12-26 9:18am修改，總共修改了11次

離散余弦變換（英語：DCT for Discrete Cosine Transform）是與傅裡葉變換相關的一種變換，類似於離散傅裡葉變換，但是只使用實數。離散余弦變換相當於一個長度大概是它兩倍的離散傅裡葉變換，這個離散傅裡葉變換是對一個實偶函數進行的（因為一個實偶函數的傅裡葉變換仍然是一個實偶函數），在有些變形裡面需要將輸入或者輸出的位置移動半個單位（DCT有8種標准類型，其中4種是常見的）。

最常用的一種離散余弦變換的類型是下面給出的第二種類型，通常我們所說的離散余弦變換指的就是這種。它的逆，也就是下面給出的第三種類型，通常相應的被稱為"反離散余弦變換"，"逆離散余弦變換"或者"IDCT"。

有兩個相關的變換，一個是離散正弦變換，它相當於一個長度大概是它兩倍的實奇函數的離散傅裡葉變換；另一個是改進的離散余弦變換，它相當於對交疊的數據進行離散余弦變換。