Combinational and Sequential Digital Systems

Introduction

Digital systems process information represented by discrete logic levels, conventionally 0 and 1. They form the computational foundation of microprocessors, communication equipment, control systems, memories, instrumentation, and embedded devices. Two broad classes are central: combinational systems, whose outputs depend only on present inputs, and sequential systems, whose outputs depend on present inputs as well as stored past information.

The distinction is not merely descriptive. It determines how a circuit is specified, analyzed, timed, tested, synthesized, and implemented in hardware-description languages and integrated circuits. A combinational circuit can be represented by Boolean functions. A sequential circuit must additionally be represented by a state model and a timing discipline.

At postgraduate level, digital design requires attention to Boolean abstraction, propagation delay, hazards, clocking, setup and hold constraints, state minimization, synchronous design methodology, and implementation trade-offs.

Learning Objectives

After studying this chapter, the learner should be able to:

1. Distinguish combinational and sequential digital systems.
2. Analyze Boolean functions using truth tables, Boolean algebra, and Karnaugh maps.
3. Design adders, subtractors, multiplexers, decoders, encoders, and comparators.
4. Explain latches, flip-flops, registers, counters, and finite-state machines.
5. Derive state equations and next-state behavior.
6. Analyze propagation delay, hazards, setup time, hold time, and metastability.
7. Apply synchronous design principles to a practical control problem.
8. Evaluate implementation choices involving speed, area, power, reliability, and testability.

1. Digital-System Abstraction

A digital system is commonly modeled as a set of input variables, output variables, logic functions, storage elements, and timing signals. Logic values may be represented by voltage ranges rather than ideal voltages. In positive logic, the higher voltage range denotes 1 and the lower range denotes 0.

A combinational circuit is described by

where X is the vector of present input variables, Y is the vector of outputs, and F is a set of Boolean functions. No internal storage is required in the ideal model.

A sequential circuit is described by

and

where Q(t) is the present state and Q(t+1) is the next state. In a clocked system, state changes normally occur only at specified clock edges.

Figure: Conceptual distinction between combinational and sequential systems.

2. Combinational Logic Design

2.1 Boolean representation

The basic Boolean operators are AND, OR, and NOT. A Boolean function may be specified by an equation, truth table, logic diagram, or hardware description. For n independent binary inputs, a complete truth table contains 2ⁿ rows.

Important identities include:

De Morgan’s laws are

A minterm is a product term containing every variable once, either complemented or uncomplemented. A maxterm is a sum term containing every variable once. A function can therefore be expressed in canonical sum-of-products or product-of-sums form.

2.2 Minimization

Minimization reduces gate count, wiring, delay, and often power. Karnaugh maps are useful for small numbers of variables; tabulation methods such as Quine–McCluskey are more systematic for larger functions. Don’t-care conditions may be treated as either 0 or 1 if doing so improves simplification, provided that the resulting behavior is safe for all actually occurring input combinations.

For example, a three-input majority function is 1 when at least two inputs are 1. With inputs A, B, and C,

The expression is symmetric and directly shows the three possible pairs that establish a majority.

2.3 Standard combinational building blocks

Multiplexer. A multiplexer selects one of several data inputs. A 2-to-1 multiplexer with data inputs D₀ and D₁ and select S has

For k select lines, a multiplexer can select one of 2ᵏ inputs.

Decoder. A decoder activates one output corresponding to a binary input code. An n-to-2ⁿ decoder ideally produces one-hot output, although enable inputs and active-low conventions are common in practice.

Encoder and priority encoder. An encoder performs the reverse mapping of a decoder. A priority encoder resolves the case in which several inputs are active by assigning priority, thereby making the output deterministic.

Comparator. For unsigned binary words, comparison begins with the most significant unequal bit. For one-bit inputs A and B:

Arithmetic circuits. A half-adder adds two bits:

A full adder adds A, B, and carry-in Cᵢ:

An n-bit ripple-carry adder connects full adders in cascade. Its principal disadvantage is that carry propagation may pass through all stages. If each stage contributes a worst-case carry delay t_c, the approximate carry-path delay is proportional to n·t_c. Carry-lookahead, carry-select, and prefix adders reduce this delay at the cost of additional area and wiring.

Worked Example 1: Full-adder verification

Let A = 1, B = 0, and Cᵢ = 1. Then

and

Thus the binary result is carry 1 and sum 0, representing decimal 2, which is correct because 1 + 0 + 1 = 2.

3. Practical Issues in Combinational Circuits

The ideal equation does not describe physical delay. Propagation delay is the time between a specified input transition and the corresponding output transition. If different paths have unequal delays, a temporary incorrect pulse may occur.

A static hazard is an unwanted transient in a signal that should remain constant. A static-1 hazard can often be removed by adding a redundant consensus term. For example, the function

may exhibit a static-1 hazard when A changes while B = C = 1. Adding BC gives

The added term does not change the steady-state Boolean function because BC is a consensus term, but it can maintain coverage during unequal path delays. Hazard elimination must be evaluated against the actual implementation and timing environment; algebraic minimization alone is not sufficient.

Fan-in, fan-out, threshold levels, noise margins, power dissipation, and loading also influence reliable operation. In CMOS logic, dynamic power is often approximated by

where α is the activity factor, C_L is effective switched capacitance in farads, V_DD is supply voltage in volts, and f is switching frequency in hertz. The relation assumes capacitive switching dominates and is an approximation, not a complete power model.

4. Sequential Logic and Storage

Sequential systems contain feedback and storage. A storage element preserves information because its next state depends on its current state. The two fundamental categories are latches and flip-flops.

A latch is level-sensitive: it may respond throughout an active enable interval. A flip-flop is edge-triggered: it samples input near a clock transition. A D flip-flop has the characteristic next-state equation

at the active clock edge. A T flip-flop satisfies

A JK flip-flop satisfies

where J and K are inputs and Q is the present state. The JK device avoids the invalid input combination associated with the traditional SR flip-flop, although implementation details still matter.

Timing parameters

For a synchronous path from one flip-flop to another, a simplified setup constraint is

where T_clock is clock period, t_clk-q is clock-to-output delay, t_comb,max is maximum combinational delay, t_setup is receiving flip-flop setup time, and t_skew is the relevant clock-skew margin. The equation assumes a single-cycle path and does not include every uncertainty term.

The maximum clock frequency is approximately

A hold constraint must also be satisfied:

The exact sign convention for skew depends on the clock-arrival definitions. Setup and hold violations can cause metastability, in which the storage element takes an unpredictable time to resolve to a valid logic state. Metastability cannot be eliminated completely, but its probability can be reduced by synchronizer stages, adequate timing margins, and appropriate interface protocols.

5. Registers, Counters, and Shift Structures

A register is a group of flip-flops storing a multibit word. A register may support parallel load, reset, enable, and shifting. A shift register transfers data between adjacent storage elements on clock edges and is used for serial-to-parallel conversion, delay, serialization, and test access.

A counter follows a prescribed sequence of states. A binary up-counter increments according to

where addition is modulo 2ⁿ for an n-bit counter. Thus a four-bit counter has 16 states, from 0000 through 1111, before returning to 0000. A decade counter uses ten states and must deliberately handle six unused states; recovery behavior from those states is an important reliability consideration.

Ripple counters allow one flip-flop output to clock another. They can be compact but exhibit accumulated delay and temporary decoded glitches. Synchronous counters clock all flip-flops together and generally offer better timing predictability.

6. Finite-State Machines

A finite-state machine (FSM) is a sequential model with a finite set of states, input symbols, output symbols, and transition rules. The two principal models are:

• Moore machine: output depends only on present state, Y = G(Q).
• Mealy machine: output depends on state and input, Y = G(Q, X).

Moore outputs are often easier to time and less susceptible to input glitches, whereas Mealy machines may respond faster and require fewer states. In both cases, outputs must be registered when glitch-free external behavior is required.

An FSM design process normally includes specification, state identification, state diagram, state table, state encoding, next-state derivation, output derivation, implementation, and verification. State encoding may be binary, one-hot, Gray, or another scheme. Binary encoding minimizes flip-flops; one-hot encoding can simplify next-state logic in programmable logic; Gray encoding limits the number of simultaneously changing state bits and can be valuable in specific crossing or counter applications.

State minimization

Two states are equivalent if, for every possible input sequence, they produce identical output sequences and transition to equivalent states. Equivalent states may be merged. Minimization reduces hardware, but aggressive optimization must not remove safety, diagnostic, or recovery states required by the system specification.

7. Worked FSM Example: Two-Coin Vending Controller

Consider an illustrative controller accepting 5-unit and 10-unit coins for a product costing 15 units. The machine dispenses the product when the accumulated credit reaches 15 or more. Assume exact coin detection, one coin per clock cycle, and no change returned.

Use states:

• S₀: credit 0
• S₅: credit 5
• S₁₀: credit 10

Inputs are C₅ and C₁₀, with the assumption that at most one is active in a clock cycle. The transitions are:

A practical design may use a Mealy dispense output for immediate response, or a Moore state such as S_D to generate a full-cycle, registered dispense pulse. The latter is generally easier to integrate with a motor or actuator because the output timing is independent of small input glitches.

For binary encoding S₀ = 00, S₅ = 01, and S₁₀ = 10, state 11 is unused. A robust implementation assigns recovery behavior from 11 to S₀. This prevents an upset or power-on uncertainty from causing indefinite operation in an illegal state.

The case illustrates a central engineering trade-off: a minimal state machine may use fewer resources, while a more explicit state structure can improve observability, fault recovery, and interface timing.

8. Clocking, Reset, and Synchronization

A synchronous design uses a common clock and restricts state changes to clock edges. Clock-domain crossings require special treatment because an asynchronous signal may violate setup or hold time. A two-flip-flop synchronizer is a common solution for a single-bit control signal, provided that the signal can tolerate synchronization latency and pulse loss is not possible. Pulses and multibit data generally require handshake protocols, pulse stretchers, asynchronous FIFOs, or Gray-coded pointer methods rather than independent synchronization of each bit.

Reset may be synchronous or asynchronous. An asynchronous reset can force state immediately but may create recovery/removal timing issues during release. A synchronous reset is easier to analyze within the clocked methodology but cannot act until a clock edge. Reset polarity, assertion behavior, deassertion synchronization, and behavior under partial power conditions must be specified explicitly.

9. Hardware Description and Verification

Hardware-description languages represent structure and behavior for synthesis and simulation. Good RTL practice includes:

• use nonblocking assignments for clocked processes;
• assign every combinational output on every path to avoid unintended latches;
• separate next-state logic from state registers where clarity helps;
• define reset and illegal-state behavior;
• avoid unintended combinational feedback;
• constrain clocks and external timing;
• verify both normal operation and fault or boundary conditions.

Simulation alone cannot prove correctness for all input sequences. Assertions, formal equivalence checking, property verification, constrained-random testing, and coverage analysis strengthen confidence. Important properties include mutual exclusion, eventual response, absence of illegal outputs, and correct reset recovery.

10. Applied Case: Reliable Sensor-Alarm Controller

Background

Consider an illustrative industrial temperature-monitoring unit. A sensor interface supplies a digital alarm request, but the signal is asynchronous to the controller clock. The system must filter short disturbances, activate an alarm after three consecutive alarm samples, and deactivate it only after five consecutive safe samples.

Problem

Directly feeding the asynchronous sensor signal into several state-machine inputs can cause metastability or inconsistent sampling. A simple combinational alarm output may chatter when the sensor fluctuates near its threshold.

Analysis and approach

First, pass the single-bit sensor signal through a two-stage synchronizer. Next, use a saturating up/down counter or an FSM. Let the synchronized signal be Aₛ. A counter C increments when Aₛ = 1 and decrements when Aₛ = 0, bounded between 0 and 5. Set the alarm when C reaches 3 and clear it when C reaches 0 after the required safe interval; alternatively, use separate consecutive-event counters to implement exactly three alarm samples and five safe samples.

The exact specification matters. A saturating counter with thresholds provides hysteresis but does not necessarily mean “three consecutive” and “five consecutive” unless the update rules are defined accordingly. For exact consecutive qualification, reset the alarm counter whenever Aₛ = 0 and reset the safe counter whenever Aₛ = 1.

Outcome

The synchronizer reduces metastability propagation risk, while digital qualification prevents nuisance activation. A registered alarm output avoids glitches at the actuator interface. Verification should include asynchronous transitions near clock edges, alternating samples, reset during an alarm, and sensor signals that remain permanently asserted.

Learning points

The case demonstrates that reliable digital design combines Boolean logic, sequential state, timing analysis, interface synchronization, specification precision, and verification. A functionally correct truth table is not enough when real signals are delayed, asynchronous, noisy, or fault-prone.

11. Contemporary Design Considerations

Modern digital systems are commonly implemented in CMOS ASICs, FPGAs, microcontrollers, and systems-on-chip. Design objectives extend beyond logical correctness to power integrity, electromagnetic compatibility, security, functional safety, and lifecycle support.

Low-power design uses clock gating, power gating, voltage scaling, operand isolation, and activity reduction. Clock gating must be implemented with dedicated glitch-safe cells or approved RTL structures. Safety-critical systems may require redundancy, watchdogs, diagnostic states, fail-safe outputs, and standards-based development processes. Security-sensitive controllers must consider fault injection, unauthorized state transitions, information leakage, and secure reset behavior.

Artificial intelligence does not replace the fundamental design discipline. Machine-learning tools can assist with logic optimization, test generation, placement, and anomaly detection, but generated hardware must be checked through simulation, formal methods, timing analysis, and human review. Traceability from requirement to implementation remains essential.

12. Best-Practice Design Workflow

A robust workflow is:

1. Define input, output, timing, reset, and illegal-condition requirements.
2. Separate purely combinational behavior from stored state.
3. Choose an appropriate state model and encoding.
4. Derive equations or RTL and check them against a truth or state table.
5. Analyze propagation delay, hazards, setup, hold, and clock-domain crossings.
6. Define recovery behavior and fault assumptions.
7. Simulate representative and adversarial cases.
8. Apply assertions, formal checks, synthesis, and static timing analysis.
9. Review power, area, testability, safety, and security.
10. Document assumptions and verify the manufactured or programmed implementation.

Chapter Summary

Combinational circuits produce outputs from present inputs, whereas sequential circuits use storage so that previous behavior influences future outputs. Boolean algebra, truth tables, canonical forms, and minimization methods support combinational analysis. Multiplexers, decoders, encoders, comparators, adders, and subtractors are reusable combinational structures.

Sequential systems are built from latches or flip-flops and are described by present-state, input, next-state, and output relationships. Registers, counters, and finite-state machines implement storage, sequencing, and control. Correct operation depends not only on logic equations but also on propagation delay, hazards, setup and hold time, clock skew, reset design, synchronization, and metastability management.

Professional design therefore combines specification, mathematical modeling, RTL implementation, timing analysis, verification, safety, power awareness, and fault recovery. The most reliable systems make timing assumptions explicit and treat illegal, asynchronous, and exceptional conditions as part of the design rather than as afterthoughts.

Key Terms

Combinational circuit: A circuit whose output depends only on present inputs.

Sequential circuit: A circuit whose behavior depends on inputs and stored state.

Boolean algebra: An algebraic system used to represent binary logic.

Minterm: A product term containing every Boolean variable once.

Multiplexer: A circuit that selects one of several inputs.

Decoder: A circuit that maps a binary code to one or more designated outputs.

Priority encoder: An encoder that resolves multiple active inputs according to priority.

Propagation delay: Time between an input transition and the corresponding output response.

Hazard: An unwanted transient caused by unequal signal-path delays.

Latch: A level-sensitive storage element.

Flip-flop: An edge-triggered storage element.

Register: A group of storage elements used to hold a multibit word.

Counter: A sequential circuit that follows a prescribed numerical or symbolic sequence.

Finite-state machine: A sequential model with finite states and defined transitions.

Moore machine: An FSM whose output depends only on present state.

Mealy machine: An FSM whose output depends on present state and input.

Setup time: Minimum interval that input data must be stable before a sampling edge.

Hold time: Minimum interval that input data must remain stable after a sampling edge.

Metastability: An uncertain temporary state caused by violation of storage-element timing requirements.

Clock-domain crossing: Transfer of information between circuits using different or unrelated clocks.

Review Questions

5 Short Answer Questions

1. What is the fundamental difference between combinational and sequential logic?
2. State De Morgan’s two laws.
3. What function does a multiplexer perform?
4. Define setup time and hold time.
5. Distinguish a Moore machine from a Mealy machine.

5 Long Answer Questions

1. Explain the design and operation of a full adder, including its Boolean equations.
2. Discuss hazards in combinational circuits and explain one method of hazard removal.
3. Explain the timing constraints of a synchronous flip-flop-to-flip-flop path.
4. Describe the complete design procedure for a finite-state machine.
5. Compare ripple and synchronous counters with respect to delay, complexity, and applications.

3 Analytical / Application Questions

1. Design a controller for a 15-unit vending machine accepting 5-unit and 10-unit coins. Define states, transitions, outputs, and illegal-state recovery.
2. A four-bit ripple counter shows temporary incorrect decoded outputs during transitions. Analyze the cause and recommend an alternative architecture.
3. An asynchronous alarm input occasionally causes unpredictable behavior in a clocked controller. Propose a synchronization and qualification strategy, and identify assumptions that must be verified.

Multiple Choice Questions with Answers

Question 1

Which expression represents the sum output of a full adder?

A. S = A + B + C_i

B. S = A ⊕ B ⊕ C_i

C. S = AB + C_i

D. S = ABC_i

Correct Answer: B. S = A ⊕ B ⊕ C_i

Question 2

How many rows are required for a complete truth table with four independent binary inputs?

A. 4

B. 8

C. 16

D. 32

Correct Answer: C. 16

Question 3

Which characteristic distinguishes a latch from an edge-triggered flip-flop?

A. A latch is level-sensitive

B. A latch cannot store binary information

C. A flip-flop has no timing requirements

D. A flip-flop is always asynchronous

Correct Answer: A. A latch is level-sensitive

Question 4

For a 2-to-1 multiplexer, which equation is correct?

A. Y = SD₀ + S̅D₁

B. Y = S̅D₀ + SD₁

C. Y = D₀D₁

D. Y = S + D₀ + D₁

Correct Answer: B. Y = S̅D₀ + SD₁

Question 5

Which condition can produce metastability in a flip-flop?

A. Excessive fan-in only

B. Violation of setup or hold time

C. Use of Boolean minimization

D. Stable data well away from the clock edge

Correct Answer: B. Violation of setup or hold time

Question 6

A Moore-machine output depends on:

A. Input only

B. Clock frequency only

C. Present state only

D. Present input and next state only

Correct Answer: C. Present state only

Question 7

What is the main timing disadvantage of a ripple-carry adder as word length increases?

A. The sum becomes nonbinary

B. Carry propagation delay increases

C. It cannot add zero

D. It requires no logic gates

Correct Answer: B. Carry propagation delay increases

Question 8

For a four-bit binary counter, how many distinct states are available in normal modulo operation?

A. 4

B. 8

C. 16

D. 32

Correct Answer: C. 16

Question 9

Which technique is commonly used for a single-bit asynchronous control signal entering a synchronous domain?

A. Two-stage synchronizer

B. Direct connection to multiple flip-flops

C. Removing the receiving clock

D. Using only a decoder

Correct Answer: A. Two-stage synchronizer

Question 10

In the dynamic-power approximation P = αC_LV_DD²f, reducing the supply voltage generally reduces dynamic power because power varies with:

A. V_DD

B. V_DD²

C. 1/V_DD

D. V_DD³

Correct Answer: B. V_DD²