Exercise: Input Pattern Matching

Objective

Understand a simple pattern recognition state machine expressed as an Arduino program using several idiomatic C/C++ program structures.

This is a very simple single-input binary pattern recognition system. However, even this state machine could be used to recognize synchronous inputs from a communications channel.

State Transition Graph

This graph represents the set of discrete states modelled by the system. States are illustrated as ovals and transitions as arrows. Each state can have an associated output, in this case the LED. Transitions between states are defined by condition rules.

digraph input_matching_time { node [fontsize=10] edge [fontsize=8] dpi="72" size="7,7!" // declare all nodes START [ label = "START\nLED is OFF" ] STATE1 [ label = "STATE1\nLED is OFF" ] STATE2 [ label = "STATE2\nLED is OFF" ] STATE3 [ label = "STATE3\nLED is ON" ] DELAY [ label = "DELAY" ] DELAY1 [ label = "DELAY1" ] DELAY2 [ label = "DELAY2" ] DELAY3 [ label = "DELAY3" ] // declare all edges with labels START -> DELAY [ label = "always" ] DELAY -> DELAY [ label = "< one second elapsed" ] DELAY -> STATE1 [ label = "one second elapsed\nAND input is HIGH" ] DELAY -> START [ label = "one second elapsed\nAND input is LOW" ] STATE1 -> DELAY1 [ label = "always" ] DELAY1 -> DELAY1 [ label = "< one second elapsed" ] DELAY1 -> START [ label = "one second elapsed\nAND input is HIGH" ] DELAY1 -> STATE2 [ label = "one second elapsed\nAND input is LOW" ] STATE2 -> DELAY2 [ label = "always" ] DELAY2 -> DELAY2 [ label = "< one second elapsed" ] DELAY2 -> STATE3 [ label = "one second elapsed\nAND input is HIGH" ] DELAY2 -> STATE1 [ label = "one second elapsed\nAND input is LOW" ] STATE3 -> DELAY3 [ label = "always" ] DELAY3 -> DELAY3 [ label = "< one second elapsed" ] DELAY3 -> STATE3 [ label = "one second elapsed\nAND input is HIGH" ] DELAY3 -> START [ label = "one second elapsed\nAND input is LOW" ] label = "InputMatcher\nState Transition Diagram" }

Each transition has a one-second duration to make it feasible to manually manipulate the switch input with a timed sequence to walk through the graph. However, this makes it harder to read the graph. The same state machine with the wait states removed is simpler to read:

digraph input_matching { node [fontsize=10] edge [fontsize=8] dpi="72" size="7,7!" // declare all nodes START [ label = "START\nLED is OFF" ] STATE1 [ label = "STATE1\nLED is OFF" ] STATE2 [ label = "STATE2\nLED is OFF" ] STATE3 [ label = "STATE3\nLED is ON" ] // declare all edges with labels START -> STATE1 [ label = "input is HIGH" ] START -> START [ label = "input is LOW" ] STATE1 -> START [ label = "input is HIGH" ] STATE1 -> STATE2 [ label = "input is LOW" ] STATE2 -> STATE3 [ label = "input is HIGH" ] STATE2 -> STATE1 [ label = "input is LOW" ] STATE3 -> STATE3 [ label = "input is HIGH" ] STATE3 -> START [ label = "input is LOW" ] label = "InputMatcher\nState Transition Diagram\n(All transitions take finite time.)" }

Steps and observations

  1. Set up an Arduino UNO with a 10K pullup resistor on PIN4 and a switch connecting PIN4 to ground, e.g. a simple binary input sensor which you can operate.

  2. Upload the InputMatcher1 sketch.

  3. Open the Serial Console and set to 115200 baud.

  4. Observe the console messages and the onboard LED. Can you deduce an input sequence which will get to State 3 and turn on the LED?

  5. Examine the code; you will be comparing this program structure to the following two versions.

  6. Repeat the test for InputMatcher2 and InputMatcher3.

  7. Choose a new pattern for the system to recognize, and choose the input example you prefer to modify. Rewrite the finite-state machine to recognize the pattern of your choosing.

Comments

This same recognition exercise could be extended to any binary input: optical switches, wall contact switches. It could also be extended to any possible sampling rate, including cycling loop() as fast as possible.

The transition properties could be extended to include other predicates: comparisons on elapsed time to prevent exiting a state before time has elapsed, more elaborate mappings of linear inputs to transition state.

You may now recognize that the switch debouncing code introduced much earlier is a specific case of a finite-state machine implementing time-based hysteresis.