Combinational Logic

Combinational Logic
 Combinational vs. Sequential Logic
In Out
Logic Logic
In Out
Circuit Circuit

State

(a) Combinational (b) Sequential

Output = f(In) Output = f(In, Previous In)

 Design Procedure

The design of combinational circuit starts from a specification of the

problem and culminates in a logic diagram or set of Boolean
equations from which the logic diagram can be obtained. The
procedure involves the following steps:

1. From the specifications of the circuit, determine the required

number of inputs and outputs, and assign a letter symbol to each.
2. Derive the truth table that defines the required relation ship
between inputs and outputs.
3. Obtain the simplified Boolean functions of each outputs as
function of the input variables.
4. Draw the logic diagram.
5. Verify the correctness of the design.
 C
X

Using NAND Gates

FULL Adder
 Half Subtractor
 Subtracting a single-bit binary value Y from anther X (I.e. X -Y ) produces a difference bit
D and a borrow out bit B-out.
 This operation is called half subtraction and the circuit to realize it is called a half
subtractor.
Half Subtractor Truth Table D(X,Y) = S (1,2)
Inputs Outputs D = X’Y + XY’
X Y D B-out D = X Y
0 0 0 0
0 1 1 1 B-out(x, y, C-in) = S (1)
1 0 1 0 B-out = X’Y
1 1 0 0

X Difference
D
Y
X Half D
Y Subtractor B-OUT B-out
 Full Subtractor
 Subtracting two single-bit binary values, Y, B-in from a single-
Difference D X
bit value X produces a difference bit D and a borrow out B-out
bit. This is called full subtraction. XY
B-in 00 01 11 10
0 2 6 4
0 1 1
Full Subtractor Truth Table 1 3 7 5
Inputs Outputs 1 1 1 B-in

X Y B-in D B-out Y
0 0 0 0 0 S = X’Y’(B-in) + XY’(B-in)’ + XY’(B-in)’ + XY(B-in)
S = X  Y  (C-in)
0 0 1 1 1
0 1 0 1 1 Borrow B-out X
0 1 1 0 1 XY
1 0 0 1 0 B-in 00 01 11 10
0 2 6 4
1 0 1 0 0 0 1
1 1 0 0 0 1 3 7 5
1 1 1 1 B-in
1 1 1 1 1
Y
S(X,Y, C-in) = S (1,2,4,7)
B-out = X’Y + X’(B-in) + Y(B-in)
C-out(x, y, C-in) = S (1,2,3,7)
Full Subtractor
 Parallel Binary Adders
 An n-bit adder used to add two n-bit binary numbers can built by connecting in series n
full adders.
 Each full adder represents a bit position j (from 0 to n-1).
 Each carry out C-out from a full adder at position j is connected to the
carry in C-in of the full adder at the higher position j+1.
 The output of a full adder at position j is given by:
Sj = Xj  Yj  Cj
Cj+1 = Xj .Yj + Xj . Cj + Y . Cj
 In the expression of the sum Cj must be generated by the full adder at the lower position
j-1.
 The propagation delay in each full adder to produce the carry is equal to two gate delays
= 2D
 Since the generation of the sum requires the propagation of the carry from the lowest
position to the highest position , the total propagation delay of the adder is approximately:
Total Propagation delay = 2 nD
 4-bit Ripple Carry Adder
Inputs to be added
Adds two 4-bit numbers:
X3X2X1X0 Y3Y2Y1Y0
X = X3 X2 X1 X0
Y = Y3 Y2 Y1 Y0
producing the sum S = S3 S2 S1 S0 ,
C-out = C4 from the most significant 4-bit
C4 C-out C-in C0 =0
position j=3 Adder

Total Propagation delay = 2 nD = 8D S3 S2 S1 S0

or 8 gate delays Sum Output

Data inputs to be added

X3 Y3 X2 Y2 X1 Y1 X0 Y0

Full C3 Full C2 Full C1 Full

C4 C-out C-in C-out C-in C-out C-in C-out C-in C0 =0
Adder Adder Adder Adder

S3 S2 S1 S0
Sum output
 An example of 4-bit addition
1
 Let’s try1our initial
1 0
example: 1 1
A=1011 0
(eleven), 1
B=1110
(fourteen).
0
1 1 0

1 1 0 0 1

1. Fill in all the inputs, including CI=0

2. The circuit produces C1 and S0 (1 + 0 + 0 = 01)
3. Use C1 to find C2 and S1 (1 + 1 + 0 = 10)
4. Use C2 to compute C3 and S2 (0 + 1 + 1 = 10)
5. Use C3 to compute CO and S3 (1 + 1 + 1 = 11)
The final answer is 11001 (twenty-five).

21
 Binary Subtractor
 The subtrcation A – B can be done by taking the 2’s
complement of B and adding it to A because A- B = A
+ (-B)
 It means if we use the inveters to make 1’s
complement of B (connecting each Bi to an inverter)
and then add 1 to the least significant bit (by setting
carry C0 to 1) of binary adder, then we can make a
binary subtractor.
Binary Subtractor
 Adder Subtractor
 The addition and subtraction can be combined into one
circuit with one common binary adder (see next slide).
 The mode M controls the operation. When M=0 the
circuit is an adder when M=1 the circuit is subtractor.
It can be don by using exclusive-OR for each Bi and
M. Note that 1 ⊕ x = x’ and 0 ⊕ x = x
Adder Subtractor
 Carry Look-Ahead Adders
 The disadvantage of the ripple carry adder is that the
propagation delay of adder (2 nD ) increases as the size of
the adder, n is increased due to the carry ripple through
all the full adders.
 Carry look-ahead adders use a different method to create
the needed carry bits for each full adder with a lower
constant delay equal to three gate delays.
Pi= Ai XOR Bi
Gi=AiBi
Si =Pi XOR Ci
Ci+1 = Gi+Pici
 Magnitude Comparator
 It is a combinational circuit that compares to numbers
and determines their relative magnitude
 The output of comparator is usually 3 binary variables
indicating: A>B
A=B
A<B
1-bit Magnitude Comparator
2-bit magnitude comparator
2-bit magnitude comparator
4-bit magnitude comparator
 Algorithm
 Algorithm -> logic
 A = A3A2A1A0 ; B = B3B2B1B0
 A=B if A3=B3, A2=B2, A1=B1and A1=B1
 Test each bit:
 equality: xi= AiBi+Ai'Bi'
 (A=B) = x3x2x1x0

 More difficult to test less than/greater than

 (A>B) = A3B3'+x3A2B2'+x3x2A1B1'+x3x2x1 A0B0'
 (A<B) = A3'B3+x3A2'B2+x3x2A1'B1+x3x2x1 A0'B0
 Start comparisons from high-order bits
 Implementation
 xi = (AiBi'+Ai'Bi)’
 Multiplexers
 Multiplexing means sharing
 Example –when serval peripheral device share a single
transmission line to communicate with computer.
 Each device is allocated brief time to send or receive data.
 At given time one & only one device using this line.
 Logic circuit –that accepts serval data inputs and allows
only one of them at a time to get through the output.
 Usually there are 2n input lines and n selection lines whose
bit combinations determine which input line is selected
 For example for 2-to-1 multiplexer if selection S is zero
then I0 has the path to output and if S is one I1 has the path
to output
Functional diagram of MUX

39
2-to-1 multiplexer
4-to-1 multiplexer
Symbol of Multiplexer
Output Waveforms in relation with the Data-Input and Data-Select
waveforms - 4-input MUX

The binary state of the data-

select
inputs during each interval
determines which data input
is selected. Here the data-
select
inputs go through a repetitive
binary sequence
00,01,10,11,00,
and so on. The resulting
output
waveform is shown.

43
8-input multiplexer

44
8-to-1 multiplexer from Smaller
MUX
16-to-1 multiplexer from 4:1 mux
Design 8 to 1 Multiplexer using 2 to
1 multiplexer.
LOGIC FUNCTION GENERATION USING MUX

Exercise 1:
Implement the logic circuit function specified in the table given below by using 74LS151
8-input data selector/multiplexer.

Input Output

A2 A1 A0 Y
0 0 0 0 0
0 0 1 1 1
0 1 0 0 2
0 1 1 1 3
1 0 0 0 4
1 0 1 1 5
1 1 0 1 6
1 1 1 0 7 48
Solution :

49
Exercise 2:
Implement the logic circuit function F= A XOR B XOR C by 8-input
data selector/multiplexer.
 LOGIC FUNCTION GENERATION USING MUX-Method

 An efficient method for implementing a Boolean function of

n variables with a MUX that has n-1 selection inputs and 2 n-1
data inputs is given below:
 List the Boolean function in a truth table
 Apply the first n-1 variables in the table to the selection inputs
of the MUX.
 For each combination of the selection variables, evaluate the
output as a function of the last variable. This function can be
0,1, the variable, or the complement of the variable. Apply
these values to the data inputs in the proper order.

52
 LOGIC FUNCTION GENERATION USING MUX-Example 2
Implement the Boolean function F=x’y’z +x’yz’ + xyz’ + xyz
using a suitable MUX

0
1

2
3

54
 LOGIC FUNCTION GENERATION USING MUX-Example 2

 The two variables x and y are applied to the selection lines in that
order; x is connected to the S1 input and y to the S0 input.
 The values for the data input lines are determined from the truth
table of the function
 For ex., when xy=00, output F is equal to z because F=0 when z=0
and F=1 when z=1. This requires that variable z is applied to the data
input 0

55
 LOGIC FUNCTION GENERATION USING MUX-Example 3
Implement the Boolean function F=A’B’C’D+A’B’CD+A’BC’D’
+AB’CD+ABC’D’+ABC’D+ABCD’+ABCD using a suitable MUX

0
1
2
3
4
5
6
7 58
Design the function F(a,b,c,d) = ∑m (0,3,6,7,11,14,15)
using 4 to 1 Multiplexer.
Design the function F(a,b,c,d) = ∑m
(0,3,6,7,11,14,15) using 4 to 1 Multiplexer.
 DEMULTIPLEXERS
A DEMULTIPLEXER (DEMUX) basically reverses the
multiplexing function. It takes data from one line and
distributes them to a given number of output lines. For
this reason, the demultiplexers is also known as a data
distributor.
A multiplexer takes several inputs and transmits one of
them to the output.
A demultiplexer (DEMUX) performs the reverse
operation ; it takes a single input and distributes it over
several outputs.

It transmits the same data to different

destination 61
 General demultiplexer
Functional diagram:- The large arrow indicates one or more
lines. The select i/p code determines to
which output the DATA input will be
transmitted

In other words, the demultiplexer

takes one data input source and
selectively distributes it to 1 of N
output channels just like
multiposition switch.

62
1-line-to-4-line demultiplexer.
1-line-to-4-line demultiplexer.

64
The serial data input waveform (Data in) and data select inputs (So and S1)
and
the corresponding data output waveforms (D0 through D3) are shown
below

65
1-line- to-8 line demultiplexer

66
Implementation of Full Subtractor
Using 1-to-8 DEMUX

From the above table, the full

subtractor output D can be written
as
D = f (A, B, C)
= ∑m (1, 2, 4, 7)
And the borrow output can be
expressed as
Bout = F (A, B, C) = ∑m (1, 2, 3, 7)
Design half adder using 1 to 4 De-
multiplexer.
Implementation of Full Subtractor
Using 1-to-8 DEMUX
Implementation of half adder Using
1-to-4 DEMUX
 Decoder

A decoder is a multiple-input, multiple-output logic circuit that converts coded

inputs into coded outputs, where the input and output codes are different; e.g. n-
to-2n, BCD decoders
2-to-4 Binary Decoder
3-to-8 Binary Decoder
2 line to 4 line decoder with NAND
gates (Active law)
Major application of Decoder
 Decoder is use to implement any combinational cicuits ( fn )
For example the truth table for full adder is s (x,y,z) = ∑ ( 1,2,4,7)
and C(x,y,z)= ∑ (3,5,6,7). The implementation with decoder is:
 The BCD-to-Decimal Decoder
 The BCD-to-
decimal converts
each BCD code
into one of ten
possible decimal
digit indications.
 Called  4-line-to-
10-line decoder or 1-
of-10 decoder
 THE 8421 BCD CODE
 BCD stands for Binary-Coded Decimal.

 A BCD number is a four-bit binary group that

represents one of the ten decimal digits 0 through 9.

Example:
Decimal number 4926 4 9 2 6

8421 BCD coded number 0100 1001 0010

0110
 BCD-to-Seven-Segment Decoder
 Specification
 Digital readouts on many digital products often use LED seven-
segment displays.
 Each digit is created by lighting the appropriate segments. The
segments are labeled a,b,c,d,e,f,g
 The decoder takes a BCD input and outputs the correct code
for the seven-segment display.

Copyright 2009 - Joanne DeGroat, ECE, OSU 9/15/09 - L12 Combinational

86
Logic Design
 Specification
 Input: A 4-bit binary value that is a BCD coded input.
 Outputs: 7 bits, a through g for each of the segments of the
display.
 Operation: Decode the input to activate the correct
segments.

Copyright 2009 - Joanne DeGroat, ECE, OSU 9/15/09 - L12 Combinational

87
Logic Design
 Formulation
 Construct a truth table

Copyright 2009 - Joanne DeGroat, ECE, OSU 9/15/09 - L12 Combinational

88
Logic Design
7-Segment LED Display Operation
Inputs
7-segment code
a
7-segment
b & c inputsdisplay
active H +5V
Note
readsthat
therefore
decimal
inputs 1are L b
(segments
segments
“active-LOW”
bb &
& cc L c
lightare
on lit)
display H
H
H
H
g

Limiting resistors Common anode

Cathode terminals (a thru g)

7-segment LED display

(common anode)
 DECODERS: BCD TO
7-SEGMENT DECODER/DRIVER
BCD input Decimal output
LED
01
0010
1
BCD-to-
7-Segment
Decoder/
Driver

• Electronic decoders are available in IC form.

• This decoder translates from BCD to decimal.
• Decimals are shown on an 7-segment LED displa
• This IC also drives the 7-segment LED display.
BCD-TO-SEV EN SEGMENT DECODER DRIVER

V+

abcdef g .
74LS47
A3 g
A2 f
A1 e
A0 d
c
b
a
5V
test
RBI RBO
 ENCODERS AND DECODERS
A0 O0 A0 O0
A1 O1 A1 O1
A2 O2 A2 O2
A3 ENCODER DECODER O3
A4 O4
A5 O5
A6 O6
A7 O7

ONLY ONE INPUT BINARY CODE INPUT

ACTIVATED AT A TIME
BINARY CODE ONLY ONE OUTPUT
OUTPUT ACTIVATED AT A TIME

ENCODER- a digital circuit that produces a binary output code

depending on which of its inputs are activated.
DECODER- a digital circuit that converts an input binary code
into a single numeric output.
 ELECTRONIC ENCODER -
DECIMAL TO BCD
BCD output
Decimal input
00
1101
0
7
Decimal
5 to
BCD
3 Encoder
0

• Encoders are available in IC form.

• This encoder translates from
decimal input to BCD output.
 The Decimal-to-BCD Encoder
 It has 10 inputs and 4
outputs corresponding
to the BCD code.
 A3 = 8+9
 A2 = 4+5+6+7
 A1 = 2+3+6+7
 A0 = 1+3+5+7+9
The Decimal-to-BCD Encoder

NOTE: A 0-digit input is not needed because the

BCD outputs are all LOW when there are no HIGH
input.
The Decimal-to-BCD Encoder (The
Application)
DesignBCD Adder. Using this 4-bit
parallel adder design BCD adder.
 When the sum of two digits is less than or equal to 9 then the
ordinary 4-bit adder can be used
 But if the sum of two digits is greater than 9 then a
correction must be added “I.e adding 0110”
 We need to design a circuit that is capable of doing the
correct addition
DesignBCD Adder. Using this 4-bit
parallel adder design BCD adder.
 The cases where the sum of two 4-bit numbers is greater
than 9 are in the following table:

S4 S3 S2 S1 S0
0 1 0 1 0 10
0 1 0 1 1 11
0 1 1 0 0 12
0 1 1 0 1 13
0 1 1 1 0 14
0 1 1 1 1 15
1 0 0 0 0 16
1 0 0 0 1 17
1 0 0 1 0 18
DesignBCD Adder. Using this 4-bit
parallel adder design BCD adder.
 Whenever S4=1 (sums greater than 15)
 Whenever S3=1 and either S2 or S1 or both are 1 (sums 10 to
15)
 The previous table can be expressed as:
X = S4 + S3 ( S2 + S1)
So, whenever X = 1 we should add a correction of 0110 to the
sum.
DesignBCD Adder. Using this 4-bit
parallel adder design BCD adder.
Parity bit generator and checker
 A parity bit 0 or 1 is attached such that total number of 1s in
the word is even for even parity and odd for odd parity.
 At the receiving end if the word received has an even
number of 1s in the odd parity system or odd number of 1s
in the even parity system than error is occurred .
 Modulo sum of even number of 1s =0
 Modulo sum of odd number of 1s =1
 If the modulo sum =0 in odd parity then error is detected
 If modulo sum=1 for even parity then error occurred.
Design a POS circuit that will generate
an even parity bit for 4-bit input
Design a circuit that will generate an odd
parity bit for 4-bit input
 FOUR BIT BINARY TO GRAY CODE CONVERTER –DESIGN
(1)…
MSB + + + + Binary code
0 1 1 0 1
TRUTH TABLE:
Gray code
0 1 0 1 1
INPUT ( BINARY) OUTPUTS (GRAY CODE)
B3 B2 B1 B0 G3 G2 G1 G0
0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 1
0 0 1 0 0 0 1 1
0 0 1 1 0 0 1 0
0 1 0 0 0 1 1 0
0 1 0 1 0 1 1 1
0 1 1 0 0 1 0 1
0 1 1 1 0 1 0 0
1 0 0 0 1 1 0 0
1 0 0 1 1 1 0 1
1 0 1 0 1 1 1 1
1 0 1 1 1 1 1 0
1 1 0 0 1 0 1 0
1 1 0 1 1 0 1 1
1 1 1 0 1 0 0 1
109 1 1 1 1 1 0 0 0
FOUR BIT BINARY TO GRAY CODE CONVERTER –DESIGN
(2)…
Simplification using K-maps:

110
 FOUR BIT BINARY TO GRAY CODE CONVERTER –DESIGN (3)

Logic Diagram:

111
FOUR BIT GRAY CODE TO BINARY CONVERTER –DESIGN
(1)…
MSB + + + + Gray code
1 0 1 0 0
 Truth Table:
Binary code
INPUT ( GRAY CODE) 1 1 )
OUTPUTS (BINARY 0 0 0

G3 G2 G1 G0 B3 B2 B1 B0

0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 1
0 0 1 0 0 0 1 1
0 0 1 1 0 0 1 0
0 1 0 0 0 1 1 1
0 1 0 1 0 1 1 0
0 1 1 0 0 1 0 0
0 1 1 1 0 1 0 1
1 0 0 0 1 1 1 1
1 0 0 1 1 1 1 0
1 0 1 0 1 1 0 0
1 0 1 1 1 1 0 1
1 1 0 0 1 0 0 0
1 1 0 1 1 0 0 1
1 1 1 0 1 0 1 1
112 1 1 1 1 1 0 1 0
FOUR BIT GRAY CODE TO BINARY CONVERTER –DESIGN
(2)…
Simplification using K-Maps:

113
 FOUR BIT GRAY CODE TO BINARY CONVERTER –DESIGN
(3)…
Simplification using K-Maps:

114
 FOUR BIT GRAY CODE TO BINARY CONVERTER –DESIGN (4)

Logic Diagram:

115
Exercise

1. Convert the binary number 0101 to Gray code with XOR

gates
2. Convert the gray code 1011 to binary with XOR gates

Solution:

116
Binary to BCD code converter.
 BCD to XS 3 code converter- Design (1)...
TRUTH TABLE FOR BCD TO XS3 CODE CONVERTER:

Input ( Std BCD code) Output ( XS3 Code)

A B C D w x y z
0 0 0 0 0 0 1 1
0 0 0 1 0 1 0 0
0 0 1 0 0 1 0 1
0 0 1 1 0 1 1 0
0 1 0 0 0 1 1 1
0 1 0 1 1 0 0 0
0 1 1 0 1 0 0 1
0 1 1 1 1 0 1 0
1 0 0 0 1 0 1 1
1 0 0 1 1 1 0 0
1 0 1 0 X X X X
1 0 1 1 X X X X
1 1 0 1 X X X X
1 1 1 0 X X X X
1 1 1 1 X X X X
120
 BCD to XS 3 code converter- Design (2)...

K-maps for simplification and simplified Boolean expressions

121
 BCD to XS 3 code converter- Design (3)...

 After the manipulation of the Boolean expressions for

using common gates for two or more outputs, logic
expressions can be given by
z=D’
y=CD+C’D’ = (C+D)’
x= B’C + B’D + BC’D’ = B’(C+D) + BC’D’
w= A + BC + BD = A + B (C+D)

122
 BCD to XS 3 code converter- Design (4)

123