DOWNLOAD LINK: Click here
ONLINE VIEW LINK: Click Here
The following doesnot contains images. To view completely download or view online using above links
UNIT I – BOOLEAN ALGEBRA AND COMBINATIONAL CIRCUITS
Boolean Variables & Truth Tables
Boolean
algebra differs in a major way from ordinary algebra in that Boolean constants
and variables are allowed to have only two possible values, 0 or 1.
Boolean 0 and 1 do not represent actual numbers but instead represent the state of a voltage variable, or what is called its logic level.
Boolean 0 and 1 do not represent actual numbers but instead represent the state of a voltage variable, or what is called its logic level.
Some
common representation of 0 and 1 is shown in the following diagram.
In
Boolean algebra, there are three basic logic operations: AND
,OR,
and NOT.
These logic gates are digital circuits constructed from diodes, transistors, and resistors connected in such a way that the circuit output is the result of a basic logic operation (OR, AND, NOT) performed on the inputs.
These logic gates are digital circuits constructed from diodes, transistors, and resistors connected in such a way that the circuit output is the result of a basic logic operation (OR, AND, NOT) performed on the inputs.
Truth Table
A
truth table is a means for describing how a logic circuit's output depends on
the logic levels present at the circuit's inputs.
In
the following twoinput logic circuit, the table lists all possible
combinations of logic levels present at inputs A and B along with the corresponding
output level X.
When
either input A OR B is 1, the output X is 1. Therefore the "?" in the
box is an OR gate.
OR Operation
The
expression X = A + B reads as "X equals A OR B". The + sign stands
for the OR operation, not for ordinary addition.
The
OR operation produces a result of 1 when any of the input variable is 1.
The
OR operation produces a result of 0 only when all the input variables are
0.
An
example of three input OR gate and its truth table is as follows:
With
the OR operation, 1 + 1 = 1, 1+ 1 + 1 = 1 and so on.
AND Operation
The
expression X = A * B reads as "X equals A AND B".
The multiplication sign stands for the AND operation, same for ordinary multiplication of 1s and 0s.The AND operation produces a result of 1 occurs only for the single case when all of the input variables are 1.The output is 0 for any case where one or more inputs are 0
The multiplication sign stands for the AND operation, same for ordinary multiplication of 1s and 0s.The AND operation produces a result of 1 occurs only for the single case when all of the input variables are 1.The output is 0 for any case where one or more inputs are 0
An
example of three input AND gate and its truth table is as follows:
With
the AND operation, 1*1 = 1, 1*1*1 = 1 and so on.
NOT Operation
The NOT operation is unlike the OR and AND
operations in that it can be performed on a single input variable. For
example, if the variable A is subjected to the NOT operation, the result x can
be expressed as x = A' where the prime (') represents the NOT operation. This
expression is read as:
x equals NOT A
x equals the inverse of A
x equals the complement of A
x equals NOT A
x equals the inverse of A
x equals the complement of A
Each
of these is in common usage and all indicate that the logic value of x = A' is
o pposite to the logic value of
A. The truth table of the NOT operation is as follows:
1'=0 because NOT 1 is 0
0' = 1 because NOT 0 is 1
0' = 1 because NOT 0 is 1
The
NOT operation is also referred to as inversion or complementation, and these
terms are used interchangeably.
NOR Operation
NOR
and NAND
gates are used extensively in digital circuitry. These gates combine the basic
operations AND,
OR
and NOT,
which make it relatively easy to describe then using Boolean algebra.
NOR
gate symbol is the same as the OR
gate symbol except that it has a small circle on the output. This
small circle represents the inversion operation. Therefore the output
expression of the two input NOR gate is:
X = (A + B)'
An
example of three inputs OR gate can be constructed by a NOR gate
plus a NOT
gate:
NAND Operation
NAND
gate symbol is the same as the AND gate symbol except that it has a
small circle on the output. This small circle represents the inversion
operation. Therefore the output expression of the two input NAND gate is:
X = (AB)'
Describing Logic Circuits Algebraically
Any
logic circuit, no matter how complex, may be completely described using the
Boolean operations, because the OR gate, AND gate, and NOT circuit are the basic building
blocks of digital systems.
This
is an example of the circuit using Boolean expression:
If an expression contains
both AND and OR operations, the AND operations are performed first (X=AB+C: AB
is performed first), unless there are parentheses in the expression, in which
case the operation inside the parentheses is to be performed first (X= (A+B)
+C: A+B is performed first).
Circuits containing Inverters
Whenever
an INVERTER
is present in a logiccircuit diagram, its output expression is simply equal to
the input expression with a prime (') over it.
Evaluating Logic Circuit Outputs
Once
the Boolean expression for a circuit output has
been obtained, the output logic level can be determined for any set of input
levels.
These
are two examples of the evaluating logic circuit output:
Let
A=0, B=1, C=1, D=1
X

=
A'BC (A+D)'

=
0'*1*1* (0+1)'


=
1 *1*1* (1)'


=
1 *1*1* 0


=
0

Let
A=0, B=0, C=1, D=1, E=1
X

=
[D+ ((A+B)C)'] * E

=
[1 + ((0+0)1 )'] * 1


=
[1 + (0*1)'] * 1


=
[1+ 0'] *1


=
[1+ 1 ] * 1


=
1

In general, the following
rules must always be followed when evaluating a Boolean expression:
1. First, perform all inversions of single terms; that is, 0 = 1 or 1 = 0.
2. Then perform all operations within parentheses.
3. Perform an AND operation before an OR operation unless parentheses indicate otherwise.
4. If an expression has a bar over it, perform the operations of the expression first and then invert the result.
1. First, perform all inversions of single terms; that is, 0 = 1 or 1 = 0.
2. Then perform all operations within parentheses.
3. Perform an AND operation before an OR operation unless parentheses indicate otherwise.
4. If an expression has a bar over it, perform the operations of the expression first and then invert the result.
Determining Output Level from a Diagram
The
output logic level for given input levels can also be determined directly from
the circuit diagram without using the Boolean expression.
Implementing Circuits from Boolean Expression
If
the operation of a circuit is defined by a Boolean expression, a logiccircuit
diagram can he implemented directly from that expression.
Suppose
that we wanted to construct a circuit whose output is y = AC+BC' + A'BC. This
Boolean expression contains three terms (AC, BC', A'BC), which are ORed
together. This tells us that a threeinput OR gate is required with inputs that
are equal to AC, BC', and A'BC, respectively.
Each
ORgate input is an AND product term, which means that an AND gate with
appropriate inputs can be used to generate each of these terms. Note the use of
INVERTERs to produce the A' and C' terms required in the expression.
Boolean Theorems
Investigating
the various Boolean theorems (rules) can help us to simplify logic expressions
and logic circuits.
Multivariable
Theorems
The
theorems presented below involve more than one variable:
(9)

x + y = y + x (commutative law)

(10)

x * y = y * x (commutative law)

(11)

x+ (y+z) = (x+y) +z = x+y+z (associative
law)

(12)

x
(yz) = (xy) z = xyz (associative law)

(13a)

x
(y+z) = xy + xz

(13b)

(w+x)(y+z) = wy + xy + wz + xz

(14)

x
+ xy = x [proof see below]

(15)

x
+ x'y = x + y

Proof of (14)
x
+ xy

=
x (1+y)

=
x * 1 [using theorem (6)]


=
x [using theorem (2)]

DeMorgan's Theorem
DeMorgan's
theorems are extremely
useful in simplifying expressions in which a product or sum of variables is
inverted. The two theorems are:
(16) (x+y)' = x' * y'
Theorem
(16) says that when the OR sum of two variables is inverted, this is the same
as inverting each variable individually and then ANDing these inverted
variables.
(17)
(x*y)' = x' + y'
Theorem
(17) says that when the AND product of two variables is inverted, this is the
same as inverting each variable individually and then ORing them.
Example
X

=
[(A'+C) * (B+D')]'

=
(A'+C)' + (B+D')' [by theorem (17)]


=
(A''*C') + (B'+D'') [by theorem (16)]


=
AC' + B'D

Three
Variables DeMorgan's Theorem
(18)
(x+y+z)' = x' * y' * z'
(19)
(xyz)' = x' + y' + z'
Universality of NAND & NOR Gates
It
is possible to implement any logic expression using only NAND
gates and no other type of gate. This is because NAND gates, in the proper
combination, can be used to perform each of the Boolean operations OR, AND, and
INVERT.
In
a similar manner, it can be shown that NOR gates can be arranged to implement
any of the Boolean operations.
Alternate Logic Gate Representations
The
left side of the illustration shows the standard symbol for each logic gate,
and the right side shows the alternate symbol. The alternate
symbol for each gate is obtained from the standard symbol by doing the
following:
1.
Invert each input and output of the standard symbol. This is done by adding bubbles (small circles) on input and output
lines that do not have bubbles, and by removing bubbles that are already there.
2.
Change the operation symbol from AND to OR, or from OR to AND. (In the special case of the
INVERTER, the operation symbol is not changed.)
Several
points should be stressed regarding the logic symbol equivalences:
1.
The equivalences are valid for gates with any number of inputs.
2.
None of the standard symbols have bubbles on their inputs, and all the
alternate symbols do.
3.
The standard and alternate symbols for each gate represent the same physical
circuit: there is no difference in the circuits represented by the two symbols.
4.
NAND and NOR gates are inverting gates, and so both the standard and alternate
symbols for each will have a bubble on either the input or the output. AND and
OR gates are noninverting gates, and so the alternate symbols for each will
have bubbles on both inputs and output.
Concept of Active Logic Levels:
When
an input or output line on a logic circuit symbol has no bubble on it, that
line is said to be activeHIGH. When an input or output line does have a bubble
on it, that line is said to be activeLOW. The presence or absence of a bubble,
then, determines the activeHIGH/activeLOW status of a circuit's inputs and
output, and is used to interpret the circuit operation.
Boolean Function
A Boolean function is an algebraic expression consists of binary
variables, the
constants 0 & 1, and the Boolean operators.For a set of given values
of the variables,
the function is evaluated to either 0 or 1
e.g. f = x • y + x • z’
The Boolean function f has 3 binaryvariables x, y
and z
The function is 1 if x and y are both 1 or if x is
1 and z is 0. Otherwise, f = 0
Operator Precedence
The operator
precedence is:
1.
Parentheses
2.
NOT
3.
AND
4.
OR
e.g. f = x • y + x
• z’
Precedence: z’, x
• y, x • z’, x • y + x • z’
e.g. f = (a +b) • (c+d’)
Precedence: a+b, d’, c+d’, (a +b) • (c+d’)
The parentheses precedence is the same as in normal algebra
Boolean Function
Truth Table
Boolean function can be represented by truth table as well.If the
function has n variables, its truth table will have 2^{n} rows
e.g. f = x • y + x • z’
f has 3
variables so 2^{3} combinations
f is 1 when the expression
is evaluated to 1 otherwise it is 0.
Minterm
In a Boolean function, a binary variable (x) may appear either in its
normal form (x) or in its complement form (x’).Consider 2 binary variables x
and y and an AND operation, there are 4 and only 4 possible combinations:
x’•y’, x’•y, x•y’ & x•y
Each of the 4 product terms is called a MINTERM or STANDARD PRODUCT
By definition, a Minterm is a product which consists of all the
variables in the normal form or the complement form but NOT BOTH.
e.g. for a function with 2 variables x and y:
x•y’ is
a minterm but x’ is NOT a minterm
e.g. for a function with 3 variables x, y andz:
x’yz’ is
a minterm but xy’ is NOT a minterm
Maxterm
Consider 2 binary variables x and y and an OR operation, there are 4 and
only 4
possible combinations: x’+y’, x’+y, x+y’, x+y.Each of the 4 sum terms is called a
MAXTERM or STANDARD SUM.By definition, a Maxterm is a sum in which each
variable appears once and only once either in its normal form or its complement
form but NOT BOTH.
Minterms and Maxterms for 3
Variables
Minterm Boolean
Expression
Boolean functions can be expressed with minterms,
e.g.f1(x,y,z) = m1
+ m4 + m6 = Î£m(1,
4, 6)
f2(x,y,z) = m2 + m4 + m6+ m7
= Î£m(2, 4, 6, 7)
Maxterm Boolean
Expression
Boolean functions can also be expressed with maxterms,
e.g.f1’ = x’y’z’+x’yz’+x’yz+xy’z+xyz
f1 = (x’y’z’+x’yz’+x’yz+xy’z+xyz)’
=
(x+y+z)(x+y’+z)(x+y’+z’)(x’+y+z’)(x’+y’+z’)
= M0•M2•M3•M5•M7
= Î M(0,
2, 3, 5, 7)
f2 = M0•M1•M3•M5
= Î M(0, 1, 3, 5)
Literal
A Literal is a variable
in a product or sum term
xy’ is a 2literal product term
x’yz has 3 literals
x’ + xy’ + x’yz is an expression of sum of products with 3 product terms.The
3 product terms have 1, 2 and 3 literals respectively
x’(x+y’)(x’+y+z) is an expression of product of sums.The 3 sum terms
have 1, 2 and 3 literals
Express Boolean
Functions in Minterms
If product terms in a Boolean function are not minterms, they can be
converted to minterms
e.g. f(a,b,c) = a’ + bc’ + ab’c
Function f has 3 variables, therefore, each minterm
must have 3 literals
Neither a’ nor bc’ are minterms.They can be converted to minterm.ab’c is
a minterm
Conversion to
Minterms
e.g.
f(a,b,c) = a’ + bc’ + ab’c
To
convert a’ to a minterm, the 2 variables (b, c) must be added, without changing
its
functionality
.Since a’=a’•1 & 1 = b+b’, a’= a’(b + b’) = a’b + a’b’
Similarly,
a’b = a’b(c + c’) = a’bc + a’bc’ and a’b’ = a’b’(c+c’) = a’b’c + a’b’c’
bc’ = bc’(a+a’) = abc’ + a’bc’
f = a’bc+a’bc’+a’b’c+a’b’c’+abc’+a’bc’+ab’c
Express Boolean
Functions in Maxterms
By using the Distribution Law: x+yz = (x+y)(x+z), a Boolean function can
be converted to an expression in product of maxterms
e.g. f(a,b,c) = a’+bc’
= (a’+b)(a’+c’) {not
maxterms}
= (a’+b+cc’)(a’+c’+bb’)
{cc’=0}
=
(a’+b+c)(a’+b+c’)(a’+c’+b)(a’+c’+b’)
= (a’+b+c)(a’+b+c’)(a’+c’+b’)
Boolean Function
Manipulation
Boolean functions can be manipulated with Boolean algebra.Manipulation
can transform logic expressions, but still keep the same logic functionality.Manipulation
can reduce the complexity, hence, easier to be implemented in hardware, i.e.
fewer logic gates
Boolean Function
Manipulation Example
f
= xy’ + xyz + x’z
= x(y’ + yz) + x’z {common factor}
=
x[(y’+y)(y’+z)] + x’z {Distribution law}
= x(y’+z) +
x’z {y’ + y = 1}
= xy’ + xz
+ x’z {Distribution law}
= xy’ + (x
+ x’)z {common factor}
= xy’ + z
{x + x’ = 1}
Simplify f1=abc+a’b+abc’ and f2=(a+b)’(a’+b’) to the minimum literals
f1 = abc+a’b+abc’ = ab(c+c’) + a’b = ab + a’b =
(a+a’)b = b
f2 =(a+b)’(a’+b’) = a’b’(a’+b’) {DeMorgan}
= a’b’a’+a’b’b’
= a’b’ + a’b’ = a’b’
QuineMcCluskey minimization method uses the same theorem
to produce the solution as the Kmap method, namely X(Y+Y')=X
 The expression is represented in the canonical
SOP form if not already in that form.
 The function is converted into numeric
notation.
 The numbers are converted into binary form.
 The minterms are arranged in a column divided
into groups.
 Begin with the minimization procedure.
 Each minterm of one group is compared with
each minterm in the group immediately below.
 Each time a number is found in one group which
is the same as a number in the group below except for one digit, the
numbers pair is ticked and a new composite is created.
 This composite number has the same number of
digits as the numbers in the pair except the digit different which is
replaced by an "x".
 The above procedure is repeated on the second
column to generate a third column.
 The next step is to identify the essential prime
implicants, which can be done using a prime implicant chart.
 Where a prime implicant covers a minterm, the
intersection of the corresponding row and column is marked with a cross.
 Those columns with only one cross identify the
essential prime implicants. > These prime implicants must be in the
final answer.
 The single crosses on a column are circled and
all the crosses on the same row are also circled, indicating that these
crosses are covered by the prime implicants selected.
 Once one cross on a column is circled, all the
crosses on that column can be circled since the minterm is now covered.
 If any nonessential prime implicant has all
its crosses circled, the prime implicant is redundant and need not be
considered further.
 Next, a selection must be made from the
remaining nonessential prime implicants, by considering how the
noncircled crosses can be covered best.
 One generally would take those prime
implicants which cover the greatest number of crosses on their row.
 If all the crosses in one row also occur on
another row which includes further crosses, then the latter is said to
dominate the former and can be selected.
 The dominated prime implicant can then be
deleted.
Find the minimal sum of products for the Boolean
expression,
f=(1,2,3,7,8,9,10,11,14,15), using
QuineMcCluskey method.
Firstly these minterms are represented in the binary form
as shown in the table below. The above binary representations are grouped into
a number of sections in terms of the number of 1's as shown in the table below.
Binary representation of minterms
Minterms

U

V

W

X

1

0

0

0

1

2

0

0

1

0

3

0

0

1

1

7

0

1

1

1

8

1

0

0

0

9

1

0

0

1

10

1

0

1

0

11

1

0

1

1

14

1

1

1

0

15

1

1

1

1

Group of minterms for different number of 1's
No of
1's

Minterms

U

V

W

X

1

1

0

0

0

1

1

2

0

0

1

0

1

8

1

0

0

0

2

3

0

0

1

1

2

9

1

0

0

1

2

10

1

0

1

0

3

7

0

1

1

1

3

11

1

0

1

1

3

14

1

1

1

0

4

15

1

1

1

1

Any two numbers in these groups which differ from each
other by only one variable can be chosen and combined, to get 2cell
combination, as shown in the table below.
2Cell combinations
Combinations

U

V

W

X

(1,3)

0

0



1

(1,9)



0

0

1

(2,3)

0

0

1



(2,10)



0

1

0

(8,9)

1

0

0



(8,10)

1

0



0

(3,7)

0



1

1

(3,11)



0

1

1

(9,11)

1

0



1

(10,11)

1

0

1



(10,14)

1



1

0

(7,15)



1

1

1

(11,15)

1



1

1

(14,15)

1

1

1



From the 2cell combinations, one variable and dash in the
same position can be combined to form 4cell combinations as shown in the
figure below.
Combinations

U

V

W

X

(1,3,9,11)



0



1

(2,3,10,11)



0

1



(8,9,10,11)

1

0





(3,7,11,15)





1

1

(10,11,14,15)

1



1



The cells (1,3) and (9,11) form the same 4cell combination
as the cells (1,9) and (3,11). The order in which the cells are placed in a
combination does not have any effect. Thus the (1,3,9,11) combination could be
written as (1,9,3,11).
From above 4cell combination table, the prime implicants
table can be plotted as shown in table below.
Prime Implicants Table
Prime
Implicants

1

2

3

7

8

9

10

11

14

15

(1,3,9,11)

X



X





X



X





(2,3,10,11)



X

X







X

X





(8,9,10,11)









X

X

X

X





(3,7,11,15)













X

X

X

X



X

X



X

X







X



The columns having only one cross mark correspond to
essential prime implicants. A yellow cross is used against every essential
prime implicant. The prime implicants sum gives the function in its minimal SOP
form.
Y = V'X + V'W + UV' + WX + UW
Logic
Combinational logic blocks
have the outputs depending on the combinations of the current inputs. Sequential logic blocks
have the outputs depending on the current inputs as well as any previous
inputs.
Binary Adder
Binary Adder is for binary number addition
Logic Circuit to be discussed:
§
Half Adder
§
Full Adder
§
Ripple Adder
§
Carry Look Ahead Adder
§
Half Adder
 Half adder is
for addition of 2 single bits
 It has two
1bit inputs and two 1bit outputs
 The inputs are
the 2 bits to be added (a, b)
 The outputs
are 1bit sum (s) & 1bit carry (c)
The logic is:
Binary
Addition
The half adder adds 2 singlebit inputs
It cannot complete a full addition
To complete a full addition, the adder needs to take in 3 inputs: a, b and the carry from the previous bit.
Full
Adder
To carry the addition, an adder with 3 inputs is required.
A Full Adder takes in 3 inputs (a, b and ci) and produces 2 outputs (s, co) a & b are the
2 bits to be added, ci is the carry input (carry over from the previous bit) and co is the carry output (to
the next bit)
Logic
for Full Adder
Logic equations derived from the truth table:
s = a Ã… b Ã… ci
co = ab + bci + aci
Full Adder
The below implementation shows implementing the full adder
with ANDOR gates, instead of using XOR gates. The basis of the circuit below
is from the above Kmap.
CircuitSUM
CircuitCARRY
Full adder
can be built from 2 half adders
s = a Ã… b Ã… ci
co = ab+bci+aci
= ab+(a’bci+abci)+(abci+ab’ci)
= ab + abci + ci (a’b+ab’) = ab + ci (a Ã… b)
nbit Ripple Adder
To perform an addition of 2
nbit numbers An1…A1A0 & Bn1…B1B0, where An1 & Bn1 are theMSB &
A0B0 are the LSB, we need a nbit adder,which can be built from ‘n ‘fulladders
Ripple Adder:
Carry ripples through the chain
CarryLookAhead Adder
The delay generated by an Nbit adder is proportional to
the length N of the two numbers X and Y that are added because the carry
signals have to propagate from one fulladder to the next. For large values of
N, the delay becomes unacceptably large so that a special solution needs to be
adopted to accelerate the calculation of the carry bits. This solution involves
a "lookahead carry generator" which is a block that simultaneously
calculates all the carry bits involved. Once these bits are available to the
rest of the circuit, each individual threebit addition (X_{i}+Y_{i}+carryin_{i})
is implemented by a simple 3input XOR gate. The design of the lookahead carry
generator involves two Boolean functions named Generate and Propagate. For each
input bits pair these functions are defined as:
Gi = X_{i} . Y_{i}
Pi = X_{i} + Y_{i}
The carry bit cout(i) generated when adding two bits Xi
and Yi is '1' if the corresponding function Gi is '1' or if the cout(i1)='1'
and the function Pi = '1' simultaneously. In the first case, the carry bit is
activated by the local conditions (the values of Xi and Yi). In the second, the
carry bit is received from the less significant elementary addition and is
propagated further to the more significant elementary addition. Therefore, the
carry_out bit corresponding to a pair of bits Xi and Yi is calculated according
to the equation:
carry_out(i) = Gi + Pi.carry_in(i1)
For a fourbit adder the carryouts are calculated as
follows
carry_out0 = G_{0} + P_{0} . carry_in_{0}
carry_out1 = G_{1} + P_{1} . carry_out_{0}
= G_{1} + P_{1}G_{0} + P_{1}P_{0} .
carry_in_{0}
carry_out2 = G_{2} + P_{2}G_{1} + P_{2}P_{1}G_{0}
+ P_{2}P_{1}P_{0} . carry_in_{0}
carry_out3 = G_{3} + P_{3}G_{2} + P_{3}P_{2}G_{1}
+ P_{3}P_{2}P_{1}G_{0} + P_{3}P_{2}P_{1}
. carry_in_{0}
The set of equations above are
implemented by the circuit below and a complete adder with a lookahead carry
generator is next. The input signals need to propagate through a maximum of 4
logic gate in such an adder as opposed to 8 and 12 logic gates in its
counterparts illustrated earlier.
Pi is called Carry Propagate
Gi is called Carry Generate
With Pi and Gi, we obtain the
sum & carry for the full adder:
Ci+1= Gi + PiCi
C1 = G0 + P0C0
C2
= G1 + P1C1
= G1 + P1(G0 + P0C0)
= G1 + P1G0 + P1P0C0
C3 = G2 + P2C2
= G2 + P2(G1 + P1G0 + P1P0C0)
= G2 + P2G1 + P2P1G0 + P2P1P0C0
Carry no longer depend on its
previous stage
LookAhead
Carry Generator
Speed: 2 gate delays for
all carry
Cost: more gates
Sums can be calculated from the following equations, where
carryout is taken from the carry calculated in the above circuit.
sum_out_{0} = X_{ 0} Y_{0} carry_out_{0}
sum_out_{1} = X_{ 1} Y_{1} carry_out_{1}
sum_out_{2} = X_{ 2} Y_{2} carry_out_{2}
sum_out_{3} = X_{ 3} Y_{3} carry_out_{3}
MSI Adder
Adders
are available in Medium Scale Integration (MSI) devices
Both
TTL and CMOS are available, e.g.
74183: TTL 1bit Full Adder
7482: TTL 4bit CarryLookAhead Adder
4008: CMOS 4bit CarryLookAhead Adder
74182: 4bit LookAhead Carry Generator
4bit
Addition
To add 2 4bit
numbers: Z = X + Y
8bit
Addition
To
add 2 8bit numbers: Z = X + Y
Subtractor
Subtractor circuits take two binary numbers as input and
subtract one binary number input from the other binary number input. Similar to
adders, it gives out two outputs, difference and borrow (carryin the case of
Adder). There are two types of subtractors.
 Half Subtractor
 Full Subtractor
Half Subtractor
The halfsubtractor is a combinational circuit which is
used to perform subtraction of two bits. It has two inputs, X (minuend) and Y
(subtrahend) and two outputs D (difference) and B (borrow). The logic symbol
and truth table are shown below.
Symbol
Truth Table
X

Y

D

B

0

0

0

0

0

1

1

1

1

0

1

0

1

1

0

0

From the above table we can draw the Kmap as shown below
for "difference" and " borrow".
The boolean expression for the difference and Borrow can be written.
From the equation we can draw
the halfsubtractor as shown in the figure below.
Full Subtractor
A full subtractor is a
combinational circuit that performs subtraction involving three bits, namely minuend,
subtrahend, and borrowin. The logic symbol and truth table are shown below.
Symbol
Truth Table
X

Y

Bin

D

Bout

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

From above table we can draw the
Kmap as shown below for "difference" and "borrow".
The boolean expression for difference and borrow can be
written as
D = X'Y'Bin + X'YBin' + XY'Bin' +
XYBin
= (X'Y' + XY)Bin + (X'Y + XY')Bin'
= (X Y)'Bin + (X Y)Bin'
= X Y Bin
Bout =
X'.Y + X'.Bin + Y.Bin
From the equation we can draw the
fullsubtractor as shown in figure below.
Fullsubtractor circuit is more
or less same as a fulladder with slight modification.
Parallel Binary
Subtractor
Parallel binary subtractor can be implemented by cascading
several fullsubtractors. Implementation and associated problems are those of a
parallel binary adder, seen before in parallel binary adder section.
Below
is the block level representation of a 4bit parallel binary subtractor, which
subtracts 4bit Y3Y2Y1Y0 from 4bit X3X2X1X0. It has 4bit difference output
D3D2D1D0 with borrow output Bout.
A serial subtractor can be obtained by converting the
serial adder using the 2's complement system. The subtrahend is stored in the Y
register and must be 2's complemented before it is added to the minuend stored
in the X register.
The circuit for a 4bit serial subtractor using fulladder
is shown in the figure below.
Comparator
Comparator compares binary
numbers.
Logic
comparing 2 bits: a and b
Magnitude Comparator
Comparator
compares binary numbers
4bit
Magnitude Comparator:
Inputs:
A3A2A1A0 & B3B2B1B0
Outputs: Y _{A>B}, Y _{A, Y A=B}
For each bit, let:
Si = AiBi + Ai’Bi’ = (AiBi’ + Ai’Bi)’
Si is true when Ai = Bi
For A = B, we must
have:
A3=B3 and A2=B2 and A1=B1
and A0=B0
Hence,
Y _{A=B} = S3•S2•S1•S0 136
Logic For A > B
For
A > B, there are 4 cases:
1.
A_{3}B_{3}
is 10 and A_{2}A_{1}A_{0 }& B_{2}B_{1}B_{0}
can be anything:
A=1xxx, B=0xxx
2.
A_{3}=B_{3 }and
A_{2}B_{2} is 10 and A_{1}A_{0} & B_{1}B_{0}
can be
anything: A=11xx, B=10xx or
A=01xx, B=00xx
3.
A_{3}=B_{3}
and A_{2}=B_{2} and A_{1}B_{1}=10 and A_{0}B_{0}
is xx: e.g.
A=011x, B=010x
4.
A3=B3 and A2=B2 and
A1=B1 and A0B0 is 10: e.g.
A=1011, B=1010
Y _{A>B}=A_{3}B_{3}’+S_{3}A_{2}B_{2}’+S_{3}S_{2}A_{1}B_{1}’+S_{3}S_{2}S_{1}A_{0}B_{0}’
Logic For A < B
For A < B,
there are also 4 cases:
1)
A_{3}B_{3 }is
01 and A_{2}A_{1}A_{0} & B_{2}B_{1}B_{0
}can be anything:
1.
A=0xxx, B=1xxx
2)
A_{3}=B_{3 }and
A_{2}B_{2} is 01 and A_{1}A_{0} & B_{1}B_{0}
can be
1.
anything: A=10xx,
B=11xx or A=00xx, B=01xx
3)
A_{3}=B_{3}
and A_{2}=B_{2} and A_{1}B_{1}=01 and A_{0}B_{0}
is xx: e.g.
1.
A=110x, B=111x
4)
A3=B3 and A2=B2 and
A1=B1 and A0B0 is 01: e.g.
1.
A=1000, B=1001
Y _{A=A3 ’B3+S3A2
’B2+S3S2A1 ’ B1+S3S2S1A0
’ B0}
4bit
Comparator Logic Circuit
MSI:
7485 4bit Magnitude Comparator
Comparison
of 4bit Numbers
Comparison
of 8  bit Numbers
Decoder
A decoder is a multipleinput, multipleoutput logic
circuit that converts coded inputs into coded outputs, where the input and
output codes are different.Binary Decoder has n inputs and 2^{n}outputs also called as nto2^{n} decoder. Inputs have all the 2^{n} combinations and the
corresponding output will be activated for each input combinations.Decoding is
necessary in applications such as data multiplexing, 7 segment display and
memory address decoding. Enable inputs must be on for the decoder to function,
otherwise its outputs assume a single "disabled" output code word.
Figure below shows the pseudo block of a decoder.
A binary decoder has n inputs and 2^{n} outputs.
Only one output is active at any one time, corresponding to the input value.
Figure below shows a representation of Binary nto2^{n} decoder
e.g. 3to8 decoder has 3 inputs and 8 outputs
3to8
Decoder
Function Table
3to8
Decoder Logic Circuit
2to4
Decoder with Output Enable
Implement
Logic Function with Decoder
 Any nvariable logic
function, in canonical sumofminterms form can be implemented using a
single nto2^{n} decoder to generate the minterms, and an OR gate
to form the sum.
 The output lines of the
decoder corresponding to the minterms of the function are used as inputs
to the or gate.
 Any combinational
circuit with n inputs and m outputs can be implemented with an nto2^{n}
decoder with m OR gates.
Suitable when a circuit has many
outputs, and each output function is expressed with few minterms.
(Ex) Full adder using decoder
S(x, y, z) = (1,2,4,7)
C(x, y, z) = (3,5,6,7)
Truth Table
X

Y

Z

C

S

0

0

0

0

0

0

0

1

0

1

0

1

0

0

1

0

1

1

1

0

1

0

0

0

1

1

0

1

1

0

1

1

0

1

0

1

1

1

1

1

From the truth table we know the
values for which the sum (s) is active and also the carry (c) is active. Thus
we have the equation as shown above and a circuit can be drawn as shown below
from the equation derived.
Use a 3to8 decoder to implement:
f = x’y’z + xy’z + xyz
(m1
+ m5 + m7)
MSI
Decoders
 2to4 Decoder
 3to8 Decoder
 4to16 Decoder
 BCDtoDecimal Decoder
 BCDtoSevenSegment Decoder
e.g. Low Power Schottky TTL:
74LS138 3to8 Decoder where G1, G2A and G2B are
enable pins
Logic Symbol
74LS138
3to8 Decoder
Implement
Logic Function with74LS138
Use a 3to8 decoder to implement:
f = x’y’z + xy’z + xyz
(m1
+ m5 + m7)
4to16
Decoder
Use 2 3to8 decoders
Inputs: D, C, B, A
Outputs: Y0 – Y15
When D = 0, top decoder is enabled
When D = 1,bottom decoderis enabled
En’ is enable
Binary Encoders
An encoder is a combinational circuit that performs the
inverse operation of a decoder. If a device output code has fewer bits than the
input code has, the device is usually called an encoder. e.g. 2^{n}ton,
priority encoders.
The simplest encoder is a 2^{n}ton
binary encoder, where it has only one of 2^{n} inputs = 1 and the
output is the nbit binary number corresponding to the active input. It
can be built from OR gates
e.g.
4to2 Encoder
OctaltoBinary Encoder
OctaltoBinary take 8 inputs and provides 3 outputs, thus
doing the opposite of what the 3to8 decoder does. At any one time, only one
input line has a value of 1. The figure below shows the truth table of an
Octaltobinary encoder.
Truth Table
I0

I1

I2

I3

I4

I5

I6

I7

Y2

Y1

Y0

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

For an 8to3 binary encoder with inputs I0I7 the logic
expressions of the outputs Y0Y2 are:
Y0 = I1 + I3 + I5 + I7
Y1= I2 + I3 + I6 + I7
Y2 = I4 + I5 + I6 +I7
Based on the above equations, we can draw the circuit as
shown below
Priority
Encoder
If more then two inputs are active simultaneously, the
output is unpredictable or rather it is not what we expect it to be.This
ambiguity is resolved if priority is established so that only one input is
encoded, no matter how many inputs are active at a given point of time. The
priority encoder includes a priority function. The operation of the priority
encoder is such that if two or more inputs are active at the same time, the
input having the highest priority will take precedence.
e.g. 4to2 PriorityEncoder
A3 has the highest priority
A0 has the lower priority
74148
8to3 Priority Encoder
16to4 Priority Encoder
Cascade two
74148 8to3 priority encoders. The Input 15 has highest priority
Multiplexer
A
multiplexer (MUX) is a digital switch which connects data from one of n sources
to the output. A number of select inputs determine which data source is
connected to the output. The block diagram of MUX with n data sources of b bits
wide and s bits wide select line is shown in below figure.
MUX acts
like a digitally controlled multiposition switch where the binary code applied
to the select inputs controls the input source that will be switched on to the
output as shown in the figure below. At any given point of time only one input
gets selected and is connected to output, based on the select input signal.
The operation of a multiplexer can be better explained
using a mechanical switch as shown in the figure below. This rotary switch can
touch any of the inputs, which is connected to the output. As you can see at
any given point of time only one input gets transferred to output.
2x1 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.
Design of a 2:1 Mux
To derive the gate level implementation of 2:1 mux we need
to have truth table as s hown in
figure. And once we have the truth table, we can draw the Kmap as shown in
figure for all the cases when Y is equal to '1'.
Combining the two 1' as shown in figure, we can drive the
output y as shown below
Y = A.S’ + B.S
Truth Table
B

A

S

Y

0

0

0

0

0

0

1

0

0

1

0

1

0

1

1

0

1

0

0

0

1

0

1

1

1

0

1


1

1

1

1

Kmap
Circuit
MSI MUX
74150: 16to1
74153: Dual 4to1
74157: Quad 2to1
74151: 8to1
16to1 MUX
Use two 74151
D = 0 enables top MUX
D = 1
enables bottom MUX
W = Y’
= (Y1+Y2)’
= (W1’+W2’)’
= W1W2
Larger multiplexers can be constructed from smaller ones.
An 8to1 multiplexer can be constructed from smaller multiplexers as shown
below.
8to1 multiplexer from Smaller
MUX
16to1 multiplexer from 4:1
mux
Quadruple 2to1 MUX
It is 2to1 MUX with 4 bits for
each input
There is 1 output of 4 bits
There is 1 select signal
When 1
input is selected, the whole group of 4 bits goes to the output
Quad 2to1 MUX
Any nvariable logic function can be implemented using a
smaller 2^{n1}to1 multiplexer and a single inverter (e.g 4to1 mux
to implement 3 variable functions) as follows.
Express function in canonical sumofminterms form. Choose
n1 variables as inputs to mux select lines. Construct the truth table for the
function, but grouping inputs by selection line values (i.e select lines as
most significant inputs).
Determine multiplexer input line i values by comparing the
remaining input variable and the function F for the corresponding selection
lines value i.
We have four possible mux input line i values:
·
Connect to 0 if the
function is 0 for both values of remaining variable.
·
Connect to 1 if the
function is 1 for both values of remaining variable.
·
Connect to remaining
variable if function is equal to the remaining variable.
·
Connect to the
inverted remaining variable if the function is equal to the remaining variable
inverted
3variable Function Using 8to1 mux
Implement the function F(X,Y,Z) = S(1,3,5,6) using an
8to1 mux. Connect the input variables X, Y, Z to mux select lines. Mux data
input lines 1, 3, 5, 6 that correspond to the function minterms are connected
to 1. The remaining mux data input lines 0, 2, 4, 7 are connected to 0.
3variable Function Using 4to1 mux
Implement the function F(X,Y,Z)
= S(0,1,3,6) using a single 4to1 mux and an inverter. We choose the two most
significant inputs X, Y as mux select lines.
Truth Table
Select i

X

Y

Z

F

Mux Input i


0

0

0

0

1

1


0

0

0

1

1

1


1

0

1

0

0

Z


1

0

1

1

1

Z


2

1

0

0

0

0


2

1

0

1

0

0


3

1

1

0

1

Z'


3

1

1

1

0

Z'


We determine multiplexer input line i values by comparing
the remaining input variable Z and the
function F for the corresponding selection lines value i
·
when XY=00 the
function F is 1 (for both Z=0, Z=1) thus mux input0 = 1
·
when XY=01 the
function F is Z thus mux input1 = Z
·
when XY=10 the
function F is 0 (for both Z=0, Z=1) thus mux input2 = 0
·
when XY=11 the
function F is Z' thus mux input3 = Z'
Example for logic
function implementation using MUX
Demultiplexers
They are digital switches which connect data from one input
source to one of n outputs.Usually implemented by using nto2^{n}
binary decoders where the decoder enable line is used for data input of the
demultiplexer.The figure below shows a demultiplexer block diagram which has
got sbitswide select input, one bbitswide data input and n bbitswide
outputs.
The operation of a demultiplexer can be better explained
using a mechanical switch as shown in the figure below. This rotary switch can
touch any of the outputs, which is connected to the input. As you can see at
any given point of time only one output gets connected to input.
1to4 Demultiplexer
Truth Table
