diszkrét Fourier-transzformáció

Magyar

Kiejtés

IPA: [ ˈdiskreːtfourijɛrtrɒnsformaːt͡sijoː]

Főnév

(matematika, algoritmusok)
1. 1. **Diszkrét Fourier-transzformáció (DFT)**

A **Diszkrét Fourier-transzformáció (DFT)** egy olyan eljárás, amely a diszkrét időtartományban adott jel **frekvenciatartománybeli reprezentációját** adja meg. Ez a módszer különösen hasznos digitális jelek és rendszerek analízisében, például jelfeldolgozásban, képkompresszióban és spektrális elemzésben.

—

1. 1. **Matematikai definíció**

A DFT a bemeneti ${\textstyle x[n]}$ diszkrét jel ${\textstyle N}$ -hosszú szekvenciáját transzformálja ${\textstyle X[k]}$ -re, amely a frekvenciatartománybeli reprezentációt adja.

1. 1. 1. **Egyenletek**: $X[k]=\sum _{n=0}^{N-1}x[n]\cdot e^{-j{\frac {2\pi }{N}}kn},\quad k=0,1,...,N-1$ ahol: - ${\textstyle x[n]}$ : Az időtartománybeli jel, - ${\textstyle X[k]}$ : A frekvenciatartománybeli komponensek, - ${\textstyle N}$ : A jel mintavételezési pontjainak száma, - ${\textstyle e^{-j{\frac {2\pi }{N}}kn}}$ : A DFT komplex exponenciális alapfüggvénye.

1. 1. 1. **Fordított DFT (IDFT)**: A frekvenciatartománybeli reprezentáció visszatranszformálása az időtartományba: $x[n]={\frac {1}{N}}\sum _{k=0}^{N-1}X[k]\cdot e^{j{\frac {2\pi }{N}}kn},\quad n=0,1,...,N-1$

—

1. 1. **Jellemzők**

1. **Komplex értékek**: - A DFT eredményei általában komplex számok ( ${\textstyle X[k]}$ ), amelyek tartalmazzák a frekvencia **amplitúdóját** és **fázisát**. - Az amplitúdó: ${\textstyle |X[k]|={\sqrt {{\text{Re}}(X[k])^{2}+{\text{Im}}(X[k])^{2}}}}$ . - A fázis: ${\textstyle \arg(X[k])=\tan ^{-1}\left({\frac {{\text{Im}}(X[k])}{{\text{Re}}(X[k])}}\right)}$ .

2. **Periodicitás**: - A ${\textstyle X[k]}$ eredmény periodikus ${\textstyle N}$ -en belül, azaz ${\textstyle X[k+N]=X[k]}$ .

3. **Lineáris komplexitás**: - Az egyenletek ${\textstyle O(N^{2})}$ műveletet igényelnek közvetlen számítással. Ez jelentős költséget jelenthet nagy ${\textstyle N}$ -re.

—

1. 1. **Gyors Fourier-transzformáció (FFT)**

A **FFT** a DFT gyorsított változata, amely optimalizálja a számítási folyamatot. Az FFT hatékonyan számolja ki a DFT-t ${\textstyle O(N\log N)}$ időben, ami nagy minták esetén jelentős gyorsulást eredményez.

—

1. 1. **Példa**

Adott a következő diszkrét jel: $x[n]=\{1,2,3,4\}$

1. 1. 1. **DFT számítása**: $N=4$ $X[k]=\sum _{n=0}^{3}x[n]\cdot e^{-j{\frac {2\pi }{4}}kn},\quad k=0,1,2,3$

1. ** ${\textstyle k=0}$ **: $X[0]=1+2+3+4=10$

2. ** ${\textstyle k=1}$ **: $X[1]=1+2e^{-j{\frac {\pi }{2}}}+3e^{-j\pi }+4e^{-j{\frac {3\pi }{2}}}$ $X[1]=1+2j-3-4j=-2-2j$

3. ** ${\textstyle k=2}$ **: $X[2]=1+2e^{-j\pi }+3e^{-j2\pi }+4e^{-j3\pi }$ $X[2]=1-2+3-4=-2$

4. ** ${\textstyle k=3}$ **: $X[3]=1+2e^{-j{\frac {3\pi }{2}}}+3e^{-j2\pi }+4e^{-j{\frac {9\pi }{2}}}$ $X[3]=1-2j-3+4j=-2+2j$

1. 1. 1. **Eredmény**: $X[k]=\{10,-2-2j,-2,-2+2j\}$

—

Python implementáció

import numpy as np

# Példa jel
x = np.array([1, 2, 3, 4])

# DFT számítása
def dft(x):
    N = len(x)
    X = np.zeros(N, dtype=complex)
    for k in range(N):
        for n in range(N):
            X[k] += x[n] * np.exp(-2j * np.pi * k * n / N)
    return X

X = dft(x)
print("DFT eredmény:", X)

# FFT összehasonlítás
X_fft = np.fft.fft(x)
print("FFT eredmény:", X_fft)

Kimenet:

DFT eredmény: [10.+0.j -2.-2.j -2.+0.j -2.+2.j]
FFT eredmény: [10.+0.j -2.-2.j -2.+0.j -2.+2.j]

C++ implementáció

#include <iostream>
#include <vector>
#include <complex>
#include <cmath>

using namespace std;

using Complex = complex<double>;

vector<Complex> dft(const vector<double>& x) {
    int N = x.size();
    vector<Complex> X(N);

    for (int k = 0; k < N; ++k) {
        Complex sum(0.0, 0.0);
        for (int n = 0; n < N; ++n) {
            double angle = -2.0 * M_PI * k * n / N;
            sum += x[n] * Complex(cos(angle), sin(angle));
        }
        X[k] = sum;
    }
    return X;
}

int main() {
    // Példa jel
    vector<double> x = {1, 2, 3, 4};

    // DFT számítása
    vector<Complex> X = dft(x);

    // Eredmény kiírása
    cout << "DFT eredmény:" << endl;
    for (const auto& val : X) {
        cout << val << endl;
    }

    return 0;
}

Kimenet:

DFT eredmény:
(10,0)
(-2,-2)
(-2,0)
(-2,2)

Előnyök

Frekvenciaelemzés:
- A DFT a jel frekvenciatartománybeli elemzésének alapvető eszköze.
Numerikus stabilitás:
- A DFT stabil és pontos, különösen digitális rendszerekben.
Széles körű alkalmazhatóság:
- Számos területen használható, például jelfeldolgozásban, képkompresszióban, radar- és távközlési rendszerekben.

Hátrányok

Számítási költség:
- A közvetlen DFT számítás (O(N^2)) időigényű, ami nagy jelek esetén lassú.
Periodicitás feltételezése:
- A DFT implicit módon feltételezi, hogy a jel periodikus, ami műtermékeket okozhat.

Alkalmazások

Jelfeldolgozás:
- Spektrális analízis, szűrés, zajcsökkentés.
Kép- és videófeldolgozás:
- Kompresszió (JPEG, MPEG), mintázatfelismerés.
Távközlés:
- Moduláció, spektrum kihasználtság elemzése.
Rendszerek szimulációja:
- Fizikai rendszerek, például rezgés- és hullámelemzés.

Összegzés

A Diszkrét Fourier-transzformáció kulcsfontosságú eszköz a jelek idő- és frekvenciatartomány közötti átalakításához. Bár a DFT közvetlen számítása számításigényes, a Gyors Fourier-transzformáció (FFT) hatékonyabbá tette a használatát, így elengedhetetlen eszközzé vált a modern jelfeldolgozásban és adatfeldolgozásban.

Fordítások

angol: discrete Fourier transform (en)
orosz: дискретное преобразование Фурье (ru) (diskretnoje preobrazovanije Furʹje)

További információk

diszkrét Fourier-transzformáció - Értelmező szótár (MEK)
diszkrét Fourier-transzformáció - Etimológiai szótár (UMIL)
diszkrét Fourier-transzformáció - Szótár.net (hu-hu)
diszkrét Fourier-transzformáció - DeepL (hu-de)
diszkrét Fourier-transzformáció - Яндекс (hu-ru)
diszkrét Fourier-transzformáció - Google (hu-en)
diszkrét Fourier-transzformáció - Helyesírási szótár (MTA)
diszkrét Fourier-transzformáció - Wikidata
diszkrét Fourier-transzformáció - Wikipédia (magyar)