New Bit Parallel Multiplier With Low Space Complexity for All Irreducible Trinomials Over GF(2^)

• Published in: IEEE transactions on very large scale integration (VLSI) systems 2012-10, Vol.20 (10), p.1903-1908
• Main Authors: Cho, Young In, Chang, Nam Su, Kim, Chang Han, Park, Young-Ho, Hong, Seokhie
• Format: Article
• Language: English
• Subjects: Applied sciences; Bit-parallel multiplier; Circuit properties; Complexity theory; Computer architecture; Delay; Design. Technologies. Operation analysis. Testing; Digital circuits; Electric, optical and optoelectronic circuits; Electronic circuits; Electronics; Exact sciences and technology; finite field; Integrated circuits; irreducible trinomial; Logic gates; Mastrovito multiplication; polynomial basis; Polynomials; Semiconductor electronics. Microelectronics. Optoelectronics. Solid state devices
• ISSN: 1063-8210; 1557-9999
• DOI: 10.1109/TVLSI.2011.2162594

Koç and Sunar proposed an architecture of the Mastrovito multiplier for the irreducible trinomial f(x)=x n +x k + 1 , where k ≠ n/2 to reduce the time complexity. Also, many multipliers based on the Karatsuba-Ofman algorithm (KOA) was proposed that sacrificed time efficiency for low space complexity. In this paper, a new multiplication formula which is a variant of KOA presented. We also provide a straightforward architecture of a non-pipelined bit-parallel multiplier using the new formula. The proposed multiplier has lower space complexity than and comparable time complexity to previous Mastrovito multipliers' for all irreducible trinomials.