HW #5 Solutions
CSEE W3827 – Fundamentals of Computer Systems Spring 2018
Warmup Problems
1. Build
(a) a T flip-flop out of a D flip-flop and combinational circuitry.
(b) a D flip-flop out of a T flip-flop and combinational circuitry.
Prof. Rubenstein
(a) T flip-flop from D flip-flop (b) D flip-flop from T flip-flop
2. Build a sequential circuit that returns 1 whenever the last 3 inputs (including the current input) were identical.
OUT
IN
CLK
DQ
DQ
3. Build a sequential circuit that returns 1 whenever the last 3 inputs (prior to the current input) were identical.
OUT
IN
CLK
DQ
DQ
DQ
1
4. Draw a state machine that returns 1 whenever the last 4 inputs (including the current input) were identical. This can be done with 6 states.
0/1
03
1/0
11
0/0
1/0
1/0
02 1/0
0/0
12
0/0
0/0
1/0
01
0/0
13 1/1
Harder Problems
1. (11 pts) A special flip-flop is formed from three latches, arranged in sequence. The first two latches behave as in a normal flip-flop: the master latchs enable is attached to the clock, and the slaves enable is attached to the complement of the clock. The third latch, which follows the slave, is also attached to the clock. Whats different about the outputs of this flip-flop?
Answer: A normal, 2-latch flip flop reads its input during the up-pulse (or down edge) and changes its output on the down pulse (or up-edge). This one delays the output for another half cycle, so that the output changes at the same time the new input is ”locked” into the master latch.
2. (30 pts) Design a circuit using J K flip-flops that takes in a binary streamB0 B1 B2 B3 · · · and outputs a 1 at time t if the stream received thusfar (i.e., B0 B1 · · · Bt−1 Bt ), when read as an unsigned binary number from low bit to high, is divisible by 3.
The following table depicts a sample input stream and what should be output.
Hint: Thevalueofthenewbitstartsasequalto1whichis1mod3,thenis2whichis2mod3,thenis4which is back to 1 mod 3, etc.
(a) (15 pts) Draw the state machine, numbering your states in an “obvious” manner. You may assume that the machine starts in the right state at time t = 0.
t
0
1
2
3
4
5
6
7
8
I n(t)
0
0
1
1
0
0
1
0
0
Val of input
0
0
4
12
12
12
76
76
76
val mod 3
0
0
1
0
0
0
1
1
1
output
1
1
0
1
1
1
0
0
0
2
01 11 21
0/1
0/1
1/0
0/0
0/0
1/1
1/0
0/0
0/0
1/0
02 12 22
1/0 1/1
(b) (15 pts) Give the algebraic formula (simplified as much as possible) for the J and K inputs of your flip- flops, and also for the output.
Current
A B C In A’ B’ C’ Out Ja Ka Jb Kb Jc Kc
Next Excitation Table
0
100
1
1
101
0
0
101
0
1
110
0
0
110
0
1
100
1
0
000
1
1
111
0
0
001
0
1
000
1
0
010
0
000 001 010 100 101 110
1X0X0X 1X0X1X 1X0XX0 1X1XX1 1XX00X 1XX10X X10X0X X11X1X
X10XX0 X10XX1 X1X00X
10100X1X00X
3
AB
CIn CIn CIn 00 01 11 10 AB 00 01 11 10 AB
00 00 00 01 01 01 11 11 11 10 10 10
00 01 11 10
1
1
1
1
1
1
X
X
X
X
X
X
X
X
X
X
0
0
1
0
X
X
1
0
X
X
X
X
0
0
X
X
0
1
X
X
0
0
X
X
0
0
X
X
0
1
X
X
J A = 1 CIn
CIn
J B = C I n
00 01 11 10 AB
CIn
J C = B ̄ I n
00 01 11 10
AB
00 01 11 10 AB
00 00 00 01 01 01 11 11 11 10 10 10
X
X
X
X
X
X
X
X
1
1
X
X
1
1
1
1
X
X
X
X
0
1
X
X
0
1
X
X
X
X
X
X
X
X
1
0
X
X
X
X
X
X
X
X
X
X
1
0
KA = 1
KB = In
00 01 11 10
00 01 11 10
̄ ̄ ̄ ̄ ̄ ̄ ̄ Out = ABCIn + CInB + CInA + BCIn
KC = In
CIn AB
1
0
0
0
0
1
0
1
X
X
X
X
0
1
0
0
4
3. (39pts)ConsiderasequentialcircuitthatreadsinaninputX(t)duringclockcyclet.Thecircuitshouldlookfor the sequence 011. Design the sequential circuit (i.e., give simplified algebraic expressions) using D flip-flops for each of the following versions:
(a) If the second 1 arrives during clock cycle t, then the circuit should output a 1 during clock cycle t, and otherwise outputs a 0.
Answer:
To design this state machine, there needs to be a state that indicates that a first 0 has been received, then a state that indicates that thusfar 01 has been received. When in the 01 state, if a 1 is received, the machine can output 1. Last, there must also be state that indicates that the sequence has not yet been initiated (i.e., a 1 has been received without a 0 immediately preceding it or without a 01 immediately preceding it. Since 3 states are needed, each state needs to be described by (at minimum) a 2-bit sequence, A(t)B(t). Arbitrarily, we will assign 00 to the not-yet-initiated state, 01 to the received-0 state, and 10 to the received 01 thusfar.
1/0 0/0
1/0
0/0
00 01 10 {} {0} 0/0 {01}
1/1
A(t) B(t) In(t)
Out(t)
A(t+1) B(t+1)
000 001 010 011 100 101 110 111
0 0 0 0 0 1 X X
01 00 01 10 01 00 XX XX
5
BIn
00 01 11 10
1
BIn
00 01 11 10
1
BIn
00 01 11 10
1
A
0
0
0
0
0
0
1
X
X
A
0
Out(t) = A(t)In(t)
A(t + 1) = B(t)In(t)
B(t + 1) = In(t)
0
0
1
0
0
0
X
X
A
0
1
0
0
1
1
0
X
X
6
(b) If the second 1 arrives during clock cycle t, then the circuit should output a 1 during the clock cycle t + 1, and otherwise outputs a 0.
Answer: Here, we need 4 states. One that represents the sequence not yet received at all (we will use state 00). Another for the 0 having been received (we will use state 01), another for 01 received (we will use state 11) and another for 011 received (we will use state 10).
0/0
1/0 0/0
1/0
1/0
00 01 11 10 {} {0} 0/0 {01} {011}
0/1 1/1
A(t) B(t) In(t)
Out(t)
A(t+1) B(t+1)
000 001 010 011 100 101 110 111
0 0 0 0 1 1 0 0
01 00 01 11 01 00 01 10
7
BIn
00 01 11 10
1
BIn
00 01 11 10
1
BIn
00 01 11 10
1
A
0
0
0
0
0
1
1
0
0
A
0
Out(t) = A(t)B(t)
A(t + 1) = B(t)In(t)
B(t + 1) = I(t) + A(t)B(t)
0
0
1
0
0
0
1
0
A
0
1
0
1
1
1
0
0
1
8
(c) Suppose the sequence is 111 instead of 011. If at time t, the current and two previous inputs were all 1, then a 1 should be output during clock cycle t, and otherwise a 0 should be output. Note that multiple consecutive outputs of 1 are possible.
start
0/0
1/0 0 0/0
11 0/0
1/0
0/0
12
1/1
1/1
13
B A’=DA
B’=DB Out
In 000000 100010 001000 101100 010000 110111 011000 111111
A
BIn
BIn BIn 00 01 11 10 A
A
00 01 11 10 A 000 111
00 01 11 10
Out=AIn
0
0
1
0
0
1
1
0
0
1
0
0
0
1
1
0
0
0
0
0
0
1
1
0
DA =AIn+BIn DB =AIn+B ̄In
9