[prev] [prev-tail] [tail] [up]

3 Optimizing a full adder for two bits

We are not ambitious here because with a width of two-bits, there are 16 possible cases already! Table 2 is the truth table of the output values. Note that we are only interested in the sum bit s1 and the carry bit c1.

x0y0x1y1s0c0s1c1
0 0 0 0 0 0 0 0
0 0 0 1 0 0 1 0
0 0 1 0 0 0 1 0
0 0 1 1 0 0 0 1
0 1 0 0 1 0 0 0
0 1 0 1 1 0 1 0
0 1 1 0 1 0 1 0
0 1 1 1 1 0 0 1
1 0 0 0 1 0 0 0
1 0 0 1 1 0 1 0
1 0 1 0 1 0 1 0
1 0 1 1 1 0 0 1
1 1 0 0 0 1 1 0
1 1 0 1 0 1 0 1
1 1 1 0 0 1 0 1
1 1 1 1 0 1 1 1

Table 2: Truth table of a 2-bit adder.

In order to optimize the SOP of a 4-variable truth table, we need to use a k-map that has four row and four columns. Table 3 is the k-map of the sum bit s1.

x1y1 ↓,x0y0 →00011110
00 0 0 1 0
01 1 1 0 1
11 0 0 1 0
10 1 1 0 1

Table 3: K-map of s1 of a two-bit adder.

From this k-map, we can see that not much can be optimized. The final expression is s1 = x0y0x1′y1′ + x0y0x1y1 + x0′x1′y1 + y0′x1′y1 + x0′x1y1′ + y0′x1y1′.

The k-map of c1 of a two-bit adder is illustrated in table 4.

x1y1 ↓,x0y0 →00011110
00 0 0 0 0
01 0 0 1 0
11 1 1 1 1
10 0 0 1 0

Table 4: K-map of c1 of a two-bit adder.

In this case, we see more opportunities for optimization. A “quad” is the row corresponding to x1y1 = 11. After optimization, we can express c1 = x1y1 + x0y0y1 + x0y0x1.

Note that the SOP expressions of s1 and c1 only involve two levels of logic (conjunction, then disjunction). This means the propagational delay of these implementations is less than that of the modular design. However, the gain of performance costs gates and real-estate on a chip.

Furthermore, the SOP expressions of s2, s3 and etc. are quite a bit more complex than that of s1.

[prev] [prev-tail] [front] [up]