International Journal of Image, Graphics and Signal Processing (IJIGSP)
IJIGSP Vol. 8, No. 10, 8 Oct. 2016
Cover page and Table of Contents: PDF (size: 597KB)
Design of Fast Fourier Transform Architecture for GF(24) with Reduced Operational Complexity
Full Text (PDF, 597KB), PP.35-41
Views: 0 Downloads: 0
Author(s)
Tejaswini P. Deshmukh
1,*
Pooja R. Pawar
1
P. R. Deshmukh
2
P. K. Dakhole
1
Index Terms
Cyclotomic, Fourier Transform, Galois Field
Abstract
In this paper, the architecture for Fast Fourier Transform over Galois Field (24) is described. The method used is cyclotomic decomposition. The Cyclotomic Fast Fourier Transforms (CFFTs) are preferred due to low multiplicative complexity. The approach used is the decomposition of the arbitrary polynomial into a sum of linearized polynomials. Also, Common Subexpression Elimination (CSE) algorithm is used to reduce the additive complexity of the architecture. By using CSE algorithm, the design with reduced operational complexity has been described.
Cite This Paper
Tejaswini P. Deshmukh, Pooja R. Pawar, P. R. Deshmukh, P. K. Dakhole,"Design of Fast Fourier Transform Architecture for GF(24) with Reduced Operational Complexity", International Journal of Image, Graphics and Signal Processing(IJIGSP), Vol.8, No.10, pp.35-41, 2016. DOI: 10.5815/ijigsp.2016.10.05
Reference
[1]Trifonov, Peter. "On the additive complexity of the cyclotomic FFT algorithm." In Information Theory Workshop (ITW), 2012 IEEE, pp. 537-541. IEEE, 2012.
[2]Trifonov, P. V., and S. V. Fedorenko. "A method for fast computation of the Fourier transform over a finite field." Problems of Information Transmission 39, no. 3 (2003): 231-238.
[3]Ghouwayel Ali Al, Yves Louet, Amor Nafkha, and Jacques Palicot. "On the FPGA implementation of the Fourier transform over finite fields GF (2m)." In Communications and Information Technologies, 2007. ISCIT'07. International Symposium on, pp. 146-151. IEEE, 2007.
[4]Wu, Xuebin, Zhiyuan Yan, and Jun Lin. "Reduced- Complexity Decoders of Long Reed-Solomon Codes Based on Composite Cyclotomic Fourier Transforms." Signal Processing, IEEE Transactions on 60.7(2012):3920-3925.
[5]Wu, Ning, et al. "Improving Common Subexpression Elimination Algorithm with A New Gate-Level Delay Computing Method." Proceedings of the World Congress on Engineering and Computer Science. Vol. 2.2013
[6]R. Blahut, "Theory and Practice of Error Control Codes," Reading Massachusetts: Addison-Wesley, 1983.
[7]Shu Lin, Daniel J. Costello Jr., "Error Control Coding," Pearson Education, 2005
[8]Chen, Ning, and Zhiyuan Yan. "Cyclotomic FFTs with reduced additive complexities based on a novel common subexpression elimination algorithm." Signal Processing, IEEE Transactions on 57.3 (2009): 1010-1020.
[9]Chang, Ching-Hsien, Chin-Liang Wang, and Yu-Tai Chang. "Efficient VLSI architectures for fast computation of the discrete Fourier transform and its inverse." Signal Processing, IEEE Transactions on 48.11 (2000): 3206-3216.
[10]Fedorenko, Sergei, and Peter Trifonov. "On computing the fast Fourier transform over finite fields." Proc. 8th Int. Workshop on Algebraic and Combinatorial Coding Theory, Tsarskoe Selo, Russia. 2002.
[11]Wu, Xuebin, et al. "Composite cyclotomic Fourier transforms with reduced complexities." Signal Processing, IEEE Transactions on 59.5 (2011): 2136-2145.
[12]Zhang, Xiaoqiang, et al. "A low-delay common subexpression elimination algorithm for constant matrix multiplications over GF (2 m)." Industrial Electronics and Applications (ICIEA), 2015 IEEE 10th Conference on. IEEE, 2015.
[13]Ahmed, Elias, and Jonathan Rose. "The effect of LUT and cluster size on deep-submicron FPGA performance and density." Very Large Scale Integration (VLSI) Systems, IEEE Transactions on 12.3 (2004): 288-298.
[14]Gao, Shuhong. "A new algorithm for decoding Reed-Solomon codes."Communications, Information and Network Security. Springer US, 2003. 55-68.
[15]R. Blahut,"Algebraic Codes for Data Transmission," Cambridge University Press, 2003.