Digital Electronics I Lecture Notes

Chapter 1

NUMBER SYSTEMS AND CODES

1.1 Introduction

Digital quantities can only take on discrete values while analog quantities vary over
a continuous range of values. Examples of analog quantities include temperature,
speed. A digital system is a combination of devices designed to manipulate phys-
ical quantities that are represented in digital form as opposed to analog systems
which manipulate systems which are represented in analog form. Examples of dig-
ital systems include electronic calculators, digital watches, digital voltmeters and
digital computers. Examples of analog devices include pointer-type instruments like
speedometers, voltmeters, analog computers, etc. Advantages of digital systems over
analog quantities are:

• They are easier to design than analog systems.

• Easy to store large quantities of information.

• Accuracy and precision are greater

• digital circuits are less affected by noise.

1.2 Number Systems

All number systems are based on an ordered set of numbers called digits. The total
number of digits used in a system is called the base or radix of the system e.g. base
10 (or radix 10) uses then ten digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9. The four number
systems that are used in digital systems are:

i) Decimal - Used in everyday calculations

Page 1 of 110
112
 Digital Electronics I Lecture Notes

ii) Binary - Used in all digital systems, including digital computers

iii) Octal

iv) Hexadecimal - This number system, along with the Octal system are used as
shorthand notation for the Binary number system.

1.3 Decimal System

This is a positional-value system, that is, the value of a digit depends on its position in
the number. It is possible to design a digital system with ten states (decimal) but this
would not be easy to design as it would mean designing a circuit with ten discrete
voltage levels.
PSfrag replacements

1.4 Binary System

This is known as Base 2 or Radix 2. Uses only two digits, 0 and 1. In digital systems,
these two digits are known as bits. The binary system is a positional value system,
with the weights weights as shown in Figure 1.1.

· · · 23 22 21 20 2−1 2−2 2−3 2−4 · · ·

binary point

Figure 1.1: Weighting factors for the binary number system

1.4.1 Binary to Decimal Conversion

The decimal equivalent of the binary number an an−1 · · · a1 a0 .a−1 a−2 · · · a−m is given
by:

(2n × an ) + (2n−1 × an−1 ) + · · · + (21 × a1 ) + (20 × a0 ) + (2−1 × a−1 ) + · · · + (2−m × a−m )

Example:

1010.1012 = (23 ×1)+(22 ×0)+(21 ×1)+(20 ×0)+(2−1 ×1)+(2−2 ×0)+(2−3 ×1) = 10.62510

Page 2 of 110
112
 Digital Electronics I Lecture Notes

1.4.2 Decimal to Binary Conversion

Integers For integers, we use repeated division by 2 (also known as successive divi-
sion by 2). The example shown on Figure 1.2 shows how to apply this method
PSfrag replacements
to convert 5310 to binary.

2 53
2 26 R1
2 13 R0
2 06 R1
2 03 R0
2 01 R1
00 R1

Figure 1.2: Example illustrating successive division by 2

The binary number is read in the direction shown by the arrow (upwards). In
this case, we can see that 5310 = 1101012

Fractions In this case we use repeated (or successive) multiplication by 2. The table
below shows this procedure to convert 0.812510 to binary.

DECIMAL BINARY
0.8125 × 2 = 1.625
1.625 − 1 = 0.625 1
0.625 × 2 = 1.250
1.250 − 1 = 0.250 1
0.250 × 2 = 0.500
0
0.500 × 2 = 1
1−1 = 0 1

In this case, the binary number is read downwards, so 0.812510 = 0.11012 .

Note that in some cases, the decimal fraction cannot be represented in a finite
number of bits - in this case, we have to truncate the binary number at some
point e.g. conversion of 0.48510 to binary:

Page 3 of 110
112
 Digital Electronics I Lecture Notes

DECIMAL BINARY
0.485 × 2 = 0.970
0
0.970 × 2 = 1.940
1.940 − 1 = 0.940 1
0.940 × 2 = 1.880
1.880 − 1 = 0.880 1
0.880 × 2 = 1.760
1.760 − 1 = 0.760 1
0.760 × 2 = 1.520
1.520 − 1 = 0.520 1
0.520 × 2 = 1.040
1.040 − 1 = 0.040 1
0.040 × 2 = 0.080
0
0.080 × 2 = 0.160
0
.. ..
. .

From the above computations, we can see that 0.48510 cannot be represented in
binary using a finite number of bits, hence 0.48510 = 0.01111100 · · · . Normally,
the conversion in such cases is done until the required number of decimal places
is obtained. To four decimal places, we can write that 0.48510 = 0.01112 , to eight
PSfragdecimal places: 0.48510 = 0.01111100, and so on.
replacements

1.5 Octal System

This is base 8 system, and it uses the eight digits 0, 1, 2, 3, 4, 5, 6 and 7. The
weighting factors are shown in Figure 1.3.

· · · 83 82 81 80 8−1 8−2 8−3 8−4 · · ·

octal point

Figure 1.3: Weighting factors for the octal number system

1.5.1 Octal to Decimal Conversion

The decimal equivalent of the octal number an an−1 · · · a1 a0 .a−1 a−2 · · · a−m is given by:

(8n × an ) + (8n−1 × an−1 ) + · · · + (81 × a1 ) + (80 × a0 ) + (8−1 × a−1 ) + · · · + (8−m × a−m )

Example:

125.368 = (82 × 1) + (81 × 2) + (80 × 5) + (8−1 × 3) + (8−2 × 6) = 85.4687510

Page 4 of 110
112
 Digital Electronics I Lecture Notes

1.5.2 Decimal to Octal Conversion

Integers For integers, we use repeated (successive) division by 8. The example

shownPSfrag replacements
on Figure 1.4 shows how to apply this method to convert 45910 to octal.

8 459
8 57 R3
8 07 R1
00 R7

Figure 1.4: Example illustrating successive division by 8

The octal number is read in the direction shown by the arrow (upwards). In
this case, we can see that 45910 = 7138 .

Fractions In this case we use repeated (or successive) multiplication by 8. The table
below shows this procedure to convert 0.7812510 to octal.

DECIMAL OCTAL
0.78125 × 8 = 6.25
6.25 − 6 = 0.25 6
0.25 × 8 = 2.00
2−2 = 0 2

In this case, the octal number is read downwards, so 0.7812510 = 0.628 .

Exercise
Show that 0.48510 expressed in octal to six decimal places equals 0.3702438 .

1.5.3 Octal to Binary Conversion

The procedure here is to convert each octal digit to its 3-bit binary equivalent then to
juxtapose these codes to give us the equivalent binary code. The 3-bit binary codes
corresponding to the octal digits are shown on the table below:

OCTAL BINARY
0 000
1 001
2 010
3 011
4 100
5 101
6 110
7 111

Page 5 of 112
110
 Digital Electronics I Lecture Notes

As an example, suppose we would like to convert 713.628 to binary. From the above
table, we can see that the 3-bit binary codes for 7, 1, 3, 6 and 2 are respectively 111,
001, 011, 110 and 010. We can therefore directly write that 713.628 = 111001011.1100102.

1.5.4 Binary to Octal conversion

In this case, we divide the binary number in groups of 3 bits, starting from the binary
point. We then use the table shown in the previous section to get the corresponding
octal digits. As an example, suppose we want to convert 10111101.11112 to octal. The
procedure is illustrated on Figure 1.5.

Divide into groups

of 3 bits on each
side of binary point
10111101.1111
one zero two zeros
added to added to
make 3 bits make 3 bits
0 1 0 1 1 1 1 0 1. 1 1 1 1 0 0

2 7 5 7 4

Figure 1.5: Binary to octal conversion

Hence 10111101.11112 = 275.748 .

We can see that it is very easy to perform binary to octal operation and vice-versa.

1.6 Hexadecimal Number System

The hexadecimal number system uses 16 digits, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D,

E and F. The table below shows the correlation between these digits and the decimal,
(4-bit) binary and octal systems.

Page 6 of 110
112
 Digital Electronics I Lecture Notes

HEXADECIMAL DECIMAL BINARY OCTAL

0 0 0000 0
1 1 0001 1
2 2 0010 2
3 3 0011 3
4 4 0100 4
5 5 0101 5
6 6 0110 6
7 7 0111 7
8 8 1000 10
9 9 1001 11
PSfrag replacements A 10 1010 12
B 11 1011 13
C 12 1100 14
D 13 1101 15
E 14 1110 16
F 15 1111 17

The weighting factors are shown in Figure 1.6.

··· 163 162 161 160 16−1 16−2 16 16

−3 −4 · · ·

hexadecimal point

Figure 1.6: Weighting factors for the hexadecimal number system

1.6.1 Hexadecimal to Decimal Conversion

The decimal equivalent of the hexadecimal number an an−1 · · · a1 a0 .a−1 a−2 · · · a−m is
given by:

(16n × an ) + · · · + (161 × a1 ) + (160 × a0 ) + (16−1 × a−1 ) + · · · + (16−m × a−m )

Example:

2EA.B16 = (162 × 2) + (161 × 14) + (160 × 10) + (16−1 × 11) = 746.687510

1.6.2 Decimal to Hexadecimal Conversion

Integers For integers, we use repeated (successive) division by 16. Note that when
a remainder exceeds 9, we replace it with the corresponding hexadecimal digit
as shown in the above table. The example shown on Figure 1.7 shows how to
apply this method to convert 42810 to hexadecimal.
The hexadecimal number is read in the direction shown by the arrow (upwards).
In this case, we can see that 42810 = 1AC16 .

Page 7 of 110
112
 Digital Electronics I Lecture Notes

16 428
16 26 R 12
16 01 R 10
00 R1

Figure 1.7: Example illustrating successive division by 16

Fractions In this case we use repeated (or successive) multiplication by 16. The
table below shows this procedure in converting 0.7539062510 .

DECIMAL HEXADECIMAL
0.75390625 × 16 = 12.0625
12.0625 − 12 = 0.0625 12 = C
0.0625 × 16 = 1.00
1−1=0 1

In this case, the hexadecimal number is read downwards, so 0.7539062510 =

0.C116 .
Exercise
Show that 0.48510 expressed in hexadecimal to five decimal places equals 0.7C28F16 .

1.6.3 Hexadecimal to Binary Conversion

The procedure is similar to that of Octal to Binary conversion, the only difference
being that we first convert each hexadecimal digit into 4-bit binary. The 4-bit binary
codes representing each hexadecimal digit are tabulated at the beginning of this
section.
As an example, suppose we want to convert 2EA.B16 to binary. From the above table,
we can see that the 4-bit binary codes for 2, E, A, and B are respectively 0010, 1110,
1010 and 1011 so we can therefore directly write that 2EA16 = 001011101010.10112.

1.6.4 Binary to Hexadecimal conversion

In this case, we divide the binary number in groups of 4 bits, starting from the bi-
nary point. We then use the table shown at the beginning of this section to get
the corresponding hexadecimal digits. As an example, suppose we want to convert
110110011.010112 to octal. The procedure is illustrated on Figure 1.8 below.
Hence 110110011.010112 = 1B3.5816 .

110
Page 8 of 112
 Digital Electronics I Lecture Notes

Divide into groups

of 4 bits on each
side of binary point
110110011.01011
three zeros three zeros
added to added to
make 4 bits make 4 bits
0 0 0 1 1 0 1 1 0 0 1 1 . 0 1 0 1 1 0 0 0

1 B 3 5 8

Figure 1.8: Binary to hexadecimal conversion

1.7 Signed Binary Numbers

Our discussion so far has assumed that we are dealing with positive numbers. The
binary numbers discussed so far are known as unsigned binary numbers.
Digital systems represent all information with binary digits (bits 0,1). Since digital
computers and calculators handle negative as well as positive numbers, some means
is required for representing the sign of the number (+ or -). This is done by the use
of a sign bit. The most significant bit of a binary number is used to denote the sign
of the number.
There are three notations that are commonly used representing signed numbers.
These are:

i) Sign-Magnitude Notation

ii) Ones (1’s) Complement Notation

iii) Twos (2’s) Complement Notation

In all these notations, positive numbers have the Most Significant Bit (MSB) as zero,
while negative numbers have an MSB of 1.

1.7.1 Sign-Magnitude Notation

To obtain the sign-magnitude notation of a given number, we first obtain its unsigned
binary equivalent using the methods described in the previous sections. If the num-
ber is positive, we then add a zero (0) to become the MSB, and if the number is
negative, we add a one (1) to become the MSB.

Example
Convert+53 and -53 to binary in sign-magnitude notation.

Page 9 of 110
112
 Digital Electronics I Lecture Notes

Solution:
The unsigned binary code for 53 can be obtained by successive division by 2 as
110101. For +53, we add a ‘0’ sign bit as MSB to give the binary sign-magnitude
code for +53 as 0110101. For -53, we add a ‘1’ for a sign bit to get 1110101. We can
tabulate the decimal equivalents of the 4-bit binary codes, assuming these codes are
in sign-magnitude notation, as shown below:
Sign-Magnitude Code Decimal
0000 +0
0001 +1
0010 +2
0011 +3
0100 +4
0101 +5
0110 +6
0111 +7
1000 -0
1001 -1
1010 -2
1011 -3
1100 -4
1101 -5
1110 -6
1111 -7

Generally, for N bits, the range of integers which can be represented using this nota-
tion = − 2(N −1) − 1 ≤ I ≤ 2(N −1) − 1 .

However, as you can see from the above table, this notation has two distinct patterns
for zero, a positive zero and a negative zero. This creates complications in arithmetic
operations, and for this reason, this notation is not commonly used.

1.7.2 Ones Complement Notation

To get the ones complement notation for a positive number, the unsigned binary
notation of the number is obtained, after which the a zero (0) is added to the number
as the MSB (This is similar to the Sign-Magnitude notation).
The ones complement notation of a negative number is obtained from the corre-
sponding positive binary number by changing each zero in the digit to a 1, and each
1 in the positive binary number to a zero. As an example, we saw in the previous sec-
tion that 53 = 110101 in unsigned binary. +53 would be represented by 0110101 in
Ones Complement Notation (OCN). To represent -53 in OCN, we simply complement
all the bits in +53 to get 1001010. We can have a table similar to one in the previous
section, this time assuming the binary codes are in the Ones Complement Notation.

110
Page 10 of 112
 Digital Electronics I Lecture Notes

Ones Complement Decimal

0000 +0
0001 +1
0010 +2
0011 +3
0100 +4
0101 +5
0110 +6
0111 +7
1000 -7
1001 -6
1010 -5
1011 -4
1100 -3
1101 -2
1110 -1
1111 -0

Generally, for N bits, the range of integers which can be represented using this nota-
tion = − 2(N −1) − 1 ≤ I ≤ 2(N −1) − 1 .

Just as in the previous case, you can see from the above table that this notation also
has two distinct patterns for zero, a positive zero and a negative zero.
To illustrate the problem created by the two patterns for zero, suppose we want to
perform the operation (7−4). This can be rewritten as 7+(−4). From the above table,
+7 = 0111 and −4 = 1011. Adding these two codes gives 10010. Since we are dealing
with 4-bit binary in this case, we can ignore the fifth bit to get 0010. From the above
table once again, we see that 0010 corresponds to +2. But we know that 7 − 4 = +3.
The incorrect result obtained above is as a result of having two zeros. Generally, the
presence of two distinct patterns for zero complicates arithmetic operations and for
this reason, this notation is not commonly used.

1.7.3 Twos Complement Notation

The procedure for obtaining the Twos Complement Notation (TCN) of a positive
number is similar to that of obtaining OCN for a positive number. For a negative
number, you add 1 to the Least Significant Bit (LSB) position of the ones complement
notation of the number.
Example
Obtain the TCN of +53 and -53.
Solution:
53 = 110101 in unsigned binary. Adding a sign bit gives +53 = 0110101 in TCN.
To obtain the code for -53, we first obtain the ones complement notation of the code
0110101, which is 1001010. We then add 1 to the LSB position to get 1001011,
which is the TCN of -53.
The decimal equivalent of the TCN binary code an an−1 · · · a1 a0 .a−1 a−2 · · · a−m is given

Page 11 of 112
Page 11 of 110
 Digital Electronics I Lecture Notes

by:

(−2n × an ) + (2n−1 × an−1 ) + · · · + (21 × a1 ) + (20 × a0 ) + (2−1 × a−1 ) + · · · + (2−m × a−m )

A table showing 4-bit TCN codes and their decimal equivalents is shown below:
Twos Complement Decimal
0000 +0
0001 +1
0010 +2
0011 +3
0100 +4
0101 +5
0110 +6
0111 +7
1000 -8
1001 -7
1010 -6
1011 -5
1100 -4
1101 -3
1110 -2
1111 -1

Generally, for N bits, the range of integers which can be represented using this nota-
tion = −2(N −1) ≤ I ≤ 2(N −1) − 1.
In this case, there is only one zero, so there are no problems with arithmetic. In
fact, digital computers use twos complement binary in arithmetic operations since
addition can be carried out just as addition (e.g. 7 − 4 = 7 + (−4). This means that
the same circuit can be used for both addition and subtraction, which saves on the
hardware to be used for these operations.
Example
Convert -29.625 into Twos Complement Binary.
Solution:

29.625 = 1 1 1 0 1 . 1 0 1 (unsigned)
+29.625 = 0 1 1 1 0 1 . 1 0 1 (signed)
-29.625 = 1 0 0 0 1 0 . 0 1 0 (OCN)
+ 1
-29.625 = 1 0 0 0 1 0 . 0 1 1 (TCN)
Hence the Twos Complement notation for -29.625 = 100010.011. As a cross-check,
using the formula for converting a TCN number to decimal, we get:

(−25 ×1)+(24 ×0)+(23 ×0)+(22 ×0)+(21 ×1)+(20 ×0)+(2−1 ×1)+(2−2 ×0)+(2−3 ×1)

= −32 + 2 + 0.5 + 0.125 = −29.625

In the above example, -29.625 is represented using 9 bits. Suppose we wanted to

represent the number using, say, 16 bits. Then the procedure is shown below:

Page 12 of 110
112
 Digital Electronics I Lecture Notes

29.625 = 1 1 1 0 1 . 1 0 1 (unsigned)
+29.625 = 0 0 0 0 0 0 0 0 1 1 1 0 1 . 1 0 1 (signed)
-29.625 = 1 1 1 1 1 1 1 1 0 0 0 1 0 . 0 1 0 (OCN)
+ 1
-29.625 = 1 1 1 1 1 1 1 1 0 0 0 1 0 . 0 1 1 (TCN)
As we can see, after obtaining the unsigned binary, we add leading zeros and a ‘0’
sign-bit to make 16 bits then we proceed as usual. Use the formula for TCN to
decimal conversion to show that the result obtained, 1111111100010.011 is equal
to -29.625.

1.8 Binary Number Codes

These are binary codes which have special applications.

1.8.1 Binary Coded Decimal (BCD) code

BCD code represents each digit of a decimal number by a 4-bit binary number. The
codes used are tabulated below:
DECIMAL BCD
0 0000
1 0001
2 0010
3 0011
4 0100
5 0101
6 0110
7 0111
8 1000
9 1001

Note that BCD code uses binary codes 0000 to 1001 to represent decimal digits, it
does not use codes 1010, 1011, 1100, 1101, 1110 and 1111. It is a weighted code.
The weightings for a 12-bit BCD number are shown below:

800 400 200 100 80 40 20 10 8 4 2 1

To convert a decimal number to BCD code, we simply write out the BCD code for
each digit e.g. to convert the decimal number 137 to BCD, we can see from the
above table that the BCD code for 1 is 0001, for 3 is 0011 and for 7 is 0111, so the
BCD code for 137 is 000100110111.
To convert a BCD code number to decimal, we simply group the bits in groups of 4
bits each and write out the decimal digit corresponding to each decimal digit.

Page 13 of 110
112
 Digital Electronics I Lecture Notes

The main advantage of BCD code is the relative ease of converting to and from dec-
imal. BCD code is used in digital machines whenever decimal information is either
applied as inputs or displayed as outputs e.g. digital voltmeters, digital clocks, e.t.c.
use BCD because they display information in decimal. Electronic calculators use BCD
because the input numbers are entered in decimal via the keypad and the output
numbers displayed in decimal.
However, BCD code is not used in modern high-speed digital computers because:

• It requires more storage space

• The arithmetic with BCD is more complicated (can you explain these points??)

1.8.2 Excess-3 code

The excess-3 code (also known as Xs-3 code) for a decimal number is obtained in the
same manner as for BCD, except that 3 is added to each digit before encoding it in
binary. The example below shows how to convert 59 to Xs-3 code.

5 9
+ 3 + 3
—— ——
8 12
↓ ↓
1000 1100
The Xs-3 code for 59 is therefore 10001100. The table below shows the codes used
by Xs-3 code, and these are listed alongside BCD codes.
DECIMAL BCD Xs-3 CODE
0 0000 0011
1 0001 0100
2 0010 0101
3 0011 0110
4 0100 0111
5 0101 1000
6 0110 1001
7 0111 1010
8 1000 1011
9 1001 1100

The Xs-3 code does not use codes 0000, 0001, 0010, 1101, 1110 and 1111.
The advantage of this code is that at least one 1 is present in all codes, providing an
error-detection ability.

110
Page 14 of 112
 Digital Electronics I Lecture Notes

1.8.3 Gray Code

In gray code, only one bit changes in going from one number to the next. It is a non-
weighted code - bit positions in the code do not have any specific weights attached
to them.

Converting from Binary to Gray Code

i) Record the MSB of the binary number.

ii) Add the binary MSB to the next bit position, record the sum and neglect any
carries.

iii) Record successive sums until completed.

Applying this procedure on the binary code 101110110, we get the equivalent Gray
Code to be 111001101.

Converting from Gray to Binary

i) Record the MSB of the Gray Code number.

ii) Add the binary MSB to the next significant bit position of the Gray Code num-
ber, again recording the sum and ignoring any carries.

iii) Continue the process until completed.

This procedure applied to Gray Code number 111001101 yields 101110110.

The table below shows the Gray codes for the first 16 decimal digits.
DECIMAL BINARY GRAY
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

110
Page 15 of 112
 Digital Electronics I Lecture Notes

Observe that only one bit position changes in the binary code in moving from one
number to the next. Gray code is often used in situations where other codes might
produce erroneous or ambiguous results during those transitions in which more than
1 bit of the code is changing e.g. in the transition from 7 to 8 in binary, all bit
positions change, and in a practical circuit, these bit positions may not change at
exactly the same time and this could cause problems in some circuits.

110
Page 16 of 112
 Digital Electronics I Lecture Notes

Chapter 2

BOOLEAN ALGEBRA AND LOGIC

GATES

2.1 Introduction

In Boolean algebra, the variables (known as Boolean variables) are allowed to have
only two possible values, usually denoted as 0 and 1, unlike ordinary algebra where
variables can take on infinitely many values.
In Boolean algebra, we can have expressions such as:

x = f (A, B)

which is read as “x is a function of variables A and B”. A and B are Boolean variables
and can only take on two possible values, 0 or 1. f () is the Boolean operation on the
variables.

2.2 Basic Operations of Boolean Algebra

Boolean algebra has only 3 basic operations:

i) Logical addition (the OR operation), Symbol +

ii) Logical multiplication (the AND operation), Symbol ·

iii) Logical complementation (the NOT operation). Different books have different
symbols for this operation, including ∗ , 0 and¯

Any Boolean function, however complex, can be broken down to a combination of these
three operations.

17

Page 17 of 110
112
 Digital Electronics I Lecture Notes

2.2.1 The OR operation

This operation operates on two or more variables. The expression:

x=A+B

is read as “x equals A OR B”. We can write the operation of the 2-variable in the
form of a table as shown below:
A B x
0 0 0
0 1 1
1 0 1
1 1 1
A table, such as the one above, which shows how a logic circuit’s outputs respond to
various combinations of logic levels at the inputs is known as a truth-table.
From the truth-table above, we can write that:
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 1
In general, a truth-table of m inputs has 2m input combinations e.g. a 3-input OR
operation (for the operation x = A + B + C) has 23 = 8 input combinations, and it is
shown on the table below:
A B C x
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 1
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 1
The OR operation is implemented using an OR gate. The Figure 2.1 shows a 2-input
OR gate and a 3-input OR gate.
In general, the OR operation produces a result of 1 when any of the input variables
is 1. The OR operation produces a result of zero only when all the input variables are
0.

110
Page 18 of 112
 Digital Electronics I Lecture Notes

PSfrag replacements
A A
x B x
B C
2−input OR gate 3−input OR gate

Figure 2.1: 2 and 3 input OR gates

2.2.2 The AND operation

This operates on two or more variables. The expression:

x=A·B

is read as “x = A AND B”. Note that in most cases, the dot between A and B is
omitted and the expression simply written as x = AB. The truth-table for the 2-
input AND operation is shown below:
A B x
0 0 0
0 1 0
1 0 0
1 1 1
The AND operation is implemented using an AND gate, and Figure 2.2 shows a 2-
input and 3-input AND gate.
PSfrag replacements
A A
x B x
B
C
2−input AND gate 3−input AND gate

Figure 2.2: 2 and 3 input AND gates

For the AND operation, an output equal to 1 occurs only for the single case when all
the inputs are 1. The output is 0 for any case where one or more inputs are 0.

2.2.3 NOT operation

The inputs have to be reduced to a single variable before a NOT operation can be
performed. It is the inversion or complementation function.
If this operation is to be applied on a variable A, we can then write:

x=A

110
Page 19 of 112
 Digital Electronics I Lecture Notes

which is read as “x = NOT A”. The truth-table for this is shown below:
A x
0 1
1 0

This means that 0 = 1 (NOT ‘0’ = ‘1’) and 1 = 0 (NOT ‘1’ = ‘0’). Note also that 0 = 0
and 1 = 1.
The NOT operation is implemented using a NOT gate, illustrated on Figure 2.3. The
NOT gate is also known as an inverter.
PSfrag replacements
A A

Figure 2.3: A NOT gate (inverter)

2.3 Other Logic Gates

2.3.1 The NOR gate

For two variables A and B, the NOR operation is defined as:

x=A+B

In this case, we read this as “x equals NOT (A OR B). This case is equivalent to a
2-input OR gate and an inverter connected in series. The symbol for a 2-input NOR
gate is shown on Figure 2.4.
PSfrag replacements
A
A+B

Figure 2.4: A 2-input NOR gate

The truth-table for a 2-input NOR gate is shown below:

A B x
0 0 1
0 1 0
1 0 0
1 1 0

110
Page 20 of 112
 Digital Electronics I Lecture Notes

2.3.2 The NAND gate

For three variables A, B and C, the NAND operation is defined as:

x=A·B·C

In this case, we read this as “x equals NOT (A AND B AND C). This is equivalent
to a 3-input AND gate and an inverter connected in series. The symbol for a 3-input
NAND gatePSfrag replacements
is shown on Figure 2.5.

A
A·B·C
B
C

Figure 2.5: A 3-input NAND gate

The truth-table for a 3-input NAND gate is shown below:

A B C x
0 0 0 1
0 0 1 1
0 1 0 1
0 1 1 1
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 0

2.3.3 The Exclusive-OR gate

For variables A and B, the Exclusive-OR function is defined as:

x=A⊕B

and the truth-table is shown below:

A B x
0 0 0
0 1 1
1 0 1
1 1 0
The Exclusive-OR operation is sometimes abbreviated as XOR or EXOR. The opera-
tion is implemented using an Exclusive-OR gate, illustrated on Figure 2.6.
Note that the XOR gate has only two inputs.

Page 21 of 110
112
 Digital Electronics I Lecture Notes

PSfrag replacements
A
A⊕B

Figure 2.6: An Exclusive-OR gate

2.3.4 The Exclusive-NOR gate

This is usually abbreviated as XNOR or EXNOR gate. It is the complement of the XOR
operation. For variables A and B,

x=A B =A⊕B

and the truth-table is shown below:

A B x
0 0 1
0 1 0
1 0 0
1 1 1
The operation is implemented using an Exclusive-NOR gate, illustrated on Figure 2.7.

PSfrag replacements
A
A⊕B

Figure 2.7: An Exclusive-NOR gate

Just as for the XOR gate, the XNOR gate has only two inputs.

2.4 Laws of Boolean Algebra

Basic Theorems
A+0=A A·1 =A
A+1=1 A·0=0
A+A=A A·A=A
A + Ā = 1 A · Ā = 0
Looking at the above table, we can see that the corresponding laws on either side are
related by:

110
Page 22 of 112
 Digital Electronics I Lecture Notes

i) Interchanging + and · symbols

ii) Interchanging 0 and 1

Theorems which are related to another by this double interchange are known as
duals.
Other theorems, each listed along with its dual, are tabulated below:

1: A+B = B +A A·B =B·A

2: A + (B + C) = (A + B) + C A · (B · C) = (A · B) · C
3: A + B · C = (A + B) · (A + C) A · (B + C) = A · B + A · C
4: A+A·B = A A · (A + B) = A
5: A+A·B =A+B A · (A + B) = A · B
6: A·B+A·B =A (A + B) · (A + B) = A
7: A · B + A · C = (A + C) · (A + B) (A + B) · (A + C) = A · C + A · B
8: A·B +A·C +B ·C = A·B+A·C (A + B) · (A + C) · (B + C) = (A + B) · (A + C)
9: A + B + C +··· = A · B · C ··· A · B · C ··· = A +B + C + ···
Law 1 is the commutative law, 2 the associative law, 3 the distributive law, 4 is
commonly referred to as the absorption theorem, 5 the simplification theorem, 6 the
reduction theorem and 9 are the De Morgan’s Theorems.

2.5 Proving Boolean Theorems

The theorems above may be proved by use of truth-table or by algebraic means.

2.5.1 Proof by truth-table

Example
Use a truth-table to prove that AB + AC + BC = AB + AC.
Solution:

A B C AB AC BC AB + AC + BC AB + AC
0 0 0 0 0 0 0 0
0 0 1 0 1 0 1 1
0 1 0 0 0 0 0 0
0 1 1 0 1 1 1 1
1 0 0 0 0 0 0 0
1 0 1 0 0 0 0 0
1 1 0 1 0 0 1 1
1 1 1 1 0 1 1 1

Page 23 of 112
110
 Digital Electronics I Lecture Notes

Looking at the table above, we can see that the columns for AB + AC + BC and
AB + AC are identical so the two expressions are equivalent. This has been shown
by means of a truth-table. Proving Boolean expressions by use of truth-table is known
as proof by perfect induction.

2.5.2 Proof by Algebraic means

This requires a masterly of the laws of Boolean algebra so a lot of practice is needed
to be able to use this technique effectively.
Example
Use algebraic means to show that A + A · B = A
Solution:
A+A·B =A·1+A·B
= A · (1 + B) = A · 1 = A

Example
Use algebraic means to show that A + A · B = A + B
Solution:
A+A·B =A+A·B +A·B
= A + (A + A) · B = A + B · (1)
=A+B

2.6 Standard Forms for Boolean Functions

There are two standard forms for Boolean expressions: Standard sum of products
form and Standard product of sums form.

2.6.1 Standard Sum of Products form

Given a function:
f (A, B, C) = (AB + C)(B + AC)
we can use the distributive rule (informally known as opening the brackets) to write:

f (A, B, C) = ABB + CB + ABAC + CAC

By use of Boolean rules, we can simplify the above expression to:

f (A, B, C) = AB + BC + ABC + AC

110
Page 24 of 112
 Digital Electronics I Lecture Notes

From the expression above, the terms AB, BC, ABC and AC are products, and
they are all combined with an OR operation (logical addition or summation) so the
expression is said to be in Sum of Products form. (Note however that expressions like
ABC + ABC are not in Sum of Products form since the inversion signs cover more
than one variable).
Now consider the expression we obtained above:

f (A, B, C) = AB + BC + ABC + AC

This is a function of variables A, B and C, but not all the product terms contain all
these variables e.g. the product term AB lacks the variable C, BC lacks the variable
A, and so on. To express the function in Standard Sum of Product form, we must add
the missing variables to all the product terms so that every variable appears in each
product term (either in its true form or in its complement form). To do this, we use
the Boolean algebra laws:

(A + A) = 1 and A·1=A

We can then write the above expression as:

f (A, B, C) = AB(C + C) + (A + A)BC + ABC + AC(B + B)

= ABC + AB C + ABC + ABC + ABC + ABC + ABC

= ABC + AB C + ABC + ABC
This form, in which a sum of products appears, each term involving all variables is
called the Standard Sum of Products form or Canonical Sum of Products form. Each
individual term in the expression is known as a minterm, e.g. ABC is a minterm.
Each minterm will have a logical value of 1 only when all the terms have a logical
value of 1 e.g. minterm ABC will have a logical value of 1 only when A = B = C =
1, AB C = 1 only if A = B = C = 1 (A = 1, B = 1, and C = 0) e.t.c. The table below
shows the minterms of the 3 variables A, B and C.
A B C minterm
0 0 0 m0 = ĀB̄ C̄
0 0 1 m1 = ĀB̄C
0 1 0 m2 = ĀB C̄
0 1 1 m3 = ĀBC
1 0 0 m4 = AB̄ C̄
1 0 1 m5 = AB̄C
1 1 0 m6 = AB C̄
1 1 1 m7 = ABC

110
Page 25 of 112
 Digital Electronics I Lecture Notes

Going back to the function we started off with and using the above table, we can
write:
f (A, B, C) = m7 + m6 + m3 + m5
Sometimes the above expression is written as:

f (A, B, C) = Σm(3, 5, 6, 7)

2.6.2 Standard Product of Sums form

Given a function:
f (A, B, C) = (AB + C)(B + AC)
we can use the distributive rule to write:

f (A, B, C) = (A + C)(B + C)(B + A)(B + C)

= (A + B)(A + C)(B + C)
The above expression is said to be in product of sums form. To convert this to the
Standard product of sums form, we add the missing variables in each term, using the
Boolean rules:
A·A=0 and (A + 0) = A
We can therefore write:

f (A, B, C) = (A + B + C C̄)(A + B B̄ + C)(AĀ + B + C)

Again using the distributive rule:

f (A, B, C) = (A + B + C)(A + B + C̄)(A + B + C)(A + B̄ + C)(A + B + C)(Ā + B + C)

f (A, B, C) = (A + B + C)(A + B + C̄)(A + B̄ + C)(Ā + B + C)

This is known as the Standard Product of Sums form or Canonical Product of Sums
form. Each of the factors in the expression above is known as a maxterm, e.g. A +
B + C is a maxterm. Each maxterm will have a logical value 0 only when all the
terms in it have a logical value 0, e.g. maxterm (A + B̄ + C) will have a logical value
0 when A = 0, B = 1 and C = 0.
The table below shows the maxterms of the 3 variables A, B and C.

110
Page 26 of 112
 Digital Electronics I Lecture Notes

A B C maxterm
0 0 0 M0 =A+B+C
0 0 1 M1 = A + B + C̄
0 1 0 M2 = A + B̄ + C
0 1 1 M3 = A + B̄ + C̄
1 0 0 M4 = Ā + B + C
1 0 1 M5 = Ā + B + C̄
1 1 0 M6 = Ā + B̄ + C
1 1 1 M7 = Ā + B̄ + C̄
We can therefore write:

f (A, B, C) = M0 · M1 · M2 · M4

Sometimes this is written as:

f (A, B, C) = ΠM (0, 1, 2, 4)

110
Page 27 of 112
 Digital Electronics I Lecture Notes

Chapter 3

SIMPLIFICATION OF BOOLEAN
EXPRESSIONS AND COMBINATIONAL
LOGIC CIRCUIT DESIGN

3.1 Simplification of Boolean Expressions

Introduction

Suppose you wanted to implement the Boolean function:

 
x = AB A + BC
We can implement this directly as shown on Figure 3.1.

B x
PSfrag replacements
C

Figure 3.1: Circuit for the unsimplified expression

This implementation requires a total of five gates.

Suppose now we decided to simplify the expression before implementing it. We first
use De Morgan’s theorems to get:
 
x = AB A · BC

28

Page 28 of 110
112
 Digital Electronics I Lecture Notes

= AB A(B + C)


= AB AB + AC
= ABAB + ABAC
= AB C
This canPSfrag
be implemented using only two gates, as shown on Figure 3.2.
replacements
A
B x
C

Figure 3.2: Circuit for the simplified expression

Generally, it is necessary to reduce Boolean expressions before implementing them

as it makes the final circuit:

i) cheaper - less gates used, needs a smaller circuit board.

ii) more reliable as there are fewer interconnections.

iii) have a lower power consumption.

There are two methods of simplifying logic expressions:

i) Algebraic Simplification - Uses theorems of Boolean Algebra.

ii) The Karnaugh map method - Graphical.

3.1.1 Algebraic Simplification

To use this method, you need to know the theorems of Boolean algebra very well -
you will need a lot of practice to improve your skills. There are generally two steps
when using this method:

i) Put the expression in Sum of Products form (not Standard Sum of Products
form). This may require the use of De Morgan’s theorem or the distributive
rules.

ii) Check for common factors and factor out whenever possible. Factoring usually
results in the elimination of some of the terms.

Page 29 of 110
112
 Digital Electronics I Lecture Notes

Example
Simplify algebraically:
ABC + AB C̄ + AB̄C
The expression is already in sum of products form, so we shall just factor out the
expression:


ABC + AB C̄ + AB̄C = AB C + C̄ + AB̄C


= AB + AB̄C = A B + B̄C
= A (B + C) = AB + AC
Example
Simplify algebraically:  
x = ABC + AB ĀC̄
This expression is not in sum of products form, so we shall first apply De Morgan’s
Theorems to get:

 
x = ABC + A + B A + C


= ABC + A + B (A + C)
= ABC + AC + AB + BC
Now the expression is in sum of products form, so we can proceed with the simplifi-
cation:


x = C A + AB + AB + BC


= C A + B + AB + BC
= AC + BC + BC + AB


= AC + B + B C + AB
= AC + C + AB
= C + AB
Example
A student may register for course X only if he satisfies the following conditions:

(1) Has completed at least 20 courses AND is an engineering student AND of good
conduct, OR

(2) Has completed at least 20 courses AND is an engineering student AND has
departmental approval, OR

(3) Has completed fewer than 20 courses AND is an engineering student AND not
of good conduct, OR

(4) Is of good conduct AND has departmental approval, OR

110
Page 30 of 112
 Digital Electronics I Lecture Notes

(5) Is an engineering student AND does not have departmental approval.

We can convert the conditions listed to letter symbols as follows:

A: Has completed at least 20 courses

B: Is an engineering student

C: Is of good conduct

D: Has departmental approval

Y: Student may register for course X

We can then write:

Y = ABC + ABD + AB C + CD + B D


= ABC + B D + AD + AB C + CD + B D


= ABC + B D + A + AB C + CD
= (ABC + AB) + B D + AB C + CD
= AB + AB C + B D + CD


= B A + ĀC̄ + B D + CD


= B A + C + B D + CD


= AB + B C + B D + CD
Recall the theorem:
AB + AC + BC = AB + AC
We can use this theorem to rewrite the expression in brackets above as:

BD + CD = BD + CD + BC

Hence:
Y = AB + B C + B D + CD + BC


= AB + B C + C + B D + CD
= AB + B + B D + CD
= B + B D + CD
= B + CD
Hence a student may register for the course X if he is an engineering student OR he
is of good conduct AND has departmental approval.

110
Page 31 of 112
 Digital Electronics I Lecture Notes

3.1.2 The Karnaugh Map

Introduction

This is a graphical method used to simplify a Boolean expression. It represents the

information in a truth-table in a different format. Each combination of inputs is
represented by a cell in the map.
Once a Karnaugh Map (K-map) has been filled with ones and zeros, the sum of prod-
ucts expression can be obtained by ORing together the those squares that contain 1s.
The product of sums expression can be obtained by ANDing together those squares
that contain 0s.

Two variable K-map

Consider the 2-variable truth-table shown below:

A B x minterm
0 0 1 m0
0 1 1 m1
1 0 0 m2
1 1 0 m3
(This
PSfragtruth-table is arbitrarily chosen - it is for purposes of illustration only). There
replacements
are four input combinations, so this truth-table can be converted to a K-map with 4
cells, as shown on Figure 3.3. Note that in this case, variable A is treated as the MSB.

A A
B 0 1 B 0 1
0 m0 m2 0 1 0

1 m1 m3 1 1 0

Figure 3.3: Two variable K-map

The K-map may be alternatively drawn with the variable A on the vertical side and
variable B on the horizontal side, as shown on Figure 3.4:

3-variable K-map

Consider the 3-input truth-table shown below:

Page 32 of 110
112
 PSfrag replacements Digital Electronics I Lecture Notes

B B
A 0 1 A 0 1
0 m0 m1 0 1 1
PSfrag replacements 1 m2 m3 1 0 0

Figure 3.4: Two variable K-map: alternative representation

A B C x minterm
0 0 0 1 m0
0 0 1 1 m1
0 1 0 1 m2
0 1 1 0 m3
1 0 0 0 m4
1 0 1 0 m5
1 1 0 1 m6
1 1 1 0 m7

This can be represented using a K-map as shown on Figure 3.5.

AB AB
C 00 01 11 10 C 00 01 11 10
0 m0 m2 m6 m4 0 1 1 1 0
PSfrag replacements
1 m1 m3 m7 m5 1 1 0 0 0

Figure 3.5: Three variable K-map

Note that the K-map cells are labelled in such a way that adjacent cells differ only in
one variable.
The 3-variable K-map may be alternatively drawn as shown on Figure 3.6.

C C
AB 0 1 AB 0 1
00 m0 m1 00 1 1

01 m2 m3 01 1 0

11 m6 m7 11 1 0

10 m4 m5 10 0 0

Figure 3.6: Three variable K-map: alternative representation

Note that the two representations shown (Figure 3.5 and Figure 3.6) are equivalent,
and you may work with whichever representation that you are more comfortable

Page 33 of 110
112
 Digital Electronics I Lecture Notes

with. The only thing you should keep in mind is the order in which the variables
appear – in this case, they appear in the order A (MSB), B and C (LSB).
PSfrag replacements
4-variable K-map

Consider the 4-input truth-table shown below:

A B C D x minterm
0 0 0 0 0 m0
0 0 0 1 1 m1
0 0 1 0 0 m2
0 0 1 1 0 m3
0 1 0 0 0 m4
0 1 0 1 1 m5
0 1 1 0 0 m6
0 1 1 1 0 m7
1 0 0 0 0 m8
1 0 0 1 0 m9
1 0 1 0 0 m10
1 0 1 1 0 m11
1 1 0 0 0 m12
1 1 0 1 1 m13
1 1 1 0 0 m14
1 1 1 1 1 m15

This may be represented using a K-map as shown on Figure 3.7.

AB AB
CD 00 01 11 10 CD 00 01 11 10
00 m0 m4 m12 m8 00 0 0 0 0

01 m1 m5 m13 m9 01 1 1 1 0

11 m3 m7 m15 m11 11 0 0 1 0

10 m2 m6 m14 m10 10 0 0 0 0

Figure 3.7: Four variable K-map

The K-map may be alternatively drawn as shown on Figure 3.8.

3.1.3 Looping

The Logic function can be simplified by properly combining those squares in the that
contain 1s. The process of combining 1s is called looping. The number of 1s that can
be looped together should be a power of 2 (1, 2, 4, 8, 16 e.t.c.).

Page 34 of 110
112
 Digital Electronics I Lecture Notes

CD CD
AB 00 01 11 10 AB 00 01 11 10
00 m0 m1 m3 m2 00 0 1 0 0

01 m4 m5 m7 m6 01 0 1 0 0

11 m12 m13 m15 m14 11 0 1 1 0

10 m8 m9 m11 m10 10 0 0 0 0

Figure 3.8: Four variable K-map: alternative representation

Groups of 2 (Pairs)

Two ones can be looped together if they are horizontally or vertically adjacent. Two
PSfrag replacements
ones next to each other diagonally are not adjacent. Looping a pair of adjacent 1s in a
K-map eliminates the variable that appears in the complemented and uncomplemented form.
Variables that are the same C
for all cells of the loop must appear in the final expression.
Example
Consider the K-map shown on Figure 3.9.

AB
C ĀB̄ ĀB AB AB̄
C̄ 0 1 1 0

C 0 0 0 0

Figure 3.9: Looping two 1s which are horizontally adjacent

The two 1s shown in the K-map are horizontally adjacent and can be looped together
as a pair as shown in the figure. Looking at the cells enclosed in the loop, we can
see that variable A appears as Ā in one cell (complemented form) and as A (uncom-
plemented form) in the other cell hence it is eliminated. Variable B appears as B in
both cells and variable C appears as C̄ so the simplified expression is:

x = B C̄

Example
Consider the K-map shown on Figure 3.10.
The two ones are vertically adjacent and the variable C is the one that changes and
is eliminated hence:
x = ĀB

Page 35 of 110
112
 Digital Electronics I Lecture Notes
C

AB
C ĀB̄ ĀB AB AB̄
C̄ 0 1 0 0

C 0 1 0 0

Figure 3.10: Looping two 1s which are vertically adjacent

PSfrag replacements
The leftmost column and the rightmost column of the K-map are considered to be
adjacent. Similarly, the top row and the bottom row of a K-map are considered to be
adjacent. C

Example
Consider the K-map shown on Figure 3.11.

AB
C ĀB̄ ĀB AB AB̄
C̄ 1 0 0 1
C 0 0 0 0

Figure 3.11: Looping two 1s which are horizontally adjacent

In this case,
x = B̄ C̄

Groups of 4 (Quads)

Four 1s PSfrag
can be replacements
looped together if they are horizontally adjacent, vertically adjacent
or form a square. A loop of four 1s eliminates 2 variables that appear in both com-
plemented and uncomplemented
C form.
Example
Consider the K-map shown on Figure 3.12.

AB
C ĀB̄ ĀB AB AB̄
C̄ 0 0 0 0

C 1 1 1 1

Figure 3.12: Looping four 1s which are horizontally adjacent

Page 36 of 110
112
 Digital Electronics I Lecture Notes

The four 1s are horizontally adjacent and are looped together to give:
PSfrag replacements
x=C

Example
Consider the K-map shown on Figure 3.13.

AB
CD ĀB̄ ĀB AB AB̄
C̄ D̄ 0 1 0 0

C̄D 0 1 0 0

CD 0 1 0 0

C D̄ 0 1 0 0

Figure 3.13: Looping four 1s which are vertically adjacent

The four 1s are vertically adjacent and are looped together to give:
PSfrag replacements
x = ĀB

Example

AB
CD ĀB̄ ĀB AB AB̄
C̄ D̄ 0 1 1 0

C̄D 0 1 1 0

CD 0 0 0 0

C D̄ 0 0 0 0

Figure 3.14: Looping four 1s which form a square

The four 1s in Figure 3.14 form a square and are looped together to give:

x = B C̄

Other examples of quads are shown on Figure 3.15, where x = B̄D for the K-map on
the left and x = B D̄ for the K-map on the right.

Page 37 of 110
112
 Digital Electronics I Lecture Notes

AB AB
CD ĀB̄ ĀB AB AB̄ CD ĀB̄ ĀB AB AB̄
C̄ D̄ 0 0 0 0 C̄ D̄ 0 1 1 0
C̄D 1 0 0 1 C̄D 0 0 0 0
PSfrag replacements
CD 1 0 0 1 CD 0 0 0 0
C D̄ 0 0 0 0 C D̄ 0 1 1 0

Figure 3.15: Looping four 1s

AB
CD ĀB̄ ĀB AB AB̄
C̄ D̄ 1 0 0 1
C̄D 0 0 0 0
CD 0 0 0 0
C D̄ 1 0 0 1

Figure 3.16: The 1s at the corners are adjacent and can looped together

Since the top row of a K-map is adjacent to the bottom row, and the right column to
the left, the corner cells of a K-map are also considered adjacent and can be looped
together if they all contain 1s, as shown on Figure 3.16.
PSfragInreplacements
this case, x = B̄ D̄.

Groups of 8 (octets)

Eight ones may be looped together if they are adjacent. A loop of eight 1s eliminates
3 variables. Examples of octets are shown on Figure 3.17.

AB AB
CD ĀB̄ ĀB AB AB̄ CD ĀB̄ ĀB AB AB̄
C̄ D̄ 1 1 0 0 C̄ D̄ 1 1 1 1
C̄D 1 1 0 0 C̄D 0 0 0 0
CD 1 1 0 0 CD 0 0 0 0
C D̄ 1 1 0 0 C D̄ 1 1 1 1

x = Ā x = D̄

Figure 3.17: Looping eight 1s (octets)

Page 38 of 110
112
 Digital Electronics I Lecture Notes

3.1.4 Complete Simplification Procedure

1. Construct the K-map and place 1s in those cells corresponding to 1s in the

truth-table. Place 0s in the other squares.

2. Examine the map and loop those 1s which are not adjacent to any other 1s.
these are called isolated 1s.

3. Identify those 1s that are adjacent to only one other 1. Loop any pair containing
such a 1. Adjacent ones which can be combined in more than one way are
temporarily bypassed.

4. Identify those 1s which can be combined with three other 1s in only one way.
If not all four 1s so involved have already been looped as pairs, loop the four
1s. The 1s that can be looped in a group of four in more than one way are
temporarily bypassed.

5. Repeat the preceding steps for groups of 8, 16 e.t.c.

6. Loop any quad that contains one or more 1s that have not yet been looped.

7. Loop any pairs necessary to include any 1s that have not yet been looped, mak-
ing sure to use the minimum number of loops.

8. Form the OR sum of all the terms generated by each loop.

Note: If the expression you obtain using the steps above can be simplified further by
algebraic means, it means you have not looped properly - you may be using too many
loops and/or your loops may not be large enough.
Carefully go through the examples below, and see if you can come up with the same
loops. These examples have been looped in such a way as to obtain the simplest
possible expressions.
Example

From Figure 3.18, x = AB̄ C̄ D̄ + ABC + BD

Example

From Figure 3.19, x = ĀB C̄ + AC̄D + ABC + ĀCD

Example

From Figure 3.20, x = ĀBC D̄ + ĀB̄ C̄ + AB C̄ + C̄D + B̄D + AD

110
Page 39 of 112
 PSfrag replacements
Digital Electronics I Lecture Notes

AB
CD ĀB̄ ĀB AB AB̄
C̄ D̄ 0 0 0 1

C̄D 0 1 1 0
PSfrag replacements CD 0 1 1 0

C D̄ 0 0 1 0

Figure 3.18: Example

AB
CD ĀB̄ ĀB AB AB̄
C̄ D̄ 0 1 0 0

C̄D 0 1 1 1
PSfrag replacements
CD 1 1 1 0

C D̄ 0 0 1 0

Figure 3.19: Example

AB
CD ĀB̄ ĀB AB AB̄
C̄ D̄ 1 0 1 0
C̄D 1 1 1 1
CD 1 0 1 1
C D̄ 0 1 0 0

Figure 3.20: Example

3.1.5 Obtaining Product of Sums Expressions from K-maps

So far, we have talked about obtaining Sum of Products expressions from K-maps. It
is also possible to obtain Product of Sums expressions – only this time we loop the
zeros together, not the ones. The examples below illustrate the procedure.
Example

From Figure 3.21, x = B̄ + C̄ + D̄ A + D̄
Example

Page 40 of 110
112
 Digital Electronics I Lecture Notes

AB
CD 00 01 11 10
00 1 1 1 1

01 0 0 1 1

11 0 0 0 1

10 1 1 1 1

Figure 3.21:replacements
PSfrag Example: looping the 0s to obtain a product of sums expression
AB
CD 00 01 11 10
00 0 0 1 1

01 1 0 0 1

11 0 0 0 0

10 1 0 0 1

Figure 3.22: Example: looping the 0s to obtain a product of sums expression

From Figure 3.22, x = (A + C + D) B̄ + D̄ C̄ + D̄ B̄ + C̄

Note that for a given K-map, looping the 1s and looping the zeros gives the same results,
only that the results are expressed in different ways. Consider the example shown on
PSfragFigure 3.23 where in one case the 1s are looped and in the other case the 0s are
replacements
looped.

AB AB
CD 00 01 11 10 CD 00 01 11 10
00 0 0 0 0 00 0 0 0 0
01 0 1 1 1 01 0 1 1 1
11 0 1 1 1 11 0 1 1 1
10 0 1 1 1 10 0 1 1 1

Figure 3.23: Example: looping 0s or 1s gives same result expressed in different ways

The Sum of Products expression obtained by looping the 1s is:

x = AD + BD + BC + AC

Page 41 of 110
112
 Digital Electronics I Lecture Notes

while the Product of Sums expression obtained by looping 0s is:

x = (C + D) (A + B)

Opening the brackets of the Product of Sums expression will yield the Sum of Prod-
ucts expression obtained by looping the 1s, showing the two expressions are equiva-
lent.

3.2 Don’t Care Terms

These are also referred to as Unused terms, Forbidden terms or Redundant terms.
These terms describe combinations of variables which never occur in practice. In a
truth-table or a K-map, these inputs are represented by an X, an R or a d. As an
example, suppose that we have a digital circuit with three inputs and one output,
and the input combinations 000, 001 and 010 give an output 0, input combinations
101, 110 and 111 give an output 1, and input combinations 011 and 100 never occur
in practice. The truth-table for this circuit is as shown below:

A B C output
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 X
1 0 0 X
1 0 1 1
1 1 0 1
PSfrag replacements
1 1 1 1
When designing with K-maps containing don’t care variables, the designer can make
the output of any don’t care condition either a 1 or a 0 in order to produce the sim-
plest output expression. This is illustrated on Figure 3.24 for the truth-table above.

AB AB
C ĀB̄ ĀB AB AB̄ C ĀB̄ ĀB AB AB̄
C̄ 0 0 1 X C̄ 0 0 1 1

C 0 X 1 1 C 0 0 1 1

x = Ā

Figure 3.24: Example: simplifying a Boolean expression with don’t care terms

Page 42 of 110
112
 Digital Electronics I Lecture Notes

3.3 NAND/NOR gate circuit implementation

To implement a logic circuit using NAND gates only:

1. Derive the minimized expression for the function in sum of products form (ob-
tained by minimizing Boolean expressions algebraically or by looping 1s in a
K-map).

2. Apply double negation and De Morgan’s theorem to convert the expression in

a form suitable for NAND gate implementation.

As an example, suppose a design problem resulted in a minimized sum of products

expression:
x = AB + BC + AC
and we were to implement this expression using NAND gates only, we then apply the
above steps as follows:

x = AB + BC + AC = AB + BC + AC

= AB · BC · AC
which is implemented as shown on Figure 3.25.

A
PSfrag replacements
B x

Figure 3.25: Example: implementation using NAND gates only

To implement a logic circuit using NOR gates only:

1. Derive the minimized expression for the function in product of sums form (ob-
tained by looping the 0s in a K-map).

2. Apply double negation and De Morgan’s theorem to convert the expression in

a form suitable for NOR gate implementation.

As an example, suppose a design problem resulted in a minimized product of sums

expression:
x = (A + B) (B + C) (A + C)

Page 43 of 110
112
 Digital Electronics I Lecture Notes

and we were to implement this expression using NOR gates only, we then apply the
above steps as follows:

x = (A + B) (B + C) (A + C) = (A + B) (B + C) (A + C)

= (A + B) + (B + C) + (A + C)
which is implemented as shown on Figure 3.26.

A
PSfrag replacements
B x

Figure 3.26: Example: implementation using NOR gates only

3.4 SSI IC-BASED Combinational Logic Circuit Design

3.4.1 Introduction

SSI Small Scale Integration - Digital ICs with less than 12 gates

MSI Medium Scale Integration - Digital ICs with 12 to 99 gates

LSI Large Scale Integration - Digital ICs with 100-9999 gates

VLSI Very Large Scale Integration - More than 10000 gates

A Combinational logic circuit is a logic circuit whose outputs are functions of the
present inputs only. It cannot ‘remember’ the effects of the previous inputs.

3.4.2 Design Procedure

1. Derivation of the truth-table.

– Understand the problem

– Define the input variables
– Define the output variables
– Relate the output variables to the input variables using a truth-table

Page 44 of 110
112
 Digital Electronics I Lecture Notes

2. Derivation of Boolean expressions from the truth-table.

– Outputs are expressed as functions of the input variables.

3. Minimization (or Simplification) of the expressions for outputs.

– Done to minimize the number of gates used in the design and hence min-
imize costs, reduce power consumption and increase circuit reliability.

Note: Use of a K-map makes it possible to combine steps 2 and 3 above.

4. Conversion of the minimized expressions to the form that allows the implemen-
tation of the circuit using the available gates.

– In some cases, we might want to implement the circuit using AND-OR-

NOT logic, NAND gates only or NOR gates only. The expression(s) ob-
tained at step 3 can be implemented directly using AND-OR-NOT logic
(using a combination of AND, OR and NOT logic gates). However, AND-
OR-NOT logic design requires three different types of ICs, all of which may
not be available at the time of the design, and in many cases, AND-OR-
NOT logic design leads to the use of a large number of logic gates, so it is
usually preferred to implement the circuits using NAND gates only or NOR
gates only. The expression obtained in step 3 then needs to be converted
to a form suitable for implementation using these gates.

5. Implementation of the circuit.

3.4.3 Examples and exercises

Example

+5V
R

SW1
+5V
R

SW2 COMBINATIONAL LED

+5V
LOGIC
R
CIRCUIT
SW3
+5V
R
SW4

Figure 3.27: Example: combinational logic circuit design

Page 45 of 110
112
 Digital Electronics I Lecture Notes

Figure 3.27 shows four switches that are part of a control circuitry in a copy machine.
The switches are at various points along the path of the copy paper as the paper
passes through the machine. Each switch is normally open and as the paper passes
over a switch, the switch closes. It is impossible for switches SW1 and SW4 to be
closed at the same time (they are far apart and the paper cannot cover them at
the same time). The LED is to light if two or more switches are closed. Design a
combinational logic circuit for the system.
Solution
The inputs in this case are switches SW1, SW2, SW3 and SW4. We shall denote
these switches as A, B, C and D respectively. Note that if a switch is open, the
corresponding input to the circuit is HIGH (Logic 1), and if a switch is closed, the
corresponding input is LOW (Logic 0). The output of the circuit is denoted as z (and
the state of this output is visually indicated by the LED): when two or more switches
closed, the output of the circuit should be HIGH (LED is LIT), otherwise the output
should be 0 (LED NOT LIT). The truth-table for the circuit is shown below:
A B C D z
0 0 0 0 X
0 0 0 1 1
0 0 1 0 X
0 0 1 1 1
0 1 0 0 X
0 1 0 1 1
0 1 1 0 X
0 1 1 1 0
1 0 0 0 1
1 0 0 1 1
PSfrag replacements 1 0 1 0 1
1 0 1 1 0
1 1 0 0 1
1 1 0 1 0
1 1 1 0 0
1 1 1 1 0

The K-map corresponding to this is shown on Figure 3.28.

AB
CD ĀB̄ ĀB AB AB̄
C̄ D̄ X X 1 1

C̄D 1 1 0 1

CD 1 0 0 0

C D̄ X X 0 1

Figure 3.28: K-map corresponding to the truth table

Figure 3.29 shows the best way to convert the don’t care variables to 1s and 0s,
achieving the biggest loops possible, and minimizing the number of loops used. The
loops have been made to obtain the minimized sum of products expression.

Page 46 of 110
112
 PSfrag replacements

Digital Electronics I Lecture Notes

AB
CD ĀB̄ ĀB AB AB̄
C̄ D̄ 1 1 1 1
C̄D 1 1 0 1
CD 1 0 0 0
C D̄ 1 0 0 1

Figure 3.29: Simplification of the Boolean function

From Figure 3.29, we can write:

z = B̄ D̄ + C̄ D̄ + ĀB̄ + ĀC̄ + B̄ C̄

For NAND gate implementation,

z = B̄ D̄ + C̄ D̄ + ĀB̄ + ĀC̄ + B̄ C̄
PSfrag replacements
 
= B̄ D̄ · C̄ D̄ · ĀB̄ · ĀC̄ · B̄ C̄

For implementation using NOR gates only, a simplified product of sums expression is
required, and this is obtained by looping the zeros as shown on Figure 3.30.
AB
CD ĀB̄ ĀB AB AB̄
C̄ D̄ 1 1 1 1

C̄D 1 1 0 1

CD 1 0 0 0

C D̄ 1 0 0 1

Figure 3.30: Looping the 0s to obtain a simplified product of sums expression

From the figure,

z = Ā + B̄ + D̄ Ā + C̄ + D̄ B̄ + C̄

= Ā + B̄ + D̄ Ā + C̄ + D̄ B̄ + C̄




= Ā + B̄ + D̄ + Ā + C̄ + D̄ + B̄ + C̄

Example
Design a circuit to convert (4-bit) BCD code to Xs-3 code.

Page 47 of 110
112
 Digital Electronics I Lecture Notes

Solution
The truth-table for this is shown below:
BCD CODE EXCESS-3 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 0 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

Do you understand how to derive the truth-table above? Complete the rest of the
exercise.
Exercise
A majority function combinational logic circuit is a circuit whose output is equal to
1 if the input variables have more ones than zeros. The output is zero otherwise.
Design a 4-input majority function combinational logic circuit and implement the
circuit using NAND gates only.
Exercise
In a certain corporation, the four board members A, B, C and D own all stock, which
is distributed as follows:
A: 40%

B: 30%

C: 20%

D: 10%

Each member has a percentage vote equal to his holdings and a total vote greater
than 50% is required to pass a motion. In the boardroom, each member is to have a
switch with which to indicate a YES or NO vote. A lamp is to light if the total vote
cast is more than 50% indicating the motion being voted on is passed. Design an
electronic voting system for the corporation and implement the circuit using:
i) NAND gates only.

ii) NOR gates only.

110
Page 48 of 112
 Digital Electronics I Lecture Notes

Exercise
Figure 3.31 shows a diagram for an automobile circuit used to detect certain unde-
sirable conditions. The 4 switches D, I, L and S are used to indicate the status of the
driver’s door, the ignition, the headlights and the driver’s seatbelt respectively. The
LED is to light under the following undesirable conditions:

(i) The headlights are ON while the ignition is OFF

(ii) The door is OPEN while the ignition is ON

(iii) The seatbelt is UNFASTENED while the ignition is ON.

Under any of these undesirable conditions, the logic circuit should produce a HIGH
output z to light the LED. Design a logic circuit to light the LED when an undesirable
condition occurs, and implement the circuit using

• NAND gates only.

• NOR gates only.

+5V
OPEN
DOOR (D)
CLOSED

+5V
ON
IGNITION (I)
OFF
LOGIC LED
z LED
+5V CIRCUIT driver
ON
LIGHTS (L)
OFF

+5V
FASTENED
PSfrag replacementsUNFASTENED SEATBELT (S)

Figure 3.31:

Page 49 of 110
112
 Digital Electronics I Lecture Notes

Chapter 4

SEQUENTIAL LOGIC CIRCUITS

4.1 Introduction

So far, we have dealt with combinational logic circuits, whose outputs are functions of
the current inputs only. This chapter deals with sequential logic circuits. A sequential
logic circuit is a circuit whose present outputs are functions of the present inputs, as
well as previous inputs. It has in it a unit called the memory which stores the effect of
the previous sequence of inputs. The stored effects of the previous inputs are called
the STATE of the circuit.
A sequential circuit can be represented by the block diagram on Figure 4.1.

external outputs
Combinational
inputs Logic
Circuit

state
Flip−flops
Clock
pulses

Figure 4.1: Block diagram of a sequential logic circuit

4.2 Flip-Flops

A flip-flop is a logic circuit that is capable of storing one bit of information (0 or 1).
It stores the one bit of information as long as power is supplied to the circuit. It is the

50

Page 50 of 110
112
 Digital Electronics I Lecture Notes

simplest memory element. It is also referred to as a bistable multivibrator. Flip-flops

are the basic building blocks for sequential logic circuits. The block diagram of a
flip-flop is shown on Figure 4.2.

normal
Q output
PSfrag replacementsinputs
inverted
Q output

Figure 4.2: A flip-flop

A Flip-flop can have one or more inputs, but it has only two outputs, the normal
output Q and the inverted (or complemented) output Q. Under normal operating
conditions Q and Q are always complements of each other, i.e. either Q = 0 and Q = 1,
or Q = 1 and Q = 0.
When we refer to the STATE of a flip-flop, we are referring to the state of its normal
(Q) output i.e. if we say that the state of a flip-flop is 1, we mean Q = 1.

4.2.1 The NAND-gate latch

The NAND-gate latch is the simplest flip-flop. It is also referred to as a bistable latch.
It is illustrated on Figure 4.3.

PSfrag replacementsA
Q

B Q

Figure 4.3: A NAND gate latch

The truth-table for the NAND-gate latch is shown below (Qn stands for present state,
while Qn+1 stands for next state):

110
Page 51 of 112
 Digital Electronics I Lecture Notes

A B Qn Qn+1 Q̄n+1
0 0 0 1 1
0 0 1 1 1
0 1 0 1 0
0 1 1 1 0
1 0 0 0 1
1 0 1 0 1
1 1 0 0 1
1 1 1 1 0
The truth-table can be summarized as shown below:
A B Qn+1
0 0 Disallowed as it causes Q = Q̄ = 1
0 1 1
1 0 0
1 1 Qn - ‘remembers’ previous state (Memory State)
A NAND-gate latch is used as a building block for other more complicated flip-flops,
and for debouncing switches. Figure 4.4 shows how the NAND gate latch can be used
to debounce a switch.
+5V

open bouncing closed

+5V
output

output

time

+5V

switch switch
in in
output position 1 bouncing position 2
+5V
1
output

time

+5V

Figure 4.4: Switch debouncing

Page 52 of 110
112
 Digital Electronics I Lecture Notes

4.2.2 The SET-RESET flip-flop

This is illustrated on Figure 4.5.

SET
Q
PSfrag replacements

RESET
Q

Figure 4.5: SET-RESET (SR) flip-flop

The truth-table for this flip-flop is shown below:

SET RESET Qn+1
0 0 Qn - ‘remembers’ previous state (Memory State)
0 1 0 - Flip-Flop RESET
1 0 1 - Flip-Flop SET
1 1 Disallowed as it causes Q = Q̄ = 1
When we have SET = 0 and RESET = 1, the flip-flop is RESET (Q = 0), and when
SET = 1 and RESET = 0, the flip-flop is SET (Q = 1). If we have SET = 1 and RESET
= 1, it is similar to setting and resetting the flip-flop at the same time, and this mode
is disallowed as it causes Q = Q̄ = 1.

4.2.3 The D Flip-Flop

The D-type flip-flop is illustrated in Figure 4.6.

PSfrag replacementsD Q

Figure 4.6: D flip-flop

It is a modified version of the SET -RESET flip-flop where SET = RESET . It has
only one input, D. The truth-table for this flip-flop is shown below:
D Qn+1
0 0
1 1

110
Page 53 of 112
 Digital Electronics I Lecture Notes

From the truth-table, we can see that Q transparently follows the input D, and for
this reason, the D flip-flop is sometimes referred to as a transparent latch.

4.2.4 The T flip-flop

A T-flip-flop (also known as a toggle flip-flop)is illustrated on Figure 4.7.

PSfrag replacements Q
T
Q

Figure 4.7: T flip-flop

The corresponding truth-table is shown below:

T Qn Qn+1
0 0 0
0 1 1
1 0 1
1 1 0
This truth-table can be summarized as shown below:
T Qn+1
0 Qn
1 Q̄n

4.2.5 The JK flip-flop

The JK flip-flop is shown on Figure 4.8.

PSfrag replacements
J Q

K Q

Figure 4.8: JK flip-flop

Its truth-table is shown below:

110
Page 54 of 112
 Digital Electronics I Lecture Notes

J K Qn Qn+1
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 0
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 0
This truth-table can be summarized as shown below:
J K Qn+1
0 0 Qn
0 1 0
1 0 1
1 1 Q̄n
From the truth-table above, we can see that the JK flip-flop does not have invalid
inputs and it can complement. These properties make the JK flip-flop very versatile,
and it is used in many sequential logic circuits.

4.3 Clock signals and clocked flip-flops

4.3.1 Introduction

Clock waveforms

A clock signal is a rectangular pulse train or a square wave. A clock waveform can
have many shapes, as shown on Figure 4.9.

Duty cycle

For a clock waveform,

THIGH
Duty Cycle = × 100%
THIGH + TLOW
where THIGH is the time the waveform is at logic level 1 and TLOW is the time the
waveform is at logic level 0.

110
Page 55 of 112
 Digital Electronics I Lecture Notes

0
1

positive going transition (PGT)/ negative going transition (NGT)/

positive edge/ negative edge/
leading edge trailing edge

Figure 4.9: Clock waveforms

Synchronous and asynchronous operation

Digital systems can operate either synchronously or asynchronously:

Asynchronous Outputs of a logic circuit change any time one or more of the inputs
change. This kind of circuits are difficult to troubleshoot since the outputs can
change at any time.

Synchronous Outputs can only change at specific instants of time, these instants
determined by the clock.

Types of clocked flip-flops

There are three types of clocked flip-flops:

• Level Driven flip-flops

• Master-Slave flip-flops

• Edge-triggered flip-flops

The first two types are no longer used in modern digital systems, but are covered
here for completeness.

Page 56 of 110
112
 Digital Electronics I Lecture Notes

4.3.2 Level-Driven flip-flops

A Level-driven flip-flop is one where one level of the clock enables the data inputs
to affect the state of the flip-flop, whereas the other level disables the data inputs
from affecting the state of the flip-flop. This type of flip-flop is illustrated using a JK
flip-flop, which is shown in Figure 4.10.

PSfrag replacementsJ
Q
CLOCK (CLK)

K Q

Figure 4.10: Level-driven JK flip-flop

From the figure, we can see that when the CLK signal is at logic level 0, X = Y = 1,
and from the truth-table of the NAND gate latch, we can see that the flip-flop will be
in the memory state, hence the inputs J and K will not have any effect on the outputs
Q and Q̄. This means that the inputs J and K are disabled from affecting the state of
the flip-flop when CLK = 0.
 

When the CLK signal is HIGH, X = J · Q̄ and Y = K · Q , hence the next state of
the flip-flop is determined by the inputs J and K. This means that when CLK = 1, the
flip-flop inputs (J and K) are enabled to affect the state of the flip-flop.
In this case, we say that the enabling level of the clock is HIGH (Logic 1).
Figure 4.11 below shows the logic symbols for level driven JK flip-flops, one case
having the enabling level of the clock as HIGH as in the case above, and the other
case with the enabling level of the clock being LOW.
PSfrag replacements
J Q J Q
K K
Q Q
CLK CLK
Enabling level Enabling level
of clock = HIGH of clock = LOW

Figure 4.11: Symbols of level-driven JK flip-flops

Exercise
Draw the circuit diagrams for level-driven SET-RESET flip-flop, D flip-flop and the T
flip-flop and explain their operation.

110
Page 57 of 112
 Digital Electronics I Lecture Notes

4.3.3 The Master-Slave flip-flop

The block diagram for a Master-Slave1 flip-flop is shown on Figure 4.12.

MASTER FF SLAVE FF
Q Q
primary
inputs outputs

PSfrag replacements Q Q
CLK CLK

Figure 4.12: A master-slave flip-flop

Assume that the basic flip-flops are enabled by the HIGH level of the clock:

CLK = HIGH Primary inputs are enabled to determine the next state of the Master
flip-flop. Clock input to the Slave flip-flop is LOW so that the Slave inputs are
disabled from affecting the state of the Slave flip-flop.

CLK = LOW Primary inputs are disabled from affecting the state of the Master flip-
flop. Clock input to the Slave flip-flop is HIGH so that the Master’s outputs
PSfrag replacements
are transferred to the Slave flip-flop to determine the next state of the Slave
flip-flop.

Figure 4.13 shows a JK Master-Slave flip-flop.

J W Q1 Y
Q2

Q1
Q2
K
X Z

CLK

Figure 4.13: JK Master-Slave flip-flop

CLK = 1: W = J Q̄ and X = (KQ), hence the primary inputs J and K determine
the next state of the Master flip-flop. At the same time, Y = Z = 1 hence the
slave flip-flop cannot change state when CLK = 1.
1
About the “political correctness” of the Master-Slave notation, see a news article at
http://www.cnn.com/2003/TECH/ptech/11/26/master.term.reut/

110
Page 58 of 112
 Digital Electronics I Lecture Notes

CLK = 0: W = X = 1 hence the Master flip-flop cannot change states. At the same
time, Y = Q̄1 and Z = Q1 hence the outputs of the Master are transferred to
the Slave flip-flop to determine the next output of the Master-Slave flip-flop.

The operation of the Master-Slave flip-flop can be summarized as shown in Fig-

ure 4.14.
HIGH
CLK=HIGH CLK=LOW
Primary inputs Outputs of the
entered into the master flip−flop
master flip−flop. transferred to the
Slave flip−flop slave flip−flop.
cannot change states Master flip−flop
cannot change states
LOW

Figure 4.14: Response of a Master-Slave flip-flop to clock signal

The symbolPSfrag
for a JK Master-Slave flip-flop is shown on Figure 4.15.
replacements

J Q
K

CLK Q

Figure 4.15: Symbol of a Master-Slave flip-flop

Exercise
Draw the circuit diagram for SET-RESET Master-Slave flip-flop and explain its opera-
tion.

4.3.4 Edge triggered flip-flops

Edge triggered flip-flops are those that only change state during the clock transitions
(HIGH to LOW or LOW to HIGH). The flip-flops that change state during the HIGH to
LOW transitions of the clock (negative going transitions) are known as negative edge
triggered flip-flops, while those that change state at the LOW to HIGH transitions
of the clock are known as positive edge triggered flip-flops. Note that there are no
flip-flops that trigger on both the positive and the negative going transitions of the
clock.
Figure 4.16 shows the logic symbol for a positive edge triggered JK flip-flop.
The corresponding truth-table is shown below:

110
Page 59 of 112
 Digital Electronics I Lecture Notes

PSfrag replacements
J
Q

Q
CLK

Figure 4.16: Symbol of a positive-edge-triggered JK flip-flop

J K CLK Qn+1
0 0 ↑ Qn
0 1 ↑ 0
1 0 ↑ 1
1 1 ↑ Q̄n
The interpretation of the truth-table is as follows:
If the inputs of the flip-flop are J = 0, K = 0 and a Positive Going Transition (PGT) of
the clock occurs, the flip-flop will remain in its present state (Qn ), while if the inputs
are J = 0, K = 1, then a PGT of the clock will make the output to be LOW (0) e.t.c.
Figure 4.17 shows the logic symbol for a negative edge triggered JK flip-flop.
PSfrag replacements
J
Q

Q
CLK

Figure 4.17: Symbol of a negative-edge-triggered JK flip-flop

The corresponding truth-table is shown below:

J K CLK Qn+1
0 0 ↓ Qn
0 1 ↓ 0
1 0 ↓ 1
1 1 ↓ Q̄n
The interpretation of the truth-table is similar to that of the positive edge triggered
flip-flop, the only difference is that changes in the state occur only on the negative
going transitions of the clock.
Exercise
Figure 4.18 shows a clock waveform and inputs J and K applied to a positive-edge
triggered JK flip-flop. Using the truth-table for a positive edge triggered JK flip-flop,

110
Page 60 of 112
 Digital Electronics I Lecture Notes

explain what happens at t0 , t1 , t2 , t3 , t4 and t5 to justify the output waveform shown

for Q. (It is assumed that the initial of Q is HIGH)

1
PSfrag replacementsCLK
0
1
J
0
1
K
0
1
Q
0
t0 t1 t2 t3 t4 t5

Figure 4.18: Exercise

4.3.5 Asynchronous inputs

The flip-flop inputs we have talked about so far (J,K, D, SET, RESET, T) are known as
synchronous inputs. This is because the effect of these inputs to the flip-flop output
is synchronized with the clock.
There is another type of inputs known as asynchronous inputs. Asynchronous inputs
operate independently of the clock input. There are two asynchronous inputs in a
flip-flop, the PRESET (sometimes referred to as SET) and CLEAR (sometimes referred
to as RESET). The PRESET input is used to set the state of the flip-flop to 1 (Q = 1)
regardless of the state of the synchronous inputs and the clock, while the CLEAR
input is used to reset the flip-flop (Q = 0). These inputs are usually active-LOW, and
a JK flip-flop having these two inputs is shown on Figure 4.19.
PSfrag replacements

P RESET

J Q
K
CLK Q
CLEAR

Figure 4.19: JK flip-flop with asynchronous inputs

112
Page 61 of 110
 Digital Electronics I Lecture Notes

The truth-table corresponding to this flip-flop is shown below:

P RESET CLEAR F lip − f lop response
1 1 Responds to J, K and CLK (synchronous operation)
1 0 Flip-Flop RESET (Q = 0)
0 1 Flip-Flop SET (Q = 1)
0 0 Not used (= Setting and Resetting at the same time)

4.3.6 IC flip-flops

Examples of flip-flop ICs are the 7474 Dual D-type positive edge-triggered flip-flop IC,
the 74107A Dual JK negative edge-triggered flip-flop IC, the 74109 Dual JK positive-
edge triggered flip-flop IC, etc.

4.4 Flip-flop timing parameters

1. Set-up time tS - Minimum time just before the triggering edge of the clock
arrives during which the synchronous inputs must be held stable (5-50ns for
TTL devices).

2. Hold-time tH - Minimum time after the triggering edge of the clock during
which the inputs must be held stable (about 10ns for TTL devices).

3. Propagation delays

– tP LH Time taken after the triggering edge of the clock for the output Q to
change from LOW to HIGH.
– tP HL Time taken after the triggering edge of the clock for the output Q to
change from HIGH to LOW.

4. Maximum clocking frequency fM AX The highest frequency that may be applied

to the clock input of a flip-flop and still have trigger reliably (TTL about 15MHz,
CMOS about 5 MHz).

5. Clock pulse HIGH and LOW times - The manufacturer will specify the maximum
duration that the clock must remain LOW before it goes HIGH (tw (L)), and the
minimum time that the clock must be kept HIGH before it goes LOW (tw (H)).

6. Asynchronous active pulse width - Minimum time duration that the PRESET or
the CLEAR input has to be kept in its active state in order to reliably set or clear
a flip-flop.

110
Page 62 of 112
 Digital Electronics I Lecture Notes

7. Clock transition times - The time the clock pulse takes to change from LOW to
HIGH (tr ), and from HIGH to LOW (tf ) should be short for reliable triggering.
(for TTL devices, tr and tf ≤ 50ns, for CMOS devices, tr and tf ≤ 200ns

4.5 Flip-flop excitation tables

SET-RESET flip-flop
Qn Qn+1 SET RESET
0 0 0 X
0 1 1 0
1 0 0 1
1 1 X 0
JK flip-flop
Qn Qn+1 J K
0 0 0 X
0 1 1 X
1 0 X 1
1 1 X 0
D flip-flop
Qn Qn+1 D
0 0 0
0 1 1
1 0 0
1 1 1
T flip-flop
Qn Qn+1 T
0 0 0
0 1 1
1 0 1
1 1 0
Exercise
Starting form the characteristic tables of the SET-RESET, JK, D and T flip-flops, derive
the excitation tables above.

110
Page 63 of 112
 Digital Electronics I Lecture Notes

4.6 Derivation of one flip-flop function form another

The procedure:

1. Construct the state transition table for the required flip-flop function.

2. Determine the combination of inputs of the flip-flop being used that gives the
same transition (this is done with the help of the flip-flop excitation tables in
section 4.5 above.

3. Determine the relationship between the required inputs and the available flip-
flop inputs.

4. Construct the circuit.

Example
Realize a JK flip-flop function using a SET-RESET (SR) flip-flop.
REQUIRED FUNCTION FLIP-FLOP BEING USED
J K Qn Qn+1 S R
0 0 0 0 0 X
0 0 1 1 X 0
0 1 0 0 0 X
PSfrag replacements 0 1 1 0 0 1
1 0 0 1 1 0
1 0 1 1 X 0
1 1 0 1 1 0
1 1 1 0 0 1
The K-maps for S and R are shown on Figure 4.20.

JK JK
Q ¯ JK J K̄
J¯K̄ JK Q ¯ JK J K̄
J¯K̄ JK
Q̄ 0 0 1 1 Q̄ X X 0 0

Q X 0 0 X Q 0 1 1 0

S R

Figure 4.20: Example

From the K-maps, we can see that:

S = J Q̄ and R = KQ

The circuit is shown on Figure 4.21.

Page 64 of 110
112
 Digital Electronics I Lecture Notes

PSfrag replacements

J S Q Q
K R

CLK
Q Q

JK flip−flop

Figure 4.21: Realizing a JK flip-flop function from an SR flip-flop

Example
Realize a D flip-flop function using an SR flip-flop.
REQUIRED FUNCTION FLIP-FLOP BEING USED
D Qn Qn+1 S R
0 0 0 0 X
0 1 0 0 1
1 0
PSfrag replacements 1 1 0
1 1 1 X 0
The K-maps for S and R are shown on Figure 4.22.

D D
Q D D Q D D
Q 0 1 Q X 0

Q 0 X Q 1 0

S R

Figure 4.22: Example

From the K-maps, we can see that:

S=D and R = D̄

The circuit is shown on Figure 4.23.

Example
Realize a JK flip-flop function using a D flip-flop.

110
Page 65 of 112
 Digital Electronics I Lecture Notes

PSfrag replacements
D S Q Q
R

CLK
Q Q

D flip−flop

Figure 4.23: Realizing a D flip-flop function from an SR flip-flop

REQUIRED FUNCTION FLIP-FLOP BEING USED

J K Qn Qn+1 D
0 0 0 0 0
0 0 1 1 1
0 1 0 0 0
0 1 1 0 0
1 0 0 1 1
1 0
PSfrag replacements 1 1 1
1 1 0 1 1
1 1 1 0 0
The K-map for D is shown on Figure 4.24.

JK
Q ¯
J¯K̄ JK JK J K̄

Q̄ 0 0 1 1

Q 1 0 0 1

Figure 4.24: Example

From the K-map, we can see that:

D = J Q̄ + K̄Q

The circuit is shown on Figure 4.25.

Exercise
From the circuit of Figure 4.26, complete the truth-table below and hence design a JK
flip-flop based circuit which has the same truth-table, but in which the asynchronous
inputs (P RESET , CLEAR) are not used.

Page 66 of 110
112
 Digital Electronics I Lecture Notes

PSfrag replacements
J D Q Q
K

CLK Q Q

JK flip−flop

Figure 4.25: Realizing a JK flip-flop function from an D flip-flop

X Qn Qn+1
0 0
0 1
1 0
PSfrag replacements
1 1

1
P RESET

X J Q
K
CLK Q
CLEAR

Figure 4.26: Execise

4.7 Counters

A counter is a circuit made up of a series of flip-flops connected in a suitable manner

to record sequences of pulses presented to it in digital form. Counters are used in
digital systems to:

1. Count events - convert a given number of event cycles into a prescribed binary
code.

2. To time events - The duration of an event can be determined from the count
and the clock frequency.

3. To generate special code sequences - In this application, the counter is used as

112
Page 67 of 110
 Digital Electronics I Lecture Notes

the heart of a logic sequencer. Such a circuit generates the next-state informa-
tion as well as the control information.

4. Frequency division

4.7.1 Classification of counters

1. Mode of operation

– Single mode counter - Counts without external control inputs.

– Multi-mode counter - Counters with external control inputs that can be
used to alter the counting sequence, the beginning of a sequence or the
end of a sequence.

2. Modulus of the counter - The maximum number that a counter can sequence
through is called the modulus of the counter, e.g. if the counter goes through
the sequence 000, 001, 010, 011, 100, it goes through five states hence the
modulus of the counter is five. A modulus N counter is also referred to as a
MOD N counter or a DIVIDE by N counter hence the above counter can be
referred to as a MOD 5 counter or a DIVIDE by 5 counter.
Generally speaking, a counter that can sequence through N states is known as
a MODULO N counter or a DIVIDE by N counter. If N is a power of 2 (2, 4, 8,
16 e.t.c.), the counter is called a binary counter. If N is a power of 10 (10, 100,
1000 e.t.c.), the counter is known as a decimal or a decade counter.

3. Clocking method - There are two types of clocking for counters:

i) Asynchronous (ripple) - Type of counter where each flip-flop serves as the

clock input signal for the next flip-flop in the chain. Examples are shown
on Figure 4.27.
PSfrag replacements
Q Q Q Q Q Q
CLK CLK CLK CLK CLK CLK
Q Q Q Q Q Q

Figure 4.27: Asynchronous (ripple) counters

ii) Synchronous - Counter in which all the flip-flops are clocked simultane-
ously. This is illustrated on Figure 4.28.

4. Code sequence generated - A counter may be a straight forward up or down

counter (a counter generating codes 00 → 01 → 10 → 11 is an up counter, while
one generating codes 11 → 10 → 01 → 00 is a down counter). Other counters

Page 68 of 112
110
 Digital Electronics I Lecture Notes

PSfrag replacements Q Q Q
CLK CLK CLK

Q Q Q

Figure 4.28: Synchronous counter

include Gray Code counters and the shift register counters (ring counter and
Johnson counters).

Note that counters can be designed using a combination of flip-flops and gates, and
counters are also available in I.C. form. In the next sections, we shall look at counters
designed using a combination of flip-flops and gates.

4.7.2 Asynchronous Counters

An asynchronous counter comprises a chain of flip-flops in which one flip-flop is

under the command of an external clock input. the other flip-flops in the chain are
indirectly controlled by the external clock. The flip-flops are connected such that each
flip-flop generates the clock input to the next flip-flop in the chain. An asynchronous
counter is also referred to as a ripple counter. This is because the effect of the external
clock ripples through the chain of flip-flops.
Example
Consider the circuit shown on Figure 4.29.
PSfrag replacements

1 1 1
MSB J J LSB J
Q3 Q2 Q1
CLK

CLK CLK CLK

Q3 1 Q2 K
1 Q1 K
1
K

Figure 4.29: A ripple counter

Assuming that we start with Q3 = Q2 = Q1 = 0, we can draw the waveforms shown

on Figure 4.30.
The truth-table corresponding to this waveforms is shown below:

110
Page 69 of 112
 Digital Electronics I Lecture Notes

1
CLK
0

1
Q1
0
PSfrag replacements
1
Q2
0

1
Q3
0

Figure 4.30: Waveforms for the counter in Figure 4.29

Q3 Q2 Q1 clock pulses
0 0 0 before applying clock pulses
0 0 1 after clock pulse #1
0 1 0 after clock pulse #2
0 1 1 after clock pulse #3
1 0 0 after clock pulse #4
1 0 1 after clock pulse #5
1 1 0 after clock pulse #6
1 1 1 after clock pulse #7
0 0 0 recycles to 000 after clock pulse #8
0 0 1 after clock pulse #9
From the table above, we can see that the counter has eight distinct states and it is an
up counter. The counter is therefore a modulo-8 up asynchronous (ripple) counter.
Note that the frequency of the waveform for Q3 is 18 of the clock frequency hence this
can also be referred to as a divide by 8 counter.
Generally, for N negative-edge triggered JK flip-flops connected in the form shown
on Figure 4.29, the counter formed is a Modulo-2N ripple up counter also known as
a Divide by 2N ripple up counter. For any ripple counter, the output from the last
flip-flop in the chain divides the input clock frequency by the MOD number of the
counter.
Example
Consider the circuit shown on Figure 4.31.
Assuming that we start with Q3 = Q2 = Q1 = 0, we can draw the waveforms shown
on Figure 4.32.
We then get the truth-table for Q1 , Q2 and Q3 , which is shown below:

Page 70 of 110
112
 Digital Electronics I Lecture Notes

PSfrag replacements

1 1 1
MSB J J LSB J
Q3 Q2 Q1
CLK

CLK CLK CLK

Q3 1 Q2 K
1 Q1 K
1
K

Figure 4.31:
1
CLK
0

1
Q1
0
1
Q1
0

PSfrag replacements 1
Q2
0

1
Q2
0

1
Q3
0

Figure 4.32: Waveforms for the counter in Figure 4.31

Q3 Q2 Q1 clock pulses
0 0 0 before applying clock pulses
1 1 1 after clock pulse #1
1 1 0 after clock pulse #2
1 0 1 after clock pulse #3
1 0 0 after clock pulse #4
0 1 1 after clock pulse #5
0 1 0 after clock pulse #6
0 0 1 after clock pulse #7
0 0 0 recycles to 000 after clock pulse #8
1 1 1 after clock pulse #9
From the table above, we can see that the counter has eight distinct states and it is
a down counter. The counter is therefore a modulo-8 down asynchronous (ripple)
counter or a divide by 8 down asynchronous counter.
Note: Negative-edge triggered JK flip-flops connected as shown on Figure 4.29 form

Page 71 of 110
112
 Digital Electronics I Lecture Notes

up-counters, while those connected as in Figure 4.31 form down counters. If positive-
edge triggered JK flip-flops were used, the situation would reverse, such that a connection
similar to that of Figure 4.29 would yield a down counter, while a connection such as the
one of Figure 4.31 would yield an up-counter. Draw the waveforms for positive-edge
triggered JK flip-flops and verify this.

4.7.3 Asynchronous Counters with MOD numbers < 2N

The general design procedure is as follows:

1. For a modulo-k counter, find the smallest number of flip-flops N such that
2N −1 < k < 2N , and connect them as a ripple counter.

2. Connect a NAND gate output to the asynchronous CLEAR inputs of all the flip-
flops.

3. Determine which flip-flops will be in the HIGH state at a count k and then
connect the normal outputs of these flip-flops to the NAND gate inputs.

Example
Design a JK flip-flop-based modulo-6 asynchronous up counter.
Solution
The MOD number k = 6, and this is not a power of 2. Using the equation above:

2N −1 < 6 < 2N

we find that the value of N which satisfies this is N = 3, hence we use three flip-flops
which we connect as a ripple counter. k = 6 = 1102 , hence the two most-significant
digits of the counter are the ones that should be connected to the input of the NAND
gate, to yield the circuit shown on Figure 4.33.

PSfrag replacements

1 1 LSB 1
Q3 J Q2 J Q1 J
CLK

CLK CLK CLK

Q3 1 Q2 1 Q1 1
K K K
CLEAR CLEAR CLEAR

Figure 4.33: A modulo 6 up ripple counter

Page 72 of 110
112
 Digital Electronics I Lecture Notes

Assuming that we start with Q3 = Q2 = Q1 = 0, we can draw the waveforms shown

on Figure 4.34.
1
CLK
0

1
Q1
0

1
PSfrag replacements Q2
0

1
Q3
0

1
X
0

Figure 4.34: Waveforms for the counter in Figure 4.33

From Figure 4.34, we can see that when Q3 and Q2 go HIGH, the output of the NAND
gate (X) goes LOW, and this clears all the flip-flops (Q3 , Q2 and Q1 are taken to the
LOW state). When Q3 and Q2 go LOW, the NAND gate output goes HIGH and the
counter resumes normal operation. The duration of the resetting pulse is very short,
typically < 100ns, so the counter state 110 a temporary state and is not considered
as a valid state of the counter. Assuming that we start with Q3 = Q2 = Q1 = 0, we
can draw the truth-table for this counter as shown below:
Q3 Q2 Q1 clock pulses
0 0 0 before applying clock pulses
0 0 1 after clock pulse #1
0 1 0 after clock pulse #2
0 1 1 after clock pulse #3
1 0 0 after clock pulse #4
1 0 1 after clock pulse #5
1 1 0 temporary state, cannot be observed
0 0 0 recycles to 000 after clock pulse #6
0 0 1 after clock pulse #7
0 1 0 after clock pulse #8
The counter has 6 stable states (000, 001, 010, 011, 100 and 101) hence it is a
modulo-6 up asynchronous counter.
NOTE: Cascading a MOD k1 ripple counter with a MOD k2 ripple counter results in a
MOD k1 k2 counter.

110
Page 73 of 112
 Digital Electronics I Lecture Notes

Exercise

i) Design a JK flip-flop-based MOD 3 ripple up counter.

ii) Cascade two of these MOD 3 counters and show that they form a MOD 9
counter which goes through the sequence 0000 → 0001 → 0010 → 0100 →
0101 → 0110 → 1000 → 1001 → 1010 → 0000

iii) Describe how propagation delays affect the performance of ripple counters.

4.7.4 Synchronous Counters

These are counters in which all the flip-flops are clocked simultaneously, and as a
result, all flip-flop output changes occur simultaneously. Propagation delays do not
add together hence synchronous counters can work at much higher frequencies than
ripple counters.
The design procedure is as follows:

i) Write the state-transition-table for the count.

ii) Derive a minimal logic expression for each flip-flop input.

iii) Implement the logic circuit using flip-flops and a suitable set of logic gates.

Example
Design a JK flip-flop based circuit whose state diagram is shown on Figure 4.35.

00

01 11

10

Figure 4.35:

Solution
Since we are to use JK flip-flops to implement this function, we shall use the JK flip-
flop excitation table given in section 4.5. We then construct the table shown below:

Page 74 of 110
112
 Digital Electronics I Lecture Notes

PRESENT STATE NEXT STATE FLIP-FLOP INPUTS

QA QB QA+1 QB+1 JA K A JB K B
0 0 0 1 0 X 1 X
0 1 1 0 1 X X 1
1 0 1 1 X 0 1 X
1 1 0 0 X 1 X 1
The K-maps corresponding to the four flip-flop inputs are shown on Figure 4.36.

QA QA
QB 0 1 QB 0 1
0 0 X 0 X 0
PSfrag replacements
1 1 X 1 X 1

JA KA

QA QA
QB 0 1 QB 0 1
0 1 1 0 X X

1 X X 1 1 1

JB KB

Figure 4.36: Example

From the figure, we can see that:

PSfrag replacements
JA = K A = Q B and J B = KB = 1

The circuit is shown on Figure 4.37.

MSB
QA JA JB 1
QB

KA KB 1
QA QB
CLK CLK

Figure 4.37: Circuit for a MOD 4 synchronous counter

Note that the flip-flops may be either positive-edge-triggered or negative-edge-triggered.

For observation of the states, QA and QB may be connected to LEDs (QA is the MSB
while QB is the LSB).

110
Page 75 of 112
 Digital Electronics I Lecture Notes

Example
Design a JK flip-flop based circuit whose state diagram is shown on Figure 4.38.
000 111

001 110

010 101

011 100

Figure 4.38:

Using the JK flip-flop excitation table given in section 4.5, we construct the table
shown below:
PRESENT STATE NEXT STATE FLIP-FLOP INPUTS
QA QB QC QA+1 QB+1 QC+1 JA KA JB KB JC KC
0 0 0 0 0 1 0 X 0 X 1 X
0 0 1 0 1 0 0 X 1 X X 1
0 1 0 0 1 1 0 X X 0 1 X
0 1 1 1 0 0 1 X X 1 X 1
1 0 0 1 0 1 X 0 0 X 1 X
1 0 1 1 1 0 X 0 1 X X 1
1 1 0 1 1 1 X 0 X 0 1 X
1 1 1 0 0 0 X 1 X 1 X 1
The K-maps corresponding to the four flip-flop inputs are shown on Figure 4.39.
From Figure 4.39, we can see that:
JA = K A = Q B Q C , JB = K B = Q C and J C = KC = 1

The circuit is shown on Figure 4.40.

In this case, QA is the MSB while QC is the LSB.
Example:
In some cases, the counter may not go through all the possible states. Such a case is
illustrated on Figure 4.41.
The counter has four states, 000, 010, 011 and 101. Since each state is represented
by three bits, it means that the counter is made using three flip-flops. Three flip-flops
can be used to construct a counter with a maximum of eight states, 000 through to
111. It therefore means that the counter above skips states 001, 100, 110 and 111.
The design procedure for such a counter is similar to the cases above, only that the
skipped states are treated as don’t-care variables. The table corresponding to this
counter is shown below:

112
Page 76 of 110
 Digital Electronics I Lecture Notes

QA QB QA QB
QC 00 01 11 10 QC 00 01 11 10
PSfrag replacements 0 X X 0 0
0 0 0 X X

1 0 1 X X 1 X X 1 0

JA KA

QA QB QA QB
QC 00 01 11 10 QC 00 01 11 10
0 0 X X 0 0 X 0 0 X

1 1 X X 1 1 X 1 1 X

JB KB

QA QB QA QB
PSfrag replacements QC 00 01 11 10 QC 00 01 11 10
0 1 1 1 1 0 X X X X

1 X X X X 1 1 1 1 1

JC KC

Figure 4.39: Example

MSB
QA JA QB JB QC JC 1

KA KB KC 1
QA QB QC
CLK
CLK CLK

Figure 4.40: Circuit for a MOD 8 synchronous counter

000

010 101

011

Figure 4.41:

Page 77 of 110
112
 Digital Electronics I Lecture Notes

PRESENT STATE NEXT STATE FLIP-FLOP INPUTS

QA QB QC QA+1 QB+1 QC+1 JA KA JB KB JC KC
0 0 0 0 1 0 0 X 1 X 0 X
0 0 1 - - - X X X X X X
0 1 0 0 1 1 0 X X 0 1 X
0 1 1 1 0 1 1 X X 1 X 0
1 0 0 - - - X X X X X X
1 0 1 0 0 0 X 1 0 X X 1
1 1 0 - - - X X X X X X
1 1 1 - - - X X X X X X

The K-maps corresponding to the four flip-flop inputs are shown on Figure 4.42.

QA QB QA QB
QC 00 01 11 10 QC 00 01 11 10
PSfrag replacements 0 X X
0 0 0 X X X X

1 X 1 X X 1 X X X 1

JA KA

QA QB QA QB
QC 00 01 11 10 QC 00 01 11 10
0 1 X X X 0 X 0 X X

1 X X X 0 1 X 1 X X

JB KB

QA QB QA QB
QC 00 01 11 10 QC 00 01 11 10
0 0 1 X X 0 X X X X

1 X X X X 1 X 0 X 1

JC KC

Figure 4.42: Example

From Figure 4.42, we can see that:

JA = QC , KA = 1, JB = Q̄C , KB = QC , JC = QB , KC = QA

Note that KA and JB may be looped in more than one way – we can loop such that
KA = QC or KA = QA , and JB = Q̄A , which are also acceptable.

Page 78 of 110
112
 Digital Electronics I Lecture Notes

MSB
QA JA QB JB QC JC

KA 1 KB QC KC
QA QB
CLK CLK
CLK

Figure 4.43:

The circuit is shown on Figure 4.43.

In this case, QA is the MSB while QC is the LSB.

4.7.5 Shift Register Counters

All shift register counters use feedback whereby the output of the last flip-flop in the
shift register is in some way connected to the first flip-flop.

Ring counter
PSfrag replacements
This is a circulating shift register connected so that the last flip-flop shifts its value
into the first flip-flop. It operates by recirculating either a single ‘1’ or a ‘0’. An example
of a 4-bit ring counter is shown on Figure 4.44.

D Q3 D Q2 D Q1 D Q0

Q3 Q2 Q1 Q0
CLK CLK CLK CLK

Figure 4.44: A 4-bit ring counter

Assuming that the initial state of the circuit is Q3 Q2 Q1 Q0 = 1000, the timing wave-
forms for the circuit are shown on Figure 4.45.
The waveforms can be summarized by the table below:

110
Page 79 of 112
 Digital Electronics I Lecture Notes

1
CLK
0
1
Q
PSfrag replacements 3 0
1
Q2
0
1
Q1
0
1
Q0
0

Figure 4.45: Timing waveforms for the 4-bit ring counter

Q3 Q2 Q1 Q0 clock pulses
1 0 0 0 before applying clock pulses
0 1 0 0 after clock pulse #1
0 0 1 0 after clock pulse #2
0 0 0 1 after clock pulse #3
1 0 0 0 after clock pulse #4 - recycles
Note that although this does not progress through the normal binary counting sequence,
it is still a counter because each count corresponds to a particular state of the counter.
The circuit shown on Figure 4.44 is therefore a MOD 4 ring counter which recircu-
lates a ‘1’. In general, a MOD N ring counter requires N flip-flops. This type of a
counter is mostly used in sequencing operations.

Johnson Counter

This type of counter is also known as the twisted-ring counter. It is constructed

PSfrag replacements
exactly like a normal ring counter, except that the inverted output of the last flip-flop
is connected to the first flip-flop. Figure 4.46 shows a 3-bit Johnson counter.

D Q2 D Q1 D Q0

Q2 Q1 Q0
CLK CLK CLK

Figure 4.46: A 3-bit Johnson (twisted ring) counter

Assuming the initial state is Q2 Q1 Q0 = 000, the timing waveforms are shown on
Figure 4.47.

110
Page 80 of 112
 Digital Electronics I Lecture Notes

1
CLK
0
1
PSfrag replacementsQ
2
0
1
Q1
0
1
Q0
0

Figure 4.47: Timing waveforms for the 3-bit Johnson counter

The table below summarizes the timing waveforms:

Q2 Q1 Q0 clock pulses
0 0 0 before applying clock pulses
1 0 0 after clock pulse #1
1 1 0 after clock pulse #2
1 1 1 after clock pulse #3
0 1 1 after clock pulse #4
0 0 1 after clock pulse #5
0 0 0 after clock pulse #6 - recycles
1 0 0 after clock pulse #7
Figure 4.46 therefore shows a MOD 6 Johnson (or twisted ring) counter. In general,
N flip-flops connected as a Johnson counter will have a MOD number 2N .

4.7.6 I.C. Counters

Although counters can be constructed using flip-flops, they are also available as
ICs. Examples of IC counters include the asynchronous 4-bit ripple counter 74293,
synchronous 4-bit 74193 and the decade counter 7490. Other IC counters include
the 74176, 74196, 74177, 74197 etc. More information on the operation of these
counter ICs can be obtained from the data books and the references listed at the end
of this handout.

4.8 Registers

A flip-flop is used to store 1 bit of information. When flip-flops are organized to store
many bits of information, they are called registers. We can therefore say that a flip-
flop is a single bit register. Registers can be implemented using discrete components
(flip-flops and gates), and are also available in IC form.
Data can be entered into a register in parallel form (all bits simultaneously), or in

Page 81 of 110
112
 Digital Electronics I Lecture Notes

PSfrag replacements
serial form (one bit at a time). If data is entered to all flip-flops in a register at
the same time, the register is referred to as a parallel register. If data is entered
and removed one bit at a time, the register is known as a serial register or a shift
register. Figure 4.48 shows a 3-bit parallel register while Figure 4.49 shows a 3-bit
shift (serial) register.

D2 D1 D0
D Q2 D Q1 D Q0

Q2 Q1 Q0
CLK CLK CLK

PSfrag replacements

Figure 4.48: A 3-bit parallel register

DATA IN DATA OUT

D Q2 D Q1 D Q0

Q2 Q1 Q0
CLK CLK CLK

Figure 4.49: A 3-bit serial register

The operation most often performed on data that is stored in a flip-flop is the trans-
fer operation. This involves the transfer of data from one register to another. A
transfer operation is said to be a synchronous transfer when the clock inputs are
used to perform the transfer, and asynchronous transfer when the asynchronous in-
puts (P RESET , CLEAR) are used. Figure 4.50 shows a synchronous parallel data
transfer while Figure 4.51 shows a synchronous serial data transfer.
Registers available in IC form can be classified in the following categories:

i) Serial In Serial Out (SISO) - For this kind of registers, data can only be entered
in serial form, and removed in serial form e.g. 7491 8-bit register.

ii) Serial In Parallel Out (SIPO) - Data entered in serial form, read in parallel form
e.g. 74164 8-bit register.

iii) Parallel In Serial Out (PISO) e.g. 7494.

iv) Parallel In Parallel Out (PIPO).

NOTE

• Some shift registers allow a combination of the operation modes above e.g. the
74165 can be operated in SISO and PISO modes.

Page 82 of 110
112
 Digital Electronics I Lecture Notes

REGISTER A REGISTER B

D Q2A D Q2B

CLK CLK

PSfrag replacements
D Q1A D Q1B

CLK CLK

D Q0A D Q0B

PSfrag replacements
CLK CLK

Figure 4.50: Synchronous parallel data transfer

REGISTER A REGISTER B

D Q2A D Q1A D Q0A D Q2B D Q1B D Q0B

CLK CLK CLK CLK CLK CLK

Figure 4.51: Synchronous serial data transfer

• A shift register where data can only be shifted to the right is known as a right-
shift register, while the ones where data can only be shifted to the left are known
as left-shift registers. The shift registers where data can be shifted both left and
right are known as bidirectional shift registers.

• If a register can be operated in all the four modes above (SISO, SIPO, PISO,
PIPO), and has a bidirectional shift, it is referred to as a universal register e.g.
74194.

Page 83 of 110
112
 Digital Electronics I Lecture Notes

Chapter 5

MSI COMBINATIONAL LOGIC

CIRCUITS AND THEIR APPLICATIONS

5.1 Introduction
Digital ICs are often categorized according to their circuit complexity as measured by
the number of gates they contain:
Complexity Number of gates
Small Scale Integration (SSI) Less than 12 gates
Medium Scale Integration (MSI) 12 to 99 gates
Large Scale Integration (LSI) 100-9999 gates
Very Large Scale Integration (VLSI) More than 10000 gates

5.2 Medium Scale Integrated (MSI) devices

MSI devices are used as building blocks for more complex digital circuits. They
perform specific digital functions commonly needed in the design of combinational
logic circuits and they are available in IC form.
Digital circuit design using MSI devices results in significant reduction in the number
of ICs required to implement logic circuits as compared to circuit implementation
using SSI devices. As an example, suppose we would like to implement the Boolean
function X
f (A, B, C, D) = m(4, 5, 7, 9, 11, 15).
To implement this function using SSI devices, it has to be simplified first, and this
results in the Boolean expression

¯
f (A, B, C, D) = ĀB C̄ + BCD + ABD.

102

Page 84 of 110
112
 Digital Electronics I Lecture Notes

Using AND-OR-NOT logic, this circuit requires three 3-input AND gates, one 3-input
OR gate and 3 inverters, a minimum of 3 SSI ICs. If the circuit were to be imple-
mented using NAND gates only, three 2-input NAND gates and four 3-input NAND
gates would be required, again requiring a minimum of 3 SSI ICs. However, as we
shall later see, it is possible to implement this function using a single multiplexer
IC without any additional components, which considerably reduces the circuit com-
plexity, power consumption and increases circuit reliability. Furthermore, for imple-
mentation using a multiplexer, the Boolean function does not need to be simplified
first.
Examples of MSI devices are decoders, encoders, multiplexers, demultiplexers, adders,
subtractors and magnitude comparators.

5.3 Decoders

5.3.1 The decoder function

A decoder is a logic circuit which converts an N -bit binary input into a maximum
of M output lines such that each output line will be activated for only one of the
possible combination of inputs.

N−bit M
input code DECODER output lines

A decoder

In general for a decoder, M ≤ 2N . For each combination of inputs, only one of the
output lines will be activated. The activated output can be HIGH (Logic 1) while
other outputs are LOW (Logic 0), or the activated output can be LOW while all other
outputs are HIGH. If the activated output of the decoder is HIGH while other outputs
are LOW, the decoder is said to have active-HIGH outputs, and if the activated output
is LOW with all other outputs HIGH, the decoder is said to have active-LOW outputs.
The logic symbols for decoders with active-HIGH outputs and active-LOW outputs
are shown in Figure 6.2.
Figure 6.3 shows an example of a decoder.
This decoder generates all the minterms for the input variables A (MSB), B and C

Page 85 of 110
112
 Digital Electronics I Lecture Notes

inputs outputs inputs outputs

DECODER DECODER

active−HIGH active−LOW
outputs outputs

Figure 6.2: Decoders with active-HIGH and active-LOW outputs

inputs
A B C

O0 = ĀB̄ C̄

O1 = ĀB̄C

PSfrag replacements O2 = ĀB C̄

O3 = ĀBC outputs

O4 = AB̄ C̄

O5 = AB̄C

O6 = AB C̄

O7 = ABC

Figure 6.3: 3 line to 8 line decoder

(LSB). This decoder can thus be thought of as a minterm generator. This makes it
useful in the design of combinational logic circuits. The truth-table for this decoder
is given below.

Page 86 of 110
112
 Digital Electronics I Lecture Notes

A B C O0 O1 O2 O3 O4 O5 O6 O7
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
The decoder shown in Figure 6.3 is referred to as

• 3 line to 8 line decoder (since it has 3 inputs and 8 outputs), or

• binary to octal decoder (since the input is a 3-bit binary code and at any time,
only one of 8 outputs (octal) is activated), or

• 1 of 8 decoder (since only one of the eight outputs is activated at a time).

6.3.2 ENABLE inputs

Some decoders have one or more ENABLE inputs that are used to control the oper-
ation of the decoder. If a decoder has ENABLE inputs, it will only function normally
if the ENABLE inputs are at the right logic levels. Most of the decoders which are
available in IC form have ENABLE inputs.
The ENABLE inputs are used for two reasons:

• The ENABLE inputs make it possible to connect several decoders together to

form a larger decoder circuit.

• The ENABLE inputs make it possible to use a decoder as a demultiplexer.

6.3.3 The 74138 1 of 8 decoder

The circuit diagram of the 74138 1 of 8 decoder IC is shown in Figure 6.4.

The truth table showing how the decoder responds to the enable inputs E0 , E1 and
E2 is shown below.
E0 E1 E2 decoder outputs
1 X X decoder disabled – all outputs HIGH
X 1 X decoder disabled – all outputs HIGH
X X 0 decoder disabled – all outputs HIGH
0 0 1 decoder enabled – outputs respond to inputs A, B, C

110
Page 87 of 112
 Digital Electronics I Lecture Notes

inputs
A B C E0 E1 E2

O0

PSfrag replacements O1

O2

O3

O4

O5

O6
PSfrag replacements
O7

Figure 6.4: Circuit diagram for the 74138 3 line to 8 line decoder

The logic symbol for the 74138 decoder is shown in Figure 6.5. (A0 is the LSB while
A2 is the MSB.)

O0
A2
data A1
O1
inputs O2
74138

A0
O3 active−LOW
O4
outputs
E2
ENABLE O5
inputs E1
O6
E0
O7

Figure 6.5: The 74138 decoder

Example
Design a 4-line to-16 decoder based on the 74138 decoder.
Solution

Page 88 of 112
110
 Digital Electronics I Lecture Notes

PSfrag replacements

The 74138 decoder has 3 data inputs and 8 outputs. To build a 4-line-to-16-line
decoder, two 74138 decoders are needed. The 4-line-to-16-line decoder has 4 data
inputs A3 (MSB), A2 , A1 and A0 (LSB) but since the 74138 decoder has only 3 data
inputs A2 (MSB), A1 and A0 (LSB), the inputs A2 , A1 and A0 are connected directly
to the data inputs of the 74138 decoders while the data input A3 is connected to the
ENABLE inputs of the decoders in a suitable manner such that when A3 = 0, one of
the decoders is selected, and when A3 = 1, the other decoder is selected.
Figure 6.6 shows the 4-line-to-16 line decoder.
A3

A2

A1

A0
+5V

E 0 E 1 E2 A0 A1 A2 E 0 E 1 E2 A0 A1 A2

74138 74138

O0 O1 O2 O3 O4 O5 O6 O7 O8 O9 O10 O11 O12 O13 O14 O15

Figure 6.6: 4-line-to-16-line decoder constructed two 74138 decoders

Exercise
You are provided with 2-line-to-4-line decoders of the form shown in Figure 6.7. (A0
isPSfrag
the LSB while A1 is the MSB.) Using as many of these decoders as you need and
replacements
no other components, design a 4-line-to-16-line decoder.

A1 O0
data
inputs
A0 O1 active−LOW
outputs
ENABLE O2
input E
O3

Figure 6.7: 2-line-to-4-line decoder

110
Page 89 of 112
 Digital Electronics I Lecture Notes

6.3.4 BCD to decimal decoder

PSfrag replacements

The 7442 is a 4-line-to-10-line decoder (or a 1 of 10 decoder). This decoder does not
have an enable input. This decoder is shown in Figure 6.8.

O0
O1
O2
D O3

7442
BCD C O4
inputs B O5
A O6
O7
O8
O9

Figure 6.8: The 7442 BCD to decimal decoder

The truth-table for the 7442 decoder is given below:

D C B A active output
0 0 0 0 O0
0 0 0 1 O1
0 0 1 0 O2
0 0 1 1 O3
0 1 0 0 O4
0 1 0 1 O5
0 1 1 0 O6
0 1 1 1 O7
1 0 0 0 O8
1 0 0 1 O9
1 0 1 0 None
1 0 1 1 None
1 1 0 0 None
1 1 0 1 None
1 1 1 0 None
1 1 1 1 None

6.3.5 Decoder applications

Applications of decoders include

 Implementation of combinational logic circuits

 Selection of memory chips (ICs) when the input code is an address from the
central processing unit of a computer.

 Displaying of data on decimal readouts.

110
Page 90 of 112
 Digital Electronics I Lecture Notes

 Sequencing operations (when the input code is from a counter).

 Used as demultiplexers.

Implementation of combinational logic circuits

In general, a decoder provides 2N minterms for N input variables. Since any Boolean
function can be expressed as a sum of minterms, a decoder can be used to generate
the minterms and an external OR gate used to form the sum. (If the decoder has
active-LOW outputs, the outputs are connected using a NAND gate).
Example
Implement the Boolean function
X
S(X, Y, Z) = m(1, 2, 4, 7) (6.3)
X
C(X, Y, Z) = m(3, 5, 6, 7) (6.4)

using PSfrag replacements

a) a 1 of 8 decoder shown in Figure 6.9,

b) a 74138 decoder.

O0
O1
A2 (MSB) O2
O3
A1
O4
A0 (LSB) O5
O6
O7

Figure 6.9:

Solution

a)

b) X
S(X, Y, Z) = m(1, 2, 4, 7) = m1 + m2 + m4 + m7

= m 1 + m 2 + m 4 + m 7 = m 1 · m2 · m4 · m7 .

Page 91 of 110
112
 PSfrag replacements
Digital Electronics I Lecture Notes

O0
O1
X A2 (MSB) O2 S
O3
Y A1
O4
Z A0 (LSB) O5
O6 C
O7
PSfrag replacements
Figure 6.10:

Similarly,
C(X, Y, Z) = m3 · m5 · m6 · m7 .
The circuit implementation using a 74138 decoder is shown in Figure 6.11.
Note that the decoder is permanently enabled.

O0
X A2
O1
Y A1 S
O2
Z A0
O3
O4
+5V E2
O5
E1 C
O6
E0
O7

Figure 6.11:

Exercise
Design a 3-bit binary to Gray code converter using a 74138 decoder and a minimum
of logic gates.

Displaying of data on decimal readouts

In this case, a decoder is used to provide outputs to drive a display so that the binary
number is displayed as a decimal digit. When a decoder is combined with a high
current driving output, it is called a decoder/driver. The high current driving output
is required because LEDs used in many decimal displays require a high current which
an ordinary decoder cannot provide.
A commonly used display is the 7-segment display shown in Figure 6.12. The seg-
ments are either LEDs or Liquid Crystal Displays (LCDs). The 7-segment LED displays
are available in two configurations: the common-anode connection or the common
cathode connection. These configurations are illustrated in Figure 6.13.

Page 92 of 112
110
 Digital Electronics I Lecture Notes

f b
g
PSfrag replacements
e c

Figure 6.12: A 7-segment display

To Vcc To GND

a a

b b

c c

d d

e e

f f
g g

Common anode Common cathode

configuration configuration

Figure 6.13: Common-anode and common-cathode configurations of 7-segment dis-

plays PSfrag replacements

A BCD-to-7-segment decoder/driver is used to take a 4-bit BCD input and provide

the outputs that will pass current through the appropriate segments of a 7-segment-
display to display a decimal digit. One such a device is the 7447, illustrated in
Figure 6.14. The decoder has active-LOW outputs.

7447 a
b
D (MSB)
c
BCD C
d
input B
e
A (LSB)
f
g

Figure 6.14: A 7447 decoder/driver

The truth-table for the 7447 BCD-to-7-segment decoder/driver is given below.

Page 93 of 110
112
 Digital Electronics I Lecture Notes

D C B A a b c d e f g
0 0 0 0 0 0 0 0 0 0 1
0 0 0 1 1 0 0 1 1 1 1
0 0 1 0 0 0 1 0 0 1 0
0 0 1 1 0 0 0 0 1 1 0
0 1 0 0 1 0 0 1 1 0 0
0 1 0 1 0 1 0 0 1 0 0
0 1 1 0 0 1 0 0 0 0 0
0 1 1 1 0 0 0 1 1 1 1
1 0 0 0 0 0 0 0 0 0 0
1 0 0 1 0 0 0 0 1 0 0
1 0 1 0 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1 1
1 1 0 0 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1 1

Note from the truth table above that if the input code is not a valid BCD code, none
of the decoder outputs is activated (all outputs are HIGH). Also note that for valid
BCD codes, more than one output is activated for each binary code, but nevertheless,
the 7447 is still referred to as a decoder.
PSfrag replacements
Figure 6.15 shows how a 7447 can be connected to a 7-segment display. Since this
decoder has active-LOW outputs, it is connected to a common-anode 7-segment dis-
play.
VCC

7447
a a
b b
D (MSB) c c
C
BCD d d
input B e e
A (LSB) f f
g g

Figure 6.15: A 7447 decoder/driver connected to a common-anode 7 segment dis-

play

6.4 Encoders

An encoder has a number of input lines, only one of which is activated at a given time,
and produces an N -bit output code, which depends on which input is activated.
An encoder is functionally the opposite of an encoder. As an example, a binary-to-
octal decoder accepts a 3-bit binary input code and activates only one of 8 output
lines. An octal to binary encoder operates in the opposite manner in that it has 8

Page 94 of 112
110
 Digital Electronics I Lecture Notes

M N−bit
inputs ENCODER output code

Figure 6.16: An encoder

PSfrag replacements

input lines, only one of which is activated at a given time, and it produces a 3-bit
binary output code which depends on which input line is activated. An octal-to-
binary encoder is shown in Figure 6.17

A0
A1
A2 O2
8 input A3
3−bit
O1
lines A4 binary code
A5 O0
A6
A7

Figure 6.17: Octal to binary encoder

The truth-table for this encoder is given below:

A0 A1 A2 A3 A4 A5 A6 A7 O2 O1 O0
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

From the truth-table above, we can write that

O2 = A 4 + A 5 + A 6 + A 7 ,

O1 = A 2 + A 3 + A 6 + A 7 ,
O0 = A 1 + A 3 + A 5 + A 7 .
The above equations can be implemented using the circuit shown in Figure 6.18.
From the truth-table above, we can see that not all the possible combinations of
the input variables are considered hence the circuit shown in Figure 6.18 will work
properly only if only one output is activated at a time. This problem is solved by use
of a priority encoder. A priority encoder works in such a way that if more than one

110
Page 95 of 112
 Digital Electronics I Lecture Notes

A0 A1 A2 A3 A4 A5 A6 A7

PSfrag replacements O2

O1

O0

Figure 6.18:

input is activated, the output code will correspond to the highest numbered of the
activated inputs. (For more information on how to design priority encoders, see the
references
PSfragatreplacements
the end of this handout.) Examples of priority encoders are the 74148
8-line-to-3-line priority encoder (with active-HIGH outputs), and the 74147 decimal-
to-BCD priority encoder (with active-LOW outputs). The 74147 encoder is shown in
Figure 6.19.

A0

A1

A2

A3 O3
74147

A4 O2

A5 O1

A6 O0

A7

A8

A9

Figure 6.19: The 74147 decimal to BCD priority encoder

The truth-table for the 74147 is given below:

Page 96 of 112
110
 Digital Electronics I Lecture Notes

Ā0 Ā1 Ā2 Ā3 Ā4 Ā5 Ā6 Ā7 Ā8 Ā9 0̄3 Ō2 Ō1 Ō0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 all outputs inactive
0 1 1 1 1 1 1 1 1 1 1 1 1 1 A0 activated
X 0 1 1 1 1 1 1 1 1 1 1 1 0
X X 0 1 1 1 1 1 1 1 1 1 0 1
X X X 0 1 1 1 1 1 1 1 1 0 0
X X X X 0 1 1 1 1 1 1 0 1 1
X X X X X 0 1 1 1 1 1 0 1 0
X X X X X X 0 1 1 1 1 0 0 1
X X X X X X X 0 1 1 1 0 0 0
X X X X X X X X 0 1 0 1 1 1
X X X X X X X X X 0 0 1 1 0

The 74147 is commonly used as a switch encoder. Consider the circuit shown in
Figure 6.20.
+5V
R
A9
SW9
+5V
R
A8
SW8
PSfrag replacements +5V
R
A7
SW7
+5V
R

SW6
A6
+5V
O0
R
74147

A5
SW5 O1
+5V BCD
R code
A4 O2
SW4
+5V
O3
R
SW3
A3
+5V
R
SW2
A2
+5V
R

SW1
A1
+5V
R
A0
SW0

Figure 6.20: Switch encoder

The switches may be keyboard switches on a calculator representing digits 0 to 9.

When no key is pressed, the output is 0000. When a digit is pressed, the output will
be the BCD code for that digit. The 74147 is a priority encoder, so pressing two keys
simultaneously will produce the BCD code for the bigger digit.

Page 97 of 112
110
 Digital Electronics I Lecture Notes

6.5 Multiplexers

6.5.1 The multiplexer function

Multiplexing means transmitting a large number of information units over a smaller

number of channels or lines. A multiplexer is a logic circuit that accepts several data
inputs and allows only one of them at a time to get to the output. The routing of
the desired data input to the output is controlled by SELECT inputs, also known as
ADDRESS inputs. A multiplexer is analogous to a multi-position switch.

Data output
inputs MUX

SELECT
inputs

Figure 6.21: A multiplexer

6.5.2 2-input multiplexer

I1
PSfrag replacements
z I0 2−line to z
1−line
I1 MUX
I0
S
S

Figure 6.22: 2-line to 1-line multiplexer

Consider the circuit shown in Figure 6.22. The output is given by

z = I1 S + I0 S.

The truth-table for the circuit is given below:

S z
0 I0
1 I1

Page 98 of 110
112
 Digital Electronics I Lecture Notes

It is clear from the truth-table that the input signals are routed to the output depend-
ing on the SELECT input S.

6.5.3 4-input multiplexer

I0
PSfrag replacements

I1 I0
I1 4−line to z
z 1−line
I2 MUX
I2
I3
S0
S1
I3 S1 S0

S1 S0

Figure 6.23: 4-line to 1-line multiplexer

From the circuit shown in Figure 6.23, the output is given by

z = I 0 S 1 S 0 + I 1 S 1 S0 + I 2 S1 S 0 + I 3 S1 S0 .

The truth-table for the circuit is given below:

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

6.5.4 4-input multiplexer with ENABLE input

Figure 6.24 shows a 4-line to 1-line multiplexer with an ENABLE input. The truth-
table for this multiplexer is given below:
E S1 S0 z
0 X X 0
1 0 0 I0
1 0 1 I1
1 1 0 I2
1 1 1 I3

110
Page 99 of 112
 Digital Electronics I Lecture Notes

PSfrag replacementsI0

I1 I0
I1 4−line to z
z 1−line
I2 MUX
S0I2 I3
S1

I3 S1 S0 E

S1 S0 E

Figure 6.24: 4-line to 1-line multiplexer with ENABLE input

PSfrag replacements
6.5.5 Examples of IC multiplexers

An example of an IC multiplexer with an ENABLE input is the 8-input 74151 multi-

plexer shown in Figure 6.25.

I0 I1 I2 I3 I4 I5 I6 I7
S2 (MSB)
S1 74151
S0 (LSB)
E Z Z

Figure 6.25: The 74151 8-input multiplexer

The truth-table for the 74151 multiplexer is given below:

Page 100 of 110

112
 Digital Electronics I Lecture Notes

E S2 S1 S0 Z Z
1 X X X 0 1
0 0 0 0 I0 I0
0 0 0 1 I1 I1
0 0 1 0 I2 I2
0 0 1 1 I3 I3
0 1 0 0 I4 I4
PSfrag replacements 0 1 0 1 I5 I5
0 1 1 0 I6 I6
0 1 1 1 I7 I7
Another example is the 74157 quad 2-input multiplexer IC (has four 2-input multi-
plexers). The circuit diagram for this multiplexer is shown in Figure 6.26.
IIa IOa IIb IOb IIc IOc IId IOd

PSfrag replacements
Za Zb Zc Zd

Figure 6.26: Circuit diagram for the 74157 Quad 2-input multiplexer

The symbol for the 74157 multiplexer is shown in Figure 6.27.

IIa IOa IIb IOb IIc IOc IId IId

IOd
S
74157
E
Za Zb Zc Zd

Figure 6.27: The 74157 Quad 2-input multiplexer

The truth-table for the 74157 is given below:

Page 101 of 110

112
 Digital Electronics I Lecture Notes

E S Za Zb Zc Zd
1 X 0 0 0 0
0 0 IOa IOb IOc IOd
0 1 IIa IIb IIc IId

6.5.6 The ENABLE input(s) in multiplexers

The ENABLE input(s) in multiplexers make it possible to connect two or more multi-
plexer ICs to form a multiplexer with a large number of inputs.
Exercise
An application requires a 16-input, 1-output multiplexer but the only multiplexer IC
available is the 8-input 74151. Using two 74151 multiplexers and a minimum of
logic gates, show how the required multiplexer can be realized.

6.5.7 Multiplexer applications

PSfrag replacements
Data Routing: Multiplexers are used to route data from one of several sources to one
destination. In the example shown in Figure 6.28, there are two BCD counters
and one seven-segment display and the 74157 multiplexer is used to route the
data from the counters to the display depending on the SELECT input.

BCD counter 1 BCD counter 2

IOa IOb IOc IOd IIa IIb IIc IId

SELECT
S
74157
E Za Zb Zc Zd

BCD to 7−segment
decoder−driver

7−segment display

Figure 6.28: An example illustrating data routing

SELECT Display
0 Contents of BCD counter 1 displayed
1 Contents of BCD counter 2 displayed

This kind of data routing is commonly used in digital watches/clocks to display

the status of different counters using a single display.

Page 102 of 110

112
 Digital Electronics I Lecture Notes

Parallel to serial conversion: Figure 6.29 shows how a multiplexer can be used to
convert data from parallel to serial form.

I0
I1
I2
PSfrag replacements
REGISTER serial
MUX output

IM
S0 S1 SN

data in
parallel form
COUNTER

Figure 6.29: Parallel to serial conversion

In this application, the register where data is in parallel form is connected to

the data inputs of a multiplexer. A counter is connected to the SELECT inputs.
The contents of the register will appear at the multiplexer output in serial form.

Waveform generation: An arbitrary waveform can be generated by the circuit shown

in Figure 6.29 by setting the desired bit pattern in the register.

Implementation of logic functions: Multiplexers can be used to implement logic

functions directly from truth-tables without simplification.

Type 0 MUX design

The SELECT inputs are used as the logic variables and each data input is con-
nected permanently HIGH or LOW as necessary to satisfy the truth-table.
Example
Implement the Boolean function
X
f (C, B, A) = m(1, 2, 7) (6.5)

using a 74151 multiplexer.

Solution
The truth-table corresponding to function (6.5) is as follows:

Page 103 of 110

112
 Digital Electronics I Lecture Notes

C B A f
0 0 0 0
0 0 1 1
PSfrag replacements 0 1 0 1
0 1 1 0
1 0 0 0
1 0 1 0
1 1 0 0
1 1 1 1

Figure 6.30 shows the circuit.

+5V

I0 I1 I2 I3 I4 I5 I6 I7
C S2
B S1 74151
A S0
E Z

Figure 6.30:

Type 1 MUX design

This type of design is carried out when the number of logic variables exceeds
the number of SELECT inputs by one. As an example, recall the Boolean func-
tion (6.1) given in Section 6.2, and reproduced here for convenience:
X
f (A, B, C, D) = m(4, 5, 7, 9, 11, 15). (6.6)

This function has 4 logic variables A, B, C and D, and to implement this func-
tion as described in the previous section, a multiplexer with 16 data inputs and
4 SELECT inputs is required. To implement this function using an 8-input mul-
tiplexer (which has 3 SELECT inputs), type 1 MUX design is applied. The least
significant input bit is partitioned off in the truth-table as shown below. A new
column is then created where the output is expressed as 0, 1, and the LSB.

Page 104 of 110

112
 Digital Electronics I Lecture Notes

Input Variables Output

A B C D f f
0 0 0 0 0
0
0 0 0 1 0
0 0 1 0 0
0
0 0 1 1 0
0 1 0 0 1
1
0 1 0 1 1
0 1 1 0 0
D
0 1 1 1 1
1 0 0 0 0
D
1 0 0 1 1
1 0 1 0 0
D
1 0 1 1 1
PSfrag replacements 1 1 0 0 0
0
1 1 0 1 0
1 1 1 0 0
D
1 1 1 1 1

The implementation of the Boolean function using a 74151 multiplexer is shown

in Figure 6.31.

+5V
D

I0 I1 I2 I3 I4 I5 I6 I7
A S2
B S1 74151
C S0
E Z

Figure 6.31:

Exercise
Implement the Boolean function
X
f (A, B, C, D) = m(4, 5, 6, 7, 10, 14)

using a single 74151 MUX and a minimum of logic gates.

Page 105 of 110

112
 Digital Electronics I Lecture Notes

6.6 Demultiplexers

A demultiplexer takes one input data source and selectively distributes it to 1 of N

output channels. For that reason, demultiplexers are sometimes referred to as data
distributors. A demultiplexer is functionally the opposite of a multiplexer.
The circuit diagram shown in Figure 6.32 is an example of a demultiplexer.
SELECT inputs Data input
S2 S1 S0 D

O0

O1

PSfrag replacements O2

O3

O4

O5

O6

O7

Figure 6.32: An example of a demultiplexer

The truth-table for the demultiplexer shown in Figure 6.32 is as follows:

S2 S1 S0 O0 O1 O2 O3 O4 O5 O6 O7
0 0 0 D 0 0 0 0 0 0 0
0 0 1 0 D 0 0 0 0 0 0
0 1 0 0 0 D 0 0 0 0 0
0 1 1 0 0 0 D 0 0 0 0
1 0 0 0 0 0 0 D 0 0 0
1 0 1 0 0 0 0 0 D 0 0
1 1 0 0 0 0 0 0 0 D 0
1 1 1 0 0 0 0 0 0 0 D

The truth-table above is similar to that of a 3-line-to-8-line decoder. A closer look at

Page 106 of 110

112
 Digital Electronics I Lecture Notes

the circuit of Figure 6.32 shows that the circuit is similar to that of a 3-line-to-8-line
decoder where the data inputs of the decoder are used the SELECT inputs and the
ENABLE input used as the data input. As such, it is possible to use a decoder as a
demultiplexer: the data inputs of the decoder are used as the SELECT inputs and the
ENABLE input serves as the data input.
In general:

 If the decoder has active-HIGH outputs, one of the active-HIGH ENABLE in-
puts should be used as the data input.

 If the decoder has active-LOW outputs, one of the active-LOW ENABLE inputs
should be used as the data input.
Exercise
Verify the validity of the above statements.
Exercise
Show how the 74138 decoder can be used as a demultiplexer.

6.7 Adders and Subtractors

6.7.1 The half adder

Given two bits X and Y , the truth table below shows the arithmetic sum S and the
carry C resulting from the addition of the two bits.
X Y sum S carry C
0 0 0 0
0 1 1 0
1 0 1 0
1 1 0 1
From the truth-table above,

S = X̄Y + X Ȳ = X ⊕ Y

and
C = XY.
The Boolean function given in the truth-table above is implemented as shown in
Figure 6.33. This circuit provides the sum and carry for two bits but does not take
into consideration the carry from a lower significant bit position. Such a circuit is
known as a half-adder (HA).

110
Page 107 of 112
 Digital Electronics I Lecture Notes

PSfrag replacements

X
Y S X S
HA
C Y C

Figure 6.33: A half adder

6.7.2 The full adder

The full adder takes in bits X and Y and a carry from the lower significant bit position
Cin , and gives the arithmetic sum S of the three bits, and a carry Cout to the next
higher bit position. The truth-table for a full adder (FA) is given below:
X Y Cin S Cout
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
S = X̄ Ȳ Cin + X̄Y C̄in + XY Cin + X Ȳ C̄in = X ⊕ Y ⊕ Cin
and
Cout = XY + Y Cin + XCin .
PSfrag replacements
Figure 6.34 shows the schematic diagram for a full adder.

X
S
Y FA
Cin Cout

Figure 6.34: A full adder

6.7.3 The half subtractor

Given two bits X and Y , the truth table below shows the arithmetic difference D and
the borrow B resulting from the subtraction of Y from X (X − Y ).

Page 108 of 110

112
 Digital Electronics I Lecture Notes

X Y difference D borrow B
0 0 0 0
0 1 1 1
1 0 1 0
1 1 0 0
From the truth-table above,

D = X̄Y + X Ȳ = X ⊕ Y

and
B = X̄Y.
PSfrag replacements
The function given in the truth-table above is implemented as shown in Figure 6.35.
X
Y D X D
HS
B Y B

Figure 6.35: A half subtractor

This circuit provides the difference and borrow for two bits but does not take into
consideration the borrow from a lower significant bit position. Such a circuit is
known as a half subtractor (HS).

6.7.4 The full subtractor

The full subtractor carries out the arithmetic operation (X − Y − Bin ), where Bin is
a borrow from a lower significant bit position, and gives the difference D and the
borrow Bout . The truth-table for a full subtractor (FS) is given below:
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
D = X̄ Ȳ Bin + X̄Y B̄in + XY Bin + X Ȳ B̄in = X ⊕ Y ⊕ Bin
and
Bout = X̄Y + X̄Bin + Y Bin .
Figure 6.36 shows the schematic diagram for a full subtractor.

Page 109 of 110

112
 Digital Electronics I Lecture Notes

PSfrag replacements

X
D
Y FS
Bin Bout

Figure 6.36: A full subtractor

Page 110 of 110

112