## Description

## CH-232 Problem Sheet 9

## 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 ]