Finite State Machines

When entering numeric values in the answer fields, you can use integers (1000, 0x3E8, 0b1111101000), floating-point numbers (1000.0), scientific notation (1e3), engineering scale factors (1K), or numeric expressions (3*300 + 100).

Problem 1. FSMs

A possible implementation of a finite state machine with two inputs and one output is shown below.

  1. If the register is 5 bits wide (i.e., k = 5) what is the appropriate size of the ROM? Give the number of locations and the number of bits in each location.

  2. If the register is 5 bits wide what is the maximum number of states in an FSM implemented using this circuit?

  3. What is the smallest possible value for the ROM's contamination delay that still ensures the necessary timing specifications are met? ±5%

  4. Assume that the ROM's \(t_{\textrm{CD}} = 3\textrm{ns}\). What is the shortest possible clock period that still ensures that the necessary timing specifications are met? ±5%

Problem 2. State Transition Diagram

Shown below is a state transition diagram for an FSM, F, with a single binary input B. The FSM has a single output, a light which is on for the three states marked by a gray dot. The starting state is marked by the heavy circle.

  1. Is there a synchronizing sequence of inputs which will return this FSM from an unknown state to its starting state? 00010 is such a sequence 01010 is such a sequence 00000 is such a sequence 11101 is such a sequence No such sequence exists

  2. Does this FSM have a pair of equivalent states that may be merged to yield a 3-state FSM? Yes; the two middle states (upper and lower) are equivalent. Yes; the lower and rightmost states are equivalent. Yes; the leftmost and rightmost states are equivalent. No two states are equivalent; this FSM cannot be reduced.

  3. The following circuit is used to implement the above 4-state FSM:

    It is known that the starting state of the 4-state FSM corresponds to 00 on the state variable input, and the light output is 1 when the light is to be on. What is the value of the light output when all three inputs to the ROM are zero? 0 (light off) 1 (light on) Cannot tell from information given

  4. Fill in the unspecified rows of the following truth table so that it implements the state transition diagram. You will need to enter some combination of three zeros or ones in each field. Other characters in the fields (e.g., spaces) will be ignored. Remember the starting state is 00.

    S1 S0  B
    S1' S0' light
     0  0  0
     0  0  1
     0  1  0
     1   1   1
     0  1  1
     0   0   1
     1  0  0
     1  0  1
     1  1  0
     1  1  1

Problem 3. Design problem: Well-formed parenthesis string checker

In 1936 Alan Turing described the "a-machine", a device that performed computations on a string of symbols according to a simple set of manipulation rules enumerated in the form of a finite-state machine (FSM). The machine consisted of

We now refer to this device as a Turing Machine (TM) and use it as our definition for what it means to be computable, i.e., we believe (Church's Thesis) that a function is algorithmically computable if and only if it's computable by a TM.

The goal of this lab is write the FSM controller for a TM that checks to see if the string of left and right parentheses it finds on its input tape "balance".

The TM has a doubly-infinite tape with discrete symbol positions (cells) each of which contains one of a finite set of symbols. The control FSM has one input: the symbol found in the current cell. The FSM produces several outputs: the symbol to be written into the current cell and a motion control that determines how the head should move. In our simulation, the tape is displayed horizontally, so the tape can move left, right, or stay where it is.

The operation of the TM is specified by a file containing one or more of the following statements:

// comment

/* ... */

symbols symbol...

states state...

action state symbol newstate writesymbol motion

tape name symbol...

result name symbol...

result1 name symbol

Here's an example file that defines a control FSM with three states (s1, s2 and s3) and two possible tape symbols: "1" and "-" (recall that the "-" symbol is predefined). There is a single tape configuration defined called "test" which consists of a blank tape. The final tape configuration is expected to be a tape containing six consecutive "1" symbols with the head positioned over the second "1". Note that there is an action declared for each possible combination of the three states and two tape symbols.

// 3-state busy beaver Turing Machine example

// See how many 1's we can write on a blank tape using
// only a three-state Turing Machine

states s1 s2 s3  // list of state names, first is starting state
symbols 1        // list of symbols (- is blank cell)

tape test -      // initial tape contents, blank in this case
result test 1 [1] 1 1 1 1 // expected result

// specify transistions: action state symbol state' write move
//    state = the current state of the FSM
//    symbol = the symbol read from the current cell
//    state' = state on the next cycle 
//    write = symbol to be written into the current cell
//    move = tape movement ("l"=left, "r"=right, "-"=stay put)
action s1 - s2     1 r
action s1 1 s3     1 l
action s2 - s1     1 l
action s2 1 s2     1 r
action s3 - s2     1 l
action s3 1 *halt* 1 r

You'll find an instance of TMSim, our TM simulator, at the bottom of this webpage. Here's what the TM simulator looks like:

The TM display consists of the following parts:

Well-formed parenthesis string checker

Your task is to write the control FSM for a TM that determines if the parenthesis string on its input tape is balanced. The initial position of the head will be at the leftmost non-blank symbol on the tape, i.e., at the left end of the parenthesis string. Your TM should halt with a current symbol of "1" if the parens balance, or a current symbol of "0" if the parens don't balance. The head should be positioned over the "0" or "1" on the tape. Note that there are no constraints on what the rest of the tape contains.

NOTE: TMs that simply use some fixed number of states to count the number of unmatched open parentheses would not be able handle an arbitrary-length inputs and so do not qualify as acceptable solutions. The staff will check this constraint during the check-off meeting.

Use the TMSim simulator below to enter your design in the "Paren Checker" tab. The initial contents of the tab are a sequence of test tapes which must be processed successfully by your TM. To run the tests, click "TMSim Assemble" and then "Checkoff". If all the tests pass, then clicking will give you credit for completing this problem. Please see the note on scoring at the end of this problem.

Note that you're welcome to add your own test tapes while debugging your implementation, but you'll need to comment them out before running the checkoff tests (otherwise the checksum mechanism will get confused).

Scoring: The number of points you'll receive at the Check-off meeting is determined by the number of states in your TM definition:

"Counting" solutions do not receive any credit.

Problem 4. Design problem: Sequential Logic

Your task is to design a sequential logic circuit that implements the FSM shown in the state transition diagram below:

The sequential circuit has three inputs:

In the test, the values of IN and RESET are provided 10ns before the rising edge of CLK, which should provide sufficient time for them to processed by logic or a ROM and influence the value for the next state.

The values of the two outputs, U and V, are determined by the current state and are as shown in the state transition diagram.

The details of the implementation are up to you. Of course, you'll need some number D registers to hold the current state. The next-state and output logic could be logic gates (see L06 slides 23 and 24) or our "standard" ROM plus register setup (see L06 slide 11).

The steps you'll need to follow to complete the design are outlined on slides 8 and 9 of L06. See the diagram on slide 11 of L06 for one way to handle setting an initial state during reset.

The Memory component can be used to build a read-only memory (ROM). You can insert a memory component into your schematic by clicking on the "MEM" icon in the schematic tab and dragging it onto the schematic. Double-click the memory component to change its properties. Please the see documentation for the Memory component at the end of the Standard Cell Library datasheet.

To build a ROM, set the memory component to have a single port with the desired number of address inputs and data outputs. Connect its CLK and WE inputs to 0'1, which will disable the ability to write into the memory, making it read-only. And connect its OE input to 1'1 which will enable the D outputs:

As described in the datasheet, you can edit the "Contents" property to specify the contents of each memory location. For example, to fill the first 4 locations of a 4-bit-wide ROM to the binary values 0000, 0101, 1010, and 1111, you could enter the following into the Contents property:
// comments are allowed, don't count as content lines
// 1 line per ROM location, starting at address 0
0b0000  // binary value
5       // decimal value
0xA     // hexadecimal value
0b1_111 // binary value, _ is ignored (useful for formatting)

Use the Jade instance below to enter your design. To complete this design problem, select the /fsm/fsm module and click in the Jade toolbar and the built-in tester will either report any discrepancies between the expected and actual outputs, or, if your design is correct, it will record the test passed.

The tests verify that all the state transitions are correct by checking the values of U and V while the circuit is processing a sequence of IN values. You can select the "Test" tab for the /fsm/fsm to see the input sequence and the expected values of U and V at each clock cycle. The IN is changed before the rising edge of the clock and the values of U and V are checked just after the rising clock edge (i.e., after the most-recent value of IN has been processed). There are comments on each test line indicating what the state of the FSM should be after processing the new IN value. { "hierarchical": "true", "parts": ["memory", "/gates/.*","/fsm/.*","/user/.*"], "tools": ["check"], "editors": ["schematic","icon","test"], "edit": "/fsm/fsm", "initial_state": { "/fsm/fsm" : {"test": [["test", ".power Vdd=1\n.thresholds Vol=0 Vil=0.1 Vih=0.9 Voh=1\n\ inputs RESET IN\ outputs U V\n.mode gate\n\n.cycle CLK=0 assert inputs tran 10n CLK=1 tran 20n CLK=0 tran 5n sample outputs tran 5n\n\n1 0 LH // 1. now in SA\n0 0 LH // 2. now in SA\n0 1 LL // 3. now in SB\n0 0 LL // 4. now in SD\n0 1 HL // 5. now in SF\n0 1 HL // 6. now in SF\n0 0 LH // 7. now in SA\n0 1 LL // 8. now in SB\n0 1 HH // 9. now in SC\n0 0 LL // 10. now in SD\n0 0 LL // 11. now in SE\n0 1 HH // 12. now in SC\n0 1 LL // 13. now in SE\n0 0 HL // 14. now in SF\n0 0 LH // 15. now in SA\n\n// now test that RESET always returns us SA\n1 0 LH // 16. now in SA (reset asserted)\n0 1 LL // 17. now in SB\n1 0 LH // 18. now in SA (reset asserted)\n0 1 LL // 19. now in SB\n0 1 HH // 20. now in SC\n1 0 LH // 21. now in SA (reset asserted)\n0 1 LL // 22. now in SB\n0 0 LL // 23. now in SD\n1 0 LH // 24. now in SA (reset asserted)\n0 1 LL // 25. now in SB\n0 0 LL // 26. now in SD\n0 1 HL // 27. now in SF\n1 0 LH // 28. now in SA (reset asserted)\n0 1 LL // 29. now in SB\n0 0 LL // 30. now in SD\n0 0 LL // 31. now in SE\n1 0 LH // 32. now in SA (reset asserted)\n\n// test RESET again this time with IN=1 on reset cycles\n1 1 LH // 33. now in SA (reset asserted)\n0 1 LL // 34. now in SB\n1 1 LH // 35. now in SA (reset asserted)\n0 1 LL // 36. now in SB\n0 1 HH // 37. now in SC\n1 1 LH // 38. now in SA (reset asserted)\n0 1 LL // 39. now in SB\n0 0 LL // 40. now in SD\n1 1 LH // 41. now in SA (reset asserted)\n0 1 LL // 42. now in SB\n0 0 LL // 43. now in SD\n0 1 HL // 44. now in SF\n1 1 LH // 45. now in SA (reset asserted)\n0 1 LL // 46. now in SB\n0 0 LL // 47. now in SD\n0 0 LL // 48. now in SE\n1 1 LH // 49. now in SA (reset asserted)\n\n.plot CLK\n.plot RESET\n.plot IN\n.plot U\n.plot V\n"]], "properties": {"test-readonly": "true","name":{"edit":"yes","type":"name","value":"","label":"Name"}, "name": {"edit": "yes", "type": "name", "value": "", "label": "Name"}}, "schematic": [["port", [-16, -64, 0], {"signal": "CLK"}], ["port", [-16, -80, 0], {"signal": "RESET"}], ["port", [-16, -96, 0], {"signal": "IN"}], ["port", [16, -96, 4], {"signal": "U", "direction": "out"}], ["port", [16, -80, 4], {"signal": "V", "direction": "out"}]]} }}