0
\$\begingroup\$

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.

\$\endgroup\$
  • 3
    \$\begingroup\$ Your truth table says? \$\endgroup\$ – Ignacio Vazquez-Abrams Dec 1 '14 at 21:36
  • \$\begingroup\$ Describe the desired full adder by using a truth table, then see if you can synthesize the logic. If you are optimizing for least propagation delay, you may end up replicating some subexpressions. \$\endgroup\$ – MarkU Dec 1 '14 at 21:46
3
\$\begingroup\$

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
|improve this answer|||||
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.