Combinational Logic Design

Introduction

A combinational logic circuit is a digital circuit whose outputs depend only on the present values of its inputs. Unlike a sequential circuit, it has no internal memory or feedback-based state. This property makes combinational circuits fundamental building blocks in processors, memory interfaces, communication equipment, control systems, and network hardware.

Typical combinational circuits include arithmetic units, comparators, encoders, decoders, multiplexers, demultiplexers, parity generators, parity checkers, and code converters. Their design normally follows a structured process: specify the function, identify inputs and outputs, construct a truth table, derive Boolean expressions, simplify the expressions, implement the circuit, and verify its operation through simulation or hardware testing.

Learning Objectives

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

• distinguish combinational circuits from sequential circuits;
• design and analyse half and full adders;
• design binary subtractors and explain borrow propagation;
• construct magnitude comparators;
• explain and implement encoders, priority encoders, decoders, multiplexers, and demultiplexers;
• design parity-generation and parity-checking circuits;
• convert between common digital codes;
• simulate and troubleshoot combinational circuits systematically;
• evaluate propagation delay, hazards, fan-in, and practical implementation limitations.

1. Foundations of Combinational Design

For a combinational circuit with input vector X and output vector Y, each output is a Boolean function of the current inputs:

Here, x₁ through xₙ are binary input variables, yᵢ is an output, and fᵢ is a Boolean function. The equation assumes ideal binary signals and no dependence on previous input values.

A standard design procedure is:

1. State the problem precisely.
2. Assign symbols to all inputs and outputs.
3. Define active-high or active-low signal conventions.
4. Prepare the truth table.
5. Derive Boolean expressions using minterms, maxterms, or direct reasoning.
6. Simplify using Boolean algebra or Karnaugh maps.
7. Select gates or integrated modules.
8. Check timing, loading, unused inputs, and logic-level compatibility.
9. Simulate all relevant input combinations.
10. Test the physical circuit and document the result.

For n independent binary inputs, the complete truth table contains:

where N is the number of possible input combinations. This applies when every input can independently assume logic 0 or logic 1.

Boolean Notation

The common notation used in this chapter is:

• AND: A·B or AB
• OR: A+B
• NOT: A̅
• XOR: A⊕B
• XNOR: A⊙B

De Morgan’s laws are particularly useful when converting between gate forms:

These identities assume Boolean variables and ideal complement operation.

2. Adders

2.1 Half Adder

A half adder adds two one-bit binary numbers, A and B. It produces a sum S and a carry C.

The equations are:

Thus, a half adder requires one XOR gate and one AND gate. It cannot accept a carry input from a lower-order bit, so it is normally used only in the least significant position or as a component of a full adder.

2.2 Full Adder

A full adder adds three one-bit inputs: A, B, and carry-in Cᵢₙ. Its outputs are sum S and carry-out Cₒᵤₜ.

The sum is 1 when an odd number of inputs are 1:

The carry-out is 1 when at least two inputs are 1:

An alternative useful form is:

A full adder can be constructed from two half adders and an OR gate. The first half adder adds A and B; the second adds its sum to Cᵢₙ; the OR gate combines the two carry outputs.

2.3 Parallel Binary Adder

An n-bit ripple-carry adder connects n full adders in cascade. The carry output of each stage becomes the carry input of the next stage. For two four-bit numbers A₃A₂A₁A₀ and B₃B₂B₁B₀, the least significant stage receives the initial carry C₀, and the final stage produces C₄.

The main limitation is propagation delay. A carry generated in the least significant stage may need to travel through every higher stage before the final sum is valid. If each stage contributes an average carry delay t_c, the worst-case carry-chain delay is approximately:

This is an engineering approximation for a ripple structure; actual delay depends on the technology, loading, logic implementation, and whether sum-generation delay is included.

Faster adders, such as carry-lookahead adders, compute carry signals using generate and propagate terms. Define:

Then:

A carry-lookahead design reduces delay at the cost of additional gates and wiring.

Worked Example: Four-Bit Addition

Add 0101₂ and 0011₂.

Column processing gives: 1 + 1 produces sum 0 and carry 1; the next column produces 0 with carry 1; the next produces 0 with carry 1; the most significant column produces 1. Therefore, the result is 1000₂, equal to 8₁₀.

3. Subtractors

3.1 Half Subtractor

A half subtractor subtracts B from A and produces difference D and borrow Bₒᵤₜ.

The equations are:

3.2 Full Subtractor

A full subtractor accepts minuend A, subtrahend B, and borrow-in Bᵢₙ. It produces difference D and borrow-out Bₒᵤₜ.

A practical alternative for binary subtraction is two’s-complement addition. To calculate A − B using an n-bit adder, complement every bit of B, add 1, and add the result to A:

This identity applies to fixed-width two’s-complement arithmetic. Overflow must be considered when signed numbers are represented with a limited number of bits.

4. Magnitude Comparators

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

For multi-bit unsigned numbers, comparison begins at the most significant bit. The first unequal bit determines the result. For two-bit numbers A₁A₀ and B₁B₀:

The expression for A < B is obtained symmetrically. Comparator outputs are widely used in address decoding, alarm systems, sorting hardware, and processor condition-code logic.

5. Decoders and Encoders

5.1 Decoder

An n-to-2ⁿ decoder activates one output corresponding to the binary input code. For a 2-to-4 active-high decoder with inputs A and B:

The output equations are:

Many practical decoders include an enable input. The enable signal may be active-high or active-low, so the data sheet must be consulted rather than assuming a polarity.

Decoders are used for memory-chip selection, instruction decoding, display selection, and demultiplexing. An incomplete decoder truth table can also implement a sum-of-minterms function by connecting selected outputs to an OR gate.

5.2 Encoder

An encoder performs the reverse operation: it converts one active input among 2ⁿ input lines into an n-bit binary code. A 4-to-2 encoder assumes that only one input is active at a time. With active inputs D₀ through D₃, the outputs may be:

A valid or enable output is often added to distinguish “no input active” from a legitimate code.

5.3 Priority Encoder

A standard encoder fails if several inputs are active simultaneously. A priority encoder resolves this by assigning priority, usually to the highest-numbered input. If D₃ has highest priority, D₃ determines the code whenever it is 1, regardless of lower inputs. A valid output indicates that at least one input is active.

Priority encoders are useful in interrupt controllers, bus arbitration, and resource allocation. Their design must specify priority direction, input polarity, and the output behavior when no request is present.

6. Multiplexers and Demultiplexers

6.1 Multiplexer

A multiplexer (MUX) selects one of several data inputs and routes it to a single output. A 4-to-1 MUX has data inputs I₀–I₃, select inputs S₁ and S₀, and output Y:

The select inputs determine which data input appears at the output. A multiplexer can also implement arbitrary Boolean functions. Select variables are connected to the select lines, and the data inputs are connected to 0, 1, or remaining variables according to the function’s truth table.

6.2 Demultiplexer

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

MUX and DEMUX circuits are used in data routing, communication channels, test systems, and processor datapaths. In real systems, enable signals and active-low outputs are common; these must be explicitly documented.

7. Parity Circuits

Parity provides a simple error-detection mechanism. An even-parity generator produces a parity bit that makes the total number of 1s even. For data bits A, B, and C:

If the data contains an odd number of 1s, the XOR result is 1 and the parity bit changes the total to even. For odd parity:

A parity checker XORs all received data bits and the received parity bit. For even parity, a zero result indicates the expected parity condition; a one indicates an error under the assumption of a single-bit error and reliable signal sampling.

Parity detects any odd number of bit errors but cannot detect an even number of bit errors. It does not identify the erroneous bit and cannot correct errors. Consequently, stronger methods such as cyclic redundancy checks or error-correcting codes are used where reliability requirements are higher.

8. Code Converters

A code converter translates one binary representation into another. The design method is to list the source code, determine the target code for each valid input, derive one Boolean expression per output bit, and simplify the expressions.

Binary-to-Gray Conversion

For an n-bit binary number Bₙ₋₁...B₀, the most significant Gray bit equals the most significant binary bit:

Each remaining Gray bit is the XOR of adjacent binary bits:

for i from 0 to n−2. For four bits:

Gray code changes only one bit between adjacent numerical values, reducing ambiguity in rotary encoders and position sensors. The converter must define behavior for all input combinations, including unused or invalid code words.

BCD-to-Excess-3 Conversion

Binary-coded decimal (BCD) represents each decimal digit with four bits from 0000 to 1001. Excess-3 represents a decimal digit by adding 0011 to its BCD representation. For example:

Thus decimal 5 is represented as 1000 in Excess-3. Inputs 1010 through 1111 are invalid BCD combinations and may be treated as don’t-care conditions only when the hardware environment guarantees that they will not occur.

9. Simulation and Troubleshooting

Simulation should test both normal operation and boundary conditions. A useful test plan includes all combinations for small circuits, representative combinations for larger circuits, carry and borrow transitions, enable changes, invalid codes, and simultaneous input activation.

Common faults include:

• reversed or mislabeled inputs;
• omitted inversion bubbles or incorrect active-low assumptions;
• floating inputs;
• incorrect carry or borrow connections;
• encoder inputs active simultaneously when priority was not designed;
• decoder enable held inactive;
• unequal propagation delays causing transient glitches;
• output loading or fan-out exceeding the device specification;
• connecting outputs together without a suitable tri-state or open-collector arrangement.

A disciplined troubleshooting sequence is to verify power and ground, confirm input levels, test each block independently, probe intermediate signals, compare observed results with the truth table, and then inspect timing. A circuit that eventually reaches the correct steady-state value may still be unsuitable if a downstream device samples during a transient interval.

Hazards and Propagation Delay

A static hazard is a brief unwanted transition caused by unequal path delays. For example, two logically adjacent product terms may not overlap during a change, producing a momentary zero in a circuit expected to remain at one. Hazards can be reduced by adding consensus terms, synchronizing sampling, or registering outputs. They cannot be evaluated from Boolean equations alone; physical gate delays and input transition timing matter.

10. Applied Case: Network Device Address-Selection Unit

The following is an illustrative case. A small network interface must select one of four internal processing channels according to a two-bit channel code, indicate whether the requested channel is available, and report a fault if an odd number of status bits has changed during transmission.

Background

The interface receives channel code S₁S₀, four availability signals A₀–A₃, and three status bits T₂T₁T₀. The design must be compact and easy to test.

Problem Analysis

A 2-to-4 decoder can convert S₁S₀ into one-hot channel-select signals. A 4-to-1 multiplexer can route the selected availability signal to a single AVAILABLE output. An XOR tree can generate a parity indication for the three status bits.

Solution

The decoder produces D₀ through D₃. The availability output is:

The same result could be obtained with a multiplexer whose select inputs are S₁ and S₀ and whose data inputs are A₀ through A₃. The parity-error signal is generated by comparing received parity with the XOR of the status bits:

For even parity, a result of 1 indicates a parity violation.

Verification and Outcome

The testbench should apply all four channel codes with each availability pattern, verify that only the selected channel affects AVAILABLE, and inject one-bit and two-bit changes into the status field. One-bit errors should be detected; two-bit errors may not be detected, illustrating the limitation of parity. The modular design also permits the decoder, multiplexer, and parity block to be tested separately.

Learning Points

The case demonstrates structured decomposition, the equivalence of alternative implementations, the importance of signal polarity, and the difference between functional correctness and error-detection capability.

11. Practical Design Considerations

Active-High and Active-Low Logic

A signal ending in “̅”, or marked with a bar or bubble, is active-low. For example, an active-low enable is asserted when its value is 0. Documentation should state the convention explicitly because many decoder, encoder, and bus-control devices use active-low signals.

Fan-In, Fan-Out, and Loading

Fan-in is the number of inputs accepted by a gate. Fan-out is the number of standard inputs that one output can drive while maintaining valid logic levels. Excessive fan-out increases delay and may violate voltage or current specifications. Buffering, hierarchical logic, or a different device family may be required.

Don’t-Care Conditions

A don’t-care input combination is one whose output is irrelevant or guaranteed not to occur. It may be assigned either 0 or 1 during minimization to obtain a simpler circuit. This is safe only when the system specification genuinely excludes that input condition.

Technology and Modern Implementation

Combinational logic may be built from discrete gates, standard logic ICs, programmable logic devices, field-programmable gate arrays, or custom integrated circuits. Hardware-description languages such as VHDL and Verilog allow designers to specify Boolean behavior and simulate it before synthesis. Synthesis tools may optimize expressions, but designers remain responsible for reset assumptions, timing constraints, unknown states, and hardware resource use.

AI-assisted design tools can suggest truth tables, Boolean simplifications, or test vectors, but their outputs require verification against the specification and device data sheets. An apparently simplified expression may mishandle active-low signals, invalid codes, or timing hazards.

Challenges and Limitations

Combinational design becomes more difficult as the number of inputs increases because truth-table size grows exponentially. Algebraic minimization may produce circuits that are logically correct but physically slow or hazard-prone. Real circuits also experience propagation delay, power consumption, noise, voltage thresholds, temperature variation, and manufacturing tolerances. Parity and simple comparison circuits provide useful functions but do not replace complete communication protocols or robust error-correcting methods.

Chapter Summary

Combinational circuits produce outputs from present inputs without storing a previous state. Their design begins with a clear specification and proceeds through input/output assignment, truth-table construction, Boolean derivation, simplification, implementation, simulation, and physical verification. Half and full adders perform binary addition; subtractors produce differences and borrows; comparators determine numerical relationships. Decoders activate one output from a binary code, while encoders perform the reverse operation and priority encoders resolve multiple active requests. Multiplexers select data paths, demultiplexers distribute data, and XOR-based parity circuits detect many transmission errors. Code converters translate representations such as binary, Gray, BCD, and Excess-3. Professional designs also account for active-low conventions, invalid states, delay, hazards, loading, fan-out, and verification limitations.

Key Terms

Combinational circuit: A circuit whose outputs depend only on present input values.

Truth table: A complete listing of input combinations and corresponding outputs.

Half adder: A circuit that adds two one-bit values 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 carry propagates from one stage to the next.

Half subtractor: A circuit that subtracts one bit from another and produces difference and borrow.

Comparator: A circuit that determines whether one binary value is greater than, equal to, or less than another.

Decoder: A circuit that activates one output corresponding to a binary input code.

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

Priority encoder: An encoder that gives precedence to one input when several are active.

Multiplexer: A circuit that selects one of several inputs for a single output.

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

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

Code converter: A circuit that translates one digital representation into another.

Don’t-care condition: An input combination whose output may be assigned for simplification.

Propagation delay: The time between an input transition and the corresponding valid output transition.

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

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

Active-low: A signal convention in which logic 0 represents assertion.

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 priority encoder require a priority rule?
4. What is the purpose of an enable input on a decoder?
5. What limitation does parity detection have when two bits change?

Long Answer Questions

1. Explain the design and operation of a full adder, including its truth-table interpretation and implementation using two half adders.
2. Describe the operation of a ripple-carry adder and explain why carry-lookahead logic can improve speed.
3. Compare encoders, priority encoders, decoders, multiplexers, and demultiplexers.
4. Explain a systematic procedure for designing a code converter and apply it to binary-to-Gray conversion.
5. Discuss propagation delay, hazards, fan-out, active-low signals, and don’t-care conditions in practical circuit design.

Analytical / Application Questions

1. Design a four-input even-parity generator and explain how its output changes for zero, one, two, and three input 1s.
2. A four-bit ripple-carry adder uses four stages, each with an approximate carry delay of 12 ns. Estimate the worst-case carry-chain delay and explain why the estimate is only approximate.
3. Design a channel-selection circuit for eight sources using a decoder and a multiplexer. Specify the number of select lines, the number of decoder outputs, and the verification tests required.

Multiple Choice Questions with Answers

Question 1

Which equation represents the sum output of a full adder?

A. S = A·B

B. S = A⊕B⊕Cᵢₙ

C. S = A+B+Cᵢₙ

D. S = A̅·B

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

Question 2

What is the main limitation of a half adder?

A. It cannot produce a sum

B. It cannot accept a carry input

C. It requires a clock

D. It can add only decimal digits

Correct Answer: B. It cannot accept a carry input

Question 3

A 3-to-8 decoder has how many output lines?

A. 3

B. 6

C. 8

D. 9

Correct Answer: C. 8

Question 4

What does a multiplexer do?

A. Routes one selected input to an output

B. Stores a binary word

C. Converts analogue signals into digital signals

D. Counts clock pulses

Correct Answer: A. Routes one selected input to an output

Question 5

For even parity, the XOR of all received data and parity bits is 1. What does this normally indicate?

A. Correct even parity

B. A parity violation

C. A guaranteed two-bit correction

D. A decoder enable condition

Correct Answer: B. A parity violation

Question 6

Which circuit resolves the problem of multiple simultaneously active encoder inputs?

A. Half subtractor

B. Priority encoder

C. Demultiplexer

D. Parity checker

Correct Answer: B. Priority encoder

Question 7

For a one-bit comparator, which expression represents A greater than B?

A. A·B̅

B. A̅·B

C. A⊙B

D. A+B

Correct Answer: A. A·B̅

Question 8

What is the four-bit Gray code corresponding to binary 1011?

A. 1110

B. 1101

C. 1010

D. 1001

Correct Answer: A. 1110

Question 9

In a ripple-carry adder, what primarily causes delay to increase as the number of bits increases?

A. The need for analogue conversion

B. Carry propagation through successive stages

C. The absence of XOR gates

D. The use of parity bits

Correct Answer: B. Carry propagation through successive stages

Question 10

If a circuit has four independent binary inputs, how many rows are required for a complete truth table?

A. 4

B. 8

C. 12

D. 16

Correct Answer: D. 16