# 用 DFT 矩阵计算线性卷积的原理与模拟报告

**实验任务：** DFT 用矩阵来计算线性卷积的基本思想及模拟
**实验环境：** Python 3.14 (NumPy, Matplotlib)
**文件路径：** `Homework/DFT_Linear_Conv/`

---

## 1. 实验目的
理解离散傅里叶变换（DFT）和圆周卷积之间的关系，并掌握如何利用 DFT 矩阵运算来等效地计算两个有限长序列的线性卷积。

---

## 2. 理论基础与基本思想

在线性时不变系统中，系统的输出等于输入信号与系统单位脉冲响应的线性卷积：
$$ y_{linear}[n] = x[n] * h[n] $$
假设 $x[n]$ 长度为 $N_1$，$h[n]$ 长度为 $N_2$，则它们的线性卷积结果 $y_{linear}[n]$ 的长度应为 $N = N_1 + N_2 - 1$。

另一方面，离散傅里叶变换（DFT）的一个重要性质是**循环卷积定理**：
在时域中对两个长度同为 $N$ 的序列进行圆周卷积，等效于在频域中对它们的 $N$ 点 DFT 进行逐点相乘，再进行 $N$ 点逆离散傅里叶变换（IDFT）。

### 为什么能用 DFT 计算线性卷积？
为了用 DFT（圆周卷积）来计算线性卷积，必须避免“混叠”现象。只要把序列 $x[n]$ 和 $h[n]$ 分别在末尾**补零（Zero-padding）**，使它们的长度都达到 $N \ge N_1 + N_2 - 1$，那么在这个长度 $N$ 下，两者的圆周卷积就完全等价于线性卷积。

### 矩阵运算思想
利用矩阵乘法，DFT 和 IDFT 可以表示为线性代数中的矩阵变换。
设 $W_N$ 为 $N \times N$ 的 DFT 变换矩阵，其元素为：
$$ W_N^{k,n} = e^{-j \frac{2\pi}{N} k n} $$
设 $W_N^{-1}$ 为 $N \times N$ 的 IDFT 变换矩阵，其元素为：
$$ W_N^{-1(n,k)} = \frac{1}{N} e^{j \frac{2\pi}{N} n k} $$

计算线性卷积的完整矩阵运算步骤如下：
1. **补零**：将 $x$ 和 $h$ 补零成长度为 $N = N_1 + N_2 - 1$ 的列向量 $x_{pad}$ 和 $h_{pad}$。
2. **正变换（DFT）**：
   $$ X = W_N \cdot x_{pad} $$
   $$ H = W_N \cdot h_{pad} $$
3. **频域相乘**：将 $X$ 和 $H$ 逐点相乘得到频域输出 $Y$：
   $$ Y[k] = X[k] \cdot H[k] $$
4. **逆变换（IDFT）**：
   $$ y_{dft} = W_N^{-1} \cdot Y $$

最终得到的向量 $y_{dft}$ 即为线性卷积的结果。

---

## 3. 代码模拟与结果分析

我们使用 Python 编写了模拟代码 `dft_linear_conv.py`。
设定输入序列为：
- $x[n] = [1, 2, 3, 4]$ (长度 $N_1 = 4$)
- $h[n] = [1, 1, 1]$ (长度 $N_2 = 3$)

### 3.1 运行结果
补零后的长度 $N = 4 + 3 - 1 = 6$。

控制台输出：
```text
x[n]: [1 2 3 4]
h[n]: [1 1 1]
Zero-padded length N = 6
y_dft (DFT Matrix computed): [1. 3. 6. 9. 7. 4.]
y_linear (np.convolve computed): [1 3 6 9 7 4]
```

可以清楚地看到，通过 DFT 矩阵运算计算出来的卷积结果与使用内置函数 `numpy.convolve()` 计算出来的标准线性卷积结果完全一致。

### 3.2 结果波形图
为了直观展示，我们将输入信号 $x[n]$、$h[n]$ 以及卷积输出结果进行了可视化对比：

![Convolution Comparison](convolution_comparison.png)

在上图的第三个子图中，红色的圆点代表标准线性卷积的结果，紫色的星号代表利用 DFT 矩阵方法计算的结果。两者完美重合，验证了“**补零后长度为 $N_1+N_2-1$ 的 DFT 矩阵乘法可以精确实现线性卷积**”的理论。

---

## 4. 结论
通过本次模拟实验，我们成功地利用 DFT 矩阵计算了线性卷积。核心思想在于：
1. **补零扩展**：防止频域相乘对应到时域时发生时域混叠。
2. **矩阵变换**：通过构造 DFT 和 IDFT 矩阵，将复杂的求和运算转化为标准的矩阵-向量乘法。
这种方法不仅具有重要的理论意义，还在使用快速傅里叶变换（FFT）加速长序列卷积计算中发挥着核心作用。
