CS251 Winter 2015
Assignment 01
Due Wednesday January 21 st 1pm
35 Total Marks
Print these pages and write your solutions in the space provided. Staple your solutions
to the assignment cover sheet from the course webpage (with the cover sheet first) and
deposit your assignment in the drop-box outside MC4065. You will receive a 0 on the
assignment if you do not include the cover page.
1. (8 points) For 4 inputs A, B, C, D, fill in the truth table for the function F that is 1
when the binary number ABCD is a digit in your student id. For example, if your
student number was 20340259, the lines 0000, 0010, 0011, 0100, 0101, and 1001
should be 1, while the other entries should be 0.
Solution depends on student number.
Your Student number ____________________
(2 points)
A
0
0
0
0
0
0
0
0
B
0
0
0
0
1
1
1
1
C
0
0
1
1
0
0
1
1
D
0
1
0
1
0
1
0
1
F
A
1
1
1
1
1
1
1
1
B
0
0
0
0
1
1
1
1
C
0
0
1
1
0
0
1
1
D
0
1
0
1
0
1
0
1
F
a) (2 points) Sum of Products Notation:
F=
b) (1 point) Simplified form of F: (if F cannot be simplified state that it cannot be
simplified further)
F=
c) (3 points) Circuit implementing F from part(a)
2. (4 points)
Complete the table below for the following CMOS circuit. The entries for Q1 and Q2
should be HIGH or LOW, while the entries for F should be 0 or 1.
3. (3 points) Complete the truth table table for G and H in the following circuit, giving the
truth table values for the internal signals D, E, and F as an intermediate step.
A
0
0
0
0
1
1
1
1
B
0
0
1
1
0
0
1
1
C
0
1
0
1
0
1
0
1
D
E
F
G
H
4.(5 points) Draw the circuit that will implement a 6×1 Multiplexor. Be sure to label all
inputs D 0, to D5. Also label output and select lines and their respective inverses. You
may insert an extra page here if you need more room.
5. Finite State Machine (11 points)
(a) (5 points)
Consider the following finite state machine:
Fill in the next-state table and the output table with 0s, 1s.
(b) (3 points)
Give the Boolean formulas for each state variable in minterm (unreduced) form.
S2=
S1=
S0=
(c) (3 points)
Complete the table below tracing the above finite state machine on a particular
sequence of input bits. Note that the Next State of one column is the State for
the next column. We have done the first step for you.
State
A
B
Next State
000
0
0
001
001
1
0
1
0
0
1
1
0
6. (4 points) Examine the D flip flop below:
In the figure below are traces of the D and C inputs to this latch. Draw in the traces
of the signals QI and QE.
The following are a few OPTIONAL exercises to help improve your understanding
of the material: You do NOT need to submit these for marking. Solutions will not
be provided.
1. Exercises from the textbook: B.7, B.8, B.11, B.13 (ignore the hierarchical part), B.14,
B.17, B.37, B.38. (Computer Organization and Design by Hennessy and Patterson)
2. Below is a 4-1 multiplexor with its select lines tied to A and B. Suppose we want to
implement the following function using this multiplexor:
A
0
0
0
0
1
1
1
1
B
0
0
1
1
0
0
1
1
C
0
1
0
1
0
1
0
1
F
0
0
0
1
1
0
1
1
Label the inputs D0, D1, D2, and D3 so that the output Q is as given by the truth table
and the select lines.
3. A binary Encoder works the opposite of a decoder. It performs the inverse of the
decoder, having 2n inputs and n outputs. In a simple binary encoder, only one input line
may be asserted at any time. The output lines are the binary representation of the
input.Therefore if D0 is 1, the outputs on both Q0 and Q1 will be 0.
Fill in the rest of the truth table and implement the internal circuit for a 4×2 Encoder. In
the case where all of the inputs to the encoder are 0, we do not care about the outputs.
D3
D2
D1
D0
0
0
0
0
1
0
0
0
1
0
0
0
1
0
0
0
1
0
0
0
Q0
Q1