fft和卷积_fft算法

2024年 9月 7日下午3:36 • 激活谷笔记

第19章：用FFT计算线性卷积和循环互相关　　高西全《数字信号处理——原理、实现与应用》书籍中讲到 “频谱分析和滤波是最基本的信号处理，频谱分析就是计算信号的离散傅里叶变换（DFT），滤波实质上就是计算两个信号的卷积。” 　　FFT无疑是数字信号处理课程中的一个重点，最近碰到了用FFT计算两个序列的相关性，于是将FFT计算相关和卷积知识复习了下。　　本章主要内容如下：　　一、用FFT计算卷积　　二、用FFT计算相关　　三、推荐阅读与总结　　一、用FFT计算线性卷积　　假设h(n)的长度为N，x(n)的长度为M，则h(n)与x(n)线性卷积出来结果序列的长度为N+M-1。　　线性卷积：
$y\left( n \right) = h\left( n \right) * x\left( n \right) = \sum\limits_{m = 0}^{N - 1} {h\left( m \right)x\left( {n - m} \right)}$ 　　循环卷积：
${y_c}\left( n \right) = h\left( n \right) \otimes x\left( n \right) = \sum\limits_{m = 0}^{N - 1} {h\left( m \right)x{{\left( {\left( {n - m} \right)} \right)}_L}} {R_L}\left( n \right)$ 　　其中
${x{{\left( {\left( {n - m} \right)} \right)}_L}}$ 是
${x\left( {n - m} \right)}$ 以L为周期的周期延拓序列，注意有个矩形窗
${R_L}\left( n \right)$ 。
$L \ge N + M - 1$ 是循环卷积结果和线性卷积结果相等的充要条件。　　值得注意的是：循环卷积，一定要指明做L点的循环卷积；且
$L \ge N + M - 1$ 这个条件求职笔试时，喜欢考填空题。　　我目前仿真过程中，碰到用线性卷积的两个知识点：　　（1）卷积码，这个可以参考《陈老湿：第2章（2）：卷积码》；　　（2）信号经过滤波器，比如脉冲成型滤波器、低通滤波器，也是卷积过程，MATLAB中可以使用conv函数，或者filter函数，可以参考《陈老湿：第1章（1）：BPSK调制解调器仿真》。　　

图1 当大于等于N+M-1时，C_linear和C_fft结果重合　　二、用FFT计算循环互相关　　用FFT计算相关，源于我之前看别人计算两个序列的互相关性，会使用下面这一种计算形式：　　和循环卷积来计算线性卷积的代码稍有不同，多了一个取共轭的操作，即conj。　　下面是MATLAB中对xcorr函数的介绍，不过下面这张截图中不是计算循环互相关。

　　从结果上来看， C_corr = C_fft = [70 64 62 64]。详细过程手动如下：　　C_corr(1,1) = 5*1+6*2+7*3+8*4 = 70；C_corr(1,2) = 5*2+6*3+7*4+8*1 = 64；　　C_corr(1,3) = 5*3+6*4+7*1+8*2 = 62；C_corr(1,2) = 5*4+6*1+7*2+8*3 = 64。　　那么计算循环互相关，有什么作用呢？　　比如在导航信号当中，假设每一个比特都乘以相同的扩频码，如果接收机需要估计接收信号与本地产生的扩频码序列相差了多少码相位？　　接收机便可以利用fft的方法计算循环互相关，并观察最大值的位置得知相差的码相位。在导航信号中，之所以使用循环互相关，是因为每一个比特乘以相同的扩频码，且信号到达接收机的时刻是不确定的。　　运行上面的代码，发现index1 = index2 = length(seq_polar_local)-location=12，这是因为代码中以本地信号为基准，即取共轭的序列相对于未取共轭的序列进行向右移动。（这句话姑且记住吧，不然代码容易出错！）　　上面这个例子便是说，m序列长度是15，假设输入信号已经相对于本地序列往右循环移动了3个位置，问题是需要将输入信号再往右循环移动多少个位置，才能与本地信号做互相关，出现最大值。　　通过计算得到index1=index1=12，即需要将输入信号再往右循环移动12个位置才能与本地序列完全对上。这里暂且没有考虑噪声以及频偏等因素的干扰。　　值得注意的是，下面的auto_corr_temp1也说明m序列的单峰值自相关特性，即只有刚好完全对上时，相关值为15，其他时候均为-1。

图2 m序列的自相关性　　顺便提一句，通信中常用的序列，除了前面提到的m序列，还有gold、ZC序列等，这些序列的自相关、互相关性又如何呢？这又是另外的问题了。于是，脑海中的小问号又增加了。　　三、推荐阅读与总结　　网上的资料有时候水平参差不齐，挑选文章也需要花费时间和精力。下面我推荐几篇不错的文章，有两个原因：　　（1）既是对我看过相关材料的一个汇总，也方便我下次翻出来学习，感谢这些朋友分享知识。　　（2）方便从我这里接触到这些概念的读者朋友，如果想继续深入学习，也能进行扩展阅读。　　汇总参考文章如下：　　（1）什么是互相关_いいこと？暁の磕盐线に胜利を刻みなさいっ！-CSDN博客　　这篇文章把线性互相关和循环互相关的概念，以图的形式讲解非常生动，值得反复看。　　（2）卷积运算和相关运算的区别与物理含义? 　　（3）用FFT计算相关函数_geophysics_mars_新浪博客　　这里给出了用FFT计算相关函数的证明。　　（4）信号处理绕不过去的坎：相关与卷积　　这里给出了MATLAB中xcorr与conv的使用。　　想到一句话：知识这东西就得经常地核实和订正，尤其是那些从别人那里听来的知识。　　本人能力有限，不足甚至错误之处，欢迎你批评指正，也欢迎读者朋友就相关技术问题与我交流，一起学习，共同进步。　　请你也别忘了把这篇文章分享给你身边正在学习通信专业的同学们，也许能够帮到Ta。这是《陈老湿·通信MATLAB仿真》的第19章，下次更新见！

fft和卷积_fft算法

相关推荐