线性卷积与圆周卷积的计算

线性卷积和圆周卷积都是信号处理中常用的运算，它们的定义和计算方法略有不同。

线性卷积：给定两个长度为 $N$ 的实数序列 $x$ 和 $y$，它们的线性卷积 $z$ 定义为：

$$ z_n = \sum_{m=0}^{N-1} x_m y_{n-m} $$

其中，$n = 0, 1, \cdots, 2N-2$。线性卷积通常用于时域信号处理。

计算线性卷积的一种常见方法是使用快速傅里叶变换（FFT）。具体而言，将序列 $x$ 和 $y$ 分别进行 $N$ 点 FFT，得到它们的频域表示 $X$ 和 $Y$，则它们的线性卷积 $z$ 可以通过将 $X$ 和 $Y$ 逐元素相乘，并进行 $N$ 点逆FFT 得到：

$$ z = {\rm IFFT}(X \cdot Y) $$

其中，${\rm IFFT}$ 表示逆傅里叶变换，$\cdot$ 表示逐元素相乘。

圆周卷积：给定两个长度为 $N$ 的复数序列 $x$ 和 $y$，它们的圆周卷积 $z$ 定义为：

$$ z_n = \sum_{m=0}^{N-1} x_m y_{(n-m) \bmod N} $$

其中，$\bmod$ 表示取模运算，$n = 0, 1, \cdots, N-1$。圆周卷积通常用于频域信号处理。

计算圆周卷积的一种常见方法是使用循环卷积定理。具体而言，将序列 $x$ 和 $y$ 分别进行 $N$ 点 DFT（离散傅里叶变换），得到它们的频域表示 $X$ 和 $Y$，则它们的圆周卷积 $z$ 可以通过将 $X$ 和 $Y$ 逐元素相乘，并进行 $N$ 点 IDFT（离散傅里叶逆变换）得到：

$$ z = {\rm IDFT}(X \cdot Y) $$

其中，${\rm IDFT}$ 表示离散傅里叶逆变换，$\cdot$ 表示逐元素相乘。需要注意的是，IDFT 的结果可能有复数部分，但是在实际应用中，通常只关注实数部分。