Paper 2019/111

On the Complexity of non-recursive $n$-term Karatsuba Multiplier for Trinomials

Yin Li and Yu Zhang and Xingpo Ma and Chuanda Qi

Abstract

In this paper, we continue the study of bit-parallel multiplier using a $n$-term Karatsuba algorithm (KA), recently introduced by Li et al. (IEEE Access 2018). Such a $n$-term KA is a generalization of the classic KA, which can multiply two $n$-term polynomials using $O(n^2/2)$ scalar multiplications. Based on this observation, Li et al. developed an efficient bit-parallel multiplier scheme for a new special class of irreducible trinomial $x^{m}+x^{k}+1, m=nk$. The lower bound of the space complexity of their proposal is about $O(\frac{m^2}{2}+m^{3/2})$. However, such a special type of trinomial does not always exist. In this contribution, we investigate the space and time complexity of Karatsuba multiplier for general trinomials, i.e., $x^m+x^k+1$ where $m>2k$. We use a new decomposition that $m=n\ell+r$, where $r<n, r<\ell$. Combined with shifted polynomial basis (SPB), a new approach other than Mastrovito approach is proposed to exploit the spatial correlation between different subexpressions. Explicit space and time complexity formulations are given to indicate the optimal choice of the decomposition. As a result, the optimal multiplier achieves nearly the same space complexity as $x^{m}+x^{k}+1, m=nk$, but it is suitable to more general trinomials. Meanwhile, its time complexity matches or is at most $1T_X$ higher than the similar KA multipliers, where $T_X$ is the delay of one 2-input XOR gate.

Note: This is a sigle column version