Modified Karatsuba multiplier for key equation solver in RS code
DOI:
https://doi.org/10.3103/S0735272715100039Keywords:
finite fields, Karatsuba algorithm, Galois field multiplier, equation solver, Reed Solomon code, VLSI, FPGAAbstract
Finite field arithmetics are often used in linear block codes such as BCH and Reed–Solomon codes and also in cryptographic algorithms. Finite field multipliers play an important role and consume a significant amount of area in VLSI design. This paper presents an improved generalized Karatsuba multiplier. Optimization of the Karatsuba multiplication algorithm can be done by splitting the product terms into two alternative forms and expressing all the terms in the repeated fashion. We have compared the hardware requirement of our proposed multiplier with the original Karatsuba multiplier. The proposed multiplier requires lesser number of additions compared to original Karatsuba multiplier and the overall area is reduced by 53.75% (without reduction) and 52.08% (with reduction). The proposed multiplier is also faster than the original Karatsuba multiplier by 3.63% (without reduction) and 3.91% (with reduction). The proposed modified Karatsuba multiplier is also applied to compute key equation in RS(47, 41) decoder which is applied in intelligent home networking. All the simulation works were done using Xilin14.3 ISE simulator and the multipliers were implemented in Vertex 5 FPGA device family.References
BERLEKAMP, E.R. Bit-serial Reed-Solomon encoders. IEEE Trans. Inf. Theory, Nov. 1982, v.28, n.6, p.869-874, DOI: http://dx.doi.org/10.1109/TIT.1982.1056591.
ZHANG, TONG; PARHI, K.K. Systematic design of original and modified Mastrovito multipliers for general irreducible polynomials. IEEE Trans. Comput., Jul. 2001, v.50, n.7, p.734-749, DOI: http://dx.doi.org/10.1109/12.936239.
REYHANI-MASOLEH, R.; HASAN, M.A. A new construction of Massey-Omura parallel multiplier over GF(2m). IEEE Trans. Comput., May 2002, v.51, n.5, p.511-520, DOI: http://dx.doi.org/10.1109/TC.2002.1004590.
WANG, C.C.; TRUONG, T.K.; SHAO, H.M.; DEUTSCH, L.J.; OMURA, J.K.; REED, I.S. VLSI architectures for computing multiplications and inverses in GF(2m). IEEE Trans. Comput., Aug. 1985, v.C-34, n.8, p.709-717, DOI: http://dx.doi.org/10.1109/TC.1985.1676616.
SHI, ZHIJIE JERRY; YUN, HAI. Software implementations of elliptic curve cryptography. Int. J. Network Security, 2008, v.7, n.1, p.141-150, http://ijns.jalaxy.com.tw/download_paper.jsp?PaperID=IJNS-2006-09-13-3&PaperName=ijns-v7-n1/ijns-2008-v7-n1-p141-150.pdf.
LEE, TRONG-YEN; LIU, MIN-JEA; FAN, CHIA-CHEN; TSAI, CHIA-CHUN; WU, HAIXIA. Low complexity digit-serial multiplier over GF(2^m) using Karatsuba technology. Proc. of Seven Int. Conf. on Complex, Intelligent, and Software Intensive Systems, CISIS, 3-5 July 2013, Taichung. IEEE, 2013, p.461-466, DOI: http://dx.doi.org/10.1109/CISIS.2013.84.
ERDEM, S.S.; KOC, C.K. A less recursive variant of Karatsuba-Ofman algorithm for multiplying operands of size a power of two. Proc. of 16th IEEE Symp. on Computer Arithmetic, 15-18 June 2003. IEEE, 2003, p.28-35, DOI: http://dx.doi.org/10.1109/ARITH.2003.1207657.
CENK, M.; OZBUDAK, F. Improved polynomial multiplication formulas over F2 using chinese remainder theorem. IEEE Trans. Comput., Apr. 2009, v.58, n.4, p.572-576, DOI: http://dx.doi.org/10.1109/TC.2008.207.
ZHOU, GANG; MICHALIK, H.; HINSENKAMP, L. Complexity analysis and efficient implementations of bit parallel finite field multipliers based on Karatsuba-Ofman algorithm on FPGAs. IEEE Trans. Very Large Scale Integration (VLSI) Systems, Jul. 2010, v.18, n.7, p.1057-1066, DOI: http://dx.doi.org/10.1109/TVLSI.2009.2020088.
PAAR, C.; FLEISCHMANN, P.; ROEISE, P. Efficient multiplier architectures for Galois fields GF(24n). IEEE Trans. Comput., Feb. 1998, v.47, n.2, p.162-170, DOI: http://dx.doi.org/10.1109/12.663762.
WEIMERSKIRCH, A.; PAAR, C. Generalizations of the Karatsuba algorithm for efficient implementations, 2010, http://www.ei.rub.de/media/crypto/veroeffentlichungen/2010/08/08/kaweb.pdf.
XIE, XIAO-NING; CHEN, GONG-LIANG; LI, YIN. Novel bit-parallel multiplier for GF(2m) defined by all-one polynomial using generalized Karatsuba algorithm. Inform. Process. Lett., Mar. 2014, v.114, n.3, p.140-146, DOI: http://dx.doi.org/10.1016/j.ipl.2013.10.009.
DYKA, ZOYA; LANGENDOERFER, PETER, VATER, FRANK. Combining multiplication methods with optimized processing sequence for polynomial multiplier in GF(2k). Research in Cryptology. Lect. Notes Comput. Sci., 2011, v.7242, p.137-150, DOI: http://dx.doi.org/10.1007/978-3-642-34159-5_10.
SAMANTA, JAGANNATH; SULTANA, RAZIA; BHAUMIK, JAYDEB. FPGA based modified Karatsuba multiplier. Proc. of Int. Conf. on VLSI and Signal Processing, ICVSP14, 10-12 Jan. 2014, IIT Kharagpur, 2014.
WICKER, STEPHEN B.; BHARGAVA, V.K. Reed-Solomon Codes and Their Applications. New York: Wiley-IEEE Press, 1999, ISBN: 978-0-7803-5391-6.
SARWATE, D.V.; SHANBHAG, N.R. High-speed architectures for Reed-Solomon decoders. IEEE Trans. Very Large Scale Integration (VLSI) Systems, Oct. 2001, v.9, n.5, p.641-655, DOI: http://dx.doi.org/10.1109/92.953498.
JIN, IK SOO. Design and implementation of efficient Reed-Solomon decoder for intelligent home networking. Communication and Networking. Berlin Heidelberg: Springer, 2012, p.261-268, DOI: http://dx.doi.org/10.1007/978-3-642-27192-2_31.
KARATSUBA, A.; OFMAN, Y. Multiplication of many-digital numbers by automatic computers. Doklady Physics, 1963, n.7, p.595-596.
