実離散フーリエ変換(後編)-実離散フーリエ変換の証明-
前編：
実離散フーリエ変換(前編)-基底変換-
中編：
実離散フーリエ変換(中編)-離散三角関数の直交性-
後編：ここ
実離散フーリエ変換
$N\in \mathbb{N},\ \tau=2\pi,\ n \in \mathbb{Z}\ (0 \leq n < N)$に対して、実$N$次数ベクトル$\mathbf{f}=\begin{bmatrix} f(0)\\ f(1)\\ \vdots \\ f(N-1) \end{bmatrix} \in \mathbb{R}^N$は離散三角関数によって次のように展開できる。
\begin{align}
f(n)
&=\begin{cases} \dfrac{a_0}{2} + \displaystyle{
\sum_{m=1}^{(N-1)/2}\left( a_m\cos(\dfrac{m}{N}n\tau)
+ b_m\sin(\dfrac{m}{N}n\tau)
\right)}
\\ & \llap{(N=2k-1,\ k \in \mathbb{N})}\\
\dfrac{a_0+(-1)^n a_{N/2}}{2}
+ \displaystyle{
\sum_{m=1}^{N/2-1}\left( a_m\cos(\dfrac{m}{N}n\tau)
+ b_m\sin(\dfrac{m}{N}n\tau)
\right)}
\\ & \llap{(N=2k,\ k \in \mathbb{N})}
\end{cases}\\
\end{align}
ただし
\begin{align}
a_m&= \dfrac{2}{N} \sum_{n=0}^{N-1}f(n)\cos(\dfrac{m}{N}n\tau)\\
b_m&= \dfrac{2}{N} \sum_{n=0}^{N-1}f(n)\sin(\dfrac{m}{N}n\tau)\\
\end{align}
離散三角関数正規直交基底$E = \{ \mathbf{e}_0,\
\mathbf{e}_1,\ \cdots\ ,\
\mathbf{e}_{N} \}$は$\mathbb{R}^N$の正規直交基底であるから、任意の数ベクトル$\mathbf{f} \in \mathbb{R}^N$を$E$により次のように展開できる。
$N$が奇数のとき、
\begin{align}
\mathbf{f}
&=\begin{bmatrix}
f(0)\\ f(1)\\ \vdots \\ f(N-1)
\end{bmatrix}\\
&=\sum_{m=0}^{N-1} (\mathbf{f} \cdot \mathbf{e}_m) \mathbf{e}_m\\
&=(\mathbf{f} \cdot \sqrt{\dfrac{1}{N}} \mathbf{c}_0) \sqrt{\dfrac{1}{N}}\mathbf{c}_0
+ \sum_{m=0}^{(N-1)/2} (\mathbf{f} \cdot \sqrt{\dfrac{2}{N}} \mathbf{c}_m) \sqrt{\dfrac{2}{N}}\mathbf{c}_m
+ \sum_{m=1}^{(N-1)/2} (\mathbf{f} \cdot \sqrt{\dfrac{2}{N}} \mathbf{s}_m) \sqrt{\dfrac{2}{N}} \mathbf{s}_m\\
&=\dfrac{1}{N} (\mathbf{f} \cdot \mathbf{c}_0)\mathbf{c}_0
+\sum_{m=0}^{(N-1)/2} \dfrac{2}{N} (\mathbf{f} \cdot \mathbf{c}_m) \mathbf{c}_m
+ \sum_{m=1}^{(N-1)/2} \dfrac{2}{N} (\mathbf{f} \cdot \mathbf{s}_m) \mathbf{s}_m\\
&=\dfrac{a_0}{2}+
\sum_{m=0}^{(N-1)/2} a_m
\begin{bmatrix}
\cos(\dfrac{m}{N}0\tau)\\ \cos(\dfrac{m}{N}1\tau)\\
\vdots \\ \cos\left( \dfrac{m}{N}(N-1)\tau \right)
\end{bmatrix}
+\sum_{m=1}^{(N-1)/2} b_m
\begin{bmatrix}
\sin(\dfrac{m}{N}0\tau)\\ \sin(\dfrac{m}{N}1\tau)\\
\vdots \\ \sin\left( \dfrac{m}{N}(N-1)\tau \right)
\end{bmatrix}\\
\end{align}
ここで
\begin{align}
a_m &=\dfrac{2}{N} \sum_{n=0}^{N-1}f(n)\cos(n \tau \dfrac{m}{N})\\
b_m &=\dfrac{2}{N} \sum_{n=0}^{N-1}f(n)\sin(n \tau \dfrac{m}{N})\\
\end{align}
$N$が偶数のときも同様にして、
\begin{align}
\mathbf{f}
&=\begin{bmatrix}
f(0)\\ f(1)\\ \vdots \\ f(N-1)
\end{bmatrix}\\
&=\sum_{m=0}^{N-1} (\mathbf{f} \cdot \mathbf{e}_m) \mathbf{e}_m\\
&=(\mathbf{f} \cdot \sqrt{\dfrac{1}{N}} \mathbf{c}_0) \sqrt{\dfrac{1}{N}}\mathbf{c}_0
+ \sum_{m=0}^{N/2-1} (\mathbf{f} \cdot \sqrt{\dfrac{2}{N}} \mathbf{c}_m) \sqrt{\dfrac{2}{N}}\mathbf{c}_m
\\&\quad \quad + \sum_{m=1}^{N/2-1} (\mathbf{f} \cdot \sqrt{\dfrac{2}{N}} \mathbf{s}_m) \sqrt{\dfrac{2}{N}} \mathbf{s}_m
+(\mathbf{f} \cdot \sqrt{\dfrac{1}{N}} \mathbf{c}_{N/2}) \sqrt{\dfrac{1}{N}}\mathbf{c}_{N/2}\\
&=\dfrac{1}{N} (\mathbf{f} \cdot \mathbf{c}_0)\mathbf{c}_0
+\sum_{m=0}^{N/2-1} \dfrac{2}{N} (\mathbf{f} \cdot \mathbf{c}_m) \mathbf{c}_m
+ \sum_{m=1}^{N/2-1} \dfrac{2}{N} (\mathbf{f} \cdot \mathbf{s}_m) \mathbf{s}_m
+\dfrac{1}{N} (\mathbf{f} \cdot \mathbf{c}_{N/2})\mathbf{c}_{N/2}\\
&=\dfrac{a_0+(-1)^n a_{N/2}}{2}+
\sum_{m=0}^{N/2-1} a_m
\begin{bmatrix}
\cos(\dfrac{m}{N}0\tau)\\ \cos(\dfrac{m}{N}1\tau)\\
\vdots \\ \cos\left( \dfrac{m}{N}(N-1)\tau \right)
\end{bmatrix}
+\sum_{m=1}^{N/2-1} b_m
\begin{bmatrix}
\sin(\dfrac{m}{N}0\tau)\\ \sin(\dfrac{m}{N}1\tau)\\
\vdots \\ \sin\left( \dfrac{m}{N}(N-1)\tau \right)
\end{bmatrix}\\
\end{align}
フーリエ級数展開と実離散フーリエ変換の対応
関数$f(x)$のフーリエ級数展開は周期を$T$とすると
\begin{align}
f(x)= \dfrac{a_0}{2} + \sum_{m=1}^{\infty}\left(a_m \cos(\dfrac{m}{T}\tau x) + b_m \cos(\dfrac{m}{T}\tau x) \right)
\end{align}
ただし
\begin{align}
a_m = \dfrac{2}{T}\int_0^T f(t)\cos(\dfrac{m}{T}\tau x) dx,\quad
b_m = \dfrac{2}{T}\int_0^T f(t)\sin(\dfrac{m}{T}\tau x) dx
\end{align}
実離散フーリエ変換の$x$を$f$、$\dfrac{n}{N}$を$x$に置き換えて$N \rightarrow \infty$の極限をとると、区分求積法より
\begin{align} f(x) &=\sum_{m=0}^{\infty} a_m\cos(m\tau x) +\sum_{m=0}^{\infty}b_m\sin(m\tau x) \end{align}
\begin{align} a_m&= \begin{cases} {\displaystyle \ \ \int_0^1 f(n)\cos(m\tau x) dx} & (m=0) \\ {\displaystyle 2\int_0^1 f(n)\cos(m\tau x) dx} & (m>0) \end{cases}\\ b_m&= 2{\displaystyle \int_0^1 f(n)\sin(m\tau x) dx} \end{align}
変形すると
\begin{align}
f(x)&=\dfrac{a_0}{2} + \sum_{m=0}^{\infty} a_m\cos(m\tau x)
+\sum_{m=0}^{\infty}b_m\sin(m\tau x) \
\left(+\ \dfrac{a_{\infty}}{2} \right)
\end{align}
\begin{align}
a_m&= 2\int_0^1 f(n)\cos(m\tau x) dx\\
b_m&= 2\int_0^1 f(n)\sin(m\tau x) dx
\end{align}
よって(このページで示した)実離散フーリエ変換は$N \rightarrow \infty$の極限で周期$\tau$のフーリエ級数展開に対応する。
$\dfrac{a_{\infty}}{2}$があるのが気持ち悪いですが、リーマン・ルベーグの補題
\begin{align}
\lim_{N\rightarrow \infty} \int_a^b f(x)\cos(Nx)dx=0
\end{align}
により$a_{\infty}=0$と消えてくれます。
リーマン・ルベーグの補題は連続フーリエ変換の収束の証明にとっても重要なものですが、その条件や証明等を説明すると長くなりそうなので省略します。
関数$f(x)$の複素離散フーリエ変換は
\begin{align}
F(m)= \sum_{n=0}^{N-1}f(n) \exp(-i\dfrac{m}{N} n\tau)
\end{align}
複素離散逆フーリエ変換は
\begin{align}
f(n)= \dfrac{1}{N}\sum_{m=0}^{N-1}F(m) \exp(i\dfrac{m}{N} n)
\end{align}
実離散フーリエ変換と複素離散フーリエ変換の関係
実離散フーリエ変換の書き換え
実離散フーリエ変換は次のように書き換えられる。
\begin{align}
f(n)
&=\begin{cases}
\dfrac{a_0}{2} + g_{(N-1)/2}(n)
& (N=2k-1,\ k \in \mathbb{N}) \\\\
\dfrac{a_0+(-1)^n a_{N/2}}{2} + g_{N/2-1}(n)
& (N=2k,\ k \in \mathbb{N}) \\
\end{cases}\\
\end{align}
ただし
\begin{align}
g_M(n)
&=\sum_{m=1}^{M}\left(
a_m\cos(\dfrac{m}{N}n\tau)+b_m\sin(\dfrac{m}{N}n\tau)
\right)\\
a_m&= \dfrac{2}{N} \sum_{n=0}^{N-1}f(n)\cos(\dfrac{m}{N}n\tau)\\
b_m&= \dfrac{2}{N} \sum_{n=0}^{N-1}f(n)\sin(\dfrac{m}{N}n\tau)\\
\end{align}
オイラーの公式による変形
$\exp(i\theta) = \cos(\theta)+i\sin(\theta)$より
$\cos(\theta)=\dfrac{\exp(i\theta)+\exp(-i\theta)}{2},\ \sin(\theta)=\dfrac{\exp(i\theta)-\exp(-i\theta)}{2i}$
実離散フーリエ変換に対して、$\theta_m=\dfrac{m}{N}n\tau$として三角関数を複素指数関数に書き直す。
$g_M(n)$の変形
\begin{align} g_M(n) &=\sum_{m=1}^{M} \left( a_m \dfrac{\exp(i\theta_m)+\exp(-i\theta_m)}{2} + b_m\dfrac{\exp(i\theta_m)-\exp(-i\theta_m)}{2i} \right)\\ &=\sum_{m=1}^{M} \left( a_m \dfrac{\exp(i\theta_m)+\exp(-i\theta_m)}{2} - b_m\dfrac{i\exp(i\theta_m)-i\exp(-i\theta_m)}{2} \right)\\ &=\sum_{m=1}^{M} \left( \dfrac{a_m-ib_m}{2} \exp(i\theta_m) + \dfrac{a_m+ib_m}{2} \exp(-i\theta_m) \right)\\ \end{align}
$a_m,\ b_m$の変形
\begin{align} a_m&= \dfrac{2}{N} \sum_{n=0}^{N-1}f(n)\cos(\dfrac{m}{N}n\tau)\\ &= \dfrac{2}{N} \sum_{n=0}^{N-1}f(n) \dfrac{\exp(i\theta_m)+\exp(-i\theta_m)}{2} \\ b_m&= \dfrac{2}{N} \sum_{n=0}^{N-1}f(n)\sin(\dfrac{m}{N}n\tau)\\ &= \dfrac{2}{N} \sum_{n=0}^{N-1}f(n) \dfrac{\exp(i\theta_m)-\exp(-i\theta_m)}{2i}\\ &= \dfrac{2}{N} \sum_{n=0}^{N-1}f(n) \dfrac{-i\exp(i\theta_m)+i\exp(-i\theta_m)}{2} \end{align}
$\dfrac{a_m \pm ib_m}{2}$の変形
\begin{align} \dfrac{a_m+ib_m}{2} &= \dfrac{1}{N} \sum_{n=0}^{N-1}f(n) \left( \dfrac{\exp(i\theta_m)+\exp(-i\theta_m)}{2} + \dfrac{\exp(i\theta_m)-\exp(-i\theta_m)}{2}\\ \right)\\ &= \dfrac{1}{N} \sum_{n=0}^{N-1}f(n)\exp(i\theta_m)\\ \dfrac{a_m-ib_m}{2} &= \dfrac{1}{N} \sum_{n=0}^{N-1}f(n) \left( \dfrac{\exp(i\theta_m)+\exp(-i\theta_m)}{2} - \dfrac{\exp(i\theta_m)-\exp(-i\theta_m)}{2}\\ \right)\\ &= \dfrac{1}{N} \sum_{n=0}^{N-1}f(n)\exp(-i\theta_m)\\ \end{align}
ここで、$h(m) = \dfrac{a_m + ib_m}{2}$とすると
$\theta_{-m}=-\dfrac{m}{N}n\tau=-\theta_m$より
\begin{align} h(-m) &= \dfrac{1}{N} \sum_{n=0}^{N-1}f(n)\exp(i\theta_{-m})\\ &= \dfrac{1}{N} \sum_{n=0}^{N-1}f(n)\exp(-i\theta_{m})\\ &= \dfrac{a_m - ib_m}{2} \end{align}
よって
\begin{align}
g_M(n)
&=\sum_{m=0}^{M}
\left(
\dfrac{a_m-ib_m}{2} \exp(i\theta_m)
+ \dfrac{a_m+ib_m}{2} \exp(i\theta_m)
\right)\\
&=\sum_{m=0}^{M}
\big(
h(-m) \exp(i\theta_m)
+ h(m) \exp(-i\theta_m)
\big)\\
\end{align}
$g_M(n)$の変数変換
$g_M(n)$の$h(m) \exp(-i\theta_{m})$に対して$m=N-k$つまり$k=N-m$とすると、
$m:1 \rightarrow M$に対して$k:N-M \rightarrow N-1$となるから
\begin{align} g_M(n) &=\sum_{m=1}^{M} h(-m) \exp(i\theta_m) + \sum_{m=1}^{M} h(m) \exp(-i\theta_m)\\ &=\sum_{m=1}^{M} h(-m) \exp(i\theta_m) + \sum_{m=N-M}^{N-1} h(N-k) \exp(-i\theta_{N-k})\\ \end{align}
ここで、
\begin{align}
\exp(i\theta_{N-m})
&=\exp(i\dfrac{N-m}{N}n\tau)\\
&=\exp(in\tau-i\dfrac{m}{N}n\tau)\\
&=\exp(in\tau)\exp(-i\dfrac{m}{N}n\tau)\\
&=\exp(-i\theta_m)\\
\end{align}
同様にして$\exp(-i\theta_{N-m})=\exp(i\theta_{m})$となる。また、
\begin{align}
h(N-m)
&= \dfrac{1}{N} \sum_{n=0}^{N-1}f(n)\exp(i\theta_{N-m})\\
&= \dfrac{1}{N} \sum_{n=0}^{N-1}f(n)\exp(-i\theta_{m})\\
&= h(-m)
\end{align}
よって$g_M(n)$は次のように書き換えられる。
\begin{align}
g_M(n)
&=\sum_{m=1}^{M} h(-m) \exp(i\theta_m)
+ \sum_{m=N-M}^{N-1} h(N-k) \exp(-i\theta_{N-k})\\
&=\sum_{m=1}^{M} h(-m) \exp(i\theta_m)
+ \sum_{m=N-M}^{N-1} h(-m) \exp(i\theta_{m})\\
\end{align}
$M=0$の場合
\begin{align}
a_0
&=\dfrac{2}{N} \sum_{n=0}^{N-1}f(n)\cos(\dfrac{0}{N}n\tau)\\
&=\dfrac{2}{N} \sum_{n=0}^{N-1}f(n)\\
h(0)
&= \dfrac{1}{N} \sum_{n=0}^{N-1}f(n) \exp(i\theta_0)\\
&= \dfrac{1}{2} \dfrac{2}{N} \sum_{n=0}^{N-1}f(n)\\
&= \dfrac{a_0}{2}\\
\exp(i\theta_0)
&= \exp(i\dfrac{0}{N}n\tau) =1\\
\end{align}
よって
\begin{align}
\dfrac{a_0}{2}=h(0)\exp(i\theta_0)
\end{align}
$N$の偶奇による場合分け
$N$が奇数の時
\begin{align} f(n) &=\dfrac{a_0}{2} + g_{(N-1)/2}(n) \\ &=h(0)\exp(i\theta_0) + \sum_{m=1}^{(N-1)/2} h(-m) \exp(i\theta_m) + \sum_{m=N-(N-1)/2}^{N-1} h(-m) \exp(i\theta_{m})\\ &=\sum_{m=0}^{(N-1)/2} h(-m) \exp(i\theta_m) + \sum_{m=(N-1)/2+1}^{N-1} h(-m) \exp(i\theta_{m})\\ &=\sum_{m=0}^{N-1} h(-m) \exp(i\theta_m) \end{align}
$N$が偶数の時
\begin{align}
a_{N/2}
&=\dfrac{2}{N} \sum_{n=0}^{N-1}f(n)\cos(\dfrac{1}{2}n\tau)\\
\\
h(N/2)
&= \dfrac{1}{N} \sum_{n=0}^{N-1}f(n)\exp(i\dfrac{1}{2}n\tau)\\
&= \dfrac{1}{2} \dfrac{2}{N} \sum_{n=0}^{N-1}f(n)\cos(\dfrac{1}{2}n\tau)\\
&= \dfrac{a_{N/2}}{2}\\
\exp(i\theta_{N/2})
&=\exp(i\dfrac{1}{2}n\tau)=(-1)^n\\
\end{align}
よって
\begin{align}
f(n)
&=\dfrac{a_0+(-1)^n a_{N/2}}{2} + g_{N/2-1}(n)\\
&=\dfrac{a_0}{2} + g_{N/2-1}(n) +\dfrac{a_{N/2}}{2}(-1)^n\\
&=h(0)\exp(i\theta_0)
+ \sum_{m=1}^{N/2-1} h(-m) \exp(i\theta_m)
+ \sum_{m=N-(N/2-1)}^{N-1} h(-m) \exp(i\theta_{m})\\
&=\sum_{m=0}^{N/2-1} h(-m) \exp(i\theta_m)
+ \sum_{m=N/2+1}^{N-1} h(-m) \exp(i\theta_{m})\\
&=\sum_{m=0}^{N-1} h(-m) \exp(i\theta_m)
\end{align}
結論
これらのことから、実離散フーリエ変換は$N$の偶奇によらず次のように変形できる。
\begin{align} f(n) &=\sum_{m=0}^{N-1} h(-m) \exp(i\dfrac{m}{N}n\tau)\\ h(-m) &= \dfrac{1}{N} \sum_{n=0}^{N-1}f(n)\exp(-i\dfrac{m}{N}n\tau)\\ \end{align}
つまり
\begin{align}
f(n)
&=\sum_{m=0}^{N-1} \left(\left(
\dfrac{1}{N} \sum_{n=0}^{N-1}f(n)\exp(-i\dfrac{m}{N}n\tau)
\right) \exp(i\dfrac{m}{N}n\tau)\right)\\
&=\dfrac{1}{N}\sum_{m=0}^{N-1} \left(
\sum_{n=0}^{N-1}f(n)\exp(-i\dfrac{m}{N}n\tau)
\right) \exp(i\dfrac{m}{N}n\tau)\\
\end{align}
ここで、
\begin{align}
F(m)= \sum_{n=0}^{N-1}f(n) \exp(-i\dfrac{m}{N} n\tau)
\end{align}
とおけば、
\begin{align}
f(n)
&=\dfrac{1}{N}\sum_{m=0}^{N-1} F(m)
\exp(i\dfrac{m}{N}n\tau)\\
\end{align}
より、複素離散フーリエ変換と完全に一致する。
関数$f(x)$の複素離散フーリエ変換は
\begin{align}
F(m)= \sum_{n=0}^{N-1}f(n) \exp(-i\dfrac{m}{N} n\tau)
\end{align}
複素離散逆フーリエ変換は
\begin{align}
f(n)= \dfrac{1}{N}\sum_{m=0}^{N-1}F(m) \exp(i\dfrac{m}{N} n)
\end{align}
参考文献
この記事を高評価した人
この記事に送られたバッジ
投稿者
