FFT(고속푸리에 변환)란 무엇인가

1. FT(Fourier Transform, 푸리에 변환)는 시간에 대한 함수(신호)를 주파수 성분으로 분해하는 작업이다. 함수가 푸리에 변환이 되면 주파수의 복소함수가 되고, 복소함수의 절대값 = 원래 함수를 구성하는 주파수 성분의 양, 편각 = 기본 사인 곡선과의 위상차를 나타낸다. 푸리에 변환은 주파수 영역 표현 이라고도 한다.

푸리에 변환이라는 용어는 주파수 영역의 함수뿐만 아니라 주파수 영역의 함수와 시간 영역의 함수를 잇는 수학적 연산(혹은 공식) 모두를 의미한다. 푸리에 변환은 시간의 함수에 제한되어있지 않지만, 용어의 통일을 위해 원래 함수의 영역을 보통 시간 영역의 함수로써 취급한다.

주파수에서 원래 함수를 복원하기 위해 모든 구성주파수 성분을 조합하는 변환을 푸리에 역변환 또는 푸리에 합성 이라 한다.

시간 영역에서 미분연산은 주파수 영역에서 곱셈과 같고, 합성곱은 평범한 곱셈과 같다. 이는 신호에 필터를 적용하는 것과 같은 모든 선형 시불변 시스템은 주파수 영역에서 비교적 쉽게 표현될 수 있다.

단점 : 시간에 대한 연속성이 고려되지 않아 문제가 많음, 이를 위해 DTFT, STFT 등 여러 기술이 나왔다.

푸리에 급수 : 주기 함수를 삼각함수의 가중치로 분해한 급수이다.

 *주파수 : 주기적인 현상이 단위시간 동안 몇 번 일어나는지 나타내는 말

 *복소함수 : 정의역과 공역이 모두 복소수인 함수

 *편각 : 복소평면 위의 극좌표에서의 각도, *극좌표 : 평면 위의 위치를 각도와 거리를 써서 나타내는 좌표계

 *위상 : 반복되는 파형의 한 주기에서 첫 시작점의 각도 혹은 어느 한 순간의 위치

 *선형 시불변 시스템(Linear Time-Invariant system : LTI)

1) 선형성(Linearity) : Superposition을 사용할 수 있으므로 출력을 계산하기 쉽다.

-Homogeneity : 입력을 n배로 했을 때 출력도 n배가 되어야 한다.

-Additivity : n개의 입력에 대한 출력은 각각의 입력에 대한 출력의 합과 같다.

2) Time Invariance : 수학적 표현은 시간이 지나도 변하지 않는다.

-x(t) -> y(t) 이면 x(t -t`) -> y(t-t`)을 만족해야 한다.

 *급수 : 수열의 모든 항을 더한 것이다.

2. DFT(Discrete Fourier Transform, 이산 푸리에 변환)은 이산적인 입력 신호에 대한 푸리에 변환이다.

공식은 위키백과 참고 

3. FFT(Fast Fourier Transform, 고속 푸리에 변환)은 DFT와 그 역변환을 빠르게 수행하는 효율적인 알고리즘이다.

DFT는 O(n^2)의 시간복잡도를 가지지만 FFT를 사용하면 O(nlogn)이 된다. DFT의 경우 n이 합성수일 때 소인수분해로 성능을 높일 수 있지만 FFT는 소수일 경우에도 O(nlogn)을 보장한다.

Cooley-Tukey Algorithm(쿨리튜키 알고리즘)

가장 일반적으로 사용되는 FFT 알고리즘으로 분할 정복(Divide and conquer)를 사용한다. 재귀적으로 n 크기의 DFT를 n = n1 n2로 나눠 계산한다. 보통 2등분하기때문에n = 2^k일 때 많이 사용되지만 n1과 n2가 같을 필요는 없기때문에 임의의 합성수일 때에도 사용할 수 있다.

공식으 위키백과 참고