Description
1 Overview
You are to construct a C program that specifically “simulates” a 256 bit Carry Lookahead
Adder using 4 bit blocks. We use the term “simulate” here because unlike in real hardware,
your CLA adder will not run faster than the serial ripple-carry adder. Here, you will be
doing the steps. However, keep in mind that if each level where done completely in parallel
via hardware, then it clear executes much, much faster.
For a list of bitwise operators and the associated C language syntax, please see: https:
//en.wikipedia.org/wiki/Operators_in_C_and_C%2B%2B. Make sure you used the older
ANSI-C operators and not the newer operator forms/syntax (e.g., XOR is ˆ in C).
Recall, that a CLA adder can be constructed from the follow:
1. Calculate gi and pi
for all 256 bits i.
2. Calculate ggj and gpj
for all 64 groups j using gi and pi
.
3. Calculate sgk and spk for all 16 sections k using ggj and gpj
.
4. Calculate ssgl and spl
for all 4 super sections l using sgk and spk. Note, it is at this
point, we can shift to computing the top-level sectional carries. This is because the
number of sections is less than or equal the block size which is 4 bits.
5. Calculate sscl using ssgl and sspl
for all l super sections and 0 for ssc−1.
6. Calculate sck using sgk and spk and correct sscl
, l = k div 4 as super sectional carry-in
for all sections k.
7. Calculate gcj using ggj
, gpj and correct sck, k = j div 4 as sectional carry-in for all
groups j.
1
8. Calculate ci using gi
, pi and correct gcj
, j = i div 4 as group carry-in for all bits i.
9. Calculate sumi using ai ⊕ bi ⊕ ci−1 for all i.
You need to construct a C-program that executes on submitty.cs.rpi.edu that reproduces this algorithm. Each step in the above algorithm will be implemented as a separate
function. Also, the arrays can be globally/statically allocated in memory. No need for
dynamic memory allocation.
More specifically, you will do the following:
1. Read two 64 digit hex numbers as input.
2. Convert the “hex” (base-16) string to a “binary” (base-2) string. NOTE: That hex[0]
is the most significant digit, so when you convert to the “binary” string, you need to
make sure that binary[255] is the most significant digit. This can be done by translating
each hex digit into it’s binary format (e.g., B = 1011) and then reversing the whole
binary array to make sure that binary[255] is the most signficant digit and in the right
order with repect to how the hex digits where translated.
3. Each bit can be a full integer and so you’ll have arrays of unsigned ints for each of the
components parts of the adder.
4. Write functions for each step in the above algorithm. You can do it using for loops
and do not have to perform the equation substitutions by hand as we did in class.
5. A master “cla” routine will run thru all the steps.
6. You main routine will invoke your input reading function, followed by your master
“cla” function and then reconvert the binary sum of the two numbers into hex output.
7. Last, you can check your answer by creating a simple ripple carry adder based on
computing the ci = gi + pi ∗ ci−1 for all i and then computing the final sum, based on
sumi = ai ⊕ bi ⊕ ci−1.
8. Convert the binary sumi array to “hex” and output your result in 128 digit “hex”
format. Note, you’ll need to re-invert/reverse the answer so that it prints correctly.
2 HAND-IN and GRADING INSTRUCTIONS
Please submit your C-code to the submitty.cs.rpi.edu grading system. The grading rubic
will be available to test your solution.
2