posted by bluelimn 2008.05.02 16:16

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를 구할 수 있게 되어 고속 계산이 가능해 진다.