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

doi:10.3969/j.issn.1000-3428.2017.03.034

计算机工程

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

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

(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.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

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

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

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

中图分类号:

TP301.6

申意,胡云山,曾光,韩文报. 一种可变长查找表的单基快速傅里叶变换倒序算法[J]. 计算机工程, doi: 10.3969/j.issn.1000-3428.2017.03.034.

SHEN Yi,HU Yunshan,ZENG Guang,HAN Wenbao. A Single-radix Fast Fourier Transform Permutation Algorithm of Variable Length Lookup Table [J]. Computer Engineering, doi: 10.3969/j.issn.1000-3428.2017.03.034.

参考文献

参考文献［1］ Alan H K.Bit Reversal on Uniprocessor［J］.SLAM Review,1996,38(1):289-307. ［2］ Wang H H.On Vectorizing the Fast Fourier Transform［J］.BIT Numerical Mathematics,1980,20(2):233-243. ［3］ Thomas G.Interpolation Algorithms for Discrete Fourier Transform of Weighed Signals［J］.EEE Transactions on Instrumentation & Measurement,1983,32(2):350-355. ［4］Pease M C.An Adaptation of the Fast Fourier Transform for Parallel Processing［J］.Journal of the ACM,1968,15(2):252-264. ［5］ Linzer E N,Feig E.Implementation of Efficient FFT Algorithms on Fused Multiply-add Architectures［J］.IEEE Transactions on Signal Processing,1993,41(1):93-107. ［6］黄佳森,陈帅,王小龙,等.基于映射迭代策略的FFT重排序算法设计［J］.计算机工程,2013,39(9):285-288. ［7］胡广书.数字信号处理理论、算法与实现［M］.北京:清华大学出版社,2003. ［8］ Kass M,Witkin A.Constraints on Deformable Models:Recovering 3D Shape and Nonrigid Motion［J］.Artificial Intelligence,1988,36(1):91-123. ［9］林水生,黄顺吉.一种实现任意基的快速整序算法［J］.电子科技大学学报,1998,27(4):343-346. ［10］应启珩,窦维蓓.离散时间信号分析和处理［M］.北京:清华大学出版社,2001. (下转第212页) (上接第203页) ［11］Yong A.A Better FFT Bit-reversal Algorithm Without Tables［J］.IEEE Transactions on Signal Processing,1991,9(10):2365-2367. ［12］James S W.A New Bit Reversal Algorithm［J］.IEEE Transactions on Acoustics Speech & Signal Processing,1990,38(8):1427-1483. ［13］贾渊,王俊波,姬长英.FFT快速整序算法的对比、改进及实现［J］.电子科技大学学报,2009,38(2):292-295. ［14］ Evans D.A Second Improved Digit-reversal Permutation Algorithm for Fast Fourier Transforms［J］.IEEE Transactions on Acoustics Speech & Signal Processing,1989,37(8):1288-1291. ［15］Evans D.A Second Improved Digit-reversal Permutation Algorithm for Fast Fourier Transforms［J］.IEEE Transactions on Acoustics Speech & Signal Processing,1989,37(8):1288-1291. ［16］汪海兵,徐淑正,杨华中.基于查找表的单基FFT原址倒序算法［J］.清华大学学报(自然科学版),2008,48(1):43-50. 编辑顾逸斐

[1]	王烁, 谷正气, 韩征彤, 马晓骙. 基于改进离散差分进化算法的桁架优化[J]. 计算机工程, 2021, 47(1): 275-283.
[2]	陈泽, 丁琳琳, 宋宝燕, 王俊陆. 大规模动态图中概率游走约束的节点相似Top-k查询方法[J]. 计算机工程, 2021, 47(1): 72-78,86.
[3]	吴玉成, 李亮, 马云飞, 刘统. 基于用户位置信息的导频分配方法[J]. 计算机工程, 2020, 46(8): 164-171.
[4]	丁青锋, 高鑫鹏, 邓玉前. 毫米波中继网络离散正交匹配追踪混合预编码算法[J]. 计算机工程, 2020, 46(7): 192-197,205.
[5]	蒋猛,禹明刚,王智学. 多策略自适应大规模本体映射算法[J]. 计算机工程, 2019, 45(3): 14-19.
[6]	张琼,张勇. 一种针对大规模社交网络的用户信任度预测算法[J]. 计算机工程, 2018, 44(8): 68-73.
[7]	李民政,李艳峰. 大规模MIMO系统中基于迫零预编码的能效优化算法[J]. 计算机工程, 2018, 44(7): 121-125,130.
[8]	孙庆鑫,雷迎春,龚奕利. 基于共享存储的MPP数据库连接执行研究[J]. 计算机工程, 2018, 44(6): 24-28.
[9]	夏秀峰,张刘畅,刘向宇. 面向大规模图数据的分布式可达性索引与查询策略 [J]. 计算机工程, 2018, 44(3): 65-72.
[10]	樊子华,常朝稳,韩培胜,潘冬存. 基于Rete算法的攻击图构建方法[J]. 计算机工程, 2018, 44(3): 151-155,165.
[11]	瞿诗齐,刘少江,倪伟传,余庆茂. 基于Hadoop平台的GPU集群加速Apriori算法[J]. 计算机工程, 2018, 44(11): 14-18,26.
[12]	刘涛涛,禹忠,王军选,杨鹏. 基于SDN的5G大规模MIMO网间频谱共享机制研究[J]. 计算机工程, 2018, 44(11): 100-104.
[13]	贾向东,颉满刚,周猛. 基于带内回程的全双工大规模MIMO异构网覆盖分析[J]. 计算机工程, 2017, 43(7): 124-128,135.
[14]	龙恳,闫冰冰,刘月贞,杜飞. 基于空时域压缩的大规模MIMO导频污染抑制算法[J]. 计算机工程, 2017, 43(7): 141-145.
[15]	陈宇涵,杜学绘,包义保. 基于通用可重构处理器的AES算法设计与实现[J]. 计算机工程, 2017, 43(5): 134-142.

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

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

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 10