The Fourier Transform

출처 : http://plaza.snu.ac.kr/~swsyoon1/research/fft/fft.php The Fourier Transform
	Fourier Transform 은 어떤 주기적인 시간 함수( x(t) )도 주파수 0 부터 시작하여 base frequency (fo = 1/T)의 정수배에 해당하는 주파수로 이루어진 sin 과 cos 함수의 무한합과 같다는 개념에서 부터 출발한다. (where T is the period of x(t) ) 주기적인 시간함수의 fourier series 는 다음과 같은 형태로 나타난다.
	이 식을 수학적 계산을 통하여 다음과 같이 간단히 나타낼 수 있다.(응용수학이나 수치해석 책을 참고 할것)
	위와 같은 fourier series는 주기적인 시간함수의 주파수 정보는 얻을수 있지만, 모든 신호가 주기적이지만은 않다는 것이다. 따라서 주기적이지 않은 신호에서 주파수 정보를 얻기위해 사람들은 fourier series 를 응용하기 시작했다. 그래서 나온 것이 Fourier integral 이다. 주기적인 함수를 비주기적인 함수로 변환하는 방법으로 주기를 무한대(infinite)로 보낸다는 것이다. 즉 T 가 무한대가 되면 그 함수는 반복적인 형태가 나올수가 없다는 것이다. 따라서 비주기적인 함수가 되는것이다. 이를 이용하면 fourier series는 다음과 같이 표현 된다.
	이는 각각 Fourier Transform pair 라고 하고, 위 식은 Inverse Fourier Transform 이고 아래식은 Fourier Transform or Fourier Intergral 이라고 한다. 따라서 Fourier series 와 Fourier Transform과의 차이점을 정리하면  적용하는 함수 형태가 다르다는 것이다. Fourier series 는 주기적인 함수에 Fourier Transform 은 비 주기적인 함수에 적용하는 것이다. 그래서 Fourier series 는 연속(continuous) , 주기적인 시간함수 (periodic time-domain function)을 discrete frequency 에의 주파수 함수로 변환하고 Fourier Transform 은 연속적인 시간함수를 연속 주파수 함수로 변환한다. 다음 그림은 이 둘의 성격을 잘 나타내준다.
	DFT (Discrete Fourier Transform)
연속함수에서는 Fourier transform을 하면 되지만 discrete 에서는 DFT를 행한다.  waveform 이 interval T 로 sampled 되었다고  하면 , sample sequence 는 x(nT) = x(0) , x(1), x(2) , x(3) , x(4) , x(5) . . . . x[(N-1)T] 라 할수 있다. (n = 0 . . . . . N-1 ) 그래서 x(nT)의 DFT 는 frequency domain에서 X(k) = X(0) ,X(). . . X[(N-1)] 같은 복소수 값의 sequence를 갖는다. DFT는 다음식과 같다. ( k = harmonic number of transform component )
( k = harmonic number of transform component )
그리고 중요한 DFT의 성질이 있는데 k번째의 요소와 k+N 번째 요소를 비교하면
따라서 위 식은 DFT 는 주기 N에 대하여 periodic 하게 나타난다는 것이다.

FFT는 DFT에 비해 의 complex 곱 계산량을 번으로 낮출수가 있고 따라서 계산 속도도 훨씬 빠르다. FFT 알고리즘은 radix-2 DIT(Decimation in Time) FFT , DIF(Decimation in frequency) FFT 등이 있는데 우선 DIT FFT를 살펴보자. DFT의 식은 다음과 같다.
	여기서   이라고 하면 로 쓸 수 있다. 여기서 몇가지 식을 유도하자. 이 관계식을 DFT 식에 적용하여 even -numbered sequence 와 odd-numbered sequence 로 나눌 수 있다. 또    이므로 다음 식과 같아진다. 이 식을 살펴보면 우측항은 N/2 point DFT (even-number , odd-number)로 이루어져 있는 걸 볼수 있다. 식을 간단히 표현하면 따라서  를 위와 같은 방법으로 다시 나누면이다. 도 마찬가지 방법으로 하면 ,위와 같이 모두 N/4 point DFT 로 나눌 수가 있다.이와 같이 N개의 point를 FFT를 하려면 로 정하고 ,각 계산 단계를 개로 나눌 수 있다.
	따라서 한가지 주의 할것이 있다면 radix-2 FFT를 사용하기 위해선 2^N 개의 point를 사용 해야 한다는 것이다. 위와 같은 계산을 Butterfly computation 이라고 하고 이를 도식화 나타내면 다음 그림과 같다 . 8개의 point를 사용했을 경우를 나타낸다.
하나의 butterfly 계산 방법을 살펴보면 , 다음과 같은 경우                                                 이 된다. 따라서 총 계산량은 그리고 각 단계 마다의 butterfly 개수를 곱한 것이 된다. 예를 들어 8-point 의 경우 r=3 , butterfly 개수 = 4개 , 그래서 12 번이 된다. DIF FFT의 경우는 모양은 비슷하나 butterfly 계산방법이 DIT FFT와는 좀 다르다. 컴퓨터로 많은 point의 FFT를 계산하기 위해서는 위와 같은 알고리즘을 적절한 language 로 coding 하여 사용하면 될 것이다.
	자료실에 FFT  C souce 와  MATLAB m file로 작성한 souce가 있습니다.

invalid-file

invalid-file

invalid-file