【信号処理】離散フーリエ級数：DFS, Discrete Fourier Series
今回は，周期信号に対する複素フーリエ級数展開（三角多項式）を離散化しよう．
これで，離散フーリエ級数（DFS: Discrete Fourier Series）を得られる．
復習：複素フーリエ級数展開（三角多項式）
信号 $${x(t)}$$ に対して，周期性
$$
x(t) = x(t+T)
$$
を課したとき，複素フーリエ級数展開（三角多項式）は以下のように表せる：
$$
x(t) = \sum_{n = - \infty}^{\infty} c_{n} \exp{(jn\omega_{0}t)}
$$
ここで， $${\omega_{0} = 2 \pi / T}$$ は基本角振動数，係数 $${c_{n}}$$ は線スペクトルと呼ばれ，
$$
c_{n} = \braket{x(t) \exp{(-jn \omega_{0}t)}}_{T}
$$
である．
復習：信号の離散化
ディラックのデルタ関数を用いた，以下のサンプリング操作を定義する：
$$
\delta_{s}(t, \tau) = \sum_{n=-\infty}^{\infty} \delta(t-n\tau)
$$
これを信号 $${x(t)}$$ に畳み込むと，離散化された信号の表現を得る：
$$
\int_{-\infty}^{\infty}\delta_{s}(t, \tau) x(t) = \sum_{n = - \infty}^{\infty} x(n\tau)
$$
この離散化の操作を周期信号と，無限長信号 $${x(t)}$$ における議論に適用しよう．
離散フーリエ級数（DFS: Discrete Fourier Series）
まず，周期信号 $${x(t) = x(t+T)}$$ に関する離散化を行う．
周期 $${T}$$ を ${N}$ 分割しよう：
$$
T = \sum_{n=0}^{N-1} T / N = \sum_{n=0}^{N-1} \tau = N \tau
$$
このサンプリング周期 $${\tau}$$ を用いて，離散化された信号を考える．
各離散化された信号 $${{x[n] \equiv x(n\tau)}}$$ を複素フーリエ展開しておくと，
$$
x[n] = \sum_{k = -\infty}^{\infty} c_{k} \exp{(j k \omega_{0} n \tau)}
$$
$${\tau = T / N }$$ および， $${ \omega_{0} = 2 \pi / T }$$ より，
$$
x[n] = \sum_{k = -\infty}^{\infty} c_{k} \exp{\left( j k \frac{2\pi}{N} n \right)}
$$
$${k = m + rN}$$ のように分解しよう．
$${m=0,1,\cdots,N-1, }$$
かつ
$${r = 0, \pm 1, \pm 2, \cdots, \pm \infty}$$ とする．
$$
\begin{equation*}
\begin{split}
x[n]
&= \sum_{r = -\infty}^{\infty} \sum_{m = 0}^{N-1} c_{m + rN} \exp{\left( j m \frac{2\pi}{N} n \right)} \exp{\left( j 2 \pi n r \right)} \\
&= \sum_{m = 0}^{N-1} \exp{\left( j m \frac{2\pi}{N} n \right)} \sum_{r = -\infty}^{\infty} c_{m + rN}
\end{split}
\end{equation*}
$$
さらに，複素フーリエ係数について離散化された形にすれば，
$$
\begin{equation*}
\begin{split}
\sum_{r = -\infty}^{\infty} c_{m+rN} &\equiv \frac{1}{N} \sum_{n = 0}^{N-1} x[n] \sum_{r = -\infty}^{\infty} \exp{\left(-j (m+rN) \frac{2 \pi}{N}n \right)} \\
&= \frac{1}{N}\sum_{n = 0}^{N-1} x[n] \exp{\left(-j m \frac{2 \pi}{N}n \right)} \prod_{r= -\infty}^{\infty} \exp{\left(j r 2 \pi n \right)} \\
&= c_{m}
\end{split}
\end{equation*}
$$
したがって，離散フーリエ展開級数の公式を得る：
$$
x[n] = \sum_{m=0}^{N-1} c_{m} \exp{\left(- j 2\pi \frac{m}{N} n \right)}
$$
ここで，展開係数は，
$$
c_{m} = \frac{1}{N}\sum_{n = 0}^{N-1} x[n] \exp{\left(-j 2 \pi \frac{m}{N}n \right)}
$$
サンプリングされた信号からDFSを得るには？
サンプリングされた信号 $${x[0], x[1], \cdots, x[n-1]}$$ から，どのようにして，その DFS を得られるでしょうか？
愚直な方法（時によくない）
$$
c_{m} = \frac{1}{N}\sum_{n = 0}^{N-1} x[n] \exp{\left(-j 2 \pi \frac{m}{N}n \right)}
$$
を用いると，以下の連立１次方程式を解けばいいことがわかります：
$$
c_{m} = A_{mn} x[n] , \text{where } m,n = 0,1,2, \cdots, N-1
$$
行列 $${A_{mn}}$$ の成分は，
$$
A_{mn} = \frac{1}{N} \exp{\left(-j 2 \pi \frac{m}{N}n \right)}
$$
であるが，この方法は適切ではない．
理由は，$${|\exp{\left(j 2 \pi \frac{m}{N}n \right)}| = 1}$$ に対して，
$${N \gg 1}$$であるから，全ての$${A_{mn} \ll 1}$$となり，
この方法では，多くの場合で，桁落ちなど誤差によって，これは計算できない．
そこで，
サンプリング信号を$${x[n]/N}$$とリスケーリングして扱うか，
先に行列の計算をした後に，$${1/N}$$を行うのが良いだろう．
逆行列を利用する方法
DFS
$$
x[n] = \sum_{m=0}^{N-1} c_{m} \exp{\left( j 2\pi \frac{m}{N} n \right)}
$$
を利用して，
$$
c_{m} = B^{-1}_{mn} x[n]
$$
という計算方法が適切である．
ここで，
$$
B_{mn} = \exp{\left( j 2\pi \frac{m}{N} n \right)}
$$
実装する上では，計算量に注意が必要である．
逆行列を求めることと，
行列とベクトルの計算に関するアルゴリズムは，
計算量が $${ \mathscr{O}(N^2) }$$ となっているので，
サンプリングされたデータが大きくなると，これでは扱えない．
ちなみに，先に示した方法でも同じ計算量である．
まとめ：DFSの公式
DFSは以下の公式で得られることがわかった：
