4. Combinational Logic Design

Introduction and Context

Digital systems are built from two broad classes of logic networks. In a combinational circuit, the output at any instant is determined only by the present combination of inputs. In a sequential circuit, by contrast, the output also depends on stored information about previous inputs. This distinction is fundamental: combinational logic performs transformation, selection, comparison, coding, and arithmetic, whereas sequential logic provides memory and state.

Combinational logic design begins with a functional specification and proceeds through Boolean modelling, optimization, implementation, and verification. The designer may describe a circuit using a truth table, Boolean equations, logic gates, a hardware description language, or a block-level architecture. At postgraduate level, it is important to recognize that a logically correct circuit is not automatically a satisfactory engineering solution. Propagation delay, fan-in, power dissipation, hazards, loading, testability, scalability, and implementation technology all influence the final design.

This chapter develops the principal combinational building blocks used in processors, controllers, communication systems, embedded platforms, and programmable logic devices. Arithmetic circuits, comparators, encoders, decoders, multiplexers, demultiplexers, parity networks, code converters, and programmable structures are treated not as isolated components but as members of a coherent design methodology.

Learning Objectives

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

1. Distinguish combinational circuits from sequential circuits and identify the assumptions underlying combinational operation.

2. Derive, simplify, and implement Boolean descriptions of practical combinational functions.

3. Design half and full adders, subtractors, ripple-carry and look-ahead adders, and arithmetic comparison circuits.

4. Explain the operation and applications of encoders, priority encoders, decoders, multiplexers, and demultiplexers.

5. Design parity generators and checkers, code converters, and magnitude comparators.

6. Evaluate propagation delay, hazards, fan-in, loading, power, and scalability in alternative implementations.

7. Use programmable logic structures and hardware description concepts to implement combinational functions.

8. Select an appropriate architecture for a specified application and verify its functional and timing behaviour.

From Specification to Hardware

A combinational design normally follows a sequence of related activities. First, the required relationship between inputs and outputs is stated precisely. The inputs and outputs are assigned binary variables, and a truth table or functional description is prepared. Unused or impossible input combinations may be identified at this stage.

Next, the designer derives Boolean expressions or an equivalent canonical representation. Simplification can be performed algebraically, with Karnaugh maps, by Quine–McCluskey methods, or with computer-aided synthesis tools. The simplified function is then mapped to gates, multiplexers, decoders, standard-cell logic, or programmable hardware. Finally, the implementation is checked for logical correctness and practical constraints such as delay, hazards, fan-out, and power.

A combinational block is often represented by

\[

\mathbf{y}=F(\mathbf{x}),

\]

where \(\mathbf{x}\) is the vector of present inputs and \(\mathbf{y}\) is the vector of outputs. No feedback path or storage element is intended in the ideal model. Real gates, however, have nonzero propagation delay. During an input transition, internal signals may change at different times, causing temporary output pulses. Thus, the mathematical model describes stable operation, while physical design must also consider transitions.

Essential terminology

A minterm is a product term containing every variable once, either complemented or uncomplemented, and corresponds to one truth-table row for which the function is one. A maxterm is a sum term containing every variable once and corresponds to a row for which the function is zero. Canonical sum of products and canonical product of sums provide systematic representations of Boolean functions.

Fan-in is the number of inputs accepted by a gate; fan-out is the number of gate inputs that one output can drive reliably. Propagation delay is the time between a change at an input and the corresponding stable change at the output. Hazard denotes an unwanted transient caused by unequal path delays. A don't-care condition is an input combination whose output is irrelevant or impossible in the application and may be assigned either value to simplify the circuit.

Arithmetic Building Blocks

Half adder and full adder

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

\[

S=A\oplus B,

\qquad C=AB.

\]

The half adder is useful as a conceptual building block, but it cannot accept a carry from a less significant position.

The full adder adds three one-bit quantities: A, B, and carry-in \(C_{in}\). Its outputs are

\[

S=A\oplus B\oplus C_{in},

\]

\[

C_{out}=AB+C_{in}(A\oplus B).

\]

An equivalent carry expression is

\[

C_{out}=AB+AC_{in}+BC_{in}.

\]

A full adder can be constructed from two half adders and an OR gate. First, A and B produce an intermediate sum and carry; the intermediate sum is then added to \(C_{in}\), and the two carry terms are ORed.

The full adder also illustrates the useful notions of propagate and generate. Define

\[

P=A\oplus B, \qquad G=AB.

\]

Then

\[

S=P\oplus C_{in}, \qquad C_{out}=G+PC_{in}.

\]

A pair of input bits generates a carry independently when G is one and propagates an incoming carry when P is one.

Parallel binary adders

An n-bit ripple-carry adder connects n full adders in cascade. The carry output of one stage becomes the carry input of the next. Its principal advantage is structural simplicity. Its weakness is delay: the most significant sum may have to wait for a carry to ripple through every stage. The worst-case delay grows approximately linearly with word length.

Carry look-ahead logic reduces this delay by expanding the carry equations. For bit position i,

\[

C_{i+1}=G_i+P_iC_i.

\]

For a four-bit group,

\[

C_1=G_0+P_0C_0,

\]

\[

C_2=G_1+P_1G_0+P_1P_0C_0,

\]

and analogous expansion gives C3 and C4. The look-ahead network uses more gates and wiring than a ripple adder but computes carries in parallel. Modern arithmetic units often use prefix structures, such as generate-propagate trees, to obtain favourable delay and area trade-offs for large word sizes.

Other architectures include carry-select adders, which calculate results for both possible carry inputs and select one after the actual carry is known, and carry-save adders, which postpone carry propagation and are particularly useful in multioperand addition and multiplication.

Subtraction and the two's-complement method

A half subtractor produces difference D and borrow B from A minus B:

\[

D=A\oplus B,

\qquad B_{out}=\overline{A}B.

\]

A full subtractor also accepts a borrow-in. Its difference is

\[

D=A\oplus B\oplus B_{in},

\]

and its borrow output may be written as

\[

B_{out}=\overline{A}B+\overline{A}B_{in}+BB_{in}.

\]

In practical binary arithmetic, subtraction is commonly performed with an adder using two's complement:

\[

A-B=A+\overline{B}+1.

\]

An n-bit adder-subtractor therefore complements each B bit conditionally using XOR gates and applies the control signal M as the least significant carry-in. For M = 0, the circuit performs addition; for M = 1, it adds the complement of B and one, thereby performing subtraction. This arrangement is efficient because one arithmetic datapath performs both operations.

For signed arithmetic, the final carry is not the criterion for overflow. In two's-complement addition, overflow occurs when two operands of the same sign produce a result of the opposite sign. It can be detected by

\[

V=C_n\oplus C_{n-1},

\]

where \(C_n\) is the carry out of the most significant bit and \(C_{n-1}\) is the carry into it. Equivalently, overflow occurs when the carry into and out of the sign bit differ.

Comparison and Selection Circuits

Magnitude comparators

A one-bit comparator produces three mutually exclusive outputs: A greater than B, A equal to B, and A less than B. For single bits,

\[

A>B=A\overline{B}, \quad A=B=AB+\overline{A}\overline{B}, \quad A<B=\overline{A}B.

\]

For multi-bit unsigned numbers, the most significant differing bit determines the result. A four-bit comparator can therefore compare the most significant pair first and allow lower-order bits to influence the result only when all higher-order pairs are equal. Cascaded comparator ICs commonly provide equality-expansion inputs and outputs so that larger words can be compared hierarchically.

A useful equality signal for n bits is

\[

E=\prod_{i=0}^{n-1}(A_i\odot B_i),

\]

where \(\odot\) denotes XNOR. Equality is often implemented efficiently using XOR or XNOR trees, followed by AND reduction.

Multiplexers

A multiplexer (MUX) selects one of several data inputs and connects it to a single output according to select lines. A 2-to-1 MUX has data inputs D0 and D1, select S, and output

\[

Y=\overline{S}D_0+SD_1.

\]

A 2^n-to-1 MUX requires n select lines. Multiplexers are data selectors, but their functional importance is broader: any Boolean function can be implemented by connecting variables or constants to data inputs and using the remaining variables as select inputs. This is known as MUX-based function realization.

A MUX may be used for bus sharing, ALU input selection, conditional data paths, sensor-channel selection, and implementation of control functions. In a large digital system, its delay, select-line skew, and capacitive loading can become important. A hierarchical MUX tree may reduce fan-in but introduce additional levels of delay.

Demultiplexers and decoders

A demultiplexer routes one input to one of several outputs. A 1-to-4 demultiplexer with data input D and select lines S1, S0 has outputs such as

\[

Y_0=D\overline{S_1}\overline{S_0},\quad

Y_1=D\overline{S_1}S_0,

\]

with analogous expressions for Y2 and Y3. When D is fixed at one, the demultiplexer becomes a decoder.

An n-to-2^n decoder activates one output corresponding to the binary input code. An enable input is frequently included. Decoders are used in memory address selection, instruction decoding, display driving, chip-select generation, and minterm generation. A decoder followed by an OR network can implement a sum-of-minterms function. If active-low outputs are used, the polarity must be considered carefully; a circuit that is logically correct at the Boolean level may be incorrectly connected because of misunderstood signal conventions.

Encoders and Code Transformation

An encoder performs the inverse conceptual operation of a decoder: it converts one active input among several into a binary code. A simple 8-to-3 encoder assumes that exactly one input is active. If multiple inputs may be active, the result is ambiguous and a priority encoder is required. The priority encoder assigns precedence, commonly to the highest-order active input, and often provides a valid bit indicating that at least one input is asserted.

Priority encoders are used in interrupt controllers, arbitration systems, exception detection, and leading-zero or leading-one detection. Their design requires attention to priority direction, invalid input combinations, and the timing of the valid output. A cascaded priority encoder may handle many request lines, but its priority scheme must be specified explicitly to avoid unfair or unintended arbitration.

A code converter maps one representation to another. Examples include binary-to-Gray, Gray-to-binary, binary-coded decimal (BCD) to seven-segment, and BCD-to-excess-3 conversion. In binary-to-Gray conversion, the most significant Gray bit equals the most significant binary bit, while each lower Gray bit is the XOR of adjacent binary bits:

\[

G_{n-1}=B_{n-1}, \qquad G_i=B_{i+1}\oplus B_i.

\]

Gray code changes only one bit between adjacent code values, reducing ambiguity during transitions in rotary encoders and position sensors. However, Gray code is not generally used for arithmetic without conversion.

A seven-segment decoder illustrates the treatment of unused states. Four BCD input bits represent decimal digits 0 through 9, while six input combinations are invalid for ordinary decimal display. These may be treated as don't-care states if the system guarantees valid BCD, or assigned blanking/error patterns if fault indication is required. The choice is a system-level decision, not merely a minimization convenience.

Parity and Error Detection

Parity circuits provide a simple form of error detection. An even-parity generator chooses a parity bit so that the total number of ones is even. For data bits \(D_0\) through \(D_{n-1}\), the even parity bit is

\[

P_e=D_0\oplus D_1\oplus\cdots\oplus D_{n-1}.

\]

If the transmitted word includes this parity bit, the XOR of all received bits should be zero for even parity. An odd-parity system uses the complement of the even parity bit, and the checking condition is correspondingly inverted.

Parity detects any odd number of bit errors but fails to detect an even number of errors. It does not identify the erroneous bit or correct the data. XOR gates may be arranged as a linear chain, balanced tree, or dedicated reduction network. A balanced tree can reduce logic depth and improve timing for wide words. In high-speed links, parity may be supplemented or replaced by stronger codes such as cyclic redundancy checks or error-correcting codes.

Hazards, Timing, and Physical Realization

Boolean simplification can produce a function that is correct for stable inputs yet exhibits a glitch during transitions. A static-1 hazard occurs when an output that should remain at one briefly falls to zero; a static-0 hazard occurs when an output that should remain at zero briefly rises to one. Dynamic hazards involve multiple transitions before settling and are more likely in multilevel networks.

For example, if a sum-of-products function contains adjacent implicants that cover two stable input conditions but the transition between them is implemented through unequal paths, a temporary zero may occur. Adding a redundant consensus term can remove a static hazard without changing the steady-state Boolean function. Hazard analysis is particularly important for asynchronous control signals, clock enables, handshaking, and externally visible strobes. In fully synchronous systems, a glitch may be harmless if it settles before the sampling edge, but that assumption must be verified rather than presumed.

Designers should also distinguish inertial and transport delay models in simulation. An inertial model suppresses pulses shorter than the gate's effective response time, while a transport model propagates them. Hardware description language simulations should use suitable timing models and should be supplemented by synthesis and post-layout verification when timing is critical.

Programmable Combinational Structures

Fixed gate networks are not the only implementation option. A programmable read-only memory (PROM) can implement a truth table by using input variables as address lines and programming output words. A programmable logic array (PLA) contains a programmable AND plane followed by a programmable OR plane, making it suitable for sum-of-products functions. A programmable array logic (PAL) generally has a programmable AND plane and a fixed OR plane, offering lower flexibility but often simpler implementation.

Field-programmable gate arrays (FPGAs) implement combinational functions mainly through lookup tables (LUTs), whose stored configuration bits represent truth tables. A k-input LUT can implement any Boolean function of k variables. Larger functions are built from multiple LUTs, multiplexers, dedicated carry chains, and routing resources. FPGA synthesis tools perform Boolean optimization, technology mapping, placement, and routing, but the designer remains responsible for specifying complete combinational assignments and avoiding unintended storage.

In a hardware description language, a combinational process must assign every output for every possible execution path. An incomplete assignment can infer a latch, changing the design from combinational to sequential. Blocking assignments are commonly used in combinational procedural descriptions because they model immediate evaluation within the procedure, although coding standards and synthesis semantics must be followed consistently. Formal equivalence checking, assertion-based verification, and constrained-random simulation can strengthen confidence in large combinational blocks.

Applied Scenario: Selecting an Arithmetic Architecture

Background

Consider an illustrative design for a 32-bit embedded controller that must execute addition and subtraction in one clock cycle. The controller is intended for moderate power consumption, but its arithmetic result contributes directly to the next stage of a high-throughput data path.

Situation and analysis

A 32-bit ripple-carry adder requires little area and has a simple regular layout, but its worst-case carry delay may dominate the cycle time. A fully expanded carry look-ahead design offers lower delay but increases wiring, logic area, and switching activity. A carry-select or prefix architecture may provide an intermediate trade-off. Subtraction can be integrated by conditionally inverting the second operand and setting the initial carry-in.

The design team first defines the numerical interpretation: operands are two's-complement signed values, and both carry-out and signed overflow must be reported. It then develops a reference model and verifies addition, subtraction, boundary values, random patterns, and control transitions. Timing estimates are obtained for candidate structures rather than selecting an architecture solely from a gate-count comparison.

Approach and solution

A hierarchical carry architecture is selected. Four-bit groups compute local generate and propagate information; a higher-level look-ahead network determines group carries. XOR gates controlled by the operation signal conditionally complement operand B, while the same signal supplies the initial carry-in. The output status block reports zero, negative, carry, and overflow conditions.

The verification plan includes exhaustive testing of all combinations within a smaller reference width, directed tests for 0, maximum positive, minimum negative, and -1, and randomized 32-bit tests against a software model. Static timing analysis checks the arithmetic path, and gate-level simulation examines whether status signals remain valid under the intended clocking assumptions.

Outcome and learning points

The selected architecture meets the timing target with more area than a ripple design but less implementation complexity than a fully flat look-ahead network. The principal lesson is that arithmetic architecture is a multiobjective decision. Logical equivalence does not imply equal speed, area, power, routability, or verification effort. A sound design process therefore combines Boolean reasoning, architectural comparison, technology awareness, and systematic verification.

Practical Applications and Professional Considerations

Combinational circuits appear in nearly every digital subsystem. Adders and comparators support processors, digital filters, address generation, counters, and measurement instruments. MUXes and decoders form the switching fabric of datapaths and memory interfaces. Encoders support event arbitration and sensor interfaces. Parity networks protect register files, communication frames, and control words. Code converters connect incompatible representations across devices and subsystems.

In professional design, interface conventions are as important as equations. Active-high and active-low signals, signed and unsigned comparison, valid and enable semantics, illegal input handling, reset assumptions, and timing constraints must be documented. Safety-related systems may require detection of invalid codes rather than treating them as don't-cares. Security-sensitive circuits should also consider fault injection, information leakage through power or timing, and the possibility that glitches affect control decisions.

Common mistakes include confusing carry with signed overflow, ignoring invalid encoder inputs, leaving outputs unspecified in HDL, using a ripple structure when timing prohibits it, assuming parity corrects errors, and minimizing away terms needed for hazard suppression. Another frequent error is optimizing only for gate count. In modern integrated circuits, interconnect delay, routing congestion, switching activity, and library-specific cell characteristics may dominate the nominal logic cost.

Best practices

A robust combinational design practice includes the following principles:

• Specify input meaning, polarity, valid ranges, and illegal states before deriving equations.
• Use truth tables or executable reference models for nontrivial functions.
• Separate functional correctness from timing and hazard analysis.
• Choose arithmetic architecture according to word length, performance, area, power, and implementation technology.
• Use balanced trees for wide XOR, AND, or OR reductions when delay matters.
• Verify signed overflow independently from carry-out.
• In HDL, assign every combinational output on every path and review synthesis reports for unintended latches.
• Apply formal or assertion-based checks to mutually exclusive outputs, such as comparator results and one-hot decoder outputs.
• Treat don't-care states as an explicit system decision, especially where safety or fault detection is important.

Current Developments

Contemporary combinational design increasingly relies on automated synthesis, formal verification, and technology-aware optimization. Standard-cell tools can select among alternative implementations using timing, power, and area constraints. FPGA tools exploit dedicated carry chains and configurable LUTs rather than mapping every function to general-purpose gates. Approximate arithmetic is being investigated for applications such as machine learning and multimedia, where controlled numerical error may reduce energy or latency.

At the same time, exact combinational logic remains essential in safety-critical and security-relevant systems. Designs are increasingly checked for equivalence across optimization stages, resilience to voltage and temperature variation, and susceptibility to faults. The central engineering skill remains unchanged: express the required relation precisely, select an architecture suited to the constraints, and demonstrate both logical and physical correctness.

Chapter Summary

Combinational logic produces outputs from present inputs without intentional storage. Its design begins with specification and proceeds through truth tables, Boolean expressions, minimization, implementation, and verification. Half and full adders form the basis of binary arithmetic; ripple, look-ahead, carry-select, carry-save, and prefix structures offer different speed, area, and power trade-offs. Subtraction is efficiently integrated through two's complement, while signed overflow must be distinguished from carry-out.

Comparators determine equality and relative magnitude. Multiplexers select data and can realize arbitrary Boolean functions; demultiplexers and decoders route or activate selected outputs. Encoders, particularly priority encoders, convert active requests into codes. Parity circuits provide limited error detection, and code converters translate among binary, Gray, BCD, and display representations. Programmable structures such as PLAs, PALs, PROMs, and FPGA LUTs provide flexible implementations.

Practical design requires attention to propagation delay, fan-in, fan-out, hazards, invalid states, HDL completeness, power, routing, and verification. The appropriate circuit is selected not simply by minimum gate count but by the complete set of system constraints.

Key Terms

Combinational circuit: A logic network whose stable output depends only on present input values.

Minterm: A product term containing every input variable and representing one truth-table combination.

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

Half adder: A circuit that adds two one-bit operands and produces sum and carry outputs.

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

Ripple-carry adder: A cascaded adder in which carries pass successively from one bit position to the next.

Carry look-ahead: An arithmetic technique that computes carries using generate and propagate signals.

Two's complement: A binary representation and arithmetic method for signed integers using bit complementation and an added one.

Overflow: A signed arithmetic condition in which the result cannot be represented in the available word size.

Magnitude comparator: A circuit that determines whether one binary number is greater than, equal to, or less than another.

Multiplexer: A data selector that routes one of several inputs to an output.

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

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

Priority encoder: An encoder that selects the highest- or lowest-priority active input when several are asserted.

Parity: A bit or property used to indicate whether the number of ones in a word is even or odd.

Hazard: An unwanted transient caused by unequal propagation delays in different logic paths.

PLA: A programmable logic array with programmable AND and OR planes.

LUT: A lookup table that implements a Boolean function by storing its truth-table outputs.

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

Review Questions

Short Answer Questions

1. Why can a half adder not be used as the only stage in a multi-bit binary adder?

2. Define propagate and generate signals for a full adder.

3. What is the functional difference between a decoder and an encoder?

4. What type of error can even parity fail to detect?

5. Why can incomplete output assignment in an HDL combinational process infer a latch?

Long Answer Questions

1. Derive the equations of a full adder and explain its implementation using two half adders.

2. Compare ripple-carry and carry-look-ahead adders in terms of delay, area, wiring, and scalability.

3. Explain how an adder-subtractor performs both addition and subtraction using two's complement.

4. Describe the operation and applications of multiplexers, demultiplexers, decoders, and priority encoders.

5. Explain static hazards and discuss methods for detecting and eliminating them.

Analytical / Application Questions

1. Design a four-bit circuit that performs either A+B or A-B under control of a mode input. Specify the treatment of carry-in, carry-out, and signed overflow.

2. A system receives several simultaneous interrupt requests but must service the highest-priority request. Select and design an appropriate combinational structure, including a valid output and a method of cascading for more inputs.

3. A seven-segment display occasionally flashes during BCD transitions. Analyze possible causes involving hazards, invalid intermediate codes, and decoder timing, and propose a verification and mitigation strategy.

22. Multiple Choice Questions with Answers

Question 1

Which expression correctly represents the carry output of a full adder?

A. A XOR B XOR Cin

B. AB + ACin + BCin

C. A'B + BCin

D. AB + A'Cin

Correct Answer: B. AB + ACin + BCin

Question 2

In a two's-complement adder, signed overflow is detected when:

A. The final carry is always one

B. The carry into and out of the sign bit differ

C. The least significant sum bit is zero

D. Both operands have opposite signs

Correct Answer: B. The carry into and out of the sign bit differ

Question 3

A 2-to-1 multiplexer implements which function?

A. Y = SD0 + S'D1

B. Y = S'D0 + SD1

C. Y = D0D1 + S

D. Y = S'D0D1

Correct Answer: B. Y = S'D0 + SD1

Question 4

What is the principal purpose of a priority encoder?

A. To activate all outputs simultaneously

B. To select a defined input when multiple inputs are active

C. To convert Gray code directly into decimal

D. To store the previous input combination

Correct Answer: B. To select a defined input when multiple inputs are active

Question 5

For an even-parity generator, the parity bit for data bits D0 through D3 is:

A. D0 + D1 + D2 + D3

B. D0D1D2D3

C. D0 XOR D1 XOR D2 XOR D3

D. The complement of D0 only

Correct Answer: C. D0 XOR D1 XOR D2 XOR D3

Question 6

Which statement about a ripple-carry adder is correct?

A. Its carry delay is independent of word length

B. It uses no full adders

C. Its worst-case carry delay generally increases with word length

D. It cannot perform subtraction

Correct Answer: C. Its worst-case carry delay generally increases with word length

Question 7

When a demultiplexer has its data input fixed at logic 1, it functions as a:

A. Decoder

B. Comparator

C. Parity checker

D. Full subtractor

Correct Answer: A. Decoder

Question 8

Why is Gray code useful in position sensors?

A. It supports direct multiplication without arithmetic circuits

B. Adjacent code values differ in only one bit

C. It always uses fewer bits than binary

D. It detects all multiple-bit errors

Correct Answer: B. Adjacent code values differ in only one bit

Question 9

Which situation most directly indicates a static-1 hazard?

A. An output intended to remain one briefly falls to zero during an input transition

B. An output remains permanently at zero

C. A decoder has more outputs than inputs

D. A parity circuit detects an odd number of errors

Correct Answer: A. An output intended to remain one briefly falls to zero during an input transition

Question 10

In an FPGA, a LUT primarily implements a combinational function by:

A. Storing its truth-table output values

B. Counting clock edges

C. Generating analog voltage levels

D. Providing sequential feedback by definition

Correct Answer: A. Storing its truth-table output values