Circuits

Assignment: Circuits

• Assign: Thursday 28 September
• Due: Thursday 5 October
• Policy: Individual graded synthesis assignment
• Submit: Upload a PDF written on the cs240-circuits-worksheet-f23.pdf submission sheet
• Reference:
  • Data as Bits
  • Integer Representation
  • Combinational Logic
  • Arithmetic Logic

Contents

• Assignment: Circuits
• Goals
• Exercises
  • 1. Karnaugh Maps (14 points)
  • 2. Universal Muxification of Gates (12 points)
  • 3. Switching Network (8 points)
  • 4. Flop-flip-flopping (10 points)
  • 5. vALUe Judgments (31 points)
  • Extra Fun (optional) Base64 Encodings
• Submission

Goals

• To practice using Karnaugh maps to simplify boolean circuits.
• To understand core combinational and sequential circuit building blocks: encoders, decoders, multiplexers, latches, and flip-flops.
• To master choosing which building blocks to use to implements high-level computational ideas.

Exercises

Please write your answers on the cs240-circuits-worksheet-f23.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. Karnaugh Maps (14 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. [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 product terms needed to derive a minimal sum-of-products. Recall that each circled block must be a maximal (that is, as large as possible without containing a 0 or being a non-power-of-two) rectangle of 1s whose width and height are powers of two. These rectangles may wrap around the edges of the diagram and may overlap.

2. [2 points] Using the Karnaugh map from part (a), write down the minimal sum-of-products expression for the original boolean expression. (The answer is not unique. There are multiple distinct answers; you only need to give one for full credit.)

3. [4 points] [Independent] Now, the goal is to construct a new circuit that outputs $1$ precisely when a 3-bit input $A$, interpreted as a 3-bit unsigned integer, is a prime number and outputs $0$ otherwise. Call the three input lines $A_2, A_1, A_0$, and consider $A_2$ as the most significant bit and $A_0$ as the least significant bit. Draw a Karnaugh map for this circuit.

4. [2 point] [Independent] Using the Karnaugh map from part (c), write down the minimal sum-of-products expression to determine if a 3-bit unsigned integer is prime.

2. Universal Muxification of Gates (12 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 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. [2 points] Use one 2:1 mux to implement A AND B (i.e. AB)
3. [2 points] [Independent] Use one 2:1 mux to implement A OR B (i.e. A+B)
4. [3 points] Use two 2:1 muxes to implement A NAND B
5. [4 points] [Independent] 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. Note that the 2-bit values on the right are arranged as $B_1$$B_0$ (that is, the bottom wire corresponds to the first, not the second, bit).

3. 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.

Note that a good approach for thinking about a circuit with two outputs (in this case, $C$ and $D$) is to independently consider the truth tables for individual outputs (e.g., what is the value of $C$ based on inputs $A$, $B$, and $S$?).

4. Flop-flip-flopping (10 points)

Consider the following circuit that uses falling-edge triggered D flip-flops.

Cycles Completed	Q2	Q1	Q0
0 (initial state)	0	0	0
1
2
…
10

Assume the Clock input, and outputs Q₀, Q₁, and Q₂, are all initially 0. Draw waveforms for Clock, Q₀, Q₁, and Q₂, showing at least ten Clock cycles. You do not need to turn in your waveform drawing, but it will help you reason about the circuit.

1. Write a table summarizing the values of Q₀, Q₁, and Q₂ after each Clock cycle.
   • Note the order that the table lists Q₀, Q₁, and Q₂: this will help you identify a pattern in the next part.
2. Briefly explain what this circuit does at a high level, treating the Q outputs together. A phrase to a couple sentences is enough. Hint: you have seen a similar circuit behavior in lab.

5. vALUe Judgments (31 points)

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.

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. Gates such as AND can have > 2 inputs.
• 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, just make sure they are readable.

Exercises:

1. [4 points] Design extra 1-bit outputs from the $n$-bit ALU for the four conditions codes. 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 for what we already covered in class.

   1. Zero Flag
   2. Sign Flag
   3. Carry Flag
   4. Overflow Flag.

2. [4 points] Describe the output of the ALU when Invert A = 1, Negate B = 1, and Operation ID = 10.

   1. 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.
   2. Explain briefly how you derived your arithmetic expression.

3. [13 points] Alice is trying to design a Less-Than flag output that computes $A < B$ for the 4-bit two’s-complement values $A$ and $B$. Her first idea is to compute $A - B$ and returns a value based on the sign bit of the result: her hope is that a 0 sign bit for the result of the subtraction means $A \geq B$ and a 1 sign bit for the result means $A < B$.

   1. [2 points] Give a pair of values, $A$ and $B$, where Alice’s approach correctly calculates $A < B$.
      • Recall that 4-bit two’s complement values range from [-8, 7].
   2. [2 point] Give a pair of values, $A$ and $B$, where Alice’s approach is incorrect in calculating $A < B$ (that is, where her approach either yields 0 when $A$ actually is less than $B$, or 1 when $A$ is not actually less than $B$). Explain what Alice’s approach returns and what the real answer is.
   3. [1 point] Name the key effect that causes Alice’s approach’s answer from the previous part to be incorrect.
   4. [5 points] Using minimal additional logic, help Alice design a 1-bit Less-Than Flag whose value always correctly indicates $A < B$. after $A - B$ is performed. That is, the new Less-Than flag should have value 1 if $A < B$ and 0 otherwise.
      • Using the provided sheet, draw and label your design.
   5. [3 points] Write how to control each of the 4 control lines of our 4-bit ALU to perform $A < B$:
      • Invert A = ?
      • Negate B = ?
      • Operation = ??

4. [7 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.

   1. [4 points] Using the provided sheet, draw and label your design.
   2. [3 points] Write how to control each of the 4 control lines the full ALU to perform $A$ == $B$:
      • Invert A = ?
      • Negate B = ?
      • Operation = ??

5. [3 points] [Independent] Consider the similarities and differences in the workings of your final designs for Less-Than and Equals. Does the problem Alice encountered with Less-Than matter in your design of equality logic? Briefly explain why or why not. Be sure to cover all possible cases in your explanation.

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-f23.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.