Better debounce algorithms

When I implemented the firmware for a keyboard prototype, I got to learn about the troublesome contact bounce of mechanical switches. Hence, I was in need of a debounce algorithm that fulfills some specific requirements.

First, it must detect any press and release event, to send the appropriate device reports. It also should be efficient in time and memory, with a low reporting latency. After all, there may be more than 100 switches to debounce. Most importantly of course, it must be robust. Even an unexpectedly long bounce or random noise interference should not trigger incorrect events. And for bonus points, it should be simple.

I have found many discussions about debouncing, most notably the often recommended article by Jack Ganssle. But no proposed algorithm was a perfect fit for my use case. Instead, I would like to showcase two alternatives.

Update

Since writing this blog post, I have continued to work on new and improved debounce algorithms. All of them are available in a dedicated test repository. In particular, I used the EvenOdd algorithm for the first official release of the Chrumm keyboard.

PingPong algorithm

PingPong is a variation of the integrator algorithm by Kenneth A. Kuhn. The integrator itself is elegant and robust. However, it requires a separate variable to keep track of the active state.

As an improvement, we can instead encode the active state directly in the count variable. For this purpose, a FLIP threshold is used. Values below FLIP represent the 0 state, values above FLIP represent the 1 state.

constexpr uint8_t FLIP = 6;
constexpr uint8_t MAX  = FLIP*2;

void loop(Test& test)
{
  static uint8_t count = MAX;

  if (test.read()) {
    if (count < MAX) {
      if (++count == FLIP) {
        count = MAX;
        test.report(1);
      }
    }
  }
  else {
    if (count > 0) {
      if (--count == FLIP) {
        count = 0;
        test.report(0);
      }
    }
  }

  test.sleep(1);
}

Like the integrator, this algorithm is very robust against noise. Because a bounce does not completely reset the counter, the latency is very consistent as well. And the combination of the count and state in a small value range allows PingPong to provide excellent debouncing with just a few bits per switch.

StateShift algorithm

Another class of algorithms records the most recent signal history with the shift operator, to detect specific event patterns. Examples are the Alternative Routine by Jack Ganssle, or the Ultimate Debouncer by Elliot Williams. However, stateless pattern-matching is not ideal to detect switch events, because noise can trigger false inputs.

To fix this, the StateShift algorithm stores the active switch state in the upper bit(s), along with the signal history in the lower bits. Events are only triggered when the history is saturated with the opposite of the active state. As a result, the events are guaranteed to alternate and the algorithm is robust against noise.

constexpr uint8_t UPPER = 0b10000000;
constexpr uint8_t LOWER = 0b01111111;

void loop(Test& test)
{
  static uint8_t state = 0xFF;

  const uint8_t current = state & UPPER;
  const uint8_t history = (state << 1) & LOWER;

  state = current | history | test.read();

  if (state == UPPER) {
    state = 0x00;
    test.report(0);
  }
  else if (state == LOWER) {
    state = 0xFF;
    test.report(1);
  }

  test.sleep(1);
}