 Multiplication |
Algorithm |
LMS Algorithm |
In order to achieve 8-bit and 12-bit signed addition we cascade two and three four-bit carry look-ahead blocks, respectively, in a ripple carry fashion (the carry out of the first adder is connected to the carry in of the second adder, etc.). The logic diagram for the 4-bit carry look-ahead block can be seen here. The equations for generating the carry in this circuit can be seen below.
We also allow for subtraction using the same carry look-ahead blocks. Subtraction is performed by negating one of the inputs and adding it to the other. Since we are dealing with signed numbers to get the negation of B we take its 2's complement. This is done by inverting each bit and adding 1. Thus, for our adder we simply need to place XOR gates at the inputs for B and XOR B with the carry in. This makes the carry in input a control signal for subtraction, if it is 0 B remains the same and is simply added to A, if it is 1 then B is inverted and 1 is added to it.
Overflow correction is performed for each of our adders by 1) generating an extra sign bit by XORing the MSBs of A and the carry out and 2) by comparing the values of the two sign bits and if they are not the same changing the output of the adder to either the maximum possible value or minimum possible value.
We also decided to use 4-bit carry look-ahead logic instead of 8-bit in order to limit the fan-in of the logic. Looking at the carry look-ahead equations it can be seen that as the number of bits increases, the complexity of the carry bit generation increases (increasing number of terms and increasing number of inputs to the gates in the logic diagram). We already require a 5 input NAND gate for the carry out generation in our 4-bit adder, with the 8-bit adder we would require a 9-input NAND gate for the carry bit and an 8-input NAND gate for the last sum bit.
gi = xi * yi
pi = xi + yi
ci+1 = pi * (gi + ci)
c1 = p0 * (g0 + c0)
= (x0 + y0) * (x0*y0 + c0)
c2 = p1 * (g1 + c1)
= (x1 + y1) * (x1*y1 + x0 + y0) * (x1*y1 + x0*y0 + c0)
c3 = g2 + p2*g1 + p2*p1*g0 + p2*p1*p0
c4 = g3 + p3*g2 + p3*p2*g1 + p3*p2*p1*g0 + p3*p2*p1*p0*c0
