Radix-8 Design Alternatives of Fast Two Operands Interleaved Multiplication with Enhanced Architecture

CSA [4] is a fast-redundant adder with constant carry path delay regardless of the number of operands’ bits. It produces the result as two-dimensional vectors: sum vector (or the partial sum) and carry vector (or partial carry). The advantage of CSA is that the speed is constant regardless the number of bits. However, its area increases linearly with the number of bits. The top view of the CSA unit along with its internal logic design architecture are provided in Fig. 1 below.

Figure 1.

In this work, we have implemented the CSA adder using VHDL code for different bit sizes ranges from 8-bits through 64-bits [8]. The synthesize results of total delay in (ns) and area in Logic Elements (LEs) were analyzed and reported in [8] and they are illustrated in Fig. 2. These results were generated using Quartus II 14.1 software [9], simulated for Altera Cyclone IV DE2–115 model [10] and they highly conform theoretical evaluation of CSA operation since the delay time is almost equal for all bits. However, the area is almost double for each number of bits. Also, the timing estimation of 64– bits CSA was generated via TimeQuest Time Analyzer tool provided in the Quartus II CAD package. Accordingly, the critical path delay is 3.529 ns which is data arrival time while the data delay is only 2.866 ns which provide a frequency of 349 Mhz. Finally, to verify the performance of CSA, we have compared it with the well-known Carry LockAhead Adder (CLA) in terms of area and delay. CLA is a carry propagation adder (CPA) with logarithmic relation between the carry propagation delay and the number of bits in operands.

Figure 2.

The simulation results of both CSA and CLA is provided in Fig. 2 shows that CSA is superior in both Area and speed. It has almost a constant time delay and relatively less area than CLA. Whereas CLA time delay increases as the number of bit increases but not much as the area size.

KSA is a fast two operands parallel prefix adder (PPAs) [11] that executes addition on parallelized manner. PPAs are just like CLA but with an enhancement in the carry propagation stage (called the middle stage). There are five different variations of PPAs namely: Ladner-Fischer Adder (LFA), Brent-Kung Adder (BKA), Kogge-Stone Adder (KSA), Hans-Carlson Adder (HCA), and Sklansky Adder (SkA). These adders differ by the tree structure design to optimize certain aspects such as, performance, power, area size, and fan in/out.

To verify the performance of all PPAs, we have implemented them on FPGA and the experimental results [6] showed that KSA utilizes larger area size to achieve higher performance comparing among all other five PPAs. Thus, we decided to consider KSA as our basic carry propagation adder (CPA) to finalize the redundant results and to build up many other units that are in-need for conventional adder. In short, the simulation results of [6] showed that KSA leading the other adders as it has the smallest time delay with only 4.504. This result is very useful and conforms the theatrical modeling of KSA which has the least number of logic levels. Like all PPAs, KSA functionality consists of three computational stages as illustrated in Fig. 3, as follows:

Figure 3.

Addition operation is not commonly used to add two operands only, instead, it is more involved with multiplication and inner product computations [12]. The use of regular two operands adders leads to intermediate results before getting the last answer which affect the performance or the time delay of a system. Therefore, Multi-operand adders are manly studied to reduce this problem. Wallace and Dadda trees [13] are considered as two variations of high-performance multi-operands addition. Fig. 4. shows the dot notation to represent the digit positions or alignments (instead of using the value which is quite useful) for the use of Multi-operand addition in multiplication and inner-product computation.

Figure 4.

In this work, we have adopted a CSA based Wallace tree since it confirmed better operands organization to improve the total addition delay [8]. We have implemented two CSA Wallace Trees: 10-operands addition and 22-operands addition. The structure logic diagram of 10 operands is given in Fig. 5. It’s clearly seen that the Wallace tree unit is designed behaviorally (FSM is generated).

Figure 5.

To enhance the performance of multiplication for large operands (i.e. 1024-bit size), a re-organization process can be adopted for the multiplication operands to utilize the maximum possible parallelism to enhance the multiplication time. Karatsuba algorithm [14] is pipelined multiplication process used mainly to construct the high precision multipliers form multiple small precision multiplier blocks by exploiting the maximum available parallelism between the multiplication blocks. The basic idea of Karatsuba algorithm is illustrated in fig. 6 and Karatsuba algorithm can be defined as follows:

Figure 6.

Let x,y be integers and B is the base (Radix_2) and m < n where n: the number of digits, then:

A more efficient implementation of Karatsuba multiplication can be accomplished as: x y = ( b 2 + b ) z 2 − b ( x 1 − x 0 ) ( y 1 − y 0 ) + ( b + 1 ) z 0

The magnitude (or digital) comparator is a hardware electronic device that takes two numbers as input in binary form and determines whether one number is greater than, less than or equal to the other number. Like that in binary addition, the efficient comparator can be implemented using G (generate) and P (propagate) signal for comparison. Basically, the comparator involves two 2-bits: A₁A₀& B₁B₀ can be realized by: (1) B B i g = A 1 ¯ B 1 + ( A 1 ⊕ B 1 ) ¯ . ( A 0 ¯ B 0 ) (2) E Q = ( A 1 ⊕ B 1 ) ¯ . ( A 0 ⊕ B 0 ) ¯

For A<B, “BBig, EQ” is “1,0”. For A=B, “BBig, EQ” is “0,1”. Hence, for A>B, “BBig, EQ” is “0,0”. Where BBig is defined as output A less than B (A_LT_B). Comparing Eq. (1) and (2) with carry signal (3): (3) C o u t = A B + ( A ⊕ B ) . C i n = G + P . C i n

Where A & B are binary inputs Cin is carry input, Cout is carry output, and G & P are generate & propagate signals, respectively. Now, after comparing equations (1) & (3), we got: (4) G 1 = A 1 ¯ B 1 , E Q 1 = ( A 1 ⊕ B 1 ) ¯ , C i n = A 0 ¯ B 0

Cin can be considered as G0. For this, encoding equation is given as: (5) G [ i ] = A [ i ] ¯ B [ i ] (6) E Q [ i ] = ( A [ i ] ⊕ B [ i ] ) ¯

Substituting the two values from equations (5) & (6) in (1) & (2) results in: (7) B B i g [ 2 j + 1 : 2 j ] = G [ 2 j + 1 ] + E Q [ 2 j + 1 ] . G [ 2 j ] (8) E Q [ 2 j + 1 : 2 j ] = E Q [ 2 j + 1 ] . E Q [ 2 j ]

G&P signals can be further combined to form group G&P signals. For instance, for 64-bit comparator, B_Big&EQ can be computed as: (9) B B i g [ 63 : 0 ] = G 63 + Σ k = 0 62 ( G k ⋅ Π m = k + 1 63 E Q m ) (10) E Q [ 63 : 0 ] = Π m = 0 63 E Q m

Fig 7. Shows the complete design of an 8-bit comparator as an example of this techniques where: i= 0…7, j = 0…3.

Figure 7.

Unlike Binary radix booth encoder, Radix-8 booth encodes each group of three bits as shown in table 1. The encoding technique uses shift operation to produce 2A and 4A while 3A is equal to 2A+A. The logic diagram of implementing CSA based Radix-8 booth multiplier is shown in Fig. 8. The use of CSA provides very powerful performance with limited area cost. The partial products for radix-2 is n (where n is the number of operand bits). However, for radix 8 the number of partial products is only n/3.

Figure 8.

As can be seen from fig. 8, the multiplier accepts two 32-bit operands (A and X) and stores the operand (A) in a shift register to select the group bits used in encoding whereas the operand (X) processed with the booth encoder. The output of encoding stage is added via the sequential CSA adder and the result is provided in a redundant representation (vector sum and vector carry).

Also, Fig. 9 illustrates the FSM diagram of 32-bit booth multiplier. It starts with Reset_State, where all signals and variables are cleared (i.e. reset). Next state is Mul_Gen, where encoding is occurred. After that, the generated vector is added to the previous results of CSA state. Fourth, results are stored in Store_State and moves back to Mul_Gen state in loop until all the bits are selected and encoded. Finally, the output results are provided in Output state. Note that in Radix-8 encoding the number of generated partial product vectors are computed by dividing the number of bits over 3, since each three bits are selected and used for encoding.

Figure 9.

In this method, we combine the benefits of the bit reduction of radix 8 booth along with the parallelism of CSA based Wallace tree as well as the pipelining process of Karatsuba multiplication. Thus, this design achieved minimum path delay and minimized area (i.e. the best performance). However, redundancy in this design produced one critical problem regarding the middle carry at the edges of blocks that affects the results. Fig. 10 illustrates the flow diagram for this design. Here, we first designed a 64-bit Karatsuba Multiplier using a 32-bit CSA based radix-8 Booth for partial products calculation (as for our target design and since we are implementing 64-bit multiplier; m was chosen to be 32 bits (half size)). First, the entered two operands are divided into halves (x1, x2, y1, y2). Next, they are fed into the Booth multiplier to compute the partial products as given in Karatsuba formula. Since the results are redundant and we have 5 partial products according to Karatsuba: b 2 z 2 + b z 2 − b ( x 1 − x 0 ) ( y 1 − y 0 ) + b z 0 + z 0 .

Figure 10.

Thus, 10 partial products are generated. In the final stage, a CSA based Wallace tree was implemented to be used for adding the resulted partial products. Final result is represented redundantly as vector sum and vector carry. This design achieves minimum path delay with limited area.

However, redundancy in this design produces one critical problem that affects the results. As a rule-of-thumb, if we multiply two N – bit numbers (i.e. p and q), the multiplication result will be increased to 2N – bit. However, this is not the case when using redundant systems since the result is stored as two 2N – bit vectors and adding the two vectors to we tend to obtain the conventional product might result in 2N + 1 bits. This additional bit brings up a new problem in the preliminary design. Now, this problem can be solved by discarding the last carry when converting back to conventional representation. However, in Karatsuba algorithm the numbers are split into 32-bit (original size is 64). The result must be 128-bit, but in Karatsuba case will be 10 partial product vectors of 64-bit shifted in such a way that adding those vectors will result in 128-bit. Thus, discarding all the generated carry when converting back to conventional system leads to error since only the carry generated of adding the two vectors corresponding to the same variable (or the same partial product in this case) needs to be discarded. Other generated carries must be considered. Fig. 11. demonstrate this problem graphically.

Figure 11.

Eventually, the mid-carry problem was solved by either using 64-bit CSA Based Radix-8 Booth, KSA Based Karatsuba multiplier or using 64-bit CSA Based Radix-8 Booth, with comparator Karatsuba multiplier. However, both solutions have added more overhead to design cost; therefore, this solution has been excluded. Both solutions are discussed in the following subsections.

1)

CSA Based Radix-8 Booth, KSA Based Karatsuba Multiplier.

Since the carry to be eliminated is the generated one from booth multiplier, a first thought is to exchange the CSA adder with KSA adder to convert back the two vectors into one 64-bit number and discard any generated carry. All the 8 vectors are reduced into five 64-bit vectors in parallel. This stage helps to eliminate the false carry without the need to do any further examination. KSA is a fast adder, thus this design maintains its high performance utilizing more logic elements. The logic diagram of the design is shown in Fig. 12.

Figure 12.

2)

CSA Based Radix-8 Booth, With Comparator Karatsuba Multiplier.

Another noticeable design option can solve the mid-carry problem is to use a 64-bit comparator to test if the two vectors will generate a carry if yes, then do the correction step before input the 10 vectors to CSA Tree. After Booth multiplication stage, connect the vector sum and vector carry that may produce carry error to the inputs of 64-Bit comparator unit, then perform correction if needed. Finally, all vectors added using CSA tree. The complete solution is depicted in fig. 13.

Figure 13.

Note that the 64-bit comparator can be built with 8 stages in total recording a total delay of 13 level gate delay and area of 317 gates (like the design of 8-bit comparator discussed in section. 2.5). To predict whether the carry will be generated or not, then we need to generate 64-Bit G (generate) and K (kill) vectors. Thus, we have three cases which might happen as follows:

Case I: when G(i) = K(i) = 0. The carry is propagated. Here we need to define the first carry state before propagate. If the state is kill, then the vector does not need any correction. But, if the state is a generate state, then we need to subtract one from the highest bit (MSB) of any vector to prevent the carry to propagate.

Case II: when G(i) = 0 and K(i) = 1. Here we have a Kill state, so that no need to correction.

Case III: when G(i) = 1 and K(i) = 0. Here is a generate state and a correction is needed. If this happed at highest bit (MSB), then it needs to subtract 2 ones. But if it after some propagate, then this is Case I.

To define the first case, we have used a comparator to compare the two vectors G and K as the comparator results:

G > k: Generate state happened first or it is the first state after propagation

K > G: kill state happened first or it is the first state after propagation

G = K: All states are propagating states, no need for correction because we do not have input carry

This design is accomplished by expanding the 32-bit booth to 64-bit. The two modules (i.e. 64-bit and 32-bit Booth) differ only in the number of generated partial products. Since radix-8 is used, 22 partial products are generated in the new module instead of 11 while other logic components remained the same. Fig. 14 shows the logic diagram of new 64-bit implementation. This design was implemented and was simulated on Altera FPGA Kit recording a path delay of 10.701 ns for one loop and since the program runs 22 times (i.e. 22 partial products), thus the total path delay is 235.422 nS. Also, this multiplier requires 3330 logic elements (LEs).

Figure 14.