DFT在零点
$underline{mathcal{F}}underline{f}(0) = displaystyle{ sum_{n=0}^{N-1}underline{f}[n]e^{-2pi ifrac{n0}{N}} = sum_{n=0}^{N-1}underline{f}[n] }$
还记得傅里叶变换在零点处也有类似的式子
$mathcal{F}f(0) = displaystyle{ int_{-infty}^{infty}f(t)e^{-2pi 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 = 1cdot 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} = 1cdot underline{omega}^{-k} = underline{omega}^{-k}}$
因此
$underline{mathcal{F}}underline{delta_k} = underline{omega}^{-k}$
对$underline{omega}^{k}$进行DFT
$egin{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^{2pi ifrac{kn}{N}}cdot e^{-2pi ifrac{mn}{N}}\
&=underline{omega}^kcdotunderline{omega}^m\
&=egin{cases}
0 & ext{ , } k
eq m \
N & ext{ , } k= m
end{cases}
end{align*}$
因此
$underline{mathcal{F}}underline{omega}^k = (underbrace{0,0,...,0,N}_{k entries},0,...,0) = Nunderline{delta_k}$
DFT矩阵
1. DFT矩阵的定义
令$omega = e^{2pi ifrac{1}{N}}$，请注意，这里的$omega$没有下划线，并不是离散信号。则有
$omega^{-mn} = e^{-2pi ifrac{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^{-} ight)^{mn}$相乘，$mn$为该矩阵的$m$行$n$列
$egin{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}
egin{pmatrix}
underline{f}[0]\
underline{f}[1]\
underline{f}[2]\
vdots\
underline{f}[N-1]
end{pmatrix}
=
egin{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 imes 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}}^{*} =
egin{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}
egin{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}$
$=
egin{pmatrix}
underline{omega}^0cdotunderline{omega}^0 &underline{omega}^1cdotunderline{omega}^0 &underline{omega}^2cdotunderline{omega}^0 &... &underline{omega}^{N-1}cdotunderline{omega}^0 \
underline{omega}^0cdotunderline{omega}^1 &underline{omega}^1cdotunderline{omega}^1 &underline{omega}^2cdotunderline{omega}^1 &... &underline{omega}^{N-1}cdotunderline{omega}^1 \
underline{omega}^0cdotunderline{omega}^2 &underline{omega}^1cdotunderline{omega}^2 &underline{omega}^2cdotunderline{omega}^2 &... &underline{omega}^{N-1}cdotunderline{omega}^2 \
vdots &vdots &vdots &... & vdots\
underline{omega}^0cdotunderline{omega}^{N-1} &underline{omega}^1cdotunderline{omega}^{N-1} &underline{omega}^2cdotunderline{omega}^{N-1} &... &underline{omega}^{N-1}cdotunderline{omega}^{N-1} \
end{pmatrix}qquadqquadqquadqquad$
$=egin{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}^lcdotunderline{omega}^k = egin{cases}
0 & ext{ , } k
eq l \
N & ext{ , } k= l
end{cases}
ight)qquadqquadqquadqquad$
$= NI qquad (I is N imes N identity matrix)qquadqquadqquadqquadqquadqquadqquadqquadqquad$
因此
$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} ight)_{mn} = frac{1}{N}omega^{mn}$
这个结果同样也能运用推导DFT矩阵的过程得出。
4. DFT矩阵运算复杂度
运算复杂度这里是值矩阵运算中乘法运算的数目，$underline{mathcal{F}}underline{f}$的每一项运算会花费$N$个乘法运算，其中共有$N$项，即运算复杂度为$N imes N$，用$O(N^2)$表示。
FFT算法的目的就是为了减少DFT的运算复杂度，FFT的复杂度为$O(NlogN)$。
DFT特性
我们上节课遗留下来了，关于DFT特性的讨论：输入和输出都是周期为$N$的周期离散函数。得出这个结论是因为离散复指数具有周期性。
1. 输入与输出离散信号周期性的证明
证明过程如下：
$underline{omega}[m] = e^{2pi i frac{m}{N}}$
$underline{omega}[m+N] = e^{2pi ifrac{m+N}{N}} = e^{2pi ifrac{m}{N}}cdot e^{2pi i}=e^{2pi ifrac{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] ight)$
它的反转为
$underline{f}^- = left( underline{f}[0],underline{f}[-1],underline{f}[-2],…,underline{f}[-(N-1)] ight)$
离散复指数$underline{omega}$的反转为
$underline{omega}^- = left( 1,e^{-2pi ifrac{1}{N}},e^{-2pi ifrac{2}{N}},…,e^{-2pi ifrac{N-1}{N}} ight) = underline{omega}^{-1}$
同理有
$left( underline{omega}^n ight)^- = underline{omega}^{-n} qquad left( underline{omega}^{-n} ight)^- = underline{omega}^{n}$
2. DFT对偶性讨论
对离散信号$underline{f}$的反转$underline{f}^-$进行DFT
$egin{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}^1underline{f}[l]underline{omega}^{l-N} qquad (letting l=N-n)\
&=sum_{l=N}^1underline{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}
ight )^- 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
ight)\
&=left(underline{mathcal{F}}underline{f}
ight )^-
end{align*}$
因此
$underline{mathcal{F}}underline{f}^- = left( underline{mathcal{F}}underline{f} ight)^-$
对离散信号连续进行两次DFT
$egin{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]
ight)underline{omega}^{-k}\
&=sum_{n=0}^{N-1}underline{f}[n]left(sum_{k=0}^{N-1}underline{omega}^{-n}[k]underline{omega}^{-k}
ight)\
&=sum_{n=0}^{N-1}underline{f}[n]left(underline{mathcal{F}}underline{omega}^{-n}
ight)\
&=sum_{n=0}^{N-1}underline{f}[n]cdot Nunderline{delta_{-n}}\
&=Nsum_{n=0}^{N-1}underline{f}[n]underline{delta_{-n}}\
&=Nsum_{n=0}^{N-1}underline{f}[n]left(underline{delta_n}
ight)^-\
&=Nleft(sum_{n=0}^{N-1}underline{f}[n]underline{delta_n}
ight)^-qquadleft(sum_{n=0}^{N-1}underline{f}[n](underline{delta_n})^-[m]=sum_{n=0}^{N-1}underline{f}[n]underline{delta_n}[-m]
ight)\
&=Nleft(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]
ight)^-
end{align*}$
我们来分析一下$displaystyle{sum_{n=0}^{N-1}underline{f}[n]underline{delta_n}[0]}$，其中$underline{delta_n}[m]=egin{cases} 1 & ext{ , } m=n \ 0 & ext{ , } m eq n end{cases}$，因此
$egin{align*}underline{mathcal{F}}underline{mathcal{F}}underline{f}
&=Nleft(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]
ight)^-\
&=Nleft(underline{f}[0],underline{f}[1],...,underline{f}[N-1]
ight )^-\
&=Nunderline{f}^-
end{align*}$
最终得
$underline{mathcal{F}}underline{mathcal{F}}underline{f} = Nunderline{f}^-$