고속 푸리에 변환

5. 고속 푸리에 변환 (FFT: Fast Fourier Transform)
    1965년 Cooley와 Tuley에 의해 이산 푸리에 변환(DFT)을 효과적으로 계산할 수
    있는 알고리듬이 개발되었으며 DFT 계산시의 반복계산을 제거하여 고속으로
    계산할 수 있다.

    표. 필요한 복소수 연산 회수 비교

데이터 수  ()	DFT		FFT
	곱셈 ()	덧셈 ()	곱셈 ()	덧셈 ()
32   (r=5)	1,024	992	80	160
64   (6)	4,096	4,032	192	384
128   (7)	16,384	16,256	448	896
256   (8)	65,536	65,280	1,024	2,048
512   (9)	262,144	261,632	2,304	4,608
1024  (10)	1,048,576	1,047,552	5,120	10,240
2048  (11)	4,194,304	4,192,256	11,264	22,528

 

5.1 시간 솎음 알고리듬

     - x(n)의 N-pt(point) DFT를 구할 때, x(n)을 n이 홀수일 때와 짝수일 때의
        2개의 부펄스열(subsequence)로 나누고, 각각에 대해 N/2-pt DFT를
        구하는 방법을 decimation-in-time DFT라고 한다.

     - N/2-pt DFT는 또 다시 계속 분해하여 2-pt DFT가 될 때까지 분해한다.
        이 때 2-pt  DFT를 butterfly 연산이라 한다.

DFT	FFT (시간 솎음 알고리듬 사용)
, N은 2의 배수

Decimation-in-time FFT algorithm

       
           

           

       
       

       
       

       다시 로 놓으면

       
       
       
       

       
       

예 1: 4-pt decimation-in-time FFT의 계산

Input sequence: x(n)={x(0) x(1) x(2) x(3) }
DFT:

DFT 계산시의 문제점은 많은 양의 twiddle factor를 계산하는 것이다.
twiddle factor는 주기함수 이므로 실제로는 모든 twiddle factor를 다 계산할 필요가 없다.

x(n)에서 짝수시간(n=0,2)과 홀수시간(n=1,3)의 시퀀스를 나누어
시간 솎음 알고리듬을 적용하면,

       
           
       
       

       
     

       
               

       
       
       
       

         
               

       
       
       
       

       
   

 
 
       
       

해석: 4-pt DFT는 2개의 2-pt DFT로 분해 되었으며, twiddle factor는
        1개()만 구하면 된다.
        이것을 신호 흐름 선도로 표시하면 다음 그림과 같다.

예 2: 8-pt decimation-in-time FFT의 계산
DFT:




 
 
 
 

x(n)에서 짝수시간(n=0,2,4,...)과 홀수시간(n=1,3,5...)의 시퀀스를 나누어
시간 솎음 알고리듬을 적용하면,

       
           
       
       

       
     
     
     
       
               

       
       
       
       
       
       
       
       

         
               

       
       
       
       
       
       
       
       

     
       

       다시 로 놓으면
       
       
       
       

       
       

       
       
       

       
       
       

       
       
       
       

5.2 주파수 솎음 알고리듬

     - x(n)의 N-pt(point) DFT를 구할 때, X(k)를 k가 홀수일 때와 짝수일 때의
        2가지 경우로 나누어 결국 N/2-pt DFT로 분할하여 구하는 방법을
        decimation-in-frequency DFT라고 한다.

     - N/2-pt DFT는 또 다시 계속 분해하여 2-pt DFT가 될 때까지 분해한다.
        이 때 2-pt  DFT를 butterfly 연산이라 한다.

DFT	FFT (주파수 솎음 알고리듬 사용)
, N은 2의 배수

Decimation-in-frequency FFT algorithm ,  
       
       

 
 
          ,
          ,   로 놓으면
 
  가 되어

각각은 N/2-pt DFT로 간략화 된다. 이를 계속 분해하여 2-pt DFT가 되게 하면
butterfly 연산만으로 DFT를 구할 수 있게 되어 고속 계산이 가능해 진다. 

[출처] 5. 고속 푸리에 변환 (FFT: Fast Fourier Transform) |작성자 빛