CS240 Homework 4-Half Adder and Full Adder Solved

Description

The assignment is to use bitwise operations to add two numbers.

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, P₇P₆P₅P₄P₃P₂P₁P₀ and Q₇Q₆Q₅Q₄Q₃Q₂Q₁Q₀. After we add P₀ and Q₀, the carry bit may be 1. We must incorporate it when adding P₁ and Q₁. 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
   • Extract the i-th bits from P and Q
   • Use fullAdderSum() and fullAdderCarry() to calculate the sum bit S and the carry bit Cout
   • Write the sum bit to the i-bit of mySum
   • 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.