基于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 结构流图,输入