07. FFT (Fast Fourier Transform, 고속 푸리에 변환)

앞에서 살펴봤던 DFT의 수식을 그대로 이용해서, 실제 신호에 대한 푸리에 변환을 하기에는 무리가 있다. 계산량이 너무 많기 때문이다.

 

$$ DFT: \; \; Y(k)=\sum_{n=0}^{N-1}{y(n)e^{-i\frac{2\pi}{N}kn}}, \; \; 0\leq k < N \tag {1} $$

 

식(1)의 DFT 수식에 따르면 실수와 복소수와의 곱 연산을 $N^2$회 수행하고, 덧셈 연산은 N(N-1)회 이루어진다. 

 

$N=4096$ 으로 하면, 신호 한 블록에 대해 16,777,216번의 연산이 필요하고, 이러한 연산을 1초 안에 수행하기에는 고속의 CPU를 사용해도 무리가 따른다. (펜티엄 2.2 GHz의 경우, 일반 실수에 대한 곱 연산을 초당 $8 \times 10^7$개 정도 수행할 수 있다 한다.  실수가 아닌 복소수와의 곱이고, 덧셈 연산도 부가되고 하면, CPU의 모든 파워를 사용해도 4096 DFT를 1초 내에 수행하지 못할 것이다.)

 

더군다나 일반 산업용 기기나 임베디드 시스템의 경우 CPU 속도가 더 느리기에, DFT를 그대로 사용할 수 없다.

 

---

DFT의 계산 속도는 $O(N^2)$이다. N이 작을 때는 큰 문제 안되나, $N=1024$ 정도만 돼도 문제가 발생한다. 

FFT(Fast Fourier Transform, 고속 푸리에 변환)는 $O(N\log{N})$ 시간에 DFT와 동일한 계산이 이루어지도록하는 알고리즘이다. $O(N\log{N})$ 이면 $N=8192$여도 감내할만한 계산량이겠다.

 

N 크기에 따른 계산량

N을 크게 하는 것은 주파수 해상도(=주파수 분해능)와 관련이 있다. 

음성신호의 경우 일반적으로 44.1kHz로 샘플링한다. 이 경우 한 $N=1024$이면 주파수 해상도는 43Hz이다. ($\frac{44100Hz}{1024}=43Hz)$

$N=4096$으로 증가시키면 주파수 해상도는 10.7Hz가 된다. 따라서, N을 증가시킬수록 세밀한 주파수 분석이 가능하다.

---

FFT를 실현하는 몇 개의 알고리즘이 있는데, 분할 정복(Divide and Conquer)을 사용하여 $O(N\log{N})$시간에 DFT 계산이 가능하도록 하는 "쿨리-튜키 알고리즘(Cooley Tukey algorithm)"이 가장 잘 알려져 있다. 

 

먼저 쿨리-튜키 알고리즘에 의한 FFT 원리를 알아보고, 엑셀 및 C에서 구현하고 활용하는 것을 알아보겠다.

 

• 07-1. FFT의 유도
• 07-2. 손으로 FFT 따라해보기
• 07-3. FFT의 구현 (엑셀 VBA)
• 07-4. FFT의 구현 (C, C++)

 

 

-끝-

이전글: 06-8. DFT 수식에 대한 해석 --> 작성중

다음글: 07-1. FFT의 유도

다음다음글: 07-2. FFT 예제를 손으로 풀어보며 이해하기