python實現(xiàn)FFT快速傅立葉變換算法案例

更新時間：2024年10月21日 09:48:29 作者：luthane

FFT（快速傅里葉變換）是計算DFT及其逆變換的一種算法,其基本思想是利用DFT的對稱性和周期性,通過分而治之的策略將DFT分解為更小的DFT,從而降低計算復雜度,FFT的算法步驟包括選擇分解、重新排序、蝶形運算和逐層計算,在Python中

FFT快速傅里葉變換介紹

FFT（快速傅里葉變換）是計算離散傅里葉變換（DFT）及其逆變換的一種高效算法。

DFT是一種將信號從時域轉換到頻域的數(shù)學工具，而FFT通過減少計算量來加速這一過程。

FFT的基本思想

FFT利用了DFT中的對稱性和周期性，通過分而治之的策略將DFT分解為更小的DFT，從而顯著減少計算復雜度。
對于長度為N的序列，直接計算DFT的復雜度是O(N^2)，而FFT的復雜度可以降低到O(N log N)。

FFT的算法步驟（以Cooley-Tukey算法為例）

選擇分解：首先，將N（序列長度）分解為兩個較小的因子，通常是選擇N的偶數(shù)因子。最常見的分解是將N分解為兩個相等的因子（即N為2的冪）。
重新排序（位反轉）：對輸入序列進行位反轉排序，這是為了將輸入序列重新排列成一種便于后續(xù)處理的順序。
蝶形運算：FFT算法的核心是蝶形運算。在蝶形運算中，兩個輸入（通常來自序列的特定位置）通過一系列乘法和加法操作結合成一個輸出。這個過程在算法的不同層級上重復進行。
逐層計算：FFT算法通過逐層（從最低層到最高層）應用蝶形運算來計算DFT。每一層都基于前一層的輸出，并且每一層的計算都更加接近最終的DFT結果。

Python FFT快速傅立葉變換

在Python中，實現(xiàn)快速傅里葉變換（FFT）的一種簡便方法是使用numpy庫中的fft模塊。numpy提供了高效的FFT算法實現(xiàn)，能夠處理一維或多維數(shù)組。

以下是一個簡單的例子，展示如何使用numpy中的fft.fft函數(shù)來計算一維數(shù)組的FFT。

首先，確保你已經安裝了numpy庫。如果沒有安裝，可以通過pip安裝：

pip install numpy

然后，你可以使用以下Python代碼來計算FFT：

import numpy as np
import matplotlib.pyplot as plt

# 創(chuàng)建一個樣本信號，例如一個包含正弦波和余弦波的復合信號
Fs = 1000  # 采樣頻率
T = 1/Fs  # 采樣周期
L = 1500  # 信號長度
t = np.linspace(0, L-1, L)*T  # 時間向量

# 創(chuàng)建一個復合信號
S = 0.7*np.sin(2*np.pi*50*t) + np.sin(2*np.pi*120*t)

# 使用numpy的fft函數(shù)計算FFT
Y = np.fft.fft(S)

# 獲取FFT的頻率軸
P2 = np.abs(Y/L)
P1 = P2[:L//2+1]
P1[1:-1] = 2*P1[1:-1]  # 去除對稱性
f = Fs*np.arange(0,(L//2+1))/L

# 繪制FFT的幅度譜
plt.figure()
plt.plot(f, P1) 
plt.title('Single-Sided Amplitude Spectrum of S(t)')
plt.xlabel('f (Hz)')
plt.ylabel('|P1(f)|')
plt.show()

在這個例子中，我們首先生成了一個包含兩個不同頻率正弦波的復合信號S。然后，我們使用numpy.fft.fft函數(shù)計算了信號的FFT。為了獲得FFT的幅度譜，我們計算了Y的絕對值并除以信號長度L，以得到歸一化的幅度。由于FFT的結果是對稱的（對于實數(shù)輸入），我們通常只關注一半的頻率范圍，并相應地調整幅度（將一半的頻率范圍中的幅度加倍，除了第一個和最后一個點）。最后，我們使用matplotlib庫繪制了FFT的幅度譜。

注意：

這個例子僅用于演示如何在Python中使用numpy庫進行FFT計算。
在實際應用中，你可能需要根據(jù)你的具體需求調整信號生成、FFT計算以及結果分析的方式。

FFT（快速傅立葉變換）是一種計算離散傅立葉變換（DFT）的快速算法，用于將信號從時域轉換為頻域。

在Python中，可以使用NumPy庫進行FFT的實現(xiàn)。

FFT python樣例

下面是一個使用NumPy實現(xiàn)FFT的示例代碼：

import numpy as np

def fft(x):
    N = len(x)
    if N <= 1:
        return x
    even = fft(x[0::2])
    odd = fft(x[1::2])
    T = [np.exp(-2j * np.pi * k / N) * odd[k] for k in range(N // 2)]
    return [even[k] + T[k] for k in range(N // 2)] + [even[k] - T[k] for k in range(N // 2)]

# 示例輸入信號
x = [0, 1, 2, 3, 4, 5, 6, 7]
# 執(zhí)行FFT
X = fft(x)
# 輸出FFT結果
print(X)

輸出結果：