UNIT II
COMBINATIONAL LOGIC
Combinational Circuits – Analysis and Design Procedures - Binary Adder- Subtractor -Decimal Adder -
Binary Multiplier - Magnitude Comparator - Decoders – Encoders – Multiplexers - Introduction to HDL –
HDL Models of Combinational circuits.
COMBINATIONAL CIRCUITS
A combinational circuit consists of logic gates whose outputs at any time are determined from only the
present combination of inputs.
A combinational circuit performs an operation that can be specified logically by a set of Boolean
functions.
Sequential circuits:
Sequential circuits employ storage elements in addition to logic gates. Their outputs are a function of
the inputs and the state of the storage elements.
Because the state of the storage elements is a function of previous inputs, the outputs of a sequential
circuit depend not only on present values of inputs, but also on past inputs, and the circuit behavior must
be specified by a time sequence of inputs and internal states.
ANALYSIS PROCEDURE
Explain the analysis procedure. Analyze the combinational circuit the following logic diagram.
(May 2015)
The a na lys is o f a c o mb ina tio na l c irc u it r eq uir e s tha t we de ter mine the func tio n tha t
the c ir c uit imp le me nts .
The a na lys is c a n be pe r fo r med ma nua lly b y f ind in g the Bo o lea n func tio ns o r tr uth
ta b le o r b y us in g a c o mp ute r s imu la tio n p ro gra m.
The f ir s t step in the a na lys is is to mak e tha t the g ive n c ir c uit is co mb ina tio na l o r
seq ue ntia l.
Once the lo g ic d ia gra m is ve r if ie d to be co mb i na tio na l, o ne ca n p ro ce ed to o bta in the
o utp ut Boo le a n fu nc tio ns or the tr uth tab le .
To obtain the output Boolean functions from a logic diagram,
Label all gate outputs that are a function of input variables with arbitrary symbols or names.
Determine the Boolean functions for each gate output.
Label the gates that are a function of input variables and previously labeled gates with other
arbitrary symbols or names. Find the Boolean functions for these gates.
Repeat the process in step 2 until the outputs of the circuit are obtained.
By repeated substitution of previously defined functions, obtain the output Boolean functions in
terms of input variables.
Page 1
1
Logic diagram for analysis example
The Boolean functions for the above outputs are,
Proceed to obtain the truth table for the outputs of those gates which are a function of previously
defined values until the columns for all outputs are determined.
Page 2
2
DESIGNPROCEDURE
Explain the procedure involved in designing combinational circuits.
The design of combinational circuits starts from the specification of the design objective and culminates
in a logic circuit diagram or a set of Boolean functions from which the logic diagram can be obtained.
The procedure involved involves the following steps,
From the specifications of the circuit, determine the required number of inputs and outputs and assign a
symbol to each.
Derive the truth table that defines the required relationship between inputs and outputs.
Obtain the simplified Boolean functions for each output as a function of the input variables.
Draw the logic diagram and verify the correctness of the design.
**************************************************
CIRCUITS FOR ARITHMETIC OPERATIONS
Half adder:
Construct a half adder with necessary diagrams. (Nov-06,May- 07)
A half-adder is an arithmetic circuit block that can be used to add two bits and produce two outputs
SUM and CARRY.
The Boolean expressions for the SUM and CARRY outputs are given by the equations
Truth Table:
Logic Diagram: Half adder using NAND gate:
*************************
Page 3
3
Full adder:
Design a full adder using NAND and NOR gates respectively. (Nov -10)
A Full-adder is an arithmetic circuit block that can be used to add three bits and produce two outputs
SUM and CARRY.
The Boolean expressions for the SUM and CARRY outputs are given by the equations
Truth table:
Karnaugh map:
K-Map for Sum K-Map for Carry
The simplified Boolean expressions of the outputs are
S = X′A′B + X′AB′ + XA′B′ + XAB
C = AB + BX + AX
Logic diagram:
Page 4
4
The Boolean expressions of S and C are modified as follows
Full adder using Two half adder:
Logic diagram according to the modified expression is shown Figure.
****************************
Page 5
5
Half subtractor:
Design a half subtractor circuit. (Nov-2009)
A half-subtractor is a combinational circuit that can be used to subtract one binary digit from anotherto
produce a DIFFERENCE output and a BORROW output.
The BORROW output here specifies whether a ‘1 ’ has been borrowed to perform the subtraction. The
Boolean expression for difference and borrow is:
Logic diagram:
*************************************
Full subtractor:
Design a full subtractor. (Nov-2009,07)
A full subtractor performs subtraction operation on two bits, a minuend and a subtrahend, and also takes
into consideration whether a ‘1’ has already been borrowed by the previous adjacent lower minuend bit
or not.
As a result, there are three bits to be handled at the input of a full subtractor, namely the two bits to be
subtracted and a borrow bit designated as Bin .
There are two outputs, namely the DIFFERENCE output D and the BORROW output Bo. The
BORROW output bit tells whether the minuend bit needs to borrow a ‘1’ from the next possible higher
minuend bit. The Boolean expression for difference and barrow is:
Page 6
6
K-Map:
Full subtractor using two half subtractor:
*************************************
Page 7
7
Comparators
Design a 2 bit magnitude comparator. (May 2006)
It is a combinational circuit that compares two numbers and determines their relative magnitude. The
output of comparator is usually 3 binary variables indicating:
A<B, A=B, A>B
1-bitcomparator: Let’s begin with 1bit comparator and from the name we can easily make out that this8
circuit would be used to compare 1bit binary numbers.
A B A>B A=B A<B
0 0 0 1 0
1 0 1 0 0
0 1 0 0 1
1 1 0 1 0
For a 2-bit comparator we have four inputs A1 A0 and B1 B0 and three output E (is 1 if two numbers are
equal) G (is 1 when A>B) and L (is 1 when A<B) If we use truth table and K-map the result is
Design of 2 – bit Magnitude Comparator.
The truth table of 2-bit comparator is given in table below
Page 14
9
Truth table:
K-Map:
Page 15
10
Logic Diagram:
********************
4 bit magnitude comparator:
Design a 4 bit magnitude comparators. (Apr – 2019)
Input
Page 16
11
BCD Adder:
Design to perform BCD addition.(or) What is BCD adder? Design an adder to perform arithmetic
addition of two decimal bits in BCD. (May -08)(Apr 2017,2018)[Nov – 2019]
Consider the arithmetic addition of two decimal digits in BCD, together with an input carry from a
previous stage. Since each input digit does not exceed 9, the output sum cannot be greater than 9 + 9 + 1
= 19, the 1 in the sum being an input carry.
Suppose we apply two BCD digits to a four-bit binary adder. The adder will form the sum in binary and
produce a result that ranges from 0 through 19. These binary numbers are listed in Table and are labeled
by symbols K, Z8, Z4, Z2, and Z1. K is the carry, and the subscripts under the letter Z represent the
weights 8, 4, 2, and 1 that can be assigned to the four bits in the BCD code.
Page 18
12
A BCD adder that adds two BCD digits and produces a sum digit in BCD is shown in Fig. The two
decimal digits, together with the input carry, are first added in the top four-bit adder to produce the
binary sum.
When the output carry is equal to 0, nothing is added to the binary sum. When it is equal to 1, binary
0110 is added to the binary sum through the bottom four-bit adder.
The condition for a correction and an output carry can be expressed by the Boolean function
C = K + Z8Z4 + Z8Z2
The output carry generated from the bottom adder can be ignored, since it supplies information already
available at the output carry terminal.
A decimal parallel adder that adds n decimal digits needs n BCD adder stages. The output carry from
one stage must be connected to the input carry o f the next higher order stage.
******************************
Binary Multiplier:
Explain about binary Multiplier.
Multiplication of binary numbers is performed in the same way as multiplication of decimal numbers.
The multiplicand is multiplied by each bit of the multiplier, starting from the least significant bit. Each
such multiplication forms a partial product.
Successive partial products are shifted one position to the left. The final product is obtained from the
sum of the partial products.
A combinational circuit binary multiplier with more bits can be constructed in a similar fashion.
A bit of the multiplier is ANDed with each bit of the multiplicand in as many levels as there are bits in
the multiplier.
The binary output in each level of AND gates is added with the partial product of the previous level to
form a new partial product. The last level produces the product.
Page 19
13
*************************************
Page 20
14
DECODERS AND ENCODERS
Decoder:
Explain about decoders with necessary diagrams. (Apr 2018)(Nov 2018)
A decoder is a combinational circuit that converts bina ry information from n input lines to a maximum
of 2n unique output lines. If the n -bit coded information has unused combinations, the decoder may
have fewer than 2n outputs.
The purpose of a decoder is to generate the 2 n (or fewer) minterms of n input variables, shown below for
two input variables.
2 to 4 decode r:
3 to 8 Decoder:
Design 3 to 8 line decoder with necessary diagram. May -10)
Truth table:
Page 31
15
Logic diagram:
Design for 3 to 8 decoder with 2 to 4 decoder:
Not that the two to four decoder design shown earlier, with its enable inputs can be used to build a three
to eight decoder as follows.
Page 32
16
Implementation of Boolean function using decode r:
Since the three to eight decoder provides all the minterms of three variables, the realisation of a
function in terms of the sum of products can be achieved using a decoder and OR gates as follows.
Example: Implement full adder using decoder.
Sum is given by ∑m(1, 2, 4, 7) while Carry is given by ∑m(3, 5, 6, 7) as given by the minterms
each of the OR gates are connected to.
Design for 4 to 16 decoder using 3 to 8 decoder: Design 5 to 32 decoder using 3 to 8 and 2 to 4 decoder:
**********************************
BCD to seven segment decoder
Design a BCD to seven segment code converter. (May-06,10, Nov- 09)
Page 33
17
Encoder:
Explain about encoders. (Nov 2018)
An encoder is a digital circuit that performs the inverse operation of a decoder. An encoder has 2 n (or
fewer) input lines and n output lines. The output lines, as an aggregate, generate the binary code
corresponding to the input value.
Octal to Binary Encode r:
The encoder can be implemented with OR gates whose inputs are determined directly from the truth
table. Output z is equal to 1 when the input octal digit is 1, 3, 5, or 7.
Output y is 1 for octal digits 2, 3, 6, or 7, and output x is 1 for digits 4, 5, 6, or 7. These conditions can
be expressed by the following Boolean output functions:
The encoder can be implemented with three OR gates.
Truth table:
Another ambiguity in the octal-to-binary encoder is that an output with all 0’s is generated when all the
inputs are 0; but this output is the same as when D0 is equal to 1. The discrepancy can be resolved by
providing one more output to indicate whether at least one input is equal to 1.
Page 36
18
MULTIPLEXERS AND DEMULTIPLEXERS
Multiplexer: (MUX)
Design a 2:1 and 4:1 multiplexer.
A multiplexer is a combinational circuit that selects binary information from one of many input lines and
directs it to a single output line. The selection of a particular input line is controlled by a set of selection
lines.
Normally, there are 2n input lines and n selection lines whose bit combinations determine which input is
selected.
2 to 1 MUX:
A 2 to 1 line multiplexer is shown in figure below, each 2 input lines A to B is applied to one input of an
AND gate. Selection lines S are decoded to select a particular AND gate. The truth table for the 2:1 mux
is given in the table below.
To derive the gate level implementation of 2:1 mux we need to have truth table as shown in figure. And
once we have the truth table, we can draw the K- map as shown in figure for all the cases when Y is
equal to '1'.
Truth table:
Logic Diagram:
Page 39
19
4 to 1 MUX:
A 4 to 1 line multiplexer is shown in figure below, each of 4 input lines I0 to I3 is applied to one input
of an AND gate.
Selection lines S0 and S1 are decoded to select a particular AND gate.
The truth table for the 4:1 mux is given in the table below.
Logic Diagram:
Truth Table:
SELECT OUTPUT
INPUT
S1 S0 Y
0 0 I0
0 1 I1
1 0 I2
1 1 I3
Problems :
Example: Implement the Boolean expression using MUX
F(A,B,C,D) = ∑m(0,1,5,6,8,10,12,15) (Apr 2017, Nov 2017)
Page 40
20
Example: Implement the boolean function using Multiplexer. [NOV – 2019]
F (x, y, z) = Σm (1, 2, 6, 7)
Solution:
Implementation table:
Multiplexer Implementation:
Example: 32:1 Multiplexer using 8:1 Mux (Nov 2018) (Apr – 2019)
Page 41
21
DEMULTIPLEXERS:
Explain about demultiplexers.
The de- multiplexer performs the inverse function of a multiplexer, that is it receives information on one
line and transmits its onto one of 2n possible output lines.
The selection is by n input select lines. Example: 1-to-4 De- multiplexer
Logic Diagram: Truth Table:
INPUT OUTPUT
E D S0 S1 Y0 Y1 Y2 Y3
1 1 0 0 1 0 0 0
1 1 0 1 0 1 0 0
1 1 1 0 0 0 1 0
1 1 1 1 0 0 0 1
Page 42
22
Example:
1. Implement full adder using De-multiplexer.
2. Implement the following functions using de-multiplexer.
f1 (A,B,C) = ∑m(1,5,7), f2 (A,B,C) = ∑m(3,6,7)
Solution:
***************************
Page 43
23
Powered by TCPDF (www.tcpdf.org)
