DSP) 고속 푸리에변환 (FFT) (2/2)

이전 포스트 : https://99kh.tistory.com/25

DSP) 고속 푸리에변환 (FFT) (1/2)

 

 

2. At DIF

DIF(Decimation In Frequency)는 DIT와 비슷하며 다르다.

결론부터 얘기하자면 총 곱셈의 수는 DIT와 같이 log_2 (N) x N/2 이다. 알아보기 어려우니 사진으로 넣겠다.

DIF에서는 홀짝으로 반갈죽 했던 DIT와 다르게, 앞뒤로 반갈죽한다.

전체 크기 N에서 앞의 N1개와 뒤의 N1개로 나눈다. 

 

N = 2 x N1 이라고 가정할 때, 위와같이 반갈죽할 수 있고 아래 처럼 하나의 sigma로 묶을 수 있다.

이에, k가 even일 때와, odd일 때로 나뉘며, 식은 아래와 같다.

결론은, 상술했듯이 DIT와 DIF방식 모두 같은 곱셈수를 가진다.

 

아래는 DIT와 동일하게, 8-point DFT를 DIF방식으로 진행한 결과다.

 

 

 

여담으로, 역 DFT는 아래와 같다.