Low-Complexity Digit-Serial MultiplierOverGF(2m)Based on Efficient Toeplitz Block Toeplitz Matrix–Vector ProductDecomposition
Abstract:
In this paper, we have shown that a regular Toeplitz matrix-vector product (TMVP) can be transformed into a Toeplitz block TMVP (TBTMVP) using a suitable permutation matrix. Based on the TBTMVP representation, we have proposed a new (a,b)-way TBTMVP decomposition algorithm for implementing a digit-serial multiplication. Moreover, it is shown that, based on iterative block recombination, we can improve the space complexity of the proposed TBTMVP decomposition. From the synthesis results, we have shown that the proposed TBTMVP-based multiplier involves less area, less area–delay product, and higher throughput compared with the existing digitserial multipliers. The proposed architecture of this paper analysis the logic size, area and power consumption using Xilinx 14.2.
Existing System:
In binary extension fields, the efficiency of algorithmsand architectures for multiplications depends on the basis ofrepresentation, e.g., polynomial basis (PB), dual basis/doublebasis (DB), and normal basis. Architectures for multiplication are classified into bit-serial, digit-serial, and bit-parallelstructures. Finite field multiplication over binaryextension fields involves a naive polynomial multiplicationfollowed by degree reduction by irreducible polynomial, whichgenerates the field. Since sparse irreducible polynomials, suchas trinomials and pentanomials, exist overGF(2),thecomplexity of degree reduction is simpler compared with the polynomial multiplication. Bit-serial multipliers generally have lessarea and large computation time, while bit-parallel multipliersperform fast computation and involve large hardware cost.
Digit-serial multipliers provide the desired tradeoff betweenspace and time complexities. Several approaches for digitserial multiplier designs have been proposed in the literature. It is found that Toeplitz matrix-vector product (TMVP)formulation can lead to low-complexity hardware architecture for field multiplication. Shifted PB (SPB) multiplication based on coefficient transformation method is used toconstruct a TMVP-based multiplication.A modified SPB (MSPB) multiplication based on basis conversionapproach is used for the TMVP computation. Employing theTMVP approach, efficient digit-serial multiplication architectures are proposed.Karatstsuba algorithm (KA) decomposition is wellknown for high-precision multiplication, which leads to subquadratic space-complexity designs for bit-parallel multiplication. It can be realized with O(nlog23) space complexity bytwo-way decomposition, herenis a power of 2. Usinga-waydecomposition, it can be realized byO(nloga((a2+a)/2)) spacecomplexity. Recently, Leeet al.have presented a generalized(a,b)-way KA decompositionfor digit-serial multiplication for a>b>0, which resultsin subquadratic space complexity, while traditional digit-serialmultipliers involve linear space complexity.
Disadvantages:
- High area coverage
- Time complexity
Proposed System:
Construction oftoeplitzblocktoeplitzmatrix-vectorproduct:
we present a permutation matrix approach toconvert a Toeplitz matrix into a Toeplitz block Toeplitz matrix.Ann×nToeplitz matrix is a matrix T=[t i,j]0≤i,j≤n−1,whereti,j =ti−j for 1≤i, j ≤n−1, satisfies the followingproperty.Proposition 1:Ann×nToeplitz matrixTis determined bythe 2n−1 entries in the first row and the first column, wherenis any power-of-2 positive integer. We can use the vector(t0,t1,…,t2n−2) to define a Toeplitz matrix T. Using suchvector representation, the addition T1+T2 can be realizedby 2n−1XORgates ifT1 and T2 are two n×nToeplitzmatrices.
Proposed TBTMVP Block Recombination:
Based on two parallel TBTMVPs-add structure, we derive(4, 2)-way TBTMVPBR scheme, and then extend that to(a,b)-way TBTMVPBR decomposition. In the following,we use one-iterative andk-iterative block recombinationsto analyze the complexity of the (a,b)-way TBTMVPBRdecomposition.
1) One-Iterative Block Recombination: LetT beai ×biToeplitz block Toeplitz matrix, andVbebi×1 column vector.The productC=TVrequiresi iterative operations to performmultiplication based on(a,b)-way TBTMVP decompositionin Section III. Assume that, to compute the product C,the first iterative operation is performed by traditional multiplication and other iterative operations use the proposed(a,b)-way TBTMVP decomposition.
Fig. 1 shows the proposed structure basedon one-iterative (4, 2)-way TBTMVPBR As shown in Fig. 1, we can find that the proposed (4, 2)-wayTBTMVPBR structure involves five EMP components,four EVP components, four CA components, and fourRcomponents.
Figure 1: Proposed one-iterative (4, 2)-way TBTMVPBR structure.
2) k-Iterative Block Recombination:Based on one-iterativeblock recombination approach, the productC=TVcan bereexpressed as
Advantages:
- Low area coverage
Software implementation:
- Modelsim
- Xilinx ISE