分裂基算法的讨论.pdf

《现代电子技术》2003 年第 18 期总第 16 1 期 仿真与测试 分裂基算法的讨论 何　璞, 张　平 (西安电子科技大学 电子工程学院　陕西 西安　7 1007 1) 摘　要: 介绍了分裂基 F F T 的原理及其在M at lab 上的实现方法, 并将基 2 算法和分裂基算法进行了性能比较。 关键词: F F T ; 分裂基算法; L 型蝶形; M at lab 中图分类号: T P 30 16　　　　　文献标识码: B 　　　　　文章编号: 1004 373X (2003) 18 03 1 03 D iscussion on Sp l it rad ix FFT H E Pu , ZHAN G P ing ( , , ′, 7 1007 1, ) D ep artm en t o f E lectron ics Eng ineer ing X id ian U n iver sity X i an Ch ina Abstract: T h is ar t icle in t rodu ce s th e p r in cip le o f sp lit rad ix F F T an d im p lem en t s it on m at lab A com p ar ison o f sp lit rad ix fft w ith rad ix 2 F F T is a lso m ade Keywords: F F T ; sp lit rad ix F F T ; L sh ap ed bu t terfly; M at lab 以取大于 8 的基数是没有实际意义的。分裂基算法的 1　引　言 基本思路就是对偶序号输出使用基 2 算法, 对奇序号 快速傅里叶变化 F F T 是离散傅里叶变换的一种 输出使用基 4 算法, 将基 2 分解和基 4 分解组合在一 快速算法。 自 1965 年 Coo ley T uk ey 的算法提出之 起。分裂基算法在 目前已知的所有针对的算法中具有 后, 新的算法不断涌现。总的说来, 这几十年的快速 最少的乘法次数和加法次数, 并且具有好的结构, 运 傅里叶变换的发展方向有 2 个; 一是针对N 等于2 的 算程序也较短, 因此被认为是一种实用的高效算法。后 整数次幂的算法, 如基 2 算法、基 4 算法、实因子算法 来的研究表明, 该算法最接近理论上所需乘法次数的 和分裂基算法等; 另一个是N 不等于 2 的整数次幂的 [2 ]