Problem 1. (Katz, problem 8.13) A finite state machine has one input and one output. The output becomes 1 and remains 1 thereafter when at least two 0's and two 1's have occurred as inputs, regardless of the order of appearance.
Assume that all inputs have been externally synchronized with clk.
module fsm01(clk,reset,one,zero,out); // state assignments parameter STATE_0_0 = 0; // 0 zeroes, 0 ones parameter STATE_0_1 = 1; // 1 zero, 0 ones parameter STATE_0_2 = 2; // 2 zeroes, 0 ones parameter STATE_1_0 = 3; // 0 zeroes, 1 one parameter STATE_1_1 = 4; // 1 zero, 1 one parameter STATE_1_2 = 5; // 2 zeroes, 1 one parameter STATE_2_0 = 6; // 0 zeroes, 2 ones parameter STATE_2_1 = 7; // 1 zero, 2 ones parameter STATE_2_2 = 8; // 2 zeroes, 2 ones input clk,reset,one,zero; output out; // level-to-pulse converters for ZERO and ONE inputs reg last_one,last_zero; wire input_one,input_zero; always @ (posedge clk) begin last_one <= reset ? 0 : one; last_zero <= reset ? 0 : zero; end assign input_one = ~last_one & one; assign input_zero = ~last_zero & zero; // fsm reg [3:0] state; always @ (posedge clk) begin if (reset) state <= STATE_0_0; else case (state) STATE_0_0: state <= input_one ? STATE_1_0 : input_zero ? STATE_0_1 : state; STATE_0_1: state <= input_one ? STATE_1_1 : input_zero ? STATE_0_2 : state; STATE_0_2: state <= input_one ? STATE_1_2 : state; STATE_1_0: state <= input_one ? STATE_2_0 : input_zero ? STATE_1_1 : state; STATE_1_1: state <= input_one ? STATE_2_1 : input_zero ? STATE_1_2 : state; STATE_1_2: state <= input_one ? STATE_2_2 : state; STATE_2_0: state <= input_zero ? STATE_2_1 : state; STATE_2_1: state <= input_zero ? STATE_2_2 : state; STATE_2_2: state <= state; default: state <= STATE_0_0; // transition out of unused states endcase end // it's a Moore machine so output only depends on current state. // Note: OUT might glitch as the logic decodes the current state. assign out = (state == STATE_2_2); endmodule
Problem 2. The ACME Company has recently received an order from a Mr. Wiley E. Coyote for their all-digital Perfectly Perplexing Padlock. The P3 has two buttons ("0" and "1") that when pressed cause the FSM controlling the lock to advance to a new state. In addition to advancing the FSM, each button press is encoded on the B signal (B=0 for button "0", B=1 for button "1"). The padlock unlocks when the FSM sets the UNLOCK output signal to 1, which it does whenever the last N button presses correspond to the N-digit combination.
100
Problem 3. Construct a "divisible-by-3" FSM that accepts a binary number entered one bit at a time, most significant bit first, and indicates with a light if the number entered so far is divisible by 3.
If the value of the number entered so far is N, then after the digit b is entered, the value of the new number N' is 2N + b. Using this fact:
if N is 1 mod 3 then for some p, N = 3p + 1. After the digit b is entered, N' = 6p + 2 + b. So N' is b+2 mod 3.
if N is 2 mod 3 then for some p, N = 3p + 2. After the digit b is entered, N' = 6p + 4 + b. So N' is b+1 mod 3.
This leads to the following transition diagram where the states are labeled with the value of N mod 3.
S1 S0 b | S1' S0' light =========|============== 0 0 0 | 0 0 1 0 0 1 | 0 1 1 0 1 0 | 1 0 0 0 1 1 | 0 0 0 1 0 0 | 0 1 0 1 0 1 | 1 0 0
__ __ light = S1*S0 __ _ __ S1' = S1*S0*b + S1*S0*b __ __ __ _ S0' = S1*S0*b + S1*S0*b
Problem 4.
M has 27 states which require a total of 5 bits in the state register (not 2 + 4 bits!).
Each FSM can in theory be in one of its N states, so an upper bound on the number of states in the combined machine is NM.
Problem 5. Ben Bitdiddle has designed an electronic lock with three buttons: "reset", "0" and "1". He has provided the following state transition diagram showing how the lock responds to a sequence of inputs.
The lock makes a transition from its current state to a new state whenever one of the three buttons is pressed and released. It ignores its inputs if more than one button is pressed. Pressing "reset" returns the lock to the state marked "R" in the diagram (arcs showing the transitions to the reset state have been omitted from the diagram to make it easier to read). Pressing "0" or "1" will cause the lock to follow the appropriately labeled transition from its current state. The lock opens if it reaches the state marked "U".
3 button presses will open the lock: 0, 0, 1.
The longest such sequence is unbounded: any number of 0's followed by 111 or 1111 will cause the lock to open for the first time.
Yes. A sequence of 1's will open the lock. You have to try the lock after each press of "1" since a different number of 1's is required depending on the starting state.
His FSM would need 9 states in addition to "reset" and "unlock".
Problem 6. Stimulated by the idea of FSMs, you have decided to cover MIT's steep tuition costs by selling simple digital locks based on the following six-state FSM:
Recall that this design has three buttons labeled "0", "1", and "Start", and generates an unlock signal U=1 when the user presses Start followed by the sequence 0,1,1,0.
Unfortunately your partner, Mark Ting, insists that the design is way too complex for normal users to understand. After asking you to help figure out how to make his watch stop beeping ("I never could figure out how to operate this damned thing"), Mark questions the need for a Start button. If 0110 is the combination, he argues, why can't I just walk up and enter 0,1,1,0 and have the lock open? After some reflection, you conclude that he may have a point.
The name of each state represents how many digits in the sequence have been input. State Sxxxx indicates that the sequences has not begun, Sxxx0 indicates that the first 0 has been input, etc.
Since 4 transitions are required for 4 button pushes, at least 5 states are needed to implement the FSM. Having only 4 states would make 3 the mininum number of transitions to the unlock state.
Since we have 5 states, 3 bits are required to encode the states, resulting in 3 unused states. If during power up it is possible to being in an unknown state, our FSM must include transitions from unknown states to known states. If the machine beings in an unknown state and a 0 in input, we should transition to state Sxxx0; if a 1 is input, we should transition to Sxxxx.
Problem 7. A possible implementation of a finite state machine with one input and one output is shown below.
2N+1 locations of N+1 bits.
2N
Problem 8. Ben Bitdiddle has designed an electronic lock with three buttons: "Breset", "B0" and "B1". He has provided the following circuit diagram showing how the lock is implemented from a ROM and 3 flip-flops.
The button circuitry converts each button press into a single pulse guaranteed to be stable the required amount of time before and after the rising edge of the clock. For example, pressing "B0" once produces the following waveform:
In answering the questions below, assume that the value of the UNLOCK output is only a function of the current state.
256 bits total: 26 locations, 4 bits wide.
How long before the rising edge of CLK must the button circuitry guarantee that the button signals are stable?
tPD,ROM + tS = 14ns.
7 assuming no looping combinations.
The current state appears on A5,A4,A3 = 110. So we want the next state field of the ROM (D2,D1,D0) to specify the same state = 110.
If the lock is programmed with this ROM data, what happens when "B0" and "B1" are pressed at the same time? Assume that "Breset" is not pressed.
State stays the same since all addresses of the form XXX011 transition to state XXX.
press B0, then B1.
Yes, you can open the lock. Noting that the UNLOCK state loops to iteself, B1-B0-B1 is one of many sequences that takes us from any state to UNLOCK.
Problem 9. Consider the following FSM state transition diagram:
Let's see if there is an equivalent state machine with fewer states by checking to see if any states in the diagram above are equivalent. Two states are equivalent if (1) they have identical outputs and (2) for each possible combination of inputs they transition to equivalent states.
Here's the state transition diagram for the simplified FSM (w/o state 3).