実離散フーリエ変換(後編)-実離散フーリエ変換の証明-

実離散フーリエ変換

フーリエ級数展開と実離散フーリエ変換の対応

実離散フーリエ変換の$x$を$f$、${\displaystyle \frac{n}{N}}$を$x$に置き換えて$N\to \mathrm{\infty }$の極限をとると、区分求積法より

$$\begin{array}{rl}f(x)& =\sum _{m=0}^{\mathrm{\infty }}{a}_m\cos \left(m\tau x\right)+\sum _{m=0}^{\mathrm{\infty }}{b}_m\sin \left(m\tau x\right)\end{array}$$

$$\begin{array}{rl}{a}_m& =\{\begin{array}{ll}{\displaystyle {\int }_0^{1}f(n)\cos \left(m\tau x\right)dx}& (m=0)\\ {\displaystyle 2{\int }_0^{1}f(n)\cos \left(m\tau x\right)dx}& (m>0)\end{array}\\ b_m& =2{\displaystyle {\int }_0^{1}f(n)\sin \left(m\tau x\right)dx}\end{array}$$

変形すると
$$\begin{array}{rl}f(x)& ={\displaystyle \frac{a_0}{2}}+\sum _{m=0}^{\mathrm{\infty }}{a}_m\cos \left(m\tau x\right)+\sum _{m=0}^{\mathrm{\infty }}{b}_m\sin \left(m\tau x\right)(+{\displaystyle \frac{a_{\mathrm{\infty }}}{2}})\end{array}$$
$$\begin{array}{rl}{a}_m& =2{\int }_0^{1}f(n)\cos \left(m\tau x\right)dx\\ b_m& =2{\int }_0^{1}f(n)\sin \left(m\tau x\right)dx\end{array}$$
よって(このページで示した)実離散フーリエ変換は$N\to \mathrm{\infty }$の極限で周期$\tau$のフーリエ級数展開に対応する。

実離散フーリエ変換と複素離散フーリエ変換の関係

実離散フーリエ変換の書き換え

実離散フーリエ変換は次のように書き換えられる。
$$\begin{array}{rl}f(n)& =\{\begin{array}{ll}{\displaystyle \frac{a_0}{2}}+g_{(N-1)/2}(n)& (N=2k-1,k\in \mathbb{N})\\ \\ {\displaystyle \frac{a_0+(-1{)}^n{a}_{N/2}}{2}}+g_{N/2-1}(n)& (N=2k,k\in \mathbb{N})\end{array}\end{array}$$
ただし
$$\begin{array}{rl}{g}_M(n)& =\sum _{m=1}^M(a_m\cos \left({\displaystyle \frac{m}{N}}n\tau \right)+b_m\sin \left({\displaystyle \frac{m}{N}}n\tau \right))\\ a_m& ={\displaystyle \frac{2}{N}}\sum _{n=0}^{N-1}f(n)\cos \left({\displaystyle \frac{m}{N}}n\tau \right)\\ b_m& ={\displaystyle \frac{2}{N}}\sum _{n=0}^{N-1}f(n)\sin \left({\displaystyle \frac{m}{N}}n\tau \right)\end{array}$$

オイラーの公式による変形

$\exp \left(i\theta \right)=\cos \left(\theta \right)+i\sin \left(\theta \right)$より

$\cos \left(\theta \right)={\displaystyle \frac{\exp \left(i\theta \right)+\exp (-i\theta )}{2}},\sin \left(\theta \right)={\displaystyle \frac{\exp \left(i\theta \right)-\exp (-i\theta )}{2i}}$

実離散フーリエ変換に対して、${\theta }_m={\displaystyle \frac{m}{N}}n\tau$として三角関数を複素指数関数に書き直す。

$g_M(n)$の変形

$$\begin{array}{rl}{g}_M(n)& =\sum _{m=1}^M(a_m{\displaystyle \frac{\exp \left(i{\theta }_m\right)+\exp (-i{\theta }_m)}{2}}+b_m{\displaystyle \frac{\exp \left(i{\theta }_m\right)-\exp (-i{\theta }_m)}{2i}})\\ & =\sum _{m=1}^M(a_m{\displaystyle \frac{\exp \left(i{\theta }_m\right)+\exp (-i{\theta }_m)}{2}}-b_m{\displaystyle \frac{i\exp \left(i{\theta }_m\right)-i\exp (-i{\theta }_m)}{2}})\\ & =\sum _{m=1}^M({\displaystyle \frac{a_m-i{b}_m}{2}}\exp \left(i{\theta }_m\right)+{\displaystyle \frac{a_m+i{b}_m}{2}}\exp (-i{\theta }_m))\end{array}$$

$a_m,b_m$の変形

$$\begin{array}{rl}{a}_m& ={\displaystyle \frac{2}{N}}\sum _{n=0}^{N-1}f(n)\cos \left({\displaystyle \frac{m}{N}}n\tau \right)\\ & ={\displaystyle \frac{2}{N}}\sum _{n=0}^{N-1}f(n){\displaystyle \frac{\exp \left(i{\theta }_m\right)+\exp (-i{\theta }_m)}{2}}\\ b_m& ={\displaystyle \frac{2}{N}}\sum _{n=0}^{N-1}f(n)\sin \left({\displaystyle \frac{m}{N}}n\tau \right)\\ & ={\displaystyle \frac{2}{N}}\sum _{n=0}^{N-1}f(n){\displaystyle \frac{\exp \left(i{\theta }_m\right)-\exp (-i{\theta }_m)}{2i}}\\ & ={\displaystyle \frac{2}{N}}\sum _{n=0}^{N-1}f(n){\displaystyle \frac{-i\exp \left(i{\theta }_m\right)+i\exp (-i{\theta }_m)}{2}}\end{array}$$

${\displaystyle \frac{a_m\pm i{b}_m}{2}}$の変形

$$\begin{gathered} \begin{array}{rl}{\displaystyle \frac{a_m+i{b}_m}{2}}& ={\displaystyle \frac{1}{N}}\sum _{n=0}^{N-1}f(n)({\displaystyle \frac{\exp \left(i{\theta }_m\right)+\exp (-i{\theta }_m)}{2}}+{\displaystyle \frac{\exp \left(i{\theta }_m\right)-\exp (-i{\theta }_m)}{2}} \\ )\\ & ={\displaystyle \frac{1}{N}}\sum _{n=0}^{N-1}f(n)\exp \left(i{\theta }_m\right)\\ {\displaystyle \frac{a_m-i{b}_m}{2}}& ={\displaystyle \frac{1}{N}}\sum _{n=0}^{N-1}f(n)({\displaystyle \frac{\exp \left(i{\theta }_m\right)+\exp (-i{\theta }_m)}{2}}-{\displaystyle \frac{\exp \left(i{\theta }_m\right)-\exp (-i{\theta }_m)}{2}} \\ )\\ & ={\displaystyle \frac{1}{N}}\sum _{n=0}^{N-1}f(n)\exp (-i{\theta }_m)\end{array} \end{gathered}$$

ここで、$h(m)={\displaystyle \frac{a_m+i{b}_m}{2}}$とすると

${\theta }_{-m}=-{\displaystyle \frac{m}{N}}n\tau =-{\theta }_m$より

$$\begin{array}{rl}h(-m)& ={\displaystyle \frac{1}{N}}\sum _{n=0}^{N-1}f(n)\exp \left(i{\theta }_{-m}\right)\\ & ={\displaystyle \frac{1}{N}}\sum _{n=0}^{N-1}f(n)\exp (-i{\theta }_m)\\ & ={\displaystyle \frac{a_m-i{b}_m}{2}}\end{array}$$

よって
$$\begin{array}{rl}{g}_M(n)& =\sum _{m=0}^M({\displaystyle \frac{a_m-i{b}_m}{2}}\exp \left(i{\theta }_m\right)+{\displaystyle \frac{a_m+i{b}_m}{2}}\exp \left(i{\theta }_m\right))\\ & =\sum _{m=0}^M(h(-m)\exp \left(i{\theta }_m\right)+h(m)\exp (-i{\theta }_m))\end{array}$$

$g_M(n)$の変数変換

$g_M(n)$の$h(m)\exp (-i{\theta }_m)$に対して$m=N-k$つまり$k=N-m$とすると、
$m:1\to M$に対して$k:N-M\to N-1$となるから

$$\begin{array}{rl}{g}_M(n)& =\sum _{m=1}^{M}h(-m)\exp \left(i{\theta }_m\right)+\sum _{m=1}^{M}h(m)\exp (-i{\theta }_m)\\ & =\sum _{m=1}^{M}h(-m)\exp \left(i{\theta }_m\right)+\sum _{m=N-M}^{N-1}h(N-k)\exp (-i{\theta }_{N-k})\end{array}$$

ここで、
$$\begin{array}{rl}\exp \left(i{\theta }_{N-m}\right)& =\exp \left(i{\displaystyle \frac{N-m}{N}}n\tau \right)\\ & =\exp (in\tau -i{\displaystyle \frac{m}{N}}n\tau )\\ & =\exp \left(in\tau \right)\exp (-i{\displaystyle \frac{m}{N}}n\tau )\\ & =\exp (-i{\theta }_m)\end{array}$$

同様にして$\exp (-i{\theta }_{N-m})=\exp \left(i{\theta }_m\right)$となる。また、
$$\begin{array}{rl}h(N-m)& ={\displaystyle \frac{1}{N}}\sum _{n=0}^{N-1}f(n)\exp \left(i{\theta }_{N-m}\right)\\ & ={\displaystyle \frac{1}{N}}\sum _{n=0}^{N-1}f(n)\exp (-i{\theta }_m)\\ & =h(-m)\end{array}$$

よって$g_M(n)$は次のように書き換えられる。
$$\begin{array}{rl}{g}_M(n)& =\sum _{m=1}^{M}h(-m)\exp \left(i{\theta }_m\right)+\sum _{m=N-M}^{N-1}h(N-k)\exp (-i{\theta }_{N-k})\\ & =\sum _{m=1}^{M}h(-m)\exp \left(i{\theta }_m\right)+\sum _{m=N-M}^{N-1}h(-m)\exp \left(i{\theta }_m\right)\end{array}$$

$M=0$の場合

$$\begin{array}{rl}{a}_0& ={\displaystyle \frac{2}{N}}\sum _{n=0}^{N-1}f(n)\cos \left({\displaystyle \frac{0}{N}}n\tau \right)\\ & ={\displaystyle \frac{2}{N}}\sum _{n=0}^{N-1}f(n)\\ h(0)& ={\displaystyle \frac{1}{N}}\sum _{n=0}^{N-1}f(n)\exp \left(i{\theta }_0\right)\\ & ={\displaystyle \frac{1}{2}}{\displaystyle \frac{2}{N}}\sum _{n=0}^{N-1}f(n)\\ & ={\displaystyle \frac{a_0}{2}}\\ \exp \left(i{\theta }_0\right)& =\exp \left(i{\displaystyle \frac{0}{N}}n\tau \right)=1\end{array}$$
よって
$$\begin{array}{r}{\displaystyle \frac{a_0}{2}}=h(0)\exp \left(i{\theta }_0\right)\end{array}$$

$N$の偶奇による場合分け

$N$が奇数の時

$$\begin{array}{rl}f(n)& ={\displaystyle \frac{a_0}{2}}+g_{(N-1)/2}(n)\\ & =h(0)\exp \left(i{\theta }_0\right)+\sum _{m=1}^{(N-1)/2}h(-m)\exp \left(i{\theta }_m\right)+\sum _{m=N-(N-1)/2}^{N-1}h(-m)\exp \left(i{\theta }_m\right)\\ & =\sum _{m=0}^{(N-1)/2}h(-m)\exp \left(i{\theta }_m\right)+\sum _{m=(N-1)/2+1}^{N-1}h(-m)\exp \left(i{\theta }_m\right)\\ & =\sum _{m=0}^{N-1}h(-m)\exp \left(i{\theta }_m\right)\end{array}$$

$N$が偶数の時

$$\begin{array}{rl}{a}_{N/2}& ={\displaystyle \frac{2}{N}}\sum _{n=0}^{N-1}f(n)\cos \left({\displaystyle \frac{1}{2}}n\tau \right)\\ \\ h(N/2)& ={\displaystyle \frac{1}{N}}\sum _{n=0}^{N-1}f(n)\exp \left(i{\displaystyle \frac{1}{2}}n\tau \right)\\ & ={\displaystyle \frac{1}{2}}{\displaystyle \frac{2}{N}}\sum _{n=0}^{N-1}f(n)\cos \left({\displaystyle \frac{1}{2}}n\tau \right)\\ & ={\displaystyle \frac{a_{N/2}}{2}}\\ \exp \left(i{\theta }_{N/2}\right)& =\exp \left(i{\displaystyle \frac{1}{2}}n\tau \right)=(-1{)}^n\end{array}$$
よって
$$\begin{array}{rl}f(n)& ={\displaystyle \frac{a_0+(-1{)}^n{a}_{N/2}}{2}}+g_{N/2-1}(n)\\ & ={\displaystyle \frac{a_0}{2}}+g_{N/2-1}(n)+{\displaystyle \frac{a_{N/2}}{2}}(-1{)}^n\\ & =h(0)\exp \left(i{\theta }_0\right)+\sum _{m=1}^{N/2-1}h(-m)\exp \left(i{\theta }_m\right)+\sum _{m=N-(N/2-1)}^{N-1}h(-m)\exp \left(i{\theta }_m\right)\\ & =\sum _{m=0}^{N/2-1}h(-m)\exp \left(i{\theta }_m\right)+\sum _{m=N/2+1}^{N-1}h(-m)\exp \left(i{\theta }_m\right)\\ & =\sum _{m=0}^{N-1}h(-m)\exp \left(i{\theta }_m\right)\end{array}$$

結論

これらのことから、実離散フーリエ変換は$N$の偶奇によらず次のように変形できる。

$$\begin{array}{rl}f(n)& =\sum _{m=0}^{N-1}h(-m)\exp \left(i{\displaystyle \frac{m}{N}}n\tau \right)\\ h(-m)& ={\displaystyle \frac{1}{N}}\sum _{n=0}^{N-1}f(n)\exp (-i{\displaystyle \frac{m}{N}}n\tau )\end{array}$$

つまり
$$\begin{array}{rl}f(n)& =\sum _{m=0}^{N-1}(({\displaystyle \frac{1}{N}}\sum _{n=0}^{N-1}f(n)\exp (-i{\displaystyle \frac{m}{N}}n\tau ))\exp \left(i{\displaystyle \frac{m}{N}}n\tau \right))\\ & ={\displaystyle \frac{1}{N}}\sum _{m=0}^{N-1}(\sum _{n=0}^{N-1}f(n)\exp (-i{\displaystyle \frac{m}{N}}n\tau ))\exp \left(i{\displaystyle \frac{m}{N}}n\tau \right)\end{array}$$
ここで、
$$\begin{array}{r}F(m)=\sum _{n=0}^{N-1}f(n)\exp (-i{\displaystyle \frac{m}{N}}n\tau )\end{array}$$
とおけば、
$$\begin{array}{rl}f(n)& ={\displaystyle \frac{1}{N}}\sum _{m=0}^{N-1}F(m)\exp \left(i{\displaystyle \frac{m}{N}}n\tau \right)\end{array}$$
より、複素離散フーリエ変換と完全に一致する。