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

《 自 动 化 技 术 与 应 用 》 2009年第 28卷第 2期 通信与信息处理

Communication and Information Processing 基于 FFT 计算线性离散卷积的一种算法 田 秀 华 , 刘 文 进 , 裴 晓 敏

(辽宁工程技术大学电信学院,辽宁 阜新 123000

摘 要:介绍一种利用快速傅里叶变换计算线性离散卷积的算法,给出了此算法的原理、 数学模型、 实现方法以及进一步减少计算量

的措施等,仿真表明此算法与一般算法相比,在运算量方面优点明显。 关键词:线性;离散卷积;离散傅里叶变换;快速傅里叶变换

中图分类号:TP13 文献标识码:A 文章编号:1003-7241(200902-0056-03

An Algorithm for Calculating the Linear Discrete Convolution With FFT

TIAN Xiu-hua, LIU Wen-jin, PEI Xiao-min (Liaoning Technical University, Fuxin 123000 China

Abstract: This papers introduces an algorithm for calculating the linear discrete convolution with FFT. The mathematic model and

the implementation of the are also presented. Key words: linear; discrete convolution; DEF; FFT

收稿日期:2008-08-18 1 引言

线性离散卷积在数字信号处理中是很重要的一种 运算, 因为离散时间系统的输出响应等于输入激励与系 统单位冲激响应的离散卷积, 所以线性离散卷积运算广 泛应用于线性移不变离散时间系统的仿真、分析与设 计等方面。线性离散卷积可以直接在时域根据定义式 进行计算, 也可以利用 z 域分析方法求解。但是不论应 用哪一种方法, 运算量都较大, 也比较麻烦。本文介绍 一种利用快速傅里叶变换(FFT 计算线性离散卷积的 方法, 此算法可以使运算工作量大大减少, 运算速度大 大的提高。

2 算法原理

设离散时间系统的输入序列 (n x 为 N 1点, 单位冲 激响应序列 (n h 为 N 2点,系统输出为二者线性卷积

[1] : ∑ ?=?= ?=1 20

N 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 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 W n x n x k X N N n nk N ∑?== =1 10DFT ( (]([ (k R W

n h n h k H N N n nk N ∑?== =120

DFT 将 (k X 与 (k H 相乘,得

《 自 动 化 技 术 与 应 用 》2009年第 28卷第 2期

Techniques of Automation & Applications | 57 通信与信息处理

Communication and Information Processing ( ( (k H k X k Y =, N 点

求 (k Y 的 N 点离散傅里叶反变换(I D F T nk N N k W

k Y N k Y n y ??=∑= =1

1 IDFT (]([ ( (n x =

(n h (n y 的前 121?+N N 个点就等于 (n x 与 (n h 的线 性卷积, 即 ?≤≤?+?+≤≤=1

1 020 2121N n N N N N n n y n y l , , ( (线性离散卷积算法的数学模型如图 1所示, D F T 和 I D F T 都采用基 -2 F F T 计算方法(取 L N 2=, L 为 正整数 。

3 FFT 的实现

基 -2 FFT 有按时间抽选法和按频率抽选法两大类 [3]

:按时间抽选的 FFT 算法是把输入序列按其顺序的奇

偶分解为越来越短的序列; 按频率抽选的 FFT 算法是把 输出序列按其顺序的奇偶分解为越来越短的序列。图 2

给出了 N =8

时按频率抽选的基 -2 FFT 结构流图,输入

是自然顺序排列, 输出是倒位序排列的。

基 -2 FFT 算法为蝶形运算,共有 L 级蝶形,每级都 由 N /

2个碟形组成,

每个碟形有一次复乘、两次复加, 图 1

线性离散卷积数学模型

图 2 按频率抽选基 -2 FFT 流图(N =8 L 级运算总共需要复数乘法次数为 N N L N m F 22

2log ==; 复数加法次数为 N N NL a F 2log ==。根据结构流图 2编 写程序, 程序只包括 L 级递推计算。 F F T 算法同样可以适用于 I D F T 运算, 即 ? ?? ?=??=?= =

= =∑ ∑]}

([{ ( (]([ (k Y N W k Y N W

k Y N k Y n y nk N N k N k nk N DFT 11 1 IDFT 101

0先将 Y (k 取共轭,就可以直接利用 FFT 子程序,最 后再将运算结果取一次共轭, 并乘以 1/N , 即得到 y (n 值。F F T 运算和 I F F T 运算可以共用一个子程序块, 很 方便。

利用 F F T 法计算线性离散卷积,所需要的乘法次数 为 +=+N N N N N 2223123

log log 。 直接根据公式(1与 F F T 法计算线性卷积两种方 法的乘法次数的比值为 +=

N N N N K 22

1231log (n x 与 (n h 点 数 差 不 多 时 ,

设 2 1N N =,

11212N N N ≈?=,则 +=

12123252N N K log 当 1281=N 时, 两种方法相当; 40961=N 时, F F T 法 约快 25倍。

4 进一步减少计算量措施

在实际中, (n x 与 (n h 一般是实序列, 采取下列措 施, 可以进一步减少计算量。 将两个实序列构成一个复序列, 即

( ( (n 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 ?+==?2 1

R DFT e (] (( (]}([{ (k R k N W k W n w k H N N ??= =?j 21

I DFT m 采取此措施, 利用 F F T 算法计算线性离散卷积, 所 需要的乘法次数变为 (N N 21log +。

N Y N

《 自 动 化 技 术 与 应 用 》 2009年第 28卷第 2期 通信与信息处理

Communication and Information Processing

在软件设计部分, 主要分接收和发送两个模块的工 作, 接收部分的软件工作相对简单, 此处重点分析发射 模块的工作流程。发射模块工作程序如图 5所示。

在正常情况下,SP30内部控制器处于一种睡眠等待 状态, 能够接收来自外部的中断, 当 S P 30执行检测时,

图 4 接收模块

图 5 发射模块软件流程图 5 结束语

仿真分析表明, 当参与线性卷积运算两个序列的点 数差不多时, 数据的点数越长, 本文所介绍的算法与一 般算法相比, 在运算量方面优点越明显。对于连续信号 的卷积运算, 可以首先对信号抽样离散化, 然后在应用 上述算法进行计算。另外, 线性相关运算同样可以应用 与本文给出的快速卷积相类似的算法分析、计算, 这对 于随机信号功率谱的估计与应用具有实际意义 [4]。

参考文献:

将 M C U 从睡眠状态唤醒, 接收测量数据, 并与上次数据 进行比较, 如果相等且在安全范围内, 则直接发射到接 收端进行正常显示;如果压力、温度值与上次不等,则判 断是否安全, 如果超出正常的范围, 则将数据送至接收 端显示,并启动报警 [2]。

5 结束语

由于汽车市场的快速增长,TPMS 系统也将拥有更多 的发展空间, 在这个充满机遇同时又面临众多技术调整 的市场上, 选择合适的解决方案将对厂商在这个市场上 是否能取得成功起着非常关键的作用, 本方案设计的汽 车轮胎压力检测系统具有电路简单、精度高、体积小、 响应时间短、性能稳定等特点, 具有很高的实用价值。

参考文献:

[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- , 男, 副教授, 从事控制工程与电 子 技 术 应 用 方 面 的 教 学 和 科 研 工 作 。

作者简介:田秀华(1961— , 女, 教授, 主要从事信息处理 与 自 动 控 制 方 面 的 教 学 与 研 究 工 作 。

[1] 刘顺兰.吴杰,数字信号处理[M].西安:西安电子科技大 学出版社,2005. [2] 胡广书.数字信号处理—理论.算法与实现[M].北京:清 华大学出版社,2004, [3] DUHAMEL P,HOLTMANN.H.Split-radix FFT algorithm[J].Electronics Letters.1994,20(1:14-16

[4] 姚天任,孙洪,现代数字信号处理[M].武汉:华中理工大 学出版社,2004. (上接第 51页

[2] 臧利林,贾磊,秦伟刚等.基于环行线圈车辆检测系统的 研究与设计[J].仪器仪表学报,2004,25(4:229-331.

[3] 刘元宾,靳世久,陈世利.压力传感器SP12在胎压监视 系统中的应用[J].电子测量技术,2008.31(2:170-172.

[4] 金爱武.直接式TPMS轮胎压力监测系统设计[J].单片 机与嵌入式系统应用.2005(8:61 -63.

作者简介:刘金华(1964- , 男, 副教授, 从事控制工程与电 子 技 术 应 用 方 面 的 教 学 和 科 研 工 作 。

作者简介:田秀华(1961— , 女, 教授, 主要从事信息处理 与 自 动 控 制 方 面 的 教 学 与 研 究 工 作 。

[1] 刘顺兰.吴杰,数字信号处理[M].西安:西安电子科技大 学出版社,2005. [2] 胡广书.数字信号处理—理论.算法与实现[M].北京:清 华大学出版社,2004, [3] DUHAMEL P,HOLTMANN.H.Split-radix FFT algorithm[J].Electronics Letters.1994,20(1:14-16

[4] 姚天任,孙洪,现代数字信号处理[M].武汉:华中理工大 学出版社,2004. (上接第 51页

本文来源：https://www.bwwdw.com/article/88fx.html