Hubbry Logo
Sequential logicSequential logicMain
Open search
Sequential logic
Community hub
Sequential logic
logo
7 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Sequential logic
Sequential logic
Sequential logic
View on Wikipedia
from Wikipedia

In automata theory, sequential logic is a type of logic circuit whose output depends on the present value of its input signals and on the sequence of past inputs, the input history.[1][2][3][4] This is in contrast to combinational logic, whose output is a function of only the present input. That is, sequential logic has state (memory) while combinational logic does not.

Sequential logic is used to construct finite-state machines, a basic building block in all digital circuitry. Virtually all circuits in practical digital devices are a mixture of combinational and sequential logic.

A familiar example of a device with sequential logic is a television set with "channel up" and "channel down" buttons.[1] Pressing the "up" button gives the television an input telling it to switch to the next channel above the one it is currently receiving. If the television is on channel 5, pressing "up" switches it to receive channel 6. However, if the television is on channel 8, pressing "up" switches it to channel "9". In order for the channel selection to operate correctly, the television must be aware of which channel it is currently receiving, which was determined by past channel selections.[1] The television stores the current channel as part of its state. When a "channel up" or "channel down" input is given to it, the sequential logic of the channel selection circuitry calculates the new channel from the input and the current channel.

Digital sequential logic circuits are divided into synchronous and asynchronous types. In synchronous sequential circuits, the state of the device changes only at discrete times in response to a clock signal. In asynchronous circuits the state of the device can change at any time in response to changing inputs.

Synchronous sequential logic

[edit]

Nearly all sequential logic today is clocked or synchronous logic. In a synchronous circuit, an electronic oscillator called a clock (or clock generator) generates a sequence of repetitive pulses called the clock signal which is distributed to all the memory elements in the circuit. The basic memory element in synchronous logic is the flip-flop. The output of each flip-flop only changes when triggered by the clock pulse, so changes to the logic signals throughout the circuit all begin at the same time, at regular intervals, synchronized by the clock.

The output of all the storage elements (flip-flops) in the circuit at any given time, the binary data they contain, is called the state of the circuit. The state of the synchronous circuit only changes on clock pulses. At each cycle, the next state is determined by the current state and the value of the input signals when the clock pulse occurs.

The main advantage of synchronous logic is its simplicity. The logic gates which perform the operations on the data require a finite amount of time to respond to changes to their inputs. This is called propagation delay. The interval between clock pulses must be long enough so that all the logic gates have time to respond to the changes and their outputs "settle" to stable logic values before the next clock pulse occurs. As long as this condition is met (ignoring certain other details) the circuit is guaranteed to be stable and reliable. This determines the maximum operating speed of the synchronous circuit.

Synchronous logic has two main disadvantages:

  • The maximum possible clock rate is determined by the slowest logic path in the circuit, otherwise known as the critical path. Every logical calculation, from the simplest to the most complex, must complete in one clock cycle. So logic paths that complete their calculations quickly are idle much of the time, waiting for the next clock pulse. Therefore, synchronous logic can be slower than asynchronous logic. One way to speed up synchronous circuits is to split complex operations into several simple operations which can be performed in successive clock cycles, a technique known as pipelining. This technique is extensively used in microprocessor design and helps to improve the performance of modern processors.
  • The clock signal must be distributed to every flip-flop in the circuit. As the clock is usually a high-frequency signal, this distribution consumes a relatively large amount of power and dissipates much heat. Even the flip-flops that are doing nothing consume a small amount of power, thereby generating waste heat in the chip. In battery-powered devices, additional hardware and software complexity is required to reduce the clock speed or temporarily turn off the clock while the device is not being actively used, in order to maintain a usable battery life.

Asynchronous sequential logic

[edit]
Main article: Asynchronous circuit

Asynchronous (clockless or self-timed) sequential logic is not synchronized by a clock signal; the outputs of the circuit change directly in response to changes in inputs. The advantage of asynchronous logic is that it can be faster than synchronous logic, because the circuit doesn't have to wait for a clock signal to process inputs. The speed of the device is potentially limited only by the propagation delays of the logic gates used.

However, asynchronous logic is more difficult to design and is subject to problems not encountered in synchronous designs. The main problem is that digital memory elements are sensitive to the order that their input signals arrive; if two signals arrive at a flip-flop or latch at almost the same time, which state the circuit goes into can depend on which signal gets to the gate first. Therefore, the circuit can go into the wrong state, depending on small differences in the propagation delays of the logic gates. This is called a race condition. This problem is not as severe in synchronous circuits because the outputs of the memory elements only change at each clock pulse. The interval between clock signals is designed to be long enough to allow the outputs of the memory elements to "settle" so they are not changing when the next clock comes. Therefore, the only timing problems are due to "asynchronous inputs"; inputs to the circuit from other systems which are not synchronized to the clock signal.

Asynchronous sequential circuits are typically used only in a few critical parts of otherwise synchronous systems where speed is at a premium, such as parts of microprocessors and digital signal processing circuits.

The design of asynchronous logic uses different mathematical models and techniques from synchronous logic, and is an active area of research.

See also

[edit]

References

[edit]

Further reading

[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Sequential logic

View on Grokipedia
from Grokipedia
Sequential logic is a type of digital circuit in which the output depends on both the current inputs and the previous state of the circuit, incorporating elements to store from past operations. This contrasts with , where outputs are determined solely by the present inputs without any of prior states. The state of a sequential circuit represents all necessary to predict its future behavior based on inputs. Key components of sequential logic include bistable devices such as and flip-flops, which serve as the basic memory units. An SR latch, for example, uses cross-coupled NOR gates to maintain one of two stable states (set or reset) until changed by set (S) or reset (R) inputs. Flip-flops, such as the D flip-flop, extend this by being edge-triggered, capturing the input value only at specific clock transitions to ensure synchronized operation. These elements enable the circuit to exhibit time-dependent behavior, often modeled as finite state machines (FSMs). Sequential circuits are classified into synchronous and asynchronous types based on timing control. In synchronous sequential logic, a common coordinates state changes, typically at rising or falling edges, preventing race conditions and ensuring predictable timing across the circuit. Asynchronous sequential logic, by contrast, responds immediately to input changes without a clock, relying on feedback paths but risking hazards like glitches if not carefully designed. Fundamental to both is the dynamic discipline, requiring inputs to remain stable during setup and hold times around clock edges in synchronous designs. These principles underpin essential digital systems, including registers for , counters for sequencing, and FSMs for control logic in processors and units. For instance, D flip-flops form the basis of shift registers used in serial-to-parallel , while SR flip-flops enable basic bistable in early computing elements. Sequential logic's ability to handle temporal dependencies makes it indispensable for implementing complex behaviors in modern integrated circuits.

Fundamentals

Definition and Principles

Sequential logic refers to digital circuits in which the output depends not only on the current inputs but also on the previous state of the circuit, achieved through the use of elements that store over time. Unlike , which produces outputs solely based on present inputs without , sequential logic incorporates feedback mechanisms to retain and update states, enabling the implementation of systems with temporal behavior such as counters and registers. This state-dependent functionality is fundamental to building complex digital systems like processors and units. The core principles of sequential logic revolve around feedback loops that connect the output of memory elements back to the input of , allowing the circuit to "remember" prior conditions and evolve based on a sequence of inputs. States are typically represented in , using bits that hold values of 0 or 1 to encode information in memory elements. Timing is managed either through clock signals, which synchronize state changes at specific edges or levels, or via level-sensitive triggers that respond to input durations, ensuring controlled transitions between states. Sequential logic originated in the early , with the first electronic flip-flops invented in by British physicists William Eccles and F.W. Jordan using vacuum tubes as bistable trigger circuits. These vacuum tube-based memory elements were pivotal in the for early computers like , which employed thousands of tubes, including modified Eccles-Jordan flip-flops, to implement sequential operations. In the late 1950s and 1960s, the technology evolved to transistor-based implementations, starting with discrete transistors and advancing to integrated circuits, enabling more reliable and compact sequential circuits. A basic sequential logic circuit can be represented by a consisting of inputs fed into , whose outputs connect to a element that stores the state; the output then feeds back to the and also provides the circuit's outputs. This structure allows the next state to be determined by both current inputs and the stored state. An introductory example of a element in sequential logic is the SR (Set-Reset) , constructed from two cross-coupled NOR gates, which provides basic state storage without a clock. The SR operates by setting the output Q to 1 when S=1 and R=0, resetting it to 0 when S=0 and R=1, holding the previous state when S=0 and R=0, and entering an invalid state when S=1 and R=1. Its behavior is summarized in the following :
SRQ(next)
00Q (hold)
010 (reset)
101 (set)
11Invalid
Flip-flops represent more advanced clocked memory elements building on such latches.

Distinction from Combinational Logic

The primary distinction between combinational and sequential logic lies in their dependency on inputs and memory elements. In combinational logic, outputs are determined solely by the current inputs, with no provision for storing previous states, making the circuits memoryless. Conversely, sequential logic incorporates memory components that retain state information from prior inputs, allowing outputs to depend on both current inputs and historical state, which enables more complex behaviors over time. This fundamental difference affects analysis methods: combinational circuits are characterized using static truth tables that enumerate all possible input-output mappings, while sequential circuits require dynamic representations like state diagrams to capture transitions between states. Timing considerations further highlight the contrast, as operates without a and relies only on inherent propagation delays through , where outputs stabilize after a brief period following input changes. Sequential logic, however, introduces mechanisms, often via clocks, to manage state updates, but this can lead to challenges such as propagation delays in state elements and the risk of —where a flip-flop output enters an unstable intermediate voltage level due to setup or hold time violations, potentially propagating errors through the system if not resolved. Without proper , sequential circuits are susceptible to timing errors from varying signal paths, unlike the more predictable, clock-independent behavior of combinational designs. Sequential logic offers significant advantages over by enabling storage, sequential operations, and control functions essential in applications like processors, where state retention allows for and data flow management across cycles. However, these benefits come with drawbacks, including greater design complexity due to and heightened vulnerability to timing errors, which can complicate verification and increase power consumption compared to the simpler, faster combinational counterparts. An illustrative example underscores input dependency differences: a half-adder, a purely combinational circuit, computes the sum and carry from two inputs (A and B) without reference to prior results, producing outputs based only on the instantaneous values, with possible outputs limited to 2^2 = 4 combinations. In contrast, a full-adder extends this by incorporating a carry-in input, which analogizes state dependency in sequential logic by relying on the "previous" carry as an additional input factor, expanding possible outputs to 2^3 = 8 while highlighting how sequential designs scale behavior with bits (e.g., 2^k states for k-bit storage). Latches serve as basic building blocks for this in sequential circuits.

Core Components

Latches

A is a bistable element in sequential logic that stores a single bit of and is level-sensitive, meaning it captures and holds the input value when an enable signal is active (typically high) and retains the previous state when the enable is inactive. Unlike edge-triggered devices, latches respond continuously to input changes during the enable period, providing transparency to the input signal. This behavior makes latches fundamental for temporary storage in feedback-based circuits without requiring precise timing edges. The SR (Set-Reset) latch is the basic form, implemented using two cross-coupled NOR gates where the output of one gate serves as the input to the other, creating feedback that maintains the state. The inputs are S (set) and R (reset), with outputs Q and its complement \overline{Q}. An enabled version adds a third input (E) that gates the S and R signals through additional NOR or NAND gates. The for the basic SR latch is as follows:
SRQ_{next}\overline{Q}_{next}Description
00Q\overline{Q}Hold previous state
0101Reset (Q = 0)
1010Set (Q = 1)
11??Forbidden (invalid, leads to metastable or both outputs low)
The state S = R = 1 is forbidden because it forces both outputs to 0 in the NOR implementation, violating the complementary nature and potentially causing instability upon release. The characteristic equation, derived from the treating the forbidden state as a don't-care, is Q_{next} = S + \overline{R} Q, where Q is the current state. In operation, when E = 1 (for gated version), the is transparent to S and R; when E = 0, it holds the state regardless of input changes. Timing waveforms illustrate this: during enable high, Q follows the set or reset assertion, but upon enable low, Q latches the last valid value, with potential glitches if S and R change simultaneously near the transition. The (Data) latch addresses the SR latch's ambiguity by using a single data input and an enable E, constructed from an SR latch with S connected to , R to \overline{}, and E gating both. This ensures Q_{next} = when E = 1, eliminating the forbidden state and making the latch transparent to during enable. The circuit typically employs four NAND gates: two for the input inversion and gating, feeding into a cross-coupled NAND pair for storage. The simplifies to:
EDQ_{next}
0XQ
100
111
where X denotes care. The characteristic equation is Q_{next} = E D + \overline{E} Q, but effectively Q_{next} = D under enable. Operationally, while E is high, any change in D propagates immediately to Q (transparent mode); when E goes low, Q holds the D value at that instant, with setup and hold times implicitly defined by gate delays to avoid . A JK latch variant extends the SR design by redefining the J (like S) and K (like R) inputs to resolve the forbidden state: when J = K = 1 and enabled, the output toggles (Q_{next} = \overline{Q}). Implemented similarly with cross-coupled gates and additional logic for toggle, it serves as a precursor to more advanced edge-triggered elements. Latches find applications in asynchronous systems for local storage without global and as foundational building blocks in constructing edge-triggered flip-flops for broader sequential designs.

Flip-Flops

Flip-flops are clocked memory elements in sequential logic that store a single bit of information and change their output state only in response to a transition, typically at the rising or falling edge, ensuring synchronized operation across a circuit. Unlike level-sensitive latches, this edge-triggering prevents continuous transparency and enables precise timing control in synchronous systems. Common types of flip-flops include the , T, and JK variants, each defined by their characteristic equations that determine the next state QnextQ_{next} based on inputs and the current state QQ. The flip-flop captures the input DD directly on the clock edge, with Qnext=DQ_{next} = D, often implemented in a master-slave configuration to achieve edge triggering. The T flip-flop toggles its state when the toggle input T=1T = 1, following Qnext=Q⊕TQ_{next} = Q \oplus T, making it useful for frequency division and counters. The JK flip-flop extends functionality with inputs JJ and KK, where Qnext=JQˉ+KˉQQ_{next} = J \bar{Q} + \bar{K} Q, resolving the invalid state of simpler SR latches by allowing toggle behavior when J=K=1J = K = 1. Key timing parameters for flip-flops ensure reliable operation: setup time tsut_{su} requires inputs to be stable for a minimum duration before the clock edge, hold time tht_h mandates stability after the edge, and clock-to-output delay tcqt_{cq} measures the time from clock edge to output change. These parameters constrain the minimum clock period TclkT_{clk}, which must satisfy Tclk>tsu+tpd+tcqT_{clk} > t_{su} + t_{pd} + t_{cq} (neglecting skew for basic analysis), where tpdt_{pd} is the propagation delay between flip-flops, to prevent setup violations. Flip-flops are typically implemented using a master-slave configuration of two in series to detect clock edges: the master latch is transparent when the clock is low (loading data), while the slave is transparent when the clock is high (transferring the stored value to output), ensuring the output updates only on the rising edge. For a flip-flop, this setup uses the input to control the master, with the slave providing the edge-triggered output. Metastability occurs in flip-flops when inputs violate setup and hold times, leading to an indeterminate output state due to unequal rise and fall times in internal nodes; the circuit resolves metastability exponentially over time, with resolution probability decaying as e^{-t/τ}, where τ is the device-specific time constant determined by the latch gain and circuit parameters. In synchronizers, multiple stages increase the mean time between failures (MTBF), which depends on clock frequency.

Synchronous Sequential Circuits

Registers and Shift Registers

Registers serve as fundamental multi-bit storage elements in synchronous sequential circuits, consisting of multiple D flip-flops connected in parallel, each capturing one bit of on the active edge of a shared . This parallel arrangement enables the simultaneous storage of an n-bit word, where n flip-flops form an n-bit register, providing temporary retention between combinational logic stages. Common types include the basic storage register, which loads only on designated clock cycles, and bidirectional variants that incorporate direction control for shifting operations, though the core focus remains on parallel access. The operation of a storage register is governed by a load enable (E) signal, which determines whether new data is captured or the current state is retained. When E is active (logic 1), the register's outputs () update to match the parallel inputs (D) on the clock edge; otherwise, the outputs hold their previous values. For a 4-bit register, this behavior can be illustrated by the following , assuming a rising-edge clock and initial state Q = 0000:
Clock EdgeED3 D2 D1 D0Q3 Q2 Q1 Q0 (after edge)
Before--0000
1st110101010
2nd011001010
3rd101100110
This table demonstrates parallel loading on enabled clocks and retention otherwise, with the excitation Qt+1=EˉQt+EDQ_{t+1} = \bar{E} Q_t + E D describing the state transition for each bit. Shift registers extend the register concept by enabling serial or parallel data movement through interconnected flip-flops, facilitating bit-by-bit shifting along the chain on each clock . Key types include serial-in/serial-out (SISO), where enters and exits serially; serial-in/parallel-out (SIPO), converting serial input to parallel output; parallel-in/serial-out (PISO), for the reverse; and parallel-in/parallel-out (PIPO), combining both. A universal shift register integrates these functions via mode select inputs (S1, S0), allowing versatile operations such as hold (no change), shift left, shift right, or parallel load, as shown in the mode select table for a typical 4-bit implementation like the 74LS194:
S1S0Mode
00Hold
01Shift Left
10Shift Right
11Parallel Load
Multiplexers at each flip-flop input route signals accordingly, enabling bidirectional shifting or direct loading. In applications, registers provide data buffering in central processing units (CPUs) for holding operands and results during arithmetic operations, while shift registers support pipeline stages by synchronizing serial data streams from peripherals or enabling bit manipulation in instruction execution. For instance, a 4-bit SISO shift register loaded with the pattern 1010 (Q3 Q2 Q1 Q0 = 1 0 1 0, MSB first) will output it serially over four clock cycles with serial input 0, where the output is the bit shifted out from Q3 each clock: after the first clock, shifted out 1, internal 0100; second clock, shifted out 0, internal 1000; third clock, shifted out 1, internal 0000; fourth clock, shifted out 0, internal 0000. This serial shifting is essential for data conversion in CPU interfaces. Timing in multi-flip-flop arrays like registers must account for , the variation in clock arrival times across flip-flops due to interconnect delays, which can violate setup or hold times and cause . While detailed analysis falls under synthesis techniques, designs often employ balanced clock trees to minimize skew below 100 ps in modern systems.

Counters and State Machines

Counters represent a fundamental class of synchronous sequential circuits that cycle through a predefined sequence of states, typically used for counting clock pulses or events. They are constructed by interconnecting flip-flops, where each flip-flop stores one bit of the count, and determine the next state based on the current state and inputs. In binary counters, the state advances in natural binary order, such as from 0000 to 0001 and so on, making them essential for applications like frequency division and timing generation. In contrast, a synchronous counter applies a single global clock to all flip-flops simultaneously, allowing parallel state transitions and enabling higher operating frequencies without propagation delays. For example, in a 4-bit binary up/down counter using JK flip-flops, the next-state logic derives J and inputs from the current Q outputs: the least significant bit toggles on every clock (J=1, K=1), while higher bits toggle conditionally based on lower bits being high for up-counting or low for down-counting. Various specialized counter types extend binary designs for specific applications. A decade counter, or BCD counter, counts through 10 states (0 to 9 in ) before resetting, useful in decimal displays and avoiding invalid BCD codes beyond 1001. A employs a with feedback from the last output to the first input, creating a circulating "one-hot" pattern where only one bit is active at a time, ideal for sequencing and decoding with minimal logic. The Johnson counter, a twisted ring variant, inverts the last output before feeding it back to the first, producing 2n unique states for n flip-flops (e.g., 8 states with 4 bits), which doubles the sequence length compared to a standard while maintaining self-decoding properties. Finite state machines (FSMs) provide a formal model for more complex sequential behavior in counters and other circuits, representing systems with a finite number of states, transitions driven by inputs and clocks, and outputs. In a , outputs depend solely on the current state, resulting in glitch-free but potentially slower responses since output changes occur only on state transitions. Conversely, a generates outputs based on both the current state and inputs, allowing faster reaction times as outputs can change combinatorially with inputs, though this may introduce timing hazards if not carefully designed. State diagrams for FSMs use circles to denote states (with the initial state marked by an arrow) and directed arcs labeled with input/output conditions to illustrate transitions, facilitating analysis and synthesis of counter logic. A practical example is a 2-bit synchronous up-counter using JK flip-flops, which sequences through states 00, 01, 10, 11 before returning to 00. The state table below outlines the present state, next state, and required JK excitation inputs, where the least significant bit (Q0) always toggles (J0=1, K0=1), and the most significant bit (Q1) toggles only when Q0=1 (J1=Q0, K1=Q0).
Present StateNext StateExcitation Inputs
Q1Q0Q1(next)Q0(next)J1K1J0K0
00010X11
01101X11
1011X011
11001111
The excitation equations are derived as J0 = 1, K0 = 1, J1 = Q0, and K1 = Q0, implemented with AND gates for conditional toggling. Desirable counter characteristics include self-starting and lock-out free operation, ensuring the circuit enters a valid from any initial or invalid state without external reset, achieved by designing unused states to transition toward the cycle. For a modulo-N counter, which cycles through N states, the period T equals N times the clock period T_clk, determining the output as f_clk / N. Counters may incorporate registers for parallel loading of initial values to set starting points.

Asynchronous Sequential Circuits

Fundamental Concepts

Asynchronous sequential circuits are digital systems in which the outputs depend not only on the current inputs but also on the previously stored states, with state transitions triggered directly by changes in input levels rather than by a global . These circuits incorporate feedback loops to maintain , allowing them to respond asynchronously to input variations. A key operational assumption is the fundamental mode, where only one input changes at a time, and the circuit must settle into a stable state before the next input alteration occurs, ensuring predictable behavior under controlled conditions. The primary components of asynchronous sequential circuits consist of elements combined with feedback paths that include devices such as unclocked latches, without relying on edge-triggered mechanisms. The processes the inputs and feedback signals to generate outputs and next-state values, while the feedback loops store the current state through level-sensitive elements that respond continuously to input levels. Latches serve as the core units in these designs. In terms of behavior, asynchronous sequential circuits are inherently level-sensitive, meaning their state changes occur based on the sustained levels of inputs and feedback rather than timed pulses, which can lead to multiple stable states defined by the values of secondary variables—the feedback signals that represent the internal memory bits. The state is thus captured by these secondary variables, enabling the circuit to hold information across input changes until a new stable configuration is reached. A representative example is the basic asynchronous SR (Set-Reset) latch, constructed using two cross-coupled NOR gates, where the inputs S (Set) and R (Reset) control the outputs Q and \overline{Q}. Under fundamental mode operation, the circuit assumes inputs change one at a time from a stable state: when S=1 and R=0, Q=1 (set state); when S=0 and R=1, Q=0 (reset state); and when S=0 and R=0, the outputs retain their previous values (hold state), while S=1 and R=1 is typically avoided as it leads to an invalid metastable condition. The truth table for the SR latch illustrates this behavior:
SRQ (next)\overline{Q} (next)State
00Q (prev)\overline{Q} (prev)Hold
0101Reset
1010Set
11??
This simple circuit demonstrates how feedback enables bistable operation without clocking. Asynchronous sequential circuits offer advantages such as faster response times due to the absence of clock distribution delays and lower power consumption, as no continuous is required to drive the system. These benefits make them suitable for applications in speed-critical paths, such as high-performance interfaces or low-power embedded systems.

Hazards and Race Conditions

In asynchronous sequential circuits, hazards represent temporary incorrect outputs due to gate delays, assuming operation in the fundamental mode where only one input changes at a time. Static occur when the output glitches but ultimately settles to the correct value, such as a static-1 hazard where the output briefly drops to 0 while intended to remain 1, or a static-0 hazard where it spikes to 1 while intended to stay 0. Dynamic hazards, in contrast, produce multiple unintended transitions during a single intended output change, often stemming from unresolved static hazards. Hazards are further classified as logic hazards, arising from single input changes in the implemented logic, or function hazards, resulting from multiple simultaneous input changes that inherently cause output uncertainty regardless of realization. Race conditions arise when two or more state variables change nearly simultaneously in response to an input, potentially leading to unpredictable behavior under the fundamental mode assumption. A critical race affects the final stable state and output, as the order of state variable transitions determines an incorrect outcome, whereas a non-critical race resolves to the intended state regardless of timing. Cycles in the , such as loops between transient states, indicate potential races or oscillations that prevent stabilization. Detection of hazards employs Karnaugh maps, where static-1 hazards appear as adjacent 1-cells not covered by the same , and static-0 hazards show similar uncovered adjacent 0-cells; dynamic hazards are inferred from timing simulations revealing multiple transitions. For races, state table analysis identifies simultaneous state variable changes, with critical races confirmed if alternate transition paths lead to different stable states, and cycles spotted as closed loops in the diagram. Elimination of static hazards involves hazard-free realizations by adding covering terms, such as consensus terms (e.g., for a static-1 hazard in an AND-OR circuit, inserting a term like bcbc to bridge uncovered transitions in the ). Dynamic hazards are mitigated by resolving underlying static ones, while extra delays can be introduced sparingly for timing correction. Critical races and cycles are addressed by cycle breaking with additional to enforce sequential state changes or by state assignment strategies that minimize simultaneous transitions. A representative example is a two-bit asynchronous binary counter cycling through states 00 → 01 → 10 → 11 → 00, where a race occurs if both bits attempt to toggle simultaneously from 11 to 00, potentially landing in an unintended state like 10 depending on delay order. This critical race is resolved by symmetric design using assignment (00 → 01 → 11 → 10 → 00), ensuring only one bit changes per transition and avoiding races.

Design and Analysis Methods

State Representation

State diagrams provide a graphical representation of sequential circuits, depicting states as nodes and transitions between states as directed arcs labeled with input conditions and corresponding output actions. This visualization aids in understanding the behavior of finite state machines (FSMs) by illustrating how the circuit evolves based on inputs from one stable state to the next. State diagrams are particularly useful for both synchronous and asynchronous designs, though they assume deterministic transitions in synchronous cases. State tables offer a tabular alternative to state diagrams, organizing the machine's behavior into rows for each present state and columns for , next states, and outputs. Similar to truth tables for , state tables systematically enumerate all possible combinations, facilitating analysis and conversion to logic equations. For a simple three-state synchronous counter (states A, B, C) that cycles A → B → C → A on clock with input enable E=1, the state table is as follows:
Present StateInput ENext StateOutput (e.g., count bit)
A0A00
A1B00
B0B01
B1C01
C0C10
C1A10
This conversion from to table highlights equivalences and supports further minimization. Once states are defined, binary encoding assigns bit patterns to represent them, with standard binary using ⌈log⁡2n⌉\lceil \log_2 n \rceil bits for nn states to minimize hardware. encoding, in contrast, employs nn bits where exactly one bit is asserted (high) per state, enabling direct decoding with simple AND gates and reducing next-state logic complexity in FPGA implementations. encoding ensures that adjacent states differ by only one bit, minimizing glitches and power consumption during transitions, especially in counters where states follow a cyclic sequence. In asynchronous sequential circuits, flow tables extend state tables to account for unstable (transient) states during input changes, listing all possible secondary states and their resolutions to stable ones without a clock. Excitation tables derive the required inputs (e.g., for SR latches) from the flow table's next-state assignments, mapping present states and inputs to flip-flop excitations for implementation. These representations handle races and hazards inherent to asynchronous operation. State reduction techniques, such as partitioning, identify equivalent states through implication tables or compatibility charts, merging them into equivalence classes to yield a minimal without altering external . For instance, in the three-state example above, if states B and C produce identical outputs for all inputs, partitioning would confirm their potential merger, reducing to two states. Algorithmic state machine (ASM) charts provide a hierarchical representation for complex controllers, using state boxes for conditional outputs, decision boxes for inputs, and conditional boxes for transitions, bridging high-level algorithms and low-level state diagrams. This format supports by embedding subcharts, improving readability for multi-level FSMs.

Synthesis Techniques

The synthesis of sequential circuits involves a systematic process that transforms a behavioral specification into a logic implementation, emphasizing optimization to minimize hardware resources and ensure reliability. This process typically proceeds from a behavioral description, often represented as a state diagram outlining desired state transitions and outputs, to state minimization, assignment, derivation of next-state and output logic, and final implementation. State minimization identifies and merges equivalent states to reduce the total number, while state assignment encodes states with binary codes to simplify logic and reduce transitions. The next-state and output functions are then derived as excitation equations for flip-flops, optimized using techniques like Karnaugh maps, followed by gate-level realization. In synchronous synthesis, the process begins with constructing a from the specification, followed by minimization using an implication chart to detect equivalent states—pairs that produce identical outputs for all inputs and lead to equivalent next states. Equivalent states are merged to eliminate redundancy, potentially reducing the number of flip-flops required; for instance, a machine with six states might be minimized to five if implication chains reveal compatibilities without conflicts. State assignment then assigns binary codes to minimized states, prioritizing adjacency for frequent transitions to minimize logic complexity and power consumption by reducing the number of changing bits. Next-state and output logic are derived via excitation tables for the chosen flip-flop type, with Karnaugh maps applied to simplify these functions into minimal sum-of-products forms. Asynchronous synthesis starts with a primitive flow table derived from the specification, capturing and unstable states for each input combination, which is then reduced by merging compatible rows using an implication chart to identify sets of states with identical outputs and non-conflicting next-state implications. The shared-row method addresses potential races by duplicating rows for states with identical outputs, ensuring that transitions to adjacent states (differing by one variable) maintain race-free without altering functionality. Hazard-free covers for the resulting excitation and output functions are obtained by selecting prime that do not intersect privileged cubes illegally, preventing dynamic hazards during multiple input changes; a dynamic-hazard-free implicant must cover the entire transition cube while avoiding off-set minterms. Tools and methods for optimization include the Quine-McCluskey algorithm, which systematically generates prime implicants for minimizing the in next-state and output functions after state encoding, particularly useful for functions with more than six variables where Karnaugh maps become impractical. As an illustrative example, consider designing a synchronous detector for the sequence "1011" using JK flip-flops with four states (S0=00, S1=01, S2=10, S3=11). The state table specifies transitions such as S0 to S0 on input 0 and to S1 on 1, with output 1 only from S3 on input 1. Excitation equations derived via Karnaugh maps yield JA=BXJ_A = B X, KA=BK_A = B, JB=AX+BXˉJ_B = A X + B \bar{X}, and KB=AXˉ+BˉXK_B = A \bar{X} + \bar{B} X, where A and B are state variables and X is the input, enabling implementation with minimized gates. Verification ensures the synthesized circuit meets specifications through of state transitions using testbenches that apply input sequences and compare outputs against expected behavior, confirming all paths in the are exercised without deadlocks. Timing analysis evaluates critical paths for setup and hold constraints, where the clock period must satisfy Tc≥tpcq+tpd+tsetupT_c \geq t_{pcq} + t_{pd} + t_{setup} to avoid violations, and hold times require tcd>thold−tccqt_{cd} > t_{hold} - t_{ccq} to prevent , with tools identifying the longest path to determine maximum operating frequency.

References

  1. https://pages.hmc.edu/harris/class/e85/DDCArv_Ch3.pdf
  2. https://www.electronics-tutorials.ws/sequential/seq_1.html
  3. https://www.renesas.com/en/support/engineer-school/digital-circuits-03-sequential-logic
  4. https://ocw.mit.edu/courses/6-071j-introduction-to-electronics-signals-and-measurement-spring-2006/d0a578bc6340f91188b1e3ac487b62ab_sequential_logic.pdf
  5. https://engineering.purdue.edu/~vlsi/ECE559_Fall09/Notes/SequentialLogic.pdf
  6. https://personal.utdallas.edu/~dodge/EE2310/lec7.pdf
  7. https://www.eecs.umich.edu/courses/eecs270/270lab/270_docs/verilog_ref_seqv2.pdf
  8. https://oercommons.org/authoring/15863-introduction-to-flip-flop/1/view
  9. https://ftp.arl.army.mil/~mike/comphist/eniac-story.html
  10. https://www.cs.ucr.edu/~ehwang/courses/cs120b/flipflops.pdf
  11. https://people.eecs.berkeley.edu/~randy/Courses/CS150.F00/CLD2/chapter02.pdf
  12. https://web.mit.edu/6.111/volume2/www/f2019/handouts/L04.pdf
  13. https://pages.hmc.edu/harris/class/hal/lect9.pdf
  14. https://drive.uqu.edu.sa/_/aagutub/files/Teaching_ComputerEngineering/1403271_Switching_Theory/Lecture_Slides/Ch4.pdf
  15. https://engineering.purdue.edu/~meyer/DDU270/Notes/PDF/2-Mod3_LS_2019.pdf
  16. https://courses.cs.washington.edu/courses/cse370/10wi/pdfs/lectures/13-SequentialLogic.pdf
  17. https://eng.auburn.edu/~agrawvd/COURSE/E2200_Fall14/LECTURES/lec7_SeqCkt.pdf
  18. https://taoxie.sdsu.edu/cs370/Lecture14.pdf
  19. https://www.ece.ucdavis.edu/~ramirtha/EEC116/F11/lecture6.pdf
  20. https://www.cs.columbia.edu/~nowick/async-applications-PIEEE-99-berkel-josephs-nowick-published.pdf
  21. https://marz.utk.edu/my-courses/cosc130/lectures/sequential-logic/
  22. http://www.cs.ucr.edu/~ehwang/courses/cs120b/sequential.pdf
  23. https://www2.cs.uh.edu/~jhuang/JCH/LD/chapter6.pdf
  24. https://www.calstatela.edu/sites/default/files/2449_ex10.pdf
  25. https://schaumont.dyn.wpi.edu/ece574f24/05timinganalysis.html
  26. https://courses.cs.washington.edu/courses/cse466/11au/resources/sims/e-masterslaveff.html
  27. https://pages.hmc.edu/harris/class/e85/old/fall19/lect5.pdf
  28. https://www.nxp.com/docs/en/application-note/AN219.pdf
  29. https://www.secs.oakland.edu/~llamocca/Courses/ECE2700/Notes%20-%20Unit%206.pdf
  30. https://ece.eng.wayne.edu/~smahmud/ECECourses/ECE2610/LectureNotes/Lecture12.pdf
  31. https://www.electronics-tutorials.ws/sequential/seq_5.html
  32. https://www.allaboutcircuits.com/textbook/digital/chpt-12/parallel-in-parallel-out-universal-shift-register/
  33. https://snsct.snscourseware.org/files/1752905081.pdf
  34. https://users.ece.utexas.edu/~mcdermot/vlsi1/main/lectures/lecture_9.pdf
  35. https://www.geeksforgeeks.org/digital-logic/counters-in-digital-logic/
  36. https://www.tutorialspoint.com/digital-electronics/digital-electronics-counters.htm
  37. https://www.allaboutcircuits.com/textbook/digital/chpt-12/ring-counters/
  38. https://www.electronics-tutorials.ws/sequential/seq_6.html
  39. https://www.geeksforgeeks.org/theory-of-computation/difference-between-mealy-machine-and-moore-machine/
  40. https://www.tutorialspoint.com/automata_theory/moore_and_mealy_machines.htm
  41. https://www.cs.siu.edu/~hexmoor/classes/CS315-S09/Chapter7-Counters.ppt
  42. https://www.electronics-tutorials.ws/counter/mod-counters.html
  43. https://web.stanford.edu/class/archive/ee/ee108a/ee108a.1082/reader/ch22to25.pdf
  44. https://www.tutorialspoint.com/digital-electronics/digital-electronics-sequential-circuits.htm
  45. https://www.allaboutcircuits.com/textbook/digital/chpt-10/s-r-latch/
  46. https://web.stanford.edu/class/archive/ee/ee371/ee371.1066/lectures/lect_12.pdf
  47. https://digitalcommons.njit.edu/cgi/viewcontent.cgi?filename=8&article=1000&context=oat&type=additional
  48. https://people.eecs.berkeley.edu/~randy/Courses/CS150.S01/Lectures/06-SeqImpl.pdf
  49. https://ocw.mit.edu/courses/6-004-computation-structures-spring-2017/pages/c6/c6s1/
  50. https://people.eecs.berkeley.edu/~randy/Courses/CS150.S01/Lectures/07-SeqEx.pdf
  51. https://ocw.mit.edu/courses/6-004-computation-structures-spring-2017/9de141eaa197ee38a3678587758df53e_5mJd--JCwBI.pdf
  52. http://web.cecs.pdx.edu/~mperkows/Nov17/025.Berkeley=fsm-minimization.pdf
  53. https://web.stanford.edu/class/archive/ee/ee108a/ee108a.1082/reader/ch14to16.pdf
  54. https://faculty-web.msoe.edu/johnsontimoj/CE1911/files1911/state_machine_encoding_hdl.pdf
  55. https://people.engr.tamu.edu/xizhang/ECEN248/Chapter_8_Part_III_Xi_Zhang.pdf
  56. https://people-ece.vse.gmu.edu/coursewebpages/ECE/ECE448/S20/viewgraphs/ECE448_lecture6_ASM_Charts.pdf
  57. https://www.ecs.csun.edu/~smirzaei/docs/ece524/ece524fall25-FSMs.pdf
  58. http://www.cs.ucr.edu/~ehwang/courses/cs120b/synthesis.pdf
  59. https://users.ece.utexas.edu/~bevans/courses/ee382c/lectures/spring2000/20_fsm/SeqSynIntro.pdf
  60. https://web.eece.maine.edu/eason/ece275/StateMinimization.pdf
  61. https://methodist.edu.in/web/uploads/files/02_async.pdf
  62. http://i.stanford.edu/pub/cstr/reports/csl/tr/94/644/CSL-TR-94-644.pdf
  63. https://www.geeksforgeeks.org/digital-logic/quine-mccluskey-method/
  64. https://drive.uqu.edu.sa/_/aagutub/files/_/teaching/1401213/Useful_Notes/6_SequentialCircuitDesign3.pdf
  65. https://safari.ethz.ch/digitaltechnik/spring2018/lib/exe/fetch.php?media=digitaldesign-s18-lecture8-timing-and-verification-v2.1.pdf
Add your contribution
Related Hubs
User Avatar
No comments yet.