傅立葉變換最開(kāi)始是在大學(xué)時(shí)學(xué)過(guò)的孙援，當(dāng)初的印象是它跟音頻圖像有關(guān)系颜阐，各種時(shí)領(lǐng)頻域的名詞讓人很容易混淆跪解，而且教材解說(shuō)得很生澀，學(xué)過(guò)之后大都忘得一干二凈楷兽。偶然看見(jiàn)知乎上有一篇文章詳細(xì)生動(dòng)地具體描述了傅立葉變換的含義地熄，看過(guò)后令人印象深刻。傅立葉變換具體內(nèi)容都在這個(gè)鏈接里面芯杀，在這篇文章里面就不再?gòu)?fù)述端考，這里只是說(shuō)它的應(yīng)用和代碼實(shí)現(xiàn)，為了保證運(yùn)算速度代碼用的是C語(yǔ)言實(shí)現(xiàn)揭厚。
現(xiàn)實(shí)生活中很多信息或者說(shuō)是信號(hào)大都不是連續(xù)的却特，而是離散的。因此這篇文章說(shuō)的傅立葉變換只針對(duì)離散傅立葉變換筛圆。

傅立葉變換(DFT)公式如下所示：（簡(jiǎn)書(shū)上不能使用 MathJax 編輯公式 裂明，有點(diǎn)遺憾,只能截圖）

DFT公式.png

x(n)為輸入函數(shù)，x(k) 由實(shí)數(shù)和虛數(shù)組成（ x(k) ( 0 < k < N -1) 是x(n) 中任意某一個(gè)點(diǎn)） X(k)則為傅立葉變換后的函數(shù)
該公式的算法復(fù)雜度是O(N^2)
為了方便用代碼寫(xiě)出來(lái)可以將這個(gè)公式拆分:
設(shè)

公式1.png

然后DFT公式可轉(zhuǎn)換為：

公式2.png

公式3.png

由公式三可以寫(xiě)出DFT公式

/**
 離散傅立葉變換
 
 @param x 原始實(shí)數(shù)
 @param y 原始虛數(shù)
 @param a 變換后實(shí)數(shù)
 @param b 變換后虛數(shù)
 @param N 變換的個(gè)數(shù)
 @param sign 為 -1時(shí) 表示進(jìn)行逆變換
 */
void dft(double x[],double y[],double *a, double *b, int N,int sign){
    float q ,W,d,c,s;
    q = 2 * M_PI/N;
    for (int k = 0; k < N ; k++) {
        a[k] = b[k] = 0;
        W = q * k;
        for (int  n = 0; n < N; n++) {
            d = W * n;
            c = cos(d);
            s =  sin(d) * sign;
            a[k] += x[n]*c + y[n]*s;
            b[k] += y[n]*c - x[n]*s;
        }
    }
    if(sign == -1){
        c = 1.0/N;
        for (int k = 0; k < N ; k++) {
            a[k] = c * a[k];
            b[k] = c * b[k];
        }
    }
}

通常來(lái)說(shuō)太援，一般應(yīng)用傅立葉變換處理的數(shù)據(jù)量是比較大的闽晦，復(fù)雜度O(N^2)這個(gè)方法無(wú)法保證程序高效率運(yùn)行。因而出現(xiàn)了快速傅立葉變換（FFT）粉寞。
FFT是在DFT的基礎(chǔ)上進(jìn)行的快速變換：
x(n)可以根據(jù)奇偶數(shù)拆分：

公式4.png

結(jié)合公式4和DFT公式得出

公式5.png

由于權(quán)系數(shù)W有對(duì)稱性

公式6.png

因而有以下公式：

公式7.png

將x(n)不斷按照上面方式拆分直至無(wú)法拆分為止尼荆，這樣就有如下圖形算法的出現(xiàn)

FFT.jpeg

上圖算法稱為蝶形算法，圖中 W(k,N)為旋轉(zhuǎn)因子
每個(gè)蝶形算拆分如下：

FFT_SPLIT.png

FFT算法復(fù)雜度是O(N*log2N)
FFT算法的前提是N必須保證是N的2次冪唧垦，如果不夠則補(bǔ)零直到條件成立為止。
公式看起來(lái)麻煩其實(shí)理解后也很簡(jiǎn)單液样。算法介紹完畢就開(kāi)始寫(xiě)代碼振亮。

快速傅立葉變換（FFT）

/**
 離散快速傅立葉變換
 @param x 原始實(shí)數(shù) 函數(shù)結(jié)束后保存變換后的實(shí)數(shù)數(shù)值
 @param y 原始虛數(shù) 函數(shù)結(jié)束后保存變換后的虛數(shù)數(shù)值
 @param N 變換的個(gè)數(shù)
 @param sign 為 -1時(shí) 表示進(jìn)行逆變換
 */
void FFT(double x[],double y[], int N,int sign){
    
    int i,j,k,L,m = 0,n1,n2;
    double c,c1,e,s,s1,t,tr,ti;
    double M = log2(N);
    if(floor(M) != ceil(M)){
        double *a =  (double *)malloc(sizeof(double) * N);
        double *b =  (double *)malloc(sizeof(double) * N);
        dft(x, y, a, b, N, 1);
        for (int i = 0; i < N; i++) {
            x[i] = a[i];
            y[i] = b[i];
        }
        free(a);
        free(b);
        
    }else{
        m = M;
    
    n1 = N - 1;
    for (j = 0, i = 0;i < n1;i++){
        if(i < j){
            tr = x[j];
            ti = y[j];
            x[j] = x[i];
            y[j] = y[i];
            x[i] = tr;
            y[i] = ti;
        }
        k = N/2;
        while (k < (j+1)) {
            j = j - k;
            k = k/2;
        }
        j = j + k;
    }
    n1 = 1;
    for (L = 1;L <= m;L++){
        n1 = 2 * n1;
        n2 = n1/2;
        e = M_PI/n2;
        c = 1.0;
        s = 0.0;
        c1 = cos(e);
        s1 = -sign * sin(e);
        for (j = 0; j < n2; j++) { // [0..1)  [0..2)  [0..4)
            for (i = j; i < N; i += n1) {
                k = i + n2;
                tr = c * x[k] - s * y[k];
                ti = c * y[k] + s * x[k];
                x[k] = x[i] - tr;
                y[k] = y[i] - ti;
                x[i] = x[i] + tr;
                y[i] = y[i] + ti;
            }
            t = c;
            c = c*c1 - s * s1;
            s = t * s1 + s * c1;
        }
    }
    if(sign == -1){
        for (i = 0; i < N; i++) {
            x[i] /= (N * 1.0);
            y[i] /= (N * 1.0);
        }
    }
        }
}

以上就是所有內(nèi)容，下一篇文章就講講下傅立葉變換在開(kāi)發(fā)中的應(yīng)用鞭莽。該歇會(huì)了坊秸。。澎怒。
博客原文：click here