Algorithm to Debounce Inputs


Input (or key) bounce is a phenomenon where an input change caused by a switch closure can change multiple times in transition from 0 to 1 or 1 to 0.  A change from 0 to 1 can actually transition from 0 to 1 to 0 to 1 (possibly multiple times), eventually settling on 1.  The opposite can also occur, when a switch closure actually causes an input to transition from 1 to 0 (think pull-up), but with many changes in state before settling to 0.  One can imagine the cause, the switch is actually slapping the contact and then bouncing off repeatedly before finally settling on the contact.

An ideal design could have each switch be a single pole, double throw switch with each throw driving the inputs of a J-K flip-flop.  But in designs with small processors/controllers, often the job of debouncing inputs is delegated to software due to cost.

Here is my favorite input debouncing algorithm.  It was inspired by an article on CRCs by Jack Crenshaw.  It seems that the fundamental improvement in his CRC algorithm is using all the bits on logical operations, where a simple minded CRC algorithm trying to mimic the hardware would waste all the bits but one when performing logical operations.

Similarly, a simple minded debouncing algorithm has separate code for each debounced input bit, usually with a counter for each.  But most system designs have more than one input on a port, so it could make sense to improve the design by operating in parallel on all the inputs that share a port. 

The fundamental idea presented here is to periodically update a circular buffer, keeping the last N inputs.  We only set a bit in the debounced result when the bit was 1 in each of the samples.  Similarly, we only clear a bit in the debounced result when that bit was 0 in each of the last N samples.

Note that AND-ing all elements of the circular buffer will generate a result that has a 1 only in a bit position that was 1 in the entire circular buffer.  That result can be OR-ed into the debounced result, setting those bits are stable at 1.  The OR of all the elements of the circular buffer will have a 0 in it only for bits that are 0 in all elements.  Thus, this result can be AND-ed into the debounced output, clearing those bits that are in a stable 0 condition.

The efficiency improvement occurs because each of the logical operations is operating on the entire word width at a time.  Depending on your word size, we are debouncing 8, 16, or even 32 inputs at a time.

Here is the code in C, with a queue length of 3:

Initialization:

debounced_port = 0;

// Initialize a circular buffer of the last three inputs.
samples[0] = 0;
samples[1] = 0;
samples[2] = 0;


Periodically:

// Advance the circular buffer.  Note that moving the data rather
// than changing an index is MUCH quicker in small processors.
samples[2] = samples[1];
samples[1] = samples[0];

// Read all bits of raw undebounced input
samples[0] = IN_PORT;

// "samples" now has the value of IN_PORT over the last three sample periods

// Any bit clear for three consecutive samples will be cleared in the result
all_or  = samples[2] | samples[1] | samples[0];
debounced_port &= all_or;

// Any bit set three consecutive times will be set in the result
all_and = samples[2] & samples[1] & samples[0];
debounced_port |= all_and;



The clean symmetry of this algorithm leads me to believe that this is the solution the computing gods always intended.  :-)

Feel free to use this code as needed, although a reference would be nice.

-Jack Bonn