CodeBlock 에서 FFTW 라이브러리를 사용한 FFT 실습

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/

 

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