Fast Debounce

These files include a number of functions that efficiently perform debouncing operations on word-size hardware inputs. The algorithm is described in this document; the algorithm is generally applicable and most readily implemented in assembly language. The Assembly language code provided is specific to the 8051 family of microcontrollers. The code is provided in a Keil C51 shell, but all the functionality is expressed in assembly language and the code may be readily adapted to any development environment for 8051 family processors. A test harness is included.

Discussion

Debouncing of input signals is necessary when reading an input device that is prone to bouncing - that is, the input changes state more than once when the actual value to be read changes state. Examples of bouncing include the reading of mechanical push buttons. Causes of such bouncing may be the mechanical springing of contacts, contacts wiping together giving variable resistance as they do so and analogue inputs having values that are briefly in an indeterminate logic state.

A typical method of debouncing an input is to read the input with a period significantly less that the period within which a change in the state of the input needs to be registered internally in the CPU. A counter is used to ensure that a change of an input is not registered until that change has been continuously present for some pre-determined period of time - time enough for the input to settle to its true state.

Debouncing of inputs is potentially a resource hungry function and debouncing algorithms are frequently implemented within interrupt service routines (ISRs). Therefore, algorithms that perform debouncing functions efficiently are of interest.

Rather than implementing a separate counter for each input, it is possible to debounce several inputs simultaneously by using so-called vertical counters.

A regular counter is simply implemented as a binary value held in a word of memory that is arithmetically incremented. Vertical counters are different, each bit of each counter is held in a different word of memory - each word holding bits of the same significance for different counters. It turns out, perhaps surprisingly, that vertical counters can advantageously be used for purposes such as debouncing inputs - provided the number of bits in the counters is small and significantly less than the word size. For example, 8 vertical counters each of 4 bits might have the following states:

vertical_counter_d:     00000001
vertical_counter_c:     00001111
vertical_counter_b:     00110110
vertical_counter_a:     01010101

Where, vertical_counter_d is a word holding the most significant bits of the vertical counters. Which gives 8 vertical counter values of 0, 1, 2, 3, 4, 7, 10 and 13. An example of debouncing using vertical counters is provided by the C function fast_debouce_4_stage_counter().

However, the advantage of vertical counters rapidly diminishes as the size of the counters increases. The reason for this is the increased overhead of dealing with carries when the counters are arithmetically incremented.

Linear Feedback Shift Registers (LFSRs) provide an alternative to arithmetic counters. For an introduction to LFSRs see here:

http://www.newwaveinstruments.com/resources/articles/m_sequence_linear_feedback_shift_register_lfsr.htm#Table%20of%20M-Sequence%20Feedback%20Taps

When an LFSR is incremented, it changes state in a non-straightforward arithmetic way. None-the-less, a maximum length LFSR of n-stages will step through (2^n)-1 discreet states (just one state less than an arithmetic counter of the same length). The key advantage of an appropriate LFSR is that implementing the feedback carries a much lower overhead than dealing with the carries in a counter.

The following table lists the states for maximum length, Fibonacci form LFSRs with 4, 5 and 6 stages:

                4-stages5-stages6-stages
                [4,3]   [5,3]      [6,5]
Initial state:  1011      10111 101111
                1001    10011       100111
                1000    10001       100011
                0100    10000       100001
                0010    01000       100000
                0001    00100       010000
                1100    00010       001000
                0110    00001       000100
                0011    10100       000010
                1101    ... ...
                1010    11010       111010
                0101    01101       011101
                1110    11110       111110
                0111    01111       011111
Final state:    1111        11111   111111

Several LFSRs may be implemented vertically - that is, each bit of each LFSR is in a different word.

Note that LFSRs of 3, 4, 5, 6, 7, 8 or 11 stages can be implemented with only two feedback taps.

Implementation

The algorithm is as follows:

        Increment the LFSRs.
        Identify input bits that have changed.
        Reset LFSRs for bits that have not changed.
        Register changes.

Most microprocessors have instruction sets that lend themselves to efficient implementation of this algorithm.

Increment the LFSR:

Incrementing a software implementation of a Fibonacci form LFSRs can be broken down into two steps. First all the bits are shifted to the right, for vertical LFSRs, this means shifting all the words to the right and this may be achieved by successive exchange instructions. Secondly, the feedback taps require that the least significant bit of the LFSR is feed to the most significant bit and if the least significant LFSR bit was set, certain LFSR bits are complemented; for vertical LFSRs this may be achieved with a move instruction and one or move exclusive-or instructions.

Identifying bits that have changed:

This is done by exclusive-oring the source of undebounced bits with the already debounced bit states. In the example code, the source of undebounced bits is simply a word in memory, but this could be a direct read of a hardware input register. Note that the source is read exactly once for each invocation of the function, this is an important feature of all such functions that read directly from hardware.

Reset LFSRs for bits that have not changed:

For those inputs that have not changed, the associated LFSRs must be reset to their start value. The start value for the LFSRs can be any value such that the required number of increments of the LFSR are needed for the LFSR to reach the all-ones state. For the maximum number of counts before the LFSR reaches the all-ones state, the start state needs to be the all-ones state.

Register changes:

Those inputs bits that have changed and for which the associated LFSR is in the all ones state can have their states registered as undebounced.

8051 Implementation Notes

In common with most microprocessors, the 8051 instruction set is well suited to efficient implementation of the algorithm described.

Examination of the code will reveal that for each extra LFSR stage beyond 4, only three additional instructions are required. This will be true for all implementations that use LFSRs requiring only two feedback taps. One extra instruction will be required for each additional feedback tap.

Real-life implementations of debouncing functions require the hardware inputs to be sampled periodically. Typically a debounce algorithm will be implemented in an Interrupt Service Routine. The code presented is both quick and uses only the accumulator and is therefore well suited to ISR implementation.

Real-life implementations will require that the period of invocation and number of counts before an input state change is registered, are carefully chosen to match the circumstances.