FFT (Fast Fourier Transform) : 고속 푸리에 변환

FFT는 이산 데이터 값들의 푸리에 변환 계산을 위한 알고리즘이다. FFT는 주어진 유한 데이터 점들의 세트, 즉 예를 들어 실세계 신호로부터 주기적으로 얻어지는 견본들을, 그 요소 주파수들의 형태로 표현한다. 이것은 또한 정확하게 반대인 주파수 데이터로부터 신호를 재구성하는 문제도 해결한다.

FFT는 수치해석의 가장 중요한 알고리즘이다. Gilbert Strang은 FFT를 가리켜, "우리 세대의 가장 중요한 알고리즘"이라고 말했다. FFT는 또한 두 개의 다항식을 곱하는데 있어 점근적으로 가장 빠르다고 알려진 알고리즘을 제공한다. C나 포트란으로 작성된 알고리즘 버전들을 온라인상에서 찾아볼 수 있다.

여기까지 출처 : 텀즈

  DFT는 시간 영역과 주파수 영역에서 모두 이산적 성질을 갖는 유일한 변환이고, 유한구간 신호에 대해서 정의된다. 비록 그것이 계산 가능한 변환이기는 하지만 식 (5.24)의 직접적인 계산은 매우 비효율적이고, 특히 신호의 길이 N이 클 때는 더욱 비효율적이다. 1965년에 Cooley와 Tukey [4] 는 DFT 연산 중에 수행할 계산의 양을 실질적으로 줄이는 과정을 보여주었다. 이로 인하여 디지털 신호 처리 분야를 포함한 여러 분야에서 DFT를 많이 사용하게 되었다. 게다가 다른 효율적인 알고리즘이 개발되는 계기가 되었다. 이러한 모든 효율적인 알고리즘들은 총체적으로 고속 푸리에 변환(fast Fourier transformation, FFT) 알고리즘으로 알려지게 되었다.

N=6-점 신호 x(n)을 생각해 보자. 식 (5.24)에 따르면 이 신호의 DFT는 다음과 같다.

 

여기서 이다. X(k)중에서 하나의 샘플을 얻으려면, N=6번의 복소수 곱셈과 (N=6-1)번의 복소수 덧셈이 필요하다. 그러므로 모든 DFT 계수의 집합을 얻으려면, N²번의 복소수 곱셈과 의 복소수 덧셈이 필요한 것이다. 또한 N²개의 복소수 계수들 를 저장해야만 한다. 즉, 내부적으로 추가적인 비용이 발생한다. 명백히 N=6-점 신호에 필요한 DFT 계산의 수는 N의 제곱에 비례하고, 다음과 같이 표시된다.

  

N이 큰 경우에 o(N²)은 실제적으로 사용할 수 없다. 일반적으로 덧셈의 처리 시간은 곱셈의 처리시간보다 훨씬 적다. 그러므로 지금부터는 그것 자체만으로 4번의 실수 곱셈과 2번의 실수 덧셈이 필요한 복소수 곱셈의 수에 초점을 맞출 것이다.

 

효율적 계산의 목표

효율적으로 설계된 알고리즘은 자료 샘플마다 계산의 수가 일정해야 하고, 총 계산의 수는 N에 대해 선형적으로 증가해야 한다.

N²에 비례하는 계산은, 계속해서 수행되는 대부분의 계산을 의 주기성

  

과 대칭성

 

  

을 이용하여 줄일 수 있다.

먼저 계산의 수를 줄이는데 있어서 대칭성과 주기성의 이점을 보여주는 예제로 시작해 보자. 그리고 나서의 계산을 필요로 하는 두 개의 특정한 FFT 알고리즘(시간 데시메이션 FFT 알고리즘과 주파수 데시메이션 FFT 알고리즘)을 분석해 보자.

□ 예제 5.19 4점 DFT의 계산 방법에 대해 알아보고, 이 계산을 위한 효율적인 알고리즘을 만들어 보아라.

  

   

위 식은 행렬 형태로 계산할 수 있다.

  

이것은 16번의 복소수 곱셈이 필요하다.

효율적 방법 : 주기성을 사용하면,

  

위의 행렬 형태를 바꾸면 다음과 같다.

  

대칭성을 이용하면 다음의 식을 얻을 수 있다.

  

   

따라서 효율적인 알고리즘은 다음과 같아진다.

 

  

이것은 단지 2번의 복소수 곱셈만이 필요하다. 이렇게 간단한 예제에서도 계산의 수가 상당히 줄어든 것이다. 이 알고리즘의 신호 흐름도 구조는 그림 5.18과 같다.

그림 5.18 예제 5.20의 신호 흐름도

 

해석 : 식 (5.57)의 효율적인 알고리즘은 다르게 해석될 수 있다. 첫째로, 4점 신호 x(n)은 2개의 2점 신호로 나누어지고, 아래와 같이 열 벡터로 정리가 된다.

  

둘째로, 각 열에 대해 더 작은 2점 DFT가 행해진다.

  

그리고 나서, 결과 행렬의 각 성분에 

를 곱한다. 여기서 p는 행의 인덱스이고, q는 열의 인덱스이다. 즉 다음과 같은 점곱셈(성분끼리의 곱셈)이 수행된다.

  

마지막으로 행벡터에 대해 두 개의 더 작은 2점 DFT 연산이 수행된다.

  

비록 이 해석이 효율적인 알고리즘보다 더 많은 곱셈을 하는 것처럼 보이기는 하지만, 큰 DFT 연산을 더 작은 DFT 연산들로 계산하는 체계적인 접근 방법을 제시해 준다.                       ■

 

분할-조합 방법(divide-and-combine approach)

N²에 비례하는 DFT 계산을 줄이기 위해서 합성수인 을 선택해야 하는데, 그 이유는 다음과 같다.

  

이제 그 신호를 길이가 L인 M개의 작은 신호로 분할하고, M번의 작은 L점 DFT 연산을 수행한다. 그리고 나서 L번의 작은 M점 DFT 연산을 통해 더 큰 DFT로 조합한다. 이것이 분할-조합 방법의 핵심이다. N=LM이라 하면 식 (5.46)의 인덱스 n과 k는 다음과 같이 쓸 수 있다.

  

그리고 신호 x(n)과 X(k)를 각각 배열 x(l,m)과 X(p,q)로 나타낸다. 그러면 식 (5.46)을 다음과 같이 쓸 수 있다.

각각의 열 m=0,...M-1에 대해 L점 DFT 배열

  

를 계산한다.

2. 다른 배열을 얻기 F(p,m)위하여 을 바꾼다.

  

인수 은 회전 인수(twiddle factor)라고 불린다.

3. 각각의 행 p=0,...L-1에 대해 M점 DFT를 계산한다.

  

이러한 방법에 대한 복소수 곱셈의 총 수는 다음과 같이 주어진다.

  

만약 M 또는 L이 합성수라면 이 과정이 반복될 것이다. 명백히, N이 고차의 합성수, 즉 일 때 가장 효율적인 알고리즘이 얻어진다. 그러한 알고리즘은 R 진수 알고리즘이라 불린다. 만약 라면, 그러한 분해는 혼합 진수(mixed radix) FFT 알고리즘이라 불린다. 가장 인기있고 쉽게 사용할 수 있는 알고리즘은 2진 FFT 알고리즘이다.

 

2진 FFT 알고리즘(radix-2 FFT algorithm)

라고 하자. 그리고 나서 , M=2, L=n/2라하고, 식 (5.48)에 따라 x(n)을 두 개의 N/2점 신호로 분할하면

  

이 된다. 신호 은 x(n)의 짝수번 샘플을 가지고 있고, 신호 

은 x(n)의 홀수번 샘플을 가지고 있다. 와 를 각각 

과 의 N/2점 DFT라고 하자. 그러면 식 (5.59)는 다음과 같이 줄어든다.

  

이것을 병합 공식(merging formula)이라 하는데, 두 개의 N/2점 DFT를 하나의 N점 DFT로 조합하는 것이다. 복소수 곱셈의 총 수는 다음과 같이 줄어든다.

  

이 과정은 계속해서 반복될 수 있다. 각 단계에서 신호들은 데시메이션(decimation)되고, 더 작은 DFT들이 결합한다. 이 데시메이션(decimation)은 N개의 1-점 신호, 즉 1-점 DFT를 갖게되는 v단계 후에 끝난다. 이러한 과정을 시간 데시메이션 FFT(decimation-in-time FFT, DIT-FFT)라 한다. 복소수 곱셈의 총 수는 다음과 같다.

  

N이 클 경우 은 근사적으로 N에 선형이 된다. 이것이 효율적 알고리즘의 목적인 것이다. 추가적으로 대칭성을 사용하면 을 으로 줄일 수 있다. N=8인 경우의 이 알고리즘에 대한 신호 흐름도를 그림 5.19에 나타내었다.

그림 5.19 인 경우의 시간 데시메이션 FFT 구조

다른 방법으로 L=2, M=N/2이라 하고, 식 (5.59)에 있는 단계들을 따라가 보자. 초기의 DFT는 복소수 곱셈을 포함하지 않은 2점 DFT임을 명심하자. 식 (5.60)으로부터

  

그리고, 식 (5.61)로부터

  

0≤n≤N/2-1에 대해 , 

이라 하자(왜냐하면 그것들은 시간 영역에서의 신호로 생각할 수 있기 때문이다). 그러면 식 (5.62)로부터 다음 식을 얻게 된다.

이것은 DFT 값 X(k)를 데시메이션 방식으로 계산함을 의미한다. 그러므로 이러한 방법을 주파수 데시메이션 FFT(decimation-in-frequency FFT, DIF-FFT) 알고리즘이라 한다. 이것의 신호 흐름도는 DIT-FFT 구조를 전치시킨 형태이고, 계산의 복잡도는 과 같다.

 

고속 콘벌루션(fast convolution)

큰 값의 (>50)에 대해서는 FFT 알고리즘을 사용하여 콘벌루션을 빠르게 하는 것이 가능하다. 이러한 방법은 선형 콘벌루션을 구현하기 위해 순환 콘벌루션을 사용하고, 순환 콘벌루션을 구현하기 위해 FFT를 사용하는 것이다. 최종적인 알고리즘을 고속 콘벌루션 알고리즘(fast convolution algorithm)이라 한다. 만약  이어서 2진 FFT를 사용한다면, 그 알고리즘은 급속 콘벌루션(high-speed convolution)이라 한다. 을  N₁점 신호, 을  N₂점 신호라 하자. 그러면 급속 콘벌루션의 N은 다음과 같이 선택할 수 있다.

 

여기서 [x]은 x보다 큰 가장 작은 정수이다(또한 상한(ceiling) 함수라고도 불린다). 이제 선형 콘벌루션 *은 2개의 N점 FFT, 하나의 N점 IFFT, 그리고 하나의 N점 점곱셈을 통해 구현한다.

 

급속 블록 콘벌루션(block convolution)

앞에서 매우 큰 신호를 비교적 작은 신호로 나누어 콘벌루션을 수행하는 중첩-보류법(overlap and save method)과 중첩-가산법(overlap and add method)이라는 블록 콘벌루션에 대해서 논의했었다. 그 부분에서는 선형 콘벌루션을 구현하기 위해 DFT를 사용한다. 이제는 급속(high-speed) 중첩-보류법을 얻기 위하여 DFT를 2진 FFT 알고리즘으로 대체할 것이다. 한층 더 계산을 줄이기 위하여 더 짧은(고정된) 신호의 FFT는 단지 한번의 계산만으로 할 수 있다.