# 离散傅里叶变换

（重定向自離散傅利葉轉換

## 定义

${\displaystyle {\hat {x}}[k]=\sum _{n=0}^{N-1}e^{-i{\frac {2\pi }{N}}nk}x[n]\qquad k=0,1,\ldots ,N-1.}$

${\displaystyle {\hat {x}}={\mathcal {F}}x}$

${\displaystyle x\left[n\right]={1 \over N}\sum _{k=0}^{N-1}e^{i{\frac {2\pi }{N}}nk}{\hat {x}}[k]\qquad n=0,1,\ldots ,N-1.}$

${\displaystyle x={\mathcal {F}}^{-1}{\hat {x}}}$

## 从连续到离散

${\displaystyle x_{discrete}(t)=x(t)\sum _{n=0}^{N-1}\delta (t-nT)=\sum _{n=0}^{N-1}x(nT)\delta (t-nT)}$

${\displaystyle {\hat {x}}_{discrete}(\omega )=\sum _{n=0}^{N-1}x(nT){\mathcal {F}}\delta (t-nT)=\sum _{n=0}^{N-1}x(nT)e^{-in\omega T}}$

${\displaystyle {\frac {1/T}{1/L}}=N}$

${\displaystyle {\hat {x}}[k]={\hat {x}}_{discrete}(\omega _{k})={\frac {1}{T}}\sum _{n=0}^{N-1}x[nT]e^{-i{\frac {2\pi }{N}}nk}}$

${\displaystyle T=1}$ ，将其归一化，就得到前面定义的离散傅里叶变换。因此，DFT就是先将信号在时域离散化，求其连续傅里叶变换后，再在频域离散化的结果。

## DFT与CFT

${\displaystyle {\mathcal {F}}x(t)={\hat {x}}(\omega )={\frac {1}{L}}\int _{0}^{L}x(t)e^{-i\omega t}dt}$

${\displaystyle {\hat {x}}(\omega _{k})={\frac {1}{L}}\int _{0}^{L}x(t)e^{-i\omega _{k}t}dt}$

${\displaystyle {\hat {x}}(\omega _{k})\approx {\frac {1}{L}}\sum _{n=0}^{N-1}x[n]e^{-i\omega _{k}nT}T={\frac {1}{N}}{\hat {x}}[k]}$

• 时域采样必须满足采样定理
• 离散傅里叶变换的处理对象是时限的

## DFT与DTFT

${\displaystyle {\hat {x}}(e^{i\omega })=\sum _{n=0}^{N-1}x[n]e^{-in\omega }}$

${\displaystyle {\hat {x}}(e^{i\omega })}$ 在离散的频点${\displaystyle \{\omega _{k}=k{\frac {2\pi }{N}}\}_{0\leq k 上采样

${\displaystyle {\hat {x}}[k]={\hat {x}}(e^{i\omega _{k}})=\sum _{n=0}^{N-1}x[n]e^{-i{\frac {2\pi }{N}}kn}\qquad k=0,\ldots ,N-1}$

### 栅栏效应

${\displaystyle N}$ 点序列的DFT只能在有限的${\displaystyle N}$ 个频点上观察频谱，这相当于从栅栏的缝隙中观察景色，对于了解信号在整个频域上的特性是不够的。为了观察到其他频率的信息，需要对原信号${\displaystyle x[n]}$ 做一些处理，以便在不同的频点上采样。

${\displaystyle {\hat {x}}'[k]={\hat {x}}(e^{ik\omega '_{k}})=\sum _{n=0}^{N-1}x[n]e^{-i{\frac {2\pi }{M}}kn}}$

${\displaystyle {\hat {x}}'[k]=\sum _{n=0}^{M-1}x'[n]e^{-i{\frac {2\pi }{M}}kn}={\mathcal {F}}x'}$

### 频谱分辨率

${\displaystyle N}$ 点DFT的频谱分辨率是${\displaystyle 2\pi /N}$ 栅栏效应一节指出可以通过补零观察到更多的频点，但是这并不意味着补零能够提高真正的频谱分辨率。这是因为${\displaystyle x[n]}$ 实际上是${\displaystyle x(t)}$ 采样的主值序列，而将${\displaystyle x[n]}$ 补零得到的${\displaystyle x'[n]}$ 周期延拓之后与原来的序列并不相同，也不是${\displaystyle x(t)}$ 的采样。因此${\displaystyle {\hat {x}}'}$ ${\displaystyle {\hat {x}}}$ 是不同离散信号的频谱。对于补零至${\displaystyle M}$ 点的${\displaystyle x'}$ 的DFT，只能说它的分辨率${\displaystyle {\frac {2\pi }{M}}}$ 仅具有计算上的意义，${\displaystyle {\hat {x}}'}$ 并不是真正的、物理意义上的频谱。频谱分辨率的提高只能在满足采样定理的条件下增加时域采样长度来实现。

## 从空间的角度分析

${\displaystyle \langle x,y\rangle =\sum _{n=0}^{N-1}x[n]y^{*}\left[n\right]}$

${\displaystyle \{e_{k}[n]=e^{i{\frac {2\pi }{N}}kn}\}_{0\leq k

${\displaystyle x=\sum _{k=0}^{N-1}{\frac {\langle x,e_{k}\rangle }{\Vert e_{k}\Vert ^{2}}}e_{k}}$

${\displaystyle {\hat {x}}[k]=\langle x,e_{k}\rangle =\sum _{n=0}^{N-1}x[n]e^{-i{\frac {2\pi }{N}}kn}}$

${\displaystyle \|e_{k}\|^{2}=N}$

${\displaystyle x[n]={\frac {1}{N}}\sum _{k=0}^{N-1}{\hat {x}}[k]e^{i{\frac {2\pi }{N}}kn}}$

## DFT与圆周卷积

${\displaystyle x[n]={\tilde {x}}[n\mod N]\qquad y[n]={\tilde {y}}[n\mod N]}$

${\displaystyle (x\otimes y)[n]=\sum _{m=0}^{N-1}x[m]y[n-m]=\sum _{m=0}^{N-1}x[n-m]y[m]}$

${\displaystyle {L}x[n]=(x\otimes y)[n]}$

${\displaystyle e_{k}}$ 与y的圆周卷积为

${\displaystyle {L}e_{k}[n]=e_{k}[n]\cdot \sum _{m=0}^{N-1}y[m]e_{k}[-m]}$

${\displaystyle {\hat {y}}[k]=\sum _{m=0}^{N-1}y[m]e_{k}[-m]}$

## 性质

### 完全性

${\displaystyle {\mathcal {F}}:\mathbf {C} ^{N}\to \mathbf {C} ^{N}}$

### 正交性

${\displaystyle \sum _{n=0}^{N-1}\left(e^{{\frac {2\pi i}{N}}kn}\right)\left(e^{-{\frac {2\pi i}{N}}k'n}\right)=N~\delta _{kk'}}$

### 移位定理

${\displaystyle {\mathcal {F}}(\{x_{n}\})_{k}=X_{k}}$
${\displaystyle {\mathcal {F}}(\{x_{n}e^{{\frac {2\pi i}{N}}nm}\})_{k}=X_{k-m}}$

### 普朗歇尔定理与帕塞瓦尔定理

${\displaystyle \sum _{n=0}^{N-1}x_{n}y_{n}^{*}={\frac {1}{N}}\sum _{k=0}^{N-1}X_{k}Y_{k}^{*}}$

${\displaystyle \sum _{n=0}^{N-1}|x_{n}|^{2}={\frac {1}{N}}\sum _{k=0}^{N-1}|X_{k}|^{2}.}$

## 应用

DFT在诸多多领域中有着重要应用，下面仅是颉取的几个例子。需要指出的是，所有DFT的实际应用都依赖于计算离散傅里叶变换及其逆变换的快速算法，即快速傅里叶变换

### 长整数与多项式乘法

${\displaystyle \mathbf {c} =\mathbf {a} \otimes \mathbf {b} }$

${\displaystyle {\mathcal {F}}\mathbf {c} ={\mathcal {F}}\mathbf {a} \cdot {\mathcal {F}}\mathbf {b} }$

${\displaystyle \mathbf {c} ={\mathcal {F}}^{-1}({\mathcal {F}}\mathbf {a} \cdot {\mathcal {F}}\mathbf {b} )}$

### OFDM

OFDM（正交频分复用）在宽带无线通信中有重要的应用。这种技术将带宽分为N个等间隔的子载波，可以证明这些子载波相互正交。尤其重要的是，OFDM调制可以由IDFT实现，而解调可以由DFT实现。OFDM还利用DFT的移位性质，在每个帧头部加上循环前缀（Cyclic Prefix），使得只要信道延时小于循环前缀的长度，就能消除信道延时对传输的影响。

## 特殊例子

### 数论转换

${\displaystyle {\begin{bmatrix}{\underset {-}{F}}\end{bmatrix}}={\begin{bmatrix}{\underset {-}{\alpha ^{cr}}}\end{bmatrix}}{\begin{bmatrix}{\underset {-}{f}}\end{bmatrix}}}$

${\displaystyle c}$ ${\displaystyle r}$  各為 Column 與 Row 的指數(index), 令 ${\displaystyle C}$ ${\displaystyle R}$  各代表Column 與 Row 的總數，則${\displaystyle C=R=N}$ ${\displaystyle c\propto {\begin{Bmatrix}0,1,...,C-1\end{Bmatrix}},r\propto {\begin{Bmatrix}0,1,...,R-1\end{Bmatrix}}}$ .

${\displaystyle \alpha ^{1}=2\qquad (mod\quad 5)}$

${\displaystyle \alpha ^{2}=4\qquad (mod\quad 5)}$

${\displaystyle \alpha ^{3}=3\qquad (mod\quad 5)}$

${\displaystyle \alpha ^{4}=1\qquad (mod\quad 5)}$

${\displaystyle {\begin{bmatrix}F(0)\\F(1)\\F(2)\\F(3)\end{bmatrix}}={\begin{bmatrix}1&1&1&1\\1&2&4&3\\1&4&1&4\\1&3&4&2\end{bmatrix}}{\begin{bmatrix}f(0)\\f(1)\\f(2)\\f(3)\end{bmatrix}}}$

## 参考文献

1. Oppenheim, Alan V.; Schafer, R. W.; and Buck, J. R., (1999). Discrete-time signal processing, Upper Saddle River, N.J. : Prentice Hall. ISBN 0137549202
2. Mallat, S., A Wavelet Tour of Signal Processing, Second Edition, Academic Press, ISBN 0-12-466606-x
3. Gill, J., Fourier Transform and Its Applications[1]