Description
Problem 9.1: JK flip-flops (1+1+1+1 = 4 points)
JK flip-flops, also colloquially known as jump/kill flip-flops, augment the behaviour of SR flip-flops.
The letters J and K were presumably picked by Eldred Nelson in a patent application.
The sequential digital circuit shown below shows the design of a JK flip-flop based on two SR
NAND latches. Assume the circuit’s output is Q = 0 and that the inputs are J = 0 and K = 0,
and that the clock input is C = 0. (You can make use of the fact that we already know how an SR
NAND latch behaves.)
Q
Q
J
K
C
a) Suppose J transitions to 1 and C transitions to 1 soon after. Create a copy of the drawing and
indicate for each line whether it carries a 0 or a 1.
b) Some time later, C transitions back to 0 and soon after J transitions to 0 as well. Create another
copy of the drawing and indicate for each line whether it carries a 0 or a 1.
c) Some time later, J and K both transition to 1 and C transitions to 1 soon after. Create another
copy of the drawing and indicate for each line whether it carries a 0 or a 1.
d) Finally, C transitions back to 0 and soon after J and K both transition to 0 as well. Create
another copy of the drawing and indicate for each line whether it carries a 0 or a 1.
Problem 9.2: ripple counter using d flip-flops (2+1 = 3 points)
The following circuit shows a 3-bit ripple counter consisting of three positive edge triggered D
flip-flops and a negation gate on the clock input C.
D Q
Q
D Q
Q
D Q
Q
Q0 Q1 Q2
C
a) Complete the following timing diagram. Assume that gate delays are very short compared to
the speed of the clock signal (i.e., you can ignore the impact of gate delays).
0 1 2 3 4 5 6 7 8 9 10 11 12 13
C
C
Q0
Q0
Q1
Q1
Q2
Q2
b) Can you make ripple counters arbitrary “long” or is there a limit on the number of D flip flops
that can be chained? Explain.
Problem 9.3: integer expression simplification (haskell) (2+1 = 3 points)
Our goal is to simplify integer expressions that may include constants and variables and which are
constructed using a sum and a product operator. For example, we want to write an program that
can simplify (2·y)·(3+ (2·2)) to 14·y. We can represent expressions in Haskell using the following
data type:
1 data Exp = C Int — a constant integer
2 | V String — a variable with a name
3 | S Exp Exp — a sum of two expressions
4 | P Exp Exp — a product of two expressions
5 deriving (Show, Eq)
We use the following rules to simplify expressions:
S1 Adding two constants a and b yields a constant, which has the value a + b, e.g., 3 + 5 = 8.
S2 Adding 0 to a variable yields the variable, i.e., 0 + x = x and x + 0 = x.
S3 Adding a constant a to a sum consisting of a constant b and a variable yields the sum of the
a + b and the variable, e.g., 3 + (5 + y) = 8 + y.
P1 Multiplying two constants a and b yields a constant, which as the value a · b, e.g., 3 · 5 = 15.
P2 Multiplying a variable with 1 yields the variable, i.e., 1 · y = y and y · 1 = y.
P3 Multiplying a variable with 0 yields the constant 0, i.e., 0 · y = 0 and y · 0 = 0.
P4 Multiplying a constant a with a product consisting of a constant b and a variable yields the
product of a · b and the variable, e.g., 3 · (2 · y) = 6 · y.
The usual associativity rules apply. Note that we have left out distributivity rules.
a) Implement a function simplify :: Expr -> Expr, which simplifies expressions that do not
contain variables. In other words, simplify returns the (constant) value of an expression that
does not contain any variables.
b) Extend the function simplify to handle variables as described above.
Submit your Haskell code plus an explanation (in Haskell comments) as a plain text file. Below is
a template providing a collection of test cases.
1 module Main (main) where
2
3 import Test.HUnit
4
5 data Exp = C Int — a constant integer
6 | V String — a variable with a name
7 | S Exp Exp — a sum of two expressions
8 | P Exp Exp — a product of two expressions
9 deriving (Show, Eq)
10
11 simplify :: Exp -> Exp
12 simplify _ = undefined
13
14 tI0 = TestList
15 [ simplify (C 3) ~?= C 3 — 3 = 3
16 , simplify (V “y”) ~?= V “y” — y = y
17 ]
18
19 tS1 = TestList
20 [ simplify (S (C 3) (C 5)) ~?= C 8 — 3 + 5 = 8
21 ]
22
23 tS2 = TestList
24 [ simplify (S (C 0) (V “y”)) ~?= V “y” — 0 + y = y
25 , simplify (S (V “y”) (C 0)) ~?= V “y” — y + 0 = y
26 ]
27
28 tS3 = TestList
29 [ simplify (S (S (C 3) (V “y”)) (C 5)) ~?= S (C 8) (V “y”) — (3 + y) + 5) = 8 + y
30 , simplify (S (S (V “y”) (C 3) ) (C 5)) ~?= S (C 8) (V “y”) — (y + 3) + 5) = 8 + y
31 , simplify (S (C 3) (S (C 5) (V “y”))) ~?= S (C 8) (V “y”) — 3 + (5 + y) = 8 + y
32 , simplify (S (C 3) (S (V “y”) (C 5))) ~?= S (C 8) (V “y”) — 3 + (y + 5) = 8 + y
33 ]
34
35 tS4 = TestList
36 [ simplify (S (S (C 3) (C 5)) (C 8)) ~?= C 16 — (3 + 5) + 8 = 16
37 , simplify (S (C 3) (S (C 5) (C 8))) ~?= C 16 — 3 + (5 + 8) = 16
38 , simplify (S (C 5) (V “y”)) ~?= S (C 5) (V “y”) — 5 + y = 5 + y
39 , simplify (S (V “y”) (C 5)) ~?= S (V “y”) (C 5) — y + 5 = y + 5
40 , simplify (S (V “x”) (V “y”)) ~?= S (V “x”) (V “y”) — x + y = x + y
41 ]
42
43 tP1 = TestList
44 [ simplify (P (C 3) (C 5)) ~?= C 15 — 3 * 5 = 15
45 ]
46
47 tP2 = TestList
48 [ simplify (P (C 1) (V “y”)) ~?= V “y” — 1 * y = y
49 , simplify (P (V “y”) (C 1)) ~?= V “y” — y * 1 = y
50 ]
51
52 tP3 = TestList
53 [ simplify (P (C 0) (V “y”)) ~?= C 0 — 0 * y = 0
54 , simplify (P (V “y”) (C 0)) ~?= C 0 — y * 0 = 0
55 ]
56
57 tP4 = TestList
58 [ simplify (P (P (C 3) (V “y”)) (C 2)) ~?= P (C 6) (V “y”) — (3 * y) * 2) = 6 * y
59 , simplify (P (P (V “y”) (C 3) ) (C 2)) ~?= P (C 6) (V “y”) — (y * 3) * 2) = 6 * y
60 , simplify (P (C 3) (P (C 2) (V “y”))) ~?= P (C 6) (V “y”) — 3 * (2 * y) = 6 * y
61 , simplify (P (C 3) (P (V “y”) (C 2))) ~?= P (C 6) (V “y”) — 3 * (y * 2) = 6 * y
62 ]
63
64 tP5 = TestList
65 [ simplify (P (P (C 3) (C 5)) (C 8)) ~?= C 120 — (3 * 5) * 8 = 120
66 , simplify (P (C 3) (P (C 5) (C 8))) ~?= C 120 — 3 * (5 * 8) = 120
67 , simplify (P (C 5) (V “y”)) ~?= P (C 5) (V “y”) — 5 * y = 5 * y
68 , simplify (P (V “y”) (C 5)) ~?= P (V “y”) (C 5) — y * 5 = y * 5
69 , simplify (P (V “x”) (V “y”)) ~?= P (V “x”) (V “y”) — x * y = x * y
70 ]
71
72 tM0 = TestList [
73 — (2 * y) * (3 + (2 * 2)) = 14 * y
74 simplify (P (P (C 2) (V “y”)) (S (C 3) (P (C 2) (C 2)))) ~?= P (C 14) (V “y”)
75 — x + (1 + -1) = x
76 , simplify (S (V “x”) (S (C 1) (C (-1)))) ~?= V “x”
77 — (1 + -1) * x = 0
78 , simplify (P (S (C 1) (C (-1))) (V “x”)) ~?= C 0
79 — (2 + -1) * x = x
80 , simplify (P (S (C 2) (C (-1))) (V “x”)) ~?= V “x”
81 — (2 * 2) * (3 + 4) = 28
82 , simplify (P (P (C 2) (C 2)) (S (C 3) (C 4))) ~?= C 28
83 ]
84
85 main = runTestTT $ TestList [tI0, tS1, tS2, tS3, tS4, tP1, tP2, tP3, tP4, tP5, tM0 ]