Fast Fourier Transform ( FFT, 푸리에 변환 )

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\phi$ , $e^{-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라 한다.

FFTW (0)	2011.06.04
Interpolated second order polynomials ( ISOP ) filter (0)	2010.02.19
Noble identities ( the six identities ) (0)	2010.02.08
Up-sampling(업샘플링) 과 Interpolation(보간)의 비교 (0)	2010.02.06
Down-sampling( 다운샘플링 ) 과 Decimation( 데시메이션 ) 비교 (1)	2010.02.06

Posted by bayron

즐거운 세상