 Open Access
 Total Downloads : 1093
 Authors : Divya Madhuri, Kedhareswarao, Madhavi Latha, Bolla Prasad
 Paper ID : IJERTV1IS7437
 Volume & Issue : Volume 01, Issue 07 (September 2012)
 Published (First Online): 29092012
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
Design of Reconfigurable Multipliers Based on High Speed Shannon Adders
Divya Madhuri, Kedhareswarao Dept. of ECE, Avanthi Institute of Engineering and Technology, Visakhapatnam.
Madhavi Latha
Asst. Prof., Dept. of ECE, GITAM University, Hyderabad.
Bolla Prasad
Asst. Prof., Dept. of EIE, GITAM University, Hyderabad.
Abstract
Multiplication is indeed the most crucial operation in digital signal processing (DSP). Its implementation requires large hardware resources and signicantly affects the size, performance, and power consumption of a DSP system. Several DSP algorithms require different types of multiplications, specically integer or Galois field (GF) multiplication. Since both functions share similarities in their structures, it is better to combine both circuits in a single circuit. In this paper, various types of multipliers for integer and Galois field multiplication will be analyzed and discussed in detail. A comparative study of reference, reconfigurable and proposed high speed Shannon adder based reconfigurable structures is made. Such study shows proposed structures have area savings of up to 1114% at a marginal reduction in delay and power around 23% compare to the conventional adder based reference and reconfigurable structures. From this perspective, functionspecic recongurable circuits based on high speed Shannon adder can be considered feasible alternatives to standard ASIC solutions.
Keywords: Integer field; Galois field; Reconfigurable multipliers; Shannon adder;

Introduction
Extensive digital signal processing (DSP) capabilities are a major characteristic of a large number of SystemonChip (SoC) designs mainly deployed in embedded systems. DSP applications in SoCs range from audio or video processing to wireless communication. Consequently, various different architecture concepts for their implementation exist ranging from application specic components to embedded recongurable
[1] hardware or digital signal processors. Each solution represents a specic tradeoff between chip area, power consumption, performance, and design effort, currently the most importantparameters in SoC design. The focus is on the analysis of multiplier circuits for integer and Galois field arithmetic [2].
Reconfigurability refers to system incorporating some form of hardware programmability that customizes how the hardware is using a number of physical control points. These control points can be changed periodically in order to execute different applications using the same hardware. The technology offers real hardware and software co design, fast functionality, flexible hardware and high performance.
Integer arithmetic may be essential for instance in ltering algorithms or Fourier transforms, while many algorithms from the communication domain like error correction codes or the widely used Advanced Encryption Standard (AES) [3], Data Encryption Standard (DES) are based on GF arithmetic. Since integer and GF multipliers [4] share numerous similarities in their structures, the potential of efficient methods for integration of both operations in one circuit is provided.
The main involvement of this work is the broad evaluation of design alternatives of parallel integer and GF multipliers, mostly including their combined reference and recongurable implementation based on conventional adder and Shannon adder [5], and the complete analysis of their area, delay and power results. The results allow to develop guidelines for designers facing the implementation of high speed circuits for integer and GF multiplication.
The rest of the paper is organized as follows. Section 2 introduces the integer and Galois field multipliers Section 3 specify the combination integer and Galois field multiplies including our proposed model based on high speed Shannon adder. The results from the proposed method and the comparison with the previous versions are given in Section 4. Finally our conclusion is made in Section 5.

Integer and Galois field multipliers

Integer field multipliers
The multiplication of two nbit numbers will deliver a result of size 2n. An unsigned integer number representation will be used for all integer operations in our operations. They are various types of integer field multipliers are proposed for high speed operations we are considering these three architectures Carry save array (CSA), Braun array (BA) and Wallace tree (WT).
1 = 0, 1 = 1. Hence, in binary arithmetic, subtraction is the same as addition [6].

Polynomials over finite fields
A primitive polynomial g(x) is used to generate the elements of GF(2m).
where gi, 0 i m, are the elements of GF(2m). Addition and multiplication of polynomials follow
si a b
a3 a2
0 0 0
a1 a0
0
b0
g x g0 g1x g2x2
. . . . . . . .
gmxm
&
adder
co ci
so
0 0 0 0 0
b1
0
b2
0
standard addition and multiplication rules of ordinary polynomials except that addition and multiplication of the coefficients are done modulo
b3
a
m
si 2. If g
=1, the polynomial is called monic. If the
m
b b 0
ad
ad
add add
add
add
add 0
polynomial of degree m over GF(2 ) cannot be
written as the product of two polynomials of lower
co
a
so
(a)
ci Ripple Carry Adder
c7 s7 s6 s5 s4 s3 s2 s1 s0
(b)
M7 M6 M5 M4 M3 M2 M1 M0
degrees over the same Galois field, then the polynomial is called irreducible polynomial. For instance, x2 +x +1 is a irreducible polynomial over GF(22) where as x2+1 is not a irreducible polynomial over GF(22) because x2 + 1 = (x + 1)2. In our analysis a 8bit Galois field multiplier with irreducible polynomial x8 + x4+x3+x2+1=0 is used.
a3 b3
add
ad
add
a3 b2
add
10bit CSA
a3 b0 a2 b0 a1 b0 a0 b0
a3 b1
b1
b2
b3
add
add 0
13bit CSA
11bit CSA
15bit CSA
16bit CSA
17bit RCA
10bit CSA

Galois field multiplier
Modular Galois field multiplier (MGF) is used in this work. The subsequent GF multipliers are generic in the sense that the generator polynomial p is an extra input, so that the multipliers can be used for any eld of the kind GF(28). This characteristic is important, since not all DSP algorithms are based
s7 s6 s5 s4 s3 s2 s1 s0
Output
on the same Galois fields.
(c) (d)
Figure 1. (a) Basic cell for integer field multipliers (b) CSA (c) BA (d) WT
The BA architecture is somewhat more optimized modification of the CSA structure. The Wallace tree [8, 9] has a similar structure, but instead of adding the partial products row by row it uses a balanced tree structure to obtain some parallelism and reduce the critical path length. [7]. These structural differences will be important for the later transformation into reconfigurable multi pliers.
2.2. Galois binary field (2m)
As In general, the code with symbols from any Galois field GF(q), where q is prime can be constructed. However, codes with symbols from the binary field GF(2) or its extension GF(2m) [6] are most widely used in digital data transmission and storage systems because information in these systems is universally coded in binary fom for practical reasons. In binary arithmetic, modulo2 addition and multiplication is used. This arithmetic is actually equivalent to ordinary arithmetic, except that it is considered that 2 to be equal to 0 (i.e., 1 + 1 = 2 = 0). Note that since 1 +
MGF is base on a very natural approach for standard basis multiplication in GF(2m) is to multiply two elements in the field as polynomial multiplication and modulo reduction with irreducible polynomial as shown in Figure 2.
Let a(x), b(x), c(x) elements in GF(2m) and g(x) the irreducible polynomial generating GF(2m). Then the finite field multiplication of a(x) Ã— b(x) is accomplished by calculating
c x a x b x mod g x
where Ã— denotes polynomial multiplication. In a first stage the product a(x) Ã— b(x) is calculated, resulting in a polynomial q(x) of degree at most 2m 2. In a second stage the modular reduction is performed on q(x), that is c(x) = q(x) mod g(x), resulting in the polynomial c(x) of degree at most m 1.
XOR operation. This is exploited to form a recongurable cell usable for both operations, which is depicted in Figure 4. (a) Compared to the original array cell in Figure 1. (a) only one extra gate is necessary. Carry propagation can be disabled for GF multiplication (conf = 0) and enabled for integer multiplication (conf = 1) by configuring the signal conf. The reconfigurable structures are shown in Figure 4.
Figure 2. MGF multiplier of 4 Ã— 4 bit



Combination of integer and Galois field multipliers
conf si
a
b
&
In this paper we are presented three types of design combinations for integer and Galois field (MGF) multipliers including our proposed model. The three different models are described below.
co +
& ci
so
(a)
(b)
Partial Product Summation

Reference multipliers
Reference architectures have been constructed as illustrated in Figure 3 by placing a fixed instance
of integer and GF multipliers in parallel and
demux
selecting the result through a multiplexer. Implementing both multiplication types always introduces a penalty in area, performance and power consumption compared to reference architecture which is a single architecture. Which of these alternatives provides the best efficiency is evaluated in the following Section 4.
Figure 3. Reference structure

Reconfigurable multipliers
The design and analysis of three special recongurable multiplier architectures that have been constructed based on the integration of MGF multiplier architecture with each of the three integer multiplier architectures. Due to the individual structures of the multipliers, special methods for the combination have been applied, which will be explained in the following.
The technique merges an array structure (CSA and BA) with the MGF architecture. It can be observed that the cells of both the integer and the MGF multipliers share a similar functionality and both contain an AND operation followed by an
Conf
Adder
Modulo
mux
Conf
Output [7:0]
(c) (d)
Figure 4. (a) Basic cell (b) Partial product summation (c) CSA&MGF (d) WT&MGF reconfigurable multipliers

Proposed reconfigurable multipliers based on high speed adders
Reference Multiplication dominates the execution time of most digital signal processing algorithms; therefore, highspeed multiplier is much desired. Adders are the building blocks of the integer multiplication. To reduce the critical path delay in multipliers, it is needed to use high performance adders as building blocks to design reconfigurable multipliers.
Proposed reconfigurable multipliers are designed by high speed Shannon adder and the comparison results with the conventional adder based reconfigurable multipliers will be discussed in Section 4.

Conventional adder
Conventional adder can be implemented by using two half adders and one logic OR gate as shown in the Figure 5 where the sum and carry outputs are generated by
Sum A B Cin
Cout
( A B)
Cin
( A B)
A
B
Cin
Sum
Cout
Figure 5. Implementation of full adder using two half adders and one OR gate

High speed Shannon adder

The Shannon theorem states that any logic expression can be expanded into two terms, the first with a particular variable setting a variable to 1, then multiplying it by the variable and then setting the variable to 0 and multiplying by the inverse. By repeating Shannon theorem for each variable in the expression, the fullest reduction in critical path can be achieved. Shannon theorem, stated in a generalized form, is as follows a function of many variables can be written as the sum of two terms, one with a particular variable (say ai) set to 0, and one with it set to 1.
f a0 , a1, a2 , , ai , , an
Figure 7. Synthesis and simulation results of WT&MGF reconfigurable multipliers based on Shannon adder
Table 1. Comparison of conventional adder and high speed adder based reconfigurable multipliers
Structure type
Design model
Area (Âµm2)
Total
power (ÂµW)
Delay (ns)
CSA
& MGF
Reference
6559.05
950.7
11.47
Reconfigurable
6333.13
761.27
10.74
Proposed
5603.11
731.76
10.3
BA
& MGF
Reference
5768.96
919.25
10.26
Reconfigurable
5480.1
724.29
9.98
Proposed
4905.14
699.22
9.5
WT
& MGF
Reference
5667.41
913.57
8.69
Reconfigurable
6282.0
757.18
9.35
Proposed
5819.34
749.31
8.82
i f a0 , a1, a2 , ,0, , an ai f a0 , a1, a2 , ,1, , an
A B A B
A B B Cin
A Cin
Cin Cin
Sum Cout
Figure 6. Implementation of full adder using Shannon theorem


Results and comparison
Starting with a Verilog HDL circuit description synthesis results are taken from the Xilinx ISE 9.2i and the Simulation results are taken from the Mentor Graphics Model sim 6.5d and the gate level synthesis results were taken from Synopsys Design Compiler C2009.06SP4 using SAED 90nm technology library. No handoptimization has been involved. Thus, it is wanted to ensure that the results can be reproduced easily and that the circuits can be integrated in any system without additional effort for changing an existing design flow.
(a)
(b)
Figure 8. (a) Area and Total power dissipation
(b) Area and Delay comparison graphs for combination of different integer field
multipliers with MGF
Reconfigurable architectures turn out to be most recommendable compare to the reference architectures. The BA&MGF architectures require less area around 5480.93m2 and less power consumption around 724.29W than the other reconfigurable structures and the WT&MGF is the most favorable solutions when timing and power constraints are much more important than area constraint and also found that reconfigurable structures using high speed Shannon adder based structures have 10% reduction in area 34% less in delay and power values compare to conventional adder based reconfigurable structures.

Conclusion
In this pper, performance results for three reference and reconfigurable unsigned integer and GF multipliers are presented. The reconfigurable circuits were constructed based on both high speed Shannon adder and conventional adder in a straightforward way. The effects of special structural particularities of the individual multiplier models on the resulting circuits are analyzed and discussed. An important contribution of this work is the evidence, that functionspecific reconfigurable circuits can be constructed which improve three design objectives. This places some of the resulting designs very close to standard ASIC solutions. Precisely, we found that reconfigurable multiplier of BA&MGF achieves small area as well as high speed and low power dissipation.
The study confirms that the design for reconfigurable structures based on high speed adders leads to results improving the design objectives considerably than the conventional adder based structures. In addition, the results highly depend on the quality of the input circuits and on the way they are combined.
References

H. Hinkelmann, Peter Zipf, Jia Li, Guifang Liu, Manfred Glesner, On the design of reconfigurable multipliers for integer and Galois field multiplication, Microprocessors and Microsystems, Feb 2009, Vol. 33, pp. 212.

P. Kitsos, G. Theodoridis, O. Koufopavlou, An efficient reconfigurable multiplier Architecture for Galois field GF (2m), Microelectronics Journal, Oct 2003, Vol. 34, pp. 975980.

C. Senthilpari, A. K. Singh, K. Diwakar, Design of a low power, high Performance, 8 Ã— 8 bit multiplier using a Shannonbased adder cell, Microelectronics Journal, May 2008, Vol. 39, pp.812821.

William Stallings,Cryptography and Network Security Principles and Practices, Fourth Edition, Prentice Hall, 2005.

Shu Lin, Daniel J. Costello, Error Control Coding: Fundamentals and Applications, Prentice Hall, 1983.

W. Drescher, G. Fettweis, VLSI architectures for multiplication in GF(2m) for Application tailored digital signal processors, IEEE Workshop on VLSI Signal Processing, Nov 1996, pp. 5564.

Raminder Preet Pal Singh, Parveen Kumar, Balwinder Singh, Performance Analysis of 32Bit Array Multiplier with a Carry Save Adder and with a CarryLookAhead Adder, IEEE International Journal of Recent Trends in Engineering, Nov 2009, Vol. 2, No. 6.

C.S. Wallace, A suggestion for a fast multiplier, IEEE Transactions on Electronic Computers, Dec 1964, Vol. EC13, pp. 1417.