DFT在零点

$\underline{\mathcal{F}}\underline{f}(0) = \displaystyle{ \sum_{n=0}^{N-1}\underline{f}[n]e^{-2\pi i\frac{n0}{N}} = \sum_{n=0}^{N-1}\underline{f}[n] }$

还记得傅里叶变换在零点处也有类似的式子

$\mathcal{F}f(0) = \displaystyle{ \int_{-\infty}^{\infty}f(t)e^{-2\pi i0t}dt = \int_{-\infty}^{\infty}f(t)dt }$

如此看来，离散傅里叶变换与傅里叶变换还是很相似的。

典型的离散信号以及它们的DFT

1. 典型的离散信号

离散信号$\underline{1}$在各采样点的采样值都为$1$

$\underline{1} = (1,1,…,1)$

离散信号$\underline{\delta_0}$只有在零点处才有为$1$的脉冲

$\underline{\delta_0} = (1,0,0,…,0)$

离散信号$\underline{\delta_k}$只有在第$k$项处，才有为$1$的脉冲

$\underline{\delta_k} = (\underbrace{0,0,...,0,1}_{k\ entries},0,...,0)$

2. 典型离散信号的DFT

对$\underline{\delta_0}$进行DFT

$\underline{\mathcal{F}}\underline{\delta_0} = \displaystyle{\sum_{n=0}^{N-1}\underline{\delta_0}[n] \underline{\omega}^{-n} = \underline{\delta_0}[0]\underline{\omega}^0 = 1\cdot \underline{\omega}^0 = (1,1,…,1) = \underline{1}}$

因此

$\underline{\mathcal{F}}\underline{\delta_0}=\underline{1}$

对$\underline{\delta_k}$进行DFT

$\underline{\mathcal{F}}\underline{\delta_k} = \displaystyle{\sum_{n=0}^{N-1}\underline{\delta_k}[n] \underline{\omega}^{-n} = \underline{\delta_k}[k]\underline{\omega}^{-k} = 1\cdot \underline{\omega}^{-k} = \underline{\omega}^{-k}}$

因此

$\underline{\mathcal{F}}\underline{\delta_k} = \underline{\omega}^{-k}$

对$\underline{\omega}^{k}$进行DFT

$\begin{align*}
\underline{\mathcal{F}}\underline{\omega}^{k}[m]
&=\sum_{n=0}^{N-1}\underline{\omega}^k[n]\underline{\omega}^{-n}[m]\\
&=\sum_{n=0}^{N-1}e^{2\pi i\frac{kn}{N}}\cdot e^{-2\pi i\frac{mn}{N}}\\
&=\underline{\omega}^k\cdot\underline{\omega}^m\\
&=\begin{cases}
0 & \text{ , } k\neq m \\
N & \text{ , } k= m
\end{cases}
\end{align*}$

因此

$\underline{\mathcal{F}}\underline{\omega}^k = (\underbrace{0,0,...,0,N}_{k\ entries},0,...,0) = N\underline{\delta_k}$

DFT矩阵

1. DFT矩阵的定义

令$\omega = e^{2\pi i\frac{1}{N}}$，请注意，这里的$\omega$没有下划线，并不是离散信号。则有

$\omega^{-mn} = e^{-2\pi i\frac{mn}{N}}$

DFT的变换式可以写成

$\underline{\mathcal{F}}\underline{f}[m] = \displaystyle{ \sum_{n=0}^{N-1}\omega^{-mn} \underline{f}[n]}$

如此一来，上式呈现了一种新的表述，即对离散信号$\underline{f}$进行DFT就相当于用$\underline{f}$与矩阵$\left( \omega^{-} \right)^{mn}$相乘，$mn$为该矩阵的$m$行$n$列

$\begin{pmatrix}
1 &1  &1  &...  &1 \\
1 &\omega^{-1}  &\omega^{-2}  &...  &\omega^{-(N-1)} \\
1 &\omega^{-2}  &\omega^{-4}  &...  &\omega^{-2(N-1)} \\
\vdots  &\vdots  &\vdots  &...  & \vdots\\
1 &\omega^{-(N-1)}  &\omega^{-2(N-1)}  &...  &\omega^{-(N-1)^2}
\end{pmatrix}
\begin{pmatrix}
\underline{f}[0]\\
\underline{f}[1]\\
\underline{f}[2]\\
\vdots\\
\underline{f}[N-1]
\end{pmatrix}
=
\begin{pmatrix}
\underline{\mathcal{F}}\underline{f}[0]\\
\underline{\mathcal{F}}\underline{f}[1]\\
\underline{\mathcal{F}}\underline{f}[2]\\
\vdots\\
\underline{\mathcal{F}}\underline{f}[N-1]
\end{pmatrix}$

上述式子左边的矩阵就是DFT矩阵，DFT矩阵是一个$N\times N$的矩阵，可以用下面的式子表达

$(\mathcal{F})_{nm} = \omega^{-nm}$

2. DFT矩阵的共轭转置

对DFT矩阵$\mathcal{F}$进行共轭转置，即

$(\mathcal{F}^{*})_{nm} = \overline{(\underline{\mathcal{F}})_{mn}} = \overline{\omega^{-mn}} = \omega^{mn}$

DFT矩阵与它的共轭转置矩阵相乘，有

$\underline{\mathcal{F}}\underline{\mathcal{F}}^{*} =
\begin{pmatrix}
1 &1  &1  &...  &1 \\
1 &\omega^{-1}  &\omega^{-2}  &...  &\omega^{-(N-1)} \\
1 &\omega^{-2}  &\omega^{-4}  &...  &\omega^{-2(N-1)} \\
\vdots  &\vdots  &\vdots  &...  & \vdots\\
1 &\omega^{-(N-1)}  &\omega^{-2(N-1)}  &...  &\omega^{-(N-1)^2}
\end{pmatrix}
\begin{pmatrix}
1 &1  &1  &...  &1 \\
1 &\omega^{1}  &\omega^{2}  &...  &\omega^{(N-1)} \\
1 &\omega^{2}  &\omega^{4}  &...  &\omega^{2(N-1)} \\
\vdots  &\vdots  &\vdots  &...  & \vdots\\
1 &\omega^{(N-1)}  &\omega^{2(N-1)}  &...  &\omega^{(N-1)^2}
\end{pmatrix}$

$=
\begin{pmatrix}
\underline{\omega}^0\cdot\underline{\omega}^0 &\underline{\omega}^1\cdot\underline{\omega}^0  &\underline{\omega}^2\cdot\underline{\omega}^0  &...  &\underline{\omega}^{N-1}\cdot\underline{\omega}^0 \\
\underline{\omega}^0\cdot\underline{\omega}^1 &\underline{\omega}^1\cdot\underline{\omega}^1  &\underline{\omega}^2\cdot\underline{\omega}^1  &...  &\underline{\omega}^{N-1}\cdot\underline{\omega}^1 \\
\underline{\omega}^0\cdot\underline{\omega}^2 &\underline{\omega}^1\cdot\underline{\omega}^2  &\underline{\omega}^2\cdot\underline{\omega}^2  &...  &\underline{\omega}^{N-1}\cdot\underline{\omega}^2 \\
\vdots  &\vdots  &\vdots  &...  & \vdots\\
\underline{\omega}^0\cdot\underline{\omega}^{N-1} &\underline{\omega}^1\cdot\underline{\omega}^{N-1}  &\underline{\omega}^2\cdot\underline{\omega}^{N-1}  &...  &\underline{\omega}^{N-1}\cdot\underline{\omega}^{N-1} \\
\end{pmatrix}\qquad\qquad\qquad\qquad$

$=\begin{pmatrix}
N &0  &0  &...  &0 \\
0 &N  &0  &...  &0 \\
0 &0  &N  &...  &0 \\
\vdots &\vdots  &\vdots  &...  &\vdots \\
0 &0  &0  &...  &N
\end{pmatrix}  \qquad \left(
\underline{\omega}^l\cdot\underline{\omega}^k = \begin{cases}
0 & \text{ , } k\neq l \\
N & \text{ , } k= l
\end{cases}
\right)\qquad\qquad\qquad\qquad$

$= NI \qquad (I\ is\ N\times N\ identity\ matrix)\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad$

因此

$\underline{\mathcal{F}}\underline{\mathcal{F}}^{*} = NI$

同理可得

$\underline{\mathcal{F}}^{*}\underline{\mathcal{F}} = NI$

3. IDFT矩阵

通过上述转置矩阵的运算结果结果，可以得到IDFT矩阵为

$\underline{\mathcal{F}}^{-1} = \frac{1}{N}\underline{\mathcal{F}}^{*}$

即

$\left( \underline{\mathcal{F}}^{-1} \right)_{mn} = \frac{1}{N}\omega^{mn}$

这个结果同样也能运用推导DFT矩阵的过程得出。

4. DFT矩阵运算复杂度

运算复杂度这里是值矩阵运算中乘法运算的数目，$\underline{\mathcal{F}}\underline{f}$的每一项运算会花费$N$个乘法运算，其中共有$N$项，即运算复杂度为$N\times N$，用$O(N^2)$表示。

FFT算法的目的就是为了减少DFT的运算复杂度，FFT的复杂度为$O(NlogN)$。

DFT特性

我们上节课遗留下来了，关于DFT特性的讨论：输入和输出都是周期为$N$的周期离散函数。得出这个结论是因为离散复指数具有周期性。

1. 输入与输出离散信号周期性的证明

证明过程如下：

$\underline{\omega}[m] = e^{2\pi i \frac{m}{N}}$

$\underline{\omega}[m+N] = e^{2\pi i\frac{m+N}{N}} = e^{2\pi i\frac{m}{N}}\cdot e^{2\pi i}=e^{2\pi i\frac{m}{N}} = \underline{\omega}[m]$

同理

$\underline{\omega}^{n}[m] = \underline{\omega}^n[m+N] \qquad \underline{\omega}^{-n}[m] = \underline{\omega}^{-n}[m+N]$

即$\underline{\omega},\underline{\omega}^n,\underline{\omega}^{-n}$都是周期为$N$的离散复指数信号。

由上述结论推广到DFT

$\underline{\mathcal{F}}\underline{f}[m+N] = \displaystyle{\sum_{n=0}^{N-1}\underline{f}[n]\underline{\omega}^{-n}[m+N]= \sum_{n=0}^{N-1}\underline{f}[n]\underline{\omega}^{-n}[m]} = \underline{\mathcal{F}}\underline{f}[m]$

因此$\underline{\mathcal{F}}\underline{f}[m+N] = \underline{\mathcal{F}}\underline{f}[m]$，表明了对离散信号$\underline{f}$进行DFT后会得到周期为$N$的离散信号。

同理，推广到IDFT

$\underline{\mathcal{F}}^{-1}\underline{f}[m+N] = \frac{1}{N}\displaystyle{\sum_{n=0}^{N-1}\underline{f}[n]\underline{\omega}^{n}[m+N]= \frac{1}{N}\sum_{n=0}^{N-1}\underline{f}[n]\underline{\omega}^{-n}[m]} = \underline{\mathcal{F}}^{-1}\underline{f}[m]$

因此$\underline{\mathcal{F}}^{-1}\underline{f}[m+N] = \underline{\mathcal{F}}^{-1}\underline{f}[m]$，表明了对离散信号$\underline{f}$进行IDFT会得到周期为$N$的离散信号。

这种周期为$N$的特性是由$\underline{\omega}$的周期性决定的。对某离散信号$\underline{f}$进行DFT，会得到周期为$N$的离散信号$\underline{\mathcal{F}}\underline{f}$，然后对$\underline{\mathcal{F}}\underline{f}$进行IDFT，即$\underline{\mathcal{F}}^{-1}\underline{\mathcal{F}}\underline{f}$，也会得到周期为$N$的离散信号$\underline{f}$，这表明了原始信号$\underline{f}$也是周期为$N$的离散信号。

因此有结论如下：

• 进行DFT的输入离散信号$\underline{f}$与输出离散信号$\underline{\mathcal{F}}\underline{f}$都是周期为$N$（$N$项）的周期信号；同理进行IDFT的输入离散信号$\underline{F}$与输出离散信号$\underline{\mathcal{F}}^{-1}\underline{F}$都是周期为$N$（$N$项）的周期信号。

在实际应用中，通常我们采集到的离散信号都不是周期为$N$的信号，甚至不具有周期性，但是在进行DFT分析时，都是从采集到的信号中取一部分出来，这部分就会被看作是周期信号中的一个周期，它进行DFT后会产生的也是周期信号。

索引的独立性

周期性可以说是限制，因为我们需要用周期信号来看待将被进行DFT、IDFT的离散信号，但是这个特性也带来了简单有益的结论：索引的独立性（independence of indexing）。

由于$\underline{f}$与$\underline{\omega}$都具有周期性，因此在计算DFT时可以采用任意连续$N$个采样，即

$\underline{\mathcal{F}}\underline{f} = \displaystyle{ \sum_{n=0}^{N-1}\underline{f}[n]\underline{\omega}^{-n} = \sum_{n=1}^{N}\underline{f}[n]\underline{\omega}^{-n} }$

我们也可以把零点放置取样值的中间，即

当$N$为奇数时

$\underline{\mathcal{F}}\underline{f} = \displaystyle{ \sum_{n=-\frac{N-1}{2}}^{\frac{N-1}{2}}\underline{f}[n]\underline{\omega}^{-n} }$

当$N$为偶数时

$\underline{\mathcal{F}}\underline{f} = \displaystyle{ \sum_{n=-\frac{N}{2}+1}^{\frac{N}{2}}\underline{f}[n]\underline{\omega}^{-n} }$

不同的软件，不同的实现对下标（索引）的表达可能会不同，因此我们需要了解通过这小节了解下标（索引）的独立性。

离散信号的反转及其DFT的对偶性

1. 离散信号反转的定义

在讨论连续信号的反转的时候，连续信号$f(x)$的反转为$f^-(x) = f(-x)$，而这里离散信号的反转被定义为$\underline{f}^{-}[m] = \underline{f}[-m]$，也就是说，如果有离散信号

$\underline{f} = \left( \underline{f}[0],\underline{f}[1],\underline{f}[2],…,\underline{f}[N-1] \right)$

它的反转为

$\underline{f}^- = \left( \underline{f}[0],\underline{f}[-1],\underline{f}[-2],…,\underline{f}[-(N-1)] \right)$

离散复指数$\underline{\omega}$的反转为

$\underline{\omega}^- = \left( 1,e^{-2\pi i\frac{1}{N}},e^{-2\pi i\frac{2}{N}},…,e^{-2\pi i\frac{N-1}{N}} \right) = \underline{\omega}^{-1}$

同理有

$\left( \underline{\omega}^n \right)^- = \underline{\omega}^{-n} \qquad \left( \underline{\omega}^{-n} \right)^- = \underline{\omega}^{n}$

2. DFT对偶性讨论

对离散信号$\underline{f}$的反转$\underline{f}^-$进行DFT

$\begin{align*}
\underline{\mathcal{F}}\underline{f}^-
&=\sum_{n=0}^{N-1}\underline{f}^-[n]\underline{\omega}^{-n}\\
&=\sum_{n=0}^{N-1}\underline{f}[-n]\underline{\omega}^{-n} \qquad (definition\ of\ reversed\ signal)\\
&=\sum_{n=0}^{N-1}\underline{f}[N-n]\underline{\omega}^{-n} \qquad (\underline{f}\ is\ period\ of\ N)\\
&=\sum_{l=N}^1\underline{f}[l]\underline{\omega}^{l-N} \qquad (letting\ l=N-n)\\
&=\sum_{l=N}^1\underline{f}[l]\underline{\omega}^l \qquad(\underline{\omega}\ is\ period\ of\ N)\\
&=\sum_{l=0}^{N-1}\underline{f}[l]\underline{\omega}^l \qquad(independence\ of\ indexing)\\
&=\sum_{l=0}^{N-1}\underline{f}[l](\underline{\omega}^{-l})^-\\
&=\left( \sum_{l=0}^{N-1}\underline{f}[l]\underline{\omega}^{-l} \right )^- \qquad \left( \sum_{l=0}^{N-1}\underline{f}[l](\underline{\omega}^{-l})^-[m] =\sum_{l=0}^{N-1}\underline{f}[l](\underline{\omega}^{-l})^[-m]\ the\ definition\ of\ reversed\ signal\right)\\
&=\left(\underline{\mathcal{F}}\underline{f} \right )^-
\end{align*}$

因此

$\underline{\mathcal{F}}\underline{f}^- = \left( \underline{\mathcal{F}}\underline{f} \right)^-$

对离散信号连续进行两次DFT

$\begin{align*}\underline{\mathcal{F}}\underline{\mathcal{F}}\underline{f}&=\sum_{k=0}^{N-1}\left(\sum_{n=0}^{N-1}\underline{f}[n]\underline{\omega}^{-n}[k]\right)\underline{\omega}^{-k}\\
&=\sum_{n=0}^{N-1}\underline{f}[n]\left(\sum_{k=0}^{N-1}\underline{\omega}^{-n}[k]\omega^{-k}\right)\\
&=\sum_{n=0}^{N-1}\underline{f}[n]\left(\underline{\mathcal{F}}\underline{\omega}^{-n}\right)\\
&=\sum_{n=0}^{N-1}\underline{f}[n]\cdot N\underline{\delta_{-n}}\\
&=N\sum_{n=0}^{N-1}\underline{f}[n]\underline{\delta_{-n}}\\
&=N\sum_{n=0}^{N-1}\underline{f}[n]\left(\underline{\delta_n}\right)^-\\
&=N\left(\sum_{n=0}^{N-1}\underline{f}[n]\underline{\delta_n}\right)^-\qquad\left(\sum_{n=0}^{N-1}\underline{f}[n](\underline{\delta_n})^-[m]=\sum_{n=0}^{N-1}\underline{f}[n]\underline{\delta_n}[-m]\right)\\
&=N\left(\sum_{n=0}^{N-1}\underline{f}[n]\underline{\delta_n}[0],\sum_{n=0}^{N-1}\underline{f}[n]\underline{\delta_n}[1],...,\sum_{n=0}^{N-1}\underline{f}[n]\underline{\delta_n}[N-1]\right)^-
\end{align*}$

我们来分析一下$\displaystyle{\sum_{n=0}^{N-1}\underline{f}[n]\underline{\delta_n}[0]}$，其中$\underline{\delta_n}[m]=\begin{cases} 1 & \text{ , } m=n \\ 0 & \text{ , } m\neq n \end{cases}$，因此

$\begin{align*}\underline{\mathcal{F}}\underline{\mathcal{F}}\underline{f}
&=N\left(\sum_{n=0}^{N-1}\underline{f}[n]\underline{\delta_n}[0],\sum_{n=0}^{N-1}\underline{f}[n]\underline{\delta_n}[1],...,\sum_{n=0}^{N-1}\underline{f}[n]\underline{\delta_n}[N-1]\right)^-\\
&=N\left(\underline{f}[0],\underline{f}[1],...,\underline{f}[N-1] \right )^-\\
&=N\underline{f}^-
\end{align*}$

最终得

$\underline{\mathcal{F}}\underline{\mathcal{F}}\underline{f} = N\underline{f}^-$

[傅里叶变换及其应用学习笔记] 二十一. 离散傅里叶变换的矩阵定义，一些性质

原文：http://www.cnblogs.com/TaigaCon/p/5104133.html