Thursday, May 22, 2014

Keypad Input Validation using State Machine Programming.


Keypad Input Validation

Using

State Machine Programming

The Problem:

You have a project that accepts commands using a keypad or receiving the data serially and want to perform validation on the commands as each character is typed.  But how?

Example:

Typical project with 16 button keypad

Here is the sample or typical protocol (commands) using only a 4 x 4 - 16 button keypad:

XX@HH:MM#

Where:

XX is a value from 1-99
HH:MM is a time format (24 hr clock or military time)
Alpha-Numeric Key Mappings:
A = @ (at sign)
B = NOT USED
D = NOT USED
C = Clear
* = : (colon)
# = Execute (accept or enter or execute) the command


The Solution:

Use state machine logic / programming to solve the problem.

Introduction to State Machine Logic / Programming

If you aren't familiar with or haven't used state machine logic in programming, it is the easiest way to to break complex problems into manageable states and state transitions especially for handling serial input.

One of the easiest ways to implement a state machine is to use a switch statement.  In my opinion it is the only way to implement serial input commands.

Example of a state machine using a switch statement:

switch(state) {
   case INITIAL:
     // process INITIAL state  
   break;
   case STATE1:
     // process STATE1 state       
   break;
   case CLEAR:
     clearAll();
     state = INITIAL;
   break;
   default:
   break;
} 

Let's now apply this logic to your project.

Here is a step by step approach to solve the problem:
  • Break the commands into states. 
    • The easiest way is to consider each character in the command as a state.
    • Given the command:  XX@HH:MM# 
      • Here are suggested state names:
        • VALUE1 - First digit of value
        • VALUE2 - Second digit of value
        • ATSIGN - At sign (@)
        • HOUR1 - First digit of hour
        • HOUR2 - Second digit of hour
        • COLON - Colon (:)
        • MIN1 - First digit of minute
        • MIN2 - Second digit of minute
        • EXECUTE - Pound sign (#)
      • Then create an additional state called INITIAL
  •  Create a list or table of all the combinations within a command or commands.
    • Given the command: XX@HH:MM# 
      • All combinations of the command:
        • XX@HH:MM# (45@12:45#)
        • XX@HH:MM# (45@1:26#)
        • X@HH:MM# (9@12:45#)
        • X@H:MM# (9@1:26#)
  • Determine all ranges for values
    • XX has a range 1 to 99 but 01-09 is also valid
    • HH has a range of 0-24 but 00-09 is also valid
    • MM has a range of 00-59
  • Create a state diagram.
    • Start with a table or spreadsheet with all the states entered:
      State Valid Keys Next State Comments
      INITIAL


      VALUE1


      VALUE2


      ATSIGN


      HOUR1


      HOUR2


      COLON


      MIN1


      MIN2


      EXECUTE


  • For each state determine what keys are valid and the next state.
    • INITIAL is the first digit of the value so valid keys are 0-9
    • VALUE1 can be the second digit of the value or the at sign (@)
    • Continue until you have completed all the valid key and next state.
      State Valid Keys Next State Comments
      INITIAL 0-9 VALUE1 X

      anything else INITIAL Display Format Msg
      VALUE1 0-9 VALUE2 XX

      @ ATSIGN X@

      anything else VALUE1 Display Format Msg
      VALUE2 @ ATSIGN XX@

      anything else VALUE2 Display Format Msg
      ATSIGN 0-9 HOUR1 X@H, XX@H

      anything else HOUR1 Display Format Msg
      HOUR1 0-9 HOUR2 X@HH, XX@HH

      : COLON X@H:, XX@H:

      anything else HOUR1 Display Format Msg
      HOUR2 : COLON X@HH:, XX@HH:

      anything else HOUR2 Display Format Msg
      COLON 0-5 MIN1 X@HH:M, XX@HH:M

      anything else COLON Display Format Msg
      MIN1 0-9 MIN2 X@HH:MM, XX@HH:MM

      anything else MIN1 Display Format Msg
      MIN2 # EXECUTE X@HH:MM#, XX:HH:MM#

      anything else MIN2 Display Format Msg
      EXECUTE run INITIAL
    • Here is the state diagram in diagram format:
Example State Diagram
  • Next create the program
    • Create #defines for each state
    • Create a switch statement with each state as a case.
      // States
      #define INITIAL       1
      #define VALUE1        2
      #define VALUE2        3
      #define ATSIGN        4
      #define HOUR1         5
      #define HOUR2         6
      #define COLON         7
      #define MIN1          8
      #define MIN2          9
      #define EXECUTE       10
      
      
      switch(state) {
         case INITIAL:
         break;
         case VALUE1:    
         break;
         case VALUE2:
         break;
         case ATSIGN:
         break;
         case HOUR1:    
         break;
         case HOUR2:
         break;
         case COLON:
         break;
         case MIN1:    
         break;
         case MIN2:
         break;
         case EXECUTE:
         break;
         default:
         break;
      }
      
     
  • Next create the some helper functions
    • Create functions to validate input keys
      // Validate keys: @ (at sign)
      // return true if valid, else false
      int validAtSign(int key) {
        int valid=0;
        switch(key) {
          case '@':
            valid=1;
          break;
        }
        return valid;
      }
      // Validate keys: : (colon)
      // return true if valid, else false
      int validColon(int key) {
        int valid=0;
        switch(key) {
          case ':':
            valid=1;
          break;
        }
        return valid;
      }
      // Validate keys: # (pound sign)
      // return true if valid, else false
      int validPoundSign(int key) {
        int valid=0;
        switch(key) {
          case '#':
            valid=1;
          break;
        }
        return valid;
      }
      // Validate keys: 0-9
      // return true if valid, else false
      int validKeys0to9(int key) {
        int valid=0;
        switch(key) {
          case '0':
          case '1':
          case '2':
          case '3':
          case '4':
          case '5':
          case '6':
          case '7':
          case '8':
          case '9':
            valid=1;
          break;
        }
        return valid;
      }
      // Validate keys: 0-5
      // return true if valid, else false
      int validKeys0to5(int key) {
        int valid=0;
        switch(key) {
          case '0':
          case '1':
          case '2':
          case '3':
          case '4':
          case '5':
            valid=1;
          break;
        }
        return valid;
      }
      
  • Add the helper functions and minimal logic to the switch statements (states)
    • Go state by state following the state diagram rules above
          switch(state) {
            case INITIAL:
              // X
              if(validKeys0to9(key)) {
                pos = displayKey(key, pos);
                storeKey(key);
                state = VALUE1;
              } else {
                invalidFormat();
              }
            break;
            case VALUE1:
              // XX
              if(validKeys0to9(key)) {
                pos = displayKey(key, pos);
                storeKey(key);
                state = VALUE2;
              } else if (validAtSign(key)) {
                // X@
                pos = displayKey(key, pos);
                state = ATSIGN;          
              } else {
                invalidFormat();
              }
            break;
            case VALUE2:
              // XX@
              if(validAtSign(key)) {
                pos = displayKey(key, pos);
                storeKey(key);
                state = ATSIGN;
              } else {
                invalidFormat();
              }
            break;
            case ATSIGN:
              // X@H, HH@H
              if(validKeys0to9(key)) {
                pos = displayKey(key, pos);
                storeKey(key);
                state = HOUR1;
              } else {
                invalidFormat();
              }      
            break;
            case HOUR1:
               // X@HH, XX@HH
              if(validKeys0to9(key)) {
                pos = displayKey(key, pos);
                storeKey(key);
                state = HOUR2;
              } else if (validColon(key)) {
                // X@HH:, XX@H:
                pos = displayKey(key, pos);
                state = COLON;          
              } else {
                invalidFormat();
              }
            break;
            case HOUR2:
               // X@HH:, XX@HH:
              if (validColon(key)) {
                // X@HH:, XX@H:
                pos = displayKey(key, pos);
                state = COLON;          
              } else {
                invalidFormat();
              }
            break;
            case COLON:     
              // X@HH:M, XX@HH:M
              if(validKeys0to5(key)) {
                pos = displayKey(key, pos);
                storeKey(key);
                state = MIN1;
              } else {
                invalidFormat();
              }
            break;
            case MIN1:
              // X@HH:MM, XX@HH:MM
              if(validKeys0to9(key)) {
                pos = displayKey(key, pos);
                storeKey(key);
                state = MIN2;
              } else {
                invalidFormat();
              }
            break;
            case MIN2:
              // X@HH:MM#, XX@HH:MM#
              if(validPoundSign(key)) {
                pos = displayKey(key, pos);
                storeKey(key);
                state = EXECUTE;
              } else {
                invalidFormat();
              }
            break;
            case CLEAR:
              clearAll();
            break;
            default:
            break;      
          } // switch
      
  • Test the results
    • Add any additional limit/range checking on values.
      • For example: valid time format is 00:00 to 24:00 
    • See example code.  It utilizes the serial terminate and some helper functions for debugging.
It's as simple as that!

Source Code:

The complete working example is available here

And on Github:
 
https://github.com/onewithhammer/StateMachineInput

Working Demo: 

 

video




Future Enhancements / Ideas:
  • The working example is meant as a teaching tool and doesn't have full validation on the values.
  • This example does include code to use the serial terminal to help you debug.
Questions?

If you have any questions please feel free to ask.

I hope this article is helpful and useful to someone interested in validating keypad input using state machine programming.  Feel free to use this code and example to validate you next project using a keypad for input command.

Thanks,
Tony