Paper Info
Title
On the Complexity of Hybrid $n$ -Term Karatsuba Multiplier for Trinomials
Abstract
The <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${n}$ </tex-math></inline-formula> -term Karatsuba algorithm (KA) is an extension of 2-term KA, which can obtain even fewer multiplications than the original one. The existing <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${n}$ </tex-math></inline-formula> -term Karatsuba hybrid <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\textit {GF}(2^{m})$ </tex-math></inline-formula> multipliers rely on factorization of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${m}$ </tex-math></inline-formula> or <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${m}-1$ </tex-math></inline-formula> , so that put a confinement to these schemes. In this contribution, we use a new decomposition <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${m}={n}\ell +{r}$ </tex-math></inline-formula> , such that <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$0\leq {r}&lt; {n}$ </tex-math></inline-formula> and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$0\leq {r}&lt; \ell $ </tex-math></inline-formula> , and propose a novel <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${n}$ </tex-math></inline-formula> -term Karatsuba hybrid <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\textit {GF}(2^{m})$ </tex-math></inline-formula> multiplier for an arbitrary irreducible trinomial <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${x}^{m}+{x}^{k}+1, {m}\geq 2{k}$ </tex-math></inline-formula> . Combined with shifted polynomial basis, a new approach (other than Mastrovito approach) is introduced to exploit the spatial correlations among different subexpressions. We investigate the explicit space and time complexities, and discuss related upper and lower bounds. As a main contribution, the flexibilities of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${n}, \ell $ </tex-math></inline-formula> and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${r}$ </tex-math></inline-formula> make our proposal approaching optimal for any given <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${m}$ </tex-math></inline-formula> . The space complexity can achieve to <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${m^{2}}/{2}+{O}({\sqrt {11} {m}^{3/2}}/{2})$ </tex-math></inline-formula> , which roughly matches the best result of current hybrid multipliers for special trinomials. Meanwhile, its time complexity is slightly higher than the counterparts, but can be improved for a new class of trinomials. In particular, we demonstrate that the hybrid multiplier for <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${x}^{m}+{x}^{k}+1$ </tex-math></inline-formula> , where <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${k}$ </tex-math></inline-formula> is approaching <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\frac {m}{2}$ </tex-math></inline-formula> , can achieve a better space-time trade-off than any other trinomials.
Year
DOI
Venue
2020
10.1109/TCSI.2019.2957886
IEEE Transactions on Circuits and Systems I: Regular Papers
Keywords
DocType
Volume
Hybrid multiplier,n-term Karatsuba algorithm,shifted polynomial basis,optimal,trinomials
Journal
67
Issue
ISSN
Citations 
3
1549-8328
0
PageRank 
References 
Authors
0.34
0
5
Name
Order
Citations
PageRank
Yin Li11615.52
Shantanu Sharma200.34
Yu Zhang302.03
Xingpo Ma401.69
Chuanda Qi5146.01