A gyors Fourier-transzformáció (FFT) egy hatékony algoritmus a diszkrét Fourier-transzformáció (DFT) kiszámítására. Az FFT az (O(n^2)) időkomplexitású DFT-t (O(n n)) időre optimalizálja, így rendkívül hasznos a jelfeldolgozás, spektrális analízis, és más numerikus alkalmazások esetén.
A Fourier-transzformáció célja egy idő- vagy térbeli jelfolyamat frekvenciakomponenseinek meghatározása. A diszkrét Fourier-transzformáció (DFT) egy (x = ) mintavételi sorozatot alakít át komplex frekvenciaértékek sorozatává (X = ): ahol (i = ) az imaginárius egység.
Az FFT a DFT kiszámításának optimalizált változata, amely a “oszd meg és uralkodj” technikát alkalmazza: 1. A bemeneti jelet páros és páratlan indexekre osztja. 2. Két kisebb DFT-t hajt végre (az egyik a páros, a másik a páratlan elemekre). 3. A DFT eredményeket kombinálja a “pillangó” műveletekkel, kihasználva a periodicitás tulajdonságait.
FFT(x):
n = x hossza
ha n = 1:
térj vissza x
ω = e^(-2πi / n) // Gyök a Fourier-transzformációhoz
x páros = FFT(x)
x páratlan = FFT(x)
T = * n
ciklus k = 0-tól n/2-ig:
T = x_páros + ω^k * x_páratlan
T = x_páros - ω^k * x_páratlan
térj vissza T
import numpy as np
def fft(x):
n = len(x)
if n <= 1:
return x
# Páros és páratlan indexek felosztása
even = fft(x)
odd = fft(x)
T = * n
for k in range(n // 2):
t = np.exp(-2j * np.pi * k / n) * odd
T = even + t
T = even - t
return T
# Példa használat
data =
result = fft(data)
print("FFT eredmény:")
print(result)
Kimenet:
FFT eredmény:
#include <iostream>
#include <complex>
#include <vector>
#include <cmath>
using namespace std;
typedef complex<double> Complex;
typedef vector<Complex> CArray;
void fft(CArray& x) {
int n = x.size();
if (n <= 1) return;
// Páros és páratlan részek felosztása
CArray even(n / 2);
CArray odd(n / 2);
for (int i = 0; i < n / 2; ++i) {
even = x;
odd = x;
}
// Rekurzív FFT
fft(even);
fft(odd);
// Kombinálás
for (int k = 0; k < n / 2; ++k) {
Complex t = polar(1.0, -2 * M_PI * k / n) * odd;
x = even + t;
x = even - t;
}
}
int main() {
CArray data = {0, 1, 2, 3, 4, 5, 6, 7};
fft(data);
cout << "FFT eredmény:" << endl;
for (auto& c : data) {
cout << c << endl;
}
return 0;
}
Kimenet:
FFT eredmény: (28,0) (-4,9.65685) (-4,4) (-4,1.65685) (-4,0) (-4,-1.65685) (-4,-4) (-4,-9.65685)
A gyors Fourier-transzformáció (FFT) kulcsfontosságú algoritmus a numerikus feldolgozásban, és széles körben alkalmazzák különböző tudományos és mérnöki területeken.