이산 푸리에 변환(DFT)와 고속 푸리에 변환(FFT)

신호를 다루는데 있어 주파수의 개념은 어떤 산업 분야를 막론하고 중요하다고 할 수 있습니다. 앞서 푸리에 변환(Fourier Transform)이 무엇인지 살펴 보았는데요. 이번 시간에는 이산 푸리에 변환(DFT)와 고속 푸리에 변환(FFT)에 대해 알아보도록 하겠습니다.

푸리에 변환(Fourier Transform, FT)

푸리에 변환(Fourier Transform, FT) 우리가 흔히 말하는 푸리에 변환(Fourier Transform, FT)이라고 하면 주파수 분석 하기위해 Time-Domain을 Frequency-Domain으로 변환하는 과정을 말합니다. 그러나 푸리에 변환

moonnote.tistory.com

이산 푸리에 변환(DFT, Discrete Fourier Transform)

디지털 신호 분석에서 사용되며 연속적인 Time-domain에서의 푸리에 변환과는 다르게 N개의 유한한 FT를 처리하는 방식입니다. 따라서, 푸리에 변환에서의 ±∞ 적분 형태의 무한 적분이 아닌 유한 합으로 대체한다고 보시면 되겠습니다. DFT에 대한 수식입니다.

자, 여기서 앞서 소개하였던 수식의 주파수 또는 주기 표현 등 자유롭게 다룰 수 있는 것이 좋다고 말씀드렸었는데요. \(wt\)에 대해 \(wt=sin(2\pi ft)=\frac{2\pi t}{T}\) 를 응용하면 아래와 같은 수식으로도 표현할 수 있습니다. (리마인드 Link : 푸리에 급수(Fourier Series))

고속 푸리에 변환(FFT, Fast Fourier Transform)

우리가 주파수 분석을 논할 때 가장 많이들 말하는 단어가 FFT가 아닐까 합니다. FFT는 DFT의 알고리즘 중 하나라고 볼 수 있는데요. FFT는 샘플링 중 필요한 신호만 골라내어 빠르게 연산하는 방법을 말합니다. 예를들어 N개의 DFT 신호가 있다고 한다면 α/N개만큼 신호를 골라내어 단순 연결하고 제외된 신호들의 예상치를 적용하는 것이죠. 과거에는 컴퓨터 성능 측면에서 DFT 계산이 너무 오래 걸리는 단점이 있었다고 합니다. 이 때 DFT 간소화하거니 샘플링을 줄여서 진행하곤 했었는데요. 요즘 컴퓨터들은 성능이 워낙 좋은 편이다보니 DFT=FFT로 보기도 한다고 합니다.

시간 복잡도와 Big-O 표기법(Time Complexity and Big-O Notation)

시간 복잡도란, 입력에서 출력이 진행될 때까지 걸리는 시간을 말합니다. 컴퓨터에서 작동하는 알고리즘이 취해 시간으로 정량화 한 것이죠. 그리고 이런 알고리즘의 효율성을 표기해 주는 방법이 Big-O 표기법인 것이죠. O(1), O(logN), O(N), O(NlogN), O(\(N^{2}\)), O(\(N^{3}\)), O(\(2^{N}\)), O(N!) 의 형태로 표기하며 아래는 이를 비교한 차트입니다.

Big-O Notation(출처 : http://devwebcl.blogspot.com/)

Fourier Transform을 소개하다가 이 이야기를 왜 하느냐? 위에서는 요즘 PC 성능이 워낙 좋다보니 DFT=FFT로 생각하기도 한다고 했지만 엄밀히 따지자면 DFT는 O(\(N^{2}\)), FFT는O(NlogN) 방식이기 때문입니다. 해당 본문에서는 대략적인 감을 익히고 참고하는 정도로 이 정도만 소개드리오니 관심있으신 분은 추가 검색을 통하여 공부를 해보시면 좋을 것 같네요. DFT : O(\(N^{2}\)), FFT : O(NlogN) 방식에 대해 샘플 n개에 대한 Computation Time을 그래프로 나타내면 아래와 같이 나오며 해당 내용을 잘 정리해보시면 DFT와 FFT에 대한 감을 익히실 수 있을 것이라 사료되네요. 만약 어려우신 분들이 계시다면 그냥 DFT가 무엇인지, DFT=FFT로 생각해도 될만큼 현재 컴퓨터 성능이 많이 좋아졌다고만 생각하셔도 무방하오니 참고용으로 시간 복잡도 및 Big-O에 대해 소개드리며 DFT와 FFT에 대한 포스팅을 마치도록 하겠습니다.