[SS] Discrete Fourier Transform (DFT)

DTFT 의 한계와 DFT의 등장.

 

DTFT는  time domain의 continuous signal $x(t)$를 discrete signal $x[n]$으로 바꾼 경우에 대한 Fourier Transform으로

CTFT에 time domain에서의 sampling을 고려한 확장이라고 볼 수 있다.

 

우선, DTFT의 공식은 다음과 같다.

 

$$\begin{aligned}X(e^{j\omega})&=\sum^\infty_{n=-\infty} x[n] e^{-j\omega n} & \text{DTFT} \\ x[n]&=\dfrac{1}{2\pi}\int_{<2\pi>} X(e^{j\omega }) e^{j\omega n }d\omega & \text{IDTFT} \end{aligned}$$

 

하지만 다음과 같은 한계를 가진다.

 

$x[n]$에 대해 무한대 range에서 고려를 해야만 DTFT를 구할 수 있음.

$x[n]$은 discrete이지만, $X(e^{j\omega})$는 continuous임 : computer로 처리할 경우 discrete로 바꾸어야한다.

 

이같은 이유로 인해 제안된 것이 바로 Discrete Fourier Transform (DFT)임.

 

---

DFT

$$\begin{aligned}X[k] &= \sum^{N-1}_{n=0} x[n] W^{kn}_N \\ x[n] &= \dfrac{1}{N}\sum^{N-1}_{k=0} X[k]W_N^{-kn} \\ W_n&=e^{-j\frac{2\pi}{N}}, \quad W_N \text{ is twiddle factor.}\end{aligned}$$

• Continuous Periodic Spectrum을 $N$ sampling하여 Discrete Periodic Spectrum 얻음
• 그 결과로 이에 대응되는 Signal이 Discrete Non-periodic에서 Discrete Periodic Signal이 됨.

즉, DFT는 다음과 같이 볼 수 있음.

• Discreted aperiodic signal($N$ samples)의 Continuous Frequency Spectrum을 $N$ sampling한 것
• Discreted aperiodic signal($N$ samples)을 주기가 $N$인 주기 신호의 한 주기에 해당하는 것으로 취급
  • 때문에 Frequency Spectrum도 최소한 $N$ 개 이상으로 sampling해야한다.
  • 만약, time domain의 신호의 샘플 수 $N$보다 작은 수의 samples를 가지도록 Frequency spectrum이 sampling 될 경우, time domain의 signal (위그림의 왼쪽 하단) 에서 aliasing(중첩)이 발생되어 IDFT를 해도 제대로 된 신호를 못 얻음.
  • 신호를 측정하는 시간이 고정된 경우, 원하는 주파수 유효 band-width에 맞춰 $N$이 결정됨.
    2023.12.07 - [.../Signals and Systems] - [SS] DFT에서 Aliasing을 피하기 위한 N은?
  • Frequency domain에서의 sampling은 frequncy resolution이라는 개념과 연결됨.
    2022.11.25 - [.../Signals and Systems] - [SS] Resolution of DFT
    

[SS] DFT에서 Aliasing을 피하기 위한 N은?

 

[SS] Resolution of DFT

DTFT는 DTFS와 매우 유사하나, 다음과 같은 차이가 있음.

• DTFS : 1/N 이 분석식, 즉 Fourier Coefficient (푸리에 계수) 계산식에 붙음
• DFT : 1/N 이 합성식, 즉 IDFT 식에 붙음 (∵ $X(\omega)$의 샘플링 개념으로 유도)

---

DFT의 개념도

CTFS, CTFT, DTFS, DTFT는 FT의 종류 혹은 분류이나
DFT는 FT의 한 종류라기 보다는
단지 수치적으로 FT를 수행하기 위한 도구일 뿐 임.

---

Twiddle Factor (회전인자): $W_N$

$$ W_N = e^{-j\dfrac{2\pi}{N}} $$

$W_N^{kn}$은 복소평면의 단위원을 같은 크기의 각도로 $N$ 등분한 점에 해당함 : Complex Exponential 에 대한 간결한 표현.

• $W_N^{kn}$은 N을 주기로 하는 periodic function임 : $W_N^{kn+N}=W^{kn}_N$
• exponent에 마이너스 기호가 있기 때문에 clockwise 로 회전함.
  • $W_N$이 한번 곱해질 때마다 clockwise로 정해진 각도만큼 회전 
• $N$이 정해지면 미리 계산해놓을 수 있음.

 

다음은 $N=8$인 경우의 twiddle factor임.

---