FFT   Fast Fourier Transform   고속 푸리에 변환

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

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

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


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

 
        최근수정     요약목록(시험중)     참고문헌