離散フーリエ変換、逆離散フーリエ変換

#1 離散フーリエ変換

$N$個の複素数列$x_{0},\cdots,x_{N-1}$に対してDFTすることで、$N$個の複素数列$X_{0},\cdots,X_{N-1}$が得られる。
$$
X_{k}=\sum_{n=0}^{N-1}x_{n}e^{-i\frac{2\pi kn}{N}}\ \ \ \ \ \ \ \ \ k=0,\cdots,N-1
$$ 

ここで$e$はネイピア数、$i$は虚数単位($i^{2}=-1$)で、$\pi$は円周率である。また、この変換を$\mathcal{F}$という記号で表し、$x=\left(x_{0},\cdots,x_{N-1}\right)$、$X=\left(X_{0},\cdots,X_{N-1}\right)$とおいて

$$
X=\mathcal{F}\left(x\right)
$$
 
のように略記することが多い。

##1.1 導出

離散時間フーリエ変換は以下のように示される。$$F\left(\omega\right)=\sum_{n=-\infty}^{\infty}f\left[n\right]e^{-j\omega n}$$
 

$f\left[n\right]$が周期的な時、左辺の$F\left(\omega\right)$は$N$で周期的かつ$\omega=2\pi k/N$に無限大のインパルスが立つ離散周波数関数$F\left[n\right]$となる。上式の総和を1周期($N$
 )にすることで、有限の値を持つ関数として表現できる。
$$
F\left[k\right]=\sum_{n=0}^{N-1}f\left[n\right]e^{-j\frac{2\pi}{N}kn}\ \ \ \ \ \left(n=0,1,\cdots,N-1\right)
$$ 

上式を離散フーリエ変換という。

#2 逆離散フーリエ変換

$$
x_{n}=\frac{1}{N}\sum_{k=0}^{N-1}X_{k}e^{i\frac{2\pi kn}{N}}\ \ \ \ \ \ \ \ \ n=0,\cdots,N-1
$$
 

##2.1 導出

離散フーリエ変換の式を以下の様に変形する。
$$
F\left(\omega\right)	=	\sum_{k=-\infty}^{\infty}f\left[n\right]e^{-j\omega n}
	=	\sum_{k=-\infty}^{\infty}c_{k}\delta\left(\omega-\frac{2\pi k}{N}\right)
$$		
 

離散時間フーリエ変換をデータ点数$N$で周期的な離散時間信号に対して行うと、$F\left(\omega\right)$
は$N$で周期的な離散周波数をもつ関数になる。上式は$F\left(\omega\right)$を$\omega=\frac{2\pi k}{N}$に$c_{k}$の値を持つ関数として表現している。また離散時間信号を連続周波数領域で表現しているため、デルタ関数$\delta\left(\omega-\frac{2\pi k}{N}\right)$をかけている。

上式を逆離散フーリエ変換$f\left[n\right]=\frac{1}{2\pi}\int_{-\pi}^{\pi}F\left(\omega\right)e^{j\omega n}d\omega$
 
に代入すると、
$$
f\left[n\right]	=	\frac{1}{2\pi}\int_{-\pi}^{\pi}\sum_{k=-\infty}^{\infty}c_{k}\delta\left(\omega-\frac{2\pi k}{N}\right)e^{j\omega n}d\omega
	=	\frac{1}{2\pi}\sum_{k=0}^{N-1}c_{k}e^{j\frac{2\pi kn}{N}}
$$
		
 

ここで、$c_{k}=F\left[k\right]\cdot2\pi/N$となるような数列$F\left[k\right]$を導入する。これを上式に代入すると、
$$f\left[n\right]=\frac{1}{N}\sum_{k=0}^{N-1}F\left[k\right]e^{j\frac{2\pi kn}{N}}\ \ \ \ \ \left(n=0,1,\cdots,N-1\right)
$$

これを逆離散フーリエ変換と呼ぶ。

#3 離散フーリエ変換と逆フーリエ変換の関係

離散フーリエ変換したものを逆フーリエ変換して元に戻ることを確認する。

```math

f\left[n\right]=\frac{1}{N}\sum_{k=0}^{N-1}F\left[k\right]e^{j\frac{2\pi}{N}kn}	=	\frac{1}{N}\sum_{k=0}^{N-1}F\left[k\right]e^{j\frac{2\pi kn}{N}}\\
	=	\frac{1}{N}\sum_{k=0}^{N-1}\left[\sum_{m=0}^{N-1}f\left[m\right]e^{-j\frac{2\pi km}{N}}\right]e^{j\frac{2\pi kn}{N}}\\
	=	\frac{1}{N}\sum_{m=0}^{N-1}f\left(m\right)\sum_{k=0}^{N-1}e^{j\frac{2\pi k\left(m-n\right)}{N}}\\
	=	\frac{1}{N}\sum_{m=0}^{N-1}f\left(m\right)N\delta_{m,n}\\
	=	f\left(n\right)
```

#4 周波数シフト

ある離散時間信号$x\left[n\right]$に$e^{j\frac{2\pi}{N}k_{1}n}$かけたものの離散フーリエ変換は、

```math
\mathcal{F}\left[e^{j\frac{2\pi}{N}k_{1}n}x\left[n\right]\right]	= 	e^{j\frac{2\pi}{N}k_{1}n}\sum_{n=0}^{N-1}x\left[n\right]e^{-j\frac{2\pi}{N}kn} \\
	=	\sum_{n=0}^{N-1}x\left[n\right]e^{-j\frac{2\pi}{N}\left(k-k_{1}\right)n}=X\left[k-k_{1}\right] 
```

 で表される。

#5 時間シフト

ある離散時間信号$x\left[n\right]$を$n_{1}$だけ進めたもの$x\left[n-n_{1}\right]$の離散フーリエ変換は、

```math
\mathcal{F}\left[x\left[n-n_{1}\right]\right]	=	\sum_{n=0}^{N-1}x\left[n-n_{1}\right]e^{-j\frac{2\pi}{N}k\left(n-n_{1}\right)}\\
	=	e^{j\frac{2\pi}{N}kn_{1}}\sum_{n=0}^{N-1}x\left[n-n_{1}\right]e^{-j\frac{2\pi}{N}kn}=e^{-j\frac{2\pi}{N}kn_{1}}X\left[k\right]
```

 で表される。位相を90度進める場合、つまり$\frac{N}{4}$を引く場合、

```math
\mathcal{F}\left[x\left[n-\frac{N}{4}\right]\right]	=	e^{j\frac{2\pi}{N}k\left(\frac{N}{4}\right)}\sum_{n=0}^{N-1}x\left[n-\frac{N}{4}\right]e^{-j\frac{2\pi}{N}kn} \\
	=	e^{-j\frac{\pi}{2}k}\sum_{n=0}^{N-1}x\left[n-\frac{N}{4}\right]e^{-j\frac{2\pi}{N}kn}\\
	=	\sum_{n=0}^{N-1}x\left[n-\frac{N}{4}\right]e^{-jk\left(\frac{2\pi}{N}n-\frac{\pi}{2}\right)}\\
	=	-j\sum_{n=0}^{N-1}x\left[n-\frac{N}{4}\right]e^{-jk\frac{2\pi}{N}n}=-jX\left[k\right]
```
 ここで、定理$e^{i\left(\theta-\frac{\pi}{2}\right)}=-ie^{i\theta}$
 を用いた。上式から、位相を90度進めることは、周波数領域で$-j$
 をかけることと等価であることがわかる。