Accurate quadrature decoding without external clocking

Question

An Incremental Encoder is a linear or rotary electromechanical device that has two output signals, A and B, which issue pulses when the device is moved. Together, the A and B signals indicate both the occurrence of and direction of movement.

Below is a photo of a typical rotary encoder:

The two output signals A and B are square waveforms, which are shifted 90 degrees with respect to each other (are in quadrature) when the encoder is rotated uniformly in one direction.
The timing diagram below illustrates these two signals when the encoder is rotated uniformly forward:

The timing diagram below illustrates these two signals when the encoder is rotated uniformly in reverse (backwards):

A full cycle of the A & B waveforms corresponds to 4 resolution steps of the encoder and collectively it contains two rising edges and 2 falling edges. By the very nature of the quadrature outputs, each edge is straddled by a pulse on the other output line, which facilitates meeting the setup & hold times of edge-sensitive flip-flops and other sequential logic.

In the absence of a real physical incremental encoder, its outputs can be simulated by the following quadrature generator: Note: The signal generator above is a 2-bit binary up/down counter, followed by an XOR gate. This means that a binary counting sequence output of a real absolute encoder can also be converted to a quadrature output (just like that of an incremental encoder) using an XOR gate connected to its 2 least significant bits.

Frequently it is necessary to determine the direction of rotation of the encoder's shaft. The naive method to detect this direction is to use a D flip-flop connected to the A and B outputs as depicted below:
You may observe the behavior of this naive detector in this simulation online.

This naive detector is flawed in many ways. Often, it is unable to detect the direction reversals as soon as possible and is totally blind to consecutive direction reversals (such as those occurring in rotational vibration).

A and B waveforms occurring during rotational vibration of the encoder's shaft:

The naive D flip-flip direction detector is also confused by the following direction reversal scenarios:

The technical publication "Accurate Quadrature Encoder Decoding Using Programmable Logic" by Yassen Gorbounov illustrates this problem and solves it using externally clocked programmable Logic.

The externally clocked solution suffers from the clocking delay and high energy consumption because its internal logic elements (gates, transistors) need to be constantly subjected to an external clock waveform (4x higher than the maximum encoder's output frequency). On the other hand, static signals almost do not cause any power dissipation in contemporary MOS circuits. The external clocking also adds the cost and complexity of a clock generator and its associated logic elements.

The solution presented below avoids an external clock while being immune to incremental encoder outputs generated when it is subjected to the rotational vibration of is shaft as well as direction reversal at an arbitrary moment.

The A and B signals during consecutive reversals are marked by the yellow rectangle on the timing diagram. You may observe its behavior in the following simulation online.

Theory of operation: Each D flip-flop functions as an edge detector. Two D flip-flops detect the rising and falling edge of the A signal and two D flip-flops detect the rising and falling edge of the B signal. The level of the other input line (the non-clocking line) is gated by the output of these D flip-flops using an AND gate and a NOR gate in order to create a 2-bit command (each active high) for the final RS flip-flop. The AND-OR gate combo (AO) is used to sense when the final RS flip-flop has executed this command and as soon this is detected, an asynchronous reset signal is applied to the D flip-flop's reset pin (active high). This "reset" loop is the basis of stability of this circuit and its immunity from logic propagation delays and race conditions. This scheme is repeated 4 times for each of the rising and falling edges on the A and B lines and the 4 commands for the final RS flip-flop are merged by the two 4-input OR gates. Only one command is active at any one time.

This quadrature direction detector is quite complex for a circuit that takes only two A & B inputs and outputs one binary signal.
QUESTION: Is a simpler self-clocked circuit with identical functionality possible?

( "simpler" means a design with fewer transistors/transfer-gates and therefore smaller silicon real-estate. This usually means fewer logic elements or less complex logic elements, e.g:. a NAND gate is less complex than a D-flip flop as it uses fewer transistors/transfer-gates. )

NOTES:

1. The practical frequencies being output by the encoder are in the range of 0Hz to 250kHz.
2. The usage of any signals appearing inside the the 2-state Quadrature Generator used to simulate the encoder's output is not acceptable in an improved solution.
3. Solutions relying on RC filters or intentional delay elements are not acceptable.
4. Only self-clocked solutions are acceptable

pt.4 rules out all externally clocked solutions including all microcontroller-based solutions since even an on-chip clock generator constitutes an external clock (external to the input signals).

Answer 1

The original question asks for a circuit which extracts the direction information from a pair of encoder signals (i.e. quadrature signals). The question asks that the circuit not employ clocks, nor should it employ delays. I interpret the latter request as the circuit should not include intentional delays. This rules out creating short pulses on the rising or falling edge of a signal by creating an intentional race condition.

The sort of circuit that is described seems to be an asynchronous finite state machine. Such an asynchronous finite state machine that decodes the directional information from quadrature signals looks like this:

The flow table for this asynchronous finite state machine is

With encoded states, the asynchronous finite state machine looks like this:

The corresponding excitation table looks like this:

Fortuitously, we can fill in the "don't care" cells in our excitation table in such a way that the whole table becomes symmetric around the horizontal line that separates the \$x=0\$ half from the \$x=1\$ half. Like this:

This gives us equations for the state variables in terms of inputs and previous state variables.

$$X = A'B'z + A'By + ABz' + AB'y'$$ $$Y = AB + Ay + By$$ $$Z = A'B + A'z + Bz$$

The equations for \$Y\$ and \$Z\$ describe a Muller C-element. The behavior of a Muller C-element is to latch the last consensus value of its inputs.

Because the inputs A and B come from a quadrature encoder, we feel safe in assuming that A and B never transition together, but rather, there is a time between a transition of A and a transition of B (and vice-versa). Further we assume that the time between A transitions and B transitions is long enough for the circuit to reach a steady or stable state before each new transition. That is, we assume that the asynchronous finite state machine operates in fundamental mode.

Note that in a transition of \$A\$ or \$B\$ in which \$x\$ changes, neither \$y\$ nor \$z\$ changes. Furthermore, only one of \$A\$ or \$B\$ changes at a time.

The equation for \$X\$ will be implemented as products feeding a nor latch.

$$S= A'B'z + A'By + ABz' + AB'y'$$ $$R= A'B'z' + A'By' + ABz + AB'y$$

Using the above implementation equations, we arrive at the following circuit, which uses neither clocks nor intentionally added delays.

This circuit has been implemented in Falstad and appears to work correctly. If one is curious about the default behavior, I set the A and B channels to different frequencies, and gave a phase shift to the A channel. This allows the order in which edges occur to change. Sometimes a rising A edge will precede a rising B edge and sometimes it will follow it. Similarly with falling edges. When two A transitions occur with no intervening B transition, then X transitions, and likewise with A and B reversed.

Answer 2

Possible XY problem?

tl, dr: yes, it's possible to make a simpler, 'accurate', non-clocked quadrature decoder, that is, one that reliably detects all the possible state transitions and infers the right direction information from them.

Decoding a quadrature waveform is a CPLD-sized task. This could very easily fit into a Silego Greenpak, Coolrunner CPLD, or other small programmable logic device.

Here's a Silego example: https://www.renesas.com/us/en/document/apn/1101-unclocked-quadrature-decoder

The Silego design outputs ‘count up’ and ‘count down’ pulse trains. It doesn't have a 'Direction' bit, but could easily add an S-R latch to make one.

The key technique in play here is edge detection. They use A and B plus delayed versions of A and B to detect state transitions. Based on the change in state they infer encoder direction. Using delays avoids the free-running clock, as you asked.

While you pre-emptively vetoed delays (or at least, ‘variable delays'), it's nevertheless a sound methodology for edge detection. All the ‘accurate’ designs referenced here use it, including Silego’s, your example and my improved version (see BONUS below.)

Speaking of which…

Your Example Design

Your example circuit uses delays on A and B. The A and B signals clock flip-flops, then self-reset a short time later. The clock-to-Q + logic turnaround + reset time is the delay, which produces a pulse. This pulse gets fed to either the ‘forward’ or ‘reverse’ OR4 gates to produce 'count up' and 'count down' pulses. Finally, the count pulses set an S-R latch to show direction.

So it works. But, there are issues. And, it could be simpler.

First, the clock-then-reset pulse scheme is really, really sketchy. It’s a glitch generator that's neither consistent or reliable. It's entirely dependent on the internal speed of the flop and the feedback gates, and could thus vary considerably with process, voltage and temperature.

Second, the circuit is pretty inefficient overall. There's lots of unnecessary gates and flops that could be done away with (as we'll see later in the BONUS section below.)

Third, it has an outright bug: if the Direction flop is set to the wrong state, it can fail to control the resets properly, resulting in erratic behavior on the count pulses and Direction bit.

Picking this design apart further, I realize that there's redundant logic for that flop reset stuff. There is no need to select which output is doing the resetting based on the direction state; we can always just reset the flop. What they did there serves to add two gate delays from clock-Q to reset pulse, which while helpful, misses the point.

Here is a version that simplifies all that, while showing more clearly what they're doing (simulate it here):

When you analyze the flop behavior, you'll see they're being fired off on every edge they're set up to detect and being reset afterward, every time. And only one fires at a time. Knowing that, we can take out some redundant stuff.

Like what? The pulse commutation is done with a demux instead of gates. I did this for clarity, but it also is smaller (fewer transistors).

Each flop has mux on its reset line, which was unnecessary. Instead we take the Q output, insert a delay (3ns) that replaces the output gating (demux) and deleted mux delays (3 gate delays total), and use that to reset the flop. Side benefit: no feedback state issues.

Simulation note: as near as I can determine, Falstad models its digital elements with a default 1ns delay. So the resulting pulse should be T(clock-q) + 3ns + T(rst-q), or 5ns.

Encoders in the real world

What if you’re designing a real part for use in the field? Encoders often must work in noisy environments, so systems working with them include some noise filtering for A and B.

Another issue is power-on state before movement has occurred. This isn’t a problem if you only care about incremental movement (such a a control knob). In contrast, it matters a lot for a closed-loop servo control: a mismatch in indicated direction can cause your system to run away.

System designs inhibit loop control until the servo has been indexed, that is, placed in a known mechanical state. The controller will waggle the actuator to find index (or at least, test for signals), and set up all the position information once it finds it.

Knowing this, you can kind of see why those HCTL-20xx parts went obsolete (aside from Broadcom’s typical SKU-pruning.) By the time you design a complete, robust and safe servo solution, you come to realize that you need a lot more than just quadrature decode. You need some intelligence to manage the system too.

And that's where a microcontroller comes in: it not only can absorb the decoding function, but also all the servo management, too.

---

BONUS As promised, a simpler, yet accurate quadrature decoder using delays on A and B to detect transitions (simulate it here).

Discussion

I claim the above design meets your request for 'accurate' and 'simpler’. It is functionally identical to your example design, while using a different approach as well as incorporating some improvements.

Let's talk about 'simpler'. That can mean fewer gates or fewer IC packages. But when you get right down to it it's transistors that matter since this equates to silicon area. We'll get into that in a bit.

Theory of Operation

How does this thing work? tl, dr version: by detecting current vs. previous state using delayed versions of A and B, making pulses and steering them to the right place. That's how the Silego design works, as well as your glitching-flop design (and my refinement of it.)

The edge detection / state decoding is an all-combinatorial path, rendered to make it clearer to understand as well as efficient. In an actual device it would be rendered differently (as a LUT, or as a sum-of-products), but nevertheless still as stateless combinatorial-only logic.

We start the design process by inspecting the encoder output sequence in each direction. There are 8 possible state transitions: four forward, four reverse:

• FWD: A,B: 00 -> 10 -> 11 -> 01 -> 00
• REV: A,B: 00 -> 01 -> 11 -> 10 -> 00

Diagram:

(From here)

The encoder output has two useful properties that help our cause:

• Only one signal changes at a time
• The changes occur in specific order, depending on direction (no illegal transitions to worry about)

We take advantage of these properties to find a state transition, encode it as a pulse, then make a decision about what to do with the pulse depending on the state of the other, not-changing input signal.

We use A and B and their delayed versions to detect rise and fall of each signal, forming pulses at each signal toggle. These are the state changes. We commutate the state-change pulses with muxes, routing them to the Count FWD and Count REV counter pulses. These pulses from the muxes set the Direction latch and can drive an up/down counter with separate clocks.

The additional AND gate makes a combined Count All that, with Direction, can drive an up/down counter directly.

These are the state transitions and how they're routed:

Forward:

• A,B 00 => 10 (A-rise, B low): send pulse to FWD
• A,B 10 => 11 (B-rise, A high): send pulse to FWD
• A,B 11 => 01 (A-fall, B high): send pulse to FWD
• A,B 01 => 00 (B-fall, A low): send pulse to FWD

Reverse:

• A,B 00 => 01 (B-rise, A low): send pulse to REV
• A,B 01 => 11 (A-rise, B high): send pulse to REV
• A,B 11 => 10 (B-fall, A high): send pulse to REV
• A,B 10 => 00 (A-fall, B low): send pulse to REV

Just A, B and their delayed versions (4 signals total) give us all the information we need to sense the direction immediately at each state transition. We absolutely don't care what the previous direction sensed was.

What’s improved?

A bunch of stuff.

• No glitch generators: controlled pulse size

Gone are those flip-flops and their sketchy glitch-generation behavior. The pulse size is set primarily by the fixed delay - in my design, at 50ns. This can be easily tailored depending on the speed required by setting the delay.

The delay can also be done digitally, yes, with a sampling clock. In a real system with noise filtering done digitally, this would come for the cost of one FF each for A and B delay.

• No feedback state / possible mismatch

In your example, the Direction signal is fed back to do pulse commutation. I noticed that I could make your design get ‘stuck’ in an illegal state if Direction gets out of sync with the motion history. This produced erratic results.

This is impossible with my design, which only counts on the input state.

• Clock pulses low, Direction flop low-triggered (NAND latch)

I did this to stage the setting of Direction on Count All low, 50ns before the rising edge. This creates setup time for Direction, so it and Count All can drive an up/down counter directly and give a reliable count.

• Portable design

Using only combinatorial logic and explicit delays gets rid of the flops in the decode path. It’s all just logic that can be expressed in various ways: in an FPGA as two 4-input lookup tables; in a CPLD as two 4-input sums-of-products.

• Ready for external clock

Finally, while my design as shown doesn’t use a sampling clock, it could very easily use one and reap some benefit: the A and B delays would become just another flop at the end of the A and B synchronizer / noise filter stages. Then the output pulse width would be precisely one sample clock wide.

And what about power, really? For a slow system (like a computer mouse or control knob) the the external clock rate can be pretty low. So the dynamic power consumed by the flops would be negligible.

A fast system by its nature would be high power anyway, so it's hard to make the clocks-consume-more-power argument in context of system power. Further, such systems will be noisy and want digital filters on A and B, like those provided by the HCTL-20xx devices, to improve reliability.

Is it simpler?

You bet. Let's compare.

My solution uses:

• 2 delay buffers (4T each => 8T)
• 2 NOT (2T each => 4T)
• 2 NAND2 gates (4T each => 8T)
• 2 OR2 gates (6T each => 12T, shown as neg-logic NAND)
• 2 4:1 muxes (12T each => 24T)*
• 2 NAND2 (4T each => 8T, wired as RS latch)

Total: = 10 gates + 2 mux, 64T

*The 4:1 muxes weigh in at 12T per since they're made from transmission gates, and we can take advantage of the fact that there are inverters available on A and B. I don't show that here as it made the drawing more complicated.

Your solution has:

• 14 AND2 (6T each => 84T)
• 4 NOR2 (4T each => 16T)
• 4 OR2 (6T each => 24T)
• 2 OR4 gates (10T each => 20T)
• 4 DFF with reset (24T each => 96T, assuming 6 gates per)
• 2 NOT (2T each => 4T)
• 2 NOR2 (4T each => 8T, wired as RS latch)

Total 36 gates, 252T

Ouch. What's particularly painful are those DFFs and 2:1 multiplexers.

Do they work the same?

Your sim has the Direction issue, which doesn’t occur with my solution since it doesn't have any state feedback.

Your sim would make really narrow ‘ghost’ pulses of indeterminate width if implemented with modern fast logic. My design uses a fixed, determinate delay, and so forms a useable clock, with guaranteed setup time for the counter’s up/down control.

Other than that, the two work identically, including the ‘vibrating shaft’ corner cases of just A or B toggling.

And Just To Stir The Pot Some More

Quite possibly, the simplest design yet (simulate it here)

It's not totally original. It's a conversion of a clocked design, like this one:

(from here)

Seems to work.

Complexity:

• 2 delay buffers (4T each => 8T)
• 3 XOR2 (6T each => 18T)
• 1 NOR2 (4T)
• 1 NOT (2T)
• 1 DFF (18T)

Total: = 7 gates + 1 DFF, 50T

And while I'm at it, a further simplification of the mux-oriented design (simulate it here):

Let's tally it up:

• 2 delay buffers (4T each => 8T)
• 3 XOR2 (6T each => 18T)
• 2 2:1 mux (6T each => 12T)
• 2 NOR2 (4T each => 8T)

Total: = 6 gates + 2 2:1 mux, 46T

Whoa, an even simpler design based on this article

Their diagram:

My Falstad version (simulate it here)::

And what's the score?

• 2 delay buffers (4T each => 8T)
• 2 XOR2 gates (6T each => 12T)
• 2 NOT gates (2T each => 4T)
• 2 NAND2 gates (4T each => 8T)
• 2 NAND2 (4T each => 8T, wired as RS latch)

Total: 10 gates, 40T

Answer 3

The circuit depicted below is a friendlier rendition of the circuit described in the accepted answer.

You can see its working simulation online here.

In practice this circuit can be implemented with the dual 74HC153 multiplexer and the 74HC239 demultiplexer (with the \$\overline{G}\$ input tied low in order to make into a 2-bit decoder) and 3 NOR-based SR latches, which feature active-high inputs.

Also, in practice the logic of this circuit can be inverted and implemented with the dual 74HC153 multiplexer and the 74HC139 demultiplexer (with the \$\overline{E}\$ input tied low in order to make into a 2-bit decoder). The 74HC139 features active-low outputs which can be matched by NAND-based SR latches which feature active-low inputs. The 74HC279 chip contains 4 such SR latches. This makes this circuit implementable with 3 standard logic chips (see here) ...or with 60* transistors/TGs with ASIC.

*) counting the 2-bit decoder as 8TG, counting each Mux without its two inverters as 12TG, counting each inverter as 2T, counting each NAND2 as 4T.

Note:
If your system allows for the usage of intentional delay elements, then Hacktastical's design is a simpler circuit (40T) for accomplishing the same task.

Answer 4

As long as the pulses have guaranteed minimum spacing between transitions (whether on the same channel or between two channels), there's no problem with a basic combinatorial decoder feeding a state latch. The timing requirements regarding setup and hold will be upheld as long as that minimum spacing is good enough.

Things get more interesting when the inputs can be glitchy. Now we need some "arbitrary" delays, because whatever consumes these outputs won't be able to react infinitely fast. Assume we had infinitely fast logic to process the quadrature inputs: glitches by definition don't exist. But downstream logic consuming our generated outputs is not infinitely fast, even if our own logic can act "as if" gliches were nothing to it. We deal with glitches and timing violations, but the output can not propagate them out. So yes, the logic must have a way of measuring time to ensure that the outputs don't flip too fast! Usually this time will be measured by delays through inverters or other non-sampled delay line building blocks. No other way around it, I'm afraid.

The basic building blocks that deal with unconstrained inputs must be inherently metastability-free, i.e. when faced with two racing inputs, they must select one of them - which one doesn't matter, but only one must be selected and the other suppressed. That's what arbiters do. Those can be then used to implement e.g. T latches that, when faced with a pulse, will either toggle or not toggle, but never fail due to metastability.

So, if someone asked me to build this using any sort of logic - whether discrete CMOS or TTL, or transistor-level CMOS, it would need to have MrGO (Seitz) arbiters or similar blocks that don't propagate metastability. There are several in the literature, but I'm intimately familiar with MrGO, as I'm actually using it in hobby projects. I would trust building blocks that have been implemented in hardware and tested through trillions/quadrillions of racing inputs without malfunction.

Before building the actual circuit out of a sea of gates or out of CMOS transistors or whatever, you'd have to first validate the most basic arbiter building block. The techniques that afford such validation without exposing gigabit signals off-chip are varied. One good example is the Weaver chip from Asynchronous Research Center at Portland State. Their approach to debuggability is quite portable and ingenious. It works well at smaller scale as well - just run it longer :)

I have to spend a bit more time testing arbiter-based latches to come up with a working implementation, but as far as I'm concerned there's always going to be arbitrary "delays". Either you use external glitch filters, that have a "delay" that determines minimum pulse width they'll pass, or you use async logic that has delay lines that filter output state transition rate, or something to that effect. And if you want proven de-glitchers, asynchronous digital logic (nothing to do with combinatorial logic!) is the domain at least part of the problem belongs.

The other answers deal well with sanitized inputs, but can't handle metastability due to glitches or invalid transitions, and that's always where problems lie. There's also some thought that has to be put into determining error recovery strategy. Suppose we detected an invalid transition: both A and B have flipped within a small window we deem "too short to be valid". What next? We probably don't want it to be ignored, but to proceed through recovery states that can classify the problem as either common-mode glitch, i.e. the inputs will both recover shortly, or as a major malfunction, where the system has to go into acquisition mode and wait for a certain number of valid transitions until it deems the input valid to produce outputs and inform the signal consumer of that fact. The outputs must not only be pulse and direction bits, but also error flags that are timing-sensitive. So, again, very much arbitrary timing constraints are imposed, much longer than how quickly the signal conditioner logic could toggle.

In fact, for a valid encoder input, we must have an arbitrary upper frequency limit, and this limit has to be detected and enforced in a race-/glitch-free manner as well.

So IMHO the "basic" solutions are not robust. Maybe they don't have to be robust, but if you want robust, this is a wee bit more complicated problem than it first seems. Including error recovery, the state table has way more states than just 8!

Industrial strength quadrature decoders are surprisingly complex beasts. Those that aren't are quite easy to get to produce garbage output presented as valid in spite of garbage input. Maybe that's OK. Maybe not. But the easy way out is mostly trivial, so out of scope of this answer.

to be continued...