Combinational Circuit Analysis and Design

Introduction

A combinational circuit is a digital system whose outputs depend only on the present values of its inputs. Unlike a sequential circuit, it has no internal memory and normally does not require a clock. Examples include arithmetic units, code converters, data selectors, address decoders, parity generators, and comparison circuits.

The design of a combinational system is best treated as a specification-to-circuit process. The designer first identifies the required function, defines inputs and outputs, establishes the truth table or Boolean equations, simplifies the logic, selects an implementation technology, and verifies the result. This process is more reliable than directly attempting to draw gates from an informal description.

Learning Objectives

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

1. Distinguish combinational circuits from sequential circuits.
2. Apply a systematic process for analyzing and designing combinational systems.
3. Derive and simplify Boolean expressions from specifications and truth tables.
4. Explain and design adders, subtractors, comparators, encoders, decoders, multiplexers, demultiplexers, parity circuits, and code converters.
5. Evaluate propagation delay, invalid inputs, active-low signals, and implementation limitations.
6. Select an appropriate combinational building block for a practical digital system.

1. The Specification-to-Circuit Process

A disciplined design procedure consists of the following stages:

1. Interpret the specification. Determine what the circuit must do, including valid input combinations, timing requirements, and exceptional conditions.
2. Name the variables. Assign symbols to every input and output, and state whether a signal is active-high or active-low.
3. Construct a truth table. List all relevant input combinations and the required output for each combination.
4. Derive Boolean functions. Express each output as a sum of minterms, product of maxterms, or another suitable form.
5. Simplify the functions. Use Boolean algebra, Karnaugh maps, or a computer-aided logic minimizer.
6. Choose an implementation. Select gates, multiplexers, decoders, programmable logic, or integrated arithmetic blocks.
7. Analyze hazards and timing. Consider propagation delay, fan-in, fan-out, and possible glitches.
8. Verify the design. Test normal, boundary, unused, and invalid cases through simulation or hardware measurement.

For n binary inputs, a complete truth table has 2ⁿ possible input rows. This formula assumes that each input is independently either 0 or 1. If some combinations are impossible or irrelevant, they may be marked as don't-care conditions, but such conditions must be justified by the system specification.

A Boolean function written in canonical sum-of-products form is constructed from minterms. For example, if output F is 1 on rows 1 and 3 of a two-input table, with inputs A and B, then:

Here, the apostrophe denotes complementation, juxtaposition denotes AND, and + denotes OR. The expression simplifies to B. A simplified expression is preferable because it commonly requires fewer gates and has lower cost and delay.

Analysis versus design

Analysis begins with a circuit and determines its behavior. The procedure is to label intermediate signals, write gate equations, substitute them into the output equations, and test representative input combinations.

Design begins with a required behavior and produces a circuit. The designer moves in the opposite direction: specification → truth table → Boolean expression → simplified implementation → verification.

2. Arithmetic Circuits

2.1 Half adder

A half adder adds two one-bit operands, A and B. It produces a sum S and a carry C. The sum is 1 when exactly one input is 1, while the carry is 1 when both inputs are 1.

The equations are:

The symbol ⊕ denotes exclusive OR. Thus, a half adder can be implemented with one XOR gate and one AND gate. It cannot add an incoming carry from a lower-order position, so it is insufficient by itself for general multi-bit addition.

2.2 Full adder

A full adder adds three one-bit values: A, B, and an incoming carry Cᵢₙ. It produces a sum S and an outgoing carry Cₒᵤₜ.

The carry expression is 1 whenever at least two of the three inputs are 1. A full adder can be built from two half adders and an OR gate:

1. The first half adder adds A and B.
2. The second half adder adds the first sum to Cᵢₙ.
3. The two carry outputs are ORed.

2.3 Multi-bit addition

Several full adders may be cascaded to form a ripple-carry adder. The carry from each bit position becomes the input carry of the next position. For an n-bit addition, the numerical relationship is:

where A and B are n-bit unsigned operands, C₀ is the initial carry, S is the n-bit sum, and Cₙ is the final carry. The final carry indicates an unsigned overflow beyond n bits.

Ripple-carry addition is simple but slow because each stage may need to wait for the previous carry. If the worst-case carry delay of one stage is t_c and there are n stages, a simplified worst-case estimate is approximately:

This estimate assumes equal stages and a carry-dependent critical path. Faster architectures, such as carry-lookahead adders, compute carries using generate and propagate signals.

For bit position i, define:

Then:

Gᵢ indicates that the position generates a carry independently; Pᵢ indicates that an incoming carry will propagate through the position.

2.4 Subtractors

A half subtractor subtracts B from A and produces a difference D and borrow Bᵣ.

A full subtractor also accepts an incoming borrow Bᵢₙ:

In practical processors, subtraction is often performed using two's-complement addition. For n-bit operands:

The complement B' is formed with NOT gates, and the initial carry input is set to 1. This permits one adder circuit to perform both addition and subtraction. A control input M can select the operation by conditionally complementing B and setting the initial carry to M.

3. Magnitude Comparators

A comparator determines whether one binary number is greater than, equal to, or less than another. For one-bit values A and B, the outputs are:

For multi-bit unsigned numbers, comparison begins with the most significant bit. A difference at the first unequal position determines the result; lower-order bits are irrelevant. If A and B have n bits, equality can be expressed as:

The product symbol represents AND across all bit positions. A cascaded comparator must ensure that a lower-order comparison is considered only when all higher-order bits are equal.

Comparators are used in address checking, threshold detection, sorting hardware, control systems, and digital measurement instruments.

4. Decoders and Encoders

4.1 Decoders

An n-to-2ⁿ decoder activates one output corresponding to an n-bit input code. In a one-hot active-high decoder, exactly one output is 1 for each valid input combination.

For a 2-to-4 decoder with inputs A and B:

Many integrated decoders include an enable input. If enable E is active-high, all outputs may be forced inactive when E = 0. Designers must carefully check whether an actual device uses active-high or active-low outputs; a small circle or bar in a schematic commonly indicates inversion.

Decoders support memory address selection, instruction decoding, display driving, chip selection, and implementation of arbitrary Boolean functions. A function can be implemented by ORing the decoder outputs associated with its 1-minterms.

4.2 Encoders

An encoder performs the reverse conceptual operation: it converts one active input among several into a binary code. A 4-to-2 encoder has four inputs and two outputs. Under the one-hot assumption:

The basic equations are:

These equations assume that exactly one input is active. If multiple inputs may be active, the result is ambiguous. A priority encoder resolves this by assigning priority, usually to the highest-numbered or highest-order input. A valid output is often included to indicate whether any input is active.

5. Multiplexers and Demultiplexers

5.1 Multiplexer

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

When S = 0, D₀ is selected; when S = 1, D₁ is selected. A 4-to-1 MUX uses two select lines and has the general form:

A MUX can implement any Boolean function by connecting selected data inputs to 0, 1, or remaining variables. It is therefore both a data-routing component and a universal logic-implementation structure.

5.2 Demultiplexer

A demultiplexer (DEMUX) routes one data input to one of several outputs. For a 1-to-4 DEMUX with data input D and select inputs S₁ and S₀:

A DEMUX is useful for data distribution, channel selection, serial-to-parallel routing, and controlled activation of devices.

6. Parity Circuits

Parity provides a simple method for detecting an odd number of bit errors. An even-parity generator produces a parity bit P such that the total number of 1s, including P, is even. For data bits D₃ through D₀:

An odd-parity generator is the complement:

At the receiving end, all data bits and the parity bit are XORed. For even parity, a result of 0 indicates that the received word has even parity; a result of 1 indicates a parity error under the assumption of no more than one bit error. Parity cannot identify the erroneous bit and cannot reliably detect an even number of bit errors.

7. Code Converters

A code converter maps one binary representation to another. The design procedure is:

1. List the source-code combinations.
2. Assign the corresponding destination code.
3. Mark unused source combinations as invalid or don't-care only when the system can safely ignore them.
4. Derive and simplify one Boolean function for each destination bit.
5. Verify all valid combinations and define behavior for invalid combinations.

Binary-to-Gray conversion

For an n-bit binary word Bₙ₋₁…B₀, the corresponding Gray code Gₙ₋₁…G₀ is:

Gray code changes only one bit between adjacent numerical values, reducing transition ambiguity in rotary encoders and position sensors. The reverse conversion is cumulative XOR:

BCD-to-seven-segment conversion

A BCD-to-seven-segment converter accepts a 4-bit decimal code and drives seven outputs corresponding to segments a through g. The ten valid BCD combinations represent decimal digits 0 through 9; six combinations are invalid. Whether invalid combinations are blanked, displayed as a pattern, or treated as don't-cares must be explicitly specified. This example illustrates why a truth table is essential: each segment has its own Boolean function.

8. Hazards, Timing, and Real Hardware

Boolean equivalence does not guarantee identical physical behavior. Gates have propagation delays, so signals that theoretically change simultaneously may arrive at different times. A temporary unwanted pulse is called a hazard.

A static-1 hazard occurs when an output expected to remain 1 briefly falls to 0. A static-0 hazard occurs when an output expected to remain 0 briefly rises to 1. Consensus terms can sometimes be added to a two-level expression to remove a hazard, although the added term may increase hardware cost.

Important practical considerations include:

• Propagation delay: time between an input transition and the corresponding stable output.
• Fan-in: number of inputs connected to one gate.
• Fan-out: number of gate inputs driven by one output.
• Loading: electrical demand placed on a signal.
• Undefined inputs: floating CMOS inputs may produce unpredictable behavior and should not be left unconnected.
• Active-low conventions: signals such as RESET̅ or ENABLE̅ require careful interpretation.
• Overflow: arithmetic overflow must be distinguished from a carry-out. For signed two's-complement addition, overflow occurs when two operands with the same sign produce a result with the opposite sign.

Simulation should include transition timing, not merely steady-state truth-table checks, when the circuit drives clocks, asynchronous controls, memory enables, or safety-related outputs.

9. Detailed Application: Digital Access-Control Panel

Background

Consider an illustrative access-control panel for a small laboratory. Four switches represent a 4-bit access code. The system must compare the entered code with a stored code, display whether the entry is equal, and route a confirmation signal to one of two doors.

Problem

The design requires:

• A four-bit entered code E₃E₂E₁E₀.
• A four-bit stored code K₃K₂K₁K₀.
• An equality indicator Q.
• A valid-entry signal V generated when the code matches.
• A door-selection input S.
• Outputs D₀ and D₁, with the confirmation signal routed to the selected door.

The security requirement is that neither door output may be active unless the code is correct.

Analysis and solution

First compare each entered bit with the corresponding stored bit using XNOR gates:

The equality output is the AND of all four comparisons:

The valid-entry signal is Q. A 1-to-2 DEMUX then receives Q as its data input and S as its select input:

If the code is incorrect, Q = 0 and both door outputs are 0 regardless of S. If the code is correct, exactly one door output is active.

Verification

Suppose the stored code is 1010 and the entered code is 1010. Every XNOR output is 1, so Q = 1. With S = 0, D₀ = 1 and D₁ = 0. If the entered code changes to 1000, the third comparison differs, making Q = 0; both door outputs become 0.

Outcome and learning points

The design combines a comparator and a demultiplexer because the requirements naturally divide into two functions: decision and routing. The case also demonstrates a safety principle: authorization should be generated before routing, and the routing stage should receive only the authorized signal. In a real installation, the combinational logic would require additional measures such as debouncing, secure storage, fault detection, and a sequential lockout mechanism.

10. Design Best Practices and Limitations

Good combinational design begins with unambiguous specifications. Designers should define invalid states, signal polarity, numeric representation, timing assumptions, and reset behavior before simplifying equations. Modular blocks such as adders, MUXs, and decoders improve readability and verification.

Hardware description languages and synthesis tools can translate Boolean or behavioral descriptions into gates. However, automated synthesis does not remove the need for engineering judgment. The designer remains responsible for checking signed versus unsigned arithmetic, inferred latches, unintended priority, timing constraints, and simulation-to-hardware differences.

Combinational circuits also have limitations. They cannot remember previous events, filter switch bounce by themselves, or guarantee glitch-free outputs without suitable timing design. A circuit that controls physical actuators may therefore need sequential synchronization, registered outputs, watchdogs, and fail-safe logic.

Chapter Summary

Combinational circuits produce outputs from present inputs and have no intended memory. Their design follows a specification-to-circuit process involving variable definition, truth-table construction, Boolean derivation, simplification, implementation, and verification. Half and full adders support binary arithmetic; subtractors and two's-complement methods support subtraction. Comparators establish equality and ordering. Decoders activate one output from a coded input, while encoders perform the reverse mapping. Multiplexers select data, and demultiplexers distribute it. XOR-based parity circuits detect many single-bit errors, while code converters translate between representations such as binary and Gray code. Practical designs must also account for propagation delay, hazards, active-low signals, invalid inputs, overflow, fan-out, and verification. The access-control example illustrates how several standard blocks can be composed into a reliable application-oriented system.

Key Terms

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

Truth table: A table listing outputs for specified input combinations.

Minterm: A product term that represents one specific input combination.

Half adder: A circuit that adds two bits and produces sum and carry.

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

Ripple-carry adder: A cascaded adder in which carries propagate between stages.

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

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

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 according to priority.

Multiplexer: A circuit that selects one of several inputs.

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

Parity: A property indicating whether the number of 1 bits is even or odd.

Code converter: A circuit that maps one digital representation to another.

Hazard: An unwanted transient caused by unequal propagation delays.

Fan-out: The number of inputs that one output can drive reliably.

Propagation delay: The time required for a circuit output to respond to an input change.

Don't-care condition: An input combination whose output may be chosen for convenient simplification, subject to system safety.

Review Questions

Short Answer Questions

1. How does a combinational circuit differ from a sequential circuit?
2. Why cannot a half adder directly accept an incoming carry?
3. What is the purpose of an enable input on a decoder?
4. Why is a priority encoder needed when multiple inputs may be active?
5. What type of error can parity commonly detect, and what important error limitation does it have?

Long Answer Questions

1. Explain the complete specification-to-circuit design process and illustrate each stage with a two-input Boolean function.
2. Derive the sum and carry equations of a full adder and explain one method of implementing it with half adders.
3. Compare ripple-carry and carry-lookahead adders in terms of structure, delay, and hardware complexity.
4. Explain how a multiplexer can implement an arbitrary Boolean function.
5. Describe the design of a binary-to-Gray code converter and explain why Gray code is useful in position sensing.

Analytical / Application Questions

1. Design a 2-bit equality comparator. Give the Boolean equation for equality and explain how the circuit behaves for equal and unequal inputs.
2. A four-bit system uses even parity. Determine the parity bit for data 1011 and explain the receiver's parity check result when the received word is 10111.
3. Design a circuit that adds two 4-bit unsigned numbers. Identify the required building blocks, explain carry propagation, and state how an unsigned overflow is indicated.

Multiple Choice Questions with Answers

Question 1

Which equation correctly describes the carry output of a half adder?

A. A ⊕ B

B. AB

C. A + B

D. A'B

Correct Answer: B. AB

Question 2

In a full adder, the sum output is:

A. A + B + Cᵢₙ

B. AB + Cᵢₙ

C. A ⊕ B ⊕ Cᵢₙ

D. A'B + BCᵢₙ

Correct Answer: C. A ⊕ B ⊕ Cᵢₙ

Question 3

What is the principal limitation of a ripple-carry adder?

A. It cannot add binary numbers

B. It requires decimal inputs

C. Carry propagation can produce a relatively long delay

D. It produces no carry output

Correct Answer: C. Carry propagation can produce a relatively long delay

Question 4

A 2-to-4 decoder normally has how many output lines?

A. 2

B. 4

C. 6

D. 8

Correct Answer: B. 4

Question 5

For a 2-to-1 multiplexer, which input is selected when S = 1?

A. D₀

B. D₁

C. Both inputs simultaneously

D. Neither input

Correct Answer: B. D₁

Question 6

What assumption is made by a basic 4-to-2 encoder?

A. All inputs must be active

B. Exactly one input is active

C. No input can ever be active

D. The inputs are analog voltages

Correct Answer: B. Exactly one input is active

Question 7

For even parity, the parity bit for data 1011 is:

A. 0

B. 1

C. 10

D. Cannot be determined

Correct Answer: B. 1

Question 8

Which gate operation is naturally used to generate parity?

A. XOR

B. AND only

C. NOR only

D. XNOR only

Correct Answer: A. XOR

Question 9

In a binary-to-Gray converter, the most significant Gray bit is:

A. Always 0

B. The complement of the most significant binary bit

C. Equal to the most significant binary bit

D. The XOR of all binary bits

Correct Answer: C. Equal to the most significant binary bit

Question 10

Which condition is most directly associated with a static hazard?

A. A permanent open circuit

B. An unwanted temporary output transition caused by unequal delays

C. A valid truth-table output

D. An increase in the number of input variables

Correct Answer: B. An unwanted temporary output transition caused by unequal delays