ICS - Sheet9 -Solved

Introduction to Computer Science

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.)

 

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.

 

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).

 

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 ]