第 27卷 第 7期
2005年 7月
现 代 雷 达
Modern Radar
Vo1.27 No.7
July 2005 23
大点数 FFT算法的改进及其实现
苏 涛 ,庄德靖
(西安 电子科技 大学雷达信 号处理重点 实验 室 , 西安 710071)
【摘要】 针对高速实时信号处理的需要,提出了一种对任意长度序列进行 FFrr的快速改进算法。通过对 FFrr处理
前数据添零个数和 DFY分解参数的优化选择 ,显著降低了 FFrr处理的运算量。结合频域脉冲压缩等信号处理实例 ,探讨
了该算法在高速 DSP上实现时的资源分配 、程序编程以及传输 I/O瓶颈问题 ,分别提出了具体 的解决方法,并在实际 DSP
系统中测试 了这种改进算法的性能指标 ,将其和普通算法的性能作了比较 。
【关键词】 数字信号处理器 ;快速傅里叶变换 ;分解 ;反序
中图分类号 :TN957 文献标识码:A
Improvement and Implementation of FFT Algorithm for Long Sequences
SU Tao。ZHUANG De-jing
(Key Laboratory of Radar Signal Processing,Xidian University, Xi an 710071。China)
【Abstract】 An improvement of FVI"algorithm for long sequences is proposed,aiming to reduce the huge computation bur-
den in high speed real time signal processing.By optimizing the number of padding zeros and the DFY decompo sition parameters ,
the computation volume of FFI"is decreased sign ificantly.This algorithm is implemented on the hi【gh speed TSIO1 DSP for applica-
tion to pulse compression processing.By an alyzing resources allocation,programming an d I/O bottleneck,methods are suggested to
improve the algorithm S performan ce.Th e perform an ce is demonstrated in real time sign al processing and is compared with ordinary
proc essing method .
【Key words】 DSP;FFrr;decomposition;bit reverse
0 引 言
F兀'是雷达信号分析与处理中的一种常用的重要
变换。实 际应 用 中,普 遍使 用 基 2或 基 4 F兀'算
法¨ J,该算法的程序代码不因变换点数变化而变化,
旋转因子规律性强,程序紧凑,速度快 。但它所能提供
的 F兀'变换点数必须是 2的整数幂 2 (对基 4 F兀'算
法应为 4 ,其中 h为正整数 ),可是在信号处理 中,处
理的数据个数往往不能满足该条件 ,需要进行补零处
理 ,对小于且接 近于 2 的点数 ,补很少 的零就可以进
行运算 ,对其运算效率不会有太大影响,但对于大于
2 且和 2¨ 相差很 大的点数,补 的零就会 很多 ,这样,
运算量增大,需要的硬件设备量增大,效率降低。Kol—
ba和 Parks提出了 PFA(素因子 vrr)算法 ,其适用
于长度可分解为一些互质因子相乘 的 DFT,能提供一
些特定点数的 DFT快速算法 ,但该算法对数据重排计
算复杂,同址运算不易实现 ,在 DSP上实现时点数越
多程序越复杂。本文针对所计算 F兀'点数的特点 ,提
收稿 日期 :2004-07-07 修订 日期 :2004—11—25
出了结合基 2或基 4 F兀'算法 的一种快速 F兀'算法。
该算法能灵活地改变 F兀'点数 ,程序容量略高于基 2
或基 4 Fn'算法 ,速度与基 2或基4 F兀'算法相近。
1 算法的原理
长度为 Ⅳ的有 限长序列 (凡)的 DFT为
N-I
( )= ∑ (n) , k=0,1,…,N一1 (1)
式中: :exp{一j2'rrkn/N}为旋转因子 。
令 N=N。N2,将 (凡)分解为 Ⅳ2个长度为 Ⅳ。的序
列 ,将这些序列用如下的阵列 X 表示
r x(0) (N2) … (Ⅳ2(N。一1)) ]
xI :
I ( ) (Ⅳ'.+1)… (Ⅳ2(ⅣI_1)+1)l
Lx(N2—1) x(2N2—1) … (Ⅳ2Ⅳ。一1) J
(2)
令 凡和 k的序 号映射定义如下
凡=Ⅳ2凡。+凡 { MN1:: (3)
维普资讯 http://www.cqvip.com
评论0