FFT란?

FFT Fast Fourier Transform

FFT는 기존의 DFT(Discrete Fourier Transform)의 연산량을 극복하려고 나온 변환입니다.

DFT 포스팅입니다 -> https://kkhipp.tistory.com/3

과거의 하드웨어로는 DFT의 연산량을 커버하기에는 무리가 있었습니다.

DFT는 의 연산량이 필요하지만 FFT는 의 연산량으로 더 적은 양이 필요합니다.

FFT는 결국 DFT의 계산 과정에서 대칭성과 주기성을 사용하여 연산량을 줄이는 변환입니다.

FFT에서 많이 사용되는 알고리즘은 Cooley-Tukey 알고리즘 입니다.

https://en.wikipedia.org/wiki/Butterfly_diagram

그리고 FFT Cooley-Tukey 알고리즘 과정을 그려보면 위와 같은 그림이 나오는데

나비 모양과 비슷하다고 하여 Butterfly model, Butterfly operation 등으로 부릅니다.