Combinational Logic Circuit Design

Introduction

A combinational logic circuit is a digital network whose output values depend only on the present input values. Unlike a sequential circuit, it has no intentional memory element or feedback path used to store state. Combinational circuits form the computational foundation of processors, controllers, communication systems, instrumentation, and embedded hardware.

Typical combinational building blocks include adders, subtractors, comparators, decoders, encoders, multiplexers, demultiplexers, parity generators, parity checkers, and programmable logic devices. Their design involves translating a functional specification into Boolean expressions, simplifying those expressions, selecting an implementation technology, and verifying timing, power, and reliability.

A practical design is not judged only by logical correctness. Propagation delay, circuit area, power dissipation, fan-out, hazards, noise margins, testability, and scalability are also important. This chapter develops a systematic approach to these issues.

Learning Objectives

After completing this chapter, a student should be able to:

1. Specify a combinational function using truth tables, Boolean expressions, and logic diagrams.
2. Simplify Boolean functions using algebraic methods and Karnaugh maps.
3. Design and analyze arithmetic circuits, comparators, encoders, decoders, multiplexers, and demultiplexers.
4. Construct parity-generation and parity-checking circuits.
5. Explain hazards and apply appropriate hazard-removal techniques.
6. Compare implementation choices in terms of speed, area, power, and flexibility.
7. Use programmable logic devices to implement combinational functions.
8. Verify a design using systematic simulation and hardware testing.

1. Specification and Representation of Combinational Functions

For a circuit with n binary inputs, there are 2ⁿ possible input combinations. If the circuit has m outputs, each output is a Boolean function of the inputs. A specification may be expressed as:

• a verbal description;
• a truth table;
• a Boolean expression;
• a sum of minterms or product of maxterms;
• a logic-gate diagram;
• a hardware-description-language model.

For variables A, B, and C, a minterm is a product term containing every variable exactly once. For example, the minterm corresponding to A = 1, B = 0, C = 1 is A B' C. The function can be written as a sum of minterms:

Here, the listed decimal numbers identify the rows for which F = 1, using ABC as a binary index. Equivalently, a function can be specified by its zero rows using a product of maxterms:

The two forms are complementary descriptions of the same function. Don’t-care conditions, denoted X, identify input combinations that never occur or whose output is irrelevant. They may be assigned either 0 or 1 during simplification, provided that the resulting circuit remains correct for all valid operating conditions.

Boolean Laws Used in Design

Important identities include:

The consensus theorem is particularly useful in hazard analysis, because the consensus term may be logically redundant but electrically important.

Two-Level Forms

A sum-of-products (SOP) circuit consists of AND terms feeding an OR gate. A product-of-sums (POS) circuit consists of OR terms feeding an AND gate. NAND–NAND networks naturally implement SOP expressions, whereas NOR–NOR networks naturally implement POS expressions. Universal NAND or NOR implementations can be formed by using one gate type to realize inversion, conjunction, and disjunction.

2. Simplification and Optimization

Boolean simplification reduces gate count, literals, wiring, delay, or power. Algebraic manipulation is useful for small expressions, while Karnaugh maps are convenient for functions with a modest number of variables.

In a Karnaugh map, adjacent cells differ in exactly one variable. Groups must contain 1, 2, 4, 8, or another power of two cells. Groups may wrap around map edges, and overlapping groups are allowed. Each group produces a product term containing only variables that remain constant throughout the group. The largest valid groups normally produce the simplest expression.

Worked Example 1: Karnaugh-Map Simplification

Consider:

The minterms correspond to all combinations for which B = 0, while A, C, and D vary. Therefore:

The original specification could require several four-variable product terms, whereas the simplified circuit requires only an inverter. This illustrates why simplification can greatly reduce area and delay.

A minimization that reduces literal count is not always the fastest implementation. A factored expression may reduce wiring, and a balanced multilevel implementation may reduce the longest propagation path. Thus, optimization must consider the target technology and design constraints.

3. Timing, Area, and Power

A gate does not respond instantaneously. Propagation delay is the time between a specified input transition and the corresponding output transition. For a path containing several gates, the approximate path delay is the sum of the delays of gates on the path:

where t_pd,i is the propagation delay of the i-th gate. This approximation assumes that loading and input transition effects have already been included in the individual delay values.

The maximum combinational delay, often called the critical-path delay, determines the highest safe operating frequency of a synchronous system. If setup time, clock skew, and other timing margins are included, a simplified synchronous constraint is:

where T_clock is the clock period, t_clk-q is source flip-flop clock-to-output delay, t_pd,critical is the worst combinational delay, t_setup is destination setup time, and t_skew represents the relevant clock-skew margin. This relation applies to a single-register-to-register path under the stated timing model.

Dynamic switching power is commonly 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 expression shows that reducing voltage is especially effective, although voltage reduction may increase delay or reduce noise margin. Static leakage power must also be considered in modern integrated circuits.

Fan-out, capacitive loading, interconnect length, and simultaneous switching affect actual performance. A logically minimal circuit may therefore be inferior to a slightly larger circuit with shorter wires or better buffering.

4. Arithmetic Circuits

4.1 Half Adder

A half adder adds two one-bit operands A and B. It produces sum S and carry C:

The half-adder truth table is:

A half adder cannot accept a carry from a less significant position.

4.2 Full Adder

A full adder adds A, B, and an input carry C_in. Its outputs are sum S and carry C_out:

An equivalent majority expression is:

The full adder can be constructed from two half adders and an OR gate. Cascading n full adders forms a ripple-carry adder. Its main advantage is simplicity; its disadvantage is that each carry must wait for the preceding carry.

4.3 Carry-Lookahead Addition

Define the propagate and generate signals for bit position i:

The carry relation is:

For a four-bit section:

Lookahead logic computes carries in parallel, reducing delay at the cost of additional gates and wiring. Practical adders often use hierarchical carry-lookahead, carry-select, carry-skip, or prefix structures.

4.4 Subtraction

Binary subtraction can use two’s complement:

The same adder hardware performs addition and subtraction by complementing each B bit when a control signal SUB = 1 and applying SUB as the initial carry. For each bit:

When SUB = 0, B_i = B_i; when SUB = 1, B_i = B_i'. The initial carry is also set to 1 for subtraction.

Worked Example 2: Four-Bit Two’s-Complement Subtraction

Compute 7 − 5 using four bits.

Invert 0101 and add 1:

Then:

Discarding the carry beyond four bits gives 0010, which is decimal 2. The result is valid because it lies within the four-bit signed range −8 to +7.

5. Comparators

A one-bit magnitude comparator produces outputs indicating A > B, A = B, and A < B:

where ⊙ denotes XNOR.

For multi-bit unsigned numbers, the most significant unequal bit determines the result. For n-bit operands A and B, define X_i = A_i ⊙ B_i. Then equality is:

The greater-than function can be expressed as a priority chain from the most significant bit to the least significant bit:

This expression assumes unsigned binary representation and indexes bit n−1 as the most significant bit.

6. Decoders and Encoders

An n-to-2ⁿ decoder activates one output corresponding to the binary input code. With an enable input E, an output may be written:

where m_k is the minterm for input code k. A 3-to-8 decoder, for example, generates eight mutually exclusive minterms. Decoders are used in memory address selection, instruction decoding, display control, and demultiplexing.

An encoder performs the reverse operation: it converts one active input among several into a binary code. A simple encoder assumes that no more than one input is active. A priority encoder resolves multiple active inputs by assigning priority, commonly to the highest-order input. It also provides a valid-output signal to distinguish an actual code from the all-zero condition.

Encoders and decoders may use active-high or active-low signals. Designers must check enable polarity, output polarity, and whether unused input combinations are treated as don’t-care conditions.

7. Multiplexers and Demultiplexers

A multiplexer (MUX) selects one of several data inputs and connects it to a single output. A 2-to-1 MUX with data inputs D₀ and D₁ and select S has:

A multiplexer can implement arbitrary Boolean functions. Select variables are connected to the select inputs, and the data inputs are tied to 0, 1, a variable, or its complement according to the function’s truth table.

Worked Example 3: MUX Implementation

Implement:

Use A and B as select variables. For each AB combination, inspect F as C varies:

Thus, a 4-to-1 MUX uses A and B as selects and connects its data inputs to C, C', C, and C, respectively.

A demultiplexer routes one input to one of several outputs. For a 1-to-2 demultiplexer with input D and select S:

Demultiplexers are used for data distribution, control-signal routing, and serial-to-parallel structures.

8. Parity Circuits

Parity provides simple error detection. Even parity makes the total number of 1s, including the parity bit, even. For data bits D₀ through D_{n−1}, the even-parity bit is:

An odd-parity bit is the complement of the even-parity bit:

At the receiver, XORing all received data and parity bits gives 0 for a correctly received even-parity word. A parity circuit detects any odd number of bit errors but cannot reliably detect an even number of errors, and it cannot identify the erroneous bit. Stronger methods include cyclic redundancy checks, checksums, and error-correcting codes.

9. Hazards and Glitches

A hazard is an unwanted transient caused by unequal propagation delays. A static-1 hazard occurs when the output should remain 1 but briefly falls to 0. A static-0 hazard occurs when the output should remain 0 but briefly rises to 1. A dynamic hazard occurs when the output changes more than once during a transition that should produce a single change.

Consider:

If B = C = 1 and A changes, the two product terms logically maintain F = 1. In a real circuit, however, A and A' do not change simultaneously. The output may momentarily fall. Adding the consensus term BC gives:

The added term does not change the steady-state Boolean function because BC is the consensus term, but it provides an overlapping path that prevents the static-1 hazard under the stated transition condition.

Hazard-reduction practices include:

• using hazard-free SOP or POS covers;
• adding consensus terms where appropriate;
• avoiding unnecessary multilevel reconvergent paths;
• synchronizing outputs before they are sampled;
• using registered interfaces for control signals;
• verifying behavior with realistic gate delays rather than zero-delay simulation.

Hazards are especially important in asynchronous systems, clock gating, reset logic, and circuits driving sensitive analog or timing interfaces. A hazard that is harmless before a register may be critical if it clocks or resets another circuit.

10. Programmable Logic Implementation

Programmable logic devices implement combinational functions using configurable interconnections. Common technologies include:

A k-input lookup table can implement any Boolean function of k variables by storing 2ᵏ output values. FPGA synthesis tools transform HDL descriptions into LUTs, multiplexers, dedicated carry chains, and routing resources. Although this greatly simplifies implementation, designers must still understand the resulting hardware. Poorly written HDL may infer latches, unnecessarily deep logic, excessive switching, or unintended priority structures.

For combinational HDL, every output must be assigned for every input condition. Incomplete assignments in a procedural block may infer storage rather than pure combinational logic. Synthesis reports, static timing analysis, power estimation, and post-synthesis simulation are essential verification tools.

11. Design Methodology

A disciplined design flow is:

1. Define input, output, polarity, timing, and environmental requirements.
2. Construct a truth table or formal behavioral specification.
3. Identify don’t-care conditions carefully.
4. Derive Boolean equations or select an appropriate standard block.
5. Simplify and factor the logic.
6. Choose an implementation: gates, MUX/decoder structure, PLA, CPLD, FPGA, or ASIC cells.
7. Estimate delay, area, fan-out, and power.
8. Check hazards and signal integrity.
9. Simulate normal, boundary, and illegal input conditions.
10. Verify the physical implementation using timing and hardware measurements.

Functional verification should include exhaustive simulation for small input spaces and constrained-random or formal methods for larger designs. Assertions can specify properties such as mutual exclusivity of decoder outputs or correctness of an adder’s arithmetic relation.

12. Applied Case: Safety Interlock Controller

Background

Consider an illustrative conveyor system with three sensors: GUARD indicates that a protective guard is closed, READY indicates that the drive is ready, and START is the operator command. The motor-enable output M should be 1 only when all three conditions are satisfied.

Problem

The controller must prevent operation if the guard is open or the drive is not ready. In addition, an emergency-stop input ESTOP is active high and must override all normal requests.

Analysis

Assume active-high normal signals and active-high ESTOP. The required condition is:

This is a combinational enable condition. However, a real safety system should not rely solely on a simple combinational equation. Emergency-stop circuits commonly use redundant contacts, monitored relays, fault detection, and safety-rated control architecture.

Approach and Solution

The logic can be implemented with a four-input AND gate after inverting ESTOP, or with cascaded gates. A safer architecture may use a safety relay or certified safety controller whose output contacts remove actuator power independently of ordinary logic. The digital controller can provide status and diagnostics, but it should not be the only protective mechanism.

The design should be tested for all combinations of inputs, including sensor disagreement, power-up states, broken wires, and transition overlap. If an enable signal must never glitch high, the circuit should be analyzed for hazards and may require registered logic or fail-safe hardware.

Outcome and Learning Points

The Boolean expression precisely describes normal operation, while the safety analysis reveals requirements not captured by truth-table correctness alone. Electrical design must consider fault behavior, diagnostic coverage, fail-safe polarity, certification, and the consequences of a transient output.

13. Challenges, Limitations, and Best Practices

Combinational design has several limitations. Gate-level minimization may increase fan-in or wiring congestion. A low-area circuit may be slow, and a fast circuit may consume more power. Don’t-care simplification can be dangerous if an assumed-invalid input becomes possible because of a software or hardware change. Simulation with ideal delays may hide hazards. Finally, arithmetic overflow, signedness, and signal polarity are frequent sources of system-level errors.

Best practices include:

• document signal names, polarity, width, and numerical interpretation;
• use standard verified components when available;
• separate functional correctness from timing closure;
• review synthesis and timing reports rather than trusting source code alone;
• add assertions for important relationships;
• test illegal and boundary conditions;
• avoid using combinational glitches as clocks or asynchronous controls;
• apply the least-powerful implementation that satisfies performance and reliability requirements;
• use independent review for safety-critical logic.

Contemporary designs increasingly use automated logic synthesis, formal equivalence checking, power-aware optimization, and machine-learning-assisted design-space exploration. These tools can search large implementation spaces, but they do not replace engineering judgment about specifications, safety, or physical behavior.

Chapter Summary

Combinational circuits produce outputs from present inputs and are specified using truth tables, Boolean expressions, minterms, maxterms, and logic diagrams. Boolean algebra and Karnaugh maps reduce expressions, but practical optimization must also consider delay, area, power, fan-out, and wiring.

Half adders and full adders form the basis of arithmetic units. Ripple-carry adders are simple but slow for wide operands, whereas carry-lookahead and related structures improve speed through parallel carry computation. Two’s-complement arithmetic allows one adder to perform both addition and subtraction.

Comparators use XNOR and priority logic to determine equality and magnitude. Decoders generate minterms, encoders convert active inputs to codes, multiplexers select data or implement functions, and demultiplexers distribute data. XOR-based parity circuits detect odd numbers of bit errors but do not locate errors or reliably detect even numbers of errors.

Unequal propagation delays can create static and dynamic hazards. Consensus terms, hazard-free covers, synchronization, and careful timing analysis reduce their consequences. Programmable logic devices provide flexible implementations, but designers must understand synthesis, timing, power, and verification.

A complete engineering design flow begins with an unambiguous specification and ends with simulation, static analysis, hardware verification, and—where applicable—safety assessment.

Key Terms

Combinational circuit: A circuit whose outputs depend only on present inputs.

Minterm: A product term containing every input variable once.

Maxterm: A sum term containing every input variable once.

Don’t-care condition: An input condition for which either output value is acceptable.

SOP: Sum-of-products Boolean form.

POS: Product-of-sums Boolean form.

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 carry propagates through successive stages.

Carry-lookahead adder: An adder that computes carries using generate and propagate signals.

Comparator: A circuit that determines equality or relative magnitude.

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 by priority.

Multiplexer: A circuit that selects one of several inputs.

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

Parity: A one-bit error-detection method based on the number of 1s.

Hazard: An unwanted transient caused by unequal propagation delays.

Critical path: The combinational path with the greatest timing delay.

Programmable logic device: Hardware with configurable logic and interconnections.

Review Questions

Short Answer Questions

1. What distinguishes a combinational circuit from a sequential circuit?
2. State the Boolean equations for the sum and carry outputs of a half adder.
3. Why is a ripple-carry adder slower than a carry-lookahead adder?
4. What function does a multiplexer perform?
5. What type of error can even parity fail to detect?

Long Answer Questions

1. Explain SOP and POS representations and describe how NAND–NAND and NOR–NOR networks implement them.
2. Derive the full-adder carry equation and explain two different ways to implement a full adder.
3. Describe the operation and applications of decoders, encoders, and priority encoders.
4. Explain static-1, static-0, and dynamic hazards, including a method for removing a static-1 hazard.
5. Compare PROMs, PLAs, PALs, CPLDs, and FPGAs for combinational logic implementation.

Analytical / Application Questions

1. Design a 4-to-1 multiplexer implementation for F(A,B,C) = ∑m(0,2,3,6), using A and B as select inputs. Specify each data input in terms of C.
2. A four-bit adder has four identical ripple stages, each with a worst-case carry propagation delay of 12 ns. Estimate the carry-chain delay and explain how a carry-lookahead design could improve it. State the simplifying assumption used.
3. A control output is defined by F = AB + A'C, with B = C = 1 while A changes. Identify the possible hazard and give a logically equivalent hazard-reduced expression.

Multiple Choice Questions with Answers

Question 1

Which expression gives the carry output of a half adder?

A. A ⊕ B

B. AB

C. A + B

D. A'B + AB'

Correct Answer: B. AB

Question 2

For a full adder, which expression represents the sum output?

A. A + B + C_in

B. AB + C_in

C. A ⊕ B ⊕ C_in

D. A'B'C_in

Correct Answer: C. A ⊕ B ⊕ C_in

Question 3

What is the principal advantage of carry-lookahead addition over ripple-carry addition?

A. It eliminates all logic gates

B. It computes carry signals more in parallel

C. It uses no input operands

D. It always consumes less area

Correct Answer: B. It computes carry signals more in parallel

Question 4

A 2-to-1 multiplexer with select S and inputs D₀ and D₁ has output:

A. SD₀ + S'D₁

B. S'D₀ + SD₁

C. D₀D₁ + S

D. S ⊕ D₀ ⊕ D₁

Correct Answer: B. S'D₀ + SD₁

Question 5

What does a decoder generally produce?

A. A selected binary input from many outputs

B. A set of minterm-like outputs from an input code

C. An analog voltage proportional to the input

D. A stored sequence of previous inputs

Correct Answer: B. A set of minterm-like outputs from an input code

Question 6

For even parity, the parity bit for data bits D₀ through D₃ is:

A. D₀ + D₁ + D₂ + D₃

B. D₀D₁D₂D₃

C. D₀ ⊕ D₁ ⊕ D₂ ⊕ D₃

D. (D₀ + D₁ + D₂ + D₃)'

Correct Answer: C. D₀ ⊕ D₁ ⊕ D₂ ⊕ D₃

Question 7

Which condition is characteristic of a static-1 hazard?

A. The output should remain 1 but briefly becomes 0

B. The output should remain 0 but briefly becomes 1

C. The output changes exactly once

D. All inputs remain permanently constant

Correct Answer: A. The output should remain 1 but briefly becomes 0

Question 8

The consensus term for AB + A'C is:

A. A + C

B. A'C'

C. BC

D. AB'C

Correct Answer: C. BC

Question 9

Which device commonly implements arbitrary k-input Boolean functions using stored configuration values?

A. A k-input FPGA lookup table

B. A transformer

C. A crystal oscillator

D. A voltage regulator

Correct Answer: A. A k-input FPGA lookup table

Question 10

Using four-bit two’s complement, 0111 − 0101 equals:

A. 0001

B. 0010

C. 1010

D. 1110

Correct Answer: B. 0010