计算机工程

• 人工智能及识别技术 • 上一篇    下一篇

一种可变长查找表的单基快速傅里叶变换倒序算法

申意  1,2,胡云山  1,2,曾光  1,2,韩文报  1,2   

  1. (1.解放军信息工程大学 四院,郑州 450001; 2.数学工程与先进计算国家重点实验室,江苏 无锡 214125)
  • 收稿日期:2016-03-01 出版日期:2017-03-15 发布日期:2017-03-15
  • 作者简介:申意(1990—),男,硕士研究生,主研方向为网络密码;胡云山,硕士研究生;曾光,副教授、博士;韩文报,教授、博士生导师。
  • 基金项目:
    国家自然科学基金(61003291);数学工程与先进计算国家重点实验室开放课题(2013A03,2013A10)。

A Single-radix Fast Fourier Transform Permutation Algorithm of Variable Length Lookup Table

SHEN Yi  1,2,HU Yunshan  1,2,ZENG Guang  1,2,HAN Wenbao  1,2   

  1. (1.Four Faculty,PLA Information Engineering University,Zhengzhou 450001,China; 2.State Key Laboratory of Mathematical Engineering and Advanced Computing,Wuxi,Jiangsu 214125,China)
  • Received:2016-03-01 Online:2017-03-15 Published:2017-03-15

摘要: 为提高运算速度,降低查找表规模,在原有查找表算法的基础上,提出一种单基快速傅里叶变换原址倒序算法。设计新的查找表构造算法,优化原有查找表的计算方法,并得出在不同倒序计算规模下最优查找表规模选取的一般规律。仿真结果表明,该算法查找表规模可变,通过循环访问查找表平衡选取查找表规模,可减少循环次数,并提高计算速度。

关键词: 快速傅里叶变换倒序, 查找表, 规模, 初始倒序对, 派生倒序对

Abstract: A single-radix Fast Fourier Transform(FFT) in-place permutation algorithm is proposed according to the original lookup table algorithm.A new lookup table configuration method is designed,and the computing method of original lookup table is optimized.The general law of selecting the optimal lookup table scale under different permutation calculation scale is obtained.Simulation results show that the scale of the lookup table is variable.The table can be searched by the cycle, the scale of the lookup table can be selected,the number of cycles can be reduced and the computing speed can be improved.

Key words: Fast Fourier Transform(FFT) permutation, lookup table, scale, initial permutation, derived permutation

中图分类号: