Reed CSCI 221 Fall 2020

Homework 06: digital circuits

Due: Thursday, October 15th

• from Git classroom link
• as ZIP file

In this homework we continue to construct digital circuits using only AND, OR, and NOT gates. In all of these, there is some collection of inputs, and those inputs should simply feed forward into gates, continuing in this way to produce some outputs. Soon we’ll add memory and feedback to our digital circuits, but these ones do not have that. Instead, they are just combinatorial circuits. They take their inputs and “combine” them (again using AND, OR, and NOT logic) to produce their outputs.

For such circuits it’s possible to apply a “truth table method” to devise the boolean expression for each output of the circuit. Here is that method’s algorithm:

1. Pick one of the outputs. Lay out a truth table describing what that output should be for each of the possible combinations of 0s and 1s fed into the inputs. If the circuit has n inputs, this table should have 2^n rows. Each row should correspond to some input situation the circuit would face.

2. Highlight the rows of the table that corresponds to an output of 1. Each such row corresponds to a condition on the inputs that would be a case when the circuit’s logic holds true.

3. Express the pattern of each row’s 0 and 1 inputs using a logical conjunction. For example, something like (NOT x) AND y AND (NOT z) for the x:y:z row labelled with 0:1:0. This conjuction is a product of the input variables or their negations. The product is called a clause describing that row’s case.

4. Link together these conjunctions with disjunction. In other words, put an OR between all the clauses found in Step 3. This is called a sum of those products.

5. Build the subcircuit for that output (say, in LogiSim). Place a single OR gate that has a number of inputs equal to the number of product clauses. Place an AND gate, one for each clause’s product. Feed each AND gate’s output into the OR gate. Feed each circuit input variable’s wire directly, or negated with NOT, into each AND gate, depending on whether that input is 0 or 1 for that clause’s row in the truth table.

6. Repeat steps 1-5 for all the other outputs.

This always builds a circuit of depth 2 or 3, that is, each path you can draw between an input and an output passes through either two or three gate “layers.” There is the final OR gate layer that forms the outputs. There is a middle AND gate layer where each feeds into the OR gates. And then there is the possible first layer of NOT gates. This layering directly corresponds to the “sum of products” logical expressions we’ve devised.

Now, in class we also talked about ways of simplifying the logic. This involved using properties of AND, OR, and NOT, the boolean laws for performing algebraic simplification of our logical expressions. A lot of these laws are built into the Karnaugh map method, which we’ll continue to demonstrate in class. This allowed us, for example to simplify the number of products for the 2:1 MUX from four products down to only two products.

Finally, we are now seeing in class how integers can be coded as 0s and 1s. This means that integer operations, things like addition or multiplication, and integer comparisons can also be reduced to logical expressions. Several of the exercises below rely on reasoning about the binary encoding of integers, and reasoning about their bits.

You should already have downloaded a copy of LogiSim which allows you to draw digital circuit diagrams and test their circuit’s logic and behavior. In this folder we’ve placed several LogiSim files (ending in .circ) that can be used as the starting points for these exercises. Modify them as specified and submit them through Git.

Exercise 1: a 2:4 decoder

A decoder circuit takes n inputs and produces 2^n outputs. For example, there are 1:2, 2:4, 3:8, etc decoder circuits. A decoder takes an n-bit binary code as input. It’s 2^n output lines are labelled with each possible n-bit binary code. When fed an input code, exactly one of those outputs is 1—namely, the one with that code—and all the other outputs are 0.

For example, a 3:8 decoder would have outputs labelled o000, o001, o010, o011, o100, o101, o110, o111. It would have the 3 input lines i2:i1:i0. If the inputs are set as 0:1:1, then o011 will output 1. The rest output 0. If instead the inputs are set as 1:0:0 then o100 outputs 1.

Build a circuit for the 2:4 decoder using only AND, OR, and NOT gates. You’ll need to develop a boolean expression for each of the 4 outputs. Hint: you won’t need any OR gates in this circuit if you apply the truth table method outlined above. Each “sum of products” will just be a single product term.

Exercise 2. comparison

Consider the comparison of two integers x and y encoded in binary with 3 bits as bits x2:x1:x0 and y1:y1:y0. Build a circuit that outputs a 1 when x is less than y, and 0 otherwise. You probably don’t want to write out a full truth table for this circuit. Instead, think about how, when reading you the bits of each input from left to right you can identify the moment when you realize that one value is smaller than the other. This is called lexicographic ordering and is similar to how we compare two alphabetic strings for their dictionary order.

Mimic this left-to-right lexicographic comparison when you build the circuit’s logic.

If you get stuck figuring out the logic, instead try to build the circuit for 2-bit inputs and see what’s at play. Or even just compare 1-bit inputs. What is the condition on the bits that make the one number less than the other?

Exercise 3. 3-bit Gray sequence logic

A Gray sequence is a circular sequence of all the binary codes of the same length, where each successive code differs by exactly one bit. For example, the periodic sequence 00, 01, 11, 10, 00, 01, 11, 10, 00, etc. shows a 2-bit Gray code that repeats every four codes. The successive 00 and 01 codes differ in their right bit, 01 and 11 differ by their left bit, 11 and 10 differ by their right bit, and so on. The cycle of codes hits every possible 2-bit code, but in this special order. A single bit is flipped with each successive code.

Note that the sequence 000, 001, 011, 010, 110, 111, 101, 100 gives a 3-bit Gray code. After 100 we just repeat the sequence again. Again, all eight possible codes are listed, and each successive code differs by only one bit.

Just below this paragraph is a table of the “next codes” for this particular Gray code. For example, in the row where prev2:prev1:prev0 is 1:0:1, the output columns have next2:next1:next0 set to1:0:0. This is because code 100 follows code 101 in the sequence.

   prev2 prev1 prev0 | next2 next1 next0
---------------------+--------------------------
     0     0     0   |   0     0     1
     0     0     1   |   0     1     1   
     0     1     0   |   1     1     0
     0     1     1   |   0     1     0
     1     0     0   |   0     0     0
     1     0     1   |   1     0     0
     1     1     0   |   1     1     1
     1     1     1   |   1     0     1

Build a 3-input, 3-output circuit for this table.