离散时间信号处理 Ch08：离散傅里叶变换

文章发布时间:

2026-07-23

最后更新时间:

2026-07-24

文章总字数:

3.3k

预计阅读时间:

17 分钟

本文是“离散时间信号处理”系列的第 08 章，主题为“离散傅里叶变换”。

上一篇：滤波器设计方法 · 下一篇：离散傅里叶变换的计算

离散傅里叶变换

周期序列的离散傅里叶级数

周期序列$\tilde{x}[n]$的傅里叶级数表示
\[ \tilde{x}[n]=\frac{1}{N}\sum_{k=0}^{N-1}\tilde{X}[k]e^{j(2\pi/N)kn} \]

傅里叶级数的系数
\[ \tilde{X}[k]=\sum_{n=0}^{N-1}\tilde{x}[n]e^{-j(2\pi/N)kn} \]

($\tilde{x}[n]$和$\tilde{X}[k]$均是周期为$N$的周期序列)

傅里叶级数系数的推导
\[ \begin{aligned} \sum_{n=0}^{N-1}\tilde{x}[n]e^{-j(2\pi/N)rn}&=\sum_{n=0}^{N-1}\frac{1}{N}\sum_{k=0}^{N-1}\tilde{X}[k]e^{j(2\pi/N)(k-r)n}\\ &=\sum_{k=0}^{N-1}\tilde{X}[k]\left[\frac{1}{N}\sum_{n=0}^{N-1}e^{j(2\pi/N)(k-r)n}\right]\\ \end{aligned} \]

而复指数具有正交性, 则
\[ \frac{1}{N}\sum_{n=0}^{N-1}e^{j(2\pi/N)(k-r)n}= \begin{cases} 1 & k-r=mN\text{, }m\text{为整数}\\ 0 & \text{其他} \end{cases} \]

因此可以得到
\[ \sum_{n=0}^{N-1}\tilde{x}[n]e^{-j(2\pi/N)rn}=\tilde{X}[r] \]

周期序列的离散傅里叶级数(DFS)
\[ W_N=e^{-j(2\pi/N)}\text{ (旋转因子)} \]

分析式
\[ \tilde{X}[k]=\sum_{n=0}^{N-1}\tilde{x}[n]W_N^{kn} \]

综合式
\[ \tilde{x}[n]=\frac{1}{N}\sum_{k=0}^{N-1}\tilde{X}[k]W_N^{-kn} \]

周期脉冲串 $\tilde{x}[n]$ 定义为
\[ \tilde{x}[n]=\displaystyle\sum\limits_{r=-\infty}^{\infty}\delta[n-rN]= \begin{cases} 1 & n=rN\text{, }r\text{为任意整数}\\ 0 & \text{其他} \end{cases} \]
其离散傅里叶级数如下。

DFS系数
\[ \tilde{X}[k]=\sum_{n=0}^{N-1}\delta[n]W_N^{kn}=W_N^0=1 \]

则离散傅里叶级数表示式为
\[ \tilde{x}[n]=\frac{1}{N}\sum_{k=0}^{N-1}W_N^{-kn}=\frac{1}{N}\sum_{k=0}^{N-1}e^{j(2\pi/N)kn} \]

DFS系数为周期脉冲串$\tilde{Y}[k]=\displaystyle\sum\limits_{r=-\infty}^{\infty}N\delta[k-rN]$的序列
\[ \tilde{y}[n]=\frac{1}{N}\sum_{k=0}^{N-1}N\delta[k]W_N^{-kn}=W_N^{-0}=1 \]

离散傅里叶级数的性质

线性

若$\tilde{x}_1[n]\stackrel{\mathcal{DFS}}{\longleftrightarrow}\tilde{X}_1[k]$, $\tilde{x}_2[n]\stackrel{\mathcal{DFS}}{\longleftrightarrow}\tilde{X}_2[k]$, 则
\[ a\tilde{x}_1[n]+b\tilde{x}_2[n]\stackrel{\mathcal{DFS}}{\longleftrightarrow}a\tilde{X}_1[k]+b\tilde{X}_2[k] \]

序列的移位

(1) 时域移位
\[ \tilde{x}[n-m]\stackrel{\mathcal{DFS}}{\longleftrightarrow}W_N^{km}\tilde{X}[k] \]

(2) 频域移位
\[ W_N^{-nl}\tilde{x}[n]\stackrel{\mathcal{DFS}}{\longleftrightarrow}\tilde{X}[k-l] \]

对偶性

若$\tilde{x}[n]\stackrel{\mathcal{DFS}}{\longleftrightarrow}\tilde{X}[k]$, 则
\[ \tilde{X}[n]\stackrel{\mathcal{DFS}}{\longleftrightarrow}N\tilde{x}[-k] \]

对称性
\[ \tilde{x}_e[n]=\frac{1}{2}(\tilde{x}[n]+\tilde{x}^*[-n])=\tilde{x}_e^*[-n]\quad\text{(共轭对称序列)} \]
\[ \tilde{x}_o[n]=\frac{1}{2}(\tilde{x}[n]-\tilde{x}^*[-n])=-\tilde{x}_o^*[-n]\quad\text{(共轭反对称序列)} \]

周期序列 DFS的系数

$\tilde{x}[n]$ $\tilde{X}[k]$
$\tilde{x}^*[n]$ $\tilde{X}^*[-k]$
$\tilde{x}[-n]$ $\tilde{X}[-k]$
$\tilde{x}^*[-n]$ $\tilde{X}^*[k]$
$\mathcal{R}e\{\tilde{x}[n]\}$ $\tilde{X}_e[k]$
$j\mathcal{I}m\{\tilde{x}[n]\}$ $\tilde{X}_o[k]$
$\tilde{x}_e[n]$ $\mathcal{R}e\{\tilde{X}[k]\}$
$\tilde{x}_o[n]$ $j\mathcal{I}m\{\tilde{X}[k]\}$

当$\tilde{x}[n]$为实数时
\[ \begin{cases} \tilde{X}[k]=\tilde{X}^*[-k]\\ \mathcal{R}e\{\tilde{X}[k]\}=\mathcal{R}e\{\tilde{X}[-k]\}\\ \mathcal{I}m\{\tilde{X}[k]\}=-\mathcal{I}m\{\tilde{X}[-k]\}\\ |\tilde{X}[k]|=|\tilde{X}[-k]|\\ \angle\tilde{X}[k]=-\angle\tilde{X}[-k] \end{cases} \]

周期序列	DFS的系数
\(\tilde{x}[n]\)	\(\tilde{X}[k]\)
\(\tilde{x}^*[n]\)	\(\tilde{X}^*[-k]\)
\(\tilde{x}[-n]\)	\(\tilde{X}[-k]\)
\(\tilde{x}^*[-n]\)	\(\tilde{X}^*[k]\)
\(\mathcal{R}e\{\tilde{x}[n]\}\)	\(\tilde{X}_e[k]\)
\(j\mathcal{I}m\{\tilde{x}[n]\}\)	\(\tilde{X}_o[k]\)
\(\tilde{x}_e[n]\)	\(\mathcal{R}e\{\tilde{X}[k]\}\)
\(\tilde{x}_o[n]\)	\(j\mathcal{I}m\{\tilde{X}[k]\}\)

周期卷积

若$\tilde{x}_1[n]\stackrel{\mathcal{DFS}}{\longleftrightarrow}\tilde{X}_1[k]$, $\tilde{x}_2[n]\stackrel{\mathcal{DFS}}{\longleftrightarrow}\tilde{X}_2[k]$, 则周期卷积
\[ \tilde{x}_1[n]\circledast\tilde{x}_2[n]=\sum_{m=0}^{N-1}\tilde{x}_1[m]\tilde{x}_2[n-m] \]

周期卷积只需要在$0\leq m\leq N-1$上求和, 然后将所得结果周期延拓即可.
\[ \tilde{x}_1[n]\circledast\tilde{x}_2[n]\stackrel{\mathcal{DFS}}{\longleftrightarrow}\tilde{X}_1[k]\tilde{X}_2[k] \]
\[ \tilde{x}_1[n]\tilde{x}_2[n]\stackrel{\mathcal{DFS}}{\longleftrightarrow}\frac{1}{N}\tilde{X}_1[k]\circledast\tilde{X}_2[k] \]

周期序列的傅里叶变换

周期信号$\tilde{x}[n]$的傅里叶变换
\[ \tilde{X}(e^{j\omega})=\sum_{k=-\infty}^{\infty}\frac{2\pi}{N}\tilde{X}[k]\delta\left(\omega-\frac{2\pi k}{N}\right) \]

周期脉冲串$\tilde{p}[n]=\displaystyle\sum\limits_{r=-\infty}^{\infty}\delta[n-rN]$的傅里叶变换

\[ \tilde{P}(e^{j\omega})=\sum_{k=-\infty}^{\infty}\frac{2\pi}{N}\delta\left(\omega-\frac{2\pi k}{N}\right) \]

时域周期延拓$\stackrel{\mathcal{DFS}}{\longrightarrow}$频域采样的推导

给定有限长序列
\[ x[n]= \begin{cases} \tilde{x}[n] & 0\leq n\leq N-1\\ 0 & \text{其他} \end{cases} \]

$\tilde{x}[n]$是由有限长序列$x[n]$以$N$为周期进行周期延拓得到的, 则有
\[ \tilde{x}[n]=x[n]*p[n]=x[n]*\sum_{r=-\infty}^{\infty}\delta[n-rN] \]

两边同时进行傅里叶变换
\[ \begin{aligned} \tilde{X}(e^{j\omega})&=X(e^{j\omega})\cdot\sum_{k=-\infty}^{\infty}\frac{2\pi}{N}\delta\left(\omega-\frac{2\pi k}{N}\right)\\ &=\sum_{k=-\infty}^{\infty}\frac{2\pi}{N}X(e^{j(2\pi/N)k})\delta\left(\omega-\frac{2\pi k}{N}\right) \end{aligned} \]

因此
\[ \tilde{X}[k]=X(e^{j(2\pi/N)k})=X(e^{j\omega})\big|_{\omega=2\pi k/N}\quad\text{(以}\frac{2\pi}{N}\text{为间隔采样)} \]

频域采样$\stackrel{\mathcal{IDFS}}{\longrightarrow}$时域周期延拓的推导

考虑一个非周期序列$x[m]$, 其傅里叶变换为$X(e^{j\omega})$, 序列$\tilde{X}[k]$是通过对$X(e^{j\omega})$在$\omega_k=\dfrac{2\pi k}{N}$频率处采样得到的, 即
\[ X(e^{j\omega})=\sum_{m=-\infty}^{\infty}x[m]e^{-j\omega m} \]
\[ \tilde{X}[k]=X(e^{j\omega})\big|_{\omega=2\pi k/N}=\sum_{m=-\infty}^{\infty}x[m]e^{-j(2\pi k/N)m} \]

假设$\tilde{X}[k]$是序列$\tilde{x}[n]$的傅里叶级数的系数, 则$\tilde{x}[n]$可表示为
\[ \begin{aligned} \tilde{x}[n]&=\frac{1}{N}\sum_{k=0}^{N-1}\tilde{X}[k]e^{j(2\pi/N)kn}\\ &=\frac{1}{N}\sum_{k=0}^{N-1}\left[\sum_{m=-\infty}^{\infty}x[m]e^{-j(2\pi/N)km}\right]e^{j(2\pi/N)kn}\\ &=\frac{1}{N}\sum_{m=-\infty}^{\infty}x[m]\sum_{k=0}^{N-1}e^{-j(2\pi/N)k(m-n)}\\ &=\sum_{m=-\infty}^{\infty}x[m]\left[\frac{1}{N}\sum_{k=0}^{N-1}W_N^{-k(n-m)}\right]\\ &=\sum_{m=-\infty}^{\infty}x[m]\sum_{r=-\infty}^{\infty}\delta[n-m-rN]\\ &=\sum_{r=-\infty}^{\infty}x[n-rN]\\ &=x[n]*\sum_{r=-\infty}^{\infty}\delta[n-rN]\quad\text{(以}N\text{为周期延拓)} \end{aligned} \]

有限长序列的离散傅里叶变换

有限长序列$x[n]$和周期序列$\tilde{x}[n]$的关系
\[ \tilde{x}[n]=\sum_{r=-\infty}^{\infty}x[n-rN]=x[((n))_N] \]
\[ x[n]= \begin{cases} \tilde{x}[n] & 0\leq n\leq N-1\\ 0 & \text{其他} \end{cases} \]

离散傅里叶变换$X[k]$和DFS系数$\tilde{X}[k]$的关系
\[ \tilde{X}[k]=X[((k))_N] \]
\[ X[k]= \begin{cases} \tilde{X}[k] & 0\leq k\leq N-1\\ 0 & \text{其他} \end{cases} \]

离散傅里叶变换(DFT)
\[ W_N=e^{-j(2\pi/N)}\text{ (旋转因子)} \]

分析式
\[ X[k]=\sum_{n=0}^{N-1}x[n]W_N^{kn},0\leq k\leq N-1 \]

综合式
\[ x[n]=\frac{1}{N}\sum_{k=0}^{N-1}X[k]W_N^{-kn},0\leq n\leq N-1 \]

离散傅里叶变换的性质

线性

若$x_1[n]\stackrel{\mathcal{DFT}}{\longleftrightarrow}X_1[k]$, $x_2[n]\stackrel{\mathcal{DFT}}{\longleftrightarrow}X_2[k]$, 则
\[ ax_1[n]+bx_2[n]\stackrel{\mathcal{DFT}}{\longleftrightarrow}aX_1[k]+bX_2[k] \]

序列的循环移位

有限长序列的循环移位

\[ x[((n-m))_N],0\leq n\leq N-1\stackrel{\mathcal{DFT}}{\longleftrightarrow}e^{-j(2\pi k/N)m}X[k] \]

对称性

周期共轭对称分量
\[ \begin{aligned} x_{ep}[n]&=\tilde{x}_e[n],0\leq n\leq N-1\\ &=\frac{1}{2}\{x[((n))_N]+x^*[((-n))_N]\},0\leq n\leq N-1\\ &=\begin{cases} \dfrac{1}{2}\{x[n]+x^*[N-n]\} & 1\leq n\leq N-1\\[2pt] \mathcal{R}e\{x[0]\} & n=0 \end{cases}\\ &=\{x_e[n]+x_e[n-N]\},0\leq n\leq N-1 \end{aligned} \]

周期反共轭对称分量
\[ \begin{aligned} x_{op}[n]&=\tilde{x}_o[n],0\leq n\leq N-1\\ &=\frac{1}{2}\{x[((n))_N]-x^*[((-n))_N]\},0\leq n\leq N-1\\ &=\begin{cases} \dfrac{1}{2}\{x[n]-x^*[N-n]\} & 1\leq n\leq N-1\\[2pt] j\mathcal{I}m\{x[0]\} & n=0 \end{cases}\\ &=\{x_o[n]+x_o[n-N]\},0\leq n\leq N-1 \end{aligned} \]

有限序列 $N$点DFT

$x[n]$ $X[k]$
$x^*[n]$ $X^*[((-k))_N]$
$x[((-n))_N]$ $X[((-k))_N]$
$x^*[((-n))_N]$ $X^*[k]$
$\mathcal{R}e\{x[n]\}$ $X_{ep}[k]$
$j\mathcal{I}m\{x[n]\}$ $X_{op}[k]$
$x_{ep}[n]$ $\mathcal{R}e\{X[k]\}$
$x_{op}[n]$ $j\mathcal{I}m\{X[k]\}$

当$\tilde{x}[n]$为实数时
\[ \begin{cases} X[k]=X^*[((-k))_N]\\ \mathcal{R}e\{X[k]\}=\mathcal{R}e\{X[((-k))_N]\}\\ \mathcal{I}m\{X[k]\}=-\mathcal{I}m\{X[((-k))_N]\}\\ |X[k]|=|X[((-k))_N]|\\ \angle X[k]=-\angle X[((-k))_N] \end{cases} \]

有限序列	\(N\)点DFT
\(x[n]\)	\(X[k]\)
\(x^*[n]\)	\(X^*[((-k))_N]\)
\(x[((-n))_N]\)	\(X[((-k))_N]\)
\(x^*[((-n))_N]\)	\(X^*[k]\)
\(\mathcal{R}e\{x[n]\}\)	\(X_{ep}[k]\)
\(j\mathcal{I}m\{x[n]\}\)	\(X_{op}[k]\)
\(x_{ep}[n]\)	\(\mathcal{R}e\{X[k]\}\)
\(x_{op}[n]\)	\(j\mathcal{I}m\{X[k]\}\)

对偶性

若$x[n]\stackrel{\mathcal{DFT}}{\longleftrightarrow}X[k]$, 则
\[ X[n]\stackrel{\mathcal{DFT}}{\longleftrightarrow}Nx[((-k))_N],0\leq k\leq N-1 \]

循环卷积

若$x_1[n]\stackrel{\mathcal{DFT}}{\longleftrightarrow}X_1[k]$, $x_2[n]\stackrel{\mathcal{DFT}}{\longleftrightarrow}X_2[k]$, 则循环卷积
\[ \begin{aligned} x_1[n]\mathbin{\text{Ⓝ}}x_2[n]&=\sum_{m=0}^{N-1}\tilde{x}_1[m]\tilde{x}_2[n-m],0\leq n\leq N-1\\ &=\sum_{m=0}^{N-1}x_1[((m))_N]x_2[((n-m))_N],0\leq n\leq N-1\\ &=\sum_{m=0}^{N-1}x_1[m]x_2[((n-m))_N],0\leq n\leq N-1 \end{aligned} \]

且有
\[ x_1[n]\mathbin{\text{Ⓝ}}x_2[n]\stackrel{\mathcal{DFT}}{\longleftrightarrow}X_1[k]X_2[k] \]
\[ x_1[n]x_2[n]\stackrel{\mathcal{DFT}}{\longleftrightarrow}\frac{1}{N}X_1[k]\mathbin{\text{Ⓝ}}X_2[k] \]

帕斯瓦尔关系式

\[ \sum_{n=0}^{N-1}|x[n]|^2=\frac{1}{N}\sum_{k=0}^{N-1}|X[k]|^2 \]

用离散傅里叶变换实现线性卷积

循环卷积与线性卷积的关系

一个$L$点长的序列$x_1[n]$和一个$P$点长的序列$x_2[n]$的线性卷积$x_3[n]$为
\[ x_3[n]=\sum_{m=-\infty}^{\infty}x_1[m]x_2[n-m] \]

$x_1[n]$和$x_2[n]$的循环卷积$x_{3p}[n]$为
\[ \begin{aligned} x_{3p}[n]&=x_1[n]\mathbin{\text{Ⓝ}}x_2[n]\\ &=\begin{cases} \displaystyle\sum\limits_{r=-\infty}^{\infty}x_3[n-rN] & 0\leq n\leq N-1\\[2pt] 0 & \text{其他} \end{cases} \end{aligned} \]

(1) 两个有限长序列的循环卷积等于有时间混叠的两个序列的线性卷积.

(2) 若DFT的长度$N$满足$N\geq L+P-1$, 则$X_1[k]X_2[k]$对应的循环卷积等于$X_1(e^{j\omega})X_2(e^{j\omega})$对应的线性卷积.

用DFT实现线性时不变系统

(1) 一个$L_\text{总}$点输入序列$x[n]$和一个$P$点脉冲响应$h[n]$的线性卷积$y[n]$是长度为$(L_\text{总}+P-1)$的有限长序列.

(2) 为了使循环卷积等于线性卷积, 循环卷积的长度至少为$(L_\text{总}+P-1)$点, 因此要计算的DFT也必须有相同的长度, 即对$x[n]$和$h[n]$进行补零.

(3) 块卷积: 将输入序列$x[n]$分割成长度为$L$的段, 然后每段信号与$h[n]$进行卷积, 再将滤波后的信号段衔接在一起, 每一块的线性滤波可用DFT来实现.

$有限长脉冲响应$h[n]$和未定义长度的信号$x[n]$$
有限长脉冲响应$h[n]$和未定义长度的信号$x[n]$

重叠相加法

将序列$x[n]$表示成长度为$L$的平移有限长序列之和
\[ x[n]=\sum_{r=0}^{\infty}x_r[n-rL] \]

其中
\[ x_r[n]= \begin{cases} x[n+rL] & 0\leq n\leq L-1\\ 0 & \text{其他} \end{cases} \]

则序列$y[n]$可表示为
\[ y[n]=x[n]*h[n]=\sum_{r=0}^{\infty}y_r[n-rL] \]

其中
\[ y_r[n]=x_r[n]*h[n] \]

$(a) 把$x[n]$分解成长度为$L$的不重叠序列段; (b) 每段与$h[n]$卷积的结果$
(a) 把$x[n]$分解成长度为$L$的不重叠序列段; (b) 每段与$h[n]$卷积的结果

(1) 每一项$y_r[n]$的长度为$(L+P-1)$, DFT的点数需要满足$N\geq L+P-1$.

(2) 每个输入段的开头与相邻段间隔$L$点, 并且每个滤波后的序列段长度为$(L+P-1)$, 所以滤波后的序列段的非零点将重叠$(P-1)$点.

(3) 计算$L_\text{总}$点输入序列的卷积需要分的段数为$\dfrac{L_\text{总}}{L}$.

重叠保留法

将序列$x[n]$分成长度为$L$的序列段, 每个输入段与先前的序列段重叠$(P-1)$点
\[ x[n]=\sum_{r=0}^{\infty}x_r[n-rL] \]

其中
\[ x_r[n]=x[n+r(L-P+1)-P+1],0\leq n\leq L-1 \]

则序列$y[n]$可表示为
\[ y[n]=x[n]*h[n]=\sum_{r=0}^{\infty}y_r[n-r(L-P+1)+P-1] \]

其中
\[ y_r[n]= \begin{cases} y_{rp}[n] & P-1\leq n\leq L-1\\ 0 & \text{其他} \end{cases} \]

$(a) 把$x[n]$分解成相互重叠的长度为$L$的序列段；(b) 每段与$h[n]$卷积的结果, 图中表示出为了得出线性卷积对过滤后的每段序列应当去掉的部分$
(a) 把$x[n]$分解成相互重叠的长度为$L$的序列段；(b) 每段与$h[n]$卷积的结果, 图中表示出为了得出线性卷积对过滤后的每段序列应当去掉的部分

(1) 每一项是一个$P$点脉冲响应$h[n]$与一个$L$点的序列段$x_r[n]$的$L$点循环卷积($N=L$).

(2) 每个输入段与先前的序列段重叠$(P-1)$点, 因此每个接续的输入序列包括$(L-P+1)$个新点, 并且从先前的序列段保留下来$(P-1)$个点, 每个输出序列段去掉区间$0\leq n\leq P-2$中的部分.

(3) 计算$L_\text{总}$点输入序列的卷积需要分的段数为$\dfrac{L_\text{总}+P-1}{L-P+1}$.

上一篇：滤波器设计方法 · 下一篇：离散傅里叶变换的计算

≡