作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程

• 开发研究与工程应用 • 上一篇    下一篇

基于映射迭代策略的FFT重排序算法设计

黄佳森a,陈 帅a,王小龙a,叶 凡a,任俊彦a,b   

  1. (复旦大学 a. 专用集成电路与系统国家重点实验室;b. 微纳电子创新平台,上海 201203)
  • 收稿日期:2012-08-29 出版日期:2013-09-15 发布日期:2013-09-13
  • 作者简介:黄佳森(1988-),男,硕士研究生,主研方向:通信集成电路设计;陈 帅、王小龙,硕士研究生;叶 凡,讲师、博士;任俊彦,教授、博士生导师
  • 基金资助:
    国家科技重大专项基金资助项目(2011ZX03004-001-02)

FFT Reordering Algorithm Design Based on Mapping Recursion Strategy

HUANG Jia-sen a, CHEN Shuai a, WANG Xiao-long a, YE Fan a, REN Jun-yan a,b   

  1. HUANG Jia-sena, CHEN Shuaia, WANG Xiao-longa, YE Fana, REN Jun-yana,b
  • Received:2012-08-29 Online:2013-09-15 Published:2013-09-13

摘要: 传统位反算法在对快速傅里叶变换(FFT)的输出进行重排序时,只能以基-2形式输入数据。为此,提出一种新的基于映射迭代策略的算法,实现对任意基形式FFT输入的输出重排序,包括对映射迭代过程收敛性的证明。得出当FFT的输入点数N确定时,混合基形式下迭代次数为lbN的结论,为硬件架构的确定提供依据。

关键词: 混合基, 快速傅里叶变换, 重排序, 映射迭代, 收敛

Abstract: Considering the problem that the traditional bit-reversal algorithm is only fit for radix-2 Fast Fourier Transform(FFT) data reordering, a novel approach based on mapping recursion is proposed for radix-r FFT data reordering. The mapping recursion process is proved to be convergent, of which the recursion times is lbN, while the parameter N refers to the input number of FFT, thus affording the guideline for the implementation by hardware.

Key words: mixed-radix, Fast Fourier Transform(FFT), reordering, mapping recursion, convergence

中图分类号: