FFT

FFT (Fast Fourier Transform)

함수의 이해

• 직선은 원의 특정 각도에서 원의 특정 점을 지나는 선입니다.

• 원은 직선의 집합입니다.

• 주기성을 가지는 함수는 Sine 함수의 집합으로 표현할 수 있습니다. (물론 모든 함수를 표현할 수 있지만 많은 Sine 함수의 합으로 표현할 수 있습니다.)

Fourier Transform

푸리에 변환(Fourier Transform)은 시간이나 공간에 대한 함수(신호)를 다양한 주파수 성분(사인 및 코사인 함수)의 합으로 분해하여, 주파수 도메인에서 신호의 구성 요소를 분석하는 수학적 원리입니다. 복잡한 파동을 단순한 주기 함수들의 합으로 나타내어 신호 처리, 영상 처리 등에서 주파수 성분별 함량을 분석하는 데 활용됩니다.

$$X(f) = \int_{-\infty}^{\infty} x(t)\, e^{-j2\pi ft} \, dt$$

$$O(N^2) \text{ time complexity}$$

DFT (Discrete Fourier Transform)

DFT는 Fourier Transform을 이산적으로 계산하는 방법입니다.

$$X(k) = \sum_{n=0}^{N-1} x(n)\, e^{-j2\pi kn/N}$$

X[k] 를 출력하기 위해서는 모든 점의 값을 계산해야 합니다.

$$\text{알고리즘 복잡도: } O(N^2)$$

FFT (Fast Fourier Transform)

• FFT는 Fourier Transform을 빠르게 계산하는 알고리즘입니다. (DFT의 계산 복잡도를 줄이기 위해 사용되는 알고리즘입니다.)

• DFT와 FFT의 결과는 완전히 일치합니다.

Even / Odd index decomposition

$$X[k] = \sum_{m=0}^{\frac{N}{2}-1} x[2m]\; e^{-j \frac{2\pi}{N} k (2m)} + \sum_{m=0}^{\frac{N}{2}-1} x[2m+1]\; e^{-j \frac{2\pi}{N} k (2m+1)}$$

$$\text{알고리즘 복잡도: } O(N \log N)$$

Exponential simplification

짝수항:

$$E[k] = e^{-j \frac{2\pi}{N} k (2m)} = e^{-j \frac{2\pi}{N/2} k m}$$

홀수항:

$$O[k] = e^{-j \frac{2\pi}{N} k (2m+1)} = e^{-j \frac{2\pi}{N/2} k m}\, e^{-j \frac{2\pi}{N} k}$$

Recursive decomposition

$$X[k] = E[k] + W_N^k O[k]$$

$$X[k + \frac{N}{2}] = E[k] - W_N^k O[k]$$

$$X[k + \frac{N}{2}] \text{ 는 계산을 할 필요 없어 } X[k] \text{ 의 계산 결과를 사용하면 됩니다. 바뀌는 부분은 } W_N^k \text{ 의 부호만 바뀝니다. }$$

여기서,

$$W_N^k = e^{-j \frac{2\pi}{N} k}$$

$$W_N^{k + \frac{N}{2}} = e^{-j \frac{2\pi}{N} (k + \frac{N}{2})} = e^{-j \frac{2\pi}{N} k} e^{-j \frac{2\pi}{N} \frac{N}{2}} = e^{-j \frac{2\pi}{N} k} e^{-j \pi} = -e^{-j \frac{2\pi}{N} k}$$

FFT는 위에서 보이는 것처럼 재귀적으로 계산됩니다. (재귀적으로 계산되기 때문에 계산 복잡도를 줄일 수 있습니다.)

• 예를 들어, N=8 인 경우, 총 3단계의 재귀 계산이 필요합니다.

  • 1단계: N/2=4 개의 점을 계산

  • 2단계: N/4=2 개의 점을 계산

  • 3단계: 1 개의 점을 계산

이렇게 계산하면 총 3단계의 재귀 계산이 필요합니다.

$$\text{알고리즘 복잡도: } O(N \log N)$$