FFT (Fast Fourier transform)는 이산 푸리에 변환(Discrete Fourier transform, DFT) 를 빠르게 하기 위한 알고리즘으로 요즘 세상에 알게 모르게 굉장히 많이 사용되고 있습니다.


 그 응용이라고 하면 너무나 광범위 하죠~

 

우리가 거의 매일 사용하는 MP3 음악 파일은 DCT(discrete cosine transform) 를 이용한 손실 압축 방식인데 여기도 FFT 가 응용되고~ 요즘 한창 많이들 사용하고 있는 통신 방식인 LTE(Long Term Evolution)나 Wibro 등은 Orthogonal frequency-division multiplexing (OFDM)이라는 기술을 근간으로 하는데~ 이 OFDM 이라는 기술도 FFT 를 통해 구현 됩니다. WIFI 는 말 할 것도 없고 스펙트럼 분석에도 FFT 가 사용되죠~

 

http://ko.wikipedia.org/wiki/%EA%B3%A0%EC%86%8D_%ED%91%B8%EB%A6%AC%EC%97%90_%EB%B3%80%ED%99%98


FFT 는 요즘 그 쓰임이 많은 만큼 여러 언어에서 함수로 제공해 주는 경우가 많은데요~

 

그러한 툴들의 많은 경우가 오늘 소개해 드리는 FFTW 라는 라이브러리를 사용하곤 합니다.

 

FFTW 의 홈페이지는 다음과 같습니다.

www.fftw.org

 

FFTW 라는 명칭은 "Fastest Fourier Transform in the West" 라고 하네요~ 서부에서 가장 빠른 푸리에 트랜스폼이란건데..

 

속도에 대한 자부심이 느껴지네요.

 

FFTW 는 MIT 의 Matteo Frigo 와 Steven G. Johnson 라는 분이 만들었습니다.

 

소개를 보면 ~ one-dimensional 뿐만이 아니라 multi-dimensional transforms도 지원을 하고 임의의 크기에 대한 DFT 도 지원을 하는군요.

 

음성이나 이미지 쪽에서 많이 쓰이는 DCT 나 DST 등도 할 수 있고~ GNU GPL 라이센스의 Free 소프트웨어라고 설명되어 있네요.

 

Non-free licenses 는 MIT 를 통해 살 수 있다고 합니다.

 

FFTW 는 MATLAB 에도 들어있더군요. 물론 Mathworks 에서 Non-free licenses  로 구매한 거겠죠.

 

이전 포스팅에 소개했던 FreeMat 이란 프로그램에도 FFTW 를 사용했다고 하더군요. 


2012/08/20 - [유틸] - MATLAB 과 유사한 Open Source 프로그램 FreeMat

 

아!! 뭔지 모르겠지만 상도 받았군요. 1999 J. H. Wilkinson Prize for Numerical Software 라는 상을 받았다고 하는데~ 상 받을 만 하니깐 받았겠죠~

 

저자들이 쓴  논문("A Fast Fourier Transform Compiler" (in PLDI 1999)) 도 2009년에 The Most Influential PLDI Paper award 라는 상을 받았군요.

 

소개는 대충 여기까지 하고 이제부터 Codeblock 을 이용해서 간단하게 사용해 보죠.

 

다운로드는 링크는 다음과 같습니다.

http://www.fftw.org/download.html

 

윈도우용 DLL 파일은 아래 주소에서 받을 수 있구요.

http://www.fftw.org/install/windows.html

 

32비트 64비트 버전이 있으니 각자 자신의 OS 에 맞게 다운로드 받으시기 바랍니다.

  

 

저는 윈도우 7, 32 비트라 fftw-3.3.2-dll32.zip 파일을 다운로드 받았습니다. 압축을 풀면 필요한 fftw3.h.dll 파일이 들어있습니다.

 

이제 Codeblock 에서 Console application 으로 프로젝트를 하나 생성하고~ 

 

fftw3.h 파일은 CodeBlocks 이 설치된 하위 폴더인 include 폴더에 넣어 줍니다. 저의 경우는 아래 경로에 넣었습니다. 각자 설치 경로에 맞게 넣어 주세요~

 

C:\Program Files\CodeBlocks\MinGW\include

 

그리고 libfftw3l-3.dll, libfftw3f-3.dll, libfftw3-3.dll 파일들은 위에서 생성한 project 폴더에 소스와 같이 넣었습니다.

 

예제는 다음과 같이 간단하게 1024 크기로 FFT 하는 예제 입니다.

 

한번 따라 해 보실~ 분들을 위해 파일로 첨부합니다.



main.cpp

 

#include <iostream>

#include <fftw3.h>

 

using namespace std;

 

int main()

{

    fftw_complex *in, *out;

    fftw_plan p;

 

    int N=1024; // FFT size

 

    in = (fftw_complex*) fftw_malloc(sizeof(fftw_complex) * N); // input buffer

    out = (fftw_complex*) fftw_malloc(sizeof(fftw_complex) * N); // output buffer

    p = fftw_plan_dft_1d(N, in, out, FFTW_FORWARD, FFTW_ESTIMATE); // FFT 준비

 

    for (int n=0; n< N ; n++) // complex data sample 생성

    {

     in[n][0]=n; // real

in[n][1]=n; // imag

    }

 

    fftw_execute(p); // FFT 수행

 

cout << fixed;

cout.precision(10);

 

for (int n=0; n< N ; n++) // 결과 확인

    {

     cout << n << " real : " <<out[n][0] << " imag : " <<out[n][1] << endl ;

    }

 

    fftw_destroy_plan(p);

    fftw_free(in); fftw_free(out);

 

    return 0;

}

 

마지막으로 Codeblock 에서 아래 그림처럼 Settings >> Compiler and … 에 들어갑니다.

 

 

 

이제 아래 그림처럼 위에서 해당 폴더에 추가 했던 dll 파일들의 path 를 잡아줍니다.

  

이제 설정은 다 끝났습니다. F9 를 눌러서 실행해보면 다음과 같이 FFTW 라이브러리를 이용한 FFT 가 정상적으로 동작하는 것을 확인 할 수 있습니다. 요렇게요~

 

 

제대로 된 건가 해서 같은 입력 값에 대해 MATLAB으로 FFT 해서 비교해 보니 똑같이 나오더군요.

 

제가 한 예제는 아래 주소의 FFTW 의 매뉴얼에 있는 튜토리얼을 보고 따라 한 건데요~

http://www.fftw.org/fftw3_doc/

 

내용이 방대하니 필요한 부분만 쏙쏙~~ 골라서 보시기 바랍니다.

 


  1. 키드 2014.05.11 18:10

    안녕하세요 제가 fftw를 이용하여 가지고 있는 데이터를 푸리에 변환 시키려고 하는데 정말 모르겠어서 이렇게 댓글 남깁니다
    혹시 보시게된다면 메일 부탁드립니다
    pokssak26@naver.com

  2. 깜찍이홍섭이 2014.07.22 16:06

    블로그 대로 수행해보다가 codeblocks의 하위폴더가 share 폴더 밖에 없고 include 폴더는 없는데 이런 경우는 어떻게 해야 합니까?

    • 남성 2014.07.22 17:46 신고

      codeblock 을 컴파일러 제외 하고 설치 한 경우인가요? 뭐 그런 경우에는 fftw3.h 파일을 해당 프로젝트 추가해서 수행해도 됩니다. 어차피 컴파일러가 인식할수 있는 path 에만 넣으면 되니까요.

      또는 Mingw 를 따로 설치 했다면 mingw 를 설치한 폴더 하위에 include 폴더에 fftw3.h 를 넣으셔도 될 겁니다.

  3. goni 2016.05.17 22:26

    안녕하세요. c++언어로 리듬게임 제작 중인 학생 입니다. 덕분에 많은 도움 됬습니다.
    질문 하나 하고 싶은데.. 혹시 fmod로 mp3 파일 데이터 추출 해서 적용 하려고 하는데 방법 아시나요?

  4. 2018.05.21 15:18

    비밀댓글입니다

    • 남성 2018.05.21 15:54 신고

      통신 전공했고 통신 분야 회사, 소프트웨어 회사, 자동차 회사 등을 거치면서 주로 알고리즘 관련한 개발을 했습니다.

요즘 영상이나 음성과 같음 미디어 컨텐츠들이 많이 사용되고 있습니다.

 

이런 미디어 파일들은 데이터 량이 굉장히 크기 때문에 손실 압축 방식으로 그 데이터를 줄이는 압축 기술들이 많이 사용되는데~

 

이런 기술에 많이 이용되는 것이 바로 DCT(Discrete cosine transform) 라고 합니다.

 

mp3, jpg 같은 파일 형식들이 다~~ DCT 를 사용한다고 하니깐 정말 우리 생활과 너무나 밀접한 기술이라 할 수 있을 것 같네요.

 

DCT 위키 피디아 : http://en.wikipedia.org/wiki/Discrete_cosine_transform

 

위 주소의 내용을 보면 DFT 는 periodic 신호의 비연속 특성 때문에 고주파가 많이 올라오는 반면에 DCT 는 연속적이어서 고주파 성분이 적고 ~ 그에 따라 저주수에 신호 파워가 몰리는 특징이 있더군요.

 

따라서 특정 Threshold 보다 작은 고주파 신호를 없앤다 해도 DFT 에 비해 신호의 왜곡이 덜 할 것이라는 것을 예상해 볼 수 있습니다.

 

DCT 도 DFT 와 유사하기 때문에 FAST DCT 알고리즘이 존재 합니다.

 

FAST DCT 에 대한 내용들이 정리되어 있는 페이지 : http://fourier.eng.hmc.edu/e161/lectures/dct/node2.html

 

오늘은 위 주소의 내용들을 참조하여 FAST DCT 에 대해 간단히 소개해 보려 합니다.

 

일반적으로 흔히 말하는 DCT 수식은 다음과 같고 DCT-II 라고 합니다.

 

 

Inverse DCT 는 DCT-III를 말하며 다음 수식과 같죠.

 

 

FAST DCT 의 과정은 다음과 같이 세 단계로 구성되더군요.

 

FAST DCT 과정

 

 

 

 

FAST IDCT 과정

 

 

 

 

이론을 알아 봤으니깐 간단하게 MATLAB으로 확인해 볼까요~

 

MATLAB Signal Processing Toolbox 가 있으신 분들은 dct(), idct() 라는 함수를 사용하실 수 있습니다. 두 함수들은 DCT,IDCT matrix 를 orthogonal 하게 만들어 주기 위해서 특정 scale factor 들을 곱해 줬는데요.

 

위에서 서명했던 DCT-II, DCT-III 수식을 MATLAB 의 orthogonal 한 DCT 수식들과 같게 만들기 위해서는 다음과 같이 scale factor 를 곱해 주어야 합니다.

 

DCT-II 의 경우는 X(0) 에 을 곱해 주고 X 전체에 를 곱해 주면 되고~

 

DCT-III 의 경우는 X(0) 에 을 곱해 주고 전체에 곱해 주면 MATLAB 내장 함수들과 동일한 결과를 얻을 수 있습니다.

 

코드는 다음과 같습니다.


 

 

실행 결과에 대해 command 창에서 확인해 보면 에러가 10-15 정도니까~~~ 0 이나 마찬가지라는 것을 확인 할 수 있죠~

 


+ Recent posts