环形折积

环形折积与线性折积类似，皆是针对两个函数的运算子。假设两个函数分别为f与g，则折积运算过程即为将其中一个函数(如f)经过翻转后，对于每个位移量，将重叠的部分相乘累加起来(见下文定义)。不同的地方在于环形折积的位移为环形位移，而线性折积的位移为平移。折积亦可以视为滑动平移的推广。

## 定义

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

x(t)经过周期延伸后之函数可写成下式:

$$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)计算环形折积的运算($x(t) \otimes h(t)$)可以下列两种等价表示式定义:

$$\begin{align} 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{align}$$

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

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

$$\begin{align} \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{align}$$

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

$$\begin{align} 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{align}$$

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

## 线性折积与环形折积之比较

<image>

### 线性折积

连续信号线性折积

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

离散信号线性折积

$$(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时，两者的结果相同。

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

## 如何利用快速傅立叶变换计算线性折积

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

我们根据折积理论知道

$$y[n] = x[n] \star h[n] = \sum_k {x[n-k] h[k]}$$

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

然而FFT的点数该如何选取呢？

因为FFT与IFFT的点数皆要是一样的，且特别要注意的一点是:

$$y_1[n] = IFFT_L (FFT_L{x_1[n]} FFT_L{h_1[n]})$$

$$y_1[n] = \sum_{k = 0}^{N-1} {x[((n-k))_L] h[k]}$$

其中FFTL为L点FFT；IFFTL为L点IFFT ((a))L: a除以L的余数

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

$$y[n] = x[n] \star h[n] = \sum_k {x[n-k] h[k]}$$

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

### xn 与 hn 皆为无限长信号

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

### xn 与 hn 皆为有限长信号

假设xn的范围n1,n2，长度为N = n2-n1+1；hn的范围为k1,k2，长度K为 k2-k1+1 在这个情况下，xn与hn的线性折积为

$$y[n] = \sum_{k = k_1}^{k_2} {x[n-k] h[k]}$$

容易以图解推得yn有值的范围为k1+n1, k2+n2，输出长度为$k_2+n_2-k_1-n_1+1 = N + K - 1$ (输出信号长度比两输入信号大)

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

$$x_1[n] = x[n+n_1] , n = 0,1,2,...,N-1$$

$$x_1[n] = 0 , n = N,N+1,N+2,...,M-1 M = N + K -1$$

$$h_1[n] = h[n+k_1] , n = 0,1,2,...,K-1$$

$$h_1[n] = 0 , n = K,K+1,K+2,...,M-1$$

$$y_1[n] = IFFT_M(FFT_M{x_1[n]} FFT_M{h_1[n]})$$

$$y[n] = y_1[n-n_1-k_1] , n-n_1-k_1 = 0,1,2,...,N-1$$

### xn 为无限长信号，而hn 为有限长信号

由于折积运算的对称性，此种类与xn 为有限长信号，而hn 为无限长信号的情况完全相同。

假设xn的范围n1,n2，长度为N = n2 - n1 + 1，hn长度为无限长。

在此情况下，折积输出yn每一点皆有值。但当我们只想求出yn的其中一段时，依然可利用快速傅立叶变换实作。

如果我们希望算出yn在范围m1,m2之间的值，此段长度为 M = m2-m1+1，此时可图解发现，在hn中与我们关心的输出范围有关联之hn范围为m1-n2,m2-n1，需要使用的FFT点数为L =N+M-1 (M为输出信号关心的长度)

实作方法如下:

$$x_1[n] = x[n+n_1] , n = 0,1,2,...,N-1$$

$$x_1[n] = 0 , n = N,N+1,N+2,...,L-1 L = N + M -1$$

$$h_1[n] = h[n+m_1-n_2] , n = 0,1,2,...,L-1$$

$$y_1[n] = IFFT_L(FFT_L{x_1[n]} FFT_L{h_1[n]})$$

$y[n] = y_1[n-m_1+N-1] , n-m_1+N-1 = N-1,N,...,L$ (只选y1n后面M个点)

## 区块折积

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