고속푸리에변환

요약 함수의 근사값을 계산하는 알고리즘이다. 푸리에변환에 근거하여 근사공식을 이용한 이산푸리에변환(discrete Fourier transform)을 계산할 때 연산횟수를 줄일 수 있도록 고안되었다.

푸리에변환에 근거하여 근사공식을 이용한 이산푸리에변환(discrete Fourier transform)을 계산할 때 연산횟수를 줄일 수 있도록 고안된 알고리즘이다. 고속푸리에변환은 1960년대 중반 J.W.콜리와 J.W.터키에 의해 일반적으로 알려지게 되었는데, 그보다 20년쯤 전부터 몇몇 사람들에 의해 독립적으로 발견되어 사용되어 왔다. h^m(0≤m≤N－1)이 복소수들의 집합일 때, 수열 {h^m}의 이산푸리에변환은 다음과 같다.





연속푸리에변환에서와 마찬가지 방법으로 이산변환도 다음과 같이 역변환을 구할 수 있다.





hⁿ은 역푸리에변환계수라 불린다. 고속푸리에변환의 알고리즘은 ①의 계산을 할 때 직적분해(direct product decomposition)를 이용하여 단계를 나누어 수행할 수 있다는 사실에 근거한다. N＝N₁N₂, N₁과 N₂가 서로 소일 때, 2차원의 푸리에변환계수를 예로 들어보자.







한 번의 복소곱셈과 복소덧셈을 하나의 기본연산으로 한다면, 호너의 방법(Horner’s method)을 사용했을 때는 N², 즉 (N₁N₂)²의 연산이 필요하나, 직적분해방법을 사용하면 N₁N₂(N₁＋N₂)의 연산으로H_n1,n2를 계산할 수 있다. 위 변환에 대응하는 행렬은 N₁×N₁과 N₂×N₂행렬의 직적(direct product)이므로, 다음 두 단계로 나누어 계산을 수행한다. 첫 단계로, 0≤m₁≤N₁－1과 0≤n₂≤N₂－1에 대하여



를 계산하고, 다음에 0≤n₁≤N₁－1과 0≤n₂≤N₂－1에 대하여



를 계산한다.