FFT (Fast Fourier Transform)

작성 중...

fft를 기저함수의 입장에서 살펴 본다.


어떤 함수 $f$가 두 벡터의 선형 결합으로 표시된다고 하자.

$f=c_1v_1+c_2v_2$

<그림 1>

예를 들면 <그림 1>에서

$f= \begin{bmatrix}
2 \\
3
\end{bmatrix}
=2 \begin{bmatrix}1 \\ 0 \end{bmatrix}+3\begin{bmatrix}0 \\ 1 \end{bmatrix}
=2v_1+3v_2$

이다. 여기서 $v_1$과 $v_2$는 상호 수직이고 크기가 1인 어떤 벡터이다.  함수 $f$와 이 벡터의 내적을 취하면

$<f,v_1>=(c_1v_1+c_2v_2)\cdot v_1=c_1<v_1,v_1>+c_2<v_2,v_1>=c_1$
$<f,v_2>=(c_1v_1+c_2v_2)\cdot v_2=c_1<v_1,v_2>+c_2<v_2,v_2>=c_2$

가 된다. 확인해보면

$<f,v_1>=[2, 3][1, 0]^T=2$
$<f,v_2>=[2, 3][0, 1]^T=3$

이다. 여기서 $v_1$과 $v_2$를 정규직교벡터(orthonormal vector) 또는 정규직교기라고 한다.

연속 함수 $f(t)$를 일정한 간격으로 샘플링을 해서 얻은 데이터의 벡터를 $f=[c_1,c_2,...,c_N]^T$라 하자.  이 벡터는 샘플링된 데이터의 형태로 함수를 표현한다.
만일 샘플 수를 무한히 크게하면 이 벡터는 함수 $f(t)$가 되고 이 추상적인 공간을 함수공간이라고 한다.

이때 함수 벡터를 $N$차원의 공간에서 나타낸다면 하나의 점이 된다.  그리고, 이 고차 공간에서 각 축의 방향을 $v_i$벡터로 표현한다고 하자.

<그림 2>

<그림 2>의 샘플된 함수 값을 정규직교기로 표현해 보자. 함수의 샘플 값이 모두 $N$개라면 정규직교벡터를

$v_1=\begin{bmatrix}1\\0\\0\\ \vdots \\0\\0 \end{bmatrix}$, $v_2=\begin{bmatrix}0\\1\\0\\ \vdots \\0\\0 \end{bmatrix}$, $\cdots$,  $v_N=\begin{bmatrix}0\\0\\0\\ \vdots \\0\\1 \end{bmatrix}$

와 같이 정의한다면

$f=c_1v_1+c_2v_2+\cdots+c_Nv_N$

가 된다. 즉, 정규직교기의 선형 결합으로 샘플된 어떤 함수 값의 표현이 가능하다. 

여기서 $c_i$ 값은 함수 값과 기저벡터 $v_i$의 내적으로 얻을 수 있다.

$c_i=<f,v_i>$

이다. 

$f=[f_1,f_2,\cdots,f_N]^T$라고 하고
$f$의 크기(norm)를 생각해보면

$\lVert f \rVert=\sqrt{{f_1}^2+{f_2}^2+\cdots+{f_N}^2}$

이다. 그런데 sample의 갯수 $N$가 많아지면 $\lVert f \rVert$가 커지므로 갯수에 대해 정규화를 하면

$\lVert f \rVert=\sqrt{{{1}\over{N}}({f_1}^2+{f_2}^2+\cdots+{f_n}^2)}=\sqrt{{1 \over N} \sum_{i} {f_i}^2 }$

이다.   

이를 연속함수로 확장하면

$\lVert f \rVert=\sqrt{{1 \over b-a} \int_{a}^{b} {f(t)}^2 dt}$

이다.




또한 두 vector $f$와 $g$의 내적을 취하면

$<f,g>=f_1g_1+f_2g_2+\cdots+f_Ng_N=\sum_{i} f_ig_i$

이다. 차원 $N$에 좌우되지 않게 하면

$<f,g>={1 \over N} \sum_{i} f_ig_i$

이고, 연속 공간에서 표현하면

$<f,g>={1 \over b-a} \int_{i} f(t)g(t) dt$

이다.








이상에서 살펴본 벡터 공간의 정규직교기를 함수공간으로 도입해 보자.

크기가 1이고 서로 직교하는 함수의 집합(함수족이라 하자)이 있다고 가정하자.
그러면 어떤 함수 값은 함수족 요소의 합으로 표시 가능하다.

다시 말하면 임의의 함수는 미리 성질을 알고 있는 많은 함수 성분으로 분해할 수 있다는 것을 의미한다.

어떤 함수 집합 $\phi_k(t), k=1,2,\cdots$를 생각하자. 함수들의 내적이

$<\phi_{m}(t),\phi_{n}(t)>={1 \over b-a} \int_{a}^{b}\phi_{m}(t) \phi_{n}(t) dt =0, (m \neq n)$

$<\phi_{m}(t),\phi_{m}(t)>={1 \over b-a} \int_{a}^{b}\phi_{m}^2 (t)dt =1, (m = n)$

인 성질을 만족하면 정규직교함수라고 한다.
이를 이용하면 임의의 함수 $f(t)$는

$f(t)=c_0\phi_{0}(t)+c_1\phi_{1}(t)+\cdots=\sum_{k=0}^{\infty} c_k\phi_{k}(t)$

이다.  각 계수 값의 결정은

$<f(t),\phi_k (t)>=(c_0\phi_{0}(t)+c_1\phi_{1}(t)+\cdots)\cdot \phi_k (t)$
$=c_0<\phi_{0}(t),\phi_k (t)>+c_1<\phi_{1}(t),\phi_k (t)>+\cdots$
$=c_k<\phi_k,\phi_k>=c_k$

이다. 따라서,

$c_k=<f(t),\phi_k (t)>={1 \over b-a}\int_{a}^{b} f(t) \phi_k (t) dt$

이다.









(예) 함수계 $\{1, \sin t, \sin 2t, \cdots \}$가 $-\pi \sim \pi$ 구간에서 직교함수계인지 확인하시오.

$<1,\sin nt>={1 \over {2\pi}}\int_{-\pi}^{\pi} \sin nt dt =-{1 \over {2n\pi}}[\cos nt ]_{-\pi}^{\pi}=0$

$<\sin mt,\sin nt>={1 \over {2\pi}}\int_{-\pi}^{\pi} \sin mt \sin nt dt
=-{1 \over {2\pi}} \int_{-\pi}^{\pi} {1 \over 2} (\cos (m+n)t-\cos (m-n)t) dt$
$=-{1 \over {4\pi (m+n)}} [\sin (m+n)t ]_{-\pi}^{\pi}+{1 \over {4\pi (m-n)}}[\sin (m-n)t ]_{-\pi}^{\pi}=0$

$<\sin nt, \sin nt>={1 \over 2\pi} \int_{-\pi}^{\pi} \sin^2 nt dt
={1 \over 2\pi} \int_{-\pi}^{\pi} {1 \over 2}(1-\cos 2nt) dt$
$={1 \over 4\pi}[t]_{-\pi}^{\pi} -{1 \over {4\pi 2n}}[\sin 2nt]_{-\pi}^{\pi}={1 \over 2}, (n=1, 2, 3, \cdots)$


위 함수계는 직교는 맞는데 정규는 아니므로 (즉, 동일 함수의 내적이 ${1 \over 2}$이므로) 각 함수에 $\sqrt 2$를 곱해 준다.

따라서

$\{1, \sqrt 2 \sin t, \sqrt 2 \sin 2t, \cdots \}$

가 정규직교 함수계가 된다.



$\circ$ 예제에서 삼각함수의 반각의 공식이 사용되었다:

$\sin^2 {\alpha \over 2}={ {1-\cos \alpha} \over 2}$

$\cos^2 {\alpha \over 2}={ {1+\cos \alpha} \over 2}$