푸리에 변환(Fourier Transform)

푸리에 변환

푸리에 변환이란 시간에 대한 신호 함수를 주파수에 대한 식으로 변환하는 것을 말한다. 성공적으로 변환을 한다면 노이즈와 여러 주파수가 섞인 신호에서 특정 주파수를 추출해낼 수 있다. 이것 외에도 푸리에 변환의 그 성질을 이용해서 어떤 연산을 더욱 쉽게 풀어쓸 수도 있다.

 

푸리에 변환의 깊은 뜻 말고 단순히 문제풀면서 겪었던 몇 가지만 적어보면 다음과 같다.

1. convolution
   • 두 수열의 convolution을 구할때 일반적으로 n^2의 연산이 필요로 한다.
   • fourier transform으로 변환 후 convolution을 빠르게 할 수 있다.
2. 큰 수의 곱셈
   • 곱셈은 일반적으로 자리수의 제곱에 해당하는 연산을 필요로 한다.
   • fourier transform으로 변환 후 곱셈을 빠르게 할 수 있다.
   • 카라추바, 쇤하게-슈트라센 방법도 있다.

이 외에도 많이 있겠지만 적절한 증명과 정리로 이 정도 이해하는 것이 목표다.

 

푸리에 변환으로 인해 얻는 장점들이 있으니 이 장점이 크다면 임의의 수열을 연산할 때 푸리에 변환 -> 연산 -> 역변환을 통한 해결도 가능할 것이다. 그러면 변환, 역변환하는 방법을 먼저 이해하고 연산의 한 종류인 convolution에 대해 알아보자. 그리고 마지막으로 20세기 최고의 알고리즘이라는 FFT까지 이해해보자.

 

아래에서 여러 식들이 나올텐데, 혼란을 방지하고자 미리 정리하자면 "대문자 수열 = 소문자 수열을 푸리에 변환한 결과" 라고 정의한다.

 

Orthogonal Functions

Orthogonal Functions은 푸리에 변환을 이해하기 위해 가장 선행되어야 하는 정리라고 생각한다.
$$ \langle f,g\rangle = \int f(x)g(x)dx $$

$ \langle f,g\rangle = 0 $ 을 만족하는 f와 g에 대해서 직교한다고 정의한다. 그리고 이를 만족하는 집합을 orthogonal set이라고 한다. (직교한다는 의미는 수직 하고는 관계없고 식 그대로 적분의 결과가 0일뿐이다)

어떤 구간에서의 orthogonal set ${V_1, V_2, ..., V_n}$ 을 구했으면 이를 이용해서 그 구간에서의 모든 함수를 표현할 수 있다.
$$ f(x) = \sum_{i=0}^{n} C_i V_i $$

이제 구간 [0, T]에서 $ \phi_k (t) = e^{2 \pi ikt/T} $ 의 함수를 한번 살펴보자.
임의의 다른 수 p와 q에 대해서 $ \int_{0}^{T} \phi_q (t) \phi_p (t)\ dt $ 는 놀랍게도 0이다.
$$ \begin{align} \sum_{t=0}^{T} \phi_q (t) \phi_p (t) &= \sum_{t=0}^{T} e^{2 \pi iqt/T}\ e^{2 \pi ipt/T} \\
&= \sum_{t=0}^{T} e^{2 \pi (q+p)t/T} \\
&= \frac{1 - (e^{2 \pi i(q+p)/T})^{T}}{1 - e^{2 \pi i(q+p)/T}} \\
&= \frac{1 - e^{2 \pi i(q+p)}}{1 - e^{2 \pi i(q+p)/T}} \end{align} $$

 

여기서 $p + q$는 정수이다. 그러면 $ e^{2 \pi in} $ 라는 수를 생각해보자.
Euler's formula 에 의해 $ e^{ix} = \cos x + i \sin x $ 이다. 이를 이용해서 다시 마지막 식을 정리하면 0이 나온다.
$$ \frac{1 - e^{2 \pi i(q+p)}}{1 - e^{2 \pi i(q+p)/T}} = 0 $$

 

따라서 $ \phi_k (t) = e^{2 \pi ikt/T} $ 는 구간 [0, T]에서 orthogonal set임을 알 수 있고 이 구간에서 모든 함수를 표현할 수 있다. 푸리에 변환할 때 나오는 복잡해 보이는 $ e^{2 \pi ikt/T} $ 꼴을 이제 그럴듯하게 느낄 수 있다.

 

Discrete Fourier Transform (DFT)

위 정리를 이용한 수열 $ a_{n} $ 의 이산 푸리에 변환 $ A_{n} $ 이다.
$$ A_{n} = \sum_{j=0}^{N-1} e^{-2 \pi ijn/N} a_{j} $$

 

Inverse Discrete Fourier Transform (IDFT)

반대로 수열 $ A_{n} $ 로부터 수열 $ a_{n} $을 구하는 역변환이다.
$$ a_n = \frac{1}{N} \sum_{j=0}^{N-1} e^{2 \pi ijn/N} A_{j} $$

 

convolution

$a$와 $b$의 convolution 결과인 $c$는 다음과 같다.
$$ \begin{align} c_m &= a[m] * b[m] \\
&= \sum_{k=0}^{N-1} a[k] b[m-k] \end{align} $$

식 그대로 연산을 하면 하나의 항을 구하기 위해 n번의 연산이 필요하다. 그러면 식 변환을 통해 푸리에 변환 꼴로 바꿨을 때 연산이 어떻게 바뀌는지 확인해보자.
$$ \begin{align} \sum_{k=0}^{N-1} a[k] b[m-k] &= \sum_{k=0}^{N-1} [\frac{1}{N}\sum_{n=0}^{N-1} A[n] e^{2\pi ikn/N}][\frac{1}{N}\sum_{l=0}^{N-1} B[l] e^{2\pi i(m-k)l/N}] \\
&= \frac{1}{N}\sum_{n=0}^{N-1}A[n]\sum_{l=0}^{N-1}B[l]\frac{1}{N} \sum_{k=0}^{N-1}e^{2\pi ikn/N} e^{2\pi i(m-k)l/N} \\
&= \frac{1}{N}\sum_{n=0}^{N-1}A[n]\sum_{l=0}^{N-1}B[l] e^{2\pi iml/N} \frac{1}{N}\sum_{k=0}^{N-1}e^{2\pi ik(n-l)/N} \\
&= \frac{1}{N}\sum_{n=0}^{N-1}A[n]\sum_{l=0}^{N-1}B[l] e^{2\pi iml/N}\delta[n-l] \\
&= \frac{1}{N}\sum_{n=0}^{N-1}[A[n]B[n]]e^{2\pi imn/N} \end{align} $$

 

마지막 식을 보면 $ A[m]B[m] $ 의 IDFT임을 알 수 있다.

따라서 convolution의 결과인 $ c_m $ 을 구하기 위해 n번의 연산이 필요했던 식을, 푸리에 변환한 수열의 $ A[m] \times B[m] $ 단순 곱셈 한 번으로 바꿀 수 있다. 이렇게 DFT, convolution, IDFT 과정을 통해 convolution를 계산하는데 빠른 속도를 보여주는 듯했지만 DFT, IDFT의 변환 과정에서 $n^2$의 연산이 필요하므로 이대로는 무의미하다.

그래서 똑똑하신 분들이 DFT, IDFT를 빠르게 하는 Fast Fourier Transform를 만들었다. 내용이 길어지니 집중력을 위해 FFT는 다음 글에서 정리한다.

 

결론만 적자면 FFT를 이용해서 DFT, IDFT를 $O(nlog_{2}n)$ 만에 할 수 있고, 따라서 convolution 계산의 총 시간복잡도는 $ O(nlog_{2}n) $ 이다.