백과

표준화된 복소수 값 신호를
x_j ( j = 1, 2, ···, N-1)
라 하고 { x_j }에 대하여

로 정의되는 복소수 값의 조·{ A_k }를 구하는 조작을 이산적(離散的)인 푸리에 변환이라 한다. { A_k }를 윗식으로구하면 N²회의 곱셈 및 덧셈이 필요하다.

N = r₁·r₂ ··· r_m
으로 인수 분해될 때에는 곱셈 및 덧셈의 회수가

(r₁ + r₂ + ··· + r_m)N으로 끝나는 셈법이 알려져 있는데 이것을 FFT라고 한다. 특히 N = 2^m일 경우 필요한 복소수 곱셈의 회수는 이 된다.