基于FFT计算线性离散卷积的一种算法

1、 自 动 化 技 术 与 应 用 2009年第 28卷第 2期通信与信息处理Communication and Information Processing基于 FFT 计算线性离散卷积的一种算法田 秀 华 , 刘 文 进 , 裴 晓 敏(辽宁工程技术大学电信学院,辽宁 阜新123000摘要:介绍一种利用快速傅里叶变换计算线性离散卷积的算法,给出了此算法的原理、 数学模型、 实现方法以及进一步减少计算量的措施等,仿真表明此算法与一般算法相比,在运算量方面优点明显。关键词:线性;离散卷积;离散傅里叶变换;快速傅里叶变换中图分类号:TP13文献标识码:A文章编号:1003-7241(200902-

2、0056-03An Algorithm for Calculating the LinearDiscrete Convolution With FFTTIAN Xiu-hua, LIU Wen-jin, PEI Xiao-min(Liaoning Technical University, Fuxin 123000 ChinaAbstract: This papers introduces an algorithm for calculating the linear discrete convolution with FFT. The mathematic model andthe impl

3、ementation of the are also presented.Key words: linear; discrete convolution; DEF; FFT收稿日期:2008-08-181引言线性离散卷积在数字信号处理中是很重要的一种 运算, 因为离散时间系统的输出响应等于输入激励与系 统单位冲激响应的离散卷积, 所以线性离散卷积运算广 泛应用于线性移不变离散时间系统的仿真、分析与设 计等方面。线性离散卷积可以直接在时域根据定义式 进行计算, 也可以利用 z 域分析方法求解。但是不论应 用哪一种方法, 运算量都较大, 也比较麻烦。本文介绍 一种利用快速傅里叶变换(FFT 计算线

4、性离散卷积的 方法, 此算法可以使运算工作量大大减少, 运算速度大 大的提高。2算法原理设离散时间系统的输入序列 (n x 为 N 1点, 单位冲 激响应序列 (n h 为 N 2点,系统输出为二者线性卷积1:=120N m l m n x m h n x n h n y ( ( ( ( ( (n y l 也是有限长序列, 其点数为 121+N N 点。由于每一个 (n x 的输入值都必须和全部的 (n h 值相乘一 次, 因此直接根据公式计算总共需要 21N N 次乘法。将 (n x 和 (n h 通过补上一定的零值点, 都变成 N 点 的序列, 即=1 , 010 , 11N n N N

5、n n x n x ( (=1, 010 , 22N n N N n n h n h ( (只要满足 121+N N N , (n x 与 (n h 的 N 点圆周卷 积就可以代替它们的线性卷积。时域序列圆周卷积在频域上相当于两个序列的离散傅里叶变换(DFT 2。求 (n x 与 (n h 各自的 N 点 D F T( ( (k R Wn x n x k X N N n nkN =110DFT ( ( (k R Wn h n h k H N N n nk N =120DFT 将 (k X 与 (k H 相乘,得 自 动 化 技 术 与 应 用 2009年第 28卷第 2期 Techniques

6、 of Automation & Applications | 57通信与信息处理Communication and Information Processing( ( (k H k X k Y =, N 点求 (k Y 的 N 点离散傅里叶反变换(I D F T nk NN k Wk Y Nk Y n y =11 IDFT ( ( (n x =(n h (n y 的前 121+N N 个点就等于 (n x 与 (n h 的线 性卷积, 即+=11 020 2121N n N N N N n n y n y l , , ( (线性离散卷积算法的数学模型如图 1所示, D F T 和 I

7、 D F T 都采用基 -2 F F T 计算方法(取 L N 2=, L 为 正整数 。3 FFT 的实现基 -2FFT 有按时间抽选法和按频率抽选法两大类3:按时间抽选的 FFT 算法是把输入序列按其顺序的奇偶分解为越来越短的序列; 按频率抽选的 FFT 算法是把 输出序列按其顺序的奇偶分解为越来越短的序列。图 2给出了N=8时按频率抽选的基 -2FFT结构流图,输入是自然顺序排列, 输出是倒位序排列的。基 -2FFT 算法为蝶形运算,共有 L 级蝶形,每级都 由N /2个碟形组成,每个碟形有一次复乘、两次复加,图1线性离散卷积数学模型图 2按频率抽选基 -2 FFT 流图(N =8L 级

8、运算总共需要复数乘法次数为 N NL N m F 222log =; 复数加法次数为 N N NL a F 2log =。根据结构流图 2编写程序, 程序只包括 L 级递推计算。F F T 算法同样可以适用于 I D F T 运算, 即=( ( ( (k Y N W k Y NWk Y N k Y n y nk N N k N k nk NDFT 111IDFT 1010先将 Y (k 取共轭,就可以直接利用 FFT 子程序,最 后再将运算结果取一次共轭, 并乘以 1/N , 即得到 y (n 值。F F T 运算和 I F F T 运算可以共用一个子程序块, 很 方便。利用 F F T 法计

9、算线性离散卷积,所需要的乘法次数 为+=+N N N N N 2223123log log 。 直接根据公式(1与 F F T 法计算线性卷积两种方法的乘法次数的比值为+=N N N N K 221231log (n x 与 (n h 点 数 差 不 多 时 ,设 21N N =,11212N N N =,则+=12123252N N K log 当 1281=N 时, 两种方法相当; 40961=N 时, F F T 法 约快 25倍。4进一步减少计算量措施在实际中, (n x 与 (n h 一般是实序列, 采取下列措 施, 可以进一步减少计算量。将两个实序列构成一个复序列, 即( ( (n

10、 h n x n w j +=对复序列求 N 点的 F F T( ( (k H k X n h n x n w k W j DFT j DFT DFT +=+=再利用 D F T 共轭对称性, 求出各自的 D F T( ( ( (k R k N W k W n w k X N N +=21R DFT e ( ( ( (k R k N W k W n w k H N N =j21I DFT m 采取此措施, 利用 F F T 算法计算线性离散卷积, 所 需要的乘法次数变为 (N N 21log +。N Y N 自 动 化 技 术 与 应 用 2009年第 28卷第 2期通信与信息处理Commun

11、ication and Information Processing 在软件设计部分, 主要分接收和发送两个模块的工 作, 接收部分的软件工作相对简单, 此处重点分析发射 模块的工作流程。发射模块工作程序如图 5所示。 在正常情况下,SP30内部控制器处于一种睡眠等待 状态, 能够接收来自外部的中断, 当 S P 30执行检测时,图 4接收模块图 5 发射模块软件流程图5结束语仿真分析表明, 当参与线性卷积运算两个序列的点 数差不多时, 数据的点数越长, 本文所介绍的算法与一 般算法相比, 在运算量方面优点越明显。对于连续信号 的卷积运算, 可以首先对信号抽样离散化, 然后在应用 上述算法进行

12、计算。另外, 线性相关运算同样可以应用 与本文给出的快速卷积相类似的算法分析、计算, 这对 于随机信号功率谱的估计与应用具有实际意义 4。参考文献:将 M C U 从睡眠状态唤醒, 接收测量数据, 并与上次数据 进行比较, 如果相等且在安全范围内, 则直接发射到接 收端进行正常显示;如果压力、温度值与上次不等,则判 断是否安全, 如果超出正常的范围, 则将数据送至接收 端显示,并启动报警 2。5结束语由于汽车市场的快速增长,TPMS 系统也将拥有更多 的发展空间, 在这个充满机遇同时又面临众多技术调整 的市场上, 选择合适的解决方案将对厂商在这个市场上 是否能取得成功起着非常关键的作用, 本方

13、案设计的汽 车轮胎压力检测系统具有电路简单、精度高、体积小、 响应时间短、性能稳定等特点, 具有很高的实用价值。参考文献:1崔光照,曹祥红,张华.基于MSP430单片机的智能型复 费率单相电能表设计J.微计算机信息,2006,(2:21-23.2臧利林,贾磊,秦伟刚等.基于环行线圈车辆检测系统的 研究与设计J.仪器仪表学报,2004,25(4:229-331.3刘元宾,靳世久,陈世利.压力传感器SP12在胎压监视 系统中的应用J.电子测量技术,2008.31(2:170-172.4金爱武.直接式TPMS轮胎压力监测系统设计J.单片 机与嵌入式系统应用.2005(8:61-63.作者简介:刘金华(1964- , 男, 副教授, 从事控制工程与电 子 技 术 应