Combinational Logic Design: Gates, Boolean Algebra, K-Maps and Standard Circuits

A combinational circuit is one whose outputs depend only on its present inputs; it has no memory. Adders, comparators, decoders and multiplexers are all combinational, and together they form the arithmetic and data-path logic of a CPU.

This is the largest unit of the subject and the one with the most exam marks.

XOR of several inputs is 1 when an odd number of inputs are 1, which is why XOR trees generate parity. XNOR is the one-bit equality comparator.

Universal gates. NAND alone (and NOR alone) can build every other gate:

Any SOP expression becomes a two-level NAND–NAND circuit directly: replace every AND and OR with NAND (bubbles cancel by De Morgan). Any POS becomes NOR–NOR.

3.2 Boolean algebra

Variables take values 0 or 1. Operations: + (OR), · (AND), ' (NOT).

Duality: swap AND↔OR and 0↔1 in a true identity and you get another true identity. De Morgan extends to any number of variables: (A + B + C)' = A'B'C'.

Standard forms. A minterm is an AND of all variables, each complemented or not, equal to 1 for exactly one input row; maxterm is an OR of all variables, equal to 0 for exactly one row.

For three variables, row i of the truth table gives minterm mᵢ (e.g. m₃ = A'BC, since 011) and maxterm Mᵢ = (mᵢ)'.

• Canonical SOP = sum of the minterms where F = 1: F = Σm(…).
• Canonical POS = product of the maxterms where F = 0: F = ΠM(…).
• The minterm indices of F and the maxterm indices of F are complementary sets.

Example: F(A,B,C) is 1 for 1, 4, 5, 7. Then F = Σm(1,4,5,7) = A'B'C + AB'C' + AB'C + ABC, and F = ΠM(0,2,3,6).

3.3 Simplification with Karnaugh maps

A K-map arranges the truth table in a grid in which adjacent cells differ by exactly one variable (Gray-code order 00, 01, 11, 10 along each axis), so that grouping adjacent 1s applies the rule AB + AB' = A visually.

Rules

1. Mark 1s for SOP (use 0s for POS).
2. Form groups of 1, 2, 4, 8, 16 adjacent cells (a power of two), rectangles only; the map wraps around top-to-bottom and left-to-right, and the four corners are adjacent.
3. Use the fewest, largest groups that cover every 1; overlap is allowed.
4. Each group gives one product term: keep the variables that do not change inside the group. Larger group → fewer literals.
5. Don't-care cells (X) may be included in a group if they enlarge it, and are otherwise ignored.
6. Prime implicant: a group that cannot be enlarged. Essential prime implicant: the only group covering some 1; it must be chosen.

Two-variable and three-variable layout (rows A, columns BC in Gray order 00, 01, 11, 10):

      BC  00  01  11  10
   A=0 |  m0  m1  m3  m2
   A=1 |  m4  m5  m7  m6

Four-variable example. F(A,B,C,D) = Σm(0, 1, 2, 5, 8, 9, 10). Layout (rows AB, columns CD in Gray order):

       CD  00  01  11  10
   AB=00 |  1   1   0   1
   AB=01 |  0   1   0   0
   AB=11 |  0   0   0   0
   AB=10 |  1   1   0   1

Groups: the four cells m0, m1, m8, m9 (columns 00 and 01 in rows 00 and 10, wrapping vertically) form B'C'; the four cells m0, m2, m8, m10 (the four corners) form B'D'; m1 and m5 (column 01, rows 00 and 01) form A'C'D. So F = B'C' + B'D' + A'C'D.

POS from the map: group the 0s, write each group as a sum of the variables that stay constant but complemented, and multiply the sums. Don't-care example. F = Σm(1, 3, 7, 11, 15) + d(0, 2, 5).

Cells 0, 1, 2, 3 form the group A'B' (using the X cells 0 and 2 to complete it), and cells 3, 7, 11, 15 form CD. Every required 1 is covered, so F = A'B' + CD; the X cell 5 is simply left out.

3.4 Arithmetic circuits

Half adder adds two bits: Sum = A ⊕ B, Carry = A·B.

Full adder adds A, B and carry-in C_in: Sum = A ⊕ B ⊕ C_in; C_out = AB + C_in(A ⊕ B). It can be built from two half adders and an OR gate.

Half subtractor: Difference = A ⊕ B, Borrow = A'B. Full subtractor: D = A ⊕ B ⊕ B_in, B_out = A'B + (A ⊕ B)' B_in.

Parallel (ripple-carry) adder. Chain n full adders, each carry-out feeding the next carry-in. It is simple but slow: the carry must ripple through all stages, so the delay is about n × (carry delay).

A carry-lookahead adder computes carries in parallel from generate G = AB and propagate P = A ⊕ B, with C₁ = G₀ + P₀C₀, C₂ = G₁ + P₁G₀ + P₁P₀C₀, and so on.

Adder-subtractor: XOR each B input with a control M and feed M as the first carry-in; M = 0 adds, M = 1 computes A + B' + 1 = A − B. Overflow is C_n ⊕ C_(n−1). A 4-bit chip is the 7483; BCD addition needs a correction of +6.

3.5 Encoders, decoders, multiplexers

Decoder (n → 2ⁿ). Exactly one output goes active for each input code, so each output is a minterm of the inputs.

A 3-to-8 decoder (74138) has three inputs, eight outputs and enable inputs; any function of three variables is the OR of the right decoder outputs. Decoders drive memory chip-select lines and BCD-to-seven-segment displays.

A 4-to-16 decoder can be built from two 3-to-8 decoders using the extra input as the enable selector.

Encoder (2ⁿ → n). The reverse: 8 inputs, 3-bit output giving the number of the active input.

A plain encoder fails if two inputs are active together; a priority encoder outputs the code of the highest-priority active input and has a valid flag.

Octal-to-binary encoder: A₂ = D₄ + D₅ + D₆ + D₇, A₁ = D₂ + D₃ + D₆ + D₇, A₀ = D₁ + D₃ + D₅ + D₇.

Multiplexer (MUX). A data selector: 2ⁿ data inputs, n select lines, one output. A 4-to-1 MUX has Y = S₁'S₀'I₀ + S₁'S₀I₁ + S₁S₀'I₂ + S₁S₀I₃.

MUX as a function generator: a 2ⁿ-to-1 MUX implements any function of n variables by connecting the variables to the selects and tying data inputs to 0, 1 or to the other variable.

Example F(A,B) = A ⊕ B on a 4-to-1 MUX with S₁ = A and S₀ = B: I₀ = 0, I₁ = 1, I₂ = 1, I₃ = 0. A 2ⁿ⁻¹-to-1 MUX can implement an n-variable function by using the last variable as data input. MUX trees expand width (a 16-to-1 MUX from five 4-to-1 MUXes).

Demultiplexer (DEMUX). One input routed to one of 2ⁿ outputs chosen by the select lines; a decoder with its enable input used as data is a DEMUX.

Magnitude comparator. For two bits, A = B when XNOR is 1; A > B when AB' = 1; A < B when A'B = 1. A 4-bit comparator (7485) compares from the most significant bit down and produces A>B, A=B, A<B.

Parity generator and checker. An even-parity bit for 4 data bits is P = D₃ ⊕ D₂ ⊕ D₁ ⊕ D₀. The checker XORs all received bits (data and parity); output 1 means an error.

3.6 Basic ideas of programmable logic

Instead of wiring gates by hand, a PLD contains a grid that can be programmed.

A PROM has a fixed AND array (a full decoder) and a programmable OR array; a PAL has a programmable AND array and fixed OR array; a PLA has both arrays programmable.

FPGAs generalise the idea with thousands of programmable lookup tables. A ROM is a combinational circuit: its address is the input, its stored word is the output.

(a) Solderless breadboard (400 tie points)

(b) HP 1653B logic analyzer

1Rows of five joined holes: place the IC across the centre gap2Power rails (red +, blue -)3Centre gap separating the two halves

3.7 Where combinational circuits are used: eight applications

1. Adders inside every CPU. The ALU is built around full adders chained together. They do addition, and with two's complement they also do subtraction and address calculation. Every spreadsheet total on a Nepali college server passes through such adders.
2. Decoders for memory and I/O selection. A decoder turns an address such as 1011 into a single active line. This selects exactly one memory chip or one device. Without it the CPU could not talk to RAM and the keyboard separately.
3. Multiplexers for data routing. A MUX picks one of many inputs and sends it on one line. Telephone exchanges, the input selector of a TV and the data paths in a CPU use it. A 4-to-1 MUX can also generate any 2-variable function.
4. Encoders for keyboards and interrupts. A priority encoder gives the binary number of the highest-priority active input. A keypad of an ATM and an interrupt controller both use it. If two keys are pressed together, the encoder picks the more important one.
5. Seven-segment display drivers. A BCD-to-seven-segment decoder (such as the 7447) lights the right segments for a digit. Electronic meters, queue-token boards in a bank and digital clocks show numbers in this way.
6. Comparators for decisions. A magnitude comparator tells whether A is greater than, equal to or smaller than B. A thermostat, a password check and a "sort" instruction all depend on it. A 4-bit comparator such as the 7485 can be cascaded for more bits.
7. Parity generators and checkers. An XOR tree creates the parity bit on sending and re-checks it on receiving. Memory modules and serial communication use this to spot a flipped bit. The circuit is simple and fast.
8. Programmable logic (PLA, PAL, FPGA). A designer can place a whole sum-of-products design in one programmable chip instead of many gates. This saves board space and allows a later change. University labs use FPGAs to test new processor designs.

Formula and fact sheet

• Half adder: S = A⊕B, C = AB. Full adder: S = A⊕B⊕Cin, Cout = AB + Cin(A⊕B).
• De Morgan: (A+B)' = A'B'; (AB)' = A'+B'. Consensus: AB + A'C + BC = AB + A'C.
• Minterm index from row; ΣF and ΠF use complementary index sets.
• K-map groups: powers of two, wrap-around, fewest and largest; X cells optional.
• n-to-2ⁿ decoder yields minterms; 2ⁿ-to-1 MUX implements any n-variable function.
• NAND–NAND = SOP; NOR–NOR = POS. A − B = A + B' + 1.

Practice

1. Simplify F = AB + A'C + BC and F = A + A'B + A'B'C.
2. Prove (A + B)(A' + C) = AC + A'B using Boolean laws.
3. Express F(A,B,C) = Σm(1, 4, 5, 7) in POS form and write the simplified SOP.
4. Simplify F(A,B,C,D) = Σm(0, 2, 5, 7, 8, 10, 13, 15).
5. Simplify F(A,B,C,D) = Σm(1, 3, 7, 11, 15) + d(0, 2, 5).
6. Realise XOR using only NAND gates and state how many are needed.
7. Design a full adder from two half adders and one OR gate; give the equations.
8. Implement F(A,B,C) = Σm(1, 2, 4, 7) using an 8-to-1 MUX and then using a 4-to-1 MUX.
9. Design a 2-bit magnitude comparator (A₁A₀ vs B₁B₀) in terms of its outputs.
10. How many 3-to-8 decoders make a 5-to-32 decoder?

Model answers: medium (5 marks) and long (10 marks) questions

Q (5 marks). Simplify F(A, B, C, D) = Σm(0, 1, 2, 5, 8, 9, 10) using a Karnaugh map and draw the resulting circuit in words.

A Karnaugh map is a Gray-coded grid in which neighbouring cells differ in one variable, so two adjacent 1s can be merged and one variable disappears.

For four variables the grid has 16 cells, with rows AB and columns CD ordered 00, 01, 11, 10 (Figure 3.2). The 1s are placed at m0, m1, m2, m5, m8, m9 and m10.

Grouping (powers of 2, as large as possible, edges wrap round):

1. Group of four m0, m1, m8, m9: A and D change, B = 0 and C = 0 stay fixed, so the term is B'C'.
2. Group of four m0, m2, m8, m10 (the four corners): A and C change, B = 0 and D = 0 stay, giving B'D'.
3. Group of two m1, m5: B changes, A = 0, C = 0, D = 1 stay, giving A'C'D.

So F = B'C' + B'D' + A'C'D. All seven 1s are covered. The original expression needs seven four-literal minterms (28 literals); the simplified one needs three terms with 7 literals.

The circuit is two-level AND–OR: two 2-input ANDs and one 3-input AND feed one 3-input OR. Using NAND gates only, each AND and the OR are replaced by NAND (NAND–NAND form), which needs just one chip type.

Q (5 marks). Explain the 4-to-1 multiplexer and show how it implements an XOR gate.

A multiplexer (MUX) selects one of several data inputs and passes it to a single output under the control of select lines. A 4-to-1 MUX has four data inputs I0–I3, two select lines S1 S0 and one output Y.

Boolean expression: Y = S1'S0'·I0 + S1'S0·I1 + S1S0'·I2 + S1S0·I3. Internally it is a 2-to-4 decoder whose outputs are ANDed with the data inputs and ORed together.

As a function generator: connect the variables to the select lines and tie each data input to 0, 1 or a variable.

For F = A ⊕ B take S1 = A and S0 = B. The truth table of XOR is 0, 1, 1, 0 for AB = 00, 01, 10, 11, so tie I0 = 0, I1 = 1, I2 = 1, I3 = 0.

A 2ⁿ-to-1 MUX can therefore realise any n-variable function with no extra gates, which is why a MUX is the basic cell of FPGA look-up tables.

Q (10 marks). Design a full adder from its truth table. Show how four full adders make a 4-bit ripple-carry adder, and compare it with a carry-lookahead adder.

Introduction. Addition is the most used arithmetic operation in a computer. A half adder adds two bits and cannot accept a carry from a lower stage, so it can only be used for the least significant bit. A full adder adds A, B and a carry-in C_in.

Truth table and equations. The outputs for ABC_in = 000 to 111 are Sum = 0, 1, 1, 0, 1, 0, 0, 1 and C_out = 0, 0, 0, 1, 0, 1, 1, 1 (see the table in 3.4). From the K-map:

• Sum = A ⊕ B ⊕ C_in (1 when an odd number of inputs are 1).
• C_out = AB + BC_in + AC_in, which equals AB + C_in(A ⊕ B).

Circuit. Figure 3.3 shows two half adders and one OR: the first half adder gives S1 = A ⊕ B and C1 = AB; the second adds S1 and C_in to give Sum and C2 = C_in·S1; and C_out = C1 + C2. In all this needs two XOR, two AND and one OR gate.

Ripple-carry adder. Connect C_out of stage i to C_in of stage i+1 for four stages, with C_in of stage 0 = 0 (or 1 for subtraction). Adding 0111 + 0101 gives 1100 with carry 0.

The adder is cheap and regular but slow: the carry must pass through every stage, so the delay is about n × (two gate delays). At 64 bits this limits the clock.

Carry-lookahead adder. It computes carries directly from generate G = AB and propagate P = A ⊕ B: C1 = G0 + P0C0, C2 = G1 + P1G0 + P1P0C0, and so on. Every carry is ready after two or three gate delays, whatever n is.

Conclusion. The full adder follows directly from its truth table and a K-map. Chaining it gives a multi-bit adder, and the speed problem of the carry is solved by lookahead logic at the cost of more gates.