Search

Multiplication schemes based on Toeplitz matrix-vector product (TMVP) have been proposed by many researchers. TMVP can be computed using the recursive two-way and three-way split methods, which are composed of four blocks. Among them, we improve the space complexity of the component matrix formation (CMF) block. This result derives the improvements of multiplication schemes based on TMVP. Also, we present a subquadratic space complexity $GF(2^m)$ multiplier with even type Gaussian normal basis (GNB). In order to design the multiplier, we formulate field multiplication as a sum of two TMVPs and efficiently compute the sum. As a result, for type 2 and 4 GNBs, the proposed multipliers outperform other similar schemes. The proposed type 6 GNB is the first subquadrtic space complexity multiplier with its explicit complexity formula.

In this paper, we present new parallel polynomial multiplication formulas which result in subquadratic space complexity. The schemes are based on a recently proposed block recombination of polynomial multiplication formula. The proposed two-way, three-way, and four-way split polynomial multiplication formulas achieve the smallest space complexities. Moreover, by providing area-time tradeoff method, the proposed formulas enable one to choose a parallel formula for polynomial multiplication which is suited for a design environment.

We propose block decompositions for the Toeplitz matrix-vector product (TMVP) using the $k$ -way splitting method presented in the above paper. As a result, we show that the space complexity for TMVP can be improved.

In the above paper, Akleylek proposed an efficient multiplication algorithm for polynomials in Chebyshev form. In this comment, we show that a recombination of the above proposed algorithm induces more efficient algorithm for the multiplications of polynomials in Chebyshev form.

This paper presents a new bit-parallel multiplier for the finite field GF(2/sup m/) defined by an irreducible all-one polynomial. In order to reduce the complexity of the multiplier, we introduce a redundant representation and use the well-known multiplication method proposed by Karatsuba. The main idea is to combine the redundant representation and the Karatsuba method to design an efficient bit-parallel multiplier. As a result, the proposed multiplier requires about 25 percent fewer AND/XOR gates than the previously proposed multipliers using an all-one polynomial, while it has almost the same time delay as the previously proposed ones.