Circuit Herbology
 Assign: Tuesday, 24 September
 Due: In class or under the door of Andy's office (SCI E116) by 11:59pm on Tuesday, 1 October
 Policy: Individual graded synthesis assignment
 Submit: A neat paper copy of the cs240circuitsworksheet.pdf submission sheet .
 Reference:
Exercises
Please write your answers on the cs240circuitsworksheet.pdf submission sheet to streamline the grading process.
1. Marauder’s Map (10 points)
Consider the following Boolean Algebra expression which you saw earlier in your Entrance Gates assignment: $A’B’C’D’ + AB’C’ + AB’CD’ + ABD + A’B’CD’ + BC’D + A’$.
 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.
 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.
 Using the Karnaugh map above, write down the minimal sum of products.
2. Encoder a.k.a. the Undecoder? (8 points)
Draw a circuit to implement a 4to2 encoder using gates. An encoder is the opposite of a decoder. It takes $2^n$ inputs and provides $n$ outputs. Here, $n = 2$. Assume exactly one of the inputs carries $1$ and all others carry $0$. The output should be an $n$bit binary number giving the index of the input that is enabled. For example, if input $2$ (in the range $0..3$) is enabled and all others are disabled, the output should be $1$ $0$.
3. Moving Staircases (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 passthrough 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.
4. Flopflipflopping (10 points)
Consider the following circuit that uses fallingedge triggered D flipflops.
Cycles Completed  Q_{2}  Q_{1}  Q_{0} 
0 (initial state)  0  0  0 
1  
2  
…  
10 
Assume the Clock input, and outputs Q_{0}, Q_{1}, and Q_{2}, are all initially 0. Draw waveforms for Clock, Q_{0}, Q_{1}, and Q_{2}, 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.

Write a table summarizing the values of Q_{0}, Q_{1}, and Q_{2} after each Clock cycle.

Briefly explain what this circuit does at a high level, treating the Q outputs together. A phrase to a couple sentences is enough.
5. Value Judgments (24 points)
In class and lab we designed an $n$bit ALU by connecting $n$ 1bit ALUs. In these exercises, you will improve the 4bit version of our design.
Summary of our ALU design:
 The
Carry out
from each bit is wired to theCarry in
of the next bit, if present.  The full $n$bit ALU has 4 lines of control input:
Invert A
controls theinvert A
inputs of all of the 1bit ALUs.Negate B
controls: the
invert B
inputs of all of the 1bit ALUs; and  the carryin of the least significant bit ALU.
 the
 Two bits of
Operation ID
control theOperation
inputs of all of the 1bit 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.
 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:

[2 points] Design extra 1bit 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.  [6 points]
Describe the output of the ALU when
Invert A
= 1,Negate B
= 1, andOperation ID
= 10. Write your answer as an arithmetic or Boolean/bitwise expression
using $A$ and $B$, e.g.,
Result
= $A \& B$ orResult
= $\frac{2A}{B}$.  Your expression must use either arithmetic operators or Boolean/bitwise operators. You may not mix them.
 Write your answer as an arithmetic or Boolean/bitwise expression
using $A$ and $B$, e.g.,

[8 points] Consider a lessthan check for two’scomplement 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 point] Give a pair of values, $A$ and $B$, where this approach correctly indicates $A < B$.

[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.
 [6 points]
Redesign lessthan using minimal additional logic to compute
the correct lessthan result for all pairs of 4bit
two’scomplement values. Provide a 1bit 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.
 Using the provided sheet, draw and label your design.
 [5 points]
Design a 1bit 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.
 [3 points] Consider the similarities and differences in the workings of your designs for lessthan and equals. Does the problem we encountered with lessthan matter in your design of equality logic? Briefly explain why or why not.