Diszkrét Fourier-transzformáció

1. Sablon:Label
   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. 1. **Matematikai definíció**

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

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

1. 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},n=0,1,...,N-1$$

—

1. 1. 1. **Jellemzők**

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

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

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

—

1. 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 $O(N\log N)$ időben, ami nagy minták esetén jelentős gyorsulást eredményez.

—

1. 1. 1. **Példa**

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

1. 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},k=0,1,2,3$$

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

2. **$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. **$k=2$**: $$X[2]=1+2e^{-j\pi }+3e^{-j2\pi }+4e^{-j3\pi }$$ $$X[2]=1-2+3-4=-2$$

4. **$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. 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

1. Frekvenciaelemzés:
   • A DFT a jel frekvenciatartománybeli elemzésének alapvető eszköze.
2. Numerikus stabilitás:
   • A DFT stabil és pontos, különösen digitális rendszerekben.
3. 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

1. 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ú.
2. Periodicitás feltételezése:
   • A DFT implicit módon feltételezi, hogy a jel periodikus, ami műtermékeket okozhat.

---

Alkalmazások

1. Jelfeldolgozás:
   • Spektrális analízis, szűrés, zajcsökkentés.
2. Kép- és videófeldolgozás:
   • Kompresszió (JPEG, MPEG), mintázatfelismerés.
3. Távközlés:
   • Moduláció, spektrum kihasználtság elemzése.
4. 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.

• Sablon:En: Sablon:T
• Sablon:Ru: Sablon:T