[신호처리] Fourier Transform vs Fast Fourier Transform(FFT)

1. 개요
   • 푸리에 변환과 고속 푸리에 변환은 모두 신호를 시간 영역에서 주파수 영역으로 변환하는 방법이다.
   • 계산 방법과 효율성에서 차이가 있다.
2. 푸리에 변환(Fourier Transform)
   • 신호가 주어지면, 이 신호를 구성하는 각 주파수 성분의 크기와 위상을 계산할 수 있다.
   • 실제 컴퓨터에서는 이산 푸리에 변환(DFT)를 사용한다. DFT는 Discrete한 길이의 신호를 주파수 성분으로 변환한다.
   • 하단의 수식의 복잡도는 N*N이다. 따라서 DFT는 신호의 샘플 수가 많아질수록 계산 비용이 커진다.

2. 고속 푸리에 변환(Fast Fourier Transform)

• 고속 푸리에 변환(FFT)은 DFT를 효율적으로 계산하는 알고리즘이다.
• FFT는 DFT의 계산을 빠르게 수행하기 위해 신호를 작은 부분으로 나누어 재귀적으로 계산한다. → 계산복잡도의 감소

    2.1. Cooley-Tukey 알고리즘

• 신호의 분할: 입력 신호를 짝수 인덱스와 홀수 인덱스로 나눈다.
• 재귀적 계산: 배열의 길이가 1인 배열의 푸리에 변환은 배열 자신이다.
• → 이 특성을 이용하여, 분할된 신호에 대해 각각 DFT를 재귀적으로 계산한다.
• 결과의 합성: 짝수 및 홀수 신호에 대한 DFT 결과를 결합하여 전체 신호의 DFT를 구한다.
• (분할 단계에서 신호를 절반으로 나누므로 log N 단계)*(각 합성 단계에서 N개의 연산이 필요) = NlogN