고속 푸리에 변환의 이해

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

 변환이란 하나의 상태 또는 측정 기준에서 다른 상태 또는 측정 기준의 값으로 바꾸는 것을 말한다. 섭씨를 화씨로 변환하는 것은 서로 다른 측정 기준에서의 값으로 변환하는 것이다. 물체의 진동 또는 파동등의 사인(Sin) 신호를 주파수(Frequency)의 성분으로 전환시키는 수학적 기법이 푸리에 변환이다. 전기를 사용하는 설비의 경우 전기 신호 및 진동 등이 시간에 따른 사인(Sin) 신호 특성을 가지고 있기 때문에 푸리에 변환을 통하여 정상적인 상태의 주파수와 비 정상적인 상태의 주파수로 구분하여 고장을 예지 하는 데 활용할 수 있다.

                                                 [ 그림 : 푸리에 변환 이미지 ]

 푸리에 변환을 사용하기 위해서는 신호가 연속적이어야 하는 가정이 필요한데, 컴퓨터 등과 같은 디지털 신호 처리 장치는 모든 데이터를 연속적으로 저장할 수가 없다.  따라서, 시간 함수 및 변환된 주파수 함수도 이산적으로 저장할 수밖에 없기 때문에 이산 푸리에 변환(DFT: Discrete Fourier Transform)을 사용하고 있다.

 이산 푸리에 변환은 계산량이 너무 많다는 단점이 있다.  위의 식을 보면 실수와 복소수의 곱 연산은 N2회 수행해야 하고, 덧셈은 N(N-1) 회 연산을 수행해야 한다. 만약에 N=4096일 경우 하나의 신호 블록에 대해서 실수와 복소수의 곱을 16.777.216번 연산을 해야 하는데 아무리 좋은 컴퓨터라고 해도 빠르게 계산할 수는 없다. 따라서, 이산 푸리에 변환을 빠르게 할 수 있는 변환 방법이 필요한데 이것이 고속 푸리에 변환(FFT : Fast Fourier Transform)이다. 이산 푸리에 변환 계산 속도를 빠르게 하기 위하여 N개의 데이터를 홀수 번호와 짝수 번호로 나눠서 계산함으로써 O(N2)의 계산 횟수는 O(N×logN)으로 줄여주는 변환 방식이다.  N의 크기가 8,192가 되더라도 FFT 변환을 하게 되면 계산 횟수는 106,496으로 줄어들게 되어 빠르게 변환할 수 있다.

                                                   [ 표 : DFT, FFT 연산 회수 비교 ]

------------------------------------------------

O(logN) : 컴퓨터 과학에서 O(log2 N)의 줄임.  데이터 원소가 N개 일 때 알고리즘이 몇 단계  필요한지 계산할 때 활용한다.