Assignment: Circuits

Contents

Exercises

Please write your answers on the cs240-circuits-worksheet.pdf submission sheet to streamline the grading process. Submit your work by scanning a PDF of all worksheet pages (in order) and uploading it to Gradescope. Remember that this course uses your Gradescope account attached to your Wellesley email address (the variety that matches your username). You can merge accounts across multiple email addresses if helpful.

1. Decoding a T-shirt (10 points)

Margaret Ligon ‘14, a Wellesley CS student in the 2012 CS342 Computer Security class, designed a T-shirt for the Wellesley participants in the Lincoln Laboratory Capture the Flag (CTF) computer security contest. The back of the T-shirt is shown in the figure below. The binary and other digits on the shirt stand for a message that can be decoded with the help of an ASCII table, such as the one at http://www.asciitable.com/

  1. [6 points] What is the message?

  2. [4 points] Explain your steps for decoding the message.

Decode the message on this T-shirt.

2. Decoding a Unicode message (15 points)

You have been sent a message that consists of the following seven bytes (expressed in hex):

49 E2 99 A5 CF 80 21

You have been informed that this message consists of Unicode characters that have been encoded into a byte sequence via the UTF-8 encoding. Your goal in this problem is to decode the message.

Start this problem by doing two things:

  1. Read this article about what every programmer should know about Unicode. It’s an oldie, but goodie. It explains that Unicode characters are understood as code points, which are just numbers that specify Unicode characters. For example, codepoint U+03B1 is the Greek letter $\alpha$ (see http://unicode.org/charts/PDF/U0370.pdf).

  2. The core to understanding the UTF-8 encoding is the following table, which is explained in the Encoding section of the Wikipedia article on UTF-8.

    UTF-8 Encoding Table.

    The table shows how Unicode characters in the UTF-8 encoding can be represented as one to four bytes. The 0 and 1 bits are header bits that indicate how many bytes are being used for the current Unicode code point. The bits marked x in the encoding are the actual bits that specify the code point.

After you’ve finished the above two steps, you can now answer the parts of this question:

  1. [7 points] What is the sequence of Unicode code points in the UTF-8 encoded message 49 E2 99 A5 CF 80 21?

  2. [5 points] Explain your steps for decoding the Unicode message.

  3. [3 points] What would this message look like when displayed in a Unicode-enabled application?

3. Karnaugh Map (10 points)

Consider the following Boolean Algebra expression which you saw earlier in your Gates assignment: $A’B’C’D’ + AB’C’ + AB’CD’ + ABD + A’B’CD’ + BC’D + A’$.

  1. [3 points] Draw a truth table for the Boolean Algebra expression $A’B’C’D’ + AB’C’ + AB’CD’ + ABD + A’B’CD’ + BC’D + A’$. This is the same expression you saw earlier in your Entrance Gates assignment.
  2. [6 points] Draw a Karnaugh map for the truth table above. Remember that the columns and rows of the table are structured by gray codes. Make sure to circle the map accordingly to indicate the minterms needed to derive a minimal sum of products.
  3. [1 point] Using the Karnaugh map above, write down the minimal sum of products.

4. Switching Network (8 points)

Draw a circuit to implement a switching network with two data inputs ($A$ and $B$), two data outputs ($C$ and $D$), and a control input ($S$). If $S = 1$, the network is in pass-through mode: $C = A$ and $D = B$. If $S = 0$, the network is in crossing mode: $C = B$, and $D = A$. Use the most reasonable combinational building blocks or gates. Label the inputs and outputs.

5. Value Judgments (24 points)

n-bit ALU
4-bit ALU

In class and lab we designed an $n$-bit ALU by connecting $n$ 1-bit ALUs. In these exercises, you will improve the 4-bit version of our design.

Summary of our ALU design:

  • The Carry out from each bit is wired to the Carry in of the next bit, if present.
  • The full $n$-bit ALU has 4 lines of control input:
    • Invert A controls the invert A inputs of all of the 1-bit ALUs.
    • Negate B controls:
      • the invert B inputs of all of the 1-bit ALUs; and
      • the carry-in of the least significant bit ALU.
    • Two bits of Operation ID control the Operation inputs of all of the 1-bit ALUs.
1-bit ALU
1-bit component ALU

Rules for extending the ALU:

  • Any additional logic may connect to any existing wires in the ALU and add gates or other building blocks as needed.
  • Minimize the number of gates or other building blocks you add.
  • Choose the simplest option and clearly label new outputs.
  • Feel free to draw answers for separate exercises on separate diagrams or to combine them in one diagram, as you wish.

Exercises:

  1. [5 points] Design extra 1-bit outputs from the $n$-bit ALU for the four conditions codes (i) Zero Flag, (ii) Sign Flag, (iii) Carry Flag, and (iv) Overflow Flag. Their definitions are given in the slides on ALUs. Using the provided sheet, draw and label the additional logic required for each condition code (flag), all on one ALU diagram. Feel free to reuse designs from your notes.

  2. [6 points] Describe the output of the ALU when Invert A = 1, Negate B = 1, and Operation ID = 10.
    • Write your answer as an arithmetic expression using $A$ and $B$, e.g., Result = $A + B$ or Result = $\frac{2A}{B}$. Your answer should not involve Boolean/bitwise operators.
    • Explain briefly how you derived your arithmetic expression. (This answer should involve Boolean/bitwise operators.)

  3. [8 points] Consider a less-than check for two’s-complement operands that computes $A - B$ and returns a value based on the sign bit of the difference: 0 means $A \geq B$, 1 means $A < B$.

    1. [1 point] Give a pair of values, $A$ and $B$, where this approach correctly indicates $A < B$.

    2. [1 point] Give a pair of values, $A$ and $B$, where this approach incorrectly indicates $A < B$, even though actually, $A \geq B$. Name the key effect that caused the answer to be incorrect.

    3. [6 points] Redesign less-than using minimal additional logic to compute the correct less-than result for all pairs of 4-bit two’s-complement values. Provide a 1-bit output of the full ALU in the style of the condition codes you implemented above, yielding 1 if $A < B$ and 0 otherwise.
      • Show how to control each of the 4 control lines of the full ALU: Invert = ?, Negate B = ?, Operation = ??.
      • Using the provided sheet, draw and label your design.
  4. [5 points] Design a 1-bit equality test output for the ALU using minimal additional logic (but no additional XOR gates). Given inputs $A$ and $B$, this output wire should carry 1 if $A = B$ and 0 otherwise.
    • Show how to control each of the 4 control lines of the full ALU.
    • Using the provided sheet, draw and label your design.
  5. [3 points] Consider the similarities and differences in the workings of your designs for less-than and equals. Does the problem we encountered with less-than matter in your design of equality logic? Briefly explain why or why not.

Submission

Please write your answers on the cs240-circuits-worksheet.pdf submission sheet to streamline the grading process. Submit your work by scanning a PDF of all worksheet pages (in order) and uploading it to Gradescope. Remember that this course uses your Gradescope account attached to your Wellesley email address (the variety that matches your username). You can merge accounts across multiple email addresses if helpful.