Sign-Magnitude Encoding for Efficient VLSIRealization of Decimal Multiplication
Abstract:
Decimal X×Y multiplication is a complex operation, where intermediate partial products (IPPs) are commonly selected from a set of precomputed radix-10Xmultiples. Some works require only[0,5]×X via recoding digits of Y to one-hot representation of signed digits in[−5,5]. This reduces the selection logic at the cost of one extra IPP. Two’s complement signed-digit (TCSD) encoding is often used to represent IPPs, where dynamic negation (via one xor per bit of X multiples) is required for the recoded digits of Y in [−5,−1].In this paper, despite generation of 17 IPPs, for 16-digit operands, we manage to start the partial product reduction (PPR) with 16 IPPs that enhance the VLSI regularity. Moreover, we save 75% of negating xors via representing precomputed multiples by sign-magnitude signed-digit (SMSD) encoding. For the first-level PPR, we devise an efficient adder, with two SMSD input numbers, whose sum is represented with TCSD encoding. Thereafter, multilevel TCSD 2:1 reduction leads to two TCSD accumulated partial products, which collectively undergo a special early initiated conversion scheme to get at the final binary-coded decimal product. As such, a VLSI implementation of 16×16-digit parallel decimal multiplier is synthesized, where evaluations show some performance improvement over previous relevant designs.The proposed architecture of this paper analysis the logic size, area and power consumption using Xilinx 14.2.
Existing System:
we briefly study several previousrelevant works by compiling their PPG and PPR characteristics in Table I. The column acronyms MR, ME, DN,#OP, PPDS, and PPDE stand for multiplier recoding, multipleencoding, dynamic negation of IPPs, number of operands tobe added (i.e., number of originally generated nonredundantdecimal numbers, or SD partial products), partial productdigit set, and partial product digit encoding, respectively.In Table I, Svoboda refers to the encoding of a digitd∈[0,6]([−6,−0])by a 5-bit binary number 3d(31−3d).Some other works on decimal multiplication with floatingpoint operands, specific designs for Field Programmable Gate Array (FPGA), or digit-by-digititerative approach are not listed in Table I, since theyare based on one of the tabulated works, or use embeddedFPGA components, which are out of the scope of this paper.
Dynamic negation of precomputed Xmultiples reduces their selection cost at the penalty of oneXORgate per each bit of the selected positive multiple. This negation cost is replicatedntimes for paralleln×nmultiplication.Moreover, theninserted 1s for 10’s complementationandn×(n+1)1s for digitwise two’s complementationhave a negative impact on area and power saving. The same istrue for the correction constant, and more complex recodingdue to zero handling, for [0,15] partial products.One way to save these costs, is togenerate the SD precomputedXmultiples with sign magnitudeformat, so as to reduce theXORgates to one per digit (roughly75% savings in the number of negatingXORgates) and removethe aforementioned negative impacts. However, besides slowing down the PPG to some extent (e.g., in comparison withradix-5 implementation), new problems are introducedin PPR, which are explained and solved in the next section,where we also reduce the depth of IPP matrix ton =16,effectively prior to termination of PPG.
Disadvantages:
- High power consumption
Proposed System:
DecimalIPPswithsign-magnituderepresentation ofsigneddigits:
Decimal SDs in[−α, α] (α≤7)are usually encoded withminimal 4-b signed numbers. For example, considerα=5in and α=7 with sign magnitude and two’scomplement representations, respectively. The latter is suitablefor basic arithmetic operations, except for negation, which isbest performed on sign magnitude format.
Fig. 1 depicts the general architecture of the proposed16×16 multiplicationP=X×Y; the details of each buildingblock will be explained later. In particular, in the top threeblocks, the multiplier’s digits are recoded tonone-hot[−5,5]SMSDs (i.e., one sign and five magnitude bits), augmentedwith a 10n-weighted carry bit. The multiples [0,5]×Xareprecomputed asn[−6,6]SMSDs and a 10n-weighted[−5,4]SMSD. Each SMSD contains a sign bits and 3-b magnitude.The negative multiples[1,5]×(−X)are achieved via dynamicsign inversion of multiples[1,5]×X at the cost of onlyoneXORgate per digit.
Figure 1: Block diagram of the proposed multiplier
Recoding of Multiplier’s Digits:
Original BCD digits of multiplier require[0,9]×Xprecomputed multiples, which include hard multiples{3,6,7,9}×Xthat unlike {2,4,5,8}×Xare not derivable without carrypropagation. On the other hand, BCD-to-redundant[−5,5]SMSD recoding of multiplier’s digits with dynamic negationof IPPs reduces the requiredXmultiples to[0,5]×Xthatinclude only one hard multiple (i.e., 3X).
Precomputed Multiples:
We need to generate 0,1,2,3,4,5}×X,whereXis a BCDmultiplicand. The only hard multiple 3Xcan be generated incarry-free manner, if it is represented via a redundant digitset. Therefore, for uniformity sake in PPR, we generate all the required multiples in the same SD numbersystem.
Partial Product Reduction:
The overall PPR forn =16 is illustrated by Fig. 2,where a bar, triangle, square, and diamond represent a BCD,[−6,6]SMSD,[−7,7]TCSD, and binary signed digit (BSD),respectively. The choice of SMSD representation for the firstlevel IPPs, while facilitating the PPG, bears no extra complexity for PPR, since all reduction levels use TCSD adders, exceptfor the first one that requires a special SMSD+SMSD-to-TCSDadder. However, as will be shown at the end of Section III-D1,this adder is not more complex than a simple TCSD adder.The red-shaded SMSD in level II of Fig. 5 is directlyconverted to BCD. Similar direct conversions are in orderfor the red-shaded digits (TCSDs, however) in the subsequentlevels III and IV.
Figure 2: Overall view of 16×16 digit multiplier.
Advantages:
- Low power consumption
Software implementation:
- Modelsim
- Xilinx ISE