数字信号处理

大学的时间有时候碎片化，大大小小的琐事间隔，一段小时间区间不知干啥，于是就做点思路整理工作

#由来

在利用FFT计算线性卷积时，遇见长序列与短序列卷积时，FFT不一定具备简化计算的优势

#思路 分而治之的思想，可能很多情况下都使用，将大问题转为能解决的已知问题。既然一长一段不行，何不把长的分段 我们设两个序列中短序列为s(n),长度为M；长序列为l(n),长度为L;可以测试，对长序列的分段点数不影响卷积结果，那我们设每段长度为N。那么，第一段的下标应该是0~N-1，第二段应该是N ->2N-1;由于我们采用每段分别求卷积，再将每段卷积通过合适的方法组合成目标结果，那么第二段应该往左移N点，以作DFT,也可以理解为周期延拓。为了让fft 或dft 代替线性卷积结果，需要有dft点数的要求，即points=2^r>=N+M-1。因此，我们要在N点基础上进行补零，往后加points-N个0即可。同时别忘了对s(n)也进行同样的补零处理。 由于时域卷积可以频域相乘再反变换求得，我们将对s(n)和每个分段分别求卷积。在得到每个分段的卷积和后，我们要由此组织我们的结果。数学上已经给出结果了，就不赘述。对数学表达式的理解为，第一段的前N个点依旧代表结果，此后的M-1个点将与第二段的前M-个点相加，其他的类似。不严谨地说，每个分段产生N+M-1个点，第二段相当于右移N个点，必然产生混叠，第三段右移2N个点。。。看两张图，结合理解。

#matlab代码实现 由于暂时不会动态分配变量或内存，我的程序只能将序列分3段，实际上你可以修改分段数目。从程序角度看，这份代码不能满足预期功能，但编程能力有待提高。