Unit 2: Combinational logic circuits
Computer Architecture notes · PTU syllabus (UGCC2502)
On this page
Unit summary
Combinational circuits produce outputs that depend only on the present inputs. They perform the arithmetic, selection and code-conversion work inside a computer. This unit covers the half adder and half subtractor, the full adder and full subtractor, the parallel binary adder and the binary adder/subtractor, multiplexers and demultiplexers and implementation of Boolean functions with them, and encoders and decoders.
After this unit you can
- Design half and full adders and subtractors from truth tables
- Explain a parallel (ripple-carry) adder and the binary adder/subtractor
- Explain multiplexers and demultiplexers and use them to implement Boolean functions
- Explain encoders and decoders with truth tables and circuits
PTU syllabus topics
- Half adder/subtractor
- full adder/subtractor
- parallel binary adder
- binary adder/subtractor
- multiplexers and demultiplexers
- implementing Boolean equations using MUX/DEMUX
- encoders and decoders
Topic 1
Combinational circuits
In a combinational circuit the output depends only on the present inputs; it has no memory. Adders, subtractors, multiplexers, decoders and encoders are combinational circuits.
Output depends on
Present inputs only
Present inputs and past state
Memory
None
Has memory elements
Clock
Not needed
Usually clocked
Examples
Adder, multiplexer, decoder
Flip-flop, counter, register
- 1State the problem and list inputs and outputs
- 2Write the truth table
- 3Obtain simplified Boolean expressions with K-maps
- 4Draw the logic diagram
- 5Verify with the truth table
Arithmetic
Adders, subtractors, comparators
Data routing
Multiplexers, demultiplexers
Code conversion
Encoders, decoders, code converters
Error checking
Parity generators and checkers
Example
Half adder: it adds two bits A and B. Sum = A XOR B and Carry = A AND B. For A = 1, B = 1: Sum = 0 and Carry = 1, which is binary 10, that is 2. A full adder adds a third input, the carry from the previous stage.
Exam tip
Design steps: list the inputs and outputs, write the truth table, simplify with a K-map, then draw the circuit.
Topic 2
Half adder and full adder
Half adder
A half adder adds two single bits A and B and gives a Sum (S) and a Carry (C).
| A | B | Sum S | Carry C |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
Sum
S = A ⊕ B
Carry
C = A · B
- A half adder cannot add an incoming carry — hence the full adder.
Full adder
A full adder adds three bits — A, B and the carry-in Cin — and produces Sum and Carry-out.
| A | B | Cin | Sum | Cout |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
Sum
S = A ⊕ B ⊕ Cin
Carry-out
Cout = AB + Cin (A ⊕ B) = AB + BCin + ACin
Inputs
2 (A, B)
3 (A, B, Cin)
Outputs
Sum, Carry
Sum, Carry-out
Gates
1 XOR + 1 AND
2 XOR + 2 AND + 1 OR (or 2 half adders + OR)
Use
Least significant bit
Every other bit
Example
Full adder with A = 1, B = 1, Cin = 1: Sum = A ⊕ B ⊕ Cin = 1 ⊕ 1 ⊕ 1 = 1. Carry = AB + Cin(A ⊕ B) = 1 + 0 = 1. The output 11 in binary is 3, which is 1 + 1 + 1.
Exam tip
A full adder can be built from two half adders and one OR gate. To add two n-bit numbers, connect n full adders in a chain (ripple-carry adder).
Topic 3
Half subtractor and full subtractor
Half subtractor
A half subtractor computes A − B and produces a Difference (D) and a Borrow (Bo).
| A | B | Difference D | Borrow Bo |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 |
Difference
D = A ⊕ B
Borrow
Bo = A′B
Full subtractor
A full subtractor computes A − B − Bin (borrow-in).
| A | B | Bin | Difference | Borrow-out |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 0 |
| 1 | 1 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 |
Difference
D = A ⊕ B ⊕ Bin
Borrow-out
Bout = A′B + (A ⊕ B)′ Bin = A′B + A′Bin + B·Bin
Sum / Difference
A ⊕ B ⊕ C
A ⊕ B ⊕ Bin
Carry / Borrow
AB + C(A ⊕ B)
A′B + (A ⊕ B)′Bin
Only difference
Carry uses A
Borrow uses A′
Example
Half subtractor with A = 0, B = 1: Difference = A ⊕ B = 1 and Borrow = A′B = 1, because 0 − 1 needs a borrow. Full subtractor with A = 1, B = 0, Bin = 1: 1 − 0 − 1 = 0, so Difference = 0 and Borrow out = 0.
Exam tip
The difference output uses the same XOR as the adder's sum. Only the borrow expression differs: it uses A′.
Topic 4
Parallel binary adder and binary adder/subtractor
Parallel (ripple-carry) adder
A 4-bit parallel adder connects four full adders; the carry-out of each stage feeds the carry-in of the next, so the carry ripples from the least to the most significant bit.
Each box is a full adder with inputs A, B, carry-in and outputs sum and carry-out
- Ripple-carry adder
- Simple but slow: delay grows with the number of bits
- Carry look-ahead adder
- Generates all carries in parallel using Generate G = AB and Propagate P = A ⊕ B
- Carry equations
- C1 = G0 + P0C0; C2 = G1 + P1G0 + P1P0C0; C3 = G2 + P2G1 + P2P1G0 + P2P1P0C0
- Sum
- Si = Pi ⊕ Ci
- Trade-off
- Look-ahead is faster but needs more gates
Example
Add A = 1011 (11) and B = 0110 (6): bit 0: 1 + 0 = 1 carry 0; bit 1: 1 + 1 = 0 carry 1; bit 2: 0 + 1 + 1 = 0 carry 1; bit 3: 1 + 0 + 1 = 0 carry 1; result C4 S3S2S1S0 = 1 0001 = 17.
Binary adder/subtractor
A subtractor is obtained from an adder using 2's complement: A − B = A + B′ + 1. A mode control M selects the operation: M = 0 gives addition, M = 1 gives subtraction.
When M = 1 the XOR gates complement B and the carry-in M = 1 adds the 1 needed for 2's complement
- M = 0
- B passes unchanged and C0 = 0, so S = A + B
- M = 1
- B is complemented and C0 = 1, so S = A − B
- Overflow (signed numbers)
- V = C(n−1) ⊕ Cn — the carry into and out of the sign bit differ
- Carry out in subtraction
- C = 1 means no borrow (A ≥ B)
Topic 5
Multiplexers and demultiplexers
Multiplexer (MUX)
A multiplexer (data selector) selects one of 2ⁿ data inputs and sends it to the single output; n select lines choose the input.
2-to-1
2
1
4-to-1
4
2
8-to-1
8
3
16-to-1
16
4
| S1 | S0 | Output Y |
|---|---|---|
| 0 | 0 | I0 |
| 0 | 1 | I1 |
| 1 | 0 | I2 |
| 1 | 1 | I3 |
Output
Y = S1′S0′ I0 + S1′S0 I1 + S1S0′ I2 + S1S0 I3
Data selection
Choose one of many sources
Parallel-to-serial conversion
Implement Boolean functions
Any n-variable function with a 2ⁿ⁻¹-to-1 MUX
Bus transfer
Register selection in a computer
Communication
Many channels on one line (time-division)
Demultiplexer (DEMUX)
A demultiplexer does the reverse — it sends one data input to one of 2ⁿ outputs chosen by the select lines.
Function
Many inputs to one output
One input to many outputs
Data inputs
2ⁿ
1
Outputs
1
2ⁿ
Select lines
n
n
Also called
Data selector
Data distributor
Example
A 4-to-1 multiplexer: with inputs I0 to I3 and select lines S1S0 = 10 (binary for 2), the output Y equals I2. A 1-to-4 demultiplexer does the reverse: with S1S0 = 10, the single input appears on output line Y2 and the other lines stay 0.
Exam tip
A MUX with 2ⁿ inputs needs n select lines: 8-to-1 needs 3, 16-to-1 needs 4.
Topic 6
Implementing Boolean equations using MUX and DEMUX
Using a multiplexer
- 1Choose n − 1 variables as select lines
- 2Make a table with one column per select combination
- 3Express the output for each column in terms of the remaining variable (0, 1, C or C′)
- 4Connect those values to the data inputs
Example
Implement F(A, B, C) = Σm(1, 2, 6, 7) with a 4-to-1 MUX using A and B as select lines: for AB = 00 (m0, m1) F = C; AB = 01 (m2, m3) F = C′; AB = 10 (m4, m5) F = 0; AB = 11 (m6, m7) F = 1.
| Select AB | Minterms | F in terms of C | Data input |
|---|---|---|---|
| 00 | m0, m1 | C | I0 = C |
| 01 | m2, m3 | C′ | I1 = C′ |
| 10 | m4, m5 | 0 | I2 = 0 |
| 11 | m6, m7 | 1 | I3 = 1 |
Data inputs I0 to I3 = C, C′, 0, 1; select lines A (S1) and B (S0)
Using a demultiplexer (decoder)
- A 1-to-2ⁿ DEMUX with D = 1 works as a decoder: each output is one minterm. A function is obtained by ORing (or NANDing active-low outputs) the outputs that correspond to its minterms.
Example
Full adder with a 3-to-8 decoder: Sum = Σm(1, 2, 4, 7) = OR of outputs 1, 2, 4, 7; Carry = Σm(3, 5, 6, 7) = OR of outputs 3, 5, 6, 7.
Topic 7
Encoders and decoders
Encoder
An encoder has 2ⁿ input lines and n output lines; it converts the active input into its binary code.
| D3 | D2 | D1 | D0 | A1 | A0 |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 | 1 |
| 0 | 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 0 | 0 | 1 | 1 |
A1
A1 = D2 + D3
A0
A0 = D1 + D3
- Priority encoder
- When several inputs are 1, the one with highest priority is encoded
- Valid bit V
- Shows that at least one input is 1
- Octal-to-binary
- 8 inputs, 3 outputs — A2 = D4 + D5 + D6 + D7
- Decimal-to-BCD
- 10 inputs, 4 outputs
- Use
- Keyboards, interrupt controllers
| D3 | D2 | D1 | D0 | A1 | A0 | V |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | X | X | 0 |
| 0 | 0 | 0 | 1 | 0 | 0 | 1 |
| 0 | 0 | 1 | X | 0 | 1 | 1 |
| 0 | 1 | X | X | 1 | 0 | 1 |
| 1 | X | X | X | 1 | 1 | 1 |
Decoder
A decoder has n inputs and up to 2ⁿ outputs; exactly one output is active for each input code — the reverse of an encoder.
| A1 | A0 | Y0 | Y1 | Y2 | Y3 |
|---|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 | 0 | 1 |
Inputs
2ⁿ
n
Outputs
n
2ⁿ
Action
Active input → binary code
Binary code → one active output
Example
Keyboard to binary
Memory address decoding, 7-segment driver
- Enable input
- Allows the decoder to be switched on or off; two 2-to-4 decoders with enables form a 3-to-8 decoder
- Active-low outputs
- NAND-based decoders give 0 on the selected line
- BCD to 7-segment
- Decoder driving the segments of a display
- Address decoding
- Selects one memory chip from the address lines
Example
3-to-8 decoder: the input 101 (decimal 5) makes output line D5 = 1 and all others 0. 8-to-3 encoder: if input line D6 is active, the output is 110. A priority encoder is used when more than one input may be active; it encodes the highest-numbered one.
Key terms
- Combinational circuit
- A circuit whose output depends only on present inputs
- Half adder
- Adds two bits giving sum and carry
- Full adder
- Adds two bits and a carry-in
- Borrow
- Bit passed to the next stage in subtraction
- Ripple-carry adder
- Parallel adder in which the carry passes stage by stage
- Multiplexer
- Selects one of many inputs to a single output
- Demultiplexer
- Sends one input to one of many outputs
- Encoder
- Converts an active input line into a binary code
- Decoder
- Converts a binary code into one active output line
Quick revision
- Half adder: S = A ⊕ B, C = AB; full adder: S = A ⊕ B ⊕ Cin, Cout = AB + Cin(A ⊕ B).
- Half subtractor: D = A ⊕ B, Bo = A′B; full subtractor uses Bin.
- Parallel adder: carry ripples; look-ahead uses G and P; adder/subtractor uses XOR with M.
- 2ⁿ-to-1 MUX has n select lines; DEMUX is the reverse.
- n-variable function with a 2ⁿ⁻¹-to-1 MUX; decoder + OR gate for Σm.
- Encoder: 2ⁿ → n; decoder: n → 2ⁿ.
Important exam questions
Practice questions written to the PTU exam pattern for this unit's syllabus: short answers (Section A style) and long answers (Sections B and C style).
Short-answer questions
- Q1.Write the equations of a half adder.
- Q2.Why is a full adder needed?
- Q3.What is a borrow? Write the equation for the half-subtractor borrow.
- Q4.What is the drawback of a ripple-carry adder?
- Q5.How does a binary adder/subtractor perform subtraction?
- Q6.How many select lines does an 8-to-1 multiplexer have?
- Q7.Differentiate between MUX and DEMUX.
- Q8.Why is a decoder called a minterm generator?
- Q9.What is a priority encoder?
- Q10.Design a 2-to-4 decoder.
Long-answer questions
- Q1.Design a full adder with truth table, K-maps and logic diagram.
- Q2.Design a full subtractor with truth table and logic diagram.
- Q3.Explain the 4-bit parallel adder and the binary adder/subtractor.
- Q4.Explain the 4-to-1 multiplexer with truth table and circuit.
- Q5.Implement F(A, B, C) = Σm(1, 2, 6, 7) using a 4-to-1 multiplexer and using a decoder.
- Q6.Explain the 4-to-2 encoder and the 2-to-4 decoder.
Stuck on this unit?
Message SBS on WhatsApp for help with Computer Architecture, or to ask about studying BCA at Synetic.
