[SS] Discrete Time Fourier Transform

1. DTFT란?

DTFT는 Discrete signal $x[n]$을 위한 Fourier Transform 으로

continuous signal에 대한 Fourier Transform $X(\Omega)$과 구분하기 위해

$X(e^{j\omega})$ (= $X(\omega)$)로 표기함.

Continuous signal $x(t)$를 $T$ 간격으로 sampling을 하고 얻은 $x_s(t)=x_s(nT)=x[n]$으로부터

• impulse train의 CTFT와
• $x_s(nT)=x[n]$을 이용하여 유도가능함.

$$X(\Omega) = \int^\infty_{t=-\infty}x(t)e^{-j\Omega t}dt \quad \text{CTFT} \\ X(e^{j\omega})=\sum^\infty_{n=-\infty} x[n] e^{-j\omega n} \quad \text{DTFT}$$

---

2. DTFT 유도

2-1. Sampling 이 CTFT에 미치는 영향.

$x(t)$에서 $x[n]$을 얻는 과정을 그림으로 나타내면 다음과 같다.

여기에서 3번째 행의

impulse train $s(t)$와 $x(t)$의 곱에 해당하는 $x_s(t)$에 대한 CTFT를 구하면

DTFT에서의 frequency spectrum이 어떻게 나타나는지 확인가능함.

 

참고로

• time domain에서 multiplication은
• frequency domain에서 convolution에 해당함.

 

이를 수식으로 보면 다음과 같음.

$$ x_s(t)=x(t)s(t) \underset{\text{CTFT}}{\longleftrightarrow}X_s(\Omega)=\dfrac{1}{2\pi}X(\Omega)*S(\Omega) $$

where

• $X(\Omega)$는 $x(t)$의 CTFT 에 해당함.
• $S(\Omega)$는 sampling을 위한 impulse train $s(t)$의 CTFT 에 해당함.

CTFT의 property에서 다음을 기억할것

$$ \begin{matrix} x(t)m(t) &\longleftrightarrow & \frac{1}{2\pi}X(\Omega)*M(\Omega), \\  x(t)*m(t) & \longleftrightarrow & X(\Omega)M(\Omega) \end{matrix}$$

 

---

2-1-1. $S(\Omega)$ 구하기

$s(t)$는 impulse train으로 식은 다음과 같음.

$$ \begin{aligned}s(t)&=\displaystyle{\sum^\infty_{n=-\infty} \delta(t-nT)}\\&=\tilde{\delta}(t)\end{aligned} $$

• $\tilde{\delta}(t)$에서 ~는 주기 $T$로 반복됨을 의미함.
• 여기서 $T$는 사실상 샘플링 간격을 의미함: impulse train의 주기는 결국 sampling interval.

impulse train의 CTFT 는 역시 impulse train으로 다음과 같음.

$$ \begin{aligned} S(\Omega)&=\color{red}{\dfrac{2\pi}{T}}\color{black}{} \displaystyle{ \sum^{\infty}_{k=-\infty} \delta \left( \Omega- k\color{red}{\dfrac{2\pi}{T}}\color{black}{} \right) } \\ &=\color{red}{\Omega_0}\color{black}{} \displaystyle{ \sum^{\infty}_{k=-\infty} \delta \left( \Omega-k \color{red}{\Omega_0}\color{black}{} \right) } \end{aligned} $$

---

2-1-2. $X_s(\Omega)$ 구하기 : Convolution

shifted impulse와의 convolution은

• 대상이 되는 function을
• shifted impulse의 shifting 만큼 shift 시킴.

shifted impulse와 convolution은
shifting에 해당함.

2023.10.19 - [.../Signals and Systems] - [SS] Convolution with an shifted impulse

---

즉, impulse train과의 convolution 은

• 각각의 shifted impulse의 shift에 해당하는 위치에
• 대상이 되는 function이 shift가 되므로,

대상이 되는 function은
impulse train의 impulse간의 간격 ($\Omega_0=\frac{2\pi}{T}$)을 주기로 반복됨.

 

time domain에서의 sampling 간격 ($=T$)이 좁을수록,
frequncy domain에서 반복되는 주기 $\Omega_0=\frac{2\pi}{T}$가 길어지므로
보다 높은 고주파 성분이 제대로 표시될 수 있음.

 

즉, time domain에서의

• sampling(간격 $T$)은 (◁ discrete)

frequency domain에서

• 원래 spectrum X($\Omega$)의 반복(간격 $\dfrac{2\pi}{T}$)으로 나타남. (◁ periodic)

duality에서
discrete와 periodic의 관계를
기억하자.

2023.12.07 - [.../Signals and Systems] - [SS] Fourier Analysis: 4가지 Fourier Transform 비교

[SS] Fourier Analysis: 4가지 Fourier Transform 비교

---

continuous signal에 해당하는 x(t)에 대한 sampling을

frequency domain에서의 spectrum으로 표현하면 앞서 그림이 된다.

$$\begin{aligned}X_s(\Omega)&=\frac{1}{2\pi} \color{red}{X(\Omega)*S(\Omega)} \\&=\frac{1}{2\pi}\color{red}{\frac{2\pi}{T}\sum^{\infty}_{k=-\infty} X(\Omega-k\Omega_0)}\\ &= \frac{1}{T}\sum^\infty_{k=-\infty}X(\Omega-k\Omega_0) \\ &=\frac{1}{T} \sum^\infty_{k=-\infty}X(\Omega-k\frac{2\pi}{T})\end{aligned}$$

---

2-2. $X_s(\Omega)$와 DTFT

여기에서 DTFT 인 $X(e^{j\omega})$에 대한 설명으로 넘어간다.

• $X_s(\Omega)$와 $X(e^{j\omega})$의 관계는 Time domain에서 $x_s(t)$와 $x[n]$과의 관계에 기반함.

discrete signal $x[n]$은 $x_s(t)$와 다음과 같은 관계이다.

$$ t=nT \\x[n]=x_s(nT) $$

• sampling 간격 $T$는 결국 고정된 수이기 때문에 매번 $nT$를 사용하는 것보다 $T$를 안다고 가정하고 $n$만으로 표현하여 1씩 증가하는 일종의 순서를 나타내는 index로 표현 가능.
• 위의 식에서 2번째식 오른쪽의 $x[n]$과 같이 표현이 일반적임.

이를 이용해 DTFT를 표현하면 다음과 같음.

 

우선 $x(t)$를 샘플링한 $x_s(t)$는 impulse train $s(t)$와 $x(t)$를 곱한 것과 같음. 다음 식은 이를 보여줌.

$$ \begin{aligned}x_s(t)&=x(t)s(t)\\&=x(t)\displaystyle{\sum^\infty_{n=-\infty}}\delta(t-nT)\\&=\displaystyle{\sum^\infty_{n=-\infty}}x(nT)\delta(t-nT)\end{aligned} $$

위를 이용하여 $X_s(\Omega)$를 구하면 다음과 같음. (현재 $x_s(t)$가 discrete이므로 $\int$대신 $\sum$이 사용됨)

$$ X(\Omega)=\int^\infty_{t=-\infty}x(t)e^{-j\Omega t}dt \\ $$ $$ X_s(\Omega)=\displaystyle{ \sum^{\infty}_{\color{red}{t(=nT)} =-\infty } x( \color{red}{t} ) e^{-j\Omega \color{red}{t}} } = \displaystyle{ \sum^{\infty}_{n=-\infty} x( \color{red}{nT} )e^{-j\Omega \color{red}{nT} } } $$

 

$nT$를 $n$으로 치환하여 표현함으로서

• $x(nT)\to x[n]$이 되면,
• $n$이 time domain에서의 독립변수가 됨.

이를 Fourier transform에서 반영하면,

• complex exponential의 $n\Omega T$를 $n\omega$ 로 표현할 수 있고, 이를 통해
• $\omega$가 frequency domain의 독립변수가 된다.
• ($\omega=\Omega T$)

많은 경우 $\omega$를 Frequency domain의 독립변수로 사용하지만, 

그 못지 않게 $e^{j\omega}$를 사용하기도 한다 (DFT등과의 비교를 위해).

 

즉, 다음과 같이 DTFT $X(e^{j\omega})$가 얻어짐.
(주의할 건 $\Omega, \omega$는 연속변수임. aperiodic에 대해선 continuous가 얻어짐을 기억할 것)

$$ X(e^{j\omega})=\displaystyle{\sum^\infty_{n=-\infty}}x[n]e^{-j\omega n} $$

---

3. 참고 : Scaling을 통한 DTFT 유도

Scaling을 이용하면, $\frac{1}{T}$를 scaling factor로 하여 $x_s(nT)$에 적용한다고 생각할 수도 있다.

2024.12.02 - [.../Signals and Systems] - [SS] Scaling Property (and Zero-Interpolation): Fourier Transform

[SS] Scaling Property: Fourier Transform

---

$x_s(Tn)$에서 $T$를 제거하는 것을 통해 $x[n]$으로 표기하는 것을 $\frac{1}{T}$로 scaling이라고 볼 수 있음

$$x_s(Tn) \rightarrow X_s(\Omega)=\frac{1}{T}\sum^\infty_{k=-\infty}X(\Omega-k\Omega_0)\\ \omega = \Omega T \\ \begin{aligned}X(e^{j\omega n})&=|T| X_s \left( \Omega T \right) \\ &= |T|\frac{1}{T}\sum^\infty_{k=-\infty}X\left( T\Omega -Tk\Omega_0 \right)\\ &= \sum^\infty_{k=-\infty} X \left(\omega - k2\pi \right)\end{aligned}$$

$X_s(\Omega)$에서
반복되는 주기가 $\Omega_0(=\frac{2\pi}{T})$였던 것이 (◁$T$에 영향을 받음)
$\color{red}{X(e^{j\omega})} \color{black}{(\text{ or } X(\omega))}$에선
$\omega$가 떨여져 있는(반복되는 주기) 간격이 $2\pi$가 됨을
Scaling을 통한 유도는 직접적으로 보여줌 (1간격)
즉, $\Omega_0$가 $2\pi$에 매핑됨.

 

• 오른쪽의 frequency domain에서
  $\Omega$ 가 독립변수일 때는 반복 주기가 $\Omega_0=\frac{2\pi}{T}$였던 것이
  $\Omega \to \omega(=\Omega T)$가 되면서
  반복주기가 $\Omega_0 \to 2\pi(=\Omega_0 T)$가 됨.
  • time domain에서의 샘플링 간격 $T$가 사라진 것처럼 보이지만,
    실제로는 frequency domain에서의 반복주기 $\Omega_0$에 영향을 준다.
  • 단, $x[n]$의 경우, $T$에 대한 정보가 수식상에서 사라지고
    일종의 순서를 가르키는 index $n$(←integer)을 이용한 일종의 수열로 바뀌게 되기 때문에
    고정된 $2\pi$의 반복주기를 가지게 되는 수식이 됨: 실제 주기를 반영한 $\Omega_0$가 $2\pi$에 매핑됨.
  • discrete signal의 Frequency domain representation이 가지는 $2\pi$주기성이 이에 해당함.
• 즉 $\omega$로 표현(=discrete한 $x_s(t)$에 대한 frequency domain representation)은
  항상, $2\pi$의 반복주기를 가지게 됨.
  (어떤 $T$로 샘플링하더라도, 변환에서 해당 $T$가 일정하다면 Fourier transform은 $2\pi$ 주기성을 가지게 됨)
  • $x[n]$에서 $n=2$일 때 $2T$의 값으로 매핑하여 인식하듯이,
    frequency domain에서 $2\pi$에 해당하는 실제 주파수는 $1/T$에 매핑된다.
  • 위의 그림의 왼쪽에서 frequency domain에서 $x(t)$의 spectrum이 반복되고
    각각이 $2\pi$가 떨어져 있지만,
    실제 샘플링 간격 $T$를 고려하면 $\frac{1}{T}$Hz 또는 $\Omega_0$가 떨어져 있는 것임.

---

4. Frequency에서의 주기: 실제 주기와 $2\pi$

• 10개의 samples을 얻는다고 가정하고, 첫번째 케이스는 $T=1/8000$ sec 으로 얻고 두번째는 케이스는 $T=1/4000$ sec 으로 얻었다고 가정하자 (두 경우 각각 10개의 samples를 얻음).
• 이 두 경우 모두 $x[n]$으로 표시하면 10개의 수열로 동일한 길이의 수열로 표현됨.
• 그리고 이를 DTFT한 경우, 두 freq. spectrum 모두 $2\pi$ 간격으로 반복이 됨.
• 단, 첫번째 케이스의 $2\pi$는 실제로는 $16000\pi$ (=8000Hz) 에 해당하며, 두번째 케이스의 $2\pi$는 $8000\pi$ (=4000Hz)에 해당함.

---

5. 결론

• Continuous variable $t$가 $nT$를 거쳐 discrete variable $n$으로 치환된 것처럼,
• Continuous frequency $\Omega$가 $\Omega T$를 거쳐 $\omega$로 치환됨.
• $T$가 사라지면서, DTFT는 결국, $2\pi$ (or $-\pi$에서 $+\pi$) 의 구간이 주기적으로 반복되는 spectrum을 얻게됨.

---

참고: Continuous Time Fourier Transform과 비교.

CTFT의 경우, $X(\Omega)$로 표시되는 이유는
CTFT에서는 frequency domain의 독립변수를 $\Omega$로 나타내도 충분하기 때문임.

• $[-\infty,\infty]$의 range에서
• (angular )frequency $\Omega(=2\pi f)$에 대한 함수로 표현됨.

Laplace Transform의 경우에는 발산하는 신호를 보다 빠르게 수렴시키기 위해 exponent에 real component를 추가한 $s=\sigma+j\Omega$를 도입하여, $j\Omega$만 사용하는 CTFT를 일반화 시킨 형태이므로 $X(s)$로 표시됨.

• 복소평면으로 확장됨. $s$가 real component를 가짐.

 

이들과 달리 위에서 DTFT의 표시는 $X(e^{j\omega})$를 사용하는데,

• 여기서 $\omega=\Omega T$로서
• DTFT가 time domain에서의 sampling으로 인해, $2\pi$ 주기성을 가짐을 의미하며,
• 주파수를 나타내는 실제적인 독립변수임.

때문에 $X(\omega)$로 기재하는 경우도 매우 많은 편임.

• $x(nT)\rightarrow x[n]$으로 처리와 $2\pi$ 주기성이 고려된 표현.
• 하지만 $2\pi$주기성이 뚜렷이 들어나지 않음.

 

결과적으로, $\omega$대신 $e^{j\omega}$를 사용한 이유는
DTFT를 complex plane에서 표현할 때 보다 $2\pi$주기성을 가짐을 표시하기 위해서임
imaginary axis를 사용하는 CTFT나 complex plane전체를 이용하는 Laplace와 달리,
complex plane의 단위원 (=반지름이 1인 원)에 DTFT가 존재함을 강조하기 위해서임.

• $2\pi$ 주기성을 강조하기 위해 단위원 $e^{j\omega}$을 사용.

 

독립변수는 $\omega$이지만 DTFT가 $2\pi$주기성으로 가지므로
complex plane의 단위원인 $e^{j\omega}=\cos\omega+j\sin \omega$
(←complex plane이 real axis와 imaginary axis로 구성되므로 $\cos \omega$는 real axis의 좌표이고 $\sin \omega$는 imaginary axis의 좌표가 되어 반지름이 1인 단위원이 됨.)를
독립변수 자리에 넣어서 $X(e^{j\omega})$로 표시한 것임.

 

수치해석적으로 구현할 때 사용되는 많은 라이브러리의 API문서에서는
주로 w를 이용하거나 f를 사용하여

angular frequency 및 freqeuncy를 frequency domain의 독립변수로 지칭하므로

$X(\omega)$로 DTFT를 표현하는 경우가 더 많지만,

$2\pi$주기성을 기억하는 뜻에서 이 문서에서는 $X(e^{j\omega})$를 사용했음.

 

다음 그림은 frequency response를 complex plane에 나타낸 것으로

• a)는 CTFT의 경우 (S 평면. $H(j\Omega)$ )를,
• b)는 DTFT의 경우 (Z 평면. $H(e^{j\omega})$)를 보여줌.

discrete signal을 사용하면서 $2\pi$주기성이 발생하여 단위원으로 표기하는 형태가 됨. 그림 (a)의 직선인 허수축이 그림 (b)에서 주기성으로 인해 단위원이 됨.

위 그림은 결국 Z Transform의 Z 평면을 반영하고 있음.

S 평면과 Z 평면의 보다 자세한 설명은 다음 Youtube 영상을 참고할 것.

https://youtu.be/acQecd6dmxw?si=noboVlAbGjR8Qbas

 

---

6. Inverse DTFT

DTFT의 역변환.

$$ x[n]=\dfrac{1}{2\pi}\int_{<2\pi>} X(e^{j\omega }) e^{j\omega n }d\omega $$

 

참고로, Inverse CTFT는 다음과 같음.

$$ x(t) = \dfrac{1}{2\pi} \int_{\Omega=-\infty}^{\infty} X(\Omega) e^{j\Omega t} d\Omega $$

---

6-1. Inverse DTFT 증명

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

 

$\dfrac{1}{2\pi}\int_{<2\pi>} e^{-j\omega (m-n)}d\omega$ 은 $e^{-j\omega n}$이 orthogonal function이기 때문에,

• $m=n$인 경우에만 1의 값을 가지며,
• $m \ne n$인 경우에는 0임.

 

즉 Kronecker delta function으로 치환 가능함.

 

$$ \hat{x}[n]=\displaystyle{\sum^\infty_{m=-\infty}x[m]\delta[n-m]}=x[n] $$

 

위와 같이 $\hat{x}[n]=x[n]$이 성립하여 DTFT의 inverse transform임을 확인할 수 있음.

---

같이 보면 좋은 자료들

https://dsaint31.tistory.com/pages/SS-Discrete-Time-Fourier-Transform

[SS] Discrete Time Fourier Transform (DTFT) and Discrete Fourier Transform (DFT)

 

7.1장 : https://product.kyobobook.co.kr/detail/S000001732452

신호 및 시스템 | 장영범 - 교보문고

---