Wikiszótár

gyors Fourier-transzformáció

Magyar

Kiejtés

  • IPA: [ ˈɟorʃfourijɛrtrɒnsformaːt͡sijoː]

Főnév

gyors Fourier-transzformáció

  1. (matematika, algoritmusok)

Gyors Fourier-transzformáció (FFT - Fast Fourier Transform)

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.


Elmélet

Fourier-transzformáció

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 = [x_0, x_1, …, x_{n-1}]) mintavételi sorozatot alakít át komplex frekvenciaértékek sorozatává (X = [X_0, X_1, …, X_{n-1}]): [ X_k = _{j=0}^{n-1} x_j e^{-2i k j / n}, k = 0, 1, …, n-1 ] ahol (i = ) az imaginárius egység.

Gyors Fourier-transzformáció (FFT)

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.


Időkomplexitás

  • DFT: (O(n^2)).
  • FFT: (O(n n)).


Pszeudokód

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[0:n:2])
    x páratlan = FFT(x[1:n:2])
    T = [0] * n
    ciklus k = 0-tól n/2-ig:
        T[k] = x_páros[k] + ω^k * x_páratlan[k]
        T[k + n/2] = x_páros[k] - ω^k * x_páratlan[k]
    térj vissza T

Python implementáció

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[0::2])
    odd = fft(x[1::2])
    T = [0] * n
    for k in range(n // 2):
        t = np.exp(-2j * np.pi * k / n) * odd[k]
        T[k] = even[k] + t
        T[k + n // 2] = even[k] - t
    return T

# Példa használat
data = [0, 1, 2, 3, 4, 5, 6, 7]
result = fft(data)
print("FFT eredmény:")
print(result)

Kimenet: 

FFT eredmény:
[(28+0j), (-4+9.65685424949238j), (-4+4j), (-4+1.6568542494923797j), (-4+0j), (-4-1.6568542494923797j), (-4-4j), (-4-9.65685424949238j)]

C++ implementáció

#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[i] = x[i * 2];
        odd[i] = x[i * 2 + 1];
    }

    // 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[k];
        x[k] = even[k] + t;
        x[k + n / 2] = even[k] - 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)

Összegzés

Előnyök:

  1. Rendkívül gyors ((O(n n))).
  2. Hatékony spektrális analízisre, szűrőkre, konvolúciókra.

Hátrányok:

  1. Az implementáció bonyolultabb, mint a DFT-é.
  2. Az adatméretnek (2^k) (hatványának) kell lennie, bár ez megoldható nullákkal történő kitöltéssel.

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.

Fordítások

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=gyors_Fourier-transzformáció&oldid=3479498”