Reduction of summands
Encyclopedia
Reduction of summands is an algorithm for fast binary multiplication of non-signed binary integers. It is performed in three steps: production of summands, reduction of summands, and summation.
1001
x1010
-----
0000
1001
0000
1001
The second and fourth row of the summands are equivalent to the first term. Production of the summands requires a simple AND gate
for each summand. Given enough AND gates, the time to produce the summands will be one cycle of the arithmetic logic unit
.
that accepts two 1-bit terms and a carry-in bit. It produces a sum and a carry-out. The full adders are arranged such that the sum remains in the same column of summands, but the carry-out is shifted left. In each round of reduction, three bits in a single column are used as the two terms and carry-in for the full adder, producing a single sum bit for the column. This reduces the bits in the column by a factor of 3. However, the column to the right will shift over carry-out bits, increasing the bits in the column by a third of the number of rows of summands. At worst, the reduction will be 2/3 the number of rows per round of reduction.
The following shows how the first round of reduction is performed. Note that all "empty" positions of the summands are considered to be zero (a . is used here as indicator of the "assumed zero values"). In each row, the top three bits are the three inputs to the full adder (two terms and carry-in). The sum is placed in the top bit of the column. The carry-out is placed in the second row of the column to the left. The bottom bit is a single feed into an adder. The sum of this adder is placed in the third row of the column. Carry-out is ignored as it will always be zero, but by design it would be placed in the fourth row of the column to the left. For design, it is important to note that rows 1, 3, 5, ... (counting from the top) are filled with sums from the column itself. Rows 2, 4, 6, ... are filled with carry-out values from the column to the right.
1011
x0110
-----
...0000
..1011.
.1011..
0000...
-------
0111010
000100.
00000..
Reduction is performed again in exactly the same way. This time, only the top three rows of summands are of interest because all other summands must be zero.
0111010
000100.
00000..
-------
0110010
001000.
When there are only two significant rows of summands, the reduction cycles end. A basic full adder normally requires three cycles of the arithmetic logic unit
. Therefore, each cycle of reduction is commonly 3 cycles long.
Production of summands
In binary multiplication, each row of the summands will be either zero or one of the numbers to be multiplied. Consider the following:1001
x1010
-----
0000
1001
0000
1001
The second and fourth row of the summands are equivalent to the first term. Production of the summands requires a simple AND gate
AND gate
The AND gate is a basic digital logic gate that implements logical conjunction - it behaves according to the truth table to the right. A HIGH output results only if both the inputs to the AND gate are HIGH . If neither or only one input to the AND gate is HIGH, a LOW output results...
for each summand. Given enough AND gates, the time to produce the summands will be one cycle of the arithmetic logic unit
Arithmetic logic unit
In computing, an arithmetic logic unit is a digital circuit that performs arithmetic and logical operations.The ALU is a fundamental building block of the central processing unit of a computer, and even the simplest microprocessors contain one for purposes such as maintaining timers...
.
Reduction of summands
The summands are reduced using a common 1-bit full adderAdder (electronics)
In electronics, an adder or summer is a digital circuit that performs addition of numbers.In many computers and other kinds of processors, adders are used not only in the arithmetic logic unit, but also in other parts of the processor, where they are used to calculate addresses, table indices, and...
that accepts two 1-bit terms and a carry-in bit. It produces a sum and a carry-out. The full adders are arranged such that the sum remains in the same column of summands, but the carry-out is shifted left. In each round of reduction, three bits in a single column are used as the two terms and carry-in for the full adder, producing a single sum bit for the column. This reduces the bits in the column by a factor of 3. However, the column to the right will shift over carry-out bits, increasing the bits in the column by a third of the number of rows of summands. At worst, the reduction will be 2/3 the number of rows per round of reduction.
The following shows how the first round of reduction is performed. Note that all "empty" positions of the summands are considered to be zero (a . is used here as indicator of the "assumed zero values"). In each row, the top three bits are the three inputs to the full adder (two terms and carry-in). The sum is placed in the top bit of the column. The carry-out is placed in the second row of the column to the left. The bottom bit is a single feed into an adder. The sum of this adder is placed in the third row of the column. Carry-out is ignored as it will always be zero, but by design it would be placed in the fourth row of the column to the left. For design, it is important to note that rows 1, 3, 5, ... (counting from the top) are filled with sums from the column itself. Rows 2, 4, 6, ... are filled with carry-out values from the column to the right.
1011
x0110
-----
...0000
..1011.
.1011..
0000...
-------
0111010
000100.
00000..
Reduction is performed again in exactly the same way. This time, only the top three rows of summands are of interest because all other summands must be zero.
0111010
000100.
00000..
-------
0110010
001000.
When there are only two significant rows of summands, the reduction cycles end. A basic full adder normally requires three cycles of the arithmetic logic unit
Arithmetic logic unit
In computing, an arithmetic logic unit is a digital circuit that performs arithmetic and logical operations.The ALU is a fundamental building block of the central processing unit of a computer, and even the simplest microprocessors contain one for purposes such as maintaining timers...
. Therefore, each cycle of reduction is commonly 3 cycles long.