Combinational Logic Design

Introduction

Combinational logic circuits are digital systems whose outputs depend only on the present values of their inputs. Unlike sequential circuits, they do not store information internally and therefore have no required memory element or clock. They are fundamental building blocks in mechatronic controllers, embedded systems, arithmetic-logic units, sensor interfaces, safety interlocks, address-decoding systems, and programmable digital hardware.

A systematic design process converts a functional requirement into Boolean equations, simplifies those equations, selects an implementation technology, and verifies the result. This chapter develops that process through arithmetic circuits, multiplexers, decoders, encoders, comparators, and programmable combinational functions.

Learning Objectives

By the end of this chapter, you should be able to:

1. Distinguish combinational logic from sequential logic.
2. Translate specifications, truth tables, and timing requirements into Boolean functions.
3. Simplify combinational logic using Boolean algebra and Karnaugh maps.
4. Design and analyze half-adders, full-adders, subtractors, and ripple-carry adders.
5. Explain and apply multiplexers, demultiplexers, decoders, encoders, and priority encoders.
6. Design magnitude comparators and identify equality, greater-than, and less-than conditions.
7. Implement Boolean functions using multiplexers, decoders, and programmable logic devices.
8. Verify circuits using simulation, timing analysis, and hardware tests.

1. Nature of Combinational Systems

A combinational circuit can be represented as

where X₁ through Xₙ are input variables, Y is an output vector, and F is a Boolean function. The output changes after a finite propagation delay following an input change. In an ideal model, the output changes immediately; in a physical circuit, gates require time to respond.

A combinational design normally follows these steps:

1. Define inputs, outputs, active levels, and operating conditions.
2. Construct a truth table or Boolean specification.
3. Derive canonical sum-of-products or product-of-sums expressions.
4. Simplify the expressions while preserving required behavior.
5. Select gates, standard integrated circuits, or programmable hardware.
6. Analyze propagation delay, hazards, loading, power, and unused states.
7. Simulate and verify normal and abnormal operating conditions.

A truth table with n binary inputs contains 2ⁿ input combinations. A function may be written in canonical sum-of-products form as

Here, Σm denotes the sum of minterms for which F = 1; the decimal indices correspond to binary input combinations, with a stated variable order. The expression above is equivalent to F = C because minterms 1, 3, 5, and 7 are exactly the rows where C = 1.

Don't-care conditions, written d(...) or X, represent input combinations that never occur or whose outputs are irrelevant. They may be treated as either 0 or 1 during simplification, but only when doing so cannot create an unsafe output under a valid operating condition.

2. Boolean Representation and Simplification

The principal Boolean operations are AND, OR, and NOT. In algebraic notation, AND is written by juxtaposition, OR by +, and complementation by an overbar or apostrophe. Thus, AB means A AND B, A + B means A OR B, and A′ means NOT A.

Important identities include:

A Karnaugh map groups adjacent 1-cells to obtain a simplified sum-of-products expression. Groups must contain 1, 2, 4, 8, and so forth cells; adjacency includes wraparound at map edges. Each group produces a product term containing only variables that remain constant throughout that group. Overlapping groups are permitted when they reduce the final expression.

For example, if a three-variable function is 1 for minterms 1, 3, 5, and 7, all four cells can be grouped. The variables A and B vary, while C remains 1, so F = C. A simplified expression generally reduces gate count, propagation delay, power consumption, and wiring complexity, although technology-specific optimization may produce a different preferred form.

3. Arithmetic Circuits

3.1 Half-Adder

A half-adder adds two one-bit operands A and B. Its outputs are sum S and carry C.

The exclusive-OR operation produces 1 when exactly one input is 1. The truth table is:

A half-adder cannot accept a carry from a less significant bit, so it is suitable only for the least significant position when no input carry exists.

3.2 Full-Adder

A full-adder adds A, B, and an input carry Cᵢ. It produces sum S and output carry Cₒ.

The carry expression is a majority function: Cₒ is 1 when at least two of the three inputs are 1. A full-adder can be constructed from two half-adders and an OR gate. If X = A ⊕ B, the first half-adder generates X and AB; the second generates S = X ⊕ Cᵢ and XCᵢ; ORing the two carry outputs gives Cₒ = AB + XCᵢ.

3.3 Ripple-Carry Addition

An n-bit ripple-carry adder connects n full-adders in cascade. The carry from bit i becomes the input carry of bit i + 1. For two four-bit numbers A₃A₂A₁A₀ and B₃B₂B₁B₀, the circuit produces S₃S₂S₁S₀ and a final carry C₄.

The principal limitation is delay. If each full-adder contributes a worst-case carry propagation delay tₚ, the approximate worst-case carry delay through n stages is

where tₚ is measured in seconds and assumes the carry must propagate through every stage. This is an approximation; actual delay depends on the logic family, loading, input transition, and internal implementation. Faster adders, such as carry-lookahead adders, compute carries using generate and propagate signals.

For bit i, define

Then

where Gᵢ indicates that the stage generates a carry and Pᵢ indicates that it propagates an incoming carry.

3.4 Subtraction

Binary subtraction is commonly implemented using two's complement:

For an n-bit circuit, every bit of B is complemented and a carry-in of 1 is applied to the least significant full-adder. An adder-subtractor uses a control signal M. XOR gates produce Bᵢ ⊕ M, and the least significant carry-in is M. When M = 0, the circuit adds; when M = 1, it subtracts.

Two's-complement overflow occurs when the mathematical result lies outside the representable signed range. For signed n-bit numbers, the range is −2ⁿ⁻¹ through 2ⁿ⁻¹ − 1. A useful detection rule is

where Cₙ is the carry into the sign position's next stage and Cₙ₋₁ is the carry into the sign bit. Equivalently, overflow occurs when two operands of the same sign produce a result of the opposite sign.

4. Multiplexers and Data Selection

A multiplexer, or MUX, selects one of several data inputs and connects it to a single output. A 2-to-1 multiplexer has data inputs D₀ and D₁, select input S, and output Y:

When S = 0, Y = D₀; when S = 1, Y = D₁. A 4-to-1 MUX uses two select lines S₁ and S₀ and has the expression

Multiplexers are useful for bus selection, sensor-source selection, arithmetic-unit control, and implementation of arbitrary Boolean functions. To implement F(A,B,C) = Σm(1,2,6,7) using a 4-to-1 MUX, choose A and B as select inputs. For each AB combination, determine the required data input as a function of C:

Thus, connect D₀ to C, D₁ and D₂ to C′, and D₃ to logic 1. This method is systematic and often avoids a separate large gate network.

A demultiplexer performs the reverse routing operation: one data input is directed to one of several outputs according to select lines. It is used in data distribution and address-controlled communication.

5. Decoders and Encoders

An n-to-2ⁿ decoder converts an n-bit binary code into one active output line. For a 2-to-4 active-high decoder with inputs A and B and enable E:

Only one output is active when E = 1. When E = 0, all outputs are inactive for an active-high design. Decoder outputs can generate minterms, select memory locations, drive displays, or activate one actuator among many. Designers must check whether a particular integrated circuit uses active-high or active-low enable and output signals.

An encoder converts one active input among many into a binary code. A simple 4-to-2 encoder assumes exactly one input is active. If multiple inputs may be active, the result is ambiguous; a priority encoder resolves this by assigning precedence, usually to the highest-priority input. A valid output flag is often included to distinguish “no input active” from a legitimate code.

Priority logic must be designed carefully in safety applications. If two sensors assert simultaneously, the circuit should produce a documented and deterministic response rather than relying on unspecified gate delays.

6. Magnitude Comparators

A comparator determines whether A is greater than, equal to, or less than B. For one-bit inputs:

The equality expression is also A XNOR B. For multi-bit unsigned numbers, comparison begins at the most significant bit because it has the greatest positional weight. For two n-bit words A and B, equality is

where ∏ denotes the AND of all bitwise equality results. A greater-than circuit can be formed by identifying the first bit, scanning from most significant to least significant, at which A and B differ, and confirming that A has 1 while B has 0 at that position.

For signed two's-complement comparison, the sign bit changes the interpretation. A negative number is less than a positive number, regardless of the magnitudes of the remaining bits. Therefore, a signed comparator must treat the sign position separately or use a component explicitly specified for signed comparison.

7. Programmable Combinational Logic

Programmable logic provides configurable interconnections between logic resources. Common structures include programmable read-only memory (PROM), programmable logic arrays (PLA), programmable array logic (PAL), and field-programmable gate arrays (FPGAs).

A PROM implements a truth table by using input variables as an address and storing the desired output word at every address. For n inputs and m outputs, the memory requires 2ⁿ address locations, each storing m bits. This is direct and systematic but can be inefficient for sparse functions.

A PLA has programmable AND and OR planes. It can implement several functions while sharing product terms. A PAL generally has a programmable AND plane and a fixed OR plane, simplifying hardware at the expense of flexibility. Modern FPGAs use lookup tables, configurable routing, registers, and dedicated arithmetic resources. A k-input lookup table can implement any Boolean function of k variables by storing 2ᵏ configuration bits, subject to the device architecture.

Hardware description languages such as VHDL and Verilog allow the designer to describe a truth table, equation, or structural interconnection. Synthesis tools convert the description into hardware. Correct combinational coding requires that every output be assigned for every possible control condition; otherwise, the synthesis tool may infer unintended latches, which are sequential elements.

8. Hazards, Timing, and Verification

A circuit's propagation delay is the time between an input transition and the corresponding stable output transition. A path with several gates may have a worst-case delay approximated by the sum of the delays along the longest sensitized path:

where tₚd,k is the propagation delay of gate k. The approximation assumes delays are additive and that the path is logically active.

A static hazard is a temporary incorrect pulse caused by unequal path delays. For example, a function that should remain at 1 while one input changes may briefly fall to 0 if two adjacent product terms do not overlap physically. Karnaugh-map hazard elimination adds a redundant consensus term covering the transition. The redundant term does not change the steady-state Boolean function, but it can prevent the glitch.

Verification should include:

• Exhaustive truth-table simulation for small circuits.
• Directed tests for boundary cases, such as all zeros, all ones, carry generation, and overflow.
• Randomized tests for larger arithmetic blocks.
• Timing simulation using realistic gate delays.
• Hardware tests with controlled input levels and measured outputs.
• Checks for floating inputs, incorrect active levels, electrical overloading, and power-up behavior.

Simulation verifies the modeled design, not automatically the physical implementation. Measurement remains necessary when wiring, noise, fan-out, power integrity, or device tolerances may affect operation.

Figure: A practical closed-loop workflow for designing and verifying combinational logic.

9. Applied Case: Safety Interlock for a Mechatronic Cell

Background

Consider an illustrative automated machining cell with a motor, a guard switch G, an emergency-stop signal E, a controller-enable signal C, and an overload signal O. The motor may run only when the guard is closed, the emergency stop is released, the controller is enabled, and no overload is present.

Problem and analysis

Assume all signals are active high except the guard-closed signal, which is represented directly as G = 1 when closed. The motor command M should be 1 only when G, E, C are 1 and O is 0. Therefore,

This direct AND implementation is easy to inspect and verify. The truth table need not list all 16 combinations if the safety requirement is expressed as a conjunction: every invalid condition forces M = 0.

Approach and verification

The design should use fail-safe wiring and clearly defined signal polarity. Emergency-stop hardware should not rely solely on a software-generated combinational equation; applicable machinery-safety standards may require redundant contacts, monitored relays, diagnostic coverage, and a controlled reset. During verification, test each permissive condition individually, then test simultaneous faults: open guard, emergency-stop activation, controller disablement, and overload.

Outcome and learning points

The Boolean model provides a concise functional specification, but safe engineering also requires electrical fault analysis, response-time limits, reset behavior, testing intervals, and compliance with relevant regulations. A logically correct circuit can still be unsafe if a broken wire creates a false “safe” signal or if a single component failure defeats the interlock.

10. Design Best Practices and Limitations

Use explicit signal names such as guard_closed rather than ambiguous names such as guard. Document active-high and active-low conventions. Avoid leaving CMOS inputs floating. Include enable and valid signals where an encoder or decoder has unused states. Consider fan-out, voltage thresholds, noise margins, power dissipation, and physical connector orientation.

Minimization is not always the sole objective. A slightly larger circuit may have lower delay, better hazard behavior, improved testability, or clearer safety review. In programmable devices, synthesis and place-and-route tools may optimize a Boolean expression differently from a hand-built gate network. Timing constraints must therefore be verified on the target technology.

Artificial intelligence tools can assist with truth-table generation, HDL drafting, test-vector creation, and fault-list analysis. They must not replace engineering review: generated logic can contain polarity errors, omitted states, inferred latches, or unsafe assumptions. Requirements, simulation results, synthesized hardware, and measured behavior must remain traceable.

Chapter Summary

Combinational logic maps present inputs to present outputs and is designed through specification, Boolean representation, simplification, implementation, and verification. Half-adders and full-adders form the basis of binary arithmetic; ripple-carry structures are simple but delay increases with word length. Multiplexers select data and can implement arbitrary Boolean functions. Decoders generate minterms and activate one-of-many outputs, while encoders perform the reverse operation and priority encoders resolve simultaneous requests. Comparators determine equality and relative magnitude, with separate care required for signed numbers.

Programmable devices implement truth tables and shared product terms efficiently, while HDLs provide scalable descriptions for synthesis. Propagation delay, hazards, active-level conventions, unused states, electrical loading, and safety requirements must be considered in practical designs. Simulation is essential, but physical measurement and fault-oriented verification are also required.

Key Terms

Combinational logic: Logic whose outputs depend only on current inputs.

Truth table: A tabular listing of outputs for every input combination.

Minterm: A product term that corresponds to exactly one input combination.

Don't-care condition: An input condition whose output is irrelevant or impossible in normal operation.

Karnaugh map: A graphical method for simplifying Boolean functions.

Half-adder: A circuit that adds two one-bit operands.

Full-adder: A circuit that adds two bits and an input carry.

Ripple-carry adder: An adder in which carries pass sequentially between stages.

Two's complement: A binary representation commonly used for signed arithmetic and subtraction.

Overflow: A result outside the representable numeric range.

Multiplexer: A circuit that selects one of several inputs.

Demultiplexer: A circuit that routes one input to one selected output.

Decoder: A circuit that activates an output corresponding to an input code.

Encoder: A circuit that converts an active input into a binary code.

Priority encoder: An encoder that resolves multiple active inputs using precedence.

Comparator: A circuit that determines equality or relative magnitude.

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

Hazard: An unwanted transient caused by unequal path delays.

Programmable logic: Configurable hardware used to implement digital functions.

Review Questions

Short Answer Questions

1. What distinguishes a combinational circuit from a sequential circuit?
2. State the Boolean equations for a half-adder.
3. Why does a ripple-carry adder become slower as the number of bits increases?
4. What is the function of the select input in a multiplexer?
5. Why is a priority encoder required when more than one input may be active?

Long Answer Questions

1. Derive the full-adder sum and carry equations from its truth table.
2. Explain how a 4-to-1 multiplexer can implement a three-variable Boolean function.
3. Compare decoders, encoders, and priority encoders, including typical applications.
4. Explain two's-complement subtraction and signed overflow detection.
5. Describe a complete workflow for designing and verifying a combinational circuit.

Analytical / Application Questions

1. Design a four-bit adder-subtractor controlled by a mode signal. Specify the input transformations, carry-in condition, and overflow test.
2. Implement F(A,B,C) = Σm(0,2,5,7) using a 4-to-1 multiplexer with A and B as select inputs. Determine each data input as a function of C.
3. Develop a Boolean interlock for a motor that requires two independent enable signals, a closed guard, and no overload. Discuss how the logic should be supplemented for fail-safe operation.

Multiple Choice Questions with Answers

Question 1

Which equation represents the sum output of a half-adder?

A. A + B

B. AB

C. A ⊕ B

D. A′B

Correct Answer: C. A ⊕ B

Question 2

For a full-adder, which expression represents the carry output?

A. A ⊕ B ⊕ Cᵢ

B. AB + ACᵢ + BCᵢ

C. A + B + Cᵢ

D. A′B′Cᵢ

Correct Answer: B. AB + ACᵢ + BCᵢ

Question 3

A 4-to-1 multiplexer requires how many select inputs?

A. 1

B. 2

C. 4

D. 8

Correct Answer: B. 2

Question 4

What does a decoder normally do?

A. Stores previous input values

B. Activates an output corresponding to an input code

C. Adds two binary numbers

D. Removes propagation delay

Correct Answer: B. Activates an output corresponding to an input code

Question 5

For one-bit inputs, which condition means A is greater than B?

A. A′B

B. A′B′ + AB

C. AB′

D. A + B

Correct Answer: C. AB′

Question 6

If a four-bit ripple-carry adder has a full-adder carry delay of 10 ns, what is the approximate worst-case carry propagation delay under the simple additive model?

A. 2.5 ns

B. 10 ns

C. 14 ns

D. 40 ns

Correct Answer: D. 40 ns

Question 7

Which technique is primarily used to simplify Boolean functions graphically?

A. Fourier transform

B. Karnaugh map

C. Nyquist plot

D. State-transition diagram

Correct Answer: B. Karnaugh map

Question 8

In two's-complement subtraction, A − B is implemented as:

A. A + B

B. A + B′ without a carry-in

C. A + B′ + 1

D. A′ + B + 1

Correct Answer: C. A + B′ + 1

Question 9

What is the main purpose of a priority encoder?

A. To resolve multiple active inputs according to precedence

B. To convert analog voltage into current

C. To delay every input equally

D. To store a binary word permanently

Correct Answer: A. To resolve multiple active inputs according to precedence

Question 10

A static hazard is best described as:

A. A permanent short circuit

B. An unwanted transient caused by unequal path delays

C. A valid change in a truth table

D. A required clock transition

Correct Answer: B. An unwanted transient caused by unequal path delays