Assignment: Circuits

Contents

Exercises

Please write your answers on the cs240-circuits-worksheet-s23.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. It has two parts: a base consisting of hex bytes and a flag consisting of bits. The hex and binary 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. [3 points] What is the message encoded in the hex bytes at the base of the flag? Explain the details of your decoding strategy by showing the character that correspond to each pair of hex digits.

  2. [7 points] What is the message encoded in the binary bits of the flag? (Hint: the line breaks in the flag don’t matter; they just make the shape of the bits look like a flag.) Explain the details of your decoding strategy by writing down the sequence of bits in the flag and showing the characters that correspond to subsequences of the bits. (Hint: focus on 8-bit bytes.)

Decode the message on this T-shirt.

2. Decoding a Unicode message (12 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 https://unicode-table.com/en/03B1 or do a web search for Unicode U+03B1.)

  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 content bits bits that specify the code point.

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

  1. [10 points] Show how to decode the Unicode UTF-8 message encoded in the hex bytes 49 E2 99 A5 CF 80 21 to a sequence of Unicode code points. Write the message bits corresponding to the message expressed in hex bytes, distinguish header bits from content bits, and indicate the number of bytes in each code point. Show the code points determined by the content bits. Write a code point as U+WXYZ, where each of W, X, Y, Z is a hex digit.

  2. [2 points] What would this message look like when displayed in a Unicode-enabled application? (Search for your code points at https://unicode-table.com/en.)

3. Universal Muxification of Gates (14 points)

Recall that a 2-to-1 mux (2:1 mux) has 3 inputs: a selector input S, and two choice inputs, labeled 0 and 1:

2:1 mux

2:1 muxes are universal in the sense that any circuit can be implemented using just 2-to-1 muxes. In this problem, you will show this by using muxes to implement various gates. In each circuit, draw the specified number of 2:1 muxes and implement the given boolean expression. A mux input can be A, B, 0, 1, or the output of another device (e.g., another mux or a decoder). Be sure to label the S, 0, and 1 inputs of every mux.

  1. [1 point] Use one 2:1 mux to implement NOT A (i.e. A')
  2. [1.5 points] Use one 2:1 mux to implement A AND B (i.e. AB)
  3. [1.5 points] Use one 2:1 mux to implement A OR B (i.e. A+B)
  4. [2 points] Use two 2:1 muxes to implement A NAND B
  5. [2 points] Use two 2:1 muxes to implement A NOR B
  6. [3 points] Use two 2:1 muxes to implement A XOR B
  7. [3 points] Use one 2:4 decoder and one 2:1 mux to implement A XOR B Recall that a 2-to-4-decoder looks like the following, and that only one of the four outputs is 1, as is determined by the output label, which corresponds to the the two input bits $B_1$$B_0$. E.g., the output labeled 01 is 1 when $B_1$ is 0 and $B_0$ is 1.
2:4 decoder

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.

Hints:
  • A good approach for thinking about a circuit with two outputs (in this case C and D) is to independently consider truth tables for individual outputs. E.g. what's a truth table for output C based on inputs A, B, S?
  • You may use multiple combinational units in your circuit.

5. 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’$. Recall that this expression has the following truth table:

A B C D out   A B C D out
0 0 0 0 1   1 0 0 0 1
0 0 0 1 1   1 0 0 1 1
0 0 1 0 1   1 0 1 0 1
0 0 1 1 1   1 0 1 1 0
0 1 0 0 1   1 1 0 0 0
0 1 0 1 1   1 1 0 1 1
0 1 1 0 1   1 1 1 0 0
0 1 1 1 1   1 1 1 1 1

  1. [8 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 product terms needed to derive a minimal sum of products. Recall that each circled block must be a maximal rectangle of 1s whose width and height are powers of two. These rectangles may wrap around the edges of the diagram and may overlap with each tother.

  2. [2 points] Using the Karnaugh map above, write down the minimal sum of products expression for the original boolean expression. (The answer is not unique. There are multiple distinct answers, but you need give only one.)

6. vALUe Judgments (29 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. [4 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. [16 points] Consider a less-than test $A < B$ 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. [3 points] Give three pairs of values, $A$ and $B$, where this approach correctly indicates $A < B$. (All results $A-B$ must be in the range [-8, 7] after arithmetic mod 16 is performed.)
      • In the first pair, both $A$ and $B$ should be positive numbers.
      • In the second pair, both $A$ and $B$ should be negative numbers.
      • In the third pair, one of the two numbers should be positive and one should be negative.

    2. [1 point] For what range(s) of values for the result $A - B$ (before modular arithmetic is performed) does the approach work correctly?

    3. [2 points] Give two pairs of values, $A$ and $B$, where this approach gives an incorrect answer to A < B. (All results $A-B$ must be in the range [-8, 7] after arithmetic mod 16 is performed.)
      • In the first pair, $A$ should be positive
      • In the second pair, $A$ should be negative

    4. [2 points] For what range(s) of values for the result $A - B$ (before modular arithmetic is performed) does the approach work incorrectly? Name the key reason that causes the answer to be incorrect.

    5. [4 points] Using minimal additional logic, design a one-bit Less-Than Flag whose value always correctly indicates $A < B$. after $A - B$ is performed. I.e., the Less-Than flag has value 1 if $A < B$ and 0 otherwise.

      • Also, show how to control each of the 4 control lines the full ALU to perform $A < B$:

        • Invert A = ? (1 bit)
        • Negate B = ? (1 bit)
        • Operation = ? (2 bits)

      • Using the provided sheet, draw and label your design.

    6. [2 points] Explain why your Less-Than Flag design always give the correct result.
  4. [3 points] Design a 1-bit Equality Flag 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.

    • Also, show how to control each of the 4 control lines the full ALU to perform $A$ == $B$:

      • Invert A = ? (1 bit)
      • Negate B = ? (1 bit)
      • Operation = ? (2 bits)

    • Using the provided sheet, draw and label your design.

  5. [3 points] Argue that, unlike for the Less-Than Flag, two’s complement signed overflow can’t lead to an incorrect result when using the Equals Flag to determine equality after the subtraction $A - B$. Consider two cases:
    • [1 point] If $A$ is equal to $B$, can $A-B$ be different from 0?
    • [2 points] If $A$ is not equal to $B$, can $A-B$ be zero?

Extra Fun (optional) Base64 Encodings

Read about Base64 encodings, and show how to express the bits in the hex bytes 49 E2 99 A5 CF 80 21 as a sequence of Base64 “digits”.

Submission

Please write your answers on the cs240-circuits-worksheet-s23.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.