FFT   Fast Fourier Transform   고속 푸리에 변환

(2020-07-02)
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. 컨볼루션 합

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

  ㅇ 필요 계산 식
     - 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


[이산푸리에변환(DFT)] 1. DFT(이산푸리에변환) 2. DFT 성질 3. 회전 인자 4. DFT 계산 5. FFT(고속푸리에변환) 6. 컨볼루션 합
  1.   기술공통
  2.   기초과학
  3.   진동/파동
  4.   방송/멀티미디어/정보이론
  5.   전기전자공학
        1. 전기 (Electricity) 이란?
        2. 전기전자공학
    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.   기술경영

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