Full Text:
<3337>
CLC number: TP30
On-line Access:
Received: 2009-05-18
Revision Accepted: 2009-08-14
Crosschecked: 2009-08-14
Cited: 1
Clicked: 5299
Novel algorithm for complex bit reversal: employing vector permutation and branch reduction methods
| |||||||||||||
Feng YU, Ze-ke WANG, Rui-feng GE. Novel algorithm for complex bit reversal: employing vector permutation and branch reduction methods[J]. Journal of Zhejiang University Science A, 2009, 10(10): 1492-1499.
@article{title="Novel algorithm for complex bit reversal: employing vector permutation and branch reduction methods",
author="Feng YU, Ze-ke WANG, Rui-feng GE",
journal="Journal of Zhejiang University Science A",
volume="10",
number="10",
pages="1492-1499",
year="2009",
publisher="Zhejiang University Press & Springer",
doi="10.1631/jzus.A0920290"
}
%0 Journal Article
%T Novel algorithm for complex bit reversal: employing vector permutation and branch reduction methods
%A Feng YU
%A Ze-ke WANG
%A Rui-feng GE
%J Journal of Zhejiang University SCIENCE A
%V 10
%N 10
%P 1492-1499
%@ 1673-565X
%D 2009
%I Zhejiang University Press & Springer
%DOI 10.1631/jzus.A0920290
TY - JOUR
T1 - Novel algorithm for complex bit reversal: employing vector permutation and branch reduction methods
A1 - Feng YU
A1 - Ze-ke WANG
A1 - Rui-feng GE
J0 - Journal of Zhejiang University Science A
VL - 10
IS - 10
SP - 1492
EP - 1499
%@ 1673-565X
Y1 - 2009
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/jzus.A0920290
Abstract: We present novel vector permutation and branch reduction methods to minimize the number of execution cycles for bit reversal algorithms. The new methods are applied to single instruction multiple data (SIMD) parallel implementation of complex data floating-point fast Fourier transform (FFT). The number of operational clock cycles can be reduced by an average factor of 3.5 by using our vector permutation methods and by 1.1 by using our branch reduction methods, compared with conventional implementations. Experiments on MPC7448 (a well-known SIMD reduced instruction set computing processor) demonstrate that our optimal bit-reversal algorithm consistently takes fewer than two cycles per element in complex array operations.
[1] Burrus, C.S., 1988. Unscrambling for fast DFT algorithms. IEEE Trans. Acoust. Speech Signal Process., 36(7):1086-1087.
[2] Carter, L., Gatlin, K.S., 1998. Towards an Optimal Bit-reversal Permutation Program. Proc. 39th Annual Symp. on Foundations of Computer Science, p.544-553.
[3] Chakraborty, T.S., Chakrabarti, S., 2008. On Output Reorder Buffer Design of Bit Reversed Pipelined Continuous Data FFT Architecture. IEEE Asia Pacific Conf. on Circuits and Systems, p.1132-1135.
[4] Chen, L., Hu, Z., Lin, J.M., Gao, G.R., 2007. Optimizing the Fast Fourier Transform on Multi-core Architecture. IEEE Int. Parallel and Distributed Processing Symp., p.1-8.
[5] Drouiche, K., 2001. A new efficient computational algorithm for bit reversal mapping. IEEE Trans. Signal Process., 49(1):251-254.
[6] Evans, D., 1987. An improved digital-reversal permutation algorithm for the fast Fourier transforms. IEEE Trans. Acoust. Speech Signal Process., 35(8):1120-1125.
[7] Evans, D., 1989. A second improved digital-reversal permutation algorithm for the fast Fourier transforms. IEEE Trans. Acoust. Speech Signal Process., 37(8):1288-1291.
[8] Freescale Semiconductor, 2005. MPC7450 RISC Microprocessor Family Reference Manual [online]. Available from http://www.freescale.com/files/32bit/doc/ref_manual/MPC7450UM.pdf [Rev.5].
[9] Freescale Semiconductor, 2007. MPC7450 RISC Microprocessor Family Software Optimization Guide [online]. Available from http://www.freescale.com/files/32bit/doc/app_note/AN2203.pdf [Rev.2].
[10] Jana, P.K., Sinha, K., 2008. Permutation algorithms on optical multi-trees. Comput. Math. Appl., 56(10):2656-2665.
[11] Lloyd, B., Boyd, C., Govindaraju, N.K., 2008. Fast Computation of General Fourier Transforms on GPUs. IEEE Int. Conf. on Multimedia and Expo, p.5-8.
[12] Lokhmotov, A., Mycroft, A., 2007. Optimal Bit-reversal Using Vector Permutations. Proc. 19th Annual ACM Symp. on Parallel Algorithms and Architectures, p.198-199.
[13] Marti-Puig, P., 2009. Two families of radix-2 FFT algorithms with ordered input and output data. IEEE Signal Process. Lett., 16(2):65-68.
[14] Pei, S.C., Chang, K.W., 2007. Efficient bit and digital reversal algorithm using vector calculation. IEEE Trans. Signal Process., 55(3):1173-1175.
[15] Püschel, M., Milder, P.A., Hoe, J.C., 2009. Permuting streaming data using RAMs. J. ACM, 56(2):Article No. 10, p.1-34.
[16] Sundararajan, D., Ahmad, M.O., Swamy, M.N.S., 1994. A fast FFT bit-reversal algorithm. IEEE Trans. Circuits Syst. II: Anal. Dig. Signal Process., 41(10):701-703.
[17] Walker, J., 1990. A new bit-reversal algorithm. IEEE Trans. Acoust. Speech Signal Process., 38(8):1472-1473.
[18] Yong, A.A., 1991. A better FFT bit-reversal algorithm without tables. IEEE Trans. Signal Process., 39(10):2365-2367.
Open peer comments: Debate/Discuss/Question/Opinion
<1>