Primitive Flow Table

Asynchronous circuits, which operate without a central clock, offer a natural and efficient way to process information based on events. Their event-driven nature, however, makes their behavior complex to describe and design. This creates a knowledge gap: how can we systematically translate a desired behavior—a system that remembers, sequences actions, or resolves conflicts—into a reliable hardware design? The answer lies in a foundational design tool known as the flow table, which acts as a precise map of a circuit's reactive logic. This article demystifies this powerful concept, starting with its most detailed form: the primitive flow table. The first chapter, "Principles and Mechanisms," will unpack the structure of the flow table, defining states, transitions, and the fundamental rules that govern them. Following that, "Applications and Interdisciplinary Connections" will demonstrate how these principles are applied to create the building blocks of modern digital systems, from simple memory to complex communication protocols.

Imagine a world without a conductor, a symphony orchestra where each musician plays their part not by watching a baton, but by listening to the notes of their neighbors. This is the world of asynchronous circuits. Unlike their synchronous cousins, which march in lockstep to the beat of a master clock, asynchronous systems are event-driven. They react, they respond, they spring into action only when an input changes. This makes their behavior more complex to describe, but it also reveals a more natural and fundamental way of processing information.

To navigate this world, we need a map. Our map is not one of geographic terrain, but of logical behavior. It's called a ​​flow table​​. This simple-looking chart is the key to understanding everything about how an asynchronous circuit works. But before we unfold this map, we must agree on a crucial rule of the road, a simplification known as the ​​fundamental-mode​​ model: inputs change one at a time, and the circuit is always given enough time to settle down and find its footing after one change before the next one arrives. This rule prevents the chaos of multiple things happening at once and allows us to reason about the circuit's behavior step-by-step.

A flow table is deceptively simple. The rows represent the circuit's internal ​​states​​—its memory of what has happened in the past. The columns represent every possible combination of its external inputs. At the intersection of any row (present state) and column (present input) is an entry that tells us two things: the ​​next state​​ the circuit will move to, and the ​​output​​ it will produce.

Think of it like a guidebook for a strange, magical building. Each room is a state. On the walls of each room are signs corresponding to different weather conditions (the inputs). If you are in the 'Blue Room' (present state) and you see the 'Rain' sign (input), the guidebook entry tells you: "Go to the 'Green Room' (next state) and put on a coat (output)."

This journey from one state to another is the heart of asynchronous dynamics. A circuit is said to be in a ​​stable state​​ when it's at rest. In our guidebook, this would be an entry that says, "If you're in the Blue Room and see the 'Sun' sign, stay in the Blue Room." In a flow table, we denote this by circling the state or showing that the next state is the same as the present state. For any given input, the circuit will remain in this stable state indefinitely.

But what happens when an input changes? The circuit is suddenly in an ​​unstable state​​. The guidebook now points to a different room. The circuit must follow this instruction, transitioning to the specified next state. This transition might lead directly to a new stable state, or it might trigger a sequence of internal state changes, like moving through a series of corridors, until a new resting place—a new stable state—is finally reached.

Let's trace a short journey. Suppose a circuit is resting comfortably in state S0 with inputs 00. The output $Z$ is 0. Now, the input changes to 01. The flow table for state S0 at input 01 points to a new state, S1. The circuit transitions to S1. We check the table again: for state S1, the entry under input 01 is S1 itself. It's a stable state! The journey is over. The circuit has settled in S1, and its new stable output is whatever the table specifies for that condition. This dance from stability through instability to new stability is the fundamental rhythm of an asynchronous machine.

To begin designing a circuit, we start with the most detailed map possible: the ​​primitive flow table​​. The word "primitive" here means fundamental, or irreducible. Its defining characteristic is a strict rule: ​​each row can have only one stable state​​.

This means each row describes a single, unique stable condition in the circuit's life. It's like having a separate, dedicated instruction page for every single resting spot in our building. State 'A' might be where the circuit rests with input 01, while state 'B' is where it rests with input 11. They get their own separate rows in the table.

This rule has a fascinating consequence. If a row is defined by its stability under input 01, what do we write in the column for input 10? According to our fundamental-mode assumption, inputs cannot change from 01 to 10 in a single step, as that would require two bits to change simultaneously. This transition is "illegal." Therefore, we have no need to specify what happens. The entry is a ​​don't care​​, often marked with a dash (--). Our map simply has no path for these forbidden journeys.

This is where the true beauty of the concept reveals itself. A flow table isn't just a dry specification; it's a way of capturing a story. It's a logical poem about behavior. How do we write it?

Let's start with something trivial: a simple inverter where the output $z$ is always the opposite of the input $x$, or $z = \overline{x}$. To build its primitive flow table, we ask: what stable conditions does this circuit need?

• When the input is held at $x=0$, the output must be $z=1$. This requires a stable state, let's call it S0, that exists for input 0.
• When the input is held at $x=1$, the output must be $z=0$. This requires another stable state, S1, for input 1. And that's it. We only need two stable states to fully describe this behavior. The primitive flow table would show that from state S0, a change in input to 1 sends the circuit to S1. From S1, a change to 0 sends it back to S0.

Now for a more subtle story. Let's design a circuit where the output $z$ becomes 1 if and only if input $x_1$ is 1 and input $x_2$ has just changed from 0 to 1. At all other times, $z$ must be 0.

Think about this. The output depends not just on the current inputs, but on their ​​history​​. The input combination $x_1x_2 = 11$ must produce a different output depending on how it was reached. This is the essence of what a "state" is for: it's the circuit's memory.

Let's trace the logic to build the table:

1. We'll need stable states for all the "boring" conditions where $z=0$. This gives us one state for each input combination 00, 01, 10, and a state for 11 when nothing special has just happened. That's four states so far.
2. Now, consider the critical event. The circuit is resting in the stable state corresponding to $x_1x_2=10$ (let's call this state S_TEN). Its output is $z=0$.
3. Suddenly, $x_2$ flips from 0 to 1. The input is now $x_1x_2=11$. The circuit must produce an output of $z=1$. To do this, it must enter a new state, let's call it S_PULSE, whose defining characteristic is that its output is 1.
4. But this $z=1$ output is momentary. If the input remains 11, the output should return to 0. This means S_PULSE cannot be a stable state for input 11. It must be a transient state. The flow table must specify that from S_PULSE, with the input still 11, the circuit immediately transitions to yet another state, say S_ELEVEN, which is stable for input 11 and has an output of $z=0$.

Do you see the elegance? To remember that a specific transition just occurred, we invented a temporary state, S_PULSE, that exists only for a moment to generate the required output before settling into the normal, quiescent state for that input. The state isn't just a label; it is the physical embodiment of memory. In total, this seemingly simple behavior requires a minimum of five distinct states to be described correctly.

As we fill in our flow tables, we might notice two different styles of specifying the output. This distinction gives rise to two "flavors" of state machines.

• In a ​​Moore machine​​, the output is solely a function of the present state. If you are in the 'Red Room', the lights are always red, no matter what the weather is outside. In a flow table, this means all specified output entries in a given row are identical.
• In a ​​Mealy machine​​, the output depends on both the present state and the present input. In the 'Red Room', the lights might be red when it's sunny but blue when it's raining. This is represented in a flow table when outputs within the same row differ from one column to the next.

Mealy machines are more general and can describe more complex behaviors, such as producing an output only during a transition, not just upon arrival in a new stable state. This subtlety is crucial. Two circuits can appear to behave identically for a long sequence of inputs, producing the same stable outputs, but a single transition might reveal a difference in their transient, Mealy-like outputs, proving they are not functionally equivalent after all.

The primitive flow table, for all its descriptive power, is just the first draft. It is a complete but often redundant account of the circuit's logic. If we look closely at the table from our edge detector example, we might find that several of the states are, from an external observer's point of view, interchangeable. They have the same outputs and their transitions lead to equivalent future behaviors. We call such states ​​compatible​​.

The art of asynchronous design doesn't stop at the primitive table. The next step is an optimization process: to identify all compatible states and merge them. This collapses the large, detailed primitive table into a smaller, more efficient ​​merged flow table​​. This merged table is what we then use to build the actual hardware of logic gates and feedback loops.

The journey from a simple verbal description to a physical circuit is a process of translation and refinement. We begin with a story. We capture that story in the raw, exhaustive detail of a primitive flow table. We then polish and condense that table by finding and merging its redundancies. At each step, we gain a deeper appreciation for the intricate dance of logic, time, and memory that lies at the heart of computation.

We have spent some time learning the formal rules of the game—the structure of a primitive flow table, the meaning of stable and unstable states, and the discipline of the fundamental-mode model. This is the grammar, the syntax, of the language of asynchronous circuits. But a language is not just its grammar; its true power and beauty are revealed in the stories it can tell and the structures it can build. Now, let's take this new tool and see what we can do with it. Let's see how this seemingly simple table of states and transitions becomes the blueprint for the intricate dance of logic that powers our world.

At its very core, an asynchronous circuit that does anything interesting must have memory. It must remember what has happened in the past to decide what to do in the present. The most basic form of memory is the ability to hold onto a single bit of information—a '0' or a '1'. How can a circuit without a clock remember anything?

Consider the challenge of a simple toggle. We have one input button, $x$, and one output light, $z$. We want the light to flip its state—from off to on, or on to off—every time we complete a full press-and-release of the button. If the light is off and we press the button, nothing should happen yet. It's only when we release it that the light should turn on. The circuit has to remember that the button was pressed. A primitive flow table reveals how this is done. It shows that to accomplish this seemingly simple task, the circuit needs at least four distinct internal states: a resting state with the light off, a state for when the button is pressed (but the light is still off), a new resting state with the light on, and a state for when the button is pressed again (with the light still on). The table maps out the full cycle, capturing the history of the input in its sequence of states.

This idea extends directly to the fundamental building blocks of all computer memory. A D-type latch, for instance, is a device that "listens" to a data input, $D$, and captures its value when a clock signal, $C$, commands it to. How does it know when to listen? A negative-edge-triggered latch listens at the precise moment the clock falls from 1 to 0. At all other times, it steadfastly ignores the data input and holds its stored value. Describing this with a primitive flow table demystifies the magic. It requires a network of states that track the values of both $D$ and $C$, guiding the circuit's output $Q$ to either hold its value or update it, purely based on the sequence of input changes. The flow table is the precise choreography for this data-capturing ballet, forming the asynchronous heart of synchronous memory systems.

With memory comes the ability to enforce rules. In the real world, this is often a matter of safety. Imagine a powerful industrial press that must only operate when the user has both hands safely on two separate buttons. Simply checking if both buttons are pressed isn't enough; what if the operator tapes one button down? A far safer system demands that the buttons be pressed in a specific order.

This is a problem of sequence detection. The system must not only know the current inputs but also the path it took to get there. Let's say the correct sequence is pressing button $x_1$ first, then pressing $x_2$. The primitive flow table for this system will have different paths. The path "no buttons pressed" $\to$ "$x_1$ pressed" $\to$ "both pressed" leads to a state where the machine turns on ($Z=1$). However, the path "no buttons pressed" $\to$ "$x_2$ pressed" $\to$ "both pressed" leads to a different internal state—one where the machine remains off ($Z=0$), even though the inputs are identical. The flow table elegantly captures this history, making it a perfect tool for designing systems where the order of operations is critical for safety and function.

This principle of latching and reset is also central to simple alarm systems. When a sensor $A$ detects a problem, an alarm $Z$ must turn on and, crucially, stay on even if the sensor signal goes away. The danger might have passed, but the event must be acknowledged. The alarm can only be turned off by a deliberate, separate action: pressing a reset button $R$. Here, the reset is dominant. The flow table for such a safety interlock clearly defines a "set" condition (when $A=1$), a "hold" or "latched" state (when $A=0$ but the alarm remains on), and a dominant "reset" condition (when $R=1$ which forces the alarm off no matter what). It's a simple, robust pattern for creating systems that remember critical events until they are explicitly handled.

In any complex system, from a computer motherboard to a network of servers, you will find conflict. Multiple devices will want to use the same shared resource—a memory bus, a hard drive, a printer—at the same time. Who gets to go first? This is the job of an arbiter.

An arbiter is a digital diplomat. Its role is to grant access to one, and only one, requestor at a time. A simple "first-come, first-served" arbiter can be beautifully described with a flow table. When two requests, $R_1$ and $R_2$, arrive, the table maps the sequence. If $R_1$ arrives first, the system moves to a state that grants access to device 1 ($G_1=1$). If $R_2$ then also makes a request, the arbiter, remembering it has already made a commitment, remains in a state that grants access only to device 1. It holds this grant until $R_1$ is released, at which point it returns to an idle state, ready to serve a new request.

Of course, not all requests are created equal. We can design more sophisticated arbiters that enforce a fixed priority. If a low-priority device has been granted access, a new request from a high-priority device can preempt it, revoking the first grant and issuing a new one. This complex set of rules, including preemption and mutual exclusion, can be systematically and unambiguously encoded in a primitive flow table. Each possible combination of active requests corresponds to a stable state whose output reflects the highest-priority request currently active.

Beyond resolving conflict, asynchronous state machines are the foundation of cooperation. How can two separate digital systems, a sender and a receiver, reliably exchange data without sharing a master clock? They use a handshake protocol. The classic four-phase handshake is a carefully choreographed sequence of "request" and "acknowledge" signals. The sender says, "I have data for you" (S_Req goes high). The receiver says, "I see your request and am taking the data" (R_Ack goes high). The sender says, "I see you've taken it, so I'm dropping my request" (S_Req goes low). Finally, the receiver says, "I see you've dropped my acknowledgement, so I'll drop my acknowledgement, and we're ready for the next round" (R_Ack goes low). The primitive flow table for this controller is the literal script for this conversation, defining the four stable states that constitute one full, successful transfer cycle.

The applications of flow tables are not confined to the abstract world inside a computer chip. They are a powerful tool for interpreting signals from the physical world. Consider a simple rotary knob, like a volume control on a stereo. How does the circuit know if you're turning it clockwise (to increase volume) or counter-clockwise (to decrease it)?

Many such knobs use a quadrature encoder, which produces two binary signals, ($X_1, X_0$), that change in a specific Gray code sequence. Turning clockwise might produce the cycle $00 \to 01 \to 11 \to 10 \to 00$, while turning counter-clockwise produces the reverse. A circuit designed with a primitive flow table can track the sequence of inputs. By remembering the previous input state, it can determine the direction of rotation from the current one. For instance, if the circuit is in a state corresponding to input $00$ and the next input is $01$, it knows the rotation is clockwise. If the next input is $10$, it must be counter-clockwise. The machine needs two states for each possible input—one for "arrived here moving CW" and another for "arrived here moving CCW"—requiring eight states in total to unambiguously track the direction.

This ability to interpret sequences extends to our everyday interactions with devices. Many gadgets distinguish between a "short press" and a "long press" of a button. How is this achieved without a stopwatch? A clever asynchronous design can use its own state transitions as a proxy for time. When the button is pressed, the circuit starts moving through a series of internal states. If the button is released quickly, the circuit is only in an early state, and the flow table directs it to a path that generates one output (e.g., a pulse on $z_1$). If the button is held down long enough for the circuit to transition to a later, different stable state, releasing it from there sends it down a completely different path, one that generates a second output (a pulse on $z_2$).

Perhaps the most fascinating application of this model is in creating circuits that are aware of their own rules. The fundamental-mode model itself is built on an assumption: inputs change one at a time. But what if this assumption fails? What if, due to noise or a fault, two inputs change simultaneously?

We can design a circuit whose very purpose is to police this rule. Using a primitive flow table, we can specify normal operation where single input changes cause transitions between a set of "normal" states. But for any state in this normal set, we can define that a simultaneous, two-input change—a transition that is normally "forbidden"—catapults the circuit into a special, permanent error state. The circuit essentially raises a flag saying, "The rules of the game have been violated!"

We can take this one step further. Instead of just entering an error state, what if the circuit could change its entire behavior in response to such an event? Imagine a circuit that starts its life as a simple AND gate. Its flow table maps inputs to outputs according to the function $z = x_1 \land x_2$. However, we add a special rule: if the circuit ever sees the normally-forbidden simultaneous change of both its inputs, it transitions to a new set of states. In this new mode, the circuit's behavior is governed by a different logic—it now acts as an OR gate, where $z = x_1 \lor x_2$, and it stays in this mode forever. This dual-mode design, specified completely within a single, larger flow table, shows the incredible flexibility of the state-machine paradigm. It allows us to build not just static logic, but dynamic, adaptive systems that can fundamentally alter their function based on their history and environment.

From the humble toggle to a self-modifying logic gate, the primitive flow table provides a unified, powerful language. It is a tool for thought that allows us to reason about systems that react, remember, and negotiate. It bridges the gap between abstract rules and concrete hardware, between the physical world and digital computation, revealing that the complex behaviors we see all around us can often be described by a simple, elegant dance of states.