CS251 Winter 2015 Assignment 01-computer science

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