How To Multiply Two Binary Numbers Fixed Point

Multiplication and Division are ii other arithmetic operations frequently required fifty-fifty in simple mathematics. CPUs accept fix of instructions for integer MULTIPLY and Carve up operations. Internally these instructions are implemented equally suitable algorithms in hardware. Not only integer arithmetics but also Floating-Point and Decimal pedagogy sets are besides likely to have these MULTIPLY and Split sets of instructions in sophisticated CPUs. Hardware implementation increases the efficiency of CPU.

This chapter is important for those who want to understand the hardware implementation of Multiplication and Division.

Multiplication

Simply recall with micro details as to how do we do multiplication using pen and paper. And then it is easier to visualize that information technology is possible to implement a hardware algorithm.

              Multiplicand Chiliad	= 12	   1100 			Multiplier Q	= xi	  x1011 						-------- 						   1100 						  1100 						 0000 						1100 						-------- 			Product P	= 132	10000100

As you see, nosotros start with LSB of the Multiplier Q, multiply the Multiplicand, the partial product is jotted down. And then we used the side by side college digit of Q to multiply the multiplicand. This time while jotting the fractional product, we shift the jotting to the left corresponding to the Q–digit position. This is repeated until all the digits of Q are used up and then we sum the fractional products. By multiplying 12x11, we got 132. You may realize that we used binary values and the product besides in binary. Binary multiplication was much simpler than decimal multiplication. Essentially this is washed by a sequence of shifting and addition of multiplicand when the multiplier consists merely of 1'due south and 0's. This is truthful and the aforementioned, in the case of Binary multiplication. Binary multiplication is simple because the multiplier would be either a 0 or i and hence the step would exist equivalent to adding the multiplicand in proper shifted position or adding 0's.

It is to be observed that when nosotros multiplied two 4-flake binary numbers, the product obtained is 8-$.25. Hence the product register (P) is double the size of the Chiliad and Q register. The sign of the production is determined from the signs of multiplicand and multiplier. If they are alike, the sign of the product is positive. If they are unlike, the sign of the product is negative.

Unsigned Multiplication

When multiplication is implemented in a digital figurer, information technology is user-friendly to change the procedure slightly. It is required to provide an adder for the summation of only two binary numbers and successively accumulate the partial products in a annals. The registers, Shift Counter and the ALU width is decided by the give-and-take size of the CPU. For simplicity of understanding, we volition take iv-bit word length i.east the Multiplier (Q) and Multiplicand (M) are both 4-bits sized. The logic is extrapolated to the word size requirement.

We need registers to store the Multiplicand (One thousand) and Multiplier (Q) and each 4-bits. All the same, nosotros employ 8-chip register which is standard and minimum and hence the annals to collect Production (P) is 16-bits. Refer to figure 9.1. The Shift counter keeps rail of the number of times the addition is to be done, which is equal to the number of bits in Q. The shifting of the contents of the registers is taken intendance of by shift register logic. The ALU takes care of add-on and hence partial product and product are obtained here and stored in P register. The control unit controls the cycles for micro-steps. The product register holds the partial results. The final effect is also bachelor in P when the shift counter reaches the threshold value.

Figure 9.1 Data path for typical Multiplication

The flowchart for the unsigned multiplication is shown in figure 9.2 and table 9.1 explains the piece of work out with an case of 12 x xi values. The flowchart is self-explanatory of the unsigned multiplication algorithm. In an unsigned multiplication, the carry bit is used equally an extension of the P register. Since the Q value is a 4-bit number, the algorithm stops when the shift counter reaches the value of 4. At this point, P holds the result of the multiplication.

Table 9.ane Workout for unsigned multiplication (12 ten eleven = 132)
Operation Step	Shift Counter Value	Multiplicand Chiliad	Multiplier Q	Product P
Initial Values for multiplication of 12x11	0	1100	1011	0000 0000
Q₀ = 1, So, Left one-half of P <- Left half of P + M	0	1100	1011	1100 0000
Shift Right P, Shift Correct Q	0	1100	0101	0110 0000
SC <- SC + ane	1	1100	0101	0110 0000
Q₀ = 1, So, Left half of P <- Left half of P + M	one	1100	0101	10010 0000
Shift Right P, Shift Right Q	1	1100	0010	1001 0000
SC <- SC + 1	2	1100	0010	1001 0000
Q₀ = 0, practice nothing	two	1100	0010	1001 0000
Shift Right P, Shift Right Q	2	1100	0001	0100 1000
SC <- SC + 1	3	1100	0001	0100 1000
Q₀ = 1, So, Left half of P <- Left half of P + Yard	3	1100	0001	10000 k
Shift Right P, Shift Correct Q	three	1100	0000	yard 0100
SC <- SC + 1	4	1100	0000	m 0100

Signed Multiplication

Signed numbers are always better handled in 2's complement format. Further, the before signed algorithm takes n steps for n digit number. The multiplication process although implemented in hardware 1-step per digit is plush in terms of execution fourth dimension. Booths algorithm addresses both signed multiplication and efficiency of operation.

Berth's Algorithm

Berth observed that multiplication can also be done with mixed additions and subtractions, instead of only additions. And it deals with signed multiplication as well.

The motivation for Booth'southward Algorithm is that ALU with add or subtract can get the same result in more than than one way .i.e. the multiplier 6 can exist dealt as:

6 = – 2 + eight

Booth'southward Algorithm categorises the multiplier as the run of 1's and further every bit begin, eye and end of runs. The run is identified as below for a number 01110.

Based on the run status, the operation to exist performed in the multiplication process is defined every bit in table ix.2. The values of the current chip (Q0) and the outgoing bit (Qe) of the multiplier decide the functioning to be performed. By this, the multiplication is achieved in less number of cycles based on the multiplier. A multiplier may have many combinations of runs based on its value. This algorithm is sensitive to bit patterns of Multiplier. A pattern like 01010101 may be the worse every bit it has many begin and end runs necessitating as many additions and subtractions and may not relieve wheel time. But by and large Booth's algorithm saves cycles.

Table nine.two Berth Encoding for Multiplication – Operation regarding the run
Electric current Bit (Q₀)	Bit to the right (Q_east)	Explaination	Case	Functioning
one	0	Begins run of 1s	00011110 00	Subtract multiplicand from fractional product
ane	one	Heart of run of 1s	0001111000	No arithmetic operation
0	1	End of run of 1s	0001 111000	Add multiplicand to partial production
0	0	Middle of run of 0s	0001111000	No arithmetic operation

Berth's algorithm uses Arithmetic Shift Right for collecting partial product. Arithmetic Shift right is a sign-extended shift; i.east if the sign bit is 0, then 0 is extended while shifting; if the sign scrap is 1, so ane is extended while shifting. For this reason, n+one is the register size. Yous may observe this in our work out in table 9.3. The work out is for (-12x -11). This instance is taken to demonstrate the effect of signed multiplication with Booth's algorithm. Both multiplicand (Thou) and Multiplier (Q) use 5-$.25 as confronting iv-digit binary number.

The fractional product and Product is collected in P and Q register. The Q register initially holds the Multiplier; equally it gets shifted out with every digit multiplication, the space in Q register is occupied past partial product. Qe is a one-fleck register holding the outgoing bit. Together PQQe is treated as one entity during the arithmetics shift, whereas only P is considered for addition or subtraction of multiplicand. The multiplicand is loaded in Thousand. Both Multiplicand and Multiplier are loaded in the simple binary class if these are positive numbers and in ii's complement form if these are negative numbers. The shift counter stops the operation once it reaches the digit count of Q, in this example, 4. Q0Qe are evaluated at every stride to decide the operation to exist carried out on Thousand and P.

Booth's Signed Multiplication — Table 9.three Berth's Signed Multiplication

It is seen that the resulting Product of multiplying two negative numbers is a positive number which is correct. One need not handle the signs separately. It is handled every bit part of the algorithm. The flow chart and the datapath may be drawn by an interested reader as an exercise or the reader may contact the author.

There is a category of Multipliers called Array multiplier which avoids this sequential operation and produces the event at once. These require a big number of gates for implementation. Even so, with the advancement in VLSI, it is a reality. Dissimilar CPUs have different implementations.