*여기에 설명된 FFT는 단순히 개념만을 설명하고 있다. 실제적인 알고리즘은 좋은 책과 인터넷 검색을 활용하여서 정확한 내용을 이해한 후에 사용하여야 한다.
푸리에 변환은 현대 공학에서 아주아주아주 다양한 범위에서 응용되는데, 그것은 실제 세상을 분석하는 실질적이면서 강력한 도구이기 때문이다. 하지만 앞서 얘기했듯, 푸리에 변환은 적분에 관한 문제이고 적분을 잘 하는 것은 아주아주아주 어려운 문제이다. 그러므로 이것은 대단히 힘든 일이 된다. 적분은 누구에게나 어려운 일인데, 하물며 수식을 이해조차 못하는 컴퓨터가 어떻게 푸리에 변환을 할 수 있을까? 그래서, 연속체에 관련된 적분 문제를 컴퓨터도 잘 할 줄 아는 단순한 덧셈으로 바꿔서 비교적 정확한 푸리에 변환을 하는 것이 DFT가 된다. 하지만 DFT는 N개의 구간으로 나눴을 때 N*N개의 계산을 하는 방법이다. 좀 더 획기적인 방법이 등장하는데, 그것이 빠른 푸리에 변환(Fast Fourier Transform=FFT)이다. 빠른 푸리에 변환은 실제로 N*N번 걸릴 계산을 N*logN번 정도로 줄여주게 된다.
가장 기본적으로, 푸리에 변환에서 사용하는 함수들이 지수함수라는 것을 생각해보자.
$e^{a}*e^{b}=e^{a+b}$
잘 보시라, 지수 함수와 로그 함수의 가장 큰 특징은 덧셈과 곱셈을 서로 바꿔 쓸 수 있다는 것이다. 지수함수에서는 곱셈이 덧셈으로 바뀌고, 로그 함수에서는 덧셈이 곱셈으로 바뀐다. 아무튼 가장 중요한 특성은 지수 밑에 있던 곱셈이 지수 위에서 덧셈으로 변신했다는 사실.
그럼, DFT에 나오는 수식을 잘 살펴보자.
$a_1=f(n2\pi/N)*e^{ik(n2\pi/N)$
저걸 $a_1$이라고 부르자.
그런데 푸리에 변환에서 나와야 하는 것은 함수이므로 k가 변하게 되면 계산을 새로 해야 한다.
하지만 – 간과해서는 안되는 사실이 있다. 저기에 더하기 전에 곱하는 숫자는 바로 크기가 1인 지수함수라는 것. 아무리 곱해도 크기는 변하지 않으며, 그 위상각만 계속 돌아간다. 게다가, 만약 구간을 정수인 N등분 해 놓는다면 k가 커지면서 계산해야 할 계수는 새로 계산할 필요 없이, $e^{i(n2\pi/N)$을 계속 곱해가면서 계산하면 된다.
$e^{i(n2\pi/N)$를 2번 먼저 곱하고 3번 곱하든, 3번 먼저 곱하고 2번 곱하든, 5번 곱했다는 사실은 변함이 없다. 바로 이런 성질을 이용하는 것이다.
우선, 귀찮으니까 $e^{i(n2\pi/N)$를 w라고 쓰고, $w(k)=w^k$라고 하자.
가령, 점이 4개 있다고 해 보자. 0, 1, 2, 3이라는 번호를 붙여보자. 그럼 4개의 점은 x(0), x(1), x(2), x(3)이 된다.
이 점 4개에 대한 이산 푸리에 변환은 다음과 같다
$X(0)=x(0)w(0)+x(1)w(1*0)+x(2)w(1*0)+x(3)w(1*0)$
$X(1)=x(0)w(0*1)+x(1)w(1*1)+x(2)w(2*1)+x(3)w(3*1)$
$X(2)=x(0)w(0*2)+x(1)w(1*2)+x(2)w(2*2)+x(3)w(3*2)$
$X(3)=x(0)w(0*3)+x(1)w(1*3)+x(2)w(2*3)+x(3)w(3*3)$
$w(k+N)=w(k)$인 성질을 이용해서 정리해주면 (이 성질이 가장 중요하다. 이러한 성질이 없다면, FFT는 불가능하고 DFT전체를 계산해야만 한다. 곱셈의 교환법칙과 유한군론의 승리.)
$X(0)=x(0)w(0)+x(1)w(0)+x(2)w(0)+x(3)w(0)$
$X(1)=x(0)w(0)+x(1)w(1)+x(2)w(2)+x(3)w(3)$
$X(2)=x(0)w(0)+x(1)w(2)+x(2)w(0)+x(3)w(2)$
$X(3)=x(0)w(0)+x(1)w(3)+x(2)w(2)+x(3)w(1)$
이 수식을 뚫어지게 쳐다보면, 이미 계산한 항이 여러번 등장하고 있는 것을 확인할 수 있다.
다시말해서, DFT를 계산할 때 저걸 전부 계산한다면 보다시피 N*N번의 계산을 전부 다 해야 한다. 하지만, 반복되는 부분을 잘 알고 있다가, 다음번에 계산할 때 써먹는다면 계산 비용이 절약된다. FFT는 수식을 뚫어지게 쳐다본 사람의 승리라고 할 수 있겠다.
하지만, 아무리 컴퓨터라도 저 숫자들을 다 외우고 있다보면 머리가 아프겠지. (응?)
정확하게는, 짝수항과 홀수항으로 나누고, 그 짝수항과 홀수항으로 나눈 것을 다시 각각 짝수항과 홀수항으로 나누고, 이 것을 반복해서 2항 푸리에 변환이 될 때까지 계속한다. 그 다음에, 조각난 푸리에 변환을 적당히 더해서 전체 푸리에 변환을 완성하게 된다.
$x(0)w(0)+x(2)w(0)$과 $x(0)w(0)+x(2)w(2)$을 계산하고, $x(1)w(0)+x(3)w(0)$과 $x(1)w(1)+x(3)w(3)$을 계산한다.
$E1=x(0)w(0)+x(2)w(0)$
$E2=x(0)w(0)+x(2)w(2)$
$E3=x(1)w(0)+x(3)w(0)$
$E4=x(1)w(1)+x(3)w(3)$
라고 해보자.
$X(0)=E1+E3$
$X(1)=E2+E4$
$X(2)=E1+E3*w(2)$
$X(3)=E2+E4*w(2)$
이렇게 된다.
처음의 DFT에서 16번의 곱셈과 12번의 덧셈이 있었다면, 나의 4점 FFT에서는 10번의 곱셈과 8번의 덧셈이 있게 되었다. 확실히 줄어들었다. (왜 NlogN번이 아니냐고는 묻지도 따지지도 말자. -_-; 숫자가 작아서 그렇다.)
숫자가 적을 때는 그다지 차이가 없지만, 만약 이 숫자가 100만개 정도 된다면 그땐 무시할 수 없는 정도로 차이가 나게 된다.
자. 그런데, 이런 것을 도대체 어떻게 이해하면 좋을까.
gnuplot의 도움을 받아서 다음 그림을 그려보았다.
그림이 좀 흐릿하지만, 대충 보자. 어느쪽이 x축이고 y축인지는 중요하지 않다.
여기서는 sin함수를 계산했지만, 대충 exp(ikx)함수라고 생각하도록 한다. 복소수 삼각함수는 그림으로 그릴 방법이 없다.
x=1인 선을 따라갈 때 생기는 함수를 알고 있을 때, x=2인 선을 따라갈 때 생기는 함수는 어떻게 계산할까? 당연히 제곱하면 된다. (사인공식에도 나오지만, 제곱하면 함수 안의 계수가 2배가 된 다른 사인함수로 변신한다.) 제곱이라는 건 자기 자신을 곱하는 것이다. x=3인 선을 따라갈 때 생기는 함수는, 다시 자기 자신을 한번 더 곱하면 알 수 있게 된다. 잘 보면 알겠지만, x가 1인 선을 따라서, y가 -2에서 2까지 변할 때 생기는 함수는 x가 2인 선을 따라서 y가 0에서 2까지 변할때 생기는 함수와 똑같이 생겼다. 잡아 당겨서 늘려주기만 하면 똑같다.
즉, 삼각함수는 제곱해서 생긴 함수의 일부가 원래의 함수와 같다. (프랙탈…그런건 따지지 말자. 프랙탈 아니다.)
저런걸 함수 f(x)에 곱해서 적분한다고 하면, 삼각함수의 특징을 잘 이용해 줄 수 있게 되는 것이다.
이해 안가는 부분은 댓글로. -_-;
댓글 남기기