[알고리즘] 고속 푸리에 변환

고속 푸리에 변환이란

고속 푸리에 변환은 복잡한 소리나 신호를 간단한 파형으로 나누는 방법이다. 예를 들어,우리가 듣는 소르를 각각의 파형으로 나누어 분석하는 것이 고속 푸리에 변환이다.

 

작동 원리

• 소리나 신호를 입력으로 받는다.
• 이 신호를 여러개의 작은 파형으로 나눈다.(신호 분할: 분할 정복 방법을 사용하여 분할)
• 각 파형의 크기와 주파수를 계산한다.(재귀적 처리: 나눈 신호를 FFT를 사용해서 처리, 이 과정을 나눌 수 없을때 까지 반복 후 나눠진 신호의 FFT 결과를 합쳐서 최종 결과 생성)

예시)

• 입력신호 : 길이가 8인 신호가 있다고 가정
• 분할 : 이 신호를 길이가 4인 두개의 신호로 나눈다.
• 재귀적 처리 : 각각의 길이가 4인 신호를 다시 두개의 길이가 2인 신호로 나눈다.
• 최종분할 : 길이가 2인 신호를 길이가 1인 신호로 나눈다.
• 합치기 길이가 1인 신호부터 FFT 결과를 합치면서 최종 결과를 얻는다.

 

수학적 배경

FFT는 복소수와 오일러 공식을 이용한다. 특히 1의 (N)제곱근을 이용해 신호를 변환한다.

 

복소수란?

z= a+bi 와 같이 실수와 허수를 합친 수를 복소수라고 한다.

 

오일러 공식이란?

오일러 공식은 복소수와 삼각함수 사이의 관계를 나타내는 수학공식이다.

오일러 공식은 다음과 같다.

$$ e^{ix}=cos(x) + i sin(x) $$

 

여기서 e는 자연상수(약 2.718),i 는 허수 단위, x는 각도(라디안)

 

오일러 공식의 의미

오일러 공식은 복소수를 극좌표로 표현할 때 유용하다. 예를 들어 복소수(z)를 극좌표로 나타내면 다음과 같다.

$$z=re^{i\theta}$$

여기서 r은 복소수의 크기(절댓값), θ 는 복소수의 각도(편각)이다.

 

예)

• 복소수 표현: (z=3+4i)
• 크기 계산 : (|z|=√{3^2 + 4^2} =5   
• 각도계산 :     

$$\theta = \tan^{-1}\left(\frac{4}{3}\right)$$

• 극좌표 표현 

$$z = 5e^{i\theta} $$

 

 

고속 푸리에 변환 알고리즘 구현 코드

#include <iostream>
#include <vector>
#include <complex>
#include <cmath>

using namespace std;
using Complex = complex<double>;
using CArray = vector<Complex>;

const double PI = acos(-1);

// FFT 함수 정의
void fft(CArray &x) {
    const size_t N = x.size();
    if (N <= 1) return;

    // 신호를 짝수와 홀수로 분할
    CArray even(N / 2);
    CArray odd(N / 2);
    for (size_t i = 0; i < N / 2; ++i) {
        even[i] = x[i * 2];
        odd[i] = x[i * 2 + 1];
    }

    // 재귀적으로 FFT 수행
    fft(even);
    fft(odd);

    // 결과 합치기
    for (size_t k = 0; k < N / 2; ++k) {
        Complex t = polar(1.0, -2 * PI * k / N) * odd[k];
        x[k] = even[k] + t;
        x[k + N / 2] = even[k] - t;
    }
}

int main() {
    const size_t N = 8;
    CArray data(N);

    // 샘플 데이터 입력
    for (size_t i = 0; i < N; ++i) {
        data[i] = Complex(i, 0);
    }

    // FFT 수행
    fft(data);

    // 결과 출력
    for (size_t i = 0; i < N; ++i) {
        cout << data[i] << endl;
    }

    return 0;
}

 

Complex 자료구조

std::complex<double> z(3.0, 4.0); // 3 + 4i

Complex는 복소수의 실수부분과 허수 부분을 저장하고 연산을 지원하는 클래스

 

Complex t = polar(1.0, -2 * PI * k / N) * odd[k];

위의 의미

• polar 함수는 극좌표를 사용해 복소수를 생성
• 첫번째 인자 1.0은 복소수의 크기(절댓값)을 의미
• 두번째 인자 -2 * PI * k/N 은 복소수의 각도(라디안) 을 의미
• 이 함수는 크기가 1이고 각도가 -2 * PI * k/N  인 복소수를 반환 

이 코드는 홀수 인덱스 배열의 k번째 요소를 특정 각도로 회전 시킨 복소수로 변환하는 작업을 수행

x[k] = even[k] + t;

even[k] 는 짝수 인덱스 배열에 t를 더해서 x[k] 에 저장한다. 이 과정은 짝수 인덱스 요소와 회전된 홀수 인덱스 요소를 합치는 작업

x[k + N / 2] = even[k] - t;

even[k] 에서 t를 빼서 x[k+N/2]에 저장한다. 이 과정은 짝수 인덱스 요소에서 회전된 홀수 인덱스 요소를 빼는 작업이다.

 

즉

FFT알고리즘은 분할정복 방법을 사용해서 입력신호를 홀수인덱스와 짝수 인덱스로 나누고 각각의 부분에 대해 재귀적으로 FFT를 수행후 결과를 합친다.

이 과정에서 회전인자를 사용해 주파수 성분을 조정한다.