FFT   Fast Fourier Transform   고속 푸리에 변환

(2021-07-06)

FFT Length


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)

이산푸리에변환(DFT)
   1. DFT(이산푸리에변환)   2. DFT 성질   3. 회전 인자   4. DFT 계산   5. FFT(고속푸리에변환)   6. 컨볼루션 합  
푸리에변환 표현 종류
   1. CTFS(연속시간 푸리에급수)   2. CTFT(연속시간 푸리에변환)   3. DTFS(이산시간 푸리에급수)   4. DTFT(이산시간 푸리에변환)   5. DFT(이산푸리에변환)   6. FFT(고속푸리에변환)  


Copyrightⓒ written by 차재복 (Cha Jae Bok)               기술용어해설 후원
"본 웹사이트 내 모든 저작물은 원출처를 밝히는 한 자유롭게 사용(상업화포함) 가능합니다"