FFT   Fast Fourier Transform   고속 푸리에 변환

(2020-07-02)
Top > [기술공통]
[기초과학]
[진동/파동]
[방송/멀티미디어/정보이론]
[전기전자공학]
[통신/네트워킹]
[정보기술(IT)]
[공학일반(기계,재료등)]
[표준/계측/품질]
[기술경영]
전기전자공학 >   1. 전기전자공학
  2. 전기 (Electricity) 이란?
[디지털공학]
[신호 및 시스템]
[회로해석]
[전자기학]
[초고주파공학]
[반도체]
[전자회로]
[전기공학]
[자동제어]
[전자공학(기타일반)]
신호 및 시스템 > [신호 표현/성질]
[시스템 표현/성질]
[신호처리 기초]
[연산 소자]
[이산 신호/이산 시스템]
[변환 해석]
[필터]
[고속 신호 회로 해석]
변환 해석 >   1. 변환 이란?
  2. 주파수 영역
  3. 복소 주파수 영역
[변환 종류]
[푸리에 변환 이론]
푸리에 변환 이론 >   1. 푸리에 표현
  2. 시간 주파수 관계
[푸리에변환 표현 종류]
[푸리에 급수]
[푸리에 변환 성질]
[푸리에변환(기타일반)]
푸리에변환 표현 종류   1. CTFS(연속시간 푸리에급수)
  2. CTFT(연속시간 푸리에변환)
  3. DTFS(이산시간 푸리에급수)
  4. DTFT(이산시간 푸리에변환)
  5. DFT(이산푸리에변환)
  6. FFT(고속푸리에변환)

Top > [기술공통]
[기초과학]
[진동/파동]
[방송/멀티미디어/정보이론]
[전기전자공학]
[통신/네트워킹]
[정보기술(IT)]
[공학일반(기계,재료등)]
[표준/계측/품질]
[기술경영]
전기전자공학 >   1. 전기전자공학
  2. 전기 (Electricity) 이란?
[디지털공학]
[신호 및 시스템]
[회로해석]
[전자기학]
[초고주파공학]
[반도체]
[전자회로]
[전기공학]
[자동제어]
[전자공학(기타일반)]
신호 및 시스템 > [신호 표현/성질]
[시스템 표현/성질]
[신호처리 기초]
[연산 소자]
[이산 신호/이산 시스템]
[변환 해석]
[필터]
[고속 신호 회로 해석]
이산 신호/이산 시스템 > [A/D,D/A 변환]
[이산 신호,이산 연산]
[이산 푸리에 표현]
[z 변환]
[이산 시스템]
이산 푸리에 표현 >   1. DTFS(이산시간 푸리에급수)
  2. DTFT(이산시간 푸리에변환)
  3. 디지털 주파수
[이산푸리에변환(DFT)]
이산푸리에변환(DFT)   1. DFT(이산푸리에변환)
  2. DFT 성질
  3. 회전 인자
  4. DFT 계산
  5. FFT(고속푸리에변환)
  6. 컨볼루션 합

1. 고속 푸리에 변환 (FFT,Fast Fourier Transform)이산 푸리에 변환(DFT)의 계산량을 줄이는 알고리즘
     - 대부분의 신호처리 응용에서 계산량을 줄이기 위해 고속 푸리에 변환 (FFT) 알고리즘을 사용
        . 한편, 고속의 FFT를 사용한 전문화된 DSP산업 전반에서 사용되고 있음

  ㅇ 1965년 Tukey와 Cooley에 의해 개발됨


2. DFT 계산의 복잡성

  ㅇ 필요 계산 식
     - X[k] = x[0]WN0 + x[1]WNk + x[2]WN2k + ... + x[N-1]WN(N-1)k  (k = 0,1,...,N-1)
        . WNkn : 회전인자(Twiddle Factor)
           .. 회전인자는, 복소지수 함수(ex)의 간결한 표현 (WNkn = e-j 2π/N kn)
        . k가 N개 점을 나타내며 이에따라, N개의 X[k] 계산이 필요 하고, 
           .. X[k] 하나의 계산은, N개 항의 곱셈과 (N-1)개의 덧셈이 필요하게 됨          

  ㅇ 즉, N점 DFT(N-point DFT, k = 0,1,...,N-1) 계산은, N²번의 복소수 곱셈 등 방대한 계산이 필요
     - 필요 곱셈 수 : 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 = 1/Δt

  ㅇ 신호 관측 구간 :  T = N Δt = N/fs

  ㅇ FFT length     :  N


[푸리에변환 표현 종류] 1. CTFS(연속시간 푸리에급수) 2. CTFT(연속시간 푸리에변환) 3. DTFS(이산시간 푸리에급수) 4. DTFT(이산시간 푸리에변환) 5. DFT(이산푸리에변환) 6. FFT(고속푸리에변환)

 
        최근수정     요약목록     참고문헌