Signal Processing2011. 6. 3. 22:53
 

 

 Fast Fourier Transform(FFT)는  통신, 신호처리 분야에서 매우 중요한 응용이다. 

 

H(f) = \int_{-\infty }^{\infty }h(t)e^{-j2\pi ft}dt

 

h(t) = \int_{-\infty}^{\infty}H(f)e^{j2\pi ft}df

 

 H(f)는 주파수 영역의 스펙트럼, h(t)는 시간에 따라 변하는 함수를 나타낸다. 위 수식은 연속함수이므로 샘플링된 값을 처리하기위해서는 아래와 같은 수식을 사용한다.

 

H(f_n)=t_\delta \sum_{k=0}^{N-1}h_k e^{\tfrac{-j2\pi kn}{N}}

 

h(t_k)=\tfrac{1}{N} \sum_{n=0}^{N-1}H_n e^{\tfrac{j2\pi kn}{N}

 

 위 수식에서 t_\delta는 샘플링한 시간간격을 나타내고, N은 샘플의 개수를 나타낸다.
FFT와 IFFT의 차이는 e의 지수 부호가 바뀐 것과 앞에 다른 상수가 곱해지는 것이므로 하나의 모듈로
두 기능을 모두 구현 할 수 있다.

 위 수식을 계산하려면 O(N^2)의 복소수 곱셈이 필요한다. 이 때, 샘플의 수를 2^a로 한정하고, e^{j\phi}=cos\phi + jsin\phie^{-j\phi}=cos\phi - jsin\phi 로 바꾸면 수식은 아래와 같이 변한다.

 

H(f_n)=\sum_{k=0}^{N-1}W_{N}^{nk}h_k=\sum_{j=0}^{\tfrac{N}{2}-1}W_{N}^{wjn}h_{2j}+\sum_{j=0}^{\tfrac{N}{2}-1}\w_{N}^{(2j+1)n}h_{wj+1}

 

=H_{n}^{e}+W_{N}^{n}H_{n}^{0}

 

h(t_k)=\sum_{n=0}^{N-1}W_{N}^{-nk}H_n=\sum_{n=0}^{\tfrac{N}{2}-1}W_{N}^{-2jk}H_{wj}+\sum_{n=0}^{\tfrac{N}{2}-1}W_{N}^{-(2j+1)k}H_{2j+1}

 

=h_{k}^{e}+W_{N}^{-k}h_{k}^{0}     ( 수식에서  W_{N}^{x}=e^{j2\pi\tfrac{x}{N}}이다.)

 

 위 수식은 N개 샘플에 대해 홀수 번째 샘플과 짝수 번째 샘플에 대해 각각을 푸리에 변환하여 상수를 곱하고 더하는 것으로 전체 푸리에 변화이 되는 것을 의미한다.
이것을 반복적으로 적용하면 결국 
N^2의 복소수 곱셈을 0(Nlog_2 N)으로 줄일 수 있다.

 이러한 방법을 통해 빠르게 계산하는 것을 FFT라 한다.

 



Posted by bayron