FFT快速整序算法的对比、改进及实现

贾渊; 王俊波; 姬长英

doi:10.3969/j.issn.1001-0548.2009.02.32

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

FFT快速整序算法的对比、改进及实现

贾渊, 王俊波, 姬长英

文章导航 > 电子科技大学学报 > 2009 > 38(2): 292-295

贾渊, 王俊波, 姬长英. FFT快速整序算法的对比、改进及实现[J]. 电子科技大学学报, 2009, 38(2): 292-295. doi: 10.3969/j.issn.1001-0548.2009.02.32

引用本文:

贾渊, 王俊波, 姬长英. FFT快速整序算法的对比、改进及实现[J]. 电子科技大学学报, 2009, 38(2): 292-295. doi: 10.3969/j.issn.1001-0548.2009.02.32

JIA Yuan, WANG Jun-bo, JI Chang-ying. Comparison, Improvement, and Implementation of FFT Permutation Algorithm[J]. Journal of University of Electronic Science and Technology of China, 2009, 38(2): 292-295. doi: 10.3969/j.issn.1001-0548.2009.02.32

Citation:

JIA Yuan, WANG Jun-bo, JI Chang-ying. Comparison, Improvement, and Implementation of FFT Permutation Algorithm[J]. Journal of University of Electronic Science and Technology of China, 2009, 38(2): 292-295. doi: 10.3969/j.issn.1001-0548.2009.02.32

FFT快速整序算法的对比、改进及实现

doi: 10.3969/j.issn.1001-0548.2009.02.32

1.
西南科技大学计算机与技术学院四川绵阳 621010;
2.
南京农业大学工学院南京 210031

基金项目:

国家自然科学基金(10776028);国家863项目(2008AA10Z211)

详细信息

作者简介:
贾渊(1973-)，男，博士，副研究员，主要从事图形图像处理方面的研究.

中图分类号: TP31

Comparison, Improvement, and Implementation of FFT Permutation Algorithm

1.
College of Computer Science and Technology,Southwest University of Science and Technology Mianyang Sichuan 621010;
2.
College of Engineering,Nanjing Agricultural University Nanjing 210031

摘要: 提出了一种改进的用于基2的FFT整序算法。改进算法对逆序表的生成进行改进，同时给出另一种数据交换的方案。首先，将顺序号分成组号和组员两部分，采用两个数组存储各组号及组员的数，以(0,2,1,3)为初始逆序表，利用已知组员与组号对应的逆序号的大小关系，求出任意更高阶的逆序表。其次，在数据交换时，避免了常规整序中顺序号与逆序号的比较运算。在Windows操作系统下编制了相关算法的C++程序，比较了运行效率，实验表明，改进算法效率最高。
- FFT整序 /
- 组号 /
- 组员 /
- 序号分组 /
- 逆序
Abstract: A new improved permutation algorithm for radix 2 fast Fourier transforms (FFTs) is discribed. The algorithm provides an improved way for obtaining the bit reversal index table and affords an alternative data permutation methods. First, The algorithm divides an index with two parts, one is called group-index, which represents the index belonging to some group, and the other is called group-member which represents the order in the group. And then two arrays are used to store the values of the group-index and group-member power. According to the relationship between the bit reversal values of group-index and group-member, any bit reversal table can be obtained with the known one, which is (0,2,1,3). Second, when the data are needed to permute, the improved algorithm avoids the comparison operations between the index and its corresponding bit reversal value, which are required in the general permutation algorithm. In order to test its performance in the windows operation systems, several algorithms are programmed with C++ language, and their operation times are compared. The experiments show that the performance of the improved algorithm introduced in this paper is superior to that of the relative algorithms.
- FFT permutation /
- group-index /
- group-member /
- indices grouping /
- inverse order

[1]	周丰丰, 孙燕杰, 范雨思. 基于miRNA组学的数据增强算法 . 电子科技大学学报, 2023, 52(2): 182-187. doi: 10.12178/1001-0548.2023002
[2]	王静, 雷珂, 李家仪, 田松涛, 王相隆. 基于非均匀循环编码的分组修复码构造 . 电子科技大学学报, 2022, 51(1): 57-64. doi: 10.12178/1001-0548.2021013
[3]	王永娟, 张诗怡, 王涛, 高杨. 对MIBS分组密码的差分故障攻击 . 电子科技大学学报, 2018, 47(4): 601-605. doi: 10.3969/j.issn.1001-0548.2018.04.020
[4]	向勇, 闫宗楷, 朱焱麟, 张晓琨. 材料基因组技术前沿进展 . 电子科技大学学报, 2016, 45(4): 634-649. doi: 10.3969/j.issn.1001-0548.2016.04.016
[5]	刘梦娟, 魏小东, 王勇. 基于延时抖动趋势的分层组播方案 . 电子科技大学学报, 2011, 40(5): 747-752. doi: 10.3969/j.issn.1001-0548.2011.05.022
[6]	王俊芳, 张思东. 通用高速分组交换调度算法 . 电子科技大学学报, 2010, 39(1): 69-73. doi: 10.3969/j.issn.1001-0548.2010.01.017
[7]	舒剑, 许春香. 高效的口令基认证组密钥协商协议 . 电子科技大学学报, 2009, 38(3): 393-396. doi: 10.3969/j.issn.1001-0548.2009.03.018
[8]	程德强, 钱建生, 杨红丽. 组播服务节点选择问题的求解算法 . 电子科技大学学报, 2008, 37(4): 523-526.
[9]	姚奕, 刘晓明, 黄松. 基于模糊偏序关系的软件测试评价方法 . 电子科技大学学报, 2007, 36(3): 503-505,509.
[10]	罗岚, 瞿泽辉, 周世杰, 张凤荔, 秦志光, 魏正耀. 带延迟的分组密码算法密钥结合模式设计 . 电子科技大学学报, 2007, 36(3): 649-651.
[11]	胡廉民, 张九华. 分组密码算法的测试方法研究 . 电子科技大学学报, 2007, 36(4): 720-722,736.
[12]	王友仁, 张砦, 施玉霞, 姚睿. 题库系统智能成卷理论和组卷方法研究 . 电子科技大学学报, 2006, 35(3): 363-366.
[13]	徐洁, 李炜. 一种基于聚合和隧道技术的MPLS组播新策略 . 电子科技大学学报, 2006, 35(2): 228-231.
[14]	宋高俊, 周正中, 钟俊. 宽带非相干空时频分组编码 . 电子科技大学学报, 2006, 35(2): 168-170,178.
[15]	刘民岷, 刘璟. 一个组播分布式访问控制系统 . 电子科技大学学报, 2005, 34(5): 642-645.
[16]	曾宪雯. 线性方程组并行迭代解法的新思路 . 电子科技大学学报, 2005, 34(3): 413-416.
[17]	蒋宗明, 唐斌, 吴伟. 基于DFT滤波器组的多信号高效数字下变频 . 电子科技大学学报, 2005, 34(6): 743-746.
[18]	任立勇. 一种基于分组对的分层组播拥塞控制机制 . 电子科技大学学报, 2002, 31(6): 602-607.
[19]	涂晓东, 李乐民. 分组公平排队算法的仿真研究 . 电子科技大学学报, 2000, 29(4): 440-444.
[20]	林水生, 黄顺吉. 一种实现任意基FFT的快速整序算法 . 电子科技大学学报, 1998, 27(4): 343-346.

点击查看大图

计量

文章访问数: 3427
HTML全文浏览量: 112
PDF下载量: 43
被引次数: 0

FFT快速整序算法的对比、改进及实现

doi: 10.3969/j.issn.1001-0548.2009.02.32

1. 西南科技大学计算机与技术学院四川绵阳 621010;

2. 南京农业大学工学院南京 210031

基金项目:

国家自然科学基金(10776028);国家863项目(2008AA10Z211)

作者简介:
贾渊(1973-)，男，博士，副研究员，主要从事图形图像处理方面的研究.

收稿日期: 2007-11-22
修回日期: 2008-04-15
刊出日期: 2009-04-15

中图分类号: TP31

关键词:

FFT整序 /
组号 /
组员 /
序号分组 /
逆序

摘要: 提出了一种改进的用于基2的FFT整序算法。改进算法对逆序表的生成进行改进，同时给出另一种数据交换的方案。首先，将顺序号分成组号和组员两部分，采用两个数组存储各组号及组员的数，以(0,2,1,3)为初始逆序表，利用已知组员与组号对应的逆序号的大小关系，求出任意更高阶的逆序表。其次，在数据交换时，避免了常规整序中顺序号与逆序号的比较运算。在Windows操作系统下编制了相关算法的C++程序，比较了运行效率，实验表明，改进算法效率最高。

English Abstract

Comparison, Improvement, and Implementation of FFT Permutation Algorithm

1. College of Computer Science and Technology,Southwest University of Science and Technology Mianyang Sichuan 621010;

2. College of Engineering,Nanjing Agricultural University Nanjing 210031

Received Date: 2007-11-22
Rev Recd Date: 2008-04-15
Publish Date: 2009-04-15

Keywords:

Abstract: A new improved permutation algorithm for radix 2 fast Fourier transforms (FFTs) is discribed. The algorithm provides an improved way for obtaining the bit reversal index table and affords an alternative data permutation methods. First, The algorithm divides an index with two parts, one is called group-index, which represents the index belonging to some group, and the other is called group-member which represents the order in the group. And then two arrays are used to store the values of the group-index and group-member power. According to the relationship between the bit reversal values of group-index and group-member, any bit reversal table can be obtained with the known one, which is (0,2,1,3). Second, when the data are needed to permute, the improved algorithm avoids the comparison operations between the index and its corresponding bit reversal value, which are required in the general permutation algorithm. In order to test its performance in the windows operation systems, several algorithms are programmed with C++ language, and their operation times are compared. The experiments show that the performance of the improved algorithm introduced in this paper is superior to that of the relative algorithms.

贾渊, 王俊波, 姬长英. FFT快速整序算法的对比、改进及实现[J]. 电子科技大学学报, 2009, 38(2): 292-295. doi: 10.3969/j.issn.1001-0548.2009.02.32

引用本文:

贾渊, 王俊波, 姬长英. FFT快速整序算法的对比、改进及实现[J]. 电子科技大学学报, 2009, 38(2): 292-295. doi: 10.3969/j.issn.1001-0548.2009.02.32

Citation:

全文HTML

下载: 全尺寸图片幻灯片

返回文章

用微信扫码二维码

分享至好友和朋友圈

编辑办公

友情链接

电子科技大学

地址: 成都市建设北路二段四号电子科技大学主楼中350室电话: 028-83202308,83207559 Email: xuebao@uestc.edu.cn

本系统由北京仁和汇智信息技术有限公司开发

留言板

FFT快速整序算法的对比、改进及实现

doi: 10.3969/j.issn.1001-0548.2009.02.32

作者简介:
贾渊(1973-)，男，博士，副研究员，主要从事图形图像处理方面的研究.

Comparison, Improvement, and Implementation of FFT Permutation Algorithm

计量

FFT快速整序算法的对比、改进及实现

doi: 10.3969/j.issn.1001-0548.2009.02.32

1. 西南科技大学计算机与技术学院四川绵阳 621010;

2. 南京农业大学工学院南京 210031

作者简介:
贾渊(1973-)，男，博士，副研究员，主要从事图形图像处理方面的研究.

English Abstract

Comparison, Improvement, and Implementation of FFT Permutation Algorithm

1. College of Computer Science and Technology,Southwest University of Science and Technology Mianyang Sichuan 621010;

2. College of Engineering,Nanjing Agricultural University Nanjing 210031

全文HTML

目录

期刊在线

编辑办公

友情链接

留言板

FFT快速整序算法的对比、改进及实现

doi: 10.3969/j.issn.1001-0548.2009.02.32

作者简介: 贾渊(1973-)，男，博士，副研究员，主要从事图形图像处理方面的研究.

Comparison, Improvement, and Implementation of FFT Permutation Algorithm

计量

出版历程

FFT快速整序算法的对比、改进及实现

doi: 10.3969/j.issn.1001-0548.2009.02.32

1. 西南科技大学计算机与技术学院 四川 绵阳 621010; 2. 南京农业大学工学院 南京 210031

作者简介: 贾渊(1973-)，男，博士，副研究员，主要从事图形图像处理方面的研究.

English Abstract

Comparison, Improvement, and Implementation of FFT Permutation Algorithm

1. College of Computer Science and Technology,Southwest University of Science and Technology Mianyang Sichuan 621010; 2. College of Engineering,Nanjing Agricultural University Nanjing 210031

全文HTML

目录

期刊在线

编辑办公

友情链接

作者简介:
贾渊(1973-)，男，博士，副研究员，主要从事图形图像处理方面的研究.

1. 西南科技大学计算机与技术学院四川绵阳 621010;

2. 南京农业大学工学院南京 210031

作者简介:
贾渊(1973-)，男，博士，副研究员，主要从事图形图像处理方面的研究.

1. College of Computer Science and Technology,Southwest University of Science and Technology Mianyang Sichuan 621010;

2. College of Engineering,Nanjing Agricultural University Nanjing 210031