1. 고속 푸리에 변환 (FFT,Fast Fourier Transform)
ㅇ 이산 푸리에 변환(DFT)의 계산량을 줄이는 알고리즘
- 대부분의 신호처리 응용에서 계산량을 줄이기 위해 고속 푸리에 변환 (FFT) 알고리즘을 사용
. 한편, 고속의 FFT를 사용한 전문화된 DSP가 산업 전반에서 사용되고 있음
ㅇ 1965년 Tukey와 Cooley에 의해 개발됨
2. DFT 계산의 복잡성
ㅇ 필요 계산 식
[# X[k] = x[0]W^0_N + x[1]W^k_N + x[2]W^{2k}_N + \cdots + x[N-1]W^{(N-1)k}_N \qquad (k = 0,1,2,\cdots,N-1) #]
- WNkn : 회전인자(Twiddle Factor)
. 회전인자는, 복소지수 함수(ex)의 간결한 표현 (WNkn = e-j 2π/N kn)
- X[k] 하나의 계산은,
. N개의 x[k] 데이터를 이용하여,
. N개 항의 곱셈 및 (N-1)개의 덧셈이 필요 함
- k가 N개 점을 나타내므로,
. 이에따라, N개의 X[k] 계산이 필요 함
ㅇ 즉, N점 DFT(N-point DFT, k = 0,1,...,N-1) 계산은, N2번의 복소수 곱셈 등 방대한 계산이 필요
- 필요 곱셈 수 : N2번 (∵ N개 점의 각 k에서 N개 곱셈이 필요, 결국 N*N개 곱)
- 필요 덧셈 수 : N(N-1)번 (∵ N개 점의 각 k에서 (N-1)개 합이 필요, 결국 N*(N-1)개 합)
ㅇ 이를 알고리즘 효율성의 척도로써 볼 때, 빅오표기법으로, O(N2) 만큼 걸림
- N이 커짐에 따라, 매 N 배수 만큼, 계산량이 매우 커짐
ㅇ 또한, 회전인자 WNkn 계산에도 필요한 항의 수가 많음
- 필요 계산 항의 수 : 0 ≤ kn ≤ (N-1)2
ㅇ 그러나, 회전인자의 대칭성 및 주기성을 이용하여, 계산량을 줄일 수 있음
- 단위 원을 한바퀴 도는데 필요한 서로다른 N개의 값 만 계산 필요
3. FFT의 계산량 줄이기 원리
ㅇ FFT는,
- DFT의 상수 및 동작의 대칭성을 이용하여 계산량을 줄임
- DFT를 길이가 짧은 여러 DFT로 계속 분할시켜 곱셈 량을 N에 비례하도록 함
. x[n]을 짧은 길이의 신호로 분할
. 각 분할된 신호의 DFT를 각각 계산
. 각 DFT 결과를 결합하여 X[k] 계산
- N-point FFT 계산 : N log2N 에 비례 O(N log2N)
ㅇ IFFT (역 FFT)는,
- FFT와 동일 구조의 계산 알고리즘을 갖음
4. FFT 주요 파라미터
ㅇ 주파수 분해능 : Δf = 1/T = fs/N
ㅇ 샘플링 주파수 : fs (sample) = 1/Δt
ㅇ 신호 관측 구간 : T = N Δt = N/fs
ㅇ FFT Length : N
5. FFT 알고리즘 계열 분류
ㅇ DIF (Decimation in Frequency)
ㅇ DIT (Decimation in Time)