[디지털 신호 처리] 고속 푸리에 변환 FFT, DTF와의 관계

고속 푸리에 변환(FFT) : 이산 푸리에 변환을 효율적으로 계산하기 위한 알고리즘

주어진 N개의 복소수 입력값에 대해 입력 신호를 N개의 동일한 길이의 부분 신호로 분할한 다음, 

각 부분 신호에 대해 DFT를 계산하고 부분 신호의 길이가 1이 될 때까지 이 과정을 반복한다.

이후 결과적으로 나온 DFT를 계산하고 부분 신호의 길이가 1이 될 때까지 이 과정을 반복한다.

이후 결과적으로 나온 DFT값을 결합하여 전체 FFT값을 얻을 수 있다.

FFT는 신호처리, 영상 등 다양한 분야에서 사용되며 고속 연산의 속도와 효율성이 좋은 것이 특징이다.

FFT와 DFT 모두 주파수 영역으로의 신호 변환에 사용되는 것은 동일하다.

 

[복소수 계산 횟수, 계산 복잡도]

DFT → O(N^2) : 길이 N이 커질 때는 계산량이 급격히 증가

FFT → O(N*logN) : 대규모 데이터에 대한 푸리에 변환을 실용적인 시간 안에 수행 가능.

▶ FFT의 주요 장점은 복소수 계산 횟수가 적어 연산 시간이 훨씬 짧고

입력 크기에 대해 로그 선형 시간 내에 계산을 수행할 수 있어 대규모 데이터에 더욱 효율적이다.