이산 푸리에 변환 (Discrete Fourier Transform, DFT) 은 주기가 $T$인 복소수열 $\{a_{n}\}$ 을 변환해 복소수열 $\{A_{n}\}$ 을 만드는 연산입니다.
$$ A_{n} = \sum_{k = 0}^{T - 1} a_{k} e^{i \frac{- 2 \pi k n}{T}} = \sum_{k = 0}^{T - 1} a_{k} \left\{ \cos\left( \frac{2 \pi k n}{T} \right) - i \sin\left( \frac{2 \pi k n}{T} \right) \right\} $$$i$는 허수 단위 $i$ , $\pi$는 원주율 $\pi$ , $\cos x$는 코사인함수 , $\sin x$는 사인함수 입니다.
$$ a_{n} = \frac{1}{T} \sum_{k = 0}^{T - 1} A_{k} e^{i \frac{2 \pi k n}{T}} = \frac{1}{T} \sum_{k = 0}^{T - 1} A_{k} \left\{ \cos\left( \frac{2 \pi k n}{T} \right) + i \sin\left( \frac{2 \pi k n}{T} \right) \right\} $$
$\{A_{n}\}$의 정의인 $A_{n} = \sum\limits_{k = 0}^{T - 1} a_{k} e^{i \frac{- 2 \pi k n}{T}}$에서 $\sum\limits_{k = 0}^{T - 1} A_{k} e^{i \frac{2 \pi k n}{T}}$ 를 계산해보면 된다.
어떤 수열 $\alpha_{n}$을 $\alpha_{n} = \sum\limits_{k = 0}^{T - 1} A_{k} e^{i \frac{2 \pi k n}{T}}$ 이라 하자.
$$
\begin{align}
\alpha_{n} & = \sum_{k = 0}^{T - 1} A_{k} e^{i \frac{2 \pi k n}{T}} \\
& = \sum_{k = 0}^{T - 1} e^{i \frac{2 \pi k n}{T}} \left( \sum_{m = 0}^{T - 1} a_{m} e^{i \frac{- 2 \pi m k}{T}} \right) \\
& = \sum_{k = 0}^{T - 1} \left( \sum_{m = 0}^{T - 1} a_{m} e^{i \frac{2 \pi k n}{T}} e^{i \frac{- 2 \pi m k}{T}} \right) \\
& = \sum_{k = 0}^{T - 1} \left( \sum_{m = 0}^{T - 1} a_{m} e^{i \frac{2 \pi k (n - m)}{T}} \right) \\
& = \sum_{k = 0}^{T - 1} \sum_{m = 0}^{T - 1} a_{m} e^{i \frac{2 \pi k (n - m)}{T}} \\
& = \sum_{m = 0}^{T - 1} \sum_{k = 0}^{T - 1} a_{m} e^{i \frac{2 \pi k (n - m)}{T}} \\
& = \sum_{m = 0}^{T - 1} \left( \sum_{k = 0}^{T - 1} a_{m} e^{i \frac{2 \pi k (n - m)}{T}} \right) \\
& = \sum_{m = 0}^{T - 1} \left( a_{m} \times \sum_{k = 0}^{T - 1} e^{i \frac{2 \pi k (n - m)}{T}} \right)
\end{align}
$$
이제 $\sum\limits_{m = 0}^{T - 1} \left( a_{m} \times \left( \sum\limits_{k = 0}^{T - 1} e^{i \frac{2 \pi k (n - m)}{T}} \right) \right)$의 연산만 해주면 된다.
$n = m$이면 $n - m = 0$에서 $\sum\limits_{k = 0}^{T - 1} e^{i \frac{2 \pi k (n - m)}{T}} = \sum\limits_{k = 0}^{T - 1} e^{0} = \sum\limits_{k = 0}^{T - 1} 1 = T$이다.
$n \not= m$이면 등비수열의 합 공식 $\sum\limits_{k = 0}^{T - 1} a^k = \frac{a^T - 1}{a - 1}$ 에서 $\sum\limits_{k = 0}^{T - 1} e^{i \frac{2 \pi k (n - m)}{T}} = \sum\limits_{k = 0}^{T - 1} \left(e^{i \frac{2 \pi (n - m)}{T}}\right)^k = \frac{\left(e^{i \frac{2 \pi (n - m)}{T}}\right)^{T} - 1}{e^{i \frac{2 \pi (n - m)}{T}} - 1} = \frac{e^{i 2 \pi (n - m)} - 1}{e^{i \frac{2 \pi (n - m)}{T}} - 1}$이다.
$T$값에 관계없이 두 정수 $n$, $m$에서 $n - m$은 정수이고, 임의의 정수 $q$에 대해 $e^{i 2\pi q} = 1$이므로 $\frac{e^{i 2 \pi (n - m)} - 1}{e^{i \frac{2 \pi (n - m)}{T}} - 1} = 0$이다.
따라서 $\sum\limits_{m = 0}^{T - 1} \left( a_{m} \times \left( \sum\limits_{k = 0}^{T - 1} e^{i \frac{2 \pi k (n - m)}{T}} \right) \right)$에서 $\left( \sum\limits_{k = 0}^{T - 1} e^{i \frac{2 \pi k (n - m)}{T}} \right)$의 값은 $n = m$일 때만 $T$의 값을 가지므로, $\sum\limits_{m = 0}^{T - 1} \left( a_{m} \times \left( \sum\limits_{k = 0}^{T - 1} e^{i \frac{2 \pi k (n - m)}{T}} \right) \right) = \sum\limits_{m = 0}^{T - 1} \left( a_{m} \times T \times \left[ n = m \right] \right) = T a_{n} = \alpha_{n}$이라 할 수 있다. ($\left[ P \right]$ 는 아이버슨 괄호 )
따라서, $T a_{n} = \alpha_{n} = \sum\limits_{k = 0}^{T - 1} A_{k} e^{i \frac{2 \pi k n}{T}}$에서 $a_{n} = \frac{1}{T} \sum\limits_{k = 0}^{T - 1} A_{k} e^{i \frac{2 \pi k n}{T}}$ 이다.
이산 푸리에 변환의 합성곱 (Convolution) $$ c_{n} = \sum_{k = 0}^{T - 1} a_{k} b_{n - k} $$ 이면 $$ C_{n} = A_{n} B_{n} $$ 이다.수열 $\{b_{n}\}$의 주기가 $T$이므로, $c_{n}$의 정의중 $b_{n - k}$에서 $n - k$가 음수일 때는 $b_{0} = b_{T}$, $b_{-1} = b_{T - 1}$...로 생각하면 됩니다. ($b_{(n - k) \pmod{T}}$)
$$
\begin{align}
C_{n} & = \sum_{k = 0}^{T - 1} c_{k} e^{i \frac{- 2 \pi k n}{T}} \tag{1} \\
& = \sum_{k = 0}^{T - 1} \left(\sum_{m = 0}^{T - 1} a_{m} b_{k - m}\right) e^{i \frac{- 2 \pi k n}{T}} \tag{2} \\
& = \sum_{k = 0}^{T - 1} \sum_{m = 0}^{T - 1} a_{m} b_{k - m} e^{i \frac{- 2 \pi (k - m) n}{T}} e^{i \frac{- 2 \pi (m) n}{T}} \tag{3} \\
& = \sum_{m = 0}^{T - 1} \sum_{k = 0}^{T - 1} a_{m} b_{k - m} e^{i \frac{- 2 \pi (k - m) n}{T}} e^{i \frac{- 2 \pi (m) n}{T}} \tag{4} \\
& = \sum_{m = 0}^{T - 1} a_{m} e^{i \frac{- 2 \pi (m) n}{T}} \sum_{k = 0}^{T - 1} b_{k - m} e^{i \frac{- 2 \pi (k - m) n}{T}} \tag{5}\\
& = \sum_{m = 0}^{T - 1} a_{m} e^{i \frac{- 2 \pi (m) n}{T}} B_{n} \tag{6}\\
& = B_{n} \sum_{m = 0}^{T - 1} a_{m} e^{i \frac{- 2 \pi (m) n}{T}} \tag{7}\\
& = A_{n} B_{n} \tag{8}
\end{align}
$$
$(1)$번식 증명 : 이산 푸리에 변환의 정의
$e^{i \frac{-2\pi x n}{T}} = \operatorname{Expi}(x)$ 라 하면, $\operatorname{Expi}(x + T) = \operatorname{Expi}(x)$ 라는 것을 알 수 있다.
$(1) \to (2)$ 증명 : 수열 $\{c_{n}\}$의 정의
$(2) \to (3)$ 증명 : 지수법칙 사용, $e^{i \frac{-2 \pi k n}{T}} = e^{i \frac{-2 \pi (k-m) n}{T}} \times e^{i \frac{-2 \pi (m) n}{T}}$
$(3) \to (4)$ 증명 : 합 순서 변경
$(4) \to (5)$ 증명 : $k$와 관계 없는 항인 $a_{m} e^{i \frac{- 2 \pi (m) n}{T}}$ 항을 옮겨줌
$(6) \to (7)$ 증명 : $m$과 관계 없는 항인 $B_{n}$ 항을 옮겨줌
$(7) \to (8)$ 증명 : 이산 푸리에 변환의 정의에 의해 $A_{n} = \sum\limits_{m = 0}^{T - 1} a_{m} e^{i \frac{- 2 \pi (m) n}{T}}$
$(5) \to (6)$ 증명
또, $\{b_{n}\}$은 주기가 $T$이므로, $b_{n + T} = b_{n}$이다.
따라서, $b_{n} \operatorname{Expi}(n) = \mathbb{B}_{n}$ 이라 하면, $\mathbb{B}_{n + T} = \mathbb{B}_{n}$이다.
$\sum\limits_{k = 0}^{T - 1} b_{k - m} e^{i \frac{- 2 \pi (k - m) n}{T}}$ 에서 $K = k - m$으로 치환하면 $\sum\limits_{k = -m}^{T - 1 - m} b_{K} e^{i \frac{- 2 \pi K n}{T}} = \sum\limits_{k = -m}^{T - 1 - m} \mathbb{B}_{K}$임을 알 수 있다.
$\mathbb{B}_{n}$의 주기성에서 $\mathbb{B}_{-m} = \mathbb{B}_{-m + T}$임을 알 수 있다.
따라서 $\sum\limits_{k = -m}^{T - 1 - m} \mathbb{B}_{K} = \sum\limits_{k = -m + 1}^{T - m} \mathbb{B}_{K}$이고, 마찬가지로 $\sum\limits_{k = -m}^{T - 1 - m} \mathbb{B}_{K} = \sum\limits_{k = -m + 1}^{T - m} \mathbb{B}_{K} = \sum\limits_{k = -m + 2}^{T - m + 1} \mathbb{B}_{K} = \cdots$ 이므로, $\sum\limits_{k = -m}^{T - 1 - m} \mathbb{B}_{K} = \sum\limits_{k = 0}^{T - 1} \mathbb{B}_{K}$ 임을 알 수 있다.
$\mathbb{B}_{K}$의 정의에서 $\sum\limits_{k = 0}^{T - 1} \mathbb{B}_{K} = \sum\limits_{k = 0}^{T - 1} b_{K} e^{i \frac{- 2 \pi K n}{T}}$이고, 이산 푸리에 변환의 정의에 의해 $B_{n} = \sum\limits_{k = 0}^{T - 1} b_{K} e^{i \frac{- 2 \pi K n}{T}}$이다.