环形折积

两个函数的环形折积定义为对一个或两个函数做周期延伸后之折积运算，而所谓的周期延伸是指原来的函数平移固定长度的整数倍再全部加起来所产生的新函数。 x(t)经过周期延伸后之函数可写成下式:

${\displaystyle x_{T}(t)\ {\stackrel {\mathrm {def} }{=}}\ \sum _{k=-\infty }^{\infty }x(t-kT)=\sum _{k=-\infty }^{\infty }x(t+kT).}$ 

其中T为周期(即周期延伸中的固定长度)

对x(t)与h(t)计算环形折积的运算(${\displaystyle x(t)\otimes h(t)}$ )可以下列两种等价表示式定义:

${\displaystyle {\begin{aligned}y(t)&=\int _{t_{o}}^{t_{o}+T}h_{T}(\tau )\cdot x_{T}(t-\tau )\,d\tau \\&=\int _{-\infty }^{\infty }h(\tau )\cdot x_{T}(t-\tau )\,d\tau \quad {\stackrel {\mathrm {def} }{=}}\quad x_{T}(t)*h(t),\end{aligned}}}$ 

其中*表示线性折积运算子

此两定义的等价关系证明如下:

${\displaystyle {\begin{aligned}\int _{-\infty }^{\infty }h(\tau )\cdot x_{T}(t-\tau )\,d\tau &=\sum _{k=-\infty }^{\infty }\left[\int _{t_{o}+kT}^{t_{o}+(k+1)T}h(\tau )\cdot x_{T}(t-\tau )\ d\tau \right]\\&=\sum _{k=-\infty }^{\infty }\left[\int _{t_{o}}^{t_{o}+T}h(\tau +kT)\cdot x_{T}(t-\tau -kT)\ d\tau \right]\\&=\sum _{k=-\infty }^{\infty }\left[\int _{t_{o}}^{t_{o}+T}h(\tau +kT)\cdot x_{T}(t-\tau )\ d\tau \right]\\&=\int _{t_{o}}^{t_{o}+T}\left[\sum _{k=-\infty }^{\infty }h(\tau +kT)\cdot x_{T}(t-\tau )\right]\ d\tau \\&=\int _{t_{o}}^{t_{o}+T}\left[\sum _{k=-\infty }^{\infty }h(\tau +kT)\right]\cdot x_{T}(t-\tau )\ d\tau \\&\ {\stackrel {\mathrm {def} }{=}}\ \int _{t_{o}}^{t_{o}+T}h_{T}(\tau )\cdot x_{T}(t-\tau )\ d\tau \quad \quad {\mbox{QED}}\end{aligned}}}$ 

上述为针对两个连续信号(函数)的环形折积之定义的说明，类似的，我们对于周期为N的离散信号之环形折积(${\displaystyle x[n]\otimes h[n]}$ )有如下的定义:

${\displaystyle {\begin{aligned}x_{N}[n]*h[n]\ &{\stackrel {\mathrm {def} }{=}}\ \sum _{m=-\infty }^{\infty }h[m]\cdot x_{N}[n-m]\\&=\sum _{m=-\infty }^{\infty }h[m]\cdot \sum _{k=-\infty }^{\infty }x[n-m-kN].\,\end{aligned}}}$ 

离散信号的环形折积可以结合快速傅立叶变换与折积理论做相当有效率的计算，然而，在实际上信号处理或系统理论的应用，线性折积运算较常被考虑也较有物理意义，于是，如果可将一个线性折积的计算问题转化为求算环形折积，则一般当两个输入信号长度相距不远时，往往计算量可以大为减少，增加了计算线性折积的效率，至于线性折积与环形折积的关系以及如何利用环形折积与傅立叶变换求得线性折积结果，将于下文进一步讨论。

线性折积

连续信号线性折积

${\displaystyle (f\star g)(t)=\int f(\tau )g(t-\tau )\,d\tau }$ 

离散信号线性折积

${\displaystyle (f\star g)[m]=\sum _{n}{f[n]g[m-n]}}$ 

对于一个线性非时变(LTI)之系统，输出的信号y(n)可以经由输入信号x(n)与系统的脉冲响应h(n)的线性折积而得。 也因此，在实际的应用上，线性折积的运算较为具有物理意义，如数位滤波器的滤波过程即为一个线性折积的运算。

环形折积

环形折积定义如前文所述，运算上是将线性折积的头尾相连变成环形，观念上可想像为一个输入在内环，另一个输入在外环，然后每一个输出的求得皆是经由内环与外环对应位置的乘加。计算下一个输出则将内环固定不动，外环圆周位移一格，再做对应位置之乘加得到此输出，以此类推。(圆环上的点数即为周期延伸的周期T或N)

比较

不管是线性折积或环形折积均有反折、位移、相乘并求和的运算，但线性折积的位移是平移，环形折积的位移则是圆周位移。除此之外，线性折积并不要求两序列长度相等，若x(n)长度为M，h(n)长度为N，则其折积输出y(n)长度为M+N-1，而环形折积则要求两输入序列等长(假设为L)，且折积输出的长度也为L。一般情况下，两等长序列的环形折积与线性折积的结果是不同的(因为环形周期序列产生的影响)，但当L≥M+N-1时，两者的结果相同。

右图为一个实际范例，可比较相同的两输入信号，线性折积与环形折积输出的差异。

由以上讨论知道一般的情况，线性折积与环形折积的输出结果并不会相同，且一般线性折积较实用而有意义。然而离散信号的处理上，由于环形折积可以借由快速傅立叶变换较有效率的求得，所以两输入信号的线性折积，如何利用环形折积与快速傅立叶变换得到，在信号处理及相关应用上是特别重要的。

我们根据折积理论知道

${\displaystyle y[n]=x[n]\star h[n]=\sum _{k}{x[n-k]h[k]}}$ 

${\displaystyle y[n]=IFFT(FFT{x[n]}FFT{h[n]})}$ 

然而FFT的点数该如何选取呢？ 因为FFT与IFFT的点数皆要是一样的，且特别要注意的一点是:

${\displaystyle y_{1}[n]=IFFT_{L}(FFT_{L}{x_{1}[n]}FFT_{L}{h_{1}[n]})}$ 

${\displaystyle y_{1}[n]=\sum _{k=0}^{N-1}{x[((n-k))_{L}]h[k]}}$ 

其中FFT_L为L点FFT；IFFT_L为L点IFFT ((a))_L: a除以L的余数

上式表示根据折积理论与快速傅立叶变换，我们求得的是两个输入信号的环形折积而不是线性折积

${\displaystyle y[n]=x[n]\star h[n]=\sum _{k}{x[n-k]h[k]}}$ 

依据两个输入信号的长度，计算方法可分类如下:

x[n] 与 h[n] 皆为无限长信号

由于此种类在实际应用上相当少且较不实际，故在此不进一步讨论

x[n] 与 h[n] 皆为有限长信号

假设x[n]的范围[n₁,n₂]，长度为N = n₂-n₁+1；h[n]的范围为[k₁,k₂]，长度K为 k₂-k₁+1 在这个情况下，x[n]与h[n]的线性折积为

${\displaystyle y[n]=\sum _{k=k_{1}}^{k_{2}}{x[n-k]h[k]}}$ 

容易以图解推得y[n]有值的范围为[k₁+n₁, k₂+n₂]，输出长度为${\displaystyle k_{2}+n_{2}-k_{1}-n_{1}+1=N+K-1}$  (输出信号长度比两输入信号大)

于是如欲以快速傅立叶变换计算线性折积，则傅立叶变换之点数M要取N+K-1，不足部分补零，实作方法如下：

${\displaystyle x_{1}[n]=x[n+n_{1}],n=0,1,2,...,N-1}$ 

${\displaystyle x_{1}[n]=0,n=N,N+1,N+2,...,M-1M=N+K-1}$ 

${\displaystyle h_{1}[n]=h[n+k_{1}],n=0,1,2,...,K-1}$ 

${\displaystyle h_{1}[n]=0,n=K,K+1,K+2,...,M-1}$ 

${\displaystyle y_{1}[n]=IFFT_{M}(FFT_{M}{x_{1}[n]}FFT_{M}{h_{1}[n]})}$ 

${\displaystyle y[n]=y_{1}[n-n_{1}-k_{1}],n-n_{1}-k_{1}=0,1,2,...,N-1}$ 

x[n] 为无限长信号，而h[n] 为有限长信号

由于折积运算的对称性，此种类与x[n] 为有限长信号，而h[n] 为无限长信号的情况完全相同。 假设x[n]的范围[n₁,n₂]，长度为N = n₂ - n₁ + 1，h[n]长度为无限长。 在此情况下，折积输出y[n]每一点皆有值。但当我们只想求出y[n]的其中一段时，依然可利用快速傅立叶变换实作。 如果我们希望算出y[n]在范围[m₁,m₂]之间的值，此段长度为 M = m₂-m₁+1，此时可图解发现，在h[n]中与我们关心的输出范围有关联之h[n]范围为[m₁-n₂,m₂-n₁]，需要使用的FFT点数为L =N+M-1 (M为输出信号关心的长度)

实作方法如下:

${\displaystyle x_{1}[n]=x[n+n_{1}],n=0,1,2,...,N-1}$ 

${\displaystyle x_{1}[n]=0,n=N,N+1,N+2,...,L-1L=N+M-1}$ 

${\displaystyle h_{1}[n]=h[n+m_{1}-n_{2}],n=0,1,2,...,L-1}$ 

${\displaystyle y_{1}[n]=IFFT_{L}(FFT_{L}{x_{1}[n]}FFT_{L}{h_{1}[n]})}$ 

${\displaystyle y[n]=y_{1}[n-m_{1}+N-1],n-m_{1}+N-1=N-1,N,...,L}$  (只选y₁[n]后面M个点)

当计算折积之两信号长度相差很大时，利用快速傅立叶变换计算折积是较没有效率的，此时较有效率的方法是将较长的信号切成一段段的区块，以此每一区块对另一输入信号进行折积再合并，常见的区块折积方法包括重叠-相加之折积法与重叠-储存之折积法，针对长度的不同，区块长度的选取亦会影响计算的效率。

• 折积
• 离散傅立叶变换
• 区块折积

• Rabiner, Lawrence R.; Gold, Bernard. Theory and application of digital signal processing. Englewood Cliffs, N.J.: Prentice-Hall. 1975: pp 63–67. ISBN 0-13-914101-4.  引文格式1维护：冗余文本 (link).
• Oppenheim, Alan V.; Schafer, Ronald W.; Buck, John A. Discrete-time signal processing. Upper Saddle River, N.J.: Prentice Hall. 1999. ISBN 0-13-754920-2. .
• Jian-Jiun Ding, Advanced digital signal processing class note,the Department of Electrical Engineering, National Taiwan University (NTU), Taipei, Taiwan, 2007.