Title: N-Term Karatsuba Algorithm and its Application to Multiplier Designs for Special Trinomials
Abstract: In this paper, we propose a new type of non-recursive Mastrovito multiplier for GF(2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m</sup> ) using an n-term Karatsuba algorithm (KA), where GF(2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m</sup> ) is defined by an irreducible trinomial, x <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m</sup> +x <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</sup> +1, m = nk. We show that such a type of trinomial combined with the n-term KA can fully exploit the spatial correlation of entries in related Mastrovito product matrices and lead to a low-complexity architecture. The optimal parameter n is further studied. As the main contribution of this paper, the lower bound of the space complexity of our proposal is about O(m <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> /2) + m <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">3/2</sup> ). Meanwhile, the time complexity matches the best Karatsuba multiplier known to date. To the best of our knowledge, it is the first time that Karatsuba-based multiplier has reached such a space complexity bound while maintaining a relatively low time delay.