可变长FFT并行旋转因子高效产生算法及实现

J4 ›› 2009, Vol. 36 ›› Issue (3): 541-546.

可变长FFT并行旋转因子高效产生算法及实现

刘红侠;杨靓;黄巾;黄士坦

(西安微电子技术研究所，陕西西安 710075)

收稿日期:2008-06-30 修回日期:2008-10-23 出版日期:2009-06-20 发布日期:2009-07-04
通讯作者: 刘红侠
基金资助:
国家部委预研基金资助(513160202,417010202)

Effective algorithm of parallel twiddle factor generation for programmable FFT processing and its implementation

LIU Hong-xia;YANG Liang;HUANG Jin;HUANG Shi-tan

(Xi'an Microelectronics Technology Institute, Xi'an 710075， China)

Received:2008-06-30 Revised:2008-10-23 Online:2009-06-20 Published:2009-07-04
Contact: LIU Hong-xia

摘要/Abstract

摘要：

为了解决FFT处理并行旋转因子产生复杂、所需存储资源多的问题，该文在分体存储器结构的基础上，提出了一种新的旋转因子存储、访问策略．该策略保证混合基4/2 FFT算法每个蝶式运算所需的3个旋转因子均可无冲突并行访问，且在同一个旋转因子查找表的基础上，使计算任意小于最大可处理长度的FFT时，各级访问旋转因子地址的产生仅与最大可处理长度有关，而与当前处理长度无关．该算法仅用一个可移位累加数寄存器，实现计算过程中旋转因子地址产生的级间切换，且使一个存储体容量及访问次数减少了一半以上．

关键词: 快速傅里叶变换(FFT), 旋转因子, 混合基4/2, 地址产生单元, FFT处理器

Abstract:

In order to resolve the problem of high complexity and high area consumption in designing a twiddle factor address generator that generates three addresses in every clock cycle, this paper presents a new storage and access strategy of twiddle factors based on the Multi-bank memory structure. The strategy guarantees that the three twiddle factors needed by a butterfly computation of mixed-radix 4/2 FFT algorithm can be accessed simultaneously without conflict. This twiddle factor generating algorithm based on one lookup table for an arbitrary size FFT is dependent only on its maximum size that can be processed. At the same time, the transition from one stage to another can be implemented with a shift addend register. Therefore, this algorithm can be implemented with less complexity and area consumption than any other existing design. In addition, the number of accesses to one of those banks and its size are reduced by at least 50 percent.

Key words: fast Fourier transform(FFT), twiddle factors, mixed radix-4/2, address generating unit, FFT processor

中图分类号:

TP303

刘红侠;杨靓;黄巾;黄士坦. 可变长FFT并行旋转因子高效产生算法及实现[J]. J4, 2009, 36(3): 541-546.

LIU Hong-xia;YANG Liang;HUANG Jin;HUANG Shi-tan. Effective algorithm of parallel twiddle factor generation for programmable FFT processing and its implementation[J]. J4, 2009, 36(3): 541-546.

参考文献

［1］Shin M, Lee H. A High-speed Four-parallel Radix-2⁴ FFT/IFFT Processor for UWB Applications ［C］//IEEE International Symposium on Circuits and Systems, ISCAS 2008. Washington: IEEE, 2008: 960-963.
［2］Lee H, Shin M. A High-Speed Low-Complexity Two-Parallel Radix-2⁴ FFT/IFFT Processor for UWB Applications［C］//IEEE Asian Solid-State Circuits Conference, ASSCC'07. Korea: IEEE, 2007: 284-287.
［3］Han Wei, Erdogan A T, Arslan T. The Development of High Performance FFT IP Cores Through Hybrid Low Power Algorithmic Methodology［C］//Proceedings of Asia and South Pacific Design Automation Conference, ASP-DAC 2005: Volume 1. ShangHai: IEEE, 2005: 549-552.
［4］谢应科, 付博. 数据全并行FFT处理器的设计［J］. 计算机研究与发展, 2004, 41(6): 1022-1029.
Xie Yingke, Fu Bo. Design and Implementation of High Throughput FFT Processor ［J］. Journal of Computer Research and Development, 2004, 41(6): 1022-1029.
［5］Jo B G, Sunwoo M H. New Continuous-flow Mixed-radix (CFMR) FFT Processor Using Novel In-place Strategy ［J］. IEEE Trans on Circuits and Systems, 2005, 52(5): 911-919.
［6］Li Xiaojin, Lai Zongsheng. A Low Power and Small Area FFT Processor for OFDM Demodulator ［J］. IEEE Trans on Consumer Electronics, 2007, 53(2): 274-277.
［7］万红星, 陈禾, 韩月秋. 并行数据FFT/IFFT处理器的设计［J］. 北京理工大学学报, 2006, 26(4): 338-341.
Wan Hongxing, Chen He, Han Qiuyue. Parallel Architecture FFT/IFFT Processor ［J］. Trans of Beijing Institute of Technology, 2006, 26(4): 338-341.
［8］唐江, 刘桥. 基于FPGA 的基-4 FFT 算法的硬件实现［J］. 重庆工学院学报(自然科学版), 2007, 21(3): 82-84.
Tang Jiang, Liu Qiao. Hardware Implementation of Radix 4 FFT Algorithm Based on FPGA ［J］. Journal of Chongqing Institute of Technology(Natural Science Edition), 2007, 21(3): 82-84.
［9］Jiang R M. An Area-Efficient FFT Architecture for OFDM Digital Video Broadcasting ［J］. IEEE Trans on Consumer Electronics, 2007, 53(4): 1322-1326.
［10］Garrido M, Grajal J. Efficient Memoryless Cordic for FFT Computation ［C］//IEEE International Conference on Speech, Signal Processing and Acoustics, ICASSP 2007: Volume 2. Honolulu: IEEE, 2007: 113-116.