Building a 2-bit adder with a propagation delay of at most 2 gates

Question

An XOR-gate itself counts as 2 gates, so if I use an XOR-gate the delay would already be 2.

I have no idea how to do this, as a full adder for one bit already contains 2 XOR-gates (or 1 XOR-gate, 1 AND gate and 1 OR gate) so that would already have a delay of 4, while I have to build a 2 bit adder with a delay of at most 2 gates.

Is it actually possible to do this? Otherwise there must be an error in my exercise book.

Answer 1

Not with only the standard AND, OR, and NOT gates. For the two-bit adder that takes in two-bit numbers AB and CD, and outputs a three-bit number XYZ, the truth table looks like this:

A B C D | X Y Z
0 0 0 0 | 0 0 0
0 0 0 1 | 0 0 1
0 0 1 0 | 0 1 0
0 0 1 1 | 0 1 1
0 1 0 0 | 0 0 1
0 1 0 1 | 0 1 0
0 1 1 0 | 0 1 1
0 1 1 1 | 1 0 0
1 0 0 0 | 0 1 0
1 0 0 1 | 0 1 1
1 0 1 0 | 1 0 0
1 0 1 1 | 1 0 1
1 1 0 0 | 0 1 1
1 1 0 1 | 1 0 0
1 1 1 0 | 1 0 1
1 1 1 1 | 1 1 0

The Karnaugh map for Y looks like this:

CD AB>
V  00 01 11 10
00  0  0  1  1
01  0  1  0  1
11  1  0  1  0
10  1  1  0  0

The problem is that since you are only allowed two gate delays, and we need both of those: one to AND together the bits in each group, and another to then OR those groups together. This means that the groups we can specify are limited to those that do not contain any NOTs, i.e. only the following:

   A         B          C         D        A*B       A*C       A*D       B*C
. . x x   . x x .    . . . .   . . . .   . . x .   . . . .   . . . .   . . . .
. . x x   . x x .    . . . .   x x x x   . . x .   . . . .   . . x x   . . . .
. . x x   . x x .    x x x x   x x x x   . . x .   . . x x   . . x x   . x x .
. . x x   . x x .    x x x x   . . . .   . . x .   . . x x   . . . .   . x x .

  B*D       C*D       A*B*C     A*B*D     A*C*D     B*C*D    A*B*C*D    True
. . . .   . . . .    . . . .   . . . .   . . . .   . . . .   . . . .   x x x x
. x x .   . . . .    . . . .   . . x .   . . . .   . . . .   . . . .   x x x x
. x x .   x x x x    . . x .   . . x .   . . x x   . x x .   . . x .   x x x x
. . . .   . . . .    . . x .   . . . .   . . . .   . . . .   . . . .   x x x x

Note that none of these groups covers the 1001 spot without covering the 1101 spot, which we need for Y. You may be able to get the correct groups using a NAND, NOR, or XNOR; but only if those count as 1 gate delay.

Note that if you are using a technology like CMOS logic where each bit has an inverse available, then using the Karnaugh map technique renders this problem trivial, with an example solution below (where a is NOT A, etc.):

X = AC + ABD + BCD
Y = Acd + abC + Abc + aCd + aBcD + ABCD
Z = bD + Bd