CS240-Homework 4 Solved

Half Adder and Full Adder
In digital circuits, the half adder adds two input bits, P and Q, and produces two output bits, sum S and carry C. See the left part of Figure 1. The truth table of the half adder is as follows.

input
output
P     Q
C       S
0      0
0       0
0      1
0       1
1      0
0       1
1      1
1       0
Ideally, we should write one function that computes both S and C, but we have not discussed how to return multiple values from a function. Therefore, we write two functions that compute S and C separately, as follows. enum bits {ZERO, ONE};

enum bits halfAdderSum(enum bits P, enum bits Q) {

                                                                               P      Q                                                P      Q

                                           (P AND Q)   C                                                    

S

(P XOR Q)

Figure 1: Left: the half adder. Right: the full adder

return P ^ Q;

}

enum bits halfAdderCarry(enum bits P, enum bits Q)

{

return P & Q;

}

The half adder adds only two bits. It becomes inadequate when we want to add more than two bits. Let us consider adding two 8-bit integers, P7P6P5P4P3P2P1P0 and Q7Q6Q5Q4Q3Q2Q1Q0. After we add P0 and Q0, the carry bit may be 1. We must incorporate it when adding P1 and Q1. Thus we need the full adder that takes three inputs: P, Q, and the carry-in Cin. The output bits are sum S and carry-out Cout. See the right part of Figure 1. The truth table of the full adder is as follows.

input
output
P
Q
Cin
Cout
S
0
0
0
0
0
0
0
1
0
1
0
1
0
0
1
0
1
1
1
0
1
0
0
0
1
1
0
1
1
0
1
1
0
1
0
1
1
1
1
1
Your task in this part of the homework is to implement the two functions for the full adder in the file adder.c. enum bits {ZERO, ONE};

enum bits fullAdderSum(enum bits P, enum bits Q, enum bits Cin)

{

}

enum bits fullAdderCarry(enum bits P, enum bits Q, enum bits Cin)

{

}

You should start by working out the Boolean expressions for S and Cout, and try to use as few Boolean operators as possible. The essence of C programming is brevity and efficiency.

2           Adding Two Numbers
Now you are ready to add two 32-bit integers bit by bit. Using a cascade of full adders, you can add a pair of bits and the carry bit from the previous position, save the sum bit, and send the carry bit to the next position. The first Cin should be set to zero. If we assume the sum of the two numbers does not overflow the 32-bit storage, we can safely discard the last Cout.

Your task in this part of the homework is to implement myAdd() in the file myAdd.c. The algorithm works as follows.

                                                                                      P1     Q1                P0     Q0
 

Figure 2: Using a cascade of full adders to add two numbers.

1.    Initialize Cin to zero

2.    For i = 0,1,...,31

(a)     Extract the i-th bits from P and Q

(b)     Use fullAdderSum() and fullAdderCarry() to calculate the sum bit S and the carry bit Cout

(c)     Write the sum bit to the i-bit of mySum

(d)     Move Cout to Cin for the next iteration

There are many ways to extract a bit or write a bit in a 32-bit storage. See the lecture notes 7 and 8 for different methods that operate on bits.

3         The Driver
The driver is in the file main.c. You should not change anything in the main program, but you should write some comments at the top of the file.

Make sure your C code follows the style guidelines. In the Report.txt file, you should write pseudo code and discuss what you found difficult about this assignment, how you planned your approach to it, and what you learned completing it.