fft란 무엇인가요?
fft는 고속 푸리에 변환입니다.
고속 푸리에 변환(Fast Fourier Transform)은 컴퓨터를 사용하여 FFT라고 하는 이산 푸리에 변환(DFT)을 계산하는 효율적이고 빠른 계산 방법의 총칭입니다. 고속 푸리에 변환은 1965년 J.W. Cooley와 T.W. 이 알고리즘을 사용하면 컴퓨터가 이산 푸리에 변환을 계산하는 데 필요한 곱셈 횟수를 크게 줄일 수 있습니다.
특히, 변환되는 샘플링 포인트 N의 수가 많을수록 FFT 알고리즘의 계산 절감 효과는 더욱 커집니다. FFT의 기본 아이디어는 원래 N 포인트 시퀀스를 일련의 짧은 시퀀스로 분해하는 것입니다. DFT 계산식에서 지수 인자의 대칭성과 주기적 특성을 최대한 활용한 다음, 이러한 짧은 시퀀스의 해당 DFT를 찾아 적절하게 결합하여 반복 계산을 제거합니다.
곱셈 연산을 줄이고 구조를 단순화하려는 목적입니다. 이후 이 아이디어를 바탕으로 하이 베이시스, 분할 베이시스 등 빠른 알고리즘이 개발되었으며, 디지털 기술의 급속한 발전과 함께 1976년 정수론과 다항식 이론을 기반으로 한 위노글러 푸리에 변환 알고리즘(WFTA)이 등장했다. 소인수 푸리에 변환 알고리즘.
가장 일반적인 특징은 N이 소수인 경우 DFT 계산을 원형 컨볼루션으로 변환하여 곱셈 횟수를 더욱 줄이고 속도를 높일 수 있다는 것입니다.