CS 111
Spring 2018

Old version

This is the CS 111 site as it appeared on May 10, 2018.

Problem Set 5

Preliminaries

In your work on this assignment, make sure to abide by the collaboration policies of the course.

If you have questions while working on this assignment, please come to office hours, post them on Piazza, or email cs111-staff@cs.bu.edu.

Make sure to submit your work on Apollo, following the procedures found at the end of the assignment.

Part I

due by 11:59 p.m. on Thursday, March 15, 2018

Problem 0: Reading and response

5 points; individual-only

Our recent focus in CS 111 has been on low-level computer organization. This week’s reading considers one man’s vision of the future of computation hardware and, more generally, of humanity itself!

Begin by reading a profile of inventor and futurist Ray Zurzweil from The Guardian.

After you have read it, write a response that addresses–at least to some extent–both of the following prompts. Put your response in a file named ps5pr0.txt. Don’t forget that the file that you submit must be a plain-text file.

  1. Kurzweil views technology as a fundamentally positive force in human development. Is his vision of the future one that you would look forward to? Why or why not?

  2. Kurzweil has a track record of remarkable inventions and successful predictions. Do you believe the predictions cited in this article? Why or why not?

As always, you only need to write a short paragraph that reflects your critical thinking about the article.

Preparing for the Remaining Problems in Part I

Warning

In each of the starter files, we have included switches for the inputs and one or more light bulbs for the outputs. You must use the provided components in your circuit, and you should not change their properties in any way (e.g., by changing their names).

If you fail to use our components without changing them, we will not be able to automate the grading of your submission, and you will lose points as a result.

Problem 1: XOR

5 points; individual-only

Open the ps5pr1.logicly starter file in Logicly (see above for instructions on how to obtain the starter files).

The XOR function takes two inputs (x and y), and it outputs a 1 if and only if exactly one of its inputs is 1. It has the following truth table:

  inputs  |
  x    y  | output
-------------------
  0    0  |   0
  0    1  |   1
  1    0  |   1
  1    1  |   0

Build a circuit for the XOR function using the minterm expansion principle that we discussed in lecture. The resulting circuit should use only AND, OR, and NOT gates.

Notes:

Problem 2: Full Adder

20 points; pair-optional

This is one or only two problems that you may complete with a partner. See the rules for working with a partner on pair-optional problems for details about how this type of collaboration must be structured.

Open the ps5pr2.logicly starter file in Logicly. If you are working with a partner, there is a text block at the top of this subcircuit for your partner’s name and email (if any). To add the necessary information, select the text block with the Selection Tool (the arrow) and edit the Text in the Label Properties pop-up window.

Build a Full Adder (FA) as described in lecture. It is also described in section 4.3.4 of the textbook. Use the minterm expansion principle to create a circuit that uses only AND, OR, and NOT gates.

Remember that a Full Adder adds a single column of digits from the bitwise sum of two binary numbers. It takes three inputs:

and it should produce two separate outputs:

See below for how to export your Full Adder so that it can be used in later problems.

Notes:

Problem 3: 4-Bit Ripple-Carry Adder

20 points; individual-only

Open the ps5pr3.logicly starter file in Logicly.

Build a 4-Bit Ripple-Carry Adder. We examined a 2-Bit Ripple-Carry Adder in lecture, and the textbook also discusses it. This problem requires you to extend that circuit to a 4-bit version.

Recall that a Ripple-Carry Adder combines multiple Full Adders to produce a circuit that adds two binary numbers. Each Full Adder handles one column of the addition. The circuit as a whole takes eight inputs:

and it should produce five outputs (s4, s3, s2, s1, and s0) that correspond to the five bits of the sum. The relationships between the inputs and the outputs are shown below:

   x3 x2 x1 x0
+  y3 y2 y1 y0
--------------
s4 s3 s2 s1 s0

Note that the sum has five bits to accommodate the possibility of a carry.

This circuit should not be built using the minterm expansion principle. Rather, it should be built by combining four instances of your Full Adder circuit.

See below for information about how to import your Full Adder, as well as for the steps needed to export Ripple-Carry Adder so that it can be used in later problems.

Notes:

Problem 4: 4x1 Multiplier

10 points; individual-only

Open the ps5pr4.logicly starter file in Logicly.

Build a 4x1 multiplier in the space provided. This circuit takes five inputs:

It will have four outputs (p3, p2, p1, and p0) that correspond to the four bits of the product. The relationships between the inputs and the outputs are shown below:

   x3 x2 x1 x0
*            y
--------------
   p3 p2 p1 p0

Because you are multiplying the first factor by either 0 or 1, the product can be computed very simply, using exactly four gates! Considering some concrete cases should help you to determine which gates you should use, and how they should be arranged. You should not need to employ the minterm expansion principle.

Notes:

Problem 5: 4x2 Multiplier

15 points; individual-only

Open the ps5pr5.logicly starter file in Logicly.

Build a 4x2 multiplier, which takes six inputs:

and produces as outputs the six bits of the product: p5, p4, p3, p2, p1, and p0.

Your circuit should perform the computation shown below:

      x3 x2 x1 x0
   *        y1 y0
-----------------
p5 p4 p3 p2 p1 p0

You circuit should employ the “elementary-school” binary multiplication algorithm that we discussed in lecture. More specifically, you need to compute two partial products: the product of the top number (x3 x2 x1 x0) with the bit y0, and the product of the top number with the bit y1. You then need to add these partial products together in the appropriate way.

This circuit should not be built using the minterm expansion principle. Rather, it should be built by combining one or more instances of your 4x1 Multiplier and your 4-Bit Ripple-Carry Adder. See below for information about adding those components to your circuit.

Notes:

Optional Bonus Problem: 3x2 Divider

for 10 points of extra credit; individual-only

Open the ps5pr6.logicly starter file in Logicly.

Build a 3x2 Divider, which takes five inputs:

and produces four outputs:

The relationships between the inputs and the first three outputs are shown below:

        q2 q1 q0
      ___________
x1 x0 | y2 y1 y0

Note that the circuit should perform integer division–rounding down and ignoring any remainders. For example, 7 divided by 2 should be 3:

      0 1 1
    _________
1 0 | 1 1 1

Two possible approaches:

  1. Use the full truth table for 3x2 division (which we discussed in lecture), and apply the minterm expansion principle three times–once for each bit of the quotient. (The portion of the circuit that handles the error bit can be constructed more simply, because its output only depends on the divisor.)

  2. Break the problem into pieces by considering each of the four possible divisors separately:

    • divisor is 1: Any dividend that is divided by 1 will be passed directly to the output quotient without any changes.

    • divisor is 2: Dividing by 2 is equivalent to shifting the bits in the dividend one place to the right to produce the quotient. The example above of 7 divided by 2 provides one illustration of this.

    • divisor is 3: This is a trickier case! Look at the rows in the truth table for this divisor, and see if you can identify any patterns that will allow you to simplify this portion of the circuit.

    • divisor is 0: This always results in an error, regardless of the value of the dividend. In addition, we don’t care what is produced for the bits of the quotient in this case.

    Each of these four divisors can be a subcircuit that you build and test on its own. Then you can combine the outputs of the subcircuits by ORing the outputs for a given output bit together. For example, the value of q0 can be obtained by ORing together the value produced for q0 by each of the subcircuits.

    When constructing the OR gate for a given output bit, you only need to include the subcircuits that may produce a 1 for that output bit. For example, when constructing the OR gates for the bits of the quotient, you don’t need to include the divisor-is-0 subcircuit, because that subcircuit only produces a 1 for the error bit.

Notes:

Part II

due by 11:59 p.m. on Sunday, March 18, 2018

Preparing for the Problems in Part II

Warning

After each change that you make to your assembly code, make sure to resave the file before you assemble and run it.

Problem 7: Cubic countdown

10 points; individual-only

In this problem you will modify an existing assembly-language program.

Your work for this problem should go in the file ps5pr7.txt that we have given you in the ps5partII folder. Begin by opening the file in any text editor.

Start by assembling and running the existing program that we have given you.

Enter an integer (e.g., 32000), and you should see the program counting upward from that number. When it gets to 32767, which is the maximum possible value, it will stop. If you want to stop the program early, you can do so by hitting Control-C.

Look over the code, and make sure that you understand how it works!

Important

Note that line 03 of the provided code uses a jumpn instruction to perform an unconditional jump to line 01. You must use jumpn when performing an unconditional jump in Hmmm. The alias jump (without the n) is not the same thing as jumpn.

Your task is to modify the code in ps5pr7.txt so that it does the following:

  1. Asks the user for an input. You may assume that the input will be positive and less than 30.

  2. Computes the cube of that input, and prints the result. You will need multiple multiplications to compute the cube! Before proceeding to the next step, add a temporary halt statement, and test the current version of your program to ensure that it works.

  3. Counts downward from the cube of the input to 0, one integer at a time, and printing each value. For example, if the user’s input is 2, the program should print the following:

    8
7
6
5
4
3
2
1
0

    Consider starting this step by just adding the statements needed to compute and print one less than the cube of the input, and then halt. Test the program to confirm that it correctly prints that value, and then add the statements needed to create a loop that continues the countdown all the way to 0.

  4. When the count is less than 0, the program should stop. Note that the last value printed should be 0, not -1.

Important notes:

  • Make sure to follow the style guidelines that we’ve specified. In particular, you must have a comment on every line except for nop and halt statements.

  • Make sure that your comments do not include any special characters (e.g., $, quotes, or &).

  • You will need to decide how many additional registers you need, and which one(s) you wish to use. You can use any register from r1 to r15. Register r0 is not available for our purposes.

  • In all of your work on this problem set, we strongly encourage you to take a one-step-at-a-time approach like the one that we’ve outlined above. Gradually add functionality to your program, and test each new addition before continuing. This should make your program development and debugging much more manageable.

  • Remember that nop statements are useful as spacers that provide room for you to grow your program without needing to renumber lines.

  • After each change that you make to your assembly code, make sure to resave the file before you assemble and run it.

Problem 8: Computing a power by looping

20 points; pair-optional

This is the second of two problems from this assignment that you may complete with a partner. See the rules for working with a partner on pair-optional problems for details about how this type of collaboration must be structured.

Your work for this problem should go in the file ps5pr8.txt that we have given you in the ps5partII folder. Begin by opening the file in a text editor.

Your task is to write an assembly-language program that uses a loop to compute a power. Your program should do the following:

  1. Ask the user to enter two inputs. You may assume that these inputs will be nonnegative integers.
  2. Use a loop to compute the result of raising the first input to the power of the second input.
  3. Print the result and exit.

For example:

Enter number: 2
Enter number: 5
32

One good model for this problem is the loop-based factorial program that we reviewed in lecture. We’ve reproduced it below:

00   read r1           # get # from user and store it in r1
01   setn r2 1         # initialize r2, which will store the result
02   jeqzn r1 08       # jump to line 08 if r1 == 0
03   mul r2 r2 r1      # r2 = r2 * r1
04   addn r1 -1        # r1 = r1 - 1
05   jumpn 02          # jump back to line 02
06   nop
07   nop
08   write r2          # write out the result
09   halt

Notes/hints:

Problem 9: Calling a distance function twice

20 points; individual-only

Your work for this problem should go in the file ps5pr9.txt that we have given you in the ps5partII folder. Begin by opening the file in a text editor.

The distance between two integers x0 and x1 is the absolute value of their difference. For example, in Python we could do the following:

distance = abs(x0 - x1)

Your task is to write a Hmmm assembly-language program that implements a separate function for computing the distance between two integers, and that uses that function twice to determine which of two candidate values is closer to a third value.

More specifically, your program should do the following:

  1. Read three integers from the user:

    • a reference value, x0
    • the first candidate value, x1
    • the second candidate value, x2

  2. Call a single separate function twice to compute:

    • the distance between the reference value x0 and the first candidate value x1

    • the distance between the reference value x0 and the second candidate value x2

    Note that the distance computations must be made by a separate function, and you must call the same function twice. You will lose points if you call two separate functions, or if you make only one call to a function that performs both distance computations.

  3. Determine which of the candidate values (x1 or x2) is closer to the reference value x0, and print the closer of the two candidate values.

In other words, your program must follow the same basic approach taken by the following code, which is a mixture of Python and pseudocode:

def main():
    read x0 from user   # This isn't real python syntax, but the
    read x1 from user   # idea here is to get the inputs from the user.
    read x2 from user
    d1 = distance(x0, x1)
    d2 = distance(x0, x2)
    if d1 <= d2:
        print(x1)
    else:
        print(x2)

def distance(x, y):
    """ compute and return the distance between the integers x and y """
    return abs(x - y)

Your task is to follow the approach taken by this code, but to do so in Hmmm assembly language. You should have a section of Hmmm code that corresponds to main above, and a section that corresponds to distance above. Note that the distance portion of the program does not print anything. It simply returns its value to main, which determines the candidate value with the smaller distance and prints that value.

Here are some sample runs of the program:

Enter a number: 3
Enter a number: 1
Enter a number: 7
1

Enter a number: 3
Enter a number: 7
Enter a number: 1
1

Enter a number: 0
Enter a number: -4
Enter a number: 3
3

Enter a number: 3
Enter a number: -1
Enter a number: 7
-1

Enter a number: 3
Enter a number: 7
Enter a number: -1
7

Notes/hints:

Submitting Your Work

Note: Apollo does not accept submissions until one week before the deadline, so you won’t be able to submit your work until we are in that window.

You should use Apollo to submit the following files:

Warnings

  • Make sure to use these exact file names, or Apollo will not accept your files. If Apollo reports that a file does not have the correct name, you should rename the file using the name listed in the assignment or on the Apollo upload page.

  • Before submitting your files, make sure that your BU username is visible at the top of the Apollo page. If you don’t see your username, click the Log out button and login again.

  • If you encounter problems with Apollo, click the Log Out button, close your browser and try again. If possible, you may also want to wait an hour or two before retrying. If you are unable to submit and it is close to the deadline, email your homework before the deadline to cs111-staff@cs.bu.edu.

Here are the steps:

  1. Login to Apollo, using the link in the left-hand navigation bar. You will need to use your Kerberos user name and password.
  2. Check to see that your BU username is at the top of the Apollo page. If it isn’t, click the Log out button and login again.
  3. Find the appropriate problem set section on the main page and click Upload files.
  4. For each file that you want to submit, find the matching upload section for the file. Make sure that you use the right section for each file. You may upload any number of files at a time.
  5. Click the Upload button at the bottom of the page.
  6. Review the upload results. If Apollo reports any issues, return to the upload page by clicking the link at the top of the results page, and try the upload again, per Apollo’s advice.
  7. Once all of your files have been successfully uploaded, return to the upload page by clicking the link at the top of the results page. The upload page will show you when you uploaded each file, and it will give you a way to download the uploaded file. Click on the link for each file so that you can ensure that you submitted the correct file. Note: Because Apollo cannot display Logicly files, you will need to download each uploaded file and view it in Logicly to confirm that you have submitted the correct file.

Warning

Apollo will automatically close submissions for a given file when its final deadline has passed. We will not accept any file after Apollo has disabled its upload form, so please check your submission carefully following the instructions in Step 7 above.