Unit 2 of 4 · BCA Sem 1

Unit 2: Combinational logic circuits

Computer Architecture notes · PTU syllabus (UGCC2502)

6 min read7 topics16 exam questions
On this page
  1. Unit summary
  2. Combinational circuits
  3. Half adder and full adder
  4. Half subtractor and full subtractor
  5. Parallel binary adder and binary adder/subtractor
  6. Multiplexers and demultiplexers
  7. Implementing Boolean equations using MUX and DEMUX
  8. Encoders and decoders
  9. Key terms
  10. Quick revision
  11. Important questions

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
1

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.

ComparisonCombinational vs sequential circuits
Combinational
Sequential

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

ProcessDesign procedure for a combinational circuit
  1. 1State the problem and list inputs and outputs
  2. 2Write the truth table
  3. 3Obtain simplified Boolean expressions with K-maps
  4. 4Draw the logic diagram
  5. 5Verify with the truth table
ClassificationCommon combinational circuits
Combinational circuits
  • 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.

2

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).

ABSum SCarry C
0000
0110
1010
1101
Key formulasHalf adder equations
  • Sum

    S = A ⊕ B

  • Carry

    C = A · B

Logic circuitHalf adder
ABX1A1SumCarry
  • 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.

ABCinSumCout
00000
00110
01010
01101
10010
10101
11001
11111
Key formulasFull adder equations
  • Sum

    S = A ⊕ B ⊕ Cin

  • Carry-out

    Cout = AB + Cin (A ⊕ B) = AB + BCin + ACin

Karnaugh mapCout = Σm(3, 5, 6, 7) = AB + BCin + ACin (variables A, B, Cin)
ABCin00011110010010312040517161AB (m6, m7)B·Cin (m3, m7)A·Cin (m5, m7)
Logic circuitFull adder built from two half adders and an OR gate
ABCinX1X2A1A2O1SumCout
ComparisonHalf adder vs full adder
Half adder
Full adder

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).

3

Topic 3

Half subtractor and full subtractor

Half subtractor

A half subtractor computes A − B and produces a Difference (D) and a Borrow (Bo).

ABDifference DBorrow Bo
0000
0111
1010
1100
Key formulasHalf subtractor equations
  • Difference

    D = A ⊕ B

  • Borrow

    Bo = A′B

Logic circuitHalf subtractor
ABX1N1A1DifferenceBorrow

Full subtractor

A full subtractor computes A − B − Bin (borrow-in).

ABBinDifferenceBorrow-out
00000
00111
01011
01101
10010
10100
11000
11111
Key formulasFull subtractor equations
  • Difference

    D = A ⊕ B ⊕ Bin

  • Borrow-out

    Bout = A′B + (A ⊕ B)′ Bin = A′B + A′Bin + B·Bin

Karnaugh mapBout = Σm(1, 2, 3, 7) = A′B + A′Bin + B·Bin (variables A, B, Bin)
ABBin00011110010011312140507160A′B (m2, m3)A′·Bin (m1, m3)B·Bin (m3, m7)
Logic circuitFull subtractor
ABBinX1X2N1A1N2A2O1DifferenceBorrow-out
ComparisonAdder vs subtractor equations
Adder
Subtractor

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′.

4

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.

Logic circuit4-bit parallel (ripple-carry) adder
A0B0C0A1B1A2B2A3B3FA0A0B0C0S0C1FA1A1B1C1S1C2FA2A2B2C2S2C3FA3A3B3C3S3C4S0S1S2S3C4

Each box is a full adder with inputs A, B, carry-in and outputs sum and carry-out

Key termsCarry propagation
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.

Logic circuit4-bit adder/subtractor (two stages shown)
A0B0A1B1MX0X1FA0A0X0MS0C1FA1A1X1C1S1C2S0S1C2

When M = 1 the XOR gates complement B and the carry-in M = 1 adds the 1 needed for 2's complement

Key termsOverflow and control
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)
5

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.

ComparisonMultiplexer sizes
Data inputs
Select lines

2-to-1

2

1

4-to-1

4

2

8-to-1

8

3

16-to-1

16

4

Logic circuit2-to-1 multiplexer (Y = S′·I0 + S·I1)
I0I1SNSA1A2O1Y
S1S0Output Y
00I0
01I1
10I2
11I3
Key formulas4-to-1 multiplexer
  • Output

    Y = S1′S0′ I0 + S1′S0 I1 + S1S0′ I2 + S1S0 I3

Logic circuit4-to-1 multiplexer
I0I1I2I3S1S0N1N0A0A1A2A3O1Y
ClassificationUses of a multiplexer
Multiplexer
  • 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.

Logic circuit1-to-4 demultiplexer (data D, select S1 S0)
DS1S0N1N0A0A1A2A3Y0Y1Y2Y3
ComparisonMUX vs DEMUX
Multiplexer
Demultiplexer

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.

6

Topic 6

Implementing Boolean equations using MUX and DEMUX

Using a multiplexer

ProcessImplementing an n-variable function with a 2ⁿ⁻¹-to-1 MUX
  1. 1Choose n − 1 variables as select lines
  2. 2Make a table with one column per select combination
  3. 3Express the output for each column in terms of the remaining variable (0, 1, C or C′)
  4. 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 ABMintermsF in terms of CData input
00m0, m1CI0 = C
01m2, m3C′I1 = C′
10m4, m50I2 = 0
11m6, m71I3 = 1
Logic circuitF = Σm(1, 2, 6, 7) with a 4-to-1 MUX
CGNDVccABNC4-to-1 MUXCNCGNDVccABYF

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.
Logic circuitF = Σm(1, 2, 6, 7) with a 3-to-8 decoder and an OR gate
ABC3-to-8 decoderABCm1m2m6m7O1F

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.

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.

D3D2D1D0A1A0
000100
001001
010010
100011
Key formulas4-to-2 encoder equations
  • A1

    A1 = D2 + D3

  • A0

    A0 = D1 + D3

Logic circuit4-to-2 encoder
D0D1D2D3O1O2A1A0
Key termsEncoder variants
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
D3D2D1D0A1A0V
0000XX0
0001001
001X011
01XX101
1XXX111

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.

A1A0Y0Y1Y2Y3
001000
010100
100010
110001
Logic circuit2-to-4 decoder
A1A0N1N0G0G1G2G3Y0Y1Y2Y3
ComparisonEncoder vs decoder
Encoder
Decoder

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

Key termsDecoder points
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

  1. Q1.Write the equations of a half adder.
  2. Q2.Why is a full adder needed?
  3. Q3.What is a borrow? Write the equation for the half-subtractor borrow.
  4. Q4.What is the drawback of a ripple-carry adder?
  5. Q5.How does a binary adder/subtractor perform subtraction?
  6. Q6.How many select lines does an 8-to-1 multiplexer have?
  7. Q7.Differentiate between MUX and DEMUX.
  8. Q8.Why is a decoder called a minterm generator?
  9. Q9.What is a priority encoder?
  10. Q10.Design a 2-to-4 decoder.

Long-answer questions

  1. Q1.Design a full adder with truth table, K-maps and logic diagram.
  2. Q2.Design a full subtractor with truth table and logic diagram.
  3. Q3.Explain the 4-bit parallel adder and the binary adder/subtractor.
  4. Q4.Explain the 4-to-1 multiplexer with truth table and circuit.
  5. Q5.Implement F(A, B, C) = Σm(1, 2, 6, 7) using a 4-to-1 multiplexer and using a decoder.
  6. 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.

WhatsApp us