CSE370 Assignment 4 - Sample Solutions

Problem 1. Katz 4.2. [8 pts]

We need to implement seven functions, C0 through C6, with four inputs, A, B, C, D. To implement then on a P16H8 chip, do the following:

To obtain C0, for example, connect fuses 32, 68, 76, 104, 133, 141. Note that since we have plenty of gates on the PAL chip, there is no need to factor common subexpressions or reduce the total number of products used.

Problem 2. Katz 4.15. Implement F' instead. [truth table: 4 pts; implementations: 4*4 pts]

First off, find F' as follows: 

F' = (A'BC+AD+AC)'                de Morgan's
   = (A+B'+C')*(A'+D')*(A'+C')    distributivity
   = (A+B'+C')*(A'+C'D')          distributivity etc.
   = A'B'+A'C'+C'D'
Build the truth table, correspondingly: 
  A  B  C  D  |  F'
 -------------------
  0  0  0  0  |  1
  0  0  0  1  |  1
  0  0  1  0  |  1
  0  0  1  1  |  1
              |
  0  1  0  0  |  1
  0  1  0  1  |  1
  0  1  1  0  |  0
  0  1  1  1  |  0
              |
  1  0  0  0  |  1
  1  0  0  1  |  0
  1  0  1  0  |  0
  1  0  1  1  |  0
              |
  1  1  0  0  |  1
  1  1  0  1  |  0
  1  1  1  0  |  0
  1  1  1  1  |  0
This function can be implemented as follows:

2a 2b

2d

To implement as ROM (2c), just store the values of F' from the truth table in the 16 ROM words.

Problem 3. Show there are at least 6 different 3-bit Gray code sequences that start from 000. Implement a circuit that has 6 inputs ABCDEF and an output GHJ. Output GHJ = NextGrayCodeSequence(ABC, DEF) where DEF is the selector for one for the six different Gray code sequences. Use 3-bit Gray code blocks equal to the one created in Assigment 3. [6 sequences: 5 pts; circuit: 10 pts; elegant implementation: bonus 2 pts]

We start with a 3-bit Gray code sequence like the one used in Assigment 3 (ignoring the 4th bit): 000, 001, 011, 010, 110, 111, 101, 100. We will call this sequence the original sequence. The 6 different sequences can be obtained by 6 different permutations of the bits of the original sequence. Naming the 3 bits X,Y,Z, the original Gray code sequence contains bits in order XYZ. The 5 other permutations are XZY, YXZ, YZX, ZXY, ZYX. The sequence corresponding to the permutation ZXY, for example, will be: 000, 100, 101, 001, 011, 111, 110, 010. It is easy to check that the six sequences are indeed different.

To implement the NextGrayCodeSequence function, we follow this approach and make the inputs D, E, F choose one of the above six permutations. We also engage a logic block, SimpleNextGrayCode, which computes the next element of the original sequence. This logic block is similar to the one built in Assignment 3.

Then we follow these steps:

Note that if permutation happens only once, the results will be incorrect.

NextGrayCodeSequence() can be implemented as follows:

Problem 4. Katz 4.27.

4a. [7*2 pts]
C0 = AD' + AB'C' + A'C + A'BD + BC + B'D'
C1 = A'B' + AC'D + A'CD + A'C'D' + B'D'
C2 = AB' + A'B + A'C' + A'D + C'D
C3 = AD' + BC'D + B'C + B'D' + CD'
C4 = AB + AC + B'D' + CD'
C5 = ACD + AB'D + A'BC' + BD' + C'D'
C6 = AB' + AD + A'BC' + B'C + CD'

4b. [10 pts]
Implementation as PLA is straightforward. (We are not asked to optimize for the smallest number of gates etc.) Notice that there are more than 16 distinct products altogether in C0...C6. For this reason, implementing this as ROM or with multiplexers may produce a smaller (but not necessarily faster) circuit.

Problem 6. Katz 5.17. [16 pts]

First, a comment on carry-in and carry-out. In this problem we implement a 1-bit slice of an ALU. This means that multiple such slices will then be put together to form a complete ALU. (For example, 16 slices for a 16-bit ALU.) Therefore, to implement the operation A-B (in 2s complement) and A+1, the carry-in of the very first slice will be connected to 1 for those two operations and to 0 for all the other operations. For all the other slices, the carry-in will come directly from the carry-out of the previous slice. (In other words, there is no need to manipulate the carry-in and carry-out - they are directly input and output of the ALU slice.) The situation is similar to that in Katz Figure 5.8 (Page 250).

The circuit implementation below takes as inputs A, B, Cin, S0, S1, S2, M, and returns as outputs Fi, Cout.

Problem 7. Exactly as one can define a real variable by an equation which needs to be solved for the given variable (for example 2x^2 + x - 2 = 0), one can also define a boolean function by giving an equation which needs to be solved for the unknown boolean function. For example, if S and T are given boolean expressions, one might define the boolean function f by requiring that S * f = T. Note that, exactly as in the real number case, there might be more than one distinct boolean function f that solves the equation (two functions are said to be distinct if one cannot be derived from the other using Boolean algebra; alternatively, if they have different truth tables).
Let R and S be 3-input functions that you have defined and that are distinct from the functions given in last quarters Assignment 4. Show how to derive all possible boolean functions f1...fn that satisfy the equation R * f = S. [8 pts]

Imagine we built a (single) truth table with columns for R and S, and we are going to add to it another column for f. When choosing the value for f in a given row of the truth table, we only need to consult the values for R and S in that same row, regardless of values of their inputs. Therefore we have the following four cases to consider:

Therefore if the truth table has a line where R=0 and S=1, the equation has no solutions. Otherwise all solutions of the equation can be built by all possible ways of assigning 0s and 1s to f in those lines of the truth table where R=S=0. (Clearly if the truth table has no such lines, the solution is unique.)

Here is an example, where the column for f shows the general form of a solution, and f1...f4 are the particular solutions. (This assumes that there are no lines with R=0 and S=1.) 

  A  B  C  |  R  |  S  |  f     |  f1 f2 f3 f4
 ----------------------------------------------
  0  0  0  |  1  |  0  |   0    |   0  0  0  0 
  0  0  1  |  0  |  0  | 0 or 1 |   0  1  0  1 
  0  1  0  |  1  |  1  |   1    |   1  1  1  1 
  0  1  1  |  0  |  0  | 0 or 1 |   0  0  1  1 
           |     |     |        |              
  . . . .  | . . | . . |  . . . |   . . . .

Problem 8. Construct a schematic diagram for the functions that appear on slide #23 of the Combinational Logic lectures.  Assign a delay of 1 to inverters, 2 to 2-inputs AND and OR gates, 4 to 3-input AND and OR gates, and 6 to XOR gates.  Use the DesignWorks simulator to create waveforms similar to those on slide #26.  Turn in a printout of the waveforms and explain why the waveforms have the shape they have and why they differ from those on slide #26. [schematic: 5 pts; waveforms: 5 pts; explanation: 3 pts]

Here are the circuits:

Here are the timings:

Out1, Out2, and Out3 represent three different representations of the same function. Different components of the circuit are assigned different delays as given in the problem statement. This results in the difference in their waveforms even though they implement the same boolean function.  We note that there are glitches when the signals a,b,c swap from 1,0,1 to 1,1,0. This is because of the inverters, which delay the signal change for a unit time, which results in a glitch in the signals.  The waveforms are different from those on the notes, and this is because the gate delays assigned are different from those assumed in the notes.

Comments to: cse370-webmaster@cs.washington.edu (Last Update: )