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 tiny (PIC) 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