FFT Algorithm, Cooley-Tukey Algorithm

 푸리에 변환은 다양한 곳에서 응용된다. 컴퓨터는 푸리에 변환 중 주기를 가진 이산 신호에 대해서만 푸리에 변환을 수행할 수 있다. DFT(Discrete Time Fourier Transform)는 다음과 같이 정의될 수 있을 것이다.

 

정의에 따라 푸리에 변환을 구하게 되면 O(N^2)의 시간이 걸리게 된다. 즉 신호의 주기가 길어질 수록 푸리에 변환을 얻기 위해 걸리는 시간은 주기 제곱에 비례하여 증가하게 되고, 이는 빨리 문제를 해결하고자 하는 우리 입장에서 바람직한 현상은 아니다. 

 

 FFT Algorithm은 주기에 따라 제곱에 비례하여 증가하는 현상을 O(NlogN)까지 개선할 수 있다. FFT의 기본적인 컨셉은 분할과 정복(Divide and Conquer)이다. 분할과 정복에 대해서 간단히 설명하자면 커다란 문제를 같은 단위의 작은 문제들로 나누고 이들을 해결하고 결합함으로써 큰 문제를 해결하겠다는 것이다. 작은 문제들을 해결할 때 중복되는 부분들이 많은 데 이 것들을 줄임으로써 전체 문제를 해결하는 데 필요한 연산량을 획기적으로 줄일 수 있다. 

 FFT를 이해하는 데 있어서 우선 회전자(Twiddle factor)의 성질에 대해서 이해할 필요가 있다. 회전자는 원래의 좌표계를 다른 좌표계로 사상하는 역할을 해준다. 여기서는 시간에 대한 값들을 주파수에 대한 좌표계로 사상해주기 위해 회전자를 사용한다. 회전자를 사용하여 다음과 같이 푸리에 변환을 정의할 수 있다.

 

 

회전자의 성질은 주기성으로 부터 온다. 회전자는 다음과 같은 성질을 가지고 있다.

 

 

이제부터 본격적으로 FFT Algorithm에 대해 설명해보고자 한다. FFT 종류는 다양하지만 이 글에서는 Cooley-Tukey Algorithm을 설명하고자 한다. 가장 기본적인 FFT 알고리즘이기도 하고, 보통 교과서 등에 수록되어 있는 방법이기도 하다.

 일단은 들어가기에 앞서서 우리는 편의를 위해 FFT를 실행할 신호의 주기가 짝수라 할 것이다. 그 후 짝수 번째의 값들과 홀수 번째의  값들을 묶어줄 것이다. 그러면 다음과 같이 표현할 수 있다.

 

주기를 짝수로 가정했기에 두 묶음은 서로 길이가 같다. 두번 째 괄호항에 대해서 다음과 같이 묶어줄 것이다.

 

 

이를 다시 써보겠다.

 

앞서서 다루었던 회전자의 성질(3c)에 의해 다시 한 번 식을 정리할 수 있다.

 

 

결과적으로 주기가 N인 신호의 푸리에 변환값은 절반의 주기를 가진 두 신호의 푸리에 변환값의 합으로 나타낼 수 있다. 여기서 FFT가 일반적인 정의를 사용하여 푸리에 변환값을 구하는 것보다 훨씬 적은 연산량이 드는 지 알 수 있다. 푸리에 변환에서 연산의 가장 큰 부분을 차지하는 것은 바로 회전자 자체의 값(거듭제곱)을 구하는 것이다. 그런데 분할한 형태를 보면 첫 번째 묶을 구하기 위해 필요한 회전자의  값들과 두번 째 묶음을 구하기 위해 필요한 회전자의 값들이 동일함을 알 수 있다. 결과적으로 원래의 형태에서 푸리에 변환값을 구하기 위해서 n=0 에서 n=N-1까지의 회전자 값들이 필요한 반면 분할을 한 번 거친 후에서는 n=0 에서 n=N/2-1까지의 회전자 값들이 필요하다. 분할이 한 단계 이루어짐에 따라 필요한 연산량이 절반으로 떨어지는 것을 알 수 있다.

f(k)에 대해서 값을 구할 수 있다면 이를 응용하여 f(k+N/2)를 구할 수 있다. 우리는 회전자의 성질 중 3a, 3b를 이용하여 다음과 같이 식을 유도할 것이다.

 

 

다음과 같이 정리할 수 있다.

 

 

위의 식을 그림으로 표현하면 나비와 같다고 해서 나비(Butterfly)라 하고, 분할 과정을 나비 연산(Butterfly Operation)이라 부른다. 

 Cooley-Tukey Algorithm에 대해 정리하여 보겠다. 푸리에 알고리즘에 있어서 주요한 연산은 각 항들에 대해 회전자와의 곱을 구하는 것과 회전자 자체를 구하는 것이다. 분할을 거침에 따라서 필요한 회전자의 수는 절반씩 줄어듦으로 주기가 N인 신호에 대해 대략 연산자를 구하기 위해 필요한 연산량은 O(logN)이다. 회전자와 항을 곱하는 횟수 역시 O(N)에서 O(N/2)로 줄어들게 된다. 결과적으로 이 알고리즘의 연산량은 O(N/2*logN)으로 표현할 수 있다. 

Cooley-Tukey Algorithm의 진가는 주기가 2의 거듭제곱 꼴일때 발휘된다. 분할이 계속 진행되다보면 최종적으로 길이가 2인 묶음이 남게 되고, 이를 구하는 과정은 매우 간단하기 때문이다. 여기서 끝이 아니다. 처음 원래의 신호와 최종적으로 나누어진 신호의 순서를 이진수로 나타내면 그림에서와 같이 대응하는 신호의 모든 비트들을 거꾸로 배열한 것과 같다. 이러한 현상을 Bit-reversal이라 한다. 신호의 주기가 2의 거듭제곱 꼴이기만 하면 Bit-reversal 현상은 나타나게 된다. 또한 계산구조가 in-place 조건(초기 입력값이 저장되어 있는 곳에 결과값이 저장되어야 한다는 조건)이 아니라면 입력자료와 출력 결과 둘 다 순서대로 나열되도록 하는 것이 가능하며, 이를 out-of-place라 한다.

 이 것으로 FFT에 대한 알고리즘에 대한 글을 마무리한다.

 

이 글의 출처  https://ko.wikipedia.org/wiki/%EA%B3%A0%EC%86%8D_%ED%91%B8%EB%A6%AC%EC%97%90_%EB%B3%80%ED%99%98

고속 푸리에 변환 - 위키백과, 우리 모두의 백과사전