글
*실제 계산에서는 적분이나 지수함수에 $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으로 줄일 수 있다.
*이 글의 댓글을 참고하여 논리적/수학적인 오류가 내포되어 있을 수 있음을 경고해 두는 바이다. 전체적인 맥락의 이해에서는 맞지만, 여기 나온 공식들을 그대로 적용하려고 할 때는 문제가 발생할 수 있으므로 다른 좋은 책들을 참고할 것을 강력히 권장한다.
원래는 푸리에 변환의 실제 계산들을 해보려고 했으나, 사실 푸리에 변환을 계산한다는 것이 $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으로 줄일 수 있다.
RECENT COMMENT