Digital Electronics and Combinational Logic

Introduction

Digital electronics represents information using discrete signal levels, most commonly binary 0 and 1. Unlike analog circuits, which process continuously varying voltages, digital circuits interpret voltage ranges as logic states. This abstraction enables reliable storage, processing, transmission, and computation. Modern computers, controllers, communication equipment, industrial systems, and consumer products are built largely from digital circuits.

This chapter develops the foundations required to analyze and design combinational digital systems. It begins with number systems and codes, then examines logic gates, logic families, Boolean algebra, Karnaugh-map minimization, and common combinational building blocks. The final sections address programmable logic, practical design constraints, and an applied digital-control example.

Learning Objectives

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

1. Convert among binary, octal, decimal, and hexadecimal representations.
2. Represent signed numbers and explain common digital codes.
3. Describe logic families, propagation delay, power dissipation, and noise margins.
4. Apply Boolean identities and De Morgan’s theorems to simplify logic expressions.
5. Use Karnaugh maps to obtain minimized sum-of-products and product-of-sums expressions.
6. Design and analyze adders, subtractors, multiplexers, decoders, encoders, and comparators.
7. Explain the operation and selection of programmable logic devices.
8. Recognize practical limitations involving hazards, loading, fan-out, and undefined inputs.

1. Digital Representation and Number Systems

A binary digit, or bit, has two possible values: 0 and 1. A group of eight bits is a byte. In an unsigned binary number, each position has a power-of-two weight:

Here, b_i is the bit in position i, n is the number of bits, and the least significant bit has i=0. For an unsigned n-bit number, the range is 0 to 2ⁿ − 1.

1.1 Binary, octal, and hexadecimal

Binary uses radix 2, octal uses radix 8, and hexadecimal uses radix 16. Hexadecimal digits A–F represent decimal values 10–15. Conversion between binary and hexadecimal is particularly convenient because one hexadecimal digit corresponds exactly to four binary bits. One octal digit corresponds to three binary bits.

Example 1: Binary to decimal and hexadecimal

For 11010110₂,

11010110₂ = 128 + 64 + 16 + 4 + 2 = 214₁₀.

Grouping from the right gives 1101\ 0110₂ = D6₁₆. Thus, 11010110₂ = 214₁₀ = D6₁₆.

Example 2: Decimal to binary

To convert 173 to binary, select powers of two:

173 = 128 + 32 + 8 + 4 + 1.

Therefore, the bits corresponding to 128, 32, 8, 4, and 1 are 1, giving 10101101₂.

For fractional values, the positional expression is

where negative indices represent fractional positions. For example, 0.101₂ = 1/2 + 1/8 = 0.625₁₀. Not every decimal fraction has a finite binary representation.

1.2 Signed-number systems

Digital systems must represent positive and negative values. Three historically important systems are sign-magnitude, one’s complement, and two’s complement.

In sign-magnitude representation, the most significant bit indicates the sign and the remaining bits represent magnitude. It has both positive and negative zero. One’s complement forms a negative number by complementing every bit; it also has two zeros.

Two’s complement is standard in most processors because addition and subtraction use the same hardware. To form the negative of a binary number, complement every bit and add 1. An n-bit two’s-complement number has range

The range is asymmetric because one bit pattern is used for the most negative value.

Example 3: Two’s-complement subtraction

Using 8 bits, represent −37. First, 37₁₀ = 00100101₂. Complementing gives 11011010₂, and adding 1 gives 11011011₂. Thus −37 is 11011011₂.

To calculate 25 − 37, add 25 to the two’s complement of 37:

00011001 + 11011011 = 11110100.

The result is negative. Complementing 11110100 and adding 1 gives 00001100, so the result is −12.

Overflow occurs when the mathematical result lies outside the representable range. In two’s complement, adding two positive numbers and obtaining a negative result, or adding two negative numbers and obtaining a positive result, indicates overflow. Carry out alone is not a reliable overflow test.

2. Digital Codes

A code assigns bit patterns to symbols or values. Codes are selected according to the required arithmetic, display, communication, or error-detection function.

Binary-coded decimal

In binary-coded decimal (BCD), each decimal digit is represented independently by four bits. For example, decimal 59 is 0101\ 1001_BCD, not the pure binary representation of 59. BCD simplifies decimal display but uses more bits than ordinary binary.

Gray code

Gray code is arranged so that adjacent values differ in only one bit. This property reduces ambiguity in position sensors and rotary encoders, where several bits might not change at exactly the same time. Binary-to-Gray conversion uses

g_n−1=b_n−1, and g_i=b_i+1⊕b_i,

where ⊕ denotes exclusive OR.

ASCII and Unicode

ASCII encodes common letters, digits, punctuation, and control characters. Unicode extends character representation to a much larger range of writing systems and symbols. The physical circuit does not interpret a character intrinsically; it processes a bit pattern according to the chosen coding convention.

Error-detecting codes

A parity bit makes the total number of 1s either even or odd. It detects any odd number of bit errors but cannot reliably detect an even number of errors and cannot correct an error. More powerful codes, such as cyclic redundancy checks and error-correcting codes, are used in communication and storage systems.

3. Logic Levels and Logic Families

A logic gate produces an output determined by one or more binary inputs. Real circuits use voltage ranges rather than ideal mathematical values. A data sheet specifies input-low and input-high limits, V_IL(max) and V_IH(min), and output limits, V_OL(max) and V_OH(min).

Noise margin measures the voltage disturbance that can be tolerated without causing a logic error:

Here, NM_L and NM_H are low- and high-state noise margins, respectively. These formulas apply when the driving and receiving devices belong to compatible logic families and the specified worst-case limits are used. Voltages are measured in volts.

Important logic-family characteristics include:

• Propagation delay: time between a valid input transition and the corresponding output transition.
• Rise and fall time: time required for a signal to move between specified voltage levels.
• Power dissipation: energy converted to heat. CMOS static power is ideally very small, but dynamic power increases with switching frequency and capacitive load.
• Fan-out: number of standard inputs that one output can drive while maintaining specifications.
• Operating-voltage range: supply range over which guaranteed operation is available.

The approximate dynamic power of a CMOS node is

where α is switching activity, C_L is load capacitance in farads, V_DD is supply voltage in volts, and f is switching frequency in hertz. This approximation neglects short-circuit and leakage components.

TTL traditionally uses bipolar transistors and commonly operates near 5 V. CMOS uses complementary MOSFETs, offers high input impedance, and generally provides lower static power. Modern systems frequently use low-voltage CMOS, but devices with different voltage standards must not be connected without checking thresholds, output drive, and protection requirements.

4. Logic Gates and Boolean Algebra

The fundamental gates are AND, OR, NOT, NAND, NOR, XOR, and XNOR. If A and B are Boolean variables, the operations are written as follows:

Boolean algebra uses 0 and 1 but is not ordinary numerical algebra. Essential identities include

A+0=A, A·1=A, A+1=1, A·0=0,

A+A=A, AA=A, A+\overline{A}=1, and A\overline{A}=0.

The distributive identities are A(B+C)=AB+AC and A+BC=(A+B)(A+C). De Morgan’s theorems are

NAND and NOR are universal gates because any Boolean function can be constructed using only NAND gates or only NOR gates. XOR is especially important in arithmetic and parity circuits.

5. Truth Tables and Canonical Forms

A truth table lists the output for every input combination. With n independent inputs there are 2ⁿ combinations. A minterm is a product term containing every variable exactly once, either complemented or uncomplemented. A maxterm is a sum term containing every variable exactly once.

A function can be written in sum-of-products form as a sum of minterms:

This means that F is 1 for minterm indices 1, 3, 5, and 7, using the conventional binary ordering ABC. The equivalent product-of-sums form identifies the rows for which the function is 0.

6. Karnaugh-Map Minimization

A Karnaugh map (K-map) is a visual arrangement of truth-table values in Gray-code order. Adjacent cells differ in exactly one variable. Groups must contain 1, 2, 4, 8, or another power of two cells. Groups may wrap around an edge, and overlapping is permitted when it produces a simpler expression. Diagonal cells are not adjacent.

For a sum-of-products result, group 1s. A variable remains in a product term only if it is constant throughout the group. Larger groups eliminate more variables. For a product-of-sums result, group 0s instead. Don’t-care conditions, represented by X, may be included when they help produce larger groups, but they need not be used.

Worked Example 4: Three-variable minimization

Suppose

F(A,B,C)=∑m(1,3,5,7).

The listed minterms are precisely the rows in which C = 1. A K-map group containing all four cells eliminates A and B, leaving

F=C.

This example demonstrates why map arrangement and adjacency matter: a visually compact but diagonally connected group would be invalid.

K-maps are practical for up to about four or five variables. For larger functions, tabulation methods or computer-aided synthesis are more scalable. Minimization should also consider hazards, gate availability, fan-in, delay, and power—not merely the number of terms.

7. Combinational-Circuit Design Procedure

A combinational circuit has outputs determined solely by present inputs. It contains no intentional memory. A systematic design method is:

1. Define the input and output variables.
2. State the required behavior in words.
3. Construct a truth table.
4. Derive Boolean expressions.
5. Minimize the expressions using algebra or K-maps.
6. Select gates or standard integrated circuits.
7. Check timing, loading, noise margins, unused inputs, and hazards.
8. Simulate, build, and test all significant input combinations.

A circuit diagram is not a substitute for a precise specification. Ambiguous active-low signals should be clearly marked, for example \overline{EN} for an enable that is active when low.

8. Arithmetic Circuits

Half adder

A half adder adds two one-bit inputs A and B. Its sum and carry are

It cannot accept a carry from a lower-order position.

Full adder

A full adder adds A, B, and carry-in C_in. Its outputs are

A full adder can be constructed from two half adders and an OR gate. Connecting full adders in cascade forms a ripple-carry adder. Its hardware is simple, but the worst-case delay increases with word length because each carry must propagate through successive stages.

A carry-lookahead design reduces delay by computing generate and propagate signals. For bit position i, G_i=A_iB_i and P_i=A_i⊕B_i are common definitions, giving C_i+1=G_i+P_iC_i. The exact implementation depends on the selected architecture.

Subtraction

Two’s-complement subtraction uses addition:

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

A controlled inverter complements B when subtraction is selected, and the initial carry-in is set to 1. One adder can therefore perform both addition and subtraction.

Comparators

A one-bit equality output is XNOR:

E=AB+\overline{A}\,\overline{B}.

For multi-bit equality, all corresponding bit comparisons are ANDed. Magnitude comparison proceeds from the most significant bit because the first unequal bit determines which number is larger.

9. Multiplexers, Demultiplexers, Decoders, and Encoders

A multiplexer (MUX) selects one of several data inputs and connects it to one output. A 2-to-1 MUX with inputs D0 and D1 and select S is

A MUX can implement arbitrary Boolean functions by connecting data inputs to 0, 1, or remaining variables. It is also used for data routing and resource sharing.

A demultiplexer routes one input to one of several outputs. A decoder activates one output corresponding to a binary input code. An n-to-2ⁿ decoder has up to 2ⁿ output lines, although enable inputs and active-low conventions are common. Decoders are used for memory address selection, instruction decoding, display control, and chip selection.

An encoder performs the reverse operation, converting one active input into a binary code. A simple encoder assumes only one input is active. A priority encoder resolves the case in which multiple inputs are active by assigning priority, usually to the highest- or lowest-numbered input. Valid and enable outputs may indicate whether any input is present.

A seven-segment display decoder converts a binary or BCD value into segment-control signals. Designs must account for common-anode versus common-cathode displays, active-low outputs, invalid BCD codes, and required current-limiting resistors.

10. Programmable Logic

Programmable logic devices implement Boolean functions using configurable connections rather than fixed, individually wired gates.

• PROM: fixed AND array and programmable OR array; useful for lookup-table implementation.
• PLA: programmable AND and OR arrays; flexible two-level logic implementation.
• PAL: programmable AND array with more constrained OR structure; generally faster or simpler than a PLA for supported functions.
• CPLD: multiple programmable logic blocks interconnected through a programmable routing structure; predictable timing and nonvolatile options are common.
• FPGA: configurable logic blocks, programmable interconnect, memory, clocking resources, and often processors or arithmetic units. FPGAs support large digital systems but require careful timing closure and resource planning.

Hardware description languages such as VHDL and Verilog describe behavior or structure. Synthesis tools convert synthesizable descriptions into gates, lookup tables, flip-flops, and routing resources. Simulation is essential, but a simulation model may differ from synthesized hardware if timing, inferred latches, multiple drivers, or incomplete assignments are mishandled.

11. Hazards and Practical Reliability

A static hazard is an unwanted temporary output transition caused by unequal propagation delays along different paths. For example, a minimized expression may logically remain 1 while one product term turns off before another turns on. Adding a redundant consensus term can remove certain static hazards, though it may increase hardware.

Dynamic hazards can occur in multilevel circuits with multiple transitions during a single intended change. Hazard analysis is particularly important in asynchronous control, clock gating, and safety-related systems. Synchronous design reduces many timing problems by allowing state changes only at controlled clock events, but combinational outputs still require appropriate setup, hold, and propagation-delay analysis when connected to sequential circuits.

Unused CMOS inputs must not be left floating. They should be tied to a defined logic level according to the manufacturer’s recommendations. Inputs can be damaged by electrostatic discharge, overvoltage, or excessive current. Grounding, decoupling capacitors, signal integrity, and correct power sequencing are part of professional digital design.

12. Applied Case: Automated Water-Tank Controller

Background

Consider an illustrative water-tank controller for a small treatment facility. The pump should run when the tank is low, provided the emergency-stop switch is not active and the source reservoir is not empty. A high-level sensor should stop the pump to prevent overflow.

Problem definition

Let L = 1 when the tank is below the low-level threshold, H = 1 when the high-level sensor is active, E = 1 when emergency stop is pressed, and S = 1 when the source reservoir is empty. Let P = 1 command the pump to run. The required behavior is

P=L\,\overline{H}\,\overline{E}\,\overline{S}.

This expression assumes that all sensors provide reliable, debounced logic levels and that the pump command is active high.

Analysis and implementation

The function can be implemented directly with NOT gates followed by a four-input AND gate. If only two-input gates are available, the AND function can be cascaded. A fail-safe design may use normally closed emergency-stop contacts and an independent hardware interlock so that a broken wire tends toward the safe, pump-off condition.

The controller should also include hysteresis or separate thresholds if the level sensor may chatter near a boundary. A watchdog, manual override with clear authority, overload protection, and an alarm for contradictory sensor states improve operational safety. The logic circuit alone does not guarantee safe operation: actuator ratings, isolation, contactor suppression, grounding, and applicable electrical-safety regulations must also be addressed.

Outcome and learning points

The case illustrates the complete design sequence: translate requirements into variables, define active levels, form a Boolean function, select an implementation, and evaluate failure modes. It also shows why practical engineering requires more than algebraic minimization. Safety, testing, sensor behavior, and regulatory compliance are integral to the design.

13. Contemporary Developments and Professional Practice

Digital systems increasingly combine conventional gates with embedded processors, programmable logic, high-speed serial interfaces, and machine-learning accelerators. AI tools can assist with Boolean minimization, HDL generation, simulation-test creation, and fault diagnosis, but generated designs require independent verification. A plausible waveform or syntactically correct HDL does not prove functional safety.

Best practice includes traceable requirements, explicit signal conventions, complete truth tables for safety functions, formal or exhaustive verification where feasible, timing analysis, documented assumptions, version control, and testing under voltage, temperature, load, and fault conditions. Designers should protect confidential hardware descriptions and avoid relying on unverified generated code.

Chapter Summary

Digital electronics uses discrete logic levels to represent and manipulate information. Binary, octal, hexadecimal, signed-number systems, BCD, Gray code, character codes, and parity serve different representation needs. Two’s complement is the dominant signed arithmetic format because it permits common addition and subtraction hardware.

Logic families are characterized by voltage limits, noise margins, propagation delay, power, fan-out, and supply requirements. Boolean algebra and universal NAND/NOR gates provide the mathematical and hardware foundations for logic design. Karnaugh maps minimize small Boolean functions by grouping adjacent cells in Gray-code order, while practical designs must also consider hazards and timing.

Half adders, full adders, subtractors, comparators, multiplexers, decoders, demultiplexers, and encoders are fundamental combinational blocks. PROMs, PLAs, PALs, CPLDs, and FPGAs provide increasingly flexible programmable implementation platforms. Reliable engineering requires explicit specifications, defined unused inputs, signal-integrity practices, verification, and attention to safety and regulatory constraints.

Key Terms

Binary number: A number represented using radix 2.

Hexadecimal: A radix-16 number system using digits 0–9 and A–F.

Two’s complement: A signed representation formed by complementing all bits and adding one.

BCD: A code representing each decimal digit with four binary bits.

Gray code: A code in which adjacent values differ by one bit.

Logic family: A technology class defining electrical and switching characteristics of digital gates.

Noise margin: The guaranteed voltage tolerance between output and input logic limits.

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

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

Boolean algebra: Algebraic system used to analyze binary variables and logic operations.

Universal gate: A gate type, such as NAND or NOR, capable of implementing any Boolean function.

Minterm: A product term containing every function variable once.

Karnaugh map: A Gray-code-ordered map used to minimize Boolean expressions.

Hazard: An unwanted transient caused by unequal propagation delays.

Half adder: A circuit adding two one-bit inputs.

Full adder: A circuit adding two bits and an input carry.

Multiplexer: A circuit selecting one of several inputs.

Decoder: A circuit activating an output corresponding to an input code.

Priority encoder: An encoder that resolves multiple active inputs by priority.

FPGA: A field-programmable gate array containing configurable logic and interconnect.

Review Questions

Short Answer Questions

1. Why does one hexadecimal digit correspond to four binary bits?
2. What is the principal advantage of two’s-complement arithmetic?
3. Define high-state and low-state noise margin.
4. Why are NAND and NOR called universal gates?
5. State one difference between a multiplexer and a decoder.

Long Answer Questions

1. Explain unsigned and two’s-complement number representation, including range and overflow.
2. Describe the operation of a K-map and state the rules for forming valid groups.
3. Compare TTL and CMOS with respect to input impedance, power, voltage, and switching behavior.
4. Derive the sum and carry expressions for a full adder and explain a ripple-carry implementation.
5. Compare PROM, PLA, PAL, CPLD, and FPGA technologies.

Analytical / Application Questions

1. Design a logic function that activates an alarm when a door is open, the system is armed, and either smoke is detected or the temperature is excessive. State assumptions and minimize the expression.
2. A four-bit controller must select one of four sensor inputs, indicate which sensor is selected, and report whether two sensor readings are equal. Propose suitable combinational blocks and explain their interconnection.
3. Analyze the water-tank controller case. Identify at least three possible failure modes and propose hardware or logic measures that reduce the associated risk.

Multiple Choice Questions with Answers

Question 1

What is the hexadecimal representation of 11010110₂?

A. B6

B. C6

C. D6

D. E6

Correct Answer: C. D6

Question 2

What is the 8-bit two’s-complement representation of −37?

A. 11011011

B. 11011010

C. 00100101

D. 10100101

Correct Answer: A. 11011011

Question 3

Which code changes only one bit between adjacent numerical values?

A. BCD

B. Gray code

C. ASCII

D. Parity code

Correct Answer: B. Gray code

Question 4

Which expression gives the high-state noise margin?

A. V_IL(max)−V_OH(min)

B. V_OH(min)−V_IH(min)

C. V_OL(max)−V_IL(max)

D. V_DD−V_SS

Correct Answer: B. V_OH(min)−V_IH(min)

Question 5

Which Boolean expression represents a 2-to-1 multiplexer?

A. SD₀+\overline{S}D₁

B. D₀D₁

C. \overline{S}D₀+SD₁

D. S+D₀+D₁

Correct Answer: C. \overline{S}D₀+SD₁

Question 6

A half adder produces which outputs?

A. Sum = AND, carry = XOR

B. Sum = XOR, carry = AND

C. Sum = OR, carry = AND

D. Sum = XNOR, carry = OR

Correct Answer: B. Sum = XOR, carry = AND

Question 7

In a Karnaugh map, valid groups must contain how many cells?

A. Any prime number of cells

B. Only diagonal cells

C. A power of two cells

D. Exactly three cells

Correct Answer: C. A power of two cells

Question 8

What is the principal function of a decoder?

A. Convert one active input into a priority code

B. Activate an output corresponding to an input code

C. Store a binary word permanently

D. Add two binary numbers

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

Question 9

For A=1 and B=1, what is the output of an XOR gate?

A. 0

B. 1

C. Undefined

D. High impedance only

Correct Answer: A. 0

Question 10

Which device generally contains configurable logic blocks and programmable interconnect?

A. Fixed-function decoder

B. FPGA

C. Half adder

D. Parity generator only

Correct Answer: B. FPGA