Topic 5

Combination Circuit

1
 What is Combinational Circuit?

• Combinational Circuit
– A digital circuit whose output depends only upon the present
combination of its inputs
– Output changes only when any of the inputs changes
• As oppose to Sequential Circuit which is
– A digital circuit whose output depends not only upon the present
input values, but also the history of input and output values
– Have feedbacks from outputs
– More complicated and difficult to analyze
• Typical modern digital circuit includes both combination
and sequential circuits

2
 How to Design Combinational Circuits?
Step Description

Step 1 Capture the Create a truth table or equations, whichever is

function most natural for the given problem, to describe
the desired behavior of the combinational logic.
Step 2 Convert to This step is only necessary if you captured the
equations function using a truth table instead of equations.
Create an equation for each output by ORing all the
minterms for that output. Simplify the equations if
desired.
Step 3 Implement For each output, create a circuit corresponding
as a logic to the output’s equation. (Sharing gates among
circuit multiple outputs is OK optionally.)

3
 Example: Count Number of 1s
• Problem: Output in binary the
number of 1s on three inputs
(e.g., 3 people are voting)
• E.g.: 01001 10110 00000
– Step 1: Capture the function
• Truth table or equation?
– Truth table is straightforward

a
– Step 2: Convert to equation b
a c
• y = a’bc + ab’c + abc’ + abc
Class
• z = a’b’c + a’bc’ + ab’c’ + abc
b
c a
b
Derivation a
b
c
yc
Class
a
z

b
– Step 3: Implement as a gate- a Derivation
c

based circuit b a
b
c
4
 Example: Three 1s Detector
• Problem: Detect three consecutive 1s
(which represent certain event) among
8 inputs: abcdefgh
– 00011101  1 10101011  0
11110000  1 a abc
b
– Step 1: Capture the function c
bcd
a
• Truth table or equation? d
– Truth table too big: 2^8=256 rows cde
– Equation: create terms for each e y
possible case of three consecutive 1s def
f
• y = abc + bcd + cde + def + efg + fgh
efg
– Step 2: Convert to equation -- g
already done fgh
h
– Step 3: Implement as a gate-
based circuit

5
 Combinational Building Blocks

• Special combinational circuits - combinational building

blocks
– Implement frequently used fundamental functions
– To build bigger combinational circuits
• We will learn
– Multiplexor (MUX)
– Half adder
– Full adder
– Carry-ripple adder
– Encoder/Decoder
– Buffer
– Tri-state buffer

6
 Multiplexor (Mux)
• Mux: A popular combinational building block
– Like a railyard switch

– Routes one of its N data inputs to its one output,

based on binary value of select inputs
• 2 inputs  needs 1 select bit ( 2 different
combinations) to select which input
2×1 2×1 2×1
to connect to the output
i0 i0 i0
• 4 inputs  2 select bits d d d
i1 i1 i1
• 8 inputs  3 select bits s0 s0 s0
select input 0 1
• N inputs  log2(N) select bits
2 to 1 or 2 by 1 or 2x1 mux
 Mux Internal Design
s0 i0 i1 d
0 0 0 0

Connect i0 to d 0 0 1 0
d = s0’ i0 i1’+ s0’ i0 i1+
when s0 is 0, 0 1 0 1
0 1 1 1
s0 i0’ i1+ s0 i0 i1
otherwise
1 0 0 0 = s0’ i0 + s0 i1
connect i1 to d
1 0 1 1
1 1 0 0
1 1 1 1

i0
2×1
d
i0 i1
d
i1
s0

s0
2x1 mux 8
 Mux Internal Design

i0
4×1
i1 i0
d i1
i2 d
i2
i3
i3
s1 s0

s1 s0

4x1 mux

9
 4-bit 2x1 Mux
2×1
a3 i0 Simplifying
d
b3 i1 notation:
s0
4-bit 4
2×1 4 C
a2 i0 2x1
d A I0 4
b2 i1
s0 4 D C is short
B I1 for
2 1
a1 i0 × s0
d
b1 i1
s0 c3

2×1 s0 c2
a0 i0
d c1
b0 i1
s0
s0 c0

• Ex: Two 4-bit inputs, A (a3 a2 a1 a0), and B (b3 b2 b1 b0)

– 4-bit 2x1 mux (just four 2x1 muxes sharing a select line) can select
between A or B
• Width of input channels may be any, 8, 18, 32, 64, …
10
 N-bit Mux Example

• Four possible display items

– Temperature (T), Average miles-per-gallon (A), Instantaneous mpg (I), and
Miles remaining (M) -- each is 8-bits wide
– Choose which to display using two inputs x and y
– Use 8-bit 4x1 mux

11
 Half Adder
• Derive Boolean functions (sum-of-
minterms) from the truth table for
A Sum both outputs
Half-Adder
B Carry Sum = A’B + AB’ = m1 + m2 = Σ (1, 2)
= (A+B)(A’+B’) = M0•M3 = Π (0, 3)

• Addition of two single bits A, B Carry = AB = m3

• Based on the operations it performs, = (A+B)(A+B’)(A’+B)
a truth table can be built = M0•M1•M2
= Π (0, 1, 2)
A B Sum Carry
0 0 0 0
0 1
Class
1 0 A
Sum
1 Derivation
0 1 0 B
1 1 0 1
Carry
12
 Application of XOR in Half-Adder
• Half adder
Sum = A’B + AB’ = A  B
Carry = AB

A
Sum Sum
A B
B
Carry
Carry

13
 Full Adder
• Derive minterm/Maxterm
A Sum expressions from the truth table for
B Full-Adder both outputs
C Carry Sum = ?

• Based on the operations it performs,

a truth table can be built Carry = ?

A B C Sum Carry
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0 Logic Circuit?
1 0 1
1 1 0
1 1 1 1 1

14
 Full Adder
A Sum
B Full-Adder
C Carry
A B C Sum Carry
0 0 0 0 0
0 0 1 1 0
0 1 0 1 0
Sum
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 = A’B’C + A’BC’ + AB’C’ + ABC Carry

=  m(1, 2, 4, 7)
Carry = A’BC + AB’C + ABC’ + ABC
=  m(3, 5, 6, 7)
Notice the circuit draw convention
15
 Application of XOR in Full Adder
• Full adder
Sum = A’B’C + A’BC’ + AB’C’ + ABC
= A’(B’C + BC’) + A(B’C’ + BC)
= A’(B  C) + A(B  C)’ (let B  C = D)
= A’D + AD’ Class
=AD
=ABC
Derivation
Carry = A’BC + AB’C + ABC’ + ABC
= (A’B+AB’) C + AB (C’+C)
= (A  B)C + AB

16
Application of XOR in Full Adder
A
B sum

carry
sum
C

A sum
H.A. H.A.
B
carry

carry
C

17
 Multi-bit Number Addition

Carry: 0 1 0 0 0 Carry: 0 0 0 0 0
A: 0100 =4 + 0 1 1 0 = +6
+ B: 0101 =5 + 0 0 0 1 = +1
Sum: 1001 =9 Sum: 0 1 1 1 = +7

The carry output (C_out) from previous

stage. It’s also the carry input (C_in) to
the present stage
Without previous stage,
Carry: 1 1 0 0 0 carry input should
A: 1 1 0 0 = 12 always be 0
+ B: 1 1 0 1 = 13
Sum: 1 1 0 0 1 = 25

Overflow! Need one more bit to hold Operation may be performed by

a number bigger than 2n-1 = 15 a full adder
18
 Carry-Ripple Adder
• carry-ripple adder
– 4-bit adder: Adds two 4-bit numbers, generates 5-bit output
• 5-bit output can be considered 4-bit “sum” plus 1-bit “carry out”
– Can easily build any size adder
carries: c3 c2 c1 cin
B: b3 b2 b1 b0
A: + a3 a2 a1 a0
cout s3 s2 s1 s0

a3 b3 a2 b2 a1 b1 a0 b0 ci
A B
a b ci a b ci a b ci a b ci a3 a2 a1 a0 b3 b2 b1 b0
FA FA FA FA 4-bit adder ci
co s co s co s co s cout s3 s2 s1 s0
c3 c2 c1
Cout S
cout s3 s2 s1 s0
(a) (b)

19
 Two’s Complement Subtractor
A B
• Using two’s complement representation
A – B = A + (-B) N-bit
= A + (two’s complement of B)
= A + invert_bits(B) + 1
A B 1
• So build subtractor using adder by Cout Adder cin
inverting B’s bits, and setting carry in to 1
S

A3 B3 A2 B2 A1 B1 A0 B0

Cout FA C3 FA C2 FA C1 FA Cin

S3 S2 S1 S0
Or 20
Lookahead Adder
 4-Bit 2’s Complement Adder
A3 B3 A2 B2 A1 B1 A0 B0

C_out FA C3 FA C2 FA C1 FA C0
0

S3 S2 S1 S0
Overflow

21
 4-Bit 2’s Complement Subtractor
A3 B3 A2 B2 A1 B1 A0 B0

Cout FA C3 FA C2 FA C1 FA C0
1

S3 S2 S1 S0
Overflow

22
 Arithmetic-Logic Unit: ALU

• ALU: Component that

can perform any of
various arithmetic (add,
subtract, increment, etc.)
and logic (AND, OR,
etc.) operations, based
on control inputs
• Key component in
computer

23
 Encoder
• Each input is given a binary code

Inputs Outputs
D0 D1 D2 D3 D4 D5 D6 D7 x y z
1 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 1
0 0 1 0 0 0 0 0 0 1 0
0 0 0 1 0 0 0 0 0 1 1
0 0 0 0 1 0 0 0 1 0 0
0 0 0 0 0 1 0 0 1 0 1
0 0 0 0 0 0 1 0 1 1 0
0 0 0 0 0 0 0 1 1 1 1

24
 Decoder
• Decoder: Popular combinational
logic building block, in addition to
d0 1 d0 0 d0 0 d0 0
logic gates
0 i0 d1 0 1 i0 d1 1 0 i0 d1 0 1 i0 d1 0
– Converts input binary number to
0 i1 d2 0 0 i1 d2 0 1 i1 d2 1 1 i1 d2 0
one high output
d3 0 d3 0 d3 0 d3 1
• 2-input decoder: four possible
input binary numbers
– So has four outputs, one for each d0 0
i1’i0’ d0
possible input binary number 1 i0 d1 0
• Internal design i1’i0 d1 1 i1 d2 0
– AND gate for each output to e d3 1
i1i0’ d2
detect input combination 1
• Decoder with enable e i1i0 d3 d0 0
– Outputs all 0 if e=0 1 i0 d1 0
– Regular behavior if e=1 1 i1 d2 0

• n-input decoder: 2n outputs e d3 0

i1 i0
0
25
 Decoder
• For any input combination, only one of the outputs is turned on

Inputs Outputs
x y z D0 D1 D2 D3 D4 D5 D6 D7
0 0 0 1 0 0 0 0 0 0 0
0 0 1 0 1 0 0 0 0 0 0
0 1 0 0 0 1 0 0 0 0 0
0 1 1 0 0 0 1 0 0 0 0
1 0 0 0 0 0 0 1 0 0 0
1 0 1 0 0 0 0 0 1 0 0
1 1 0 0 0 0 0 0 0 1 0
1 1 1 0 0 0 0 0 0 0 1

26
Gate-Level Implementation of 3×8 Decoder
x

D0 = x’y’z’
y
D1 = x’y’z
z
D2 = x’yz’

D3 = x’yz Minterm
Generator
D4 = xy’z’

D5 = xy’z

D6 = xyz’

D7 = xyz
27
 Implementation of Any Circuit with a Decoder
• P (A, B, C) = Σ m(1, 2, 3, 5) and Q (A, B, C) = Σ m(0, 4, 5, 6)
• Since there are three inputs and total of 8 minterms, we can
implement the circuits with a 3-to-8-line decoder

0
A 22 1
P
2
B 21 3×8 Decoder 3
4
C 5
20
6 Q
7

28
 Decoder Example
• New Year’s Eve Countdown Display
– Microprocessor counts from 10 down to 0 in binary
– Want to illuminate one of 11 lights for each binary number
– May use a 4x16 decoder
• 5 outputs unused
3
21540 0
Happy
1
00 01 New Year
i0 d0
10 010
Microprocessor
i1 d1 1
010 i2 d2 100 2
00 i3 d3 100 3
d4 001 4
d5 010 5

…
e
d9
d10 9
4x16 d11 10
…
…
d15
decoder 29
 Buffer and Three State (Tri-state) Buffer
• A buffer is a one directional transmission logic device
– somewhat like a NOT gate without complementing the binary value
– amplify the driving capability of a signal
– insert delay
– Protect input from output

• A three state (Tri-state) buffer can have three different output values,
controlled by an enable bit
– 0 (off) when B = 1, A = 0;
– 1 (on) when B = 1, A = 1;
– Z (high impedance, no voltage) when B = 0, A = x;

30
 Tri-state Buffers
• Different types of tri-state buffers

31
Tri-state Buffer Application – Bidirectional I/O Port

rcv_data

inbound_data
32

Device
32 32

reg_to_bus data_to_from_bus

send_data

32
Applications of Decoders and Tri-state Buffers
• Based on the control signals, only one path will be connected

Data1 Data2 Data8

33
 Alternative Implementation of Datapath
Control
• Based on the control signals, only one path will be connected

Data1 Data2 Data8

May be replaced with ?

34