07-7. C로 짠 FFT Code

C나 C++로 된 FFT 코드는 예전부터 많이 있을 것이기에, C용 FFT 코드는 잘 되어 있는 코드를 소개만 하려고 했었다.

그러나, 여러 코드들을 구글링해서 찾아봤으나, 예상외로 맘에 드는 코드를 찾지 못했다.

간단히 짤 수 있을 거 같은데, 복잡하게 짰거나, 너무 길게 짠 코드가 대부분이었다.

그래서, 계획에 없었으나 C로 FFT를 짜기로 한다.

 

---

코드 작성 방침

• 가능한 간단히 짠다. 
• 최상의 속도가 나오도록 한다.
• 포인터를 사용하지 않는다. 신호데이터를 double형 배열로 처리
• 기본 제공되는 cos 함수 정도만 사용하고, 특수한 함수를 사용하지 않는다.
• 입력 데이터의 개수 제한을 하지 않는다. 메모리가 허용하는 한 
• 쿨리-튜키 알고리즘 사용
• fft만 구현 (ifft는 구현하지 않음)
• 2^n 사이즈의 데이터만 허용 (아닌 경우 모자라는 부분을 0으로 채워서 사용하면 됨)

 

작성된 코드

단순하게 c 파일 1개, 헤더 파일 1개로 구성한다.

• fft.c
• fft.h

제공되는 함수는 2개

• int fft(long N, double XR[], double XI[]);
• char * cplxStr(double re, double im);

소스코드는 여기 참조

 

FFT 코드 수행 방법

1. fft.h를 include
2. 입력 데이터의 크기 N 만큼의 double형 배열 2개를 만든다. 실수부 및 허수부용 배열
3. 실수부용 배열에 입력 데이터를 넣는다.
4. 실수부, 허수부 배열 2개와, 배열 크기 N을 파라미터로 해서 fft 함수 호출
5. 실수부 및 허수부 배열 값에 fft 결괏값 출력됨
6. "a+bi" 형태의 문자열을 얻으려면 cplxStr 함수 사용

const long N=8;    
double XR[8]= {0,0,0,0,1,1,1,1};
double XI[8]; 

printf("** test_simple_fft **\n");
int result = fft(N,XR, XI);

for(long i=0; i<N; ++i)  printf("%s, ", cplxStr(XR[i],XI[i]));
printf("\n");

 

코드 수행 속도

test_fft.c에 64kB 데이터에 대한 fft 수행 시간을 재는 코드가 있다.

 

수행 결과, 64kB 데이터에 대한 fft 수행 시간은 약 11ms ~ 13ms

 

• 입력 데이터 크기: 64 kBytes
• fft 수행 시간: 11ms ~ 13ms
• 사용 컴퓨터 사양: 11th Gen Intel(R) Core(TM) i7-1165G7 @ 2.80GHz

테스트 코드는 다음과 같다.

#define CNT 65536
#define PI 3.14159265358979
int test64k(void){
    long N = CNT;
    static double XR[CNT]; //use heap not stack avoiding "Segmentation Fault" for over 1M data
    static double XI[CNT];
   
    printf("** test_measure_time **\n");

    for(long i=0;i<N;++i){
        XR[i] = cos(2*PI*0.004*i);
    }

    double beforeT, diffT;
    int result=-1;
    beforeT = clock();
    result=fft(N, XR, XI);
    diffT = clock() - beforeT;
    printf("%.0fms\n", diffT);

    if(result < 0){
        printf("FFT calculation Error\n");
    }

    for(long i=0;i<8;++i)  printf("%s ,",cplxStr(XR[i],XI[i]));
    printf("\n");
    for(long i=(N-8);i<N;++i)  printf("%s ,",cplxStr(XR[i],XI[i]));
    
    return 0;
}

테스트 코드 수행 화면

64kBytes 입력데이터에 대한 fft 수행화면. 12ms 소요

 

 

-끝-