這兩天一直在研究FFT算法，研究了兩天總算整明白了快速傅里葉變換算法，今天就寫一篇文章來總結(jié)一下。

FFT和IFFT的Python語言實現(xiàn)源代碼

直接把我用了一個晚上寫好的快速傅里葉變換和快速傅里葉逆變換的Python語言代碼貼出，關鍵部分有注釋，里面只用到了Python標準庫cmath庫，因為要計算cos、sin函數(shù)的值。直接復制到自己的Python程序中就可以直接使用了。

"""
@Author: Sam
@Function: Fast Fourier Transform
@Time: 2020.02.22 16:00
"""
from cmath import sin, cos, pi

class FFT_pack():
    def __init__(self, _list=[], N=0):  # _list 是傳入的待計算的離散序列，N是序列采樣點數(shù)，對于本方法，點數(shù)必須是2^n才可以得到正確結(jié)果
        self.list = _list  # 初始化數(shù)據(jù)
        self.N = N
        self.total_m = 0  # 序列的總層數(shù)
        self._reverse_list = []  # 位倒序列表
        self.output =  []  # 計算結(jié)果存儲列表
        self._W = []  # 系數(shù)因子列表
        for _ in range(len(self.list)):
            self._reverse_list.append(self.list[self._reverse_pos(_)])
        self.output = self._reverse_list.copy()
        for _ in range(self.N):
            self._W.append((cos(2 * pi / N) - sin(2 * pi / N) * 1j) ** _)  # 提前計算W值，降低算法復雜度

    def _reverse_pos(self, num) -> int:  # 得到位倒序后的索引
        out = 0
        bits = 0
        _i = self.N
        data = num
        while (_i != 0):
            _i = _i // 2
            bits += 1
        for i in range(bits - 1):
            out = out << 1
            out |= (data >> i) & 1
        self.total_m = bits - 1
        return out

    def FFT(self, _list, N, abs=True) -> list:  # 計算給定序列的傅里葉變換結(jié)果，返回一個列表，結(jié)果是沒有經(jīng)過歸一化處理的
        """參數(shù)abs=True表示輸出結(jié)果是否取得絕對值"""
        self.__init__(_list, N)
        for m in range(self.total_m):
            _split = self.N // 2 ** (m + 1)
            num_each = self.N // _split
            for _ in range(_split):
                for __ in range(num_each // 2):
                    temp = self.output[_ * num_each + __]
                    temp2 = self.output[_ * num_each + __ + num_each // 2] * self._W[__ * 2 ** (self.total_m - m - 1)]
                    self.output[_ * num_each + __] = (temp + temp2)
                    self.output[_ * num_each + __ + num_each // 2] = (temp - temp2)
        if abs == True:
            for _ in range(len(self.output)):
                self.output[_] = self.output[_].__abs__()
        return self.output

    def FFT_normalized(self, _list, N) -> list:  # 計算給定序列的傅里葉變換結(jié)果，返回一個列表，結(jié)果經(jīng)過歸一化處理
        self.FFT(_list, N)
        max = 0   # 存儲元素最大值
        for _ in range(len(self.output)):
            if max < self.output[_]:
                max = self.output[_]
        for _ in range(len(self.output)):
            self.output[_] /= max
        return self.output

    def IFFT(self, _list, N) -> list:  # 計算給定序列的傅里葉逆變換結(jié)果，返回一個列表
        self.__init__(_list, N)
        for _ in range(self.N):
            self._W[_] = (cos(2 * pi / N) - sin(2 * pi / N) * 1j) ** (-_)
        for m in range(self.total_m):
            _split = self.N // 2 ** (m + 1)
            num_each = self.N // _split
            for _ in range(_split):
                for __ in range(num_each // 2):
                    temp = self.output[_ * num_each + __]
                    temp2 = self.output[_ * num_each + __ + num_each // 2] * self._W[__ * 2 ** (self.total_m - m - 1)]
                    self.output[_ * num_each + __] = (temp + temp2)
                    self.output[_ * num_each + __ + num_each // 2] = (temp - temp2)
        for _ in range(self.N):  # 根據(jù)IFFT計算公式對所有計算列表中的元素進行*1/N的操作
            self.output[_] /= self.N
            self.output[_] = self.output[_].__abs__()
        return self.output

    def DFT(self, _list, N) -> list:  # 計算給定序列的離散傅里葉變換結(jié)果，算法復雜度較大，返回一個列表，結(jié)果沒有經(jīng)過歸一化處理
        self.__init__(_list, N)
        origin = self.list.copy()
        for i in range(self.N):
            temp = 0
            for j in range(self.N):
                temp += origin[j] * (((cos(2 * pi / self.N) - sin(2 * pi / self.N) * 1j)) ** (i * j))
            self.output[i] = temp.__abs__()
        return self.output





if __name__ == '__main__':
   list = [1, 2, 3, 4, 5, 6, 7, 8, 0, 0, 0, 0, 0, 0, 0, 0]
   a = FFT_pack().FFT(list, 16, False)
   print(a)

下面對源代碼的一些關鍵部分進行解釋：
我直接將計算方法的調(diào)用封裝成了一個類，這樣可以很方便進行擴展和調(diào)用。在FFT_pack（）這個類之中，我定義了下面的幾種方法
1.構(gòu)造函數(shù)__init__()，目的是初始化需要進行FFT變換的序列，對采樣點數(shù)進行賦值、計算分治算法需要進行分組的層數(shù)，計算旋轉(zhuǎn)因子的系數(shù)列表等。
2._reverse_pos()方法，是為了獲得位倒序后的順序，這個方法是一個不需要外部調(diào)用的方法。
3.FFT()方法，顧名思義，是計算給定序列的快速傅里葉變換結(jié)果。里面涉及到四個參數(shù)，在實際調(diào)用的時候需要傳入三個參數(shù)-list N abs。_list參數(shù)是需要進行FFT運算的列表，N參數(shù)是參加計算的點的個數(shù)，注意： 這里面N的值必須是2的m次方，例如N可以是2、4、8、16、32、……1024、2048、4096等這樣的數(shù)，如果填入了別的數(shù)，無法得到正確的計算結(jié)果。 abs參數(shù)是缺省值為True的參數(shù)，當abs賦值為True或者使用缺省值的時候，返回的FFT運算結(jié)果是取絕對值以后的序列，當abs參數(shù)賦值為False時，返回的FFT運算結(jié)果就是一個復數(shù)，含有實部和虛部的值。
4.FFT_normalized()方法，用法與FFT()方法類似，只不過沒有abs參數(shù)，方法的返回值是經(jīng)過歸一化處理的FFT變換結(jié)果。
5.IFFT()方法，返回給定序列的快速傅里葉逆變換的序列。
6.DFT()方法，返回給定序列的離散傅里葉變換序列，返回結(jié)果是經(jīng)過取絕對值運算的。這個DFT（）方法主要是用來與FFT方法的運算性能進行對比的，實際使用中還是使用FFT方法。