快捷導(dǎo)航

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

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

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

FFT快速傅里葉變換介紹

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

DFT是一種將信號(hào)從時(shí)域轉(zhuǎn)換到頻域的數(shù)學(xué)工具，而FFT通過減少計(jì)算量來加速這一過程。

FFT的基本思想

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

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

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

Python FFT快速傅立葉變換

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

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

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

pip install numpy

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

import numpy as np
import matplotlib.pyplot as plt

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

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

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

# 獲取FFT的頻率軸
P2 = np.abs(Y/L)
P1 = P2[:L//2+1]
P1[1:-1] = 2*P1[1:-1]  # 去除對(duì)稱性
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()

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

注意：

這個(gè)例子僅用于演示如何在Python中使用numpy庫進(jìn)行FFT計(jì)算。
在實(shí)際應(yīng)用中，你可能需要根據(jù)你的具體需求調(diào)整信號(hào)生成、FFT計(jì)算以及結(jié)果分析的方式。

FFT（快速傅立葉變換）是一種計(jì)算離散傅立葉變換（DFT）的快速算法，用于將信號(hào)從時(shí)域轉(zhuǎn)換為頻域。

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

FFT python樣例

下面是一個(gè)使用NumPy實(shí)現(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)]

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

輸出結(jié)果：

[(28+0j), (-4+9.65685424949238j), (-4+4j), (-4+1.6568542494923806j), (-4+0j), (-4-1.6568542494923806j), (-4-4j), (-4-9.65685424949238j)]

上述代碼中的 fft 函數(shù)使用遞歸將輸入信號(hào)劃分為偶數(shù)和奇數(shù)索引的兩個(gè)部分，然后再將兩部分合并。函數(shù)的返回值是FFT變換后的結(jié)果。

注意：

上述代碼是一個(gè)簡化的FFT實(shí)現(xiàn)，不考慮性能優(yōu)化和處理異常情況。
在實(shí)際應(yīng)用中，可以使用NumPy庫中的 numpy.fft.fft 函數(shù)進(jìn)行FFT計(jì)算，它提供了更高效和穩(wěn)定的實(shí)現(xiàn)。