Dual-Butterfly Parallel Access Constant Geometry Pipeline Radix-2 FNT Algorithm

Abstract:

A dual-butterfly parallel access constant geometry pipeline radix-2 FNT (Fermat Number Transform) is proposed to enhance the computing performance of FNT. By the extending the conventional constant geometry FNT, two radix-2 butterflies could be calculated simultaneously in each stage, and the address generating method for parallel access without conflicts is deduced to make the dual-butterfly’s four operators fetched and stored at the same time. Compared with other single data stream FNT, the efficiency is enhanced by 3 times. Compared with the traditional convolution and the convolution based on conventional FNT, the convolution based on the proposed algorithm has the advantage in computing efficiency, which also indicates the efficiency of the proposed algorithm.

• Periodical: Applied Mechanics and Materials (Volumes 220-223)
• Pages: 2192-2198
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.220-223.2192
• Online since: November 2012
• Authors: Dan Huang, Ji Yang Yu, Hong Meng, Xiao Ping Huang, Yuan Feng, Guang Yun Li, Wen Wei Li
• Keywords: Constant Geometry, Dual-Butterfly, FNT, Parallel Access

References

[1] J. Zhang, S. G. Li, High Speed Parallel Architecture for Cyclic Convolution Based on FNT, IEEE Computer Society Annual Symposium on VLSI, 2009: 199-204.

DOI: 10.1109/isvlsi.2009.10

[2] E. D. Mark, S. M. Eugene, A microcode implementation of a fermat number transform for fast digital convolution, IEEE Conference on Decision and Control including the Symposium on Adaptive Processes, 1980: 1235-1241.

DOI: 10.1109/cdc.1980.272000

[3] C. Cheng, K.K. Parhi, Hardware efficient fast DCT based on novel cyclic convolution structures, IEEE Trans. Signal processing, 2006, 54(11), pp.4419-4434.

DOI: 10.1109/tsp.2006.881269

[4] T. Toivonen and J. Heikkila, Video Filtering With Fermat Number Theoretic Transforms Using Residue Number System, IEEE Trans. on Circuits and Systems for Video Technology, 2006, 16(1): 92-101.

DOI: 10.1109/tcsvt.2005.858612

[5] S. Gudvangen and A. Patel, Rapid synthesis of a macro-pipelined CMOS ASIC for the Fermat number transform, Proc. NORSIG, 1-2 Sept. 1995, Stavanger, Norway: 143–148.

[6] J. H. McClellan, Hardware realization of a fermat number transform, IEEE Trans. on Acoustics Speech, and Signal Processing, 1976, asps-24(3): 216-225.

DOI: 10.1109/tassp.1976.1162806

[7] M. Benaissa, S.S. Dlay, A.G.J. Holt, CMOS VLSI design of a high-speed Fermat number transform based convolver/correlator using three-input adders, Circuits, Devices and Systems, IEE Proceedings G, Vol. 138(2),1991: 182-190.

DOI: 10.1049/ip-g-2.1991.0035

[8] S. Gudvangen, A Class of Sliding Fermat Number Transforms that Admit a Tradeoff Between Complexity and Input–Output Delay, IEEE Trans. on Signal Processing, 1997, 45(12): 3094-3096.

DOI: 10.1109/78.650272

[9] T. Tao, J.-P. Chu and Z.-S. Lai, et al, A parameterized FPGA realization of high-speed FNT processor, Microelectronics and Computer, 2004, 21(10): 165-169.

[10] G. Suraj, P. Aaron , J. Robert . Werthimer, Dan. Automated placement for parallelized FPGA FFTs, IEEE International Symposium on Field-Programmable Custom Computing Machines, 2011: 206-209.

DOI: 10.1109/fccm.2011.52