What is the minimum amount of 1bit Full Adders required to implement the equation 4X + 3Y + 13?

Question

Using 1bit FAs and 0/1 constants only, while X(x1,x2,x3) and Y(y1,y2,y3) are 3bit each.

It is possible to implement it easily with 7FA, and there's a solution with 6FA as well.

Is there a solution with 5 or less? If not, why? Is there any systematic way to solve such problems?

This is how I break down the problem:

0  x1  x2  x3   0  0
0   0  y1  y2  y3  0
0   0   0  y1  y2 y3
0   0   1   1   0  1
====================
z1 z2  z3  z4  z5 z6

Here is a truth table I made for the problem.

Currently, I've got to the conclusion that:

z6 = ~y3
z5 = y2
z4 = ~(x3 XOR y1 XOR y2 XOR y3)

But I'm not sure how helpful that is.

Answer 1

Well, to consider your basic question: what is the minimum number of full adders required?

You have initially twelve partial products (bits), while your result has six. Each fully utilized full adder will remove one partial product (bit) and therefore you need exactly12 - 6 = 6 full adders. Then, given that you do not use half adders, there may in practice be more. The ways to get around this are to recode the bits and/or simplify some computations to not use full adders (as you say, some inputs are constant).

Here's an alternative solution:

Rewrite 3Y as 4Y-Y leading to (a' denoting not(a))

 0  x1  x2  x3   0   0
 0  y1  y2  y3   0   0
y1' y1' y1' y1' y2' y3'  -- Sign-extend, invert and add a one at the LSB position
 0   0   0   0   0   1   
 0   0   1   1   0   1

The sign extension can be rewritten as

 0  x1  x2  x3   0   0
 0  y1  y2  y3   0   0
 0   0   0  y1 y2' y3'  -- Sign-extend, invert and add a one at the LSB position
 1   1   1   1   0   0  -- In two's complement one can use this trick to avoid the negative sign bit -b = 1-b'
 0   0   0   0   0   1   
 0   0   1   1   0   1

This now results in:

 0  x1  x2  x3   0   0
 0  y1  y2  y3   0   0
 0   0   0  y1  y2' y3'
 0   0   1   0   1   0 

Now, there are eleven partial products, but two of them are inverted. Also, as the second least significant column contains only two partial products, we will need to employ an additional full adder, despite a half adder being enough.

Looking at y2' + 1, the sum bit becomes (as you've noted) y2, while the carry bit becomes y2'. Hence, no full adder is needed. This leaves you with

 0  x1  x2  x3   
 0  y1  y2  y3   
 0   0   1  y1     
 0   0   0  y2' 
----------------------
z1  z2  z3  z4  y2  y3' 

and nine partial products producing a result with four bits, i.e., five full adders.

To get away with the inverter, one can rewrite this as (using 2y2 + y2' = 1 + y2)

 0  x1  x2  x3   
 0  y1   1  y3   
 0   0   0  y1     
 0   0   0  y2
 0   0   0   1 
----------------------
z1  z2  z3  z4  y2  y3' 

although it will not change the number of full adders.

Now, if you want to save one more full adder, you can recode some of the bits into something possibly "easier". Consider the partial products

0  y1   1  y1   
0   0   0   1     

Which is the expression 5y1 + 3. Hence, the truth table for this part is

y1   result  binary
---------------------
 0      3     0011
 1      8     1000

This leads to that we can change these four partial products to the following three

y1  x1  x2  x3   
 0   0  y1' y3   
 0   0   0  y2    
 0   0   0  y1'    
----------------------
z1  z2  z3  z4  y2  y3' 

resulting in eight partial products, but still five full adders (out of which two computing z1 and z2 can be made half adders).

Answer 2

The problem is in \$z_4\$. You want to add four bits, which could make 100, so you'd have to go to \$z_2\$ with the carry.

There is a normal approach, where you see 13 as a variable like x and y, so basically this is able to solve equations \$4x+3y+a\$ with \$a = (a_1,a_2,0,a_4)\$. In this approach, you can easily calculate the number of full adders needed by working from the right to the left:

• At \$z_6\$ you add two bits, so you require 1 adder.
• At \$z_5\$ you add two bits and the carry \$c_6\$ from \$z_6\$, so you require 1 adder.
• At \$z_4\$ you add four bits and \$c_5\$, so you require 2 adders.
• At \$z_3\$ you add three bits and two carries, so you require 2 adders.
• At \$z_2\$ you add one bit and two carries, so you require 1 adder.
• At \$z_1\$ you'd only 'add' the carry, which makes 0 adders.

This requires 7 adders.

---

However, because 13 isn't really a variable but a constant, you might be able to do something smart. In that case, you can work from the normal setup for \$4x+3y\$:

• \$z_6 = y_3\$ (1 bit, 1 adder, 2 bits open)
• \$z_5 = c_6 + y_3 + y_2\$ (3 bits, 1 adder, 0 bits open)
• \$z_4 = c_5 + y_2 + y_1 + x_3\$ (4 bits, 2 adders, 2 bits open)
• \$z_3 = c_{4_1} + c_{4_2} + y_1 + x_2\$ (4 bits, 2 adders, 2 bits open)
• \$z_2 = c_{3_1} + c_{3_2} + x_1\$ (3 bits, 1 adder, 0 bits open)
• \$z_1 = c_2\$ (1 bit, 0 adders, 0 bits open)

However, this basic setup for \$4x+3y\$ already requires 7 adders. Since \$z_4\$ uses two adders, you will have two carries that you have to add to \$z_3\$, which makes that you have there two adders as well - and thus two carries.

It might be possible to do something smart to lose one adder, but it's not going to work with 5 adders, and here is why:

---

\$z_1\$ is just an overflow and requires no adders. \$z_2\$ through \$z_6\$ though, there are adders needed. This makes 5 adders. Now, you need at least two adders at \$z_4\$, since you are adding \$x_3\$, \$y_2\$, \$y_1\$ and the carry from \$z_5\$, \$c_5\$. So at \$z_4\$ you have to add four bits, which makes that you need two adders instead of one, making the total at least 6.

Please note that you need at least 6 for the simplified equation, \$4x+3y\$, so it's not relevant whether you can do something smart with the 13 or not - this is the basic setup and you will need at least 6 adders for it.

Answer 3

You can do this with 5 full adders and 1 Not gate.

Z6 and z5 can be implemented the way you've described. For z4 through z1, you'll need to use fulladders. To start with, lets find out the carry that goes into z4's column (let me call this Ci4). This is equal to y3, so no additional hardware is required to generate this.

We need to add 5 numbers (Ci4, x3, y2, y1 and 1) to get z4. This will require 2 full adders (feed Ci4, x3 and y2 to the first fulladder to generate an intermediate sum S4x, then feed this sum along with y1 and 1 to the second full adder). Now, the two fulladders will generate 2 carries (let me call them Ci3a and Ci3b), which we'll feed the next stage(z3).

For z3 also we have to add 5 numbers (x2, y1, 1, Ci3a and Ci3b). Use the same approach as we did for z4 (add 3 signals, and add the intermediate sum with the remaining two). This stage will leave us with two generated carries Ci2a and Ci2b.

For z2's column, we have only one input x1, along with Ci2a and Ci2b. We need just one full adder to handle these 3 inputs. Sum generated by this full adder will be z2 and its carry will be z1.

You can, maybe, have a look at hardware multipliers, particularly the stage that adds the shifted partial-products.