# 10 Fast Fourier Transform (1)

1. Cooley-Tukey 분할 방식(Decomposition)

Cooley-Tukey 분할 방식(Decomposition)을 사용한 FFT(Fast Fourier Transform) 알고리즘은 이산 푸리에 변환(DFT)의 연산량을 획기적으로 줄이는 방법이다.

1.1. Divide-and-Conquer 방식

• n과 k를 P와 Q에 대한 식으로 정리하여 분할

• Q-point DFT

• twiddle factors

• P-point DFT

• Cooley-Tukey docomposition procdeure

• Q-point matrix

• twiddle factor matrix

• P-point matrix

 

1.2. 재귀적 분해

재귀적 분해로 인해 FFT의 시간 복잡도가 얼마나 주는지 확인해보자.

• 기존 DFT의 연산량과 Dooley-Tukey Decomposition의 차이
• 예제도 보면서 M(2)=0인 걸 기억