FFT

FFT (Fast Fourier Transform)

함수의 이해

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

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

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

Fourier Transform

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

X(f)=x(t)ej2πftdtX(f) = \int_{-\infty}^{\infty} x(t)\, e^{-j2\pi ft} \, dt
O(N2) time complexityO(N^2) \text{ time complexity}

DFT (Discrete Fourier Transform)

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

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

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

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

FFT (Fast Fourier Transform)

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

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

Even / Odd index decomposition

X[k]=m=0N21x[2m]  ej2πNk(2m)+m=0N21x[2m+1]  ej2πNk(2m+1)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)}
알고리즘 복잡도: O(NlogN)\text{알고리즘 복잡도: } O(N \log N)

Exponential simplification

짝수항:

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

홀수항:

O[k]=ej2πNk(2m+1)=ej2πN/2kmej2πNkO[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]+WNkO[k]X[k] = E[k] + W_N^k O[k]
X[k+N2]=E[k]WNkO[k]X[k + \frac{N}{2}] = E[k] - W_N^k O[k]
X[k+N2] 는 계산을 할 필요 없어 X[k] 의 계산 결과를 사용하면 됩니다. 바뀌는 부분은 WNk 의 부호만 바뀝니다. X[k + \frac{N}{2}] \text{ 는 계산을 할 필요 없어 } X[k] \text{ 의 계산 결과를 사용하면 됩니다. 바뀌는 부분은 } W_N^k \text{ 의 부호만 바뀝니다. }

여기서,

WNk=ej2πNkW_N^k = e^{-j \frac{2\pi}{N} k}
WNk+N2=ej2πN(k+N2)=ej2πNkej2πNN2=ej2πNkejπ=ej2πNkW_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단계의 재귀 계산이 필요합니다.

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

Last updated