【线性卷积的DFT算法--重叠相加法和重叠保留法】-Toy模板网

这篇具有很好参考价值的文章主要介绍了【线性卷积的DFT算法--重叠相加法和重叠保留法】。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前言

在复习数字信号处理课程中，有关线性卷积的DFT算法的重叠相加法和重叠保留法根据教材不甚理解，网络上未找到便于手算的例题讲解过程，故在学习之后两种方法分别用两个例题详细过程用于理解，写下此文章用于其他人查找和自己学习。

一、重叠相加法

步骤

1、将长序列 $x [n]$ 拆分成多个短序列
$x[n]=\sum_{k}x_k[n-kL]$
$x_k[n]$ 长度为 $L,L\ll N_x$
$\begin{equation} x_k(n)=\left\{ \begin{aligned} &x[n+kL]\quad &n=0,1,2,...,L-1\\ &0\quad &其他\\ \end{aligned} \right . \nonumber \end{equation}$
2、重叠相加
$\begin{equation} \begin{split} y[n]&=(\sum_k x_k[n-kL])\otimes h[n]\\ &=\sum_k x_k[n-kL]\otimes h[n]\\ &=\sum_k y_k[n-kL] \end{split} \nonumber \end{equation}$

例题

例：计算序列 $x [n]$ 与序列 $h [n]$ 的线性卷积和，其中
$x[n]=\left\{1,2,3,2,1,0,1,2,2,1,1,1 \right\},h[n]=\left\{ 1,2,1 \right\}$

解:序列分解，用 $x [n]$ 做分解

% Matlab代码
x = [1 2 3 2 1 0 1 2 2 1 1 1];
h = [1 2 1];
x1=[1 2 3 2 0 0 0 0 0 0 0 0] ;
x2=[0 0 0 0 1 0 1 2 0 0 0 0];
x3=[0 0 0 0 0 0 0 0 2 1 1 1];
xh1 = conv(x1, h); % [1 4 8 10 7 2 0 0 0 0 0 0 0 0]
xh2 = conv(x2, h); % [0 0 0 0 1 2 2 4 5 2 0 0 0 0]
xh3 = conv(x3, h); % [0 0 0 0 0 0 0 0 2 5 5 4 3 1]
y=conv(x,h); % [1 4 8 10 8 4 2 4 7 7 5 4 3 1]

分别将分解出的序列与 $h [n]$ 作线性卷积，然后相加得到结果。

二、重叠保留法

步骤

1、将长序列 $x [n]$ 拆分成多个短序列
$x[n]=\sum_k x_k[n-kL]$
$x_k[n]$ 长度为 $L，L\ge M,M为h[n]的长度$
$\begin{equation} x_k(n)=\left\{ \begin{aligned} &x[n+k(L-M+1)]\quad &n=0,1,2,...,L-1\\ &0\quad &其他\\ \end{aligned} \right . \nonumber \end{equation}$
2、重叠保留圆周卷积 $x_k[n] \normalsize{\textcircled{\scriptsize{L }}}\normalsize h[n]$ 的后 $L - M + 1$ 点。原因是 $L$ 点序列与 $M$ 点序列圆周卷积后，前 $M - 1$ 点发生了混叠。
$w_k[n]=x_k[n] \normalsize{\textcircled{\scriptsize{L }}}\normalsize h[n]$
$\begin{equation} y[n]=\sum_k y_k[n-kL],y_k[n]=\left\{ \begin{aligned} &0\quad &n=0,1,2,...,L-1\\ &w_k[n]\quad &M-1\le n\le L-1\\ \end{aligned} \right . \nonumber \end{equation}$

例题

例：计算序列 $x [n]$ 与序列 $h [n]$ 的线性卷积和，其中
$x[n]=\left\{1,2,3,2,1,0,1,2,2,1,1,1 \right\},h[n]=\left\{ 1,2,1 \right\}$

解：序列分解（以 $x [n]$ 为例）

% Matlab代码
x = [1 2 3 2 1 0 1 2 2 1 1 1];
h = [1 2 1]; H = fft(h,6);
x1=[0 0 1 2 3 2];
x2=[3 2 1 0 1 2];
x3=[1 2 2 1 1 1];
x4=[1 1 0 0 0 0];
X1=fft(x1,6); Y1=X1.*H;
X2=fft(x2,6); Y2=X2.*H;
X3=fft(x3,6); Y3=X3.*H;
X4=fft(x4,6); Y4=X4.*H;
y1=ifft(Y1,6);y2=ifft(Y2,6);
y3=ifft(Y3,6);y4=ifft(Y4,6);

即分解成 $x_1[n]=\left\{0,0,1,2,3,2 \right\},x_2[n]=\left\{3,2,1,0,1,2 \right\},x_3[n]=\left\{1,2,2,1,1,1 \right\},x_4[n]=\left\{1,1,0,0,0,0 \right\}$
如此分解是因为选取 $L=6\ge M$ ,前 $M - 1$ 即2点发生混叠，保留后4点，于是在初始选取时需要在前面补2个零，弥补混叠后丢失的值。
计算有
$x_1[n] \normalsize{\textcircled{\scriptsize{6 }}}\normalsize h[n]=\left\{7,2,1,4,8,10 \right\}\\ x_2[n] \normalsize{\textcircled{\scriptsize{6 }}}\normalsize h[n]=\left\{8,10,8,4,2,4 \right\}\\ x_3[n] \normalsize{\textcircled{\scriptsize{6 }}}\normalsize h[n]=\left\{4,5,7,7,5,4 \right\}\\ x_4[n] \normalsize{\textcircled{\scriptsize{6 }}}\normalsize h[n]=\left\{1,3,3,1,0,0\right\}$
于是每个结果保留后4位，得到最后结果
$x_[n] \normalsize{\textcircled{\scriptsize{L }}}\normalsize h[n]=\left\{1,4,8,10,8,4,2,4,7,7,5,4,3,1 \right\}$ 文章来源地址https://www.toymoban.com/news/detail-495961.html