[신호및시스템] Phase 3-3 - Fast Fourier Transform

Fast Fourier Transform

앞서 확인한 DFT Matrix 를 이용해 연산을 처리하면 반복되는 연산을 미리 끝내두고, 병렬 연산의 적용이 가능해 연산 처리 효율이 높일 수 있기는 하지만, 여전히 $O(n^2)$ 의 연산량을 가진다. 혹시 중복되는 계산이나 계산 결과를 재사용할 수 있는 부분이 있을지에 대해 고민한 결과, Fast Fourier Transform (이하 FTT) 에 대한 컨셉이 나오게 되었다.

ㅤ

$N=4$ 인 상황을 다시 가져와 생각해보자.

$$
\left[
\begin{matrix}
X_0\\ X_1\\X_2\\X_3
\end{matrix}
\right] = \left[
\begin{matrix}
1&1&1&1\\
1&-j&-1&j\\
1&-1&1&-1\\
1&j&-1&-j
\end{matrix}
\right]\cdot \left[
\begin{matrix}
x[0]\\ x[1]\\x[2]\\x[3]
\end{matrix}
\right]
$$

ㅤ

요녀석을 수식으로 각각 풀어보면 이렇게 정리할 수 있다. 여기에서 홀수항과 짝수항을 분리해서 묶어주자. 묶는 기준은 복소항의 포함 여부이다.

ㅤ

요걸 다시 묶어보면 이렇게 예쁘게 묶이는 것을 볼 수 있다. 여기에서 잘 보면 중복되는 부분들이 눈에 들어오기 시작한다.

ㅤ

왼쪽 항에서는 위아래 2개가 중복으로 동일하게 등장하고, 오른쪽 항에서는 전체적으로 -1 이 곱해진 여부를 제외하면 중복해서 동일한 형태가 등장한다.

ㅤ

여기에서 한 번 더 중복을 찾아내주자. 오른쪽 복소수에서, 패턴을 찾을 수 있다. 해당 값들은 G, H, W 라는 배열로 미리 계산을 완료해두면 두 번 계산하지 않아도 되므로 효율적이다.

ㅤ

이렇게 반복 패턴을 활용해서 다시 수식을 작성해보면 아래처럼 정리할 수 있다.

ㅤ

기존 방식에서라면 곱셈 16번에 덧셈 12번이나 해야했는데, 개선된 방식에서는 덧셈 8번에 곱셈 2번이면 연산을 완료할 수 있다. 이렇게 큰 틀에서 등분해가면서 패턴을 찾고 미리 연산을 끝내두는 방식으로 Divide and Conquer 를 적용하면 훨씬 효율적으로 연산할 수 있다.

ㅤ

이론적으로는 기존에는 $O(n^2)$ 만큼 걸리던 시간복잡도를 $O(n\cdot \log{n})$ 까지 줄일 수 있다!! 와우!!!

ㅤ

차량용 임베디드에서 연산을 수행해야 하는 상황일 때, 1ms 마다 1024 개의 신호에 대해서 연산을 수행해야 한다고 가정해보자. 기존 방식에서는 1,048,576 회의 복소수 곱셈을 수행해야하고, 100MHz 단위로 100ms 가 소요된다. 그러나 FFT를 적용하면 10,240 회의 복소수 곱셈만 수행하면 되기에 100MHz 환경에서 1ms 만에 처리할 수 있다. 이렇게 보니깐 차이가 진짜 크네!

 

샤라웃

혁펜하임의 “퍼펙트” 신호 및 시스템 (Signals & Systems)

혁펜하임의 “퍼펙트” 신호 및 시스템 (Signals & Systems)