Unit 4: Introduction to Combinational Logic Circuits

I. Foundations of Combinational Logic

A combinational logic circuit is a digital circuit whose outputs depend only on the inputs present at that instant. Unlike a sequential circuit, it contains no memory element, stored state, or clock-dependent feedback. Combinational circuits are constructed from logic gates and are described using Boolean expressions, truth tables, and logic diagrams.

• Binary convention: Logic 0 usually represents LOW voltage and logic 1 represents HIGH voltage; exact voltage ranges depend on the logic family, such as TTL or CMOS.
• Boolean operations:
  • AND (·): Output is 1 only when all inputs are 1.
  • OR (+): Output is 1 when at least one input is 1.
  • NOT ('): Complements the input, so 0 becomes 1 and 1 becomes 0.
  • XOR (⊕): Output is 1 when its inputs are different.
• Input-output relationship: For n binary inputs, a complete truth table contains 2^n input combinations.
• No memory: If the same input combination is applied again, the circuit produces the same output, apart from propagation delay.
• Propagation delay: A physical gate requires a small time to respond, so output changes occur shortly after input changes.
• Design procedure: A combinational circuit is commonly developed by defining inputs and outputs, constructing a truth table, deriving Boolean expressions, simplifying them, and implementing the required gates.

II. Adders — Binary Addition Circuits

A. Adders

Adders are combinational circuits that perform binary addition and produce a sum together with any carry generated.

• Binary addition rules: The basic arithmetic combinations are concrete consequences of base-2 notation.
  • 0 + 0 = 0
  • 0 + 1 = 1
  • 1 + 0 = 1
  • 1 + 1 = 10₂, giving sum 0 and carry 1.
• Half adder: A half adder adds two one-bit inputs, A and B, without accepting an input carry.

A B | S C
0 0 | 0 0
0 1 | 1 0
1 0 | 1 0
1 1 | 0 1

S = A ⊕ B
C = A·B

• S is the sum bit.
• C is the carry bit.
• An XOR gate generates S, while an AND gate generates C.
  • Half-adder limitation: It cannot directly add a carry from a less significant position, so it is unsuitable by itself for every stage of a multi-bit adder.
  • Full adder: A full adder adds input bits A and B and an input carry Cᵢ, producing sum S and output carry Cₒ.

S  = A ⊕ B ⊕ Cᵢ
Cₒ = A·B + Cᵢ(A ⊕ B)

• Cᵢ is the carry received from the preceding, less significant stage.
• Cₒ is the carry passed to the next, more significant stage.
  • Construction: One full adder can be made from two half adders and one OR gate. The first adds A and B; the second adds Cᵢ to the first sum.
  • Parallel adder: Multiple full adders can be cascaded to add multi-bit numbers. In a ripple-carry adder, each Cₒ becomes the next stage’s Cᵢ.
  • Worked example: For A = 1, B = 1, and Cᵢ = 1, the total is binary 11₂; therefore, S = 1 and Cₒ = 1.
  • Applications: Adders are used in arithmetic logic units, address calculations, counters, digital signal processing, and multiplication circuits.

III. Subtractors — Binary Difference Circuits

A. Subtractors

Subtractors are combinational circuits that subtract one binary number from another and indicate whether borrowing is required.

• Binary subtraction rules:
  • 0 − 0 = 0
  • 1 − 0 = 1
  • 1 − 1 = 0
  • 0 − 1 requires a borrow, giving difference 1.
• Half subtractor: A half subtractor calculates A − B, where A is the minuend bit and B is the subtrahend bit.

A B | D Bₒ
0 0 | 0 0
0 1 | 1 1
1 0 | 1 0
1 1 | 0 0

D  = A ⊕ B
Bₒ = A'·B

• D is the difference bit.
• Bₒ is the borrow output.
• Borrow occurs only when A = 0 and B = 1.
  • Full subtractor: A full subtractor computes A − B − Bᵢ, where Bᵢ is the borrow received from a less significant stage.

D  = A ⊕ B ⊕ Bᵢ
Bₒ = A'·B + A'·Bᵢ + B·Bᵢ

• Construction: A full subtractor can be formed using two half subtractors and an OR gate, in a structure analogous to a full adder.
• Multi-bit subtraction: Full subtractors can be cascaded, with each borrow output connected to the next stage’s borrow input.
• Worked example: For A = 0, B = 1, and Bᵢ = 1, the operation is 0 − 1 − 1. The output is D = 0 with Bₒ = 1, representing a borrowed value of two.
• Adder-subtractor circuits: Practical systems often use full adders for subtraction by adding the two’s complement of the subtrahend.
• Applications: Subtractors occur in arithmetic logic units, digital comparison, address calculations, and control systems.

IV. Multiplexers — Data Selection Circuits

A. Multiplexers

Multiplexers select one of several input lines and connect the selected input to a single output line.

• Basic function: A multiplexer is called a data selector because select inputs determine which data input reaches the output.
• Line relationship: A multiplexer with 2^n data inputs requires n select lines. Thus, a 4-to-1 multiplexer has four data inputs and two select inputs.
• 2-to-1 multiplexer: Inputs I₀ and I₁ are controlled by select line S.

S | Y
0 | I₀
1 | I₁

Y = S'·I₀ + S·I₁

• Y is the output.
• When S = 0, the term S'·I₀ passes I₀.
• When S = 1, the term S·I₁ passes I₁.
  • 4-to-1 multiplexer: With select lines S₁S₀, combinations 00, 01, 10, and 11 select I₀, I₁, I₂, and I₃, respectively.
  • Enable input: Many integrated multiplexers include an enable terminal that activates or disables the complete device.
  • Boolean-function realization: By connecting data inputs to 0, 1, or selected variables, a multiplexer can implement Boolean functions.
  • Applications: Multiplexers are used for data routing, communication-channel selection, parallel-to-serial conversion, and input selection in processors.

V. De-multiplexers — Data Distribution Circuits

A. De-multiplexers

De-multiplexers route one data input to one of several output lines according to the applied select code.

• Basic function: A de-multiplexer is a data distributor and performs the reverse routing function of a multiplexer.
• 1-to-2 de-multiplexer: Data input D is directed by select input S to output Y₀ or Y₁.

Y₀ = D·S'
Y₁ = D·S

• For S = 0, Y₀ = D and Y₁ = 0.
• For S = 1, Y₀ = 0 and Y₁ = D.
  • Output relationship: A de-multiplexer with n select inputs can control as many as 2^n outputs.
  • 1-to-4 operation: Select values 00, 01, 10, and 11 route data to Y₀, Y₁, Y₂, and Y₃, respectively.
  • Inactive outputs: Outputs not selected normally remain at logic 0; the selected output reproduces the data input.
  • Decoder relationship: A decoder with an enable input can act as a de-multiplexer when the enable terminal is used as the data input.
  • Applications: De-multiplexers support serial-to-parallel distribution, memory addressing, communication routing, and clock or control-signal distribution.

VI. Decoders — Code Recognition Circuits

A. Decoders

Decoders convert an n-bit binary input code into one of up to 2^n distinct output signals.

• One-hot output: In an active-HIGH decoder, exactly one output is normally HIGH for each valid input combination.
• 2-to-4 decoder: Inputs A₁A₀ select one of four outputs.

Y₀ = A₁'·A₀'
Y₁ = A₁'·A₀
Y₂ = A₁ ·A₀'
Y₃ = A₁ ·A₀

• Input 00 activates Y₀.
• Input 01 activates Y₁.
• Input 10 activates Y₂.
• Input 11 activates Y₃.
  • Enable control: When the enable input is inactive, all outputs remain inactive regardless of the input code.
  • Active-LOW versions: Some decoder ICs indicate the selected output with 0 rather than 1; bubbles on logic symbols identify active-LOW terminals.
  • Larger decoders: Enable lines allow smaller decoders to be combined. For example, 3-to-8 decoding can be organized using enabled lower-order stages.
  • Applications: Decoders are used in memory-chip selection, instruction decoding, display systems, and device-address recognition.

VII. Encoders — Code Generation Circuits

A. Encoders

Encoders convert one active input out of several input lines into a compact binary output code.

• Basic relationship: A 2^n-to-n encoder represents the active input number using n output bits.
• 4-to-2 encoder: Assuming exactly one input is HIGH, inputs D₀ to D₃ produce outputs Y₁Y₀.

Active input | Y₁ Y₀
D₀           | 0  0
D₁           | 0  1
D₂           | 1  0
D₃           | 1  1

Y₁ = D₂ + D₃
Y₀ = D₁ + D₃

• Input restriction: A basic encoder gives ambiguous results if multiple inputs are active simultaneously.
• Priority encoder: A priority encoder assigns precedence, usually to the highest-numbered input, and outputs the code of that input when several are active.
• Valid output: Priority encoders may provide a valid bit to distinguish an active D₀ from the condition in which no input is active, since both could otherwise produce code 00.
• Decoder contrast: An encoder compresses one-of-many inputs into a binary code, whereas a decoder expands a binary code into one-of-many outputs.
• Applications: Encoders are used in keyboard interfaces, interrupt controllers, sensor arrays, and code conversion.

VIII. Comparator up to 2-bit — Magnitude Comparison

A. Comparator up to 2-bit

A magnitude comparator determines whether one binary number is greater than, equal to, or less than another.

• Outputs: For numbers A and B, the three mutually exclusive outputs are A > B, A = B, and A < B.
• One-bit comparator: For single bits A and B, comparison follows directly from their values.

G = A·B'
E = A'·B' + A·B
L = A'·B

• G = 1 means A > B.
• E = 1 means A = B; this is the XNOR function.
• L = 1 means A < B.
  • Two-bit numbers: Let A = A₁A₀ and B = B₁B₀, where subscript 1 denotes the most significant bit.
  • Equality condition: The two numbers are equal only when both corresponding bit pairs are equal.

E = (A₁ XNOR B₁)·(A₀ XNOR B₀)

• Greater-than condition: A is greater if its most significant bit is greater, or if the most significant bits are equal and A₀ > B₀.

G = A₁·B₁' + (A₁ XNOR B₁)·A₀·B₀'

• Less-than condition: A is less if its most significant bit is smaller, or if the most significant bits are equal and A₀ < B₀.

L = A₁'·B₁ + (A₁ XNOR B₁)·A₀'·B₀

• Worked example: For A = 10₂ and B = 01₂, the most significant comparison is A₁ = 1 > B₁ = 0; therefore, G = 1, while E = 0 and L = 0.
• Cascading principle: Comparators for larger words compare the most significant unequal bit first; lower bits matter only when all higher corresponding bits are equal.
• Applications: Comparators are used in sorting hardware, threshold detection, arithmetic logic units, digital control, and address matching.