Arithmetic Circuits, Decoders, Encoders, Multiplexers & PLDs
Idea in plain words
Half Adder: Sum = A ⊕ B, Carry = A · B; Full Adder: Sum = A ⊕ B ⊕ C_{in}, Carry = AB + C_{in}(A ⊕ B).
Exam tip
High-yield exam topic (Very High).
Explanation
Combinational logic circuits produce outputs that depend purely on the present state of inputs, containing no memory elements or feedback loops. Large arithmetic logic units (ALUs) replace sequential ripple carry propagation O(n) with parallel CLA logic O(1). Multiplexers serve as universal function generators by connecting truth table output values directly to data input lines while mapping function variables to select inputs.
Key points
- Carry Look-Ahead Adder (CLA): Eliminates ripple carry delay by computing Carry Generate G_i = A_i · B_i and Carry Propagate P_i = A_i ⊕ B_i simultaneously.
- Adder-Subtractor Circuit: Uses an XOR control gate on input B with M (Mode bit): if M = 0 (Add), B ⊕ 0 = B and C₀ = 0; if M = 1 (Subtract), B ⊕ 1 = B' and C₀ = 1 (2's complement).
- Decoders: n-to-2^n lines. An active-low 3-to-8 decoder (IC 74138) can generate any minterm. Encoders: 2^n-to-n lines. Priority encoders resolve multiple simultaneous active inputs.
- Multiplexers (Data Selectors): 2^n inputs to 1 output via n selection lines. Any Boolean function of n variables can be implemented directly using a 2^{n-1}-to-1 MUX.
- Programmable Logic: ROM (fixed AND array, programmable OR); PLA (programmable AND, programmable OR); PAL (programmable AND, fixed OR array).
Example
Example
Design of a 4-bit Ripple Carry Adder using cascaded Full Adders: Full Adder 0 takes A0, B0, C0=0 and outputs S0, C1. FA 1 takes A1, B1, C1 and outputs S1, C2. Total propagation delay = 4 × t_{FA}.
Code examples
// Implementation of Boolean Function Using 8-to-1 Multiplexer
// Function: F(A, B, C, D) = ∑m(1, 3, 4, 11, 12, 13, 14, 15)
// Connect A, B, C to Select Lines S2, S1, S0. D is the data input:
// Minterm Pairs | Output F | Input to MUX (I_k)
// (m0, m1) | (0, 1) | I0 = D
// (m2, m3) | (0, 1) | I1 = D
// (m4, m5) | (1, 0) | I2 = D'
// (m6, m7) | (0, 0) | I3 = 0
// (m8, m9) | (0, 0) | I4 = 0
// (m10, m11) | (0, 1) | I5 = D
// (m12, m13) | (1, 1) | I6 = 1
// (m14, m15) | (1, 1) | I7 = 1
// Hardware connection: S2=A, S1=B, S0=C; I0=D, I1=D, I2=D', I3=0, I4=0, I5=D, I6=1, I7=1.
Exam questions
- [8 Marks] Design a 4-bit Carry Look-Ahead Adder (CLA) circuit with mathematical derivations for carry generate (G) and carry propagate (P) terms.
- [7 Marks] Implement the Boolean function F(A, B, C, D) = ∑m(0, 1, 3, 4, 8, 9, 15) using an 8-to-1 Multiplexer.
- [7 Marks] Design a 3-to-8 line decoder using basic gates and show how a Full Adder can be implemented using a 3-to-8 decoder and two OR gates.