Back to Search
Start Over
On the Complexity of Hybrid $n$ -Term Karatsuba Multiplier for Trinomials
- Source :
- IEEE Transactions on Circuits and Systems I: Regular Papers. 67:852-865
- Publication Year :
- 2020
- Publisher :
- Institute of Electrical and Electronics Engineers (IEEE), 2020.
-
Abstract
- The ${n}$ -term Karatsuba algorithm (KA) is an extension of 2-term KA, which can obtain even fewer multiplications than the original one. The existing ${n}$ -term Karatsuba hybrid $\textit {GF}(2^{m})$ multipliers rely on factorization of ${m}$ or ${m}-1$ , so that put a confinement to these schemes. In this contribution, we use a new decomposition ${m}={n}\ell +{r}$ , such that $0\leq {r} and $0\leq {r} , and propose a novel ${n}$ -term Karatsuba hybrid $\textit {GF}(2^{m})$ multiplier for an arbitrary irreducible trinomial ${x}^{m}+{x}^{k}+1, {m}\geq 2{k}$ . 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 ${n}, \ell $ and ${r}$ make our proposal approaching optimal for any given ${m}$ . The space complexity can achieve to ${m^{2}}/{2}+{O}({\sqrt {11} {m}^{3/2}}/{2})$ , 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 ${x}^{m}+{x}^{k}+1$ , where ${k}$ is approaching $\frac {m}{2}$ , can achieve a better space-time trade-off than any other trinomials.
- Subjects :
- Physics
Current (mathematics)
020208 electrical & electronic engineering
Karatsuba algorithm
02 engineering and technology
Trinomial
Space (mathematics)
Upper and lower bounds
Combinatorics
Multiplier (Fourier analysis)
Polynomial basis
Factorization
0202 electrical engineering, electronic engineering, information engineering
Electrical and Electronic Engineering
Subjects
Details
- ISSN :
- 15580806 and 15498328
- Volume :
- 67
- Database :
- OpenAIRE
- Journal :
- IEEE Transactions on Circuits and Systems I: Regular Papers
- Accession number :
- edsair.doi...........98fd1483ae1fb0e5247bfa41b640b38c