06-2. 이산 푸리에 변환(DFT, Discrete Fourier Transform)

앞 페이지에서 이산 시간 푸리에 변환(DTFT)까지 유도했고, 이제 주파수까지 이산인 이산 푸리에 변환(DFT)을 유도해본다.

 

---

시간을 '이산'으로 만드는 것은, 어떤 아날로그 신호에 대해서 연속된 시간으로 값을 측정할 수 없는 현실적인 이유 때문이었다. 현실에서는, 아무리 시간을 잘게 쪼게도 연속된 시간에 대한 값을 잴 수도 저장할 수도 없다.

 

주파수에 대해서도 마찬가지로, 연속된 주파수 값을 가지는 것을 현실에서 측정하거나 저장할 수 없다. (컴퓨터 등에서 디지털 적으로 처리할 수 없다는 말이다.)

따라서, 주파수에 대해서도 연속된 것이 아닌, 간격이 존재하는 이산 주파수의 형태로 다뤄줘야 한다.

 

위 그림은 주파수 사이를 $\frac {1}{6}$ 간격으로 샘플링하는 것을 보여준다.

이렇게 샘플링하게 되면, 주기 $N=6$이되고, 주파수 $f=\frac {k}{N}$인 지점에서만 값을 가지는 신호가 된다. ( $k$: 정수)

 

즉, 주파수 $f$에 의한 함수 $Y(f)$가, 정수값 $k$에 의한 함수 $Y(k)$로 변경되게 된다. 

 

이렇게 주파수 공간에서 이산 간격으로 샘플링된 신호에 대한 푸리에 변환은, 연속된 주파수일 때와는 좀 다른 표현법이 된다. 이러한 이산 시간 및 이산 주파수에 대한 푸리에 변환을 이산 푸리에 변환(DFT, Discrete Fourier Transform)이라 한다. DFT는 DTFT(이산 시간 푸리에 변환)으로부터 쉽게 유도될 수 있다. 

 

DTFT에서 $Y(f)$에 대한 식은 다음과 같았다.

 

$$DTFT: \; \; Y(f) = \sum _{n=-\infty} ^{\infty} {y(n)e^{-i2\pi fn}} \tag {1}$$

 

식 (1)에서 주파수 $f=\frac {k}{N}$로 놓고 계산하면, 연속된 주파수 공간이 아닌, 샘플링된 주파수의 값만을 가지는 신호에 대한 식으로 변형시킬 수 있다. ($\frac{k}{N}$에 해당하는 주파수만 존재)

 

적용하면 다음과 같이 변경되고, 이것이 DFT 식이다.

 

$$ DFT: \; \; Y(k) = \sum _{n=0} ^{N-1} {y(n)e^{-i\frac{2\pi}{N}kn}}, \; \; 0 \leq k < N \tag {2}$$

 

 

---

식 (2)의 내부에 있는 $y(n)$에 대해서도 어떻게 되는지 표현을 해야 한다. 즉, IDFT(Inverse DFT) 수식을 알아내야 한다.

 

IDFT의 수식은, 앞 페이지의 이산 시간 푸리에 변환에서 DTFT를 구할 때, CTFT의 $y(t)$를 구하는 식 대신에 $y(n)$을 구하는 식을 넣어서 구하는 방식으로는, IDFT의 $y(n)$을 구할 수 없다. 

 

DTFT의 경우는 시간에 대해서만 이산(discrete)적인 샘플링을 해서 $y(t)$가 $y(n)$으로 표현된 것이고, 주파수 영역에 대한 변화는 없기에, 기존의 주파수 함수 $Y(k)$를 이용해 표현해도 무방하나, DFT의 경우는 주파수도 이산적인 샘플링을 하기에, 기존의 $Y(k)$에 대한 식을 그대로 이용하면 안 된다.

 

따라서, 식(2)의 식 내부에 있는 $y(n)$을 다른 방식으로 구해야 하는데, 그 한 가지 방법으로, 복소 정현파의 직교성을 이용해서 구하고자 한다.

 

이 블로그에서는,  03. 푸리에 계수에서  $y(t)$에 대한 신호식을 일반화하고, 이 신호식에서의 각 계수는 정현파의 일반 특성을 이용해 구했다.  이렇게 하는 것이 좀 더 직관적으로 푸리에 급수 및 푸리에 변환을 이해하는데 편하다. 대신 수학적인 간결함은 떨어진다. 

사인파의 특성을 이용해서 계수를 구하는 과정에서 숨어있는 성질은, 두 복소 정현파는 서로 주파수가 다르면 서로 직교하고, 이때 두 정현파의 내적은 0이 된다는 성질이다.  이러한 직교성을 이용하면, 수학적으로 좀 더 간결하게 푸리에 변환을 설명할 수 있다. (반면에, 처음에 이해하기는 좀 더 어렵다.)

 

먼저, 복소 정현파의 내적 및 직교성에 대해 알아보자.

복소 정현파의 직교성

1) 벡터 공간에서, 두 벡터를 내적한 것이 0이면 서로 직교(수직)이다. 

 

$$ \vec {A} \cdot \vec {B} = 0  \; \; then, \vec {A} \perp \vec {B}$$

 

(고등수학에 나오는, 벡터의 가장 중요한 성질 중 하나이다.)

 

2) 함수의 내적합이 0이면, 두 함수는 직교한다.

두 함수에 대해서도 비슷한 표현을 한다. 만약 어떤 구간에 대해서 두 함수 $f_1$과 $f_2$의 내적을 적분한 것이 0이면, 두 함수는 그 구간에 있어서 직교한다고 얘기할 수 있다.

 

$$ \int _{a} ^{b} {f_1 \cdot f_2} = 0 \; \; then, f_1 \perp f_2$$

 

3) 복소평면에서 두 복소수의 내적이 0이면, 두 복소수는 직교한다.

복소평면에서도 비슷한데, 두 복소수 $A=a+bi$와 $B=c+di$의 내적이 0이면 두 복소수는 직교한다고 한다.

 

여기서 주의할 것은 복소수 $A$와 $B$의 내적은 $A$와 $B^*$의 곱으로 계산된다는 점. $B^*$는 $B$의 켤레 복소수이고, 켤레 복소수는 원래 복소수의 허수부의 부호가 반대인 복소수를 말한다. 즉, $B=c+di$에 대해 $B^*=c-di$ (복소평면에서 내적을 켤레 복소수와의 곱으로 정의한 이유는, 그렇게 정의하지 않고 그냥 두 복소수의 곱으로 정의하면, 자기 자신과의 내적의 결과가 0이 나오는, 이상한 결과를 보이기 때문)

 

따라서, 두 복소수 $A=a+bi$와 $B=c+di$의 내적 $<A,B>$는,

 

$$ <A,B> = A \cdot B^* = (a+bi) \cdot (c-di) = ac + bd$$

 

위 식에서 $ac+bd=0$이면 두 복소수 $A$와 $B$는 직교한다.

 

4) 복소평면에서 두 신호의 내적이 0이면, 두 신호는 직교한다. 

복소평면에서 구간 $a$와 $b$사이에서 시간 $t$에 따라 값을 가지는 어떤 신호 $y(t)$와 $z(t)$가 있을 때, $y(t)$와 $z(t)$의 내적 $<y(t), z(t)> = 0$이면, 두 신호는 직교한다.

 

복소평면에서의 두 신호 $y(t)$와 $z(t)$의 내적은, $y(t)$와 $z^*(t)$의 곱에 대한 적분값으로 정의되고, 여기서 $z^*(t)$는 $z(t)$의 켤레 복소수 신호이다.

 

$$ <y(t), z(t)> = \int _{a} ^{b} {y(t)z^*(t)dt}=0 \; \; then, y(t) \perp z(t)$$ 

 

연속신호에 대해서는 적분을 하고, 이산 신호의 경우는 모든 신호에 대한 내적 합을 계산한다.

 

5) 복소평면에서 서로 다른 주파수의 신호는 직교한다.

복소평면서의 어떤 신호는 삼각함수 혹은 복소지수함수로 표현될 수 있다. 

 

주파수가 $f$, 주기가 $T$인 정현파를 삼각함수 및 복소지수함수로 표현하면 다음과 같다.

 

$$ \cos{(2\pi nft)} + \sin {(2\pi nft)} = e^{i2\pi nft} = e^{i \frac {2\pi n t}{T}}$$

 

삼각 함수에서 복소지수함수로의 변환은 오일러 공식에 의해서 이루어진다. ( 이 부분에 대한 상세 설명은 04-4 푸리에 급수를 복소지수로 표현하기 참조)

 

같은 주기 내에서 주파수가 다른 두 정현파 $y(t)$와 $z(t)$의 내적을 계산해보자. 

서로 다른 주파수를 가진다는 것을 표현하기 위해서 $y(t)=e^{i \frac {2\pi p t}{T}}$라 하고, $z(t)=e^{i \frac {2\pi k t}{T}}$라고 하자. ($p$와 $k$로 다르게 표현)

 

구간은 한 주기 구간인 $(0,T)$까지로 하자. 두 신호의 내적을 해보면,

 

$$ \begin{align}  <e^{i \frac {2\pi pt}{T}}, e^{i \frac {2\pi kt}{T}}>  &= \int _{0} ^{T} {e^{i \frac {2\pi pt}{T}} e^{-i \frac {2 \pi kt}{T}}dt} \\ &= \int _{0} ^{T} {e^{i \frac {2\pi (k-p)t}{T}}}dt \end{align}$$

 

여기서 $k=p$인 경우에는(주파수가 같은 경우),

 

$$ \int _{0} ^{T} {e^{0}} dt = T$$

 

반면 주파수가 같지 않은 $k \ne p$인 경우에는, $q = k-p$로 치환하여 계산하면,

 

$$ \begin{align} \int _{0} ^{T} {e^{i \frac {2\pi qt}{T}}}dt  &= \frac{T}{i2\pi q} \left| e^{i\frac {2\pi qt}{T}} \right| ^{T} _{0} \\ &= \frac{T}{i2\pi q} (e^{i2\pi q} - e^{0} ) \\ &= \frac {T}{i2\pi q}(1-1) \\ &= 0 \end{align}$$ 

 

정리하면, 두 정현파의 내적은, 

• 주파수가 같으면 내적값은 $T$
• 주파수가 다르면, 내적값은 $0$이기에, 서로 직교한다.

이처럼 두 파형에 대해 주파수가 다르면 그 내적이 0이 된다. 이제, 이 성질을 이용하여, IDFT 수식을 유도해볼 것이다.

 

 

DFT에서 Inverse DFT 식의 유도

이 글의 위 쪽 편에서 DFT에 대한 식이 아래 식 (2)와 같았다.

 

$$ Y(k) = \sum _{n=0} ^{N-1} {y(n)e^{-i\frac{2\pi}{N}kn}}, \; \; 0 \leq k < N \tag {2}$$

 

신호의 직교성에 따른 특성을 이용하기 위해, $e^{i\frac{2\pi}{N}kn}$  파형을 양변에 곱해서 합을 구하게 해본다.

 

먼저, 식(2)의 양변에 $e^{i\frac{2\pi}{N}kn}$을 곱한다.

 

$$\begin{align} Y(k) \cdot e^{i\frac{2\pi}{N}kn}  = \sum_{p=0}^{N-1}y(p)e^{-i\frac{2\pi}{N}kp}\cdot e^{i\frac{2\pi}{N}kn} \end{align} \; \tag{3}$$

 

식 (3)에서, 뒤 편에 N개의 신호를 더하는 부분은, 원래 사용했던 $n$ 대신에 $p$를 사용했음에 유의한다.

원래의 $n$과는 다른 변수임을 표시하기 위해 다른 변수를 사용한 것이고, 아래편에서 이 $p$가 $n$과 같을 때와 다를 때를 나눠서 비교하게 된다.

 

이제 식 (3)에 $0$에서 $N-1$까지의 신호를 더한다. (두 신호를 내적 한다는 것이, 곱을 한 것에 대한 전체 합이기 때문에, 이렇게 합을 해주는 것임)

 

$$ \begin{align} & \sum_{k=0}^{N-1}Y(k) \cdot e^{i\frac{2\pi}{N}kn} \; \tag{4} \\ &= \sum_{k=0}^{N-1} \sum_{p=0}^{N-1} y(p)e^{-i\frac{2\pi}{N}kp}\cdot e^{i\frac{2\pi}{N}kn} \\ &= \sum_{k=0}^{N-1} \sum_{p=0}^{N-1} y(p)e^{i\frac{2\pi}{N}k(n-p)}\;  \tag{5} \end{align} $$

 

식 (5)에서 $ \sum_{k=0}^{N-1} e^{i\frac{2\pi}{N}k(n-p)} $는 $n \ne p$에서는 0이고, $n=p$인 경우에만 $N$이 된다. 

 

따라서 식 (5)에서 $n=p$의 경우에만 값을 가지기에 $y(p)$는 $y(n)$이 되고, 결국 $y(n)N$이 된다.

 

$$ \sum_{k=0}^{N-1} \sum_{p=0}^{N-1} y(p)e^{i\frac{2\pi}{N}k(n-p)} = y(n)N \; \tag{6}$$

 

이 부분이 좀 이해 안 될 수 있는데, p에 대해서 $0$에서 $N-1$까지 차례로 넣으면서 더하는 것이기에, $p=0$일 때 ~ $p=N-1$일 때의 값을 차례로 생각해보면, 결괏값이 이해될 것이다.

$ p=0: \; \sum_{k=0}^{N-1}  y(0)e^{i\frac{2\pi}{N}k(n-0)} \rightarrow 0$
$ p=1: \; \sum_{k=0}^{N-1}  y(1)e^{i\frac{2\pi}{N}k(n-1)} \rightarrow 0$
...
$ p=n: \; \sum_{k=0}^{N-1}  y(n)e^{i\frac{2\pi}{N}k(n-p)} \rightarrow y(n)N$
...
$ p=1: \; \sum_{k=0}^{N-1}  y(1)e^{i\frac{2\pi}{N}k(n-1)} \rightarrow 0$

 

결과적으로 식 (4)번의 값이 $y(n)N$이 되는 것이기에,

 

$$ \sum_{k=0}^{N-1}Y(k) e^{i\frac{2\pi}{N}kn} = y(n)N$$

$$ \therefore y(n) = \frac{1}{N}  \sum_{k=0}^{N-1}Y(k) e^{i\frac{2\pi}{N}kn} \tag{7} $$

 

식 (7)이 DFT에 대한 IDFT이고, 이렇게 IDFT 식에 대한 유도가 되었다.

 

식 (2)와 식 (7)을 다시 써보면,

 

$$ DFT: \; \; Y(k)=\sum_{n=0}^{N-1}{y(n)e^{-i\frac{2\pi}{N}kn}}, \; \; 0\leq k < N \tag {2} $$

$$ IDFT: \; \; y(n) = \frac{1}{N}  \sum_{k=0}^{N-1}Y(k) e^{i\frac{2\pi}{N}kn}, \; \; 0 \le n < N \tag{7} $$

 

---

DFT 및 IDFT에 대한 식의 유도가 끝났다.

 

DFT와 IDFT를 사용하는 입장에서는, 이러한 유도보다는, DFT 식이 어떤 의미를 가지는지, 그리고 어떻게 활용되는지가 더 중용하다. 

 

다음 페이지에서는 DFT 식이 과연 어떤 의미를 가지는지에 대해서 다룬다.

 

-끝-

 

이전글: 06-1. 이산시간 푸리에 변환(DTFT, Discrete Time Fourier Transform)

다음글: 06-3. DFT의 수식 이해

다음다음글: 06-4. 엑셀을 이용한 DFT 계산(1/4)