*실제 계산에서는 적분이나 지수함수에 $2\pi$만큼이 곱해지거나 나눠지거나 등등의 일이 일어나므로, 정확한 공식은 책을 찾아보고 상황에 적합한 것을 사용할 것을 권한다. 아래의 설명 및 이 블로그에서의 설명은 모두 정규화(Normalization)을 하지 않은 개념 이해를 위한 설명일 뿐이다.

*이 글의 댓글을 참고하여 논리적/수학적인 오류가 내포되어 있을 수 있음을 경고해 두는 바이다. 전체적인 맥락의 이해에서는 맞지만, 여기 나온 공식들을 그대로 적용하려고 할 때는 문제가 발생할 수 있으므로 다른 좋은 책들을 참고할 것을 강력히 권장한다.

원래는 푸리에 변환의 실제 계산들을 해보려고 했으나, 사실 푸리에 변환을 계산한다는 것이 $e^{ikx}$를 곱해서 잘 적분하면 끝나는 것인지라 이건 오히려 적분 기술에 가까워서 그만 두었다. 어떤 함수의 푸리에 변환이 궁금하면 적분을 잘 해보시기를. 부분적분과 치환적분을 여러번 잘 사용해야 한다. 그리고 인터넷 검색하면 대표적인 함수들의 푸리에 변환 표가 있으니까 참고해도 좋다. 이보다 어려운 문제는 보통 더 많은 함수들의 푸리에 변환 표를 찾아보거나, Maple 이나 Mathematica 등의 수학 프로그램을 쓰면 된다. 그것도 없으면 곧 다음 문단에서 소개할 DFT를 이용하면 된다.
http://ipml.ee.duth.gr/~papamark/circuits/Table%20of%20Fourier%20Transforms.htm
http://www.mas.ecp.fr/Personnel/lilla/classes/image_processing/pdf/FourierTransformPairs.pdf

이번 시간에는 이산 푸리에 변환(Discrete Fourier Transform=DFT)에 대해서 알아보도록 하겠다.
사실 DFT 자체는 그다지 효용이 없다. 하지만 이걸 응용하면 빠른 푸리에 변환(Fast Fourier Transform=FFT)이 가능하고, FFT는 현대 통신 기술의 중요한 방법론 중의 하나이므로 우선 DFT를 소개하는 것이 좋겠다.

말은 아주 거창하게 했으나 실제로 DFT는 대단히 간단하고, 따라서 이 글도 짧다.

푸리에 변환의 요점은 오직 "적분을 하면 된다"는 점이다. 그런데 대부분, 무한히 많은 수의 함수들은 적분을 할 수 없거나 적분하기 힘든 함수들이다. 함수 형태가 딱히 해석적인 형태로 주어지지 않고 모든 점에 주어진 숫자로 이루어진 경우도 있다. 이런 식으로, 적분하기 괴로울 때 수학자들이 사용하는 방법은 원점으로의 회귀다. 적분은 원래 아주 많은 것들을 더하다가, 무한을 발견하게 되어 무한히 많은 것을 어떻게 더할지 고민하다가 등장한 계산법이다. 따라서, 적분은 원래 덧셈이고, 그 덧셈은 원래 연속적인게 아니라 띄엄띄엄하게 끊어져 있었다. 즉, Discretization이다.

그리하여,
$\int_0^{2\pi}dx e^{-ikx}f(x) \rightarrow \sum_{n=0}^{N-1} exp(-ikn\frac{2\pi}{N})f(n\frac{2\pi}{N})\frac{2\pi}{N}$
가 DFT의 중심 공식이 된다. 각각 적분기호는 합산 기호로, 적분 구간은 수열 번호로, 적분소 dx는 한 구간의 길이로 바꾸면 된다. 이제, 푸리에 변환은 함수값을 여러개 찾아서 모두 더하는 덧셈으로 바뀌었기 때문에 컴퓨터를 이용해서 계산할 수도 있다. (물론 사람이 할 수도 있다)
푸리에 변환은 어떤 함수로부터 다른 함수를 구하는 것이므로, 위의 함수는 k가 결정되면 함수값이 결정되는 함수일 것이다.

사실 이건 공식이랄것도 없이, 연속적인 적분을 구분구적법처럼 다시 표현한 것에 불과하다. 실제로 구분구적법은 구간을 잘라낸 갯수인 N을 무한대로 보내는 극한을 취하지만 손으로 계산하거나 컴퓨터에게 일을 시킬 때 진짜로 N을 무한대로 보낼 수는 없으므로, 우리가 원하는 적당한 오차 범위와 계산 시간을 고려하여 N을 적당히 큰 숫자로 정하게 된다.
만약 원래 주어진 함수 자체가 끊어져서 들어온다면, 즉 주어진 함수가 모든 점에서의 값이 주어진 것이 아니라 유한한 수의 점에서만 함수값이 주어져 있다면 이 경우에는 연속적인 적분이 불가능하고 항상 덧셈으로 정의된 적분을 해야 한다. 이때는 변환과 역변환 사이에 오차가 없게 된다. 가령, n개의 점에서 함수값이 주어져 있다면, 즉 $(a_1, f(a_1)), (a_2, f(a_2)), ..., (a_n, f(a_n))$ 으로 함수가 주어져 있는 경우, 이것은 하나의 "벡터"라고 볼 수 있고 푸리에 변환은 저 벡터를 다른 벡터로 보내는 1차 변환이 된다. 물론 그 역변환도 가능하다.

한가지 생각해 보자. 이 계산을 다 하려면, 구간을 N개로 잘랐다고 할 때 몇번의 계산을 해야 할까? 함수값에 대입하는건 빼고, 덧셈과 곱셈을 수행하려면 N*N번의 계산을 해야 한다. (심각하게 고민해 보시기를)

*DFT에 관한 괜찮은 설명은 위키피디아를 찾아보면 된다.
http://en.wikipedia.org/wiki/Discrete_Fourier_transform
*Paul Bourke이라는 사람이 DFT에 대한 알고리즘과 구현에 대해 설명한 것도 있다.
http://local.wasp.uwa.edu.au/~pbourke/other/dft/

다음편 스포일러 : FFT는 계산 시간을 N*logN으로 줄일 수 있다.
by snowall 2007. 10. 8. 12:44
  • ileshy 2007.10.08 21:27 신고 ADDR EDIT/DEL REPLY

    이거 없으면 연구고 개발이고 다 집어쳐야죠.. 그런데 일반인들이 fft를 쓸때는 그저 푸리에 변환을 효율적으로 해주는것이라는 정도로 아는것으로 충분할 듯합니다. 뭐 fft 자체가 이론적으로 중요하지는 않쟎아요.. 물론 알고리즘 개발하시는 분이거나 깊이 공부하시는 분은 알아야 겠지만..

    • snowall 2007.10.09 00:39 신고 EDIT/DEL

      어떻든간에, 푸리에 변환은 조금 오래 되었지만, 여전히, 이공계에서 가장 강력하면서 가장 쓸만한 연구 도구입니다.

  • 무지개타고 2007.10.08 23:37 ADDR EDIT/DEL REPLY

    링크된 페이지를 봤는데요...
    머리에 쥐 날라 캅니다... -_-;;

    • snowall 2007.10.09 00:40 신고 EDIT/DEL

      링크된 페이지는 이해하시는게 아니라, 잘 모르거나 필요할 때 찾아서 참고하시면 됩니다. 머리에 쥐나실 필요 없어요. ^^;;;;

  • 2007.10.09 00:11 ADDR EDIT/DEL REPLY

    비밀댓글입니다

    • snowall 2007.10.09 00:40 신고 EDIT/DEL

      N등분한 것중에 n번째 요소를 표현한 겁니다.
      그건 그렇고, 교과과정이 바뀌었군요...

  • snowall 2007.10.09 11:35 신고 ADDR EDIT/DEL REPLY

    수식이 조금 이상하게 표현되었었군요 -_-; 사정상 IE에서 글을 썼는데, IE6에서는 수식 변환스크립트가 작동을 안하네요.

  • rainyvale 2007.10.09 11:56 ADDR EDIT/DEL REPLY

    물리학에서는 푸리에 변환에 대해 보는 관점이 좀 다른건가요? "각각 적분기호는 합산 기호로, 적분 구간은 수열 번호로, 적분소 dx는 한 구간의 길이로 바꾸면 된다."고 말씀하신 continuous-time 함수의 푸리에 변환에의analogy는 정확한 표현 같지만, 구분구적법을 언급하시면 좀 헷갈리게 되는것 아닌가 싶은데... 일단 DFT가 continuous-time 함수의 푸리에 변환의 적분을 합으로 바꾸어 극한을 취하는 형태라는 것이 저에게는 전혀 이해가 안된다는... 변환 식 자체에서는 극한을 취하지도 않쟎아요. 그냥 N point 함수이면 N개의 합을 취할 뿐이죠. 극한 취하는 과정 없이요. 그래서 저는 그냥 discrete-time 함수에서 discrete계수로의 변환이라고만 생각하고 있었네요.

    • snowall 2007.10.09 12:16 신고 EDIT/DEL

      관점이 다르기보다는, 제 설명 방식의 문제입니다.
      구분구적법과의 비유를 고쳐야겠네요. 조언 감사합니다.

  • rainyvale 2007.10.10 09:42 ADDR EDIT/DEL REPLY

    아직도 잘 이해가 안 가는 면이 있어서... ^^

    "실제로 구분구적법은 구간을 잘라낸 갯수인 N을 무한대로 보내는 극한을 취하지만 손으로 계산하거나 컴퓨터에게 일을 시킬 때 진짜로 N을 무한대로 보낼 수는 없으므로, 우리가 원하는 적당한 오차 범위와 계산 시간을 고려하여 N을 적당히 큰 숫자로 정하게 된다."
    이 부분은 여전히 오해의 소지가 있습니다. DFT에서는 N이 함수값이 0이 아닌 포인트들이 걸쳐있는 '길이' 이상이면 원래 신호를 복원할 수 있는 DFT계수들을 얻을수 있습니다. (보다 엄밀히 말하면, 원래 함수를 주기 N으로 반복시켜 놓은 함수를 복원할 수 있는 계수들을 얻을수 있죠. 따라서, 만일 N이 원래 함수의 길이보다 더 짧다면 계수로부터 복원된 함수는 aliasing이 생기게 됩니다.) N을 유한한 값을 취하기 때문에 생기는 오차범위 같은 건 애초에 없는 것이죠.

    그리고 공식의 우변에서는 f(n 2 pi / N)을 쓰셨는데 반드시 꼭 이럴 필요는 없습니다. DFT는 샘플링을 어떻게 하느냐와는 무관하게 discrete-time함수에서는 모두 성립됩니다. 즉, f() 안에서 쓰이는 샘플링 주기와 DFT공식에 있는 N은 다를수 있죠. (물론 나중에 continuous-time에서 해석할때 좀 더 신경써야 하긴 하지만 요...)

    그리고, 타이포 하나. 씨그마의 윗부분은 N-1까지이죠.

    역시 사람은 자기 관련분야에서는 까탈스러워지나 봅니다. ^^

    • snowall 2007.10.10 10:50 신고 EDIT/DEL

      이렇게까지 꼼꼼하게 보실 줄이야...^^; 감사합니다.
      우선, 변명부터 하자면, 제가 푸리에 변환을 배울 때는 DFT/FFT가 뒤에 있다고 못배웠고, 전산물리에서 배울 때는 알고리즘과 구현으로 바로 넘어가서 깊이있게 생각을 못했습니다.
      좀 더 공부해서 수정해보겠습니다. 그러나 시간이 부족해서 언제쯤 논리적으로 정확해질지는 모르겠네요. 그때까지는 주의사항을 달아둬야겠습니다. 아무튼 지적해주신 부분에 대해서는 좀 더 생각해보도록 하겠습니다. 감사합니다. ^^

    • snowall 2007.10.11 20:01 신고 EDIT/DEL

      원래 DFT라는 것이 끊겨서 들어오는 불연속 신호를 처리할 때 쓰이긴 하지만 연속적인 함수라고 해도 DFT로 변환할 수 있습니다. 이 경우에는 함수를 얼마나 조밀하게 자르느냐에 따라 오차가 달라지겠죠. 제가 말한 "오차"는 이 형태의 오차입니다.
      말씀하신대로 유한한 갯수의 신호를 변환할 때는 신호 갯수 이상의 N이기만 하면 오차 없이 변환과 역변환이 가능합니다. 이에 대한 설명은 수정하도록 하겠습니다.
      그리고 제가 글에 적은 공식은 정확한 공식이라기보다는 이해를 위한 공식입니다. 책이나 자료를 찾아보고 적은게 아니라 그냥 생각나는대로 적어둔 것이라 제가 아는 것 까지만 설명되어 있습니다. 나중에 보충하도록 해야겠네요.
      여러가지 조언 감사합니다. ^^

  • 정태영 2007.10.26 02:03 ADDR EDIT/DEL REPLY

    대단한 문제는 아니지만 f(x) -> F(k) 로 변환하는 것은 e^ixk 가 아니라 e^-ixk 가 되어야 합니다. :) 또한 continuous time 에서의 fourier transform 은 적분 범위가 -무한대 ~ 무한대 까지입니다.

    그리고 대게 1차원에선 time domain -> frequency domain 을 의미하므로 t 와 f (혹은 2*pi*f 를 의미하는 w) 를 사용하는데 변수를 좀 특이하게 사용하시네요. 2차원에서는 흔히 x,y -> u,v 로 표현을 하기도 하지만 하여튼 약간 믹스네요.

    • snowall 2007.10.26 10:34 신고 EDIT/DEL

      지적해주신 부분 감사합니다. 대충 쓴건데 의외로 꼼꼼하게 보시는 분들이 많으시네요. :)
      1. +와 -틀린건 고쳐야겠네요
      2. 적분 범위는 "푸리에 변환"이라면 말씀하신대로 -무한대부터 +무한대까지 하는 것이 맞지만, 제가 저 글을 쓸 때는 "푸리에 급수"를 생각하면서 썼기 때문에 적분 구간이 유한한 구간으로 나온 겁니다. 설명을 수정해서 좀 더 올바른 표현이 되도록 생각해 봐야겠네요.
      3. 변수 기호는, 물리학과에서는 위치와 운동량에 관한 변환을 하는지라 p(또는 k)와 x를 씁니다. -_-; 전공 특징이예요...

  • jmK 2008.07.22 19:01 ADDR EDIT/DEL REPLY

    #5는 언제 나오나요?

    • snowall 2008.07.22 19:07 신고 EDIT/DEL

      음...
      일단 시간이 좀 생긴 다음에요.
      최근 4개월간 하도 야근을 많이 해서 공부를 못했습니다 -_-;;