FFT   Fast Fourier Transform   고속 푸리에 변환

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

Top > [기술공통]
[기초과학]
[진동/파동]
[방송/멀티미디어/정보이론]
[전기전자공학]
[통신/네트워킹]
[정보기술(IT)]
[공업일반(기계,재료등)]
[표준/계측/품질]
[기술경영]
전기전자공학 >   1. 전기 (Electricity) 이란?
  2. 전기전자공학
[디지털공학]
[신호 및 시스템]
[회로해석]
[전자기학]
[초고주파공학]
[반도체]
[전자회로]
[전기공학]
[자동제어]
[전자공학(기타일반)]
신호 및 시스템 > [신호 표현/성질]
[시스템 표현/성질]
[신호처리 기초]
[연산 소자]
[이산 신호/이산 시스템]
[변환 해석]
[필터]
[고속 신호 회로 해석]
이산 신호/이산 시스템 > [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 계산 복잡성 감축

  ㅇ N점 DFT는 N²번의 곱셈 등 방대한 계산이 필요
     - 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)

  ㅇ N개 점의 계산에 필요한 곱셈 수
     - N-point DFT 계산 : N2번 곱셈 필요  O(N2)     ☞ 계산복잡도 참조
        . 필요 곱셈 수 : N2번 (∵ 각 k에서 N개 곱, 결국 N*N개 곱)
        . 필요 덧셈 수 : N(N-1)번 (∵ 각 k에서 (N-1)개 합, 결국 N*(N-1)개 합)

  ㅇ 회전인자 WNkn 계산에 필요한 항의 수가 많음
     - 필요 계산 항의 수 : 0 ≤ kn ≤ (N-1)2
     - 회전인자 대칭성주기성을 이용하여, 계산량을 줄일 수 있음

  ㅇ FFT는,
     - DFT상수 및 동작의 대칭성을 이용하여 계산량을 줄임
     - DFT를 길이가 짧은 여러 DFT로 계속 분할시켜 곱셈 량을 N에 비례하도록 함
        . x[n]을 짧은 길이의 신호로 분할
        . 각 분할된 신호DFT를 각각 계산
        . 각 DFT 결과를 결합하여 X[k] 계산
     - N-point FFT 계산 : N log2N 에 비례  O(N log2N)

  ㅇ IFFT (역 FFT)는,
     - FFT와 동일 구조를 갖는 계산 알고리즘을 갖음


3. 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(고속푸리에변환)

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