FFT(고속 푸리에 변환 알고리즘) 알고리즘을 보기전에 DFT(이산 푸리에 변환)을 간단히 알아보자.

DFT(Discrete Fourier transform)은 무엇인가??

DFT 식

FFT (Fast Fourier Transform) Algorithm이란 무엇인가??

FFT algorithm의 동작 방식

- Cooley-Tukey Algorithm

FFT algorithm의 성능 분석

- big-O notation(빅오 표기법) 이란??

- FFT Algorithm의 성능

FFT algorithm code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import numpy as np


def fft(x):
    N = len(x) # 파라미터 리스트의 길이

    even = fft(x[0::2]) # 짝수 항 0부터 2간격
    odd = fft(x[1::2]) # 홀수 항 1부터 2간격
    T = [np.exp(-2j*np.pi*k/N)*odd[k] for k in range(N//2)] # 홀수항과 회전인자 곱

    # 합치기
    return [even[k] + T[k] for k in range(N//2)] + \
           [even[k] - T[k] for k in range(N//2)]

x(t) = 3cos(20πt) + 6sin(30πt - 3/(4π)) (0 <= t <= 1)의 FFT 그래프

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
import numpy as np
from matplotlib import pyplot as plt
from pylab import rcParams

rcParams['figure.figsize'] = 11, 10  # 그래프를 나타낼 창의 크기 설정


def fft(x):
    # FFT 사용자 함수 정의
    N_len = len(x)  # 파라미터 리스트의 길이

    if N_len <= 1:
        return x
    even = fft(x[0::2])  # 짝수 항 0부터 2간격
    odd = fft(x[1::2])  # 홀수 항 1부터 2간격
    T = [np.exp(-2j*np.pi*k/N_len)*odd[k]
         for k in range(N_len//2)]  # 홀수 항과 회전인자의 곱

    # 합치기
    T_sum = [even[k] + T[k] for k in range(N_len//2)] + \
            [even[k] - T[k] for k in range(N_len//2)]
    return T_sum


fs = 512    # 샘플링 주파수
dt = 1/fs   # 샘플링 주기
N = 512     # 데이터 길이

t = np.arange(0, 1, 1/fs)  # 0 <= t <= 1, step

# 입력 신호
r = 3 * np.cos(2 * np.pi * 10 * t) + 6 * \
    np.sin(2 * np.pi * (15 * t - 3/8*pow(np.pi, 2)))

x_list = list(r)    # 입력신호 type list로 변경
x_fft = fft(x_list)  # 입력신호 FFT함수에 입력

# 변환된 그래프가 그려질 주파수 범위 설정
f = np.arange(0, N)

# Original Signal 그래프 나타내기
plt.subplot(211)
plt.title('Original Signal x(t)')  # title of graph
plt.xlabel('time')  # x축 label
plt.plot(t, r)

# 변환된 그래프 나타내기
plt.subplot(212)
plt.title('Fast Fourier Transform Graph X(f)')  # title of graph
plt.xlabel('frequency')  # x축 label
plt.plot(f[0: int(N//20)], x_fft[0:int(N//20)])
plt.savefig('./img/fast_fourier.png')  # 사진으로 저장하기
plt.show()

정리

FFT(고속 푸리에 변환)에 대해 알아보았다. DFT(이산 푸리에 변환)과 FFT(고속 푸리에 변환)을 비교해 보며 시간 복잡도가 큰 역할을 한다는 것을 알게 되었다.

실제로 푸리에 변환을 사용하게 된다면 방대한 데이터를 다룰 것이기 때문에 고속 푸리에 변환은 중요하다고 생각한다. 예를들어 푸리에 변환은 푸리에 급수와 다르게 비주기 함수도 변환이 가능하다는 장점을 이용해 창업자가 가게를 내고 싶은 지역의 유동인구를 그래프화 한 다음 푸리에 변환을 통해 유동인구가 많은 시간이나 연령대를 알기 쉬울것 같다고 생각한다.

항상 어렵다고 생각했던 것들이 우리에게 많은 도움을 주고, 다양한 형태로 사용될 수 있다고 느꼈다.

FFT(Fast Fourier Transform) Algorithm

DFT(Discrete Fourier transform)은 무엇인가??

DFT 식