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

목차

Ⅰ.개요
Ⅱ.목적
Ⅲ.수식
Ⅳ.응용

본문내용

FFT(Fast Fourier Transform)
Ⅰ.개요
고속푸리에변환(Fast Fourier Transform: FFT)은 이산푸리에변환(DFT)을 고속으로 산출하기 위한 하나의 알고리즘으로써 1965년 Tukey와 Cooley에 의해 개발 되었다. 이러한 알고리듬의 개발에 의해 처음으로 컴퓨터에 의한 이산푸리에변환이 실용화되었다.
Ⅱ.목적
이산푸리에변환의 계산량을 감소시키기 위해 만들어진 알고리즘으로 이산푸리에변환 공식에서 반복계산을 제거함으로써 이산푸리에변환을 고속으로 산출하기 위한 하나의 알고리즘으로 볼 수 있다.
고속푸리에변환에는 시간솎음(시간영역 분해) 알고리듬과 주파수솎음(주파수영역 분해) 알고리듬으로 나눌 수 있다.
※ 계산량의 비교 : DFT를 구하기 위해 복소계산은 회의 곱셈과 회의 덧셈이 필요하지만 FFT를 이용하면 회의 곱셈과 회의 덧셈이면 된다. 특히 컴퓨터에 의한 계산에서는, 계산시간은 거의 곱셈의 회수에 좌우되므로 의 값이 크면 클수록 FFT는 위력을 더욱더 발휘 함
Ⅲ.수식
① DIT FFT - N-point DFT를 각각 짝/홀수번째의 항만으로 이루어진 두 개의 (N/2)-point DFT로 나누고, 다시 각각 두 개의 (N/4)-point DFT로 나누어서.. 결국 2-point DFT가 나타날 때 까지 계속.
N-Point DFT의 정의는 - 분해식
이 식을
으로 쓸 수 있으며 다시 0 ≤ k ≤ N/2-1에 대한 부분과 N/2 ≤ k ≤ N-1에 대한 부분으로 나우어 다시 쓸수 있다.
0 ≤ k ≤ N/2-1
N/2 ≤ k ≤ N-1
0 ≤ k ≤ N/2-1
여기에 나타나는 2개의 N/2-point DFT 와 는 k에 관해 주기가 N/2인 주기수열이 되며, N/2가 짝수이면 다시 와 를 각각 2개의 (N/4)-point DFT로 나누어 쓸 수 있다.
, 0≤k≤N/2-1
, 0≤k≤N/2-1
원래 주어진 수열의 길이가 이면, 이런 작업을 NLog2-1번 반복함으로써 (N/2)개의 2-point DFT를 얻게 된다.
만약, 인 경우, 최종결과는
이런 방법으로 8-point DFT를 계산하는 과정을 보이는 신호흐름선도가 아래에 있다. 과 같은 이득을 가진 Branch의 개수를 카운트함으로써 각 단계마다 N회의 복소수 곱셈과 N회의 복소덧셈이 필요하며, 총 단계에 대해 총 ()회의 복소수곱셈과 덧셈이 필요하다.
※ FFT를 쓰지 않으면
, 0≤k≤N-1 (DFT)에 의해 X(k)한 개를 계산하는데 N회의 복소수곱셈과 (N-1)회의 복소수 덧셈이 필요하므로, k=0부터 N-1까지 총 N 개의 X(k)값을 계산하는데는 회의 복소수 곱셈과 N(N-1)회의 복소수 덧셈이 필요하게 된다.
② FFT 알고리즘을 이용한 IDFT의 계산
0≤n≤N-1
위식을 DFT 식과 비교해보면 곱해지는 항 의 지수의 부호가 음수이고, 그 크기 1/N로 된것만 다르다. 따라서 IFFT는 FFT 알고리즘에서 입력 데이터 x[n]을 X[K] 로 바꾸고 의 지수의 부호를 (-)로 하며, 최종적인 출력 데이터의 값에 1/N을 곱해주면 된다.
또 다른 방법은 위식의 공액복소수를 취해서 얻어진다.
먼저 X(k)의 공액복소수 에 데헤 FFT를 적용한후, 그 결과의 공액복소수를 취하고 , 다시 1/N을 곱해서 x[n]을 구할 수 있다.
Ⅳ.응용

키워드

FFT,   이산푸리에변환,   스펙트럼