Steps Reduction_of_summands

1 steps

1.1 production of summands
1.2 reduction of summands
1.3 summation

steps
production of summands

in binary multiplication, each row of summands either 0 or 1 of numbers multiplied. consider following:

1001
x1010
-----
0000
1001
0000
1001

the second , fourth row of summands equivalent first term. production of summands requires simple , gate each summand. given enough , gates, time produce summands 1 cycle of arithmetic logic unit.

reduction of summands

the summands reduced using common 1-bit full adder accepts 2 1-bit terms , carry-in bit. produces sum , carry-out. full adders arranged such sum remains in same column of summands, carry-out shifted left. in each round of reduction, 3 bits in single column used 2 terms , carry-in full adder, producing single sum bit column. reduces bits in column factor of 3. however, column right shift on carry-out bits, increasing bits in column third of number of rows of summands. @ worst, reduction 2/3 number of rows per round of reduction.

the following shows how first round of reduction performed. note empty positions of summands considered 0 (a . used here indicator of assumed 0 values ). in each row, top 3 bits 3 inputs full adder (two terms , carry-in). sum placed in top bit of column. carry-out placed in second row of column left. bottom bit single feed adder. sum of adder placed in third row of column. carry-out ignored zero, design placed in fourth row of column left. design, important note rows 1, 3, 5, ... (counting top) filled sums column itself. rows 2, 4, 6, ... filled carry-out values column right.

1011
x0110
-----
...0000
..1011.
.1011..
0000...
-------
0111010
000100.
00000..

reduction performed again in same way. time, top 3 rows of summands of interest because other summands must zero.

0111010
000100.
00000..
-------
0110010
001000.

when there 2 significant rows of summands, reduction cycles end. basic full adder requires 3 cycles of arithmetic logic unit. therefore, each cycle of reduction commonly 3 cycles long.

summation

when there 2 rows of summands remaining, added using fast adder. there many designs of fast adders, of may used complete algorithm.