BASIC Stamp does Finite State Machines

(c) 1998, 2001 EME Systems, Berkeley CA U.S.A.
<stamp index> <home>

Contents: (updated 4/27/2005)

pushbutton increment/decrement as a state machine


This is one of the most common problems that comes up on the BASIC Stamps list. It goes something like this.

"I have a gizmo that displays a number of counts. It needs to increment one count up when I press one button (or detect and event with a sensor), and decrement once count down when I press a second button. If I just do the counting when the button is down or up, the count just keeps increasing or decreasing as long as I hold down the switch. I've tried putting delays in the program, but too short a delay and I have the same problem, too long a delay and everything slows down to molasses and the program misses the button press. What can I do? Should I be using the BUTTON command? Oh, by the way, I have to do 2 different counters at once, with 4 buttons."

Do this sort of thing in a loop, a "state machine":

' buttons on p0 to p2, active low 0 when pressed
x0 VAR nib ' prior state of 4 input pins
x1 VAR nib ' present state of 4 input pins
xx VAR nib ' detect change in state of 4 input pins
c0 VAR byte ' first counter
c1 VAR byte ' second counter
x1 = inA ' get state of all 4 input pushbuttons or sensors
xx = x1^x0 & x1 ' detect changes, bit =1 when button is released
x0 = x1 ' update old state of all 3 buttons
C0 = C0 + xx.bit0 - xx.bit1 ' update counts, up for p0, down for p1
C1 = C1 + xx.bit2 - xx.bit3 ' up for p2, down for p3
DEBUG DEC C0,TAB,DEC C1, CR ' to display
PAUSE 10 ' program can do other stuff here. Exact delay is not critical.
LOOP ' over and over

The main trick there is to detect the change in state on the pins. That is all done in parallel, on all four input pins at once. The XOR operator {"^" in Stampese) is put in between the present state and the prior state. The operator acts bit by bit, and the result bit is one if and only if the two corresponding bits in x0 and x1 are opposite. For example, if x0=1101, and x1=%1110, then the result of x1^x0 will equal 0011. The ones show that the two lower bits have changed since the last scan. Sometimes that is all you need. But here we only want to take action with the counters when the state of the button goes from DOWN to UP, from 0-->1. That brings up the AND operator ("&" in Stampese). The  result of the XOR operation is ANDed with x1, so that the final result is a 1 only in the positions where a change has occurred from 0-->1. In the example, xx=%1101 ^ %1110 & %1101 = %0011 & %1110 = %0010. Only the second button has just been released.

In this example, those individual bits are used to increment or decrement a counter. In other applications, the action taken may be more complex, say

 IF xx.bit0 then phoneHome

More advanced use of the boolean logic of XOR, AND etc, to detect changes in the state machine, are found in all the application notes below. Interfaces to sensors such as rain gages, anemometers, and event counters can make use of this kind of code, and are described in the sensors and OWL data logger section.

But first here, a note about the BUTTON command.

BUTTON command


This note concerns the BUTTON command that is built into the BASIC Stamp. Why put it here in the document on state machines? Well, the button command is in itself an instructive state machine. To make the best use of the command, you have to understand its inner workings. The BASIC stamp manual does not give sufficient data. The results here come from investigations and experiments I did to get to the bottom of its operation.

When all is said and done, I do not use the button command much. I prefer tto write my own specific keyscan routines, for example, the one above for the matrix keypad.

The button command is a state machine that depends only on 1) the current value of the working variable, 2) the state of the input pin at the instant of sampling, and 3) on the parameters delay and rate. Here are the functional names of the paramters.

BUTTON inPin,downState,delay,rate,workVariable,targetState,targetAction

Let's think about a specific form of the command, where the targetAction is taken when the input pin goes to 0 to indicate the "downstate":

BUTTON inPin,0,delay,rate,workVariable,1,targetAction

  1. if inPin is 1 (UP, opposite of downState) at the instant of sampling, then, workVariable is cleared to zero. No further action is taken.
  2. if inPin is 0 (DOWN, =downState) at the instant of sampling, then, [four cases follow, depending on current value of workVariable]
    1. if workVariable=0, then WorkVariable is set equal to parameter "delay" The program branches to targetAction.
    2. if workVariable=255 then No action taken. (waiting for inPin to return UP, case 1)
    3. if 1<workVariabl<255, then workVariable is decremented by one. No further action.
    4. if workVariable=1, then workVariable is set equal to the parameter "rate". The program branches to targetAction.

When delay=255, then debounce is enabled, autorepeat is disabled. The state machine alternates between case 1, 2A and 2B, as described above for simple debounce. The work variable alternates between zero and 255. Once the button is pressed into its active state, it has to go back up again to the inactive state before the target action will occur again.

When delay=0, then both debounce and autorepeat are disabled, and the state machine alternates between states 1 and 2a. WorkVariable is always set equal to zero, and the program branches to targetAction every time it hits the button command. Not too useful, I think.

When delay is some other value from 1 to 254, the autorepeat function operates. If the BUTTON command is branching to target-action for the first time (button down and current workvariable=0), then the workvariable is set equal to the parameter "delay". Then on subsequent hits of the BUTTON command the workvariable is decremented (state 2C). If the workvariable gets down to 1, then instead of going to zero on the next pass, the BUTTON command sets the workvariable equal to the parameter "rate". And the cycle repeats over and over so long at the input is in its downState. As soon as the input goes UP, and the BUTTON command detects that, the workvariable is set back to zero and stays in state 1 until the button is pressed DOWN again.

It is a very simple state machine that depends only on the state variables and parameters.

That covers all cases when downState=0 and targetState=1. The variations 00, 10, 11 follow similar logic. The parameter "targetState" is a little confusing. If targetState=1, then the branch to targetAction occurs when the input _is_ in its downState. But if targetState=0, then targetAction occurs when the input _is not_ in the downState.

It is possible to change workVariable at any point in a program. The button command just acts on the current value of workVariable, whatever it is. You might be able to come up with some tricky schemes that depend on making the delay a variable, and presetting workvariable to a value other than zero.


One buzzword that causes a lot of confusion is debounce. People often misunderstand what that means, and expect more than the Stamp really delivers.

The manual is misleading. Here are a couple of excerpts: "When you press a button or flip a switch, the contacts make or break a connection. A brief (1 to 20-ms) burst of noise occurs as the contacts scrape and bounce against each other. BUTTON's debounce feature prevents this..." And, ""When the state of the input first matches 'downstate' it debounces the pushbutton".

The misunderstanding occurs because the button command is of no help for rejecting impulse noise, or for accidental very brief activation's of the button, or for slow bounce. When a Stamp program encounters a BUTTON command, it samples the input once and takes action (branch or not branch, or count for autorepeat) depending on that one sample. If a noise pulse happens to come along at that instant, the BUTTON command will happily respond. The Stamp does not take multiple samples over several successive clock cycles and say, "sorry, this is not really a good solidly pressed pushbutton", if the samples do not agree. To many engineers, that is the meaning of debounce. In an effort to understand how the button command deals with contact bounce, I fed the output of a function generator (variable duty & frequency cmos levels) to an input pin of a Stamp2. I won't bore you with the details, but I was surprised to learn that the button command offers no noise rejection whatsoever. There is nothing in the button command that will stop it from responding to a very narrow noise pulse that happens to occur at the instant when the button command samples its input. Do not expect the button command to be robust in the presence of noise. That's not what the term debounce means for BUTTON.

For example, let us say that a noise pulse comes along, and the stamp happens to sample at that instant. It will immediately execute the "downstate" code, but as soon as it hits the button command again it will find it in the "upstate". So the button command is immediately rearmed to respond again. In a noisy environment, it could execute the BUTTON command repeatedly and wrongly. The noise could come for example from a loose switch, or electrical noise from a generator, or from an unintended jiggle by a human operator.

Most switches bounce for a very short time, less than one millisecond. The BASIC Stamp is so slow that it is not likely to return to the BUTTON command during the uncertain interval of millisecond bounce. But a bad or unconventional switch might continue to bounce for more than a few milliseconds. There would be a real possibility that the Stamp would detect and respond to more than one event.

Debounce has the following narrow meaning for the BASIC Stamp: With debounce enabled (delay=255 in the BUTTON parameters), an action may occur when the input goes into its downstate. But then that action will not occur again until the input goes back to uts upstate, detected by the BUTTON command, and then back to the downstate again.

I hope this is useful to others. My own experience with the command is, I hardly ever use it. The DOWN-UP-DOWN debounce function can be obtained with one bit for one button, instead of the whole byte that is consumed by the button command as a work variable. It is possible to put several such bits in one nib or byte and service several inputs at once. The matrix scanning routine shown below shows how to implement true debouncing in this way, to deal with several keys in parallel at once.I do think the BUTTON comand would be useful for autorepeat functions, but I do not need those much.

State machine: two-bit quadrature encoder


encoder patternA rotary or linear two-bit encoder has two photocells that shine through two tracks laid down in a pattern as shown, 90 degrees out of phase. (see the another article below on absolute, Gray Code wheels) The signals from the two photocells go high and low in turn, as the pattern moves. By decoding the signals it is possible to tell which direction the wheel is turning and how far. A disk may have several hundred alterations of light and dark, so it is possible to resolve the position to better than a degree. There is often an index mark at some position on the wheel, and a third phototransistor, to establish a "home" position. Here are the possible states in sequence:

----> ----> ----> ---->    CW
0 1 1 0 0 B
0 0 1 1 0 A
<---- <---- <---- <---- CCW
0 1 3 2 0 state

The "1" and "0" are logical levels produced by the phototransistors. Every transition is significant. For example, a transition from 10 to 11 means clockwise, while a transition from 10 to 00 means counterclockwise. The states have binary values of 0 to 3. A transition from a state to itself does not count, of course, and there are some transitions that should not occur, for example, 00 to 11. That leaves are 4 possible starting states and 4 possible ending states. Here are the sixteen possible transitions, written out in a matrix form. cw=clockwise, ccw=counter clockwise, - = transition to self, *=disallowed transition. Note that 8 of the 16 states are "significant".

0 1 2 3
- cw ccw *
old 1 ccw - * cw
2 cw * - ccw
3 * ccw cw -

The null transitions consist of both diagonals of the table. We can rewrite this as a strictly numerical matrix, with cw=1, ccw=-1 and - and * both as 0, no motion.

1 2 3
0 0 1 -1 0
old 1 -1 0 0 1
2 1 0 0 -1
3 0 -1 1 0

Here is BASIC Stamp II routine to look up the state in a table. The important snippet is highlighted in red. The result can be used to increment a counter, or whatever is needed for the application. The big caveat is that the decode routine has to be run often enough so that none of the significant transitions are missed. This requirement puts a limit on how fast the encoder can move, and still be compatible with the relatively slow BASIC Stamp. If this might be a problem, the disallowed transitions 0<-->3 and 1<-->2 will sometimes occur. You could put a special code in the lookup table below to test for those states and ring an alarm if the motion gets to be too fast.

' encoder, signals on P8 and P9 (two lsbs of nibC)
' using lookup table logic
old var nib ' state variable
new var nib ' state variable
x var word ' for lookup
cnt var word ' for demonstration
dirC=0 ' make port C inputs
old=inC ' read initial state of inputs
new=inC&3 ' read new state of encoder, two bits
lookup old*4+new,[0,1,-1,0,-1,0,0,1,1,0,0,-1,0,-1,1,0],x
' new becomes old
cnt=cnt+x ' where are we
debug home,sdec5 cnt
goto decode

Encoders usually require substantial power (10 or more milliamps may be considered lots of power in some applications). It is possible to turn on the power to the encoder only when a sample is going to be taken. That is how encoder based water depth gages like the Unidata 6511 work, in order to achieve a battery life of two years. They sample the state of the encoder with brief pulses. The caveats about speed of rotation apply to sampled data recorders. The samples have to be taken often enough to avoid missing any transitions.

 high epower ' turn on the excitation
new=inC&3 ' read new state from photosensors
low epower ' off

Another way to decode the sequence is strictly Boolean. Scott Edwards discusses this with BS1 code in app note #8 in st_app2.pdf. Look at the diagonal terms in the state sequence, going from the A bit of the first state to the B bit of the second state. As shown, for clockwise rotation, those two bits are always different. One is a 0 and the other is a one. If you do the same thing for counterclockwise rotation, you find that the two bits are always the same. So an XOR between those two bits will always give a 1 for CW rotation and 0 for CCW rotation.


0     1    3     2     0  state
----> ----> ----> ----> CW

0 _ 1 _ 1 _ 0 _ 0 B
/ / / / all 0->1 or 1->0
0 - 0 - 1 - 1 - 0 A

0 1 3 2 0 state
<---- <---- <---- <---- CCW

0 _ 1 _ 1 _ 0 _ 0 B
\ \ \ \ all 0->0 or 1->1
0 - 0 - 1 - 1 - 0 A

The code for this is

direction_bit = old.bit0 ^ new.bit1 ' 1 if CW, 0 if CCW

Here is a routine that counts up or down based on this XOR logic.

' encoder, signals on P8 and P9 (two lsbs of nibC)
' using XOR logic
old var nib ' previous state, only two bits
new var nib ' current state
ob var old.bit0 ' bits to test
nb var new.bit1
cnt var word ' for demonstration
dirC=0 ' make port C inputs
old=inC & 3 ' read initial state of inputs
new=inC & 3 ' read state of encoder, two bits
if new=old then decode ' loop until change to new state
cnt=ob^nb*2-1+cnt ' calculate motion
old=new ' new becomes old
debug home,sdec5 cnt
goto decode

The calculation of the count adds 1 when ob^nb=1 and subtracts 1 when ob^nb=0.

The logic can be extended to more than one encoder. Suppose there are 4 encoders, with their signals connected in pairs to inputs P8 to P15 (on the high byte inputs). The following program logic is implemented as a state machine. State machine logic really shines when several encoders have to be scanned at the same time, because the logic for all of them happens in parallel.. This logic can be extended to 8 encoders on 16 inputs with exactly the same number of lines of code.

' 4 encoders, signals on P8 thru P15 (by bit pairs)
' using XOR state machine logic
' Tracy Allen,
old var nib ' previous state, only two bits
new var nib ' current state
x var byte ' internal state variable
x0 var x.bit0 ' alias first bit of byte x
i var nib ' index into state array
cnt var word(4) ' for demonstration
' -----------------
dirH=0 ' p8 to p15 inputs
old=inH ' read initial state of inputs
new=inH ' read new states from all 4 encoders, eight bits
x = new ^ old ' changed bits are one
x = (x>>1 & %01010101) | (x<<1 & %10101010) | x ' see note
x = new >> 1 ^ old & %01010101 + %01010101 & x ' form the result
old=new ' reinitialize
for i=0 to 3
cnt(i)=cnt(i)+x0(i*2)-x0(i*2+1) ' compute counts from bits of x
debug dec cnt(i)
debug home
goto decode

All of this is state machine logic, and while it is relatively slow on a BASIC Stamp, it is much faster than any way using lots of IF and THENs to sort out the possible states. Note that the algorithm has to run fast enough to detect all of the states.   On the BASIC Stamp, encoder frequency could not exceed much over 100 Hertz.   It is possible to code this same logic on a blindingly fast processor like the Ubicom SX series, which can keep up with the fastest rotation.

Below is another way to code the same thing, but this method uses an additional state variable and cuts down on the computation. This one puts the directional information in the even numbered bits of byte X. A one means CW rotation, a zero means CCW rotation. The overall change in state is held in the even numbered bits of byte Y.  The final computation of the counts uses the even bits of x to compute the direction {either +1 or -1 for CW or CCW}, masked by the even bits of y, for state change.

' 4 encoders, signals on P8 thru P15 (by bit pairs)
' using XOR state machine logic
old var nib ' previous state, only two bits
new var nib ' current state
x var byte ' internal state variable ends up with even bits as directions
x0 var x.bit0 ' alias first bit of byte x
y var byte ' internal state variable ends up with even bits as state changes
y0 var y.bit0 ' alias first bit of byte y
i var nib ' index into state array
cnt var word(4) ' four counts for demonstration
dirH=0 ' p8 to p15 inputs
old=inH ' read initial state of inputs
new=inH ' read new states from all 4 encoders, eight bits
x = new ^ old ' changed bits are one
y = x>>1 | x ' bits {0,2,4 or 6} equal 1 iff there is a state change in either bit of a pair {01, 23, 45, 67}
x = new >> 1 ^ old ' bits {0,2,4,6} equal 1 for clockwise, 0 for CCW
old=new ' reinitialize
for i=0 to 6 step 2
cnt(i)=cnt(i)+(2*x0(i)-1*y0(i)) ' compute counts
debug dec cnt(i)
debug home
goto decode

Gray code to binary conversion


grayCode patternGray code is used in absolute encoders, where rotary or linear position is sensed by photosensors looking at or through at a code disk or code strip. Let's say a dark area is a "0" and a light area is a "1". Here is a 4-bit gray code that has 16 possible values, in sequence, running clockwise around the wheel, with the least significant bit in the center.:



It goes through all 16 combinations of zeros and ones, but it steps through them in a different order from the usual binary number sequence. The important thing to notice about the Gray code is that only one bit changes at each step. In contrast, with a straight binary code, sometimes two or more bits change at once in a transition. It is difficult to align a code disk accurately enough. For example, a two bit transition from 0011 to 0100 might come out as three steps 0011->0001->0100, due to misalignment of the sensors. The Gray code does not have that problem.

Nevertheless, you usually want to work with an ordinary binary sequence once the sequence is in the computer. There's a neat circuit using XOR gates in "The Art of Electronics" for converting a Gray code to Binary. Here is how it comes out translated to BS2 PBASIC. The input is a 4-bit gray code, gc, and the output is a 4 bit binary code, bn.


gc var nib ' input gray code 4 bits
gc0 var gc.bit0 ' alias for lsb of gc
bn var nib ' output binary 4 bits
bn0 var bn.bit0 ' alias for lsb of bn
ii var nib ' index for conversion loop

gc=1011 ' pick a gray code to enter here
' this number is just for a demo
' now start the conversion routine here
bn.bit3=gc.bit3 ' convert to binary
for ii=2 to 0 ' bit by bit XOR
debug bin4 gc,tab,bin4 bn,cr
' the result printed is the gray code
' and the corresponding binary code

This is not really a finite state machine, but I put it here to go with the other material on encoder wheels.

The inverse conversion, from binary to Gray code, is almost trivial. Shift the binary value right by one bit and XOR it with the original binary value:

gc=(bn>>1)^ bn ' to convert binary bn to Gray code gc

State machine: Direction of motion decoder


Here's some BS2 code for a direction-of-motion detector where an object moves past detectors in so as to interrupt the beam signals in a pattern: 11-10-00-01-11 for one direction of motion and 11-01-00-10-11 for the other direction of motion. (see the figure below.) This code also works for linear or rotary encoder strips (see the previous article).

directional This is an BS2 implementation in software of a circuit that I originally made in hardware, shown to the right. This appeared in EDN "Design Ideas" under the title, "Direction Detector Doubles as Decoder". The original application was to detect the movement of bumblebees in and out of their nest. The inputs of the quad schmitt trigger are normally pulled to a low level, due to a light source falling on the phototransistors. When an object moves completely through the field of view, it blocks first one and then the other light path, and then unblocks them in the same order. A pulse occurs on one or the other output, depending on which way the object goes through. On an encoder disk, a sequence of opaque and transparent bands is like a sequence of objects moving through the light path, and the circuit generates a sequence of pulses corresponding to the direction of rotation.

directional circuit diagramHere is the circuit implemented on a BS2. The phototransistors go directly to BS2 inputs, with pull-up resistors. The voltage at the input pins is LOW until an object moves through the light path. The following BS2 routine samples input port inL once, and then makes the determination of direction from that and from an internal "memory" variable. The trick here is that it is all done with static logic. There are no IF statements. This makes the execution relatively fast. It is important to sample the two phototransistor signals at exactly the same point in time to avoid false results. The Stamp will have to respond fast enough to "see" all the states in the sequence. The speed limit depends on how much the stamp has to do before it returns to sampling the signal. As shown it can work reliably up to about 100 hertz--each state has to be stable on the inputs for greater than 5 milliseconds.

The output of the routine is two signals:

 -- bit variable x1 goes high as a message for "clockwise"
-- bit variable x2 goes high as a message for "counterclockwise".

They stay high for one iteration of the loop. The routine is "self-debouncing", in the sense that jitter back and forth generates either no signal, or both signals (first one and then the reverse).

 ' bumbled1.bs2
' Tracy Allen,
' decodes direction of motion, or encoder wheel (see circuit diagram)
' l.e.d.s are attached to P8 and P9 to signal motions
iB var byte 'holds sample of input port with photoxistors
i0 var iB.bit0 'sampled status of input pin 0, xistor #0
i1 var iB.bit1 'sampled status of input pin 1, xistor #1
m0 var bit 'internal state memory bit
m1 var bit 'internal state memory bit
x0 var bit 'transient rotation state, 0=no rotation, 1=clockwise
x1 var bit 'transient rotation state, 0=no rotation, 1=counter-clockwise
y0 var bit 'temporary bit variable
y1 var bit 'temporary bit variable

' 1) get sample:
iB = inL ' read pins P0 to P7 into byte iB
' 2) process rotation info:
y0 = ~(i0 & m0) ' NAND of input and memory states
y1 = ~(i1 & m1)
x0 = y0 ^ m0 & y0 & m1 ' cross-coupled logic, looks for change in y0
x1 = y1 ^ m1 & y1 & m0 ' same for y1
m0 = y0 ' update memory states
m1 = y1
3) deal with the result, here just blink an l.e.d. to indicate rotation
pulsout 8,x0*500 '
pulsout 9,x1*500
goto loop

Here is the state diagram:

 State machine:
y0 y1 m0 m1 x0 x1 "clockwise"
0 0 1 1 0 0
1 0 0 1 0 0
1 1 0 1 0 0
0 1 1 0 ^1 0 ^1 means transient (one iteration)
0 0 1 1 0 0

y0 y1 m0 m1 x0 x1 "counter-clockwise"
0 0 1 1 0 0
0 1 1 0 0 0
1 1 1 0 0 0
1 0 0 1 0 ^1 ^1 means transient (one iteration)
0 0 1 1 0 0

It is straightforward to extend this to as many as 8 separate pairs on 16 inputs of a BS2 without much expansion of the code. The logic works all at once, in parallel, on pairs of bits in byte or word-wide variables.

The following assumes that there are 4 pairs of phototransistors are connected as above to 8 BS2 inputs: P0-P1, P2-P3, P4-P5 and P6-P7. To indicate the directional results, the message byte is output on P8-P15, and to the debug screen. The fancy term with shifts right and left in the following program calculates the cross-terms in x0 and x1. Observe that this "quad" program is hardly any longer than the program that processes one directional signal. Only 4 lines of program code.

' bumbled4.bs2
' Tracy Allen,
' decodes direction of motion, or encoder wheel (see circuit diagram)
' l.e.d.s are attached to P8 to P15 to signal motions
dirs=$FF00 ' high byte is outputs attached to indicator leds
' lo byte is inputs attached to encoder
I var byte ' holds sample of input port with photoxistors
M var byte ' holds memory of past state of inputs
X var byte ' output from routine, bits go high to indicated rotations
Y var byte ' intermediate variable in state machine

' get sample:
I = inL
' process rotation info:
Y = ~(I & M) ' NAND of input and memory states
X = Y ^ M & Y & (M & %01010101 << 1 | (M & %10101010 >>1))
' X = Y ^ M & Y & (I & %01010101 << 1 | (I & %10101010 >>1)) & ~I
' note: I forget why the second commented version of the line is for??
' optional show states:
' debug home,bin8 I,cr,bin8 M,cr,bin8 Y,cr,bin8 X
M = Y ' update memory states
' deal with the result, here just blink an LEDs to indicate rotation
outh = X ' l.e.d.s with rotations ON
outh = 0 ' l.e.ds OFF
goto loop

Game show, state machine


Here is a question that Edwin posted on the Stamps list:

A year ago I made a light panel for "Game Show Nite" at a Camp that took 8 Button inputs and lit 1 of 8 light bulbs (100W) so the game show host could tell who pressed first. It locked out all others after the first person pressed. What they were wondering was if it could detect the first 3 guessers and then flash the light bulbs as follows:
1st guesser fastest flash.
2nd guesser medium flash.
3rd guesser slowest flash
All others locked out.
That way they could know who was next to answer the question if the first person got the wrong answer. I am using a BS2 with the 0-7 pins as the inputs, 8-15 as outputs.

I'm kind of proud of the following, because it reduces the whole program, from detecting the buttons to flashing the lights, to four lines of program code in a loop, with no IFs or branches. It is a "state machine" that takes advantage of the fabulous capabilities of the stamp2 to address chunks of data as elements of an array. An explanation follows the program.

' Tracy Allen,
' pins 0-7 are inputs for 8 pushbuttons
' normally high, low when pressed
' pins 8-15 are outputs for lights
' high level turns on a light
' STATE Variables:
first var byte ' e.g. contestant #3 is first=%00001000
second var byte ' e.g. contestant #6 is second=%01000000
third var byte ' e.g. contestant #0 is third=%00000001
losers var byte ' catch-all for non-placing contestants

win var first ' alias name for "first"
' will address as array
' win(0)=first, win(1)=second, win(2)=third
' win(3)=losers
ix var nib ' index into the array win(ix).

drum var word ' counter for the flash rate
d0 var drum.bit6 ' fastest
d1 var drum.bit7 ' medium
d2 var drum.bit8 ' slowest

dirs=$FF00 ' 0->7 are inputs from pushbuttons, normally HI
' input goes LO as a button is pressed.
' 8-15 are outputs to the lamp controls.

win(ix) = ~inL & ~(first | second)
ix = win(ix) max 1 + ix max 3
outH = d0 * first | (d1 * second) | (d2 * third)
drum = drum+1
goto loop

' explanation:
' The index, ix, starts out at zero, pointing to "first".
' As buttons are pressed, the value of ix advances to
' point to "second" and then "third" and then "losers".
' The index stops at 3, so that all late entries are
' put in the "losers" category.
' Any time a new pushbutton is pressed, the value of win(ix)
' changes from zero to a button-specific value. For example,
' if button #3 is pressed, then win(ix)=:%00001000. The
' statement ~(first | second) helps when the first place and/or
' second place contestants continue to hold down their buttons;
' the state machine ignores buttons that have already registered.
' The statement that starts with "ix=" increments the index
' whenever a new pushbutton is detected, up to 3.
' The bits d0, d1 and d2 are just bits of the counter variable,
' "drum", and they go high and low in the usual binary pattern,
' d0 being the fastest. In this loop, the d0 frequency is
' about 2.5 per second. Multiplying each of these bits times
' "first", "second" and "third", and ORing together the result
' causes the lights to flash by placement order. For faster
' or slower flash rates, choose different bits of"drum".
' The lights start flashing immediately when each button is
' pressed--you can see immediately who is first, without having
' to wait for all three responses. There is a small chance of
' a tie between two contestants. The loop executes in 3-4
' milliseconds, so a tie is unlikely. The scoreboard will show
' ties as two bulbs flashing at the same rate. Press RESET to
' start a new round.
' ---Tracy Allen,


And, it is always gratifying to know it performed in the real world...

Thank You for your code you wrote for My Camp's Quiz Board. It is a big hit! I added the light flash introduction and modified the board to accept pull down resistors on the input. It works flawless. We did have on tie for first place but it just added to the excitement!
Thanks Again,
Ed Stevenson

Matrix keypad scanner as state machine


A matrix keypad is arranged with buttons in rows and columns, so that pressing a button makes an electrical connection between a particular row and column. A 16-key matrix keypad typically has connections arranged into 4 columns and 4 rows, as follows:

 O = open keyswitch
X = closed keyswitch

10kohm x4
| | | | | |
| | | | | | |
| | | | | | | |
| | | | | | | | |
\ \ \ \ \ \ \ \ |
/ / / / / / / / 220ohm |
\ \ \ \ \ \ \ \ <- x8 |
| | | | | | | | |
P8 P9 P10 P11 P12 P13 P14 P15 +5

BS2 port C outputs BS2 port D inputs

In this example a keyswitch is shown ("X") closed at the intersection of the second row and second column When closed it electrically connects pin P9 to pin P14 on the stamp. If P9 outputs a LOW level, then P14 will detect a low level. All the other inputs, P12, P14 and P15 detect a high level due to the 10kohm pull-up resistors to +5 volts.

The 10 kohm resistors are pullups for the inputs, to hold them at a high level unless a switch is closed and a column is made output low under program control. The 220 ohm resistors in series with the pins are there for protection. There might be static electricity, or there might be contention (a short circuit) if Stamp pins on two sides of a closed switch incorrectly are made outputs of opposite polarity. Pullups can also be used on the port C pins, but it is not absolutely necessary.

The PBASIC program works by making the column outputs P8 to P11 LOW one at a time (while keeping the others columns as inputs), and looking at the resulting inputs on P12 to P15. This determines which key or multiple keys are pressed at the moment.

This is usually followed by a decoding step, to take some action like printing a character or dialing a touch tone or starting a machine, that corresponds to the key or key combination or key sequence pressed. The process of scanning the keypad should be thought of as independent from the decoding.

One refinement of keypad scanning is debouncing. A very short tap on a key should not be counted as a true key press. The program should test the keyswitch a couple of times before finally deciding it is really up or down.

It might seem that there is a lot of decision logic to be made to handle all of the different keys and determine how long each of them has been pressed down. However, a state machine can handle the scanning and debouncing of all the keys in parallel. The scanning itself takes only 9 lines of BASIC code. The decoding is shown as a separate subroutine that emits a touchtone and prints a character on an LCD screen when a key is pressed. The debouncing is handled by a series of three word-size state variables. One holds the current state, and two hold the two most recent past samples. Each bit in the words represents the state of one key. For example, bit 3 in each word holds the state (0 or 1) of the third key in the zeroth column, or bit 15 in each word holds the state of the last key in the last column. The state of the corresponding bit in all three words has to agree before the button is registered as down or up. This is sometimes referred to as a "vertical counter", because the bits that count up the state of one switch are in different words, rather than a conventional "horizontal" counter, where all the bits are in one word. Each key has its own bit in each of the state variables. You can see much better how it works if you include the debug statements that are included, but commented out, in the program.

' Tracy Allen,
' scans a 16 key (4x4) matrix keypad
' using state machine for debouncing, all keys in parallel
' The columns are connected to BS2 outputs of port C, P8 to P11
' The rows are connected to BS2 inputs of port D, P12 to P15
' with pull-up resistors to Vdd=+5 volts.
' This routine has two output variables, "keys" and "keyx"
' Bits in "keys" go low after the corresponding key is
' pressed and debounced.
' Bits in "keyx" go high for _one iteration only_ to signal
' a high to low transition (button pushed & debounced)
' of the corresponding key
' In all state variables, each bit corresponds to one key.
' One word is used for 16 keys, in a 4x4 array.
' This uses a lot of variables, but in many applications it is
' possible to reuse most of the variables outside the keyscan loop
' Note that the scan can detect key combinations.
' The decoding step can miss keys only if they are pressed at
' exactly the same instant.

kout var outC ' 4-bit keypad columns, state, if output
kdir var dirC ' 4-bit keypad columns, input or output
kin var inD ' inputs from keypad rows connected to port D
' bit low for key pressed
key0 var word ' state variable, first detection
key1 var word ' state variable, second detection
key2 var word ' state variable, third detection
keyn var key0.nib0 ' address the first detection as nibble array
keys var word ' debounced output, bit low for key pressed
keyz var word ' state variable, previous state of keys
keyx var word ' transition output, bit high one iteration for each press
ix var word ' index for array addressing

dirs=%0000111111111111 ' port D is input, all others output
outs=%0000000000000000 ' start with port C columns output low
' pins P0 to P7 are not used in this program
debug cls ' Clear screen

key2=key1 ' move the debounced states
for ix=0 to 3 ' scan 4 cols by bringing one col at a time low.
kdir = dcd ix ' 0001,0010,0100,1000 in succession
' this makes one column at a time output low
' while the other columns are inputs
keyn(ix)=kin ' read the row inputs into nibbles of key0
kdir = %1111 ' make all columns output (avoid floating inputs)
keys=key0&key1&key2|keys ' key bit 0->1 when all 3 are high
keys=key0|key1|key2&keys ' key bit 1->0 when all 3 are low
keyx=keys^keyz & keyz ' detect change 1->0 (active low keypress)
' optional debug to visualize operation of the state machine
' slows down the operation tremendously
' debug home,bin16 key0,cr,bin16 key1,cr,bin16 key2,cr
' debug bin16 keys,32,bin16 keyx,home
' optional branch to decode keypress, note keyx is transient
if keyx>0 then decode
' pause 30 ' optional delay to slow the scanning
goto scanloop

code var byte ' code variable
code = ncd keyx-1 ' binary encode the most significant key
lookup code,[10,7,4,1,0,8,5,2,11,9,6,3],code ' translate to code
dtmfout 7,[code] ' send as touchtone
lookup code,["0123456789*#"],code ' --> printable character
debug code ' print on screen
goto scanloop

The code can be simplified quite a bit when debouncing is unecessary. Then there is no need for the variables key1, key2 and keys.

' without debouncing
for ix=0 to 3 ' scan 4 cols by bringing one col at a time low.
kdir = dcd ix ' 0001,0010,0100,1000 in succession
' this makes one column at a time output low
' while the other columns are inputs
keyn(ix)=kin ' read the row inputs into nibbles of key0
kdir = %1111 ' make all columns output (avoid floating inputs)
keyx=key0^keyz & keyz ' detect change 1->0 (active low keypress)
' optional debug to visualize operation of the state machine
' debug home,bin16 key0,32,bin16 keyx
' optional branch to decode keypress, note keyx is transient
if keyx then decode
goto scanloop


A case of doors, open and shut


query from the stamps list:

> I have a project that will require the BS2 to be able
> to tell when the state of a pin (set up as an Input)
> has changed from High to Low (Do Something) and from
> Low to High (Do Some Thing).
> What I would like to do is have anywhere from 4 to 8
> inputs to monitor doors in a remote building I have.
> If possible, what I would like to do is monitor the door
> with an input and when the door is opened the input to
> (lets say) pin0 goes from High to low, and at this
> time I want to have the BS2 do something and only do
> it once. The (Do Something) will probably be different
> for different inputs. Some may be the same.

Here is an program for checking all the doors, and it can handle events where two or more doors happen to change state at the the same time.

The program detects transitions in state by using XOR logic between the old state of the pin and the new state, common to all the state machine logic. It also makes efficient use of the NCD operator and the BRANCH command to reduce the main program loop to 5 lines of program statements.

 ' door inputs to P0 to P8
x0 var byte ' old state of doors
x1 var byte ' new state of doors
xx var byte ' transition state of doors
xy var byte ' transition state 0->1

x0=inL ' read states at start

x1=inL ' read new state
xx=x1 ^ x0 ' see if there are any transitions
xy = xx & x1 ' distinguish 0->1 xitions from 1->0
x0=x1 ' update old state
branch ncd xx,[waiting,firstdoor,seconddoor,..,eighthdoor]

xx=xx & %11111110 ' knock down the 1st door bit
branch xy.bit0,[door1opened,door1closed]
' do something
goto checkalldoors ' back to test other doors
' do something
goto checkalldoors

xx=xx & %11111101 ' knock down the 2nd door bit
branch xy.bit1,[door2opened,door2closed]
' do something
goto checkalldoors ' back to test other doors
' do something
goto checkalldoors

' etc etc

Suppose two doors change at the same time, for example, xx=%00010100. The NCD operator returns the index of the highest bit set in a binary value, so NCD %00010100 would return 5 (transition on fifthdoor). That will make the routine branch to the fifthdoor routine, which now knocks down the fifth bit, making xx=%00000100. After doing something for the fifth door, the program returns to the checkalldoors point, where now NCD %00000100 makes the program branch to the thriddoor routine, which knocks down the third bit and does the action for the third door and again returns to checkalldoors. Now xx=0, and NCD 0 = 0 so the routine returns to waiting for the next event.

<top> <index> <home> logo <>