Your CPUs have gotten pretty saucy about how you don’t appreciate all the work they do. They want you to have to live in a binary world like they do, with no easy access to fancy, high-level concepts like addition and subtraction. If you want those fancy parts of math, you’ll have to earn them.
That’s right; you’ll be implementing a ripple carry adder in this homework.
You’ve seen the ripple carry adder back in lecture 10, and once again in lecture 24, but how much did you understand about it? The ripple carry adder is made up of one-bit adders, with the carry out of one unit going into the next.
Each bit of the adder can be described by this truth table:
| a | b | CarryIn | Sum | CarryOut |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
To add a pair of eight-bit numbers together, you would need 8 one-bit ripple carry adders.
Wikipedia has a fun animation, for everyone who enjoys those.
You will be provided with main program in hw5_main.c. It
will attempt to call three functions, which you must write. They are
defined as follows:
typedef struct BitResult BitResult;
struct BitResult {
bool sum;
bool carry;
};
void rippleCarryAdd(BitResult* results, unsigned int width, unsigned int a, unsigned int b);
void rippleCarrySubtract(BitResult* results, unsigned int width, unsigned int a, unsigned int b);
void rippleMultiply(BitResult* results, unsigned int width, unsigned int a, unsigned int b);width is the number of bits in the number, which is also
the number of BitResult structs inside of the results
variable.
The functions must be written in a file named rcadder.c.
That is also the only file that you will submit for this homework.
Addition is as we have discussed, and works with negative numbers in
2’s complement, but we haven’t discussed subtraction or multiplication.
Multiplication is actually the simpler concept. Begin with the 0 valued
array of bit results and add a into it b
times.
Subtraction can be done in different ways. You could take the two’s
complement of the subtrahend, b, and then add it to the
minuend, a, to get the difference. That would perform
a + (-b). Let’s look at the truth table for subtraction
before we do that.
| a | b | BorrowIn | Diff | BorrowOut |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 0 |
| 1 | 1 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 |
BorrowOut means that we’ll need to borrow a value from the next most significant digit. If that final operation has a 1 for BorrowOut, then the entire result is negative.
Notice that the equations for the sum and the different are the same.
The equations for Cout
and Bout
are similar, with negation of a making them the same
equation.
You must have the three described functions in
rcadder.c, but they can all share the same code for bit
addition, if you would like to add in an argument to handle
subtraction:
void bitAdd(BitResult* result, unsigned int bit_a, unsigned int bit_b, unsigned int carry_in, bool subtraction)Or you could implement different functions for subtraction and addition:
void bitAdd(BitResult* result, unsigned int bit_a, unsigned int bit_b, unsigned int carry_in);
void bitSub(BitResult* result, unsigned int bit_a, unsigned int bit_b, unsigned int borrow);Either option is fine. What matters is that your program compiles and
runs, and passes all of the tests. And one more thing. To help you
better appreciate the hard work of the CPUs in your computers, phones,
smart watches, cars, TVs, and toasters, they would also like you to do
this assignment without every using the +, -,
or * operators. You may use -- and
++ operators, and of course you can use the
BitResult* type, but if you use those operators somewhere
else you will lose 5 points (5 for each of the three operators, so 15
points in total).
Some examples:
make hw5 will build the code.
It takes 3 arguments. The first is the width of the numbers, in bits, and the second is the two numbers, a and b. The program will then print the sum, difference, and product, in binary.
$ make hw5 gcc hw5_main.c rcadder.c rcadder.h -o hw5 $ ./hw5 8 0x1 0x1 00000010 00000000 00000001 $ ./hw5 8 0x1 0x2 00000011 11111111 00000010 $ ./hw5 8 0x1 0x81 10000010 OF 10000000 10000001 $ ./hw5 8 0xFF 0x01 00000000 11111110 11111111 $ ./hw5 8 8 2 00001010 00000110 00010000
Testing
A testing script will be provided shortly.
Submission
You should submit your rcadder.c file through
Canvas.