yProcessingClub

すみません、許してください

離散フーリエ変換 式展開メモ

離散フーリエ変換(DFT)のメモ。
合ってるかは知りません。

離散フーリエ変換は以下の通り。
 F\left[ k \right] \displaystyle = \sum_{n=0}^{N-1} f(n)e^{{-j}\frac{2 \pi kn}{N}},\ \ \ \ k = 1,2,\ldots,N-1 \ \ \cdots \ (*)

これをベクトル表現すると以下の通り。
 \bf{F} \rm{=} \bf{W}_{\rm{DFT}}f

要素であらわすと、

\begin{pmatrix} F\left[ 0 \right] \\ F\left[ 1 \right] \\ \vdots \\ F\left[ N-1 \right]  \end{pmatrix}
= 
\begin{pmatrix} 
W^{0}_{N} & W^{0}_{N} &W^{0}_{N} & \ldots & W^{0}_{N} \\
W^{0}_{N} & W^{1}_{N} & W^{2}_{N} & \ldots & W^{N-1}_{N} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
W^{0}_{N} & W^{N-1}_{N} & W^{(N-1)2}_{N} & \ldots & W^{(N-1)(N-1)}_{N}
\end{pmatrix}
\begin{pmatrix} f\left( 0 \right) \\ f\left( 1 \right) \\ \vdots \\ f\left( N-1 \right)\end{pmatrix}
\ \ \cdots \ (**)

 W_{N} = e^{{-j}\frac{2 \pi}{N}}

となる。



以下、具体的に計算して(*)(**)が行えるかを確認する。





N = 2の場合

F\left[ k \right] \displaystyle = \sum_{n=0}^{1} f(n)e^{{-j}\frac{2 \pi kn}{2}}

k = 0, 1の場合をそれぞれ計算すると、

F\left[ 0 \right] \displaystyle = \sum_{n=0}^{1} f(n) = f(0) + f(1)\\
F\left[ 1 \right] \displaystyle = \sum_{n=0}^{1} f(n)e^{{-j}\frac{2 \pi n}{2}}= f(0) + f(1)e^{-j\pi}\\

行列でまとめると、

\begin{pmatrix} F\left[ 0 \right] \\ F\left[ 1 \right]\end{pmatrix}
= 
\begin{pmatrix} 
1 & 1 \\
1 & e^{-j\pi} \\
\end{pmatrix}
\begin{pmatrix} f\left( 0 \right) \\ f\left( 1 \right) \end{pmatrix}

ここで  W_{N} = e^{{-j}\frac{2 \pi}{N}} より、
 W_{2} = e^{{-j}\frac{2 \pi}{2}} = e^{-j \pi}
よって、
 W^{0}_{2} =  \left( e^{-j \pi} \right) ^{0} = 1
 W^{1}_{2} = \left( e^{-j \pi} \right) ^{1} = e^{-j \pi}

よって、

\begin{pmatrix} F\left[ 0 \right] \\ F\left[ 1 \right]\end{pmatrix}
= 
\begin{pmatrix} 
W^{0}_{2} & W^{0}_{2} \\
W^{0}_{2} & W^{1}_{2} \\
\end{pmatrix}
\begin{pmatrix} f\left( 0 \right) \\ f\left( 1 \right) \end{pmatrix}

となり、(*)(**)となった。



N = 3の場合

F\left[ k \right] \displaystyle = \sum_{n=0}^{2} f(n)e^{{-j}\frac{2 \pi kn}{3}}

k = 0, 1, 2の場合をそれぞれ計算すると、

F\left[ 0 \right] \displaystyle = \sum_{n=0}^{2} f(n) = f(0) + f(1) + f(2)\\
F\left[ 1 \right] \displaystyle = \sum_{n=0}^{2} f(n)e^{{-j}\frac{2 \pi n}{3}}
= f(0) + f(1)e^{-j \frac{2 \pi}{3}}+ f(2)e^{-j \frac{4 \pi}{3}}\\
F\left[ 2 \right] \displaystyle = \sum_{n=0}^{2} f(n)e^{{-j}\frac{4 \pi n}{3}}
= f(0) + f(1)e^{-j \frac{4 \pi}{3}}+ f(2)e^{-j \frac{8 \pi}{3}}\\
行列でまとめると、

\begin{pmatrix} F\left[ 0 \right] \\ F\left[ 1 \right] \\ F\left[ 2 \right] \end{pmatrix}
= 
\begin{pmatrix} 
1 & 1 & 1\\
1 & e^{-j \frac{2 \pi}{3}} & e^{{-j}\frac{4 \pi}{3}} \\
1 & e^{-j \frac{4 \pi}{3}} & e^{-j \frac{8 \pi}{3}}\\

\end{pmatrix}
\begin{pmatrix} f\left( 0 \right) \\ f\left( 1 \right) \\ f\left( 2 \right) \end{pmatrix}


ここで、 W_{3} = e^{{-j}\frac{2 \pi}{3}}より、
よって、
 W^{0}_{3} =  \left( e^{{-j}\frac{2 \pi}{3}} \right) ^{0} = 1
 W^{1}_{3} = \left( e^{{-j}\frac{2 \pi}{3}} \right) ^{1} = e^{{-j}\frac{2 \pi}{3}}
 W^{2}_{3} = \left( e^{{-j}\frac{2 \pi}{3}} \right) ^{2} = e^{{-j}\frac{4 \pi}{3}}
 W^{4}_{3} = \left( e^{{-j}\frac{2 \pi}{3}} \right) ^{4} = e^{{-j}\frac{8 \pi}{3}}


よって、

\begin{pmatrix} F\left[ 0 \right] \\ F\left[ 1 \right] \\ F\left[ 2 \right] \end{pmatrix}
= 
\begin{pmatrix} 
W^{0}_{3} & W^{0}_{3} & W^{0}_{3}\\
W^{0}_{3} & W^{1}_{3} & W^{2}_{3}\\
W^{0}_{3} & W^{2}_{3} & W^{4}_{3}\\

\end{pmatrix}
\begin{pmatrix} f\left( 0 \right) \\ f\left( 1 \right) \\ f\left( 2 \right) \end{pmatrix}

となり、(*)(**)となった。