DMI COLLEGE OF ENGINEERING

CS1201-DIGITAL PRINCIPLES AND COMPUTER

ORGANIZATION

UNITI COMBINATIONAL CIRCUITS:

-Combinational Circuits
– Karnaugh Map-Analysis and Design Procedures
– Code Conversions
– Binary Adder–Subtractor
– Decimal Adder
-Magnitude Comparator
–Decoder
– Encoder
– Multiplexers
-Demultiplexers
- Introduction to HDL
-HDL models for Combinational Circuits
 DMI COLLEGE OF ENGINEERING

INTRODUCTION
The digital system consists of two types of circuits, namely
(i) Combinational circuits
(ii) Sequential circuits

Combinational circuit consists of logic gates whose output at any time is

determined from the present combination of inputs. The logic gate is the most
basic building block of combinational logic. The logical function performed by a
combinational circuit is fully defined by a set of Boolean expressions.

Sequential logic circuit comprises both logic gates and the state of
storage elements such as flip-flops. As a consequence, the output of a sequential
circuit depends not only on present value of inputs but also on the past state of
inputs.
In the previous chapter, we have discussed binary numbers, codes, Boolean
algebra and simplification of Boolean function and logic [Link] this chapter,
formulation and analysis of various systematic designs of combinational circuits
will be discussed.

A combinational circuit consists of input variables, logic gates, and output

variables. The logic gates accept signals from inputs and output signals are
generated according to the logic circuits employed in it. Binary information
from the given data transforms to desired output data in this process. Both
input and output are obviously the binary signals,i.e., both the input and output
signals are of two possible states, logic 1 and logic 0.

Block diagram of a combinational logic circuit

For n number of input variables to a combinational circuit, 2n possible combinations

of binary input states are possible. For each possible combination, there is one
and only one possible output combination. A combinational logic circuit can
be described by m Boolean functions and each output can be expressed interms
of n input variables.
 DMI COLLEGE OF ENGINEERING

DESIGN PROCEDURE:
Any combinational circuit can be designed by the following steps of design
procedure.
1. The problem is stated.
2. Identify the input and output variables.
3. The input and output variables are assigned letter symbols.
4. Construction of a truth table to meet input-output requirements.
5. Writing Boolean expressions for various output variables interms of
input variables.
6. The simplified Boolean expression is obtained by any method of
minimization—algebraic method, Karnaugh map method,or tabulation method.
7. A logic diagram is realized from the simplified Boolean expression using
logic gates.
The following guidelines should be followed while choosing the preferred form for
hardware implementation:
1. The implementation should have the minimum number of gates, with the
gates used having the minimum number of inputs.
2. There should be a minimum number of interconnections.
3. Limitation on the driving capability of the gates should not be ignored.

ARITHMETIC CIRCUITS–BASIC BUILDING BLOCKS:

In this section, we will discuss those combinational logic building blocks

that can be used to perform addition and subtraction operations on binary
numbers. Addition and subtraction are the two most commonly used arithmetic
operations, as the other two, namely multiplication and division, are
respectively the processes of repeated addition and repeated subtraction.
The basic building blocks that form the basis of all hardware used to perform
the arithmetic operations on binary numbers are half-adder,full adder,half-
subtractor,full-subtractor.

Half-Adder:
A half-adder is a combinational circuit that can be used to add twobinary
bits. It has two inputs that represent the two bits to be added and two outputs,
with one producing the SUM output and the other producing the CARRY.
 DMI COLLEGE OF ENGINEERING

Block schematic of half-adder

The truth table of a half- adder, showing all possible input combinations and the
corresponding outputs are shown below.

Inputs Outputs
A B Carry(C Sum(S)
)
0 0 0 0
0 1 0 1
1 0 0 1
1 1 1 0
Truth table of half adder K-map simplification for carry and sum:
The Boolean expressions for the SUM and CARRYoutputs are given by the
equations,
Sum, S=A’B+AB’=AB
Carry, C=A.B The logic diagram of the half adder is

The first one representing the SUM output is that of an EX-OR

gate, the second one representing the CARRYoutput is that of an AND
gate.
Full-Adder:
A full adder is a combinational circuit that forms the arithmetic sum of three
input [Link] consists of 3 inputs and 2 outputs.
Two of the input variables, represent the significant bits to be [Link]
third input represents the carry from previous lower significant [Link] block
diagram of full adder is given by,

Block schematic of full-adder

 DMI COLLEGE OF ENGINEERING

The full adder circuit overcomes the limitation of the half-adder, which can
beused to add two bits only. As there are three input variables, eight different
input combinations are [Link] truthtable is shown below,

TruthTable:

Input Output
s s
A B Ci Sum(S) Carry(Co
n ut)
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

To derive the simplified Boolean expression from the truthtable, the Karnaugh map
method is adopted as,

The Boolean expressions for the SUM and CARRYoutputs are given by the
equations,
Sum, S=A’B’Cin+A’BC’in+AB’C’in+ABCin
Carry, Cout=AB+ACin+BCin.

The logic diagram for the above functions is shown as,

 DMI COLLEGE OF ENGINEERING

Implementation of full-adder in Sum of Products

The logic diagram of the full adder can also be implemented with two
half- adders and one OR [Link] Soutput from the second half adder is the
exclusive- OR of Cin and the output of the first half-adder,giving

Sum=Cin(AB) [xy=x‘y+xy‘]
=Cin(A‘B+AB‘)
=C‘in(A‘B+AB‘)+Cin(A‘B+AB‘)‘ [(x‘y+xy‘)‘=(xy+x‘y‘)]
=C‘in(A‘B+AB‘)+Cin(AB+A‘B‘)
=A‘BC‘in+AB‘C‘in+ABCin+A‘B‘Cin.
And the carry output is,
Carry, Cout=AB+Cin(A’B+AB’)
=AB+A‘BCin+AB‘Cin
=AB(Cin+1)+A‘BCin+AB‘Cin [Cin+1=1]
=ABCin+AB+A‘BCin+AB‘Cin
=AB+ACin(B+B‘)+A‘BCin
=AB+ACin+A‘BCin
=AB(Cin+1)+ACin+A‘BCin [Cin+1=1]
=ABCin+AB+ACin+A‘BCin
=AB+ACin+BCin(A+A‘)
=AB+ACin+BCin.
 Implementation of full adder with two half-adders and an ORgate

Half-Subtractor:Block schematic of half-subtractor

A half-subtractor is a combinational circuit that can be used to subtract one binary

digit from another to produce a DIFFERENCE output and a BORROW output. The
BORROWout put here specifies whether a‗1‘has been borrowed to perform the
[Link] truth table of half-subtractor, showing all possible input
combinations and the corresponding outputs are shown below.
K-map simplification for half subtractor:

The Boolean expressions for the DIFFERENCE and BORROW outputs are given
by the equations,
Difference, D= A’B+ AB’=AB
Borrow, Bout=A’.B
The first one representing the DIFFERENCE (D) output is that of an
exclusive-OR gate,the expression for the BORROW output (Bout)is that of an
AND gate with input A complemented before it is fed to the gate.
Input Output
A B Difference( Borrow(Bout)
D)
0 0 0 0
0 1 1 1
1 0 1 0
1 1 0 0
 The logic diagram of the half adder is,

Logic Implementation of Half-Subtractor

Comparing a half-subtractor with a half-adder, we find that the
expressions for the SUM and DIFFERENCE outputs are just the same. The
expression for BORROW inthe case of the half-subtractor is also similar to
what we have for CARRY in the case of the [Link] the input A, ie.,the
Minuend is complemented an AND gate can be used be used to implement the
BORROW output.
Full Subtractor:
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
[Link] are two outputs, namely the DIFFERENCE output D and the
BORROW [Link] BORROW output bit tells whether the minuend bit
Needs to borrow a‗1‘from the next possible higher minuend bit.

Block schematic of full-adder

The truth table for full-subtractor is,
Input Output
s s
A B B i Difference(D Borrow(Bo
n ) ut)
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
 K-map simplification for full-subtractor:

The Boolean expressions for the DIFFERENCE and BORROW outputs are
given by the equations,
Difference, D =A’B’Bin+A’BB’in+AB’B’in+ABBin
PreparedByKAVIARASAN.S/[Link].,PIT

Borrow, Bout =A’B+A’Cin+BBin.

The logic diagram for the above functions is shown as,

Implementation of full-adder in Sum of Products

The logic diagram of the full-subtractor can also be implemented with two
Half-subtractors and one OR [Link] difference, Doutput from the second half
subtractor is the exclusive-OR of Bin and the output of the first half-subtractor,
giving Difference, D=Bin(AB) [xy=x‘y+xy‘]
=Bin(A‘B+AB‘)
=B‘in(A‘B+AB‘)+Bin(A‘B+AB‘)‘ [(x‘y+xy‘)‘=(xy+x‘y‘)]
=B‘in(A‘B+AB‘)+Bin(AB+A‘B‘)
=A‘BB‘in+AB‘B‘in+ABBin+A‘B‘Bin.
And the borrow output is,
Borrow, Bout=A’B+Bin(A’B+AB’)’[(x‘y+xy‘)‘=(xy+x‘y‘)]
=A‘B+Bin(AB+A‘B‘)
=A‘B+ABBin+A‘B‘Bin
 =A‘B(Bin+1)+ABBin+A‘B‘Bin [Cin+1=1]
=A‘BBin+A‘B+ABBin+A‘B‘Bin
=A‘B+BBin(A+A‘)+A‘B‘Bin [A+A‘=1]
=A‘B+BBin+A‘B‘Bin
=A‘B(Bin+1)+BBin+A‘B‘Bin [Cin+1=1]
=A‘BBin+A‘B+BBin+A‘B‘Bin
=A‘B+BBin+A‘Bin(B+B‘)
=A‘B+BBin+A‘Bin.
Therefore, We can implement full-subtractor using two half-subtractors and OR gate
as,

Implementation of full-subtractor with two half-subtractors and

an OR gate
Four–bit Binary Adder(Parallel Adder):
The 4-bit binary adder using full adder circuits is capable of
adding two4- bit numbers resulting in a 4-bit sum and a carry output
as shown in figure below.

4-bit binary parallel Adder

Since all the bits of augend and addend are fed into the adder
circuits simultaneously and the additions in each position are taking
place at the same time, this circuit is known as parallel adder.
 Let the 4- bit words to be added be represented by, A3A2A1A0=1111 and
B3B2B1B0=0011.

The bits are added with full adders, starting from the least significant position, to
form the sum it and carry [Link] input carry C0 in the least significant position
must be 0. The carry output of the lower order stage is connected to the carry input of
the next higher order stage. Hence this type of adder is called ripple-carry adder.
In the least significant stage, A 0, B0 and C0 (which is 0) are added
resulting in sum S0 and carry C1. This carry C1 becomes the carry input to the
second stage. Similarly in the second stage, A 1, B1and C1 are added resulting
in sum S1and carry C2, in the third stage, A2, B2 and C2 are added resulting in
sum S2 and carry C3, in the third stage, A3, B3 and C3 are added resulting in
sum S3 and C4, which is the output [Link] the circuit results in a sum
(S3S2S1S0) and a carry output (Cout).
Though the parallel binary adder is said to generate its output
immediately after the inputs are applied, its speed of operation is limited by the
carry propagation delay through all stages. However, there are several methods
to reduce this delay.
One of the methods of speeding up this process is look-ahead carry
addition which eliminates the ripple-carry delay.

Binary Subtractor (Parallel Subtractor):

The subtraction of unsigned binary numbers can be done most
conveniently by means of complements. The subtraction A-B can be done by
taking the 2‘s complement of B and adding it to A. The 2‘s complement can be
obtained by taking the 1‘s complement and adding 1 to the least significant pair
of bits.
The 1‘s complement can be implemented with inverters and a1can be added to
the sum through the input carry.
The circuit for subtracting A-B consists of an adder with inverters placed
between each data input B and the corresponding input of the full adder. The
input carry C0 must be equal to 1 when performing [Link] operation thus
performed becomes A, plus the1‘s complement of B, [Link] is equal to A
 plus the 2‘s complement of B.

4-bit Parallel Subtractor

4-Bit Parallel Adder/Subtractor:

The addition and subtraction operation can be combined into one circuit
with one common binary [Link] is done by including an exclusive-OR gate
with each fulladder.A 4-bit adder Subtractor circuit is shown below.
The mode input M controls the [Link] M=0, the circuit is an adder and when
M=1, the circuit becomes a Subtractor. Each exclusive- OR gate receives inputM
and one of the inputs of B. When M=0, we have B0=B. The full adders receive
the value of B, the input carry is 0, and the circuit performs A plus [Link] M=1, we
have B1= B‘and C0=1. The B inputs are all complemented and a1 is added
through the input carry. The circuit performs the operation A plus the 2‘s
complement of B. The exclusive-OR with output V is for detecting an overflow.

Decimal Adder (BCD Adder):

The digital system handles the decimal number in the form of binary coded
decimal numbers (BCD). ABCD adder is a circuit that adds two BCD bits and produces
a sum digital so in BCD.
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 1is the sum being an input carry.
The adder will form the sum in binary and produce a result that ranges from 0
through 19.
These binary numbers are labeled by symbols K, Z 8, Z4, Z2, Z1, K is the carry.
The columns under the binary sum list the binary values that appear in the outputs of
the 4-bit binary adder. The output sum of the two decimal digits must be represenin
BCD.

BinarySum BCDSum
Decimal
K Z Z4 Z2 Z1 C S8 S S2 S1

8 4
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 1 1
0 0 0 1 0 0 0 0 1 0 2
0 0 0 1 1 0 0 0 1 1 3
0 0 1 0 0 0 0 1 0 0 4
0 0 1 0 1 0 0 1 0 1 5
0 0 1 1 0 0 0 1 1 0 6
0 0 1 1 1 0 0 1 1 1 7
0 1 0 0 0 0 1 0 0 0 8
0 1 0 0 1 0 1 0 0 1 9
0 1 0 1 0 1 0 0 0 0 10
0 1 0 1 1 1 0 0 0 1 11
0 1 1 0 0 1 0 0 1 0 12
0 1 1 0 1 1 0 0 1 1 13
0 1 1 1 0 1 0 1 0 0 14
0 1 1 1 1 1 0 1 0 1 15
1 0 0 0 0 1 0 1 1 0 16
1 0 0 0 1 1 0 1 1 1 17
1 0 0 1 0 1 1 0 0 0 18
1 0 0 1 1 1 1 0 0 1 19

In examining the contents of the table, it is apparent that when the binary sum is
equal to or less than 1001, the corresponding BCD number is identical, and therefore
no conversion is [Link] the binary sum is greater than 9 (1001), we obtain a
non-valid BCD [Link] addition of binary 6 (0110) to the binary sum
converts it to the correct BCD representation and also produces an output carry as
required.
The logic circuit to detect sum greater than
9 can be determined by simplifying the Boolean expression of the given truth table.

To implement BCD adder we require:

 4-bit binary adder for initial addition
 Logic circuit to detect sum greater than 9 and
 One more 4-bit adder to add 01102 in the sum if the sum is greater than 9 or
carry is1.
The two decimal digits, together with the input carry, are first added in the
top 4-bit binary adder to provide the binary sum. When the output carry is equal
to zero, nothing is added to the binary sum. When it is equal to one, binary 0110
is added to the binary sum through the bottom 4-bit adder. The output carry
generated from the bottom adder can be ignored, since it supplies information
already available at the output carry terminal. The output carry from one stage
must be connected to the input carryof the next higher-order stage.
 Block diagram of BCD adder

MAGNITUDE COMPARATOR

A magnitude comparator is a combinational circuit that compares two

given numbers (A and B) and determines whether one is equal to, less than or greater
than the [Link] output is in the form of three binary variables
Block diagram of n-Bit magnitude comparator

Representing the conditions A=B, A>B and A<B, if A and B are the two
numbers being [Link] comparison of two n-bit numbers, the classical method
to achieve the Boolean expressions requires a truth table of 22n entries and becomes
too lengthy and cumbersome.

1-Bit Magnitude Comparator:

A comparator used to compare two bits is called a single-bit [Link] consists
of two inputs each for two single-bit numbers and three outputs to generate less than,
equal to, and greater than between two binary numbers.
The truth table for a1-bit comparator is given below:
 From the above truth table logical expressions for each output can be expressed as
follows:
A>B: AB'
A<B:A'B
A=B:A'B'+AB
From the above expressions we can derive the following formula:

By using these Boolean expressions, we can implement a logic circuit for this comparator
as given below:

2-Bit Magnitude Comparator:

The truth table of 2-bit comparator is given in table below—
Truth table:
 Input Outputs
s
A A2 A1 A0 A>B A=B A<B
3
0 0 0 0 0 1 0
0 0 0 1 0 0 1
0 0 1 0 0 0 1
0 0 1 1 0 0 1
0 1 0 0 1 0 0
0 1 0 1 0 1 0
0 1 1 0 0 0 1
0 1 1 1 0 0 1
1 0 0 0 1 0 0
1 0 0 1 1 0 0
1 0 1 0 0 1 0
1 0 1 1 0 0 1
1 1 0 0 1 0 0
1 1 0 1 1 0 0
1 1 1 0 1 0 0
1 1 1 1 0 1 0
K-map Simplification:

Logic Diagram:
ENCODERS:
An encoder is a digital circuit that performs the inverse operation of a
decoder. Hence, the opposite of the decoding process is called encoding. An
encoder is a combinational circuit that converts binary information from 2n input lines
to a maximum of‗n ‘unique output lines.
The general structure of encoder circuitis–

General structure of Encoder

It has 2n input lines, only one which 1 is active at any time and‗n‘output
[Link] encodes one of the active inputs to a coded binary output with ‗n‘bits. In
an encoder, the number of outputs is less than the number of inputs.

Octal-to-Binary Encoder:
It has eight inputs (one for each of the octal digits) and the three outputs
 that generate the corresponding binary number. It is assumed that only one
input has a value of 1 at any given time.

Inputs Outputs
D D D D D D D D A B C
0 1 2 3 4 5 6 7
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

The encoder can be implemented with OR gates whose inputs are

determined directly from the truth [Link] z is equal to1, when the input
Octal digit is 1 or 3 or 5 or 7. Output y is 1 for octal digits 2, 3, 6, or 7 and the
output is1for digits 4, 5, 6 or 7. These conditions can be expressed by the following
output Boolean functions:
z=D1+D3+D5+D7
y=D2+D3+D6+D7
x=D4+D5+D6+D7
The encoder can be implemented with three OR [Link] encoder
defined in the below table, has the limitation that only one input can be active
at any given time. If two inputs are active simultaneously, the output produces
an undefined combination.
For eg., if D3 and D6 are 1 simultaneously, the output of the encoder
may be [Link] does not represent either D6 or D3. To resolve this problem,
encoder circuits must establish an input priority to ensure that only one input is
encoded. If we establish ahigher priority for inputs with higher subscript
numbers and if D3 and D6 are 1 at the same time, the output will be 110
because D6 has higher priority than D3.
 Octal-to-BinaryEncoder
Another problem in the octal-to-binary encoder is that an output with all 0‘s
is generated when all the inputs are 0; this output is same as when D 0 is equal to 1.
The discrepancy can be resolved by providing one more output to indicate that
atleast one input is equal to 1.
Priority Encoder:
A priority encoder is an encoder circuit that includes the priority function.
Inpriority encoder, if two or more inputs are equal to1at the same time, the input
having the highest priority will take precedence.
In addition to the two outputs x and y, the circuit has a third output, V (valid
bit indicator).It is set to 1 when one or more inputs are equal to [Link] all inputs are 0,
there is no valid input and V is equal to 0. The higher the subscript number, higher
the priority of the input. Input D3, has the highest priority. So, regardless of the
values of the other inputs, when D3 is 1, the output for xy is 11.
D2 has the next priority [Link] output is 10, if D2=1 provided D3=0. The
output for D1 is generated only if higher priority inputs are 0, and so on down the
priority levels.
Truth table:
Input Outputs
s
D D D D x y V
0 1 2 3
0 0 0 0 x x 0
1 0 0 0 0 0 1
x 1 0 0 0 1 1
x X 1 0 1 0 1
x X x 1 1 1 1
Although the above table has only five rows, when each don‘t care
condition is replaced first by 0 and then by 1, we obtain all 16 possible input
combinations.
For example, the third row in the table with X100 represents minterms 0100 and
 [Link] don‘t care condition is replaced by 0 and 1as shown in the table
below.
Modified Truth table:
Input Outputs
s
D D D D x y V
0 1 2 3
0 0 0 0 x x 0
1 0 0 0 0 0 1
0 1 0 0
1 1 0 0 0 1 1
0 0 1 0
0 1 1 0
1 0 1 0 1 0 1
1 1 1 0
0 0 0 1
0 0 1 1
0 1 0 1
0 1 1 1 1 1 1
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 1
K-map Simplification:
 The priority encoder is implemented according to the above Boolean functions.

Input Priority Encoder

DECODERS:
A decoder is a combinational circuit that converts binary information From
‗n‘ input lines to a maximum of ‗2n‘ unique output lines. The general structure
of decoder circuit is–
General structure of decoder

The encoded information is presented as ‗n‘inputs producing

‗2n‘possible outputs. The 2n output values are from 0 through 2n-1. A decoder
is provided with enable inputs to activate decoded output based on data inputs.
When any one enable input is unasserted, all outputs of decoder are disabled.
Binary Decoder (2 to 4 decoder):
A binary decoder has‗n‘ bit binary input and a one activated output out of
2n outputs. A binary decoder is used when it is necessary to activate exactly
one of 2n outputs based on a nn-bit input value.
2-to-4 Line decoder
Here the 2 inputs are decoded into 4 outputs, each output representing one of the
minterms of the two input variables.

Input Output
s s
Enabl A B Y Y Y Y
e 3 2 1 0
0 x x 0 0 0 0
1 0 0 0 0 0 1
1 0 1 0 0 1 0
1 1 0 0 1 0 0
1 1 1 1 0 0 0

As shown in the truth table, if enable input is 1(EN=1) only one of the
outputs (Y0–Y3), is active for a given input.
The output Y0 is active, ie.,Y0=1 when inputs A=B=0, Y1 is active when inputs,
A=0 and B=1, Y2 is active, when input A=1 and B=0,Y3 is active,
When inputs A=B=1.
3 to-8 Line Decoder:
A 3-to-8 line decoder has three inputs (A, B, C) and eight outputs (Y0- Y7).
Based on the 3 inputs one of the eight outputs is [Link] three inputs are decoded
into eight outputs, each output representing one of the minterms of the 3-input
[Link] decoder is used for binary-to- octal [Link] input variables may
represent a binary number and the outputs will represent the eight digits in the octal
number [Link] output variables are mutually exclusive because only one output
can be equal to 1 at any one [Link] output line whose value is equal to1represents the
minterm equivalent of the binar y number presently available in the input lines.

Input Output
s s
A B C Y Y Y Y Y Y Y Y
0 1 2 3 4 5 6 7
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

3-to-8 line decoder BCD to 7-Segment Display Decoder:

A seven-segment display is normally used for displaying any one of
the decimal digits, 0 through 9. ABCD-to-seven segment decoder accepts a
decimal digit in BCD and generates the corresponding seven-segment code.

Each segment is made up of a material that emits light when current is passed
through [Link] segments activated during each digit display are tabulated as—
Digit Display Segments
Activated

0 a,b,c,d,e,f

1 b,c

2 a,b,d,e,g

3 a,b,c,d,g

4 b,c,f,g

5 a,c,d,f,g

6 a,c,d,e,f,g

7 a,b,c

8 a,b,c,d,e,f,g
 9 a,b,c,d,f,g

Truthtable:

BCDcode 7-
Segmentcode
Digi A B C D a b c d e f g
t
0 0 0 0 0 1 1 1 1 1 1 0
1 0 0 0 1 0 1 1 0 0 0 0
2 0 0 1 0 1 1 0 1 1 0 1
3 0 0 1 1 1 1 1 1 0 0 1
4 0 1 0 0 0 1 1 0 0 1 1
5 0 1 0 1 1 0 1 1 0 1 1
6 0 1 1 0 1 0 1 1 1 1 1
7 0 1 1 1 1 1 1 0 0 0 0
8 1 0 0 0 1 1 1 1 1 1 1
9 1 0 0 1 1 1 1 1 0 1 1

K-mapSimplification:
LogicDiagram

BCD to 7-segment display decoder

Applications of decoders:
1. Decoders are used in counter system.
2. They are used in analog to digital converter.
3. Decoder outputs are used to drive a display system.

MULTIPLEXER: (Data Selector)

A multiplexer or MUX, is a combinational circuit with more than one
Input line, one output line and more than one selection line. A multiplexer selects
binary information present from one of many input lines, depending upon the logic
status ofthe selection inputs, and routes it to the output line. Normally, there are
2 n input linesand n selection lines whose bit combinations determine which input
is selected. The multiplexer is often labeled as MUX in block diagrams.
 A multiplexer is also called a data selector, since it selects one of many
inputs and steers the binary information to the output line.

Block diagram of Multiplexer

2-to-1-line Multiplexer:
The circuit has two data input lines, one output line and one selection line, S. When
S=0, the upper AND gate is enabled and I0 has a path to the output.
When S=1, the lower AND gate is enabled and I1 has a path to the output.

The multiplexer acts like an electronic switch that selects one of the two sources.
Truth table:
S Y
0 I0
1 I1
 4-to-1-line Multiplexer:
A 4-to-1-line multiplexer has four (2n) input lines, two (n) select lines
and one output line. It is the multiplexer consisting of four input channels and
information of one of the channels can be selected and transmitted to an output
line according to the select inputs combinations. Selection of one of the four
input channel is possible by two selection inputs.
Each of the four inputs I0 through I3, is applied to one input of AND
[Link] lines S1and S0 are decoded to select a particular AND [Link] outputs
of the AND gate are applied to a single OR gate that provides the 1-line output.

4-to-1-Line Multiplexer
Function table:

S1 S0 Y
0 0 I0
0 1 I1
1 0 I2
1 1 I3

To demonstrate the circuit operation, consider the case when S 1S0= 10. The
AND gate associated with input I2 has two of its inputs equal to 1 and the third input
connected to [Link] other three AND gates have atleast one input equal to 0,which
makes their outputs equal to 0. The OR output is now equal to the value of I 2,
providing a path from the selected input to the output.
The data input is equal to I0 only if S0=0 and S1=0;
 Y= I0S1‘S0‘.The data output is equal to I1 onlyif S1= 0 and S0= 1;
Y= I1S1‘[Link] data output is equal to I2 only if S1= 1 and S0= 0;
Y= I2S1S0‘.The data output is equal to I3 only if S1=1and S0=1;
Y=I3S1S0.
When the seterms are ORed, the total expression for the data output is,
Y=I0S1’S0’+I1S1’S0+I2S1S0’+I3S1S0.
As in decoder, multiplexers may have an enable input to control the
operation of the unit. When the enable input is in the inactive state, the outputs
are disabled, and when it isin the active state, the circuit functions as a normal
multiplexer.
Quadruple 2-to-1 Line Multiplexer:

This circuit has four multiplexers, each capable of selecting one of two
input lines. Output Y0can be selectedto comefrom either A0 or B0. Similarly,
output Y1 may have the value of A1 or B1, and so on. Input selection line, S
selects one of the lines
in each of the four [Link] enable input E must be active for normal
operation.
Although the circuit contains four 2-to-1-Line multiplexers, it is viewed
as a circuit that selects one of two 4-bit sets of data lines. The unit is enabled
when E=Then if S=0, the four A inputs have a path to the four [Link] the
other hand, if S=1, the four B inputs are applied to the outputs. The outputs
have all 0‘s when E= 1, regardless of the value of S.
Application:
The multiplexer is a very useful MSI function and has various ranges of
applications in data communication. Signal routing and data communication are
the important applications of a [Link] is used for connecting two or more
sources to guide to a single destination among computer units and it is useful
for constructing a common bus system. One of the general properties of a
multiplexer is that Boolean functions can be implemented by this device.

Implementation of Boolean Function using MUX:

Any Boolean or logical expression can be easily implemented using a
multiplexer. If a Boolean expression has (n+1) variables, then ‗n‘ of these
variables can be connected to the select lines of the multiplexer. The remaining
single variable along with constants 1 and 0 isused as the input of the
[Link] example, if C is
the single variable, then the inputs of the multiplexers are C, C‘, 1 and [Link] this
method any logical expression can be implemented.
In general, a Boolean expression of (n+1) variables can be implemented
using a multiplexer with 2n inputs.

Implement the following Boolean function using 4:1 multiplexer,

F(A,B,C)=∑m(1,3,5,6).
Solution:
Variables, n=3(A,B,C) Se lectlines=n-1=2(S1,S0) 2n-1 to MUX i.e., 22to1=4
to 1 MUX Input lines=2n-1=22=4(D0,D1,D2,D3)

Implementation table:
Apply variables A and B to the select lines. The procedures for implementing the
function are:
i. List the input of the multiplexer
ii. List under them all the minterms in two rows as shown below.
The first half of the minterms is associated with A‘and the second half with A.
The given function is implemented by circling the minterms of the function and
applying the following rules to find the values for the inputs of the multiplexer.
1. If both the minterms in the column are not circled, apply 0 to the
corresponding input.
2. If both the minterms in the column are circled, apply 1 to the corresponding
input.
 3. If the bottom minterm is circled and the top is not circled, apply C to the
input.
4. If the top minterm is circled and the bottom is not circled, apply C‘to the input.
Multiplexer Implementation:

2. F(x,y,z)=∑m(1,2,6,7)
Solution: Implementation table:

Multiplexer Implementation:
 4. F(A,B,C)=∑m(1,2,4,5)
Solution: Variables, n=3(A,B,C)Selectli nes=n-1=2(S1,S0)
n-1 2
2n-1 to MUX i.e., 22to1=4to1 MUX Input lines=2 =2 =4(D0,D1,D2,D3)
Implementation table:

Multiplexer Implementation

4.F(P,Q,R,S)=∑m(0,1,3,4,8,9,15)

Solution:
Variables, n=4(P,Q,R,S)Sel ectlines=n-1=3(S2,S1,S0)
2n-1 to MUX i.e., 23to1=8 to1MUX
Input lines=2n-1=23=8(D0,D1,D2,D3,D4,D5,D6,D7)

Implementation table:

Multiplexer Implementation:
 5. Implement the Boolean function using 8:1 and also using 4:1 multiplexer
F(A,B,C,D)=∑m(0,1,2, 4, 6, 9, 12, 14)
Solution:
Variables, n=4(A,B,C,D) Select lines=n-1=3(S2,S1,S0)
2n-1 to MUX i.e., 23 to 1=8 to1MUX
Input lines=2n-1=23=8(D0,D1,D2,D3,D4,D5,D6,D7)

Implementation table: Multiplexer Implementation (Using 8:1MUX):

Using 4:1MUX:

6.F(A,B,C,D)=∑m(1,3,4,11,12,13,14,15)
Solution:
Variables,n=4(A,B,C,D)Selectlines=n-1=3(S2,S1,S0)
2n-1to MUX i.e., 23to1=8 to1MUX
Inputlines=2n-1=23=8(D0, D1, D2, D3, D4, D5, D6, D7)

Implementation table:

MultiplexerImplementation:
7. ImplementtheBooleanfunctionusing8:1multiplexer.
F(A,B,C,D)=A’BD’+ACD+B’CD+A’C’D.
Solution:
Convert into standard SOP form,
=A‘BD‘(C‘+C)+ACD(B‘+B)+B‘CD(A‘+A)+A‘C‘D(B‘+B)
=A‘BC‘D‘+A‘BCD‘+AB‘CD+ABCD+A‘B‘CD+AB‘CD+A‘B‘C‘D
+A‘BC‘D
=A‘BC‘D‘+A‘BCD‘+AB‘CD+ABCD+A‘B‘CD+A‘B‘C‘D+A‘BC‘
D
=m4+m6+m11+m15+m3+m1+m5
=∑m(1,3,4,5,6,11,15)

Implementation table: Multiplexer Implementation:

8. Implement the Boolean function using 8:1multiplexer.

F(A,B,C,D)=AB’D+A’C’D+B’CD’+AC’D.
Solution:
Convert into standard SOP form,
=AB‘D(C‘+C)+A‘C‘D(B‘+B)+B‘CD‘(A‘+A)+AC‘D(B‘+B)
=AB‘C‘D+AB‘CD+A‘B‘C‘D+A‘BC‘D+A‘B‘CD‘+AB‘CD‘+AB‘C‘D+
ABC‘D
=AB‘C‘D+AB‘CD+A‘B‘C‘D+A‘BC‘D+A‘B‘CD‘+AB‘CD‘+ABC‘
D
 =m9+m11+m1+m5+m2+m10+m13
=∑m(1,2,5,9,10,11,13).
ImplementationTable:

Multiplexer Implementation:

9. Implement the Boolean function using 8:1 and also using 4:1multiplexer
F(w,x,y,z)=∑m(1,2,3,6,7,8,11,12,14)
Solution:
Variables,n=4(w,x,y,z)Select lines=n-1=3(S2,S1,S0)
2n-1toMUX i.e., 23to1=8to1 MUX
Inputlines=2n-1=23=8(D0,D1,D2,D3,D4,D5,D6,D7)
Implementation table:
 Multiplexer Implementation (Using 8:1 MUX):

(Using 4:1 MUX):

10. Implement the Boolean function using 8:1multiplexer

F(A,B,C,D)=∏m(0,3,5,8,9,10,12,14)
Solution:
Variables, n=4(A,B,C,D) Selectlines=n-1=3(S2,S1,S0)
2n-1toMUXi.e., 23 to1=8 to1MUX
Inputlines=2n-1=23=8(D0,D1,D2,D3,D4,D5,D6,D7)
Implementation table:
Multiplexer Implementation:

[Link] the Boolean function using 8:1multiplexer

F(A,B,C,D)=∑m(0,2,6,10,11,12,13)+d(3,8,14)
Solution:
Variables,n=4(A,B,C,D)Se lectlines=n-1=3(S2,S1,S0)
2n-1toMUXi.e., 23to1=8to1MUX
Inputlines=2n-1=23=8(D0,D1,D2,D3,D4,D5,D6,D7)
ImplementationTable:

Multiplexer Implementation:
 [Link] 8×1multiplexer has inputs A,B andC connected to the selection inputs S2, S1,
and S0 [Link] data inputs I0 to I7 are as follows
I1=I2=I7=0;I3=I5=1;I0=I4=DandI6=D'.
Determine the Boolean function that the multiplexer implements.
Implementationtable:

Multiplexer Implementation:

F(A,B,C,D)=∑m(3,5,6,8,11,12,13).

DEMULTIPLEXER:
Demultiplex means one into many. Demultiplexing is the process of taking
information from one input and transmitting the same over one of several outputs.
A demultiplexer is a combinational logic circuit that receives information on a single input
and transmits the same information over one of several (2n) output lines.
Block diagram mof demultiplexer
 The block diagram of a demultiplexer which is opposite to a multiplexer
[Link],‗n‘select signals and
2noutput signals. The select inputs determine to which output thedata input will
beconnected. As the serial data is changed to parallel data, i.e., the input
caused to
appearononeofthenoutputlines,thedemultiplexerisalsocalleda―datadistributer‖ ora
―serial-to-parallelconverter‖.

1-to-4Demultiplexer:

Logic Symbol
A 1-to 4 demultiplexer has a single input, Din, four outputs (Y0toY3) and two select
inputs(S1andS0
The input variable Dinhas a path to all four outputs, but the input
informationisdirectedtoonlyoneoftheoutputlines.Thetruthtableofthe1- to-4
demultiplexer isshownbelow
 Enabl S1 S0 Din Y0 Y1 Y2 Y3
e
0 x x x 0 0 0 0
1 0 0 0 0 0 0 0
1 0 B 0 1 1 , 0 0 0
1 0 1 0 0 0 0 0
1 0 1 1 0 1 0 0
1 1 0 0 0 0 0 0
1 1 0 1 0 0 1 0
1 1 1 0 0 0 0 0
1 1 1 1 0 0 0 1
Truthtableof1-to-4demultiplexer

Fromthetruthtable,itisclearthatthedatainput,DinisconnectedtotheoutputY0
,when S1=0and S0=0andthedatainputisconnectedtooutput Y1when S1= 0
andS0= 1. Similarly, the data input is connected to output Y2and Y3when S1=
1 and S0= 0and when S1= 1 and S0= 1, respectively. Also, from the truth table,
the expression foroutputscanbewrittenasfollows,

Y0=
S1’S0’DinY1=
S1’S0DinY2=S1S0

’Din
Y3=S1S0Din

Logic diagram of 1-to-4demultiplexer

Now,usingtheaboveexpressions,a1-to-4 demultiplexer canbe

implementedusingfour3-inputAND gatesand twoNOT gates.
Here,theinputdatalineDin,isconnectedto allthe
ANDgates.ThetwoselectlinesS1,S0enableonlyonegate at a
[Link]
atedoutputline.

1-to-8Demultiplexer:
A1-to-
8demultiplexerhasasingleinput,Din,eightoutputs(Y0toY7)andthreeselectinputs(S2,S
1andS0).Itdistributesoneinputlinetoeightoutputlinesbasedontheselectinputs
.Thetruthtableof1-to-8demultiplexerisshownbelow.

Din S S1 S0 Y Y Y Y Y Y Y Y
2 7 6 5 4 3 2 1 0
0 x x x 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 1
1 0 0 1 0 0 0 0 0 0 1 0
1 0 1 0 0 0 0 0 0 1 0 0
1 0 1 1 0 0 0 0 1 0 0 0
1 1 0 0 0 0 0 1 0 0 0 0
1 1 0 1 0 0 1 0 0 0 0 0
1 1 1 0 0 1 0 0 0 0 0 0
1 1 1 1 1 0 0 0 0 0 0 0
Truthtableof1-to-8demultiplexer
Fromtheabovetruthtable,itisclearthatthedatainputisconnectedwithoneoftheei
[Link],theexpressionforeightout
putscanbewrittenasfollows:
Y0=S2‘S1‘S0‘Din
Y1=S2‘S1‘S0Din
Y2=S2‘S1S0‘Din
Y3=S2‘S1S0Din
Y4=S2S1‘S0‘Din

Y5=S 2 S 1 ‘S 0

Y6=S2S1S0‘Din

Y7=S2S1S0Din
Now using the above expressions, the logic diagram of a 1-to-8 demultiplexer
can bedrawnas shown below. Here,the single data line, Dinis connectedto all
the eightANDgates, butonly oneof theeightANDgateswill be enabled by the
select input lines. Forexample, if S2S1S0= 000, then only AND gate-0 will be
enabled and thereby the
datainput,[Link],thedifferentcombinationsoftheselectinp
uts,theinputDinwillappearattherespectiveoutput.

Logicdiagramof1-to-8demultiplexer

1. Design1:8 demultiplexer using two1:4 DEMUX.

2. Implement full subtractor using demultiplexer.

Input Output
s s
A B Bi Difference(D Borrow(Bo
n ) ut)
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
3. Implement full subtractor using demultiplexer.

Input Output
s s
A B Bi Difference(D Borrow(Bo
n ) ut)
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

HDL (HARDWARE DESCRIPTION LANGUAGE)

In electronics, a Hardware description Language or HDLis any language from
a class of computer languages and /or programming languages for formal
description of digital logic and electronic circuits. HDLs are used to write
executable specifications of some piece of hardware. A simulation program,
designed to implement the underlying semantics of the language statements,
couples with simulating the progress of time, provides the hardware designer
with the ability to model a piece of hardware before it is created physically.
HDL MODELS OF COMBINATIONAL CIRCUITS.
The Verilog HDL model of a combinational circuit can be described in any one of
the following modeling styles,

 Gate leve lmodeling-using instantiations of predefined and user defined primitive

gates.
  Data flow modeling using continuous assignment with the keyword assign.
 Behavioral modeling using procedural assignment statements with the keyword
always.

 Gate level modeling

In this type, a circuit is specified by its logic gates and their interconnections. Gate
level modeling provides a textual description of a schematic diagram. The verilog
HDL includes 12 basic gates as predefined primitives. They are and, nand, or, nor,
xor, xnor, not & buf.

 Data flow modeling

Dataflow modeling of combinational logic uses a number of operators that act on

operands to produce desired results. Verilog HDL provides about 30 different
operators. Dataflow modeling uses continuous assignments and the keyword
assign. A continuous assignment is a statement that assigns a value to a net. The
data type family net is used to represent a physical connection between circuit
elements.

HDL for 2-to-4 line decoder

 Behavioral modeling

Behavioral modeling represents digital circuits at a functional and algorithmic

level. It is used mostly to describe sequential circuits, but can also be used to
describe combinational circuits. Behavioral descriptions use the keyword always,
followed by an optional event control expression and a list of procedural
assignment statements.

Code Conversion
Converting from one code form to another code form is called code conversion.
 Excess-3 code
Excess-3 is an on weighted code used to express decimal numbers. The code
derives its name from the fact that each binary code is the corresponding 8421code
plus 0011(3).

Example: 1000 of 8421=1011 in Excess-3

 Gray code
The gray code belongs to a class of codes called minimum change codes, in which
only one bit in the code changes when moving from one code to the next. The Gray
code is non-weighted code, as the position of bit does not contain any weight. In
digital Gray code has got a special place.

Decimal Binary Code Gray Code

Number
0 0000 0000
1 0001 0001
2 0010 0011
3 0011 0010
4 0100 0110
5 0101 0111
6 0110 0101
7 0111 0100
8 1000 1100
9 1001 1101
10 1010 1111
11 1011 1110

12 1100 1010
13 1101 1011
14 1110 1001
15 1111 1000
The gray code is a reflective digital code which has the special property that any
two subsequent numbers codes differ by only one bit. This is also called a unit-
distance code.
Important when an analog quantity must be converted to a digital representation.
Only one bit changes between two successive integers which are being coded.