*여기에 설명된 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)에 곱해서 적분한다고 하면, 삼각함수의 특징을 잘 이용해 줄 수 있게 되는 것이다.

이해 안가는 부분은 댓글로. -_-;
by snowall 2009. 2. 22. 10:07
  • Lex 2009.02.26 14:54 ADDR EDIT/DEL REPLY

    답변 감사드립니다. ^^
    마지막 그림이 잘 이해가 안되어서 며칠 고민했습니다. ㅋ
    전에 메일 답변에서 FFT는 수학적 사고 방식이라고 하셨는데, 샘플링 이론과 오버랲핑 이론을 이용하면 물리적으로 설명할 수 있지 않을까요? 계속 그림을 그려가면서 고민을 하고 있는데, 저의 배경지식으로는 잘 풀리지가 않습니다. ㅜㅜ;

    그리고, 한 가지 더 질문이 생겼습니다.
    푸리에 급수와 계수를 복소표현으로 전개할 때, 급수는 e의 지수로 양의 부호를 가지고, 계수는 e의 지수로 음의 부호를 갖습니다.
    그런데, 급수에서 시그마의 구간의 표현을 조금만 바꾸면, 급수와 계수의 e의 지수의 부호는 서로 바뀝니다. 즉, 음의 주파수와 양의 주파수가 서로 바뀝니다. 그런데, 이 음의 주파수와 양의 주파수는 원래의 신호가 가지고 있는 성분입니다.(맞죠? 아직 정립이 잘 안되서..^^;) 그렇다면, 부호의 차이는 어떠한 영향도 끼치기 않는다고 생각합니다. 그런데, 어째서 급수는 양의 부호를 가지고 계수는 음의 부호를 가지게 된거죠?
    그리고, 불연속 푸리에 변환을 할 때, 음의 주파수에 대한 언급은 없습니다. 음의 주파수는 아무런 가치가 없는건가요?

    혹시나 저의 질문에 오류가 있다면 댓글 달아주십시오. 정정하겠습니다. ^^

    그럼, 답변 부탁드립니다.

    • snowall 2009.02.26 20:12 신고 EDIT/DEL

      푸리에 변환이든 샘플링이든 오버랩핑이든 본질은 "물체의 운동을 여러개의 함수의 합으로 표현한다" 맞죠?

      가령, 어떤 시분할 함수를 주파수 분할 함수로 바꿔서 본다고 합시다. 그런데 세상에는 주파수 분할 형태로 전달되는 "현상"이 없어요. 우리가 실제로 관찰할 수 있는 것은 전부 시분할 함수일 뿐이죠. 우리는 주파수 자체를 관찰할 수가 없습니다. 다만 시분할 함수를 관찰한 후 거기서 주파수에 관한 정보를 알아낼 수 있을 뿐입니다.

      따라서 푸리에 변환은 물리적/공학적 응용이 너무나 많지만 어디까지나 수학적 도구에 불과합니다. 그 물리적 실체는 없다고 봐도 좋습니다.

      한가지 예상 가능한 반론으로서, 자유공간을 돌아다니는 전자의 파동함수를 생각해 볼 수 있습니다.(단 1개의 진동수를 가지는 삼각함수만으로 표현됩니다) 하지만 이 경우에는 전자의 위치와 운동량의 불확정성이 무한대가 되어버리므로 우리가 관찰하는 전자와는 관련이 없게 됩니다.

    • snowall 2009.02.26 20:17 신고 EDIT/DEL

      어떤 함수의 푸리에 계수를 구할 때 지수의 부호의 차이가 영향을 주지 않는다면 그런 함수는 Even function이겠군요.
      Odd function은 항의 부호가 바뀝니다.(지수 말고...)

      보통, exp(i*t)를 생각할 때 t가 커지면 저 삼각함수는 복소 평면에서 반시계 방향으로 돌아갑니다. 그리고 그게 보통 사람들이 생각하는 "+방향"이죠. 그렇다면, exp(i*t)에서 t가 커질 때의 경우를 생각해서 푸리에 급수를 전개하게 되면, 당연히 exp(i*t)에서 급수에서 나오는 지수의 부호는 +가 됩니다.
      물론 이걸 상쇄시켜서 적분해야 원래의 함수가 나오게 되므로 계수에 있는 지수의 부호는 -가 되겠죠.

    • snowall 2009.02.26 20:18 신고 EDIT/DEL

      불연속 푸리에 변환은 구간이 정해져 있으므로 그 구간 내에서 값들이 +가 되든 -가 되든 별로 중요하지 않습니다.
      그리고 어차피 삼각함수니까 Even과 Odd를 나눠서 구하게 된다면, Odd인 부분들은 다 사라지는거 아닌가 싶기도 하네요.

  • Lex 2009.02.27 13:38 ADDR EDIT/DEL REPLY

    답변 감사드립니다. ^^
    아직 Even function과 Odd function에 대한 지식이 부족하여, 이해하려고 노력중입니다. ㅋ

    마침내, 어제 참고서(파동의 모험)를 정독으로 다 읽었습니다.
    그래서, 처음부터 끝까지 머리속으로 정리를 하려고 하는데, 갑자기, 처음부터 걸리는게 있어서 또 질문을 드리려고 합니다.(너무 귀찮게 해드리는거 같아 미안하네요. ^^;)

    갑작스레 막힌 부분은 바로 "모든 복잡한 파동은 단순 파동의 합으로 나타낼 수 있다."라는 가설이었습니다. 하지만, 그 가설을 머리에 넣고 책을 끝까지 정독하였는데도, 그 가설에 대한 증명은 어디에도 없었던겁니다. 순간, 머리가 멍~ 해지면서, "과연 내가 뭘 공부했지?"라는 생각이 스쳤습니다. 그래서, 인터넷으로 푸리에급수에 대한 증명을 찾아봤는데, 증명이 안되었다는 얘기도 있고, 속시원한 정보를 찾을 수가 없었습니다. ㅠㅠ;

    푸리에급수는 증명이 되었나요? 되었다면, 그 증명을 어디서 볼 수 있죠? 그리고, 안되었다면 증명도 안된 공식을 어떻게 쓸 수가 있는거죠?

    질문에 오류가 있다면 댓글 달아주십시오. 정정하겠습니다. ^^

    그럼, 답변 부탁드립니다.

    • snowall 2009.02.27 14:03 신고 EDIT/DEL

      물론 증명되었죠. :)
      푸리에 급수가 원래 함수로 수렴한다는 것은 증명할 수 있습니다.
      저는 아래의 책을 보고 공부했었습니다.
      Fourier Analysis: An Introduction (Princeton Lectures in Analysis, Volume 1)
      by Elias M. Stein (Author), Rami Shakarchi (Author)
      # ISBN-10: 069111384X
      # ISBN-13: 978-0691113845
      근데 이해하려면 수학적으로 좀 높은 수준이 필요해서요...;; (수학과에서는 4학년때 배웁니다. 대학원 가서 제대로 배우게 되구요)
      Lebesgue의 일반적인 Measure Theory를 어느정도 이해하고 Lebesgue Integral에 대해서 개념적인 이해가 필요합니다.

      하지만. 물론! 푸리에 급수를 유한 항까지 전개한 수열과 원래 함수를 빼서, 그 뺀 함수의 절대값의 제곱이 0으로 수렴한다는 것을 증명하면 되긴 합니다. 다만, "함수 수열의 수렴"이라는 것이 "함수의 수렴"도 아니고 "수열의 수렴"도 아니고 "급수의 수렴"도 아니어서 이해하는데 난감할 수도 있습니다.

  • Lex 2009.02.27 22:15 ADDR EDIT/DEL REPLY

    헉.. 그렇군요. ㅜㅜ;
    어느 정도의 선수지식을 동반하지 않고서는 이해하는데 무리가 있겠군요. 생각 같아서는 끝까지 파보고도 싶지만, 푸리에변환을 어느 정도 이해했다는 것만으로 만족을 해야겠네요. ㅠㅠ;
    오디오코덱에서는 FFT 이외에는 거의 쓰이지 않지만, 음성코덱에서는 LPC나 LSP 같은 DSP 알고리즘들이 쓰이고 있어, 이제는 그 쪽으로 눈을 돌려야 할 것 같습니다. 혹시, LPC나 LSP의 개념에 대해서 알기 쉽게 나온 책이나 필요한 선수지식이 있으면 좀 알려주십시오. 단순한 코더로 남기는 싫어서 발악을 하고 있는데, 쉽지가 않네요. ㅋ ^^;

    그럼, 궁금한게 있으면 또 여쭤보러 오겠습니다. ^^

    • snowall 2009.02.28 00:24 신고 EDIT/DEL

      DSP에 대해서는 "디지털 신호 처리"라는 것 외에는 전혀 모릅니다. -_-;;;;
      저는 전공이 물리와 수학일 뿐, 공학은 잘 몰라서요...;;;
      질문은 언제든 환영입니다. 제가 답할 수 있다면....