백과

N절의 이산 푸리에 변환의 계산은 N²회의 복소곱셈을 필요로 하는데, 이 계산량을 줄일 필요에서 발견된 복소곱셈횟수가 적은 고속의 변환, 전형적인 예로서 쿨리-류키의 알고리즘, 위노그라드의 고속 푸리에 변환, 혼합기수 변환이 있다. 이들 알고리즘에서의 곱셈회수 줄이기는, 긴 신호계열의 이산 푸리에 변환을 보다 짧은 신호계열의 이산 푸리에 변환으로 축차분해하는 것 및 회전인자(버터플라이 연산 참고)의 대칭성과 주기성을 이용하는 것으로써 이루어진다.

고속 푸리에 변환은 그 계산량이 적다는 데서, 이산시간신호 주파수영역해석, 주파수영역에서의 합성곱계산, 상관함수의 계산, 수치해석 등의 고속계산을 위해서 쓰인다. 고속 푸리에 변환의 알고리즘은, 쿨리(Cooly, J. W.)와 튜키(Tukey, J. W.)에 의하여 1965년에 발견되었다. 이 발견이 변환영역에서의 이산시간신호의 처리를 실행가능하게 했으며, 또 다른 고속의 알고리즘을 발견하는 계기가 되어, 디지털 신호처리의 발전을 크게 촉진하였다. 현재, 신호처리 프로세서라든가 전용 하드웨어에 의하여 실현되었으며, 디지털 신호처리의 광범한 영역에서 사용되고 있다(디지털 신호처리 프로세서 참고). 〈참조어〉 신호처리