CPE 202

INTRODUCTION TO
DIGITAL SYSTEMS

1
INTRODUCTION
In science, technology, business, and, in fact, most other fields of endeavor, we are
constantly dealing with quantities. Quantities are measured, monitored, recorded, manipulated
arithmetically, observed, or in some other way utilized in most physical systems. It is important
when dealing with various quantities that we be able to represent their values efficiently and
accurately. There are basically two ways of representing the numerical value of
quantities: analog and digital.

In analog representation a quantity is represented by a continuously variable,

proportional indicator. An example is an automobile speedometer from the classic muscle cars of
the 1960s and 1970s. The deflection of the needle is proportional to the speed of the car and
follows any changes that occur as the vehicle speeds up or slows down. Thermometers before the
digital revolution used analog representation to measure temperature, and many are still in use
today. Mercury thermometers use a column of mercury whose height is proportional to
temperature. Another example is an outdoor thermometer on which the position of the pointer
rotates around a dial as a metal coil expands and contracts with temperature changes. The
position of the pointer is proportional to the temperature. Regardless of how small the change in
temperature, there will be a proportional change in the indication.
In these two examples the physical quantities (speed and temperature) are being coupled to an
indicator by purely mechanical means.

In electrical analog systems, the physical quantity that is being measured or processed is
converted to a proportional voltage or current (electrical signal). This voltage or current is then
used by the system for display, processing, or control purposes. Sound is an example of a
physical quantity that can be represented by an electrical analog signal. A microphone is a device
that generates an output voltage that is proportional to the amplitude of the sound waves that
strike it. Variations in the sound waves will produce variations in the microphone‘s output
voltage. Tape recordings can then store sound waves by using the output voltage of the
microphone to proportionally change the magnetic field on the tape.
Analog quantities such as those cited above have an important characteristic, no matter how they
are represented: they can vary over a continuous range of values.

The automobile speed can have any value between zero and,
say, 100 mph. Similarly, the microphone output might have any value within a range of zero to
10 mV (e.g., 1 mV, 2.3724 mV, 9.9999 mV).

In digital representation the quantities are represented not by continuously variable

indicators but by symbols called digits. As an example, consider the digital clock, which
provides the time of day in the form of decimal digits that represent hours and minutes (and
sometimes seconds). As we know, the time of day changes continuously, but the digital clock
reading does not change continuously; rather, it changes in steps of one per minute (or per
second).

2
 In other words, this digital representation of the time of day changes in discrete steps, as
compared with the representation of time provided by an analog ac line-powered wall clock,
where the dial reading changes continuously.
The major difference between analog and digital quantities, then, can be
simply stated as follows:

Analog continuous

Digital Discrete (step by step)

DIGITAL SYSTEMS
A digital system is a combination of devices designed to manipulate logical information
or physical quantities that are represented in digital form; that is, the quantities can take on only
discrete values. These devices are most often electronic, but they can also be mechanical,
magnetic, or pneumatic. Some of the more familiar digital systems include digital computers and
calculators, digital audio and video equipment, and the telephone system—the world‘s largest
digital system.
To make things simpler, we work with a digital abstraction of our analog world. Instead
of working with an infinite continuous range of values, we use just two values! Yes, just two
values: 1 and 0, on and off, high and low, true and false, black and white, or however you want
to call it. It is certainly much easier to control and work with two values rather than an infinite
range. We call these two values a binary value for the reason that there are only two of them. A
single 0 or a single 1 is then a binary digit or bit. This sounds great, but we have to remember
that the underlining building block for our digital circuits is still based on an analog world.
In electronic digital systems, binary information is represented by voltages (or currents)
that are present at the inputs and outputs of the various circuits. Typically, the binary 0 and 1 are
represented by two nominal voltage levels. For
example, zero volts (0 V) might represent binary 0, and 5 V might represent binary 1. In
actuality, because of circuit variations, the 0 and 1 would be represented by voltage ranges. This
is illustrated in Figure 1(a), where any voltage between 0 and 0.8 V represents a 0 and any
voltage between 2 and 5 V represents a 1. All input and output signals will normally fall within
one of these ranges, except during transitions from one level to another.
Another significant difference between digital and analog systems is, in digital systems, the exact
value of a voltage is not important.

For example, for the voltage assignments of Figure 1a, a voltage of 3.6 V means the same
as a voltage of 4.3 V. In analog systems, the exact value of a voltage is important. For instance, if
the analog voltage is proportional to the temperature measured by a transducer, the 3.6 V would
represent a different temperature than would 4.3 V. In other words, the voltage value carries
significant information.

3
FIGURE 1: (a) Typical voltage assignments in digital system; (b) typical digital signal timing
diagram.

This characteristic means that the design of accurate analog circuitry is generally more
difficult than that of digital circuitry because of the way in which exact voltage values are
affected by variations in component values, temperature, and noise (random voltage
fluctuations).

4
Number Systems
The study of number systems is important from the viewpoint of understanding how data
are represented before they can be processed by any digital system including a digital computer.
It is one of the most basic topics in digital electronics.
Number system or numeral system is the system of naming or representing numbers.
There are various types of number systems. In order to bridge the gap between the way our
brains think (decimal) and how we build our computers (binary), we need to understand the
basics of number systems.
Different characteristics that define a number system include the number of independent
digits used in the number system, the place values of the different digits constituting the number
and the maximum numbers that can be written with the given number of digits. Among the three
characteristic parameters, the most fundamental is the number of independent digits or symbols
used in the number system. It is known as the radix or base of the number system. The decimal
number system with which we are all so familiar can be said to have a radix of 10 as it has 10
independent digits, i.e. 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9. Similarly, the binary number system with
only two independent digits, 0 and 1, is a radix-2 number system. The octal and hexadecimal
number systems have a radix (or base) of 8 and 16 respectively. We will see in the following
sections that the radix of the number system also determines the other two characteristics. The
place values of different digits in the integer part of the number are given by r0, r1, r2, r3 and so
on, starting with the digit adjacent to the radix point. For the fractional part, these are r−1, r−2, r−3
and so on, again starting with the digit next to the radix point. Here, r is the radix of the number
system. Also, maximum numbers that can be written with n digits in a given number system are
equal to rn.
One or more numerals are used to form a number. We define the number of numerals in
the system using the terms radix or base. For example, decimal number system is said to be base
10, or have a radix of 10 because it consists of 10 unique numerals or symbols:
Radix = Base = the number of numerals in the number system
Generic Structure
In order to represent larger or smaller numbers than the lone numerals in a number
system can represent, we adopt a positional system. In a positional number system, the relative
position of the numeral within the overall number dictates its value. When defining the position

5
of a numeral, a location to which all of the numerals are positioned with respect to are defined.
The radix point as the point within a number to which numerals to the left represent whole
numbers and numerals to the right represent fractional numbers is also define. The radix point is
denoted with a period (i.e ―.‖).
A particular number system often renames this radix point to reflect its base. For
example, in the base 10-number system (i.e., decimal), the radix point is commonly called the
decimal point; however, the term radix point can be used across all number systems as a generic
term. If the radix point is not present in a number, it is assumed to be to the right of number.
Figure below shows an example number highlighting the radix point and the relative positions of
the whole and fractional numerals.

Next, the position of each numeral with respect to the radix point is defined. The position of the
numeral is assigned a whole number with the number to the left of the radix point having a
position value of 0. The position number increases by 1 as numerals are added to the left (2, 3, 4 .
. .) and decreased by 1 as numerals are added to the right (-1, -2, -3). We will use the variable p
to represent position. The position number will be used to calculate the value of each numeral in
the number based on its relative position to the radix point. Figure below shows the example
number with the position value of each numeral highlighted. We write a number from left to
right starting with the highest position digit that is greater than 0 and end with the lowest position
digit that is greater than 0.

Decimal Number System (Base 10)

Human brain has been taught to count, label, and measure using the decimal number system.
Regardless, our brains are trained to think of the real world in terms of a decimal system. The
decimal number system is a radix-10 number system and therefore has 10 different digits or
symbols. These are 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9. All higher numbers after ‗9‘ are represented in

6
terms of these 10 digits only. The process of writing higher-order numbers after ‗9‘ consists in
writing the second digit (i.e. ‗1‘) first, followed by the other digits, one by one, to obtain the next
10 numbers from ‗10‘ to ‗19‘. The next 10 numbers from ‗20‘ to ‗29‘ are obtained by writing the
third digit (i.e. ‗2‘) first, followed by digits ‗0‘ to ‗9‘, one by one. The process continues until we
have exhausted all possible two-digit combinations and reached ‗99‘. Then we begin with three-
digit combinations. The first three-digit number consists of the lowest two-digit number followed
by ‗0‘ (i.e. 100), and the process goes on endlessly.
The place values of different digits in a mixed decimal number, starting from the decimal
point, are 100,101,102 and so on (for the integer part) and 10−1,10−2,10−3 and so on (for the
fractional part). The value or magnitude of a given decimal number can be expressed as the sum
of the various digits multiplied by their place values or weights.
As an illustration, in the case of the decimal number 3586.265, the integer part (i.e. 3586)
can be expressed as
3586= 6×100+8×101+5×102+3×103= 6+80+500+3000= 3586
and the fractional part can be expressed as
265= 2×10−1+6×10−2+5×10−3= 0 2+0 06+0 005= 0 265
Binary Number System (Base 2)
The binary number system contains two unique numerals (0 and 1). The binary number
system is a radix-2 number system with ‗0‘ and ‗1‘ as the two independent digits. All larger
binary numbers are represented in terms of ‗0‘ and ‗1‘. The procedure for writing higher order
binary numbers after ‗1‘ is similar to the one explained in the case of the decimal number
system. For example, the first 16 numbers in the binary number system would be 0, 1, 10, 11,
100, 101, 110, 111, 1000, 1001, 1010, 1011, 1100, 1101, 1110 and 1111. The next number after
1111 is 10000, which is the lowest binary number with five digits. This also proves the point
made earlier that a maximum of only 16 (= 24 numbers could be written with four digits. Starting
from the binary point, the place values of different digits in a mixed binary number are 20,21,22
and so on (for the integer part) and 2−1,2−2,2−3 and so on (for the fractional part).
Example 1.1
Consider an arbitrary number system with the independent digits as 0, 1 and X. What is the radix
of this number system? List the first 10 numbers in this number system.
Solution

7
 • The radix of the proposed number system is 3.
• The first 10 numbers in this number system would be 0, 1, X, 10, 11, 1X, X0, X1, XX
and 100.
Due to the need for multiple bits to represent meaningful information, there are terms
dedicated to describe the number of bits in a group.
When 4 bits are grouped together, they are called a nibble.
When 8 bits are grouped together, they are called a byte.
Larger groupings of bits are called words.
The size of the word can be stated as either an n-bit word or omitted if the size of the
word is inherently implied. For example, if you were using a 32-bit microprocessor, using the
term word would be interpreted as a 32-bit word. The leftmost bit in a binary number is called
the most significant bit (MSB). The rightmost bit in a binary number is called the least
significant bit (LSB).
Advantages
Logic operations are the backbone of any digital computer, although solving a problem
on computer could involve an arithmetic operation too. The introduction of the mathematics of
logic by George Boole laid the foundation for the modern digital computer. He reduced the
mathematics of logic to a binary notation of ‗0‘ and ‗1‘. As the mathematics of logic was well
established and had proved itself to be quite useful in solving all kinds of logical problem, and
also as the mathematics of logic (also known as Boolean algebra) had been reduced to a binary
notation, the binary number system had a clear edge over other number systems for use in
computer systems.
Yet another significant advantage of this number system was that all kinds of data could
be conveniently represented in terms of 0s and 1s. Also, basic electronic devices used for
hardware implementation could be conveniently and efficiently operated in two distinctly
different modes. For example, a bipolar transistor could be operated either in cut-off or in
saturation very efficiently.
Lastly, the circuits required for performing arithmetic operations such as addition,
subtraction, multiplication, division, etc., become a simple affair when the data involved are
represented in the form of 0s and 1s.

8
Octal Number System (Base 8)
The octal number system has a radix of 8 and therefore has eight distinct digits. All
higher-order numbers are expressed as a combination of these on the same pattern as the one
followed in the case of the binary and decimal number systems. The independent digits are 0, 1,
2, 3, 4, 5, 6 and 7. The next 10 numbers that follow ‗7‘, for example, would be 10, 11, 12, 13, 14,
15, 16, 17, 20 and 21. In fact, if we omit all the numbers containing the digits 8 or 9, or both,
from the decimal number system, we end up with an octal number system. The place values for
the different digits in the octal number system are 80,81,82 and so on (for the integer part) and
8−1,8−2, 8−3 and so on (for the fractional part).

Hexadecimal Number System (Base 16)

The hexadecimal number system is a radix-16 number system and its 16 basic digits are
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E and F. The place values or weights of different digits in a
mixed hexadecimal number are 160,161,162 and so on (for the integer part) and 16−1,16−2,16−3
and so on (for the fractional part). The decimal equivalent of A, B, C, D, E and F are 10, 11, 12,
13, 14 and 15 respectively, for obvious reasons. The hexadecimal number system provides a
condensed way of representing large binary numbers stored and processed inside the computer.
One such example is in representing addresses of different memory locations. Let us assume that
a machine has 64K of memory. Such a memory has 64K (= 216 = 65 536) memory locations and
needs 65 536 different addresses. These addresses can be designated as 0 to 65 535 in the
decimal number system and 00000000 00000000 to 11111111 11111111 in the binary number
system. The decimal number system is not used in computers and the binary notation here
appears too cumbersome and inconvenient to handle. In the hexadecimal number system, 65 536
different addresses can be expressed with four digits from 0000 to FFFF. Similarly, the contents
of the memory when represented in hexadecimal form are very convenient to handle.

9
Base Conversion
There are distinct techniques for converting to and from decimal. There are also
techniques for converting between bases that are powers of 2 (e.g., base 2, 4, 8, 16).
Converting to Decimal
The value of each digit within a number is based on the individual digit value and the
digit‘s position. Each position in the number contains a different weight based on its relative
location to the radix point. The weight of each position is based on the radix of the number
system that is being used. The weight of each position is defined as
Weight = (Radix)p
This expression gives the number system the ability to represent fractional numbers since
an expression with a negative exponent (e.g., x-y) is evaluated as one over the expression with the
exponent change to positive (e.g., 1/xy). Figure below shows the generic structure of a number
with its positional weight highlighted.

10
Weight Definition
In order to find the value of each of the numerals in the number, its individual numeral
value is multiplied by its positional weight. In order to find the value of the entire number, each
value of the individual numeral-weight products is summed. The generalized format of this
conversion is written as
pm ax i

Total Decimal Value   d .radix

i  pm in
i

Converting from Binary to Decimal

Let‘s convert 101.112 to decimal. Converting from binary to decimal can be
accomplished quickly in your head due to the fact that the bit values in the products are either 1
or 0. That means any bit that is a 0 has no impact on the outcome and any bit that is a 1 simply
yields the weight of its position. Example below shows the step-by-step process converting a
binary number to decimal.

Converting Binary to Decimal

Converting Octal to Decimal
When converting from octal to decimal, the same process is followed with the exception
that the base in the weight is changed to 8. Example below shows an example of converting an
octal number to decimal.

11
Converting Octal to Decimal
Converting Hexadecimal to Decimal
Let‘s convert 1AB.EF16 to decimal. The same process is followed with the exception that
the base is changed to 16. When performing the conversion, the decimal equivalents of the
numerals A–F need to be used. Example below shows the step-by-step process converting a
hexadecimal number to decimal.

Converting Hexadecimal to Decimal

12
Converting from Decimal
The process of converting from decimal to another base consists of two separate
algorithms. The process for converting the whole number portion is to divide the decimal
number by the base of the system you wish to convert to. The division will result in a quotient
and a whole number remainder. The remainder is recorded as the least significant numeral in the
converted number. This process is repeated until a quotient of 0 is achieved. At that point the
conversion is complete. The remainders will always be within the numeral set of the base being
converted to.
The process for converting the fractional portion is to multiply just the fractional
component of the number by the base. This will result in a product that contains a whole number
and a fraction. The whole number is recorded as the most significant digit of the new converted
number. The new fractional portion is then multiplied again by the base with the whole number
portion being recorded as the next lower order numeral. This process is repeated until the product
yields a fractional component equal to zero or the desired level of accuracy has been achieved.
Let‘s convert 11.37510 to binary. Example below shows the step-by-step process converting a
decimal number to binary.

13
Decimal to Octal
Let‘s convert 10.410 to octal with an accuracy of four fractional digits. When converting the
fractional component of the number, the algorithm is continued until four digits worth of
fractional numerals have been achieved. Once the accuracy has been achieved, the conversion is
finished even though a product with a zero fractional value has not been obtained. Example
below shows the step-by-step process converting a decimal number to octal with a fractional
accuracy of four digits.

14
Converting Decimal to Octal
Converting Decimal to Hexadecimal
Let‘s convert 254.65510 to hexadecimal with an accuracy of three fractional digits. When
doing this conversion, all of the divisions and multiplications are done using decimal. If the
results end up between 1010 and 1510, then the decimal numbers are substituted with their hex
symbol equivalent (i.e., A to F). Example below shows the step-by-step process of converting a
decimal number to hex with a fractional accuracy of three digits.

15
Converting Between 2n Bases
Converting between 2n bases (e.g., 2, 4, 8, 16) takes advantage of the direct mapping that
each of these bases has back to binary. Base 8 numbers take exactly 3 binary bits to represent all
8 symbols (i.e., 08 = 0008, 78 = 1112). Base 16 numbers take exactly 4 binary bits to represent all
16 symbols (i.e., 016 = 00002, F16 = 11112).
Binary to Octal
Example below shows the step-by-step process of converting a binary number to octal.

16
Converting Binary to Octal
Binary to Hexadecimal
Example below shows the step-by-step process of converting a binary number to hexadecimal.

Converting Binary to Hexadecimal

Octal to Binary
When converting to binary from any 2n base, each of the symbols in the originating
number are replaced with the appropriate-sized number of bits. An octal symbol will be replaced

17
with 3 binary bits while a hexadecimal symbol will be replaced with 4 binary bits. Any leading
or trailing 0s can be removed from the converted number once complete. Example below shows
the step-by-step process of converting an octal number to binary.

Converting Octal to Binary

Hexadecimal to Binary
Example below shows the step-by-step process of converting a hexadecimal number to binary.

Converting Hexadecimal to Binary

Octal to Hexadecimal
When converting between 2n bases (excluding binary) the number is first converted into
binary and then converted from binary into the final 2n base using the algorithms described

18
before. Example below shows the step-by-step process of converting an octal number to
hexadecimal

Converting Octal to Hexadecimal

Hexadecimal to Octal
Example below shows the step-by-step process of converting a hexadecimal number to octal.

Converting Hexadecimal to Octal

19
Binary code
Binary codes are special strings of binary digits. While the binary system of
representation is the most extensively used one in digital systems, including computers, octal and
hexadecimal number systems are commonly used for representing groups of binary digits. The
binary coding system, called the straight binary code becomes very cumbersome to handle when
used to represent larger decimal numbers. To overcome this shortcoming, and also to perform
many other special functions, several binary codes have evolved over the years. Some of the
better-known binary codes, including those used efficiently to represent numeric and
alphanumeric data, and the codes used to perform special functions, such as detection and
correction of errors are binary coded decimal (BCD) code, Gray code, Excess-3 code, and 7-
segment code.
BINARY CODED DECIMAL (BCD)
The binary coded decimal (BCD) is a type of binary code used to represent a given
decimal number in an equivalent binary form. BCD-to-decimal and decimal-to-BCD conversions
are very easy and straightforward. It is also far less cumbersome an exercise to represent a given
decimal number in an equivalent BCD code than to represent it in the equivalent straight binary
form.
The BCD equivalent of a decimal number is written by replacing each decimal digit in
the integer and fractional parts with its four-bit binary equivalent. As an example, the BCD
equivalent of (23.15)10 is written as (0010 0011.0001 0101)BCD. The BCD code described
above is more precisely known as the 8421 BCD code, with 8, 4, 2 and 1 representing the
weights of different bits in the four-bit groups, starting from MSB and proceeding towards LSB.
This feature makes it a weighted code, which means that each bit in the four-bit group
representing a given decimal digit has an assigned
The 8421 code is a type of BCD (binary coded decimal) code means that each decimal
digit, 0 through 9, is represented by a binary code of four bits. The designation 8421 indicates the
binary- weights of the four bits (23, 22, 21, 2°). The ease of conversion between 8421 code
numbers and the familiar decimal numbers is the main advantage of this code. The 8421 code is
the predominant BCD code, and when we refer to BCD, we always mean the 8421 code unless
otherwise stated.

20
 To express any decimal number in BCD, simply replace each decimal digit with the
appropriate 4-bit code

It is equally easy to determine a decimal number from a BCD number. Start at the rightmost bit
and break the code into groups of four bits. Then write the decimal digit represented by each 4-
bit group.

Excess-three Code
The excess-3 code is another important BCD code. It is particularly significant for
arithmetic operations as it overcomes the shortcomings encountered while using the 8421 BCD
code to add two decimal digits whose sum exceeds 9. The excess-3 code has no such limitation,
and it considerably simplifies arithmetic operations. Table below lists the excess-3 code for the
decimal numbers 0–9.
The excess-3 code for a given decimal number is determined by adding ‗3‘ to each
decimal digit in the given number and then replacing each digit of the newly found decimal
number by its four-bit binary equivalent. It may be mentioned here that, if the addition of ‗3‘ to a
digit produces a carry, as is the case with the digits 7, 8 and 9, that carry should not be taken

21
forward. The result of addition should be taken as a single entity and subsequently replaced with
its excess-3 code equivalent.

As an example, let us find the excess-3 code for the decimal number 597:
• The addition of ‗3‘ to each digit yields the three new digits/numbers ‗8‘, ‗12‘ and ‗10‘.
• The corresponding four-bit binary equivalents are 1000, 1100 and 1010 respectively.
• The excess-3 code for 597 is therefore given by: 1000 1100 1010 = 100011001010.
Example 2.3
Find (a) the excess-3 equivalent of (237.75)10 and (b) the decimal equivalent of the excess-3
number 110010100011.01110101.
Solution
(a) Integer part = 237. The excess-3 code for (237)10 is obtained by replacing 2, 3 and 7 with
the four-bit binary equivalents of 5, 6 and 10 respectively. This gives the excess-3 code
for (237)10 as: 0101 0110 1010 = 010101101010.
(b) Fractional part = .75. The excess-3 code for (.75)10 is obtained by replacing 7 and 5 with
the four-bit binary equivalents of 10 and 8 respectively. That is, the excess-3 code for
(.75)10 = .10101000. Combining the results of the integral and fractional parts, the
excess-3 code for
(237.75)10 = 010101101010.10101000.
Seven Segment Display Code
A seven-segment (LED) display is used to display binary to decimal information. It is a very
common code that practically everyone encounters every day is the 7-segment type of code.
Seven-segment displays are very common and are found almost everywhere, from pocket
calculators, digital clocks and electronic test equipment to petrol pump, digital watches,

22
voltmeters, blood pressure monitors, microwave ovens, toys s. A single seven-segment display or
a stack of such displays invariably meets our display requirement. There are both LED and LCD
types of seven-segment display. Furthermore, there are common anode-type LED displays where
the arrangement of different diodes, designated a, b, c, d, e, f and g. An example of this code is
shown in Table below for a 7-segment display.

7-segment code for a 7-segment display

Gray Code
The Gray code was designed by Frank Gray at Bell Labs and patented in 1953. It is an
unweighted binary code in which two successive values differ only by 1 bit. Owing to this
feature, the maximum error that can creep into a system using the binary Gray code to encode
data is much less than the worst-case error encountered in the case of straight binary encoding.
Table 2.3 lists the binary and Gray code equivalents of decimal numbers 0–15. An examination
of the four-bit Gray code numbers, as listed in Table below, shows that the last entry rolls over to
the first entry. That is, the last and the first entry also differ by only 1 bit. This is known as the
cyclic property of the Gray code.
Although there can be more than one Gray code for a given word length, the term was
first applied to a specific binary code for non-negative integers and called the binary-reflected
Gray code or simply the Gray code.
There are various ways by which Gray codes with a given number of bits can be
remembered. One such way is to remember that the least significant bit follows a repetitive
pattern of ‗2‘ (11, 00, 11, … ), the next higher adjacent bit follows a pattern of ‗4‘ (1111, 0000,
1111, … ) and so on. We can also generate the n-bit Gray code recursively by prefixing a ‗0‘ to

23
the Gray code for n −1 bits to obtain the first 2n-1 numbers, and then prefixing ‗1‘ to the reflected
Gray code for n −1 bits to obtain the remaining 2n-1 numbers. The reflected Gray code is nothing
but the code written in reverse order. The process of generation of higher-bit Gray codes using
the reflect and-prefix method is illustrated in Table below. The columns of bits between those
representing the Gray codes give the intermediate step of writing the code followed by the same
written in reverse order.

Applications
1. The Gray code is used in the transmission of digital signals as it minimizes the occurrence of
errors.
2. The Gray code is preferred over the straight binary code in angle-measuring devices. Use of
the Gray code almost eliminates the possibility of an angle misread, which is likely if theangle is
represented in straight binary. The cyclic property of the Gray code is a plus in this application.
3. The Gray code is used for labelling the axes of Karnaugh maps, a graphical technique used for
minimization of Boolean expressions.
4. The use of Gray codes to address program memory in computers minimizes power
consumption. This is due to fewer address lines changing state with advances in the program
counter.
5. Gray codes are also very useful in genetic algorithms since mutations in the code allow for
mostly incremental changes. However, occasionally a one-bit change can result in a big leap,
thus leading to new properties

24
Binary arithmetic is essential in all digital computers and in many other types of digital systems.
To understand digital systems, you must know the basics of binary addition. subtraction,
multiplication, anddivision.

Binary Addition

The four basic rules for adding binary digits (bits) are as follows:

0+0=0 Sum of 0 with a carry of 0

0+1 = 1 Sum of I with a carry of 0

1+0=1 Sum of I with a carry of 0

1 + I = 10 Sum of 0 with a carry of I

Remember, in binary 1 + 1 = 10, not 2.

Notice that the first three rules result in a single bit and in the fourth rule the addition of two Is
yields a binary two (10). When binary numbers are added, the last condition creates a sum of 0 in
a given column and a carry of I over to the next column to the left,as illustrated in the following
addition of 1 1 + 1:

Carry Carry

In the right column, 1 + 1=0with a carry of I to the next column to the left. In the middle column,
1+1+0= 0 with a carry of I to the next column to the left. In the left column, I + 0 + 0 = 1.

When there is a carry of I.you have a situation in which three bits are being added (a bit in each
of the two numbers and a carry bit). This situation is illustrated as follows:

25
Binary Subtraction

The four basic rules for subtracting bits are as follows:

0-0=0

1–1=0

1–0=1

10 – 1 = 1 0 - 1 with a borrow of 1

Remember in binary 10 - 1 = 1, not 9.

When subtracting numbers, you sometimes have to borrow from the next column to the left. A
borrow is required in binary only when you try to subtract a 1 from a 0. In this case, when a 1 is
borrowed from the next column to the left, a 10 is created in the column being subtracted, and
the last of the four basic rules just listed must be applied.

Binary Multiplication

26
The four basic rules for multiplying bits are as follows:

0X0=0

0 X 1=0

1X0=0

1 X 1= 1

Multiplication is performed with binary numbers in the same manner as with decimal numbers. It
involves forming partial products, shifting each successive partial product left one place, and
then adding all the partial products.

Binary Division

Division in binary follows the same procedure as division in decimal, as Example below
illustrates. The equivalent decimal divisions are also given

27
Logic Gates and Related Devices
Logic gates are electronic circuits that can be used to implement the most elementary
logic expressions, also known as Boolean expressions. The logic gate is the most basic building
block of combinational logic. There are three basic logic gates, namely the OR gate, the AND
gate and the NOT gate. Other logic gates that are derived from these basic gates are the NAND
gate, the NOR gate, the EXCLUSIVEOR gate and the EXCLUSIVE-NOR gate.
Truth Table
A truth table lists all possible combinations of input binary variables and the
corresponding outputs of a logic system. The logic system output can be found from the logic
expression, often referred to as the Boolean expression, that relates the output with the inputs of
that very logic system.
When the number of input binary variables is only one, then there are only two possible
inputs, i.e. ‗0‘ and ‗1‘. If the number of inputs is two, there can be four possible input
combinations, i.e. 00, 01, 10 and 11. Figure below shows the truth table of the two-input logic
system represented. The logic system of Fig. below is such that Y= 0 only when both A= 0 and
B= 0. For all other possible input combinations, output Y = 1. Similarly, for three input binary
variables, the number of possible input combinations becomes eight, i.e. 000, 001, 010, 011, 100,
101, 110 and 111. This statement can be generalized to say that, if a logic circuit has n binary
inputs, its truth table will have 2n possible input combinations, or in other words 2n rows. Figure
4.2 shows the truth table of a three-input logic circuit, and it has 8 (= 23) rows.
A B X
0 0 0
0 1 1
1 0 1

28
1 1 1

A B C Y
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 0
1 0 0 0
1 0 1 0
1 1 0 0
1 1 1 1

Logic Gates
The logic gate is the most basic building block of any digital system, including
computers. Each one of the basic logic gates is a piece of hardware or an electronic circuit that
can be used to implement some basic logic expression. While laws of Boolean algebra could be
used to do manipulation with binary variables and simplify logic expressions, these are actually
implemented in a digital system with the help of electronic circuits called logic gates. The three
basic logic gates are the OR gate, the AND gate and the NOT gate.

OR Gate
An OR gate performs an ORing operation on two or more than two logic variables. The
OR operation on two independent logic variables A and B is written as Y = A + B and reads as Y
equals A OR B and not as A plus B. An OR gate is a logic circuit with two or more inputs and
one output. The output of an OR gate is LOW only when all of its inputs are LOW. For all other
possible input combinations, the output is HIGH. This statement when interpreted for a positive
logic system means the following. The output of an OR gate is a logic ‗0‘ only when all of its
inputs are at logic ‗0‘. For all other possible input combinations, the output is a logic ‗1‘. Figure

29
below shows the circuit symbol and the truth table of a two-input OR gate. The operation of a
two-input OR gate is explained by the logic expression

The OR operation

Y=A+B
AB Y
000
011
101
111
As an illustration, if we have four logic variables and we want to know the logical output of (A+
B+C+D, then it would be the output of a four-input OR gate with A, B, C and D as its inputs.
AND Gate
An AND gate is a logic circuit having two or more inputs and one output. The output of
an AND gate is HIGH only when all of its inputs are in the HIGH state. In all other cases, the
output is LOW. When interpreted for a positive logic system, this means that the output of the
AND gate is a logic ‗1‘ only when all of its inputs are in logic ‗1‘ state. In all other cases, the
output is logic ‗0‘. The logic symbol and truth table of a two-input AND gate are shown in
Figures below.
Do the logic symbols of three-input and four-input AND gates respectively.
The AND operation on two independent logic variables A and B is written as Y =AB and reads
as Y equals A AND B. Here, A and B are input logic variables and Y is the output. An AND gate
performs an ANDing operation:

30
 The AND operation.

Y=A.B
ABY
000
010
100
111
NOT Gate
A NOT gate is a one-input, one-output logic circuit whose output is always the
complement of the input. That is, a LOW input produces a HIGH output, and vice versa. When
interpreted for a positive logic system, a logic ‗0‘ at the input produces a logic ‗1‘ at the output,
and vice versa. It is also known as a ‗complementing circuit‘ or an ‗inverting circuit‘. Figure
below shows the circuit symbol.
The NOT operation changes one logic level to the opposite logic level, as indicated in
Figure below. When the input is HIGH (1), the output is LOW (0). When the input is LOW, the
output is HIGH. In either case, the output is not the same as the input. The NOT operation is
implemented by a logic circuit known as an inverter.

The NOT operation

BOOLEAN OPERATIONS AND EXPRESSIONS
Boolean algebra is the mathematics of digital systems. A basic knowledge of Boolean
algebra is indispensable to the study and analysis of logic circuits.
Variable, complement, and literal are terms used in Boolean algebra. A variable is a
symbol (usually an italic uppercase letter) used to represent a logical quantity. Any single
variable can have a I or a 0 value. The complement is the inverse of a variable and is indicated

31
by a bar over the variable (over bar). For example, the complement of the variable A is A . If A =
I. then A is 0. If A is 0 then A = 1. The complement of the variable A is read as "not A" or "A
bar." Sometimes a prime symbol rather than an over bar is used to denote the complement of a
variable; for example A1. A literal is a variable or the complement of a variable.
Boolean Addition
Boolean addition is equivalent to the OR operation and the basic rules are illustrated with
their relation to the OR gate as follows:

In Boolean algebra, a sum term is a sum of literals. In logic circuits, a sum term is produced by
an OR operation with no AND operations involved. Some examples of sum terms are
A sum term is equal to 1 when one or more of the
literals in the term are 1. A sum term is equal to 0 only if each of the literals is 0.

Boolean Multiplication
Boolean multiplication is equivalent to the AND operation and the basic rules arc
illustrated with their relation to the AND gate as follows:

The- AND gate is a Boolean multiplier

In Boolean algebra, a product term is the product of literals. In logic circuits, a product
term is produced by an AND operation with no OR operations involved. Some examples of

32
product terms are A product term is equal to I only if each of the
literals in the term is I. A product term is equal to 0 when one or more of the literals are 0.

LAWS AND RULES OF BOOLEAN ALGEBRA

As in other areas of mathematics, there are certain well-developed rules and laws that
must be followed in order to properly apply Boolean algebra. The most important of these are
presented in this section.
Laws of Boolean Algebra
The basic laws of Boolean algebra—the commutative laws for addition and multiplication the
associative laws for addition and multiplication, and the distributive law -are the same as in
ordinary algebra. Each of the laws is illustrated with two or three variables, but the number of
variables is not limited to this.
Commutative Laws: The commutative law of addition for two variables is written as
A + B= B + A
This law states that the order in which the variables are ORcd makes no difference. In
Boolean algebra as applied to logic circuits, addition and the OR operation are the same. Figure
4-1 illustrates the commutative law as applied to the OR gate and shows that it doesn't matter to
which input each variable is applied. (The symbol  means "equivalent to")

Figure 4-1: Application of commutative law of addition.

The commutative law of multiplication for two variables is
AB = BA
This law states that the order in which the variables are ANDed makes no difference. Figure
4-2 illustrates this law as applied to the AND gate.

33
Figure 4-2: Application of commutative law of multiplication.
Associative Laws: The associative law of addition is written as follows for three variables:
A + (B + C) = (A + B)+ C
This law states that when ORing more than two variables, the result is the same regardless of the
grouping of the variables. Figure 4-3 illustrates this law as applied to 2-input OR gates.

Figure 4-3: Application of associative law of addition.

The associative law of multiplication is written as follows for three variables:
A(BC) = {AB)C
This law states that it makes no difference in what order the variables are grouped when
ANDing more than two variables. Figure 4-4 illustrates this law as applied to 2-input
AND gates

Application of associative law of multiplication

Distributive Law: The distributive law is written for three variables as follows:
A(B + C) = AB +AC
This law states that ORing two or more variables and then ANDing the result with a single
variable is equivalent to ANDing the single variable with each of the two or more variables and
then ORing the products. The distributive law also expresses the process of factoring in which
the common variable A is factored out of the product terms, for example. AB+AC=A (B+C)
Figure 4-5 illustrates the distributive law in terms of gate implementation.

34
Application of dntributrve law.
Rules of Boolean Algebra
Table 4-I lists 12 basic rules that are useful in manipulating and simplifying Boolean
expressions. Rules I through 9 will be viewed in terms of their application to logic gates. Rules
10 through 12 will be derived in terms of the simpler rules and the laws previously discussed.

Basic Rules of Boolean algebra

Rule 1: A + 0 = A. A variable ORed with 0 is always equal to the variable. If the input
variable A is 1, the output variable X is 1, which is equal to A. If A is 0, the output is 0 which is
also equal to A. This rule is illustrated in the Figure below where the lower input is fixed at 0.

Rule 2: A + 1 = 1. A variable ORed with 1 is always equal to 1. A 1 on an input to an OR gate

produces 1 on the output, regardless of the value of the variable on the other input. This rule is
illustrated in the figure below, where the lower input is fixed at I.

Rule 3: A . 0 = 0. A variable ANDed with 0 is always equal to 0. Any time one input to an AND
gate is 0, the output is 0 regardless of the value of the variable on the other input. This rule is
illustrated below where the lower input is fixed at 0.

35
Rule 4: A . 1 = A. A variable ANDed with 1 is always equal to the variable. If A is 0 the output
of the AND gate is 0. If A is 1, the output of the AND gate is 1 because both inputs are now 1s.
This rule is shown in the figure below where the lower input is fixed at I.

Rule 5: A + A = A. A variable ORed with itself is always equal to the variable. If A is 0. then 0 +
0 = 0; and if A is 1. then 1+ 1 = 1.This is shown in Figure below where both in puts are the same
variable.

Rule 6: A  A  1 . A variable ORed with its complement is always equal to 1. If A is 0, then

0  0  0  1  1 . If A is 1, then 1  1  1  0  1 . See Figure below, where one input is the
complement of the other.

Rule 7: A . A = A. A variable ANDed with itself is always equal to the variable. If A = 0, then
0.0 = 0; and if A = 1, then 1 . 1= 1. Figure below illustrates this rule.

Rule 8: A. A  0 . A variable ANDed with its complement is always equal to 0. Either A or A will
always be 0; and when a 0 is applied to the input of an AND gate, the output will be 0 also.
Figure below illustrates this rule.

36
Rule 9: A  A . The double complement of a variable is always equal to the variable. If you start
with the variable A and complement (invert) it once, you get A . If you then take A and
complement (invert) it, you get A. which is the original variable. This rule is shown in Figure
below using inverters.

Rule 10: A +AB =A. This rule can be proved by applying the distributive law, rule 2 and rule 4
as follows:
A + AB = A( 1 + B) Factoring (distributive law)
=A•1 Rule 2: (1+ B) = 1
=A Rule 4: A . 1= A
The proof is shown in the table below, which shows the truth table and the resulting logic circuit
simplification.

Rule 10: A+ AB = A.
Rule 11: A  AB  A  B . This rule can be proved as follows:
̅ ( ) ̅ Using Rule 10 :
( ̅ ) Using Associative Law
( ̅) Using Distributive law
( ) using Rule 6
=A+B

37
The proof is shown on the table below, which shows the truth table and the resulting logic circuit
simplification.

Rule 11: A  AB  A  B .
Rule 12: (A + B)(A + C) = A + BC. This rule can be proved as follows:
(A + B)(A + C) = AA + AC + AB + BC Distributive law
= A + AC + AB + BC Rule 7: AA = A
=A( 1 + C) + AB + BC Factoring (distributive law)
= A • 1 + AB + BC Rule 2: 1+ C = 1
= A(1 + B) + BC Factoring (distributive law)
= A . 1 + BC Rule 2: I + B = I
= A + BC Rule 4: A • 1 = A
The proof is shown in Table below, which shows the truth table and the resulting logic circuit
simplification.

Rule 12: (A 4 B) (A 4 C) = A + BC
DEMORGAN'S THEOREMS

38
 DeMorgan a mathematician who knew Boole, proposed two theorems that are an
important part of Boolean algebra. In practical terms, DeMorgan's theorems provide
mathematical verification of the equivalency of the NAND and negative-OR gates and the
equivalency of the NOR and negative - ANDgates.
One of DeMorgan's theorems is stated as follows:
The complement of a product of variables is equal to the sum of the complements of the
variables.
Stated another way;
The complement of two or more ANDed variables is equivalent to the OR of the complements of
the individual variables.
The formula for expressing this theorem for two variables is:
XY  X  Y
DeMorgan's second theorem is stated as follows:
The complement of a sum of variables is equal to the product of the complements of the
variables.
Stated another way;
The complement of two or more ORed variables is equivalent to the AND of the complements of
the individual variables.
The formula for expressing this theorem for two variables is:
X  Y  X .Y
Figures below shows the gate equivalencies and truth tables for the Equations above.
Gate equivalencies and the corresponding truth tables that illustrate DeMorgan's theorems.
Notice the equality of the two output columns in each table. This shows that the equivalent gates
perform the same logic function.
As stated, DeMorgan's theorems also apply to expressions in which there are more than two
variables. The following examples illustrate the application of DeMorgan's theorems to 3-
variable and 4-variable expressions

39
Applying DeMorgan's Theorems
The following procedure illustrates the application of DeMorgan's theorems and Boolean

algebra to the specific expression A  BC  D( E  F )

Step I: Identify the terms to which you can apply DeMorgan's theorems, and think of each term


as a single variable. Let A  BC  X and D E  F  Y 

COMPUTER ORGANIZATION AND DESIGN

The Von Neumann model of a computer, shown below, consists of four main
components: the input, the output, the memory, and the microprocessor (or CPU). The parts that
you purchased for your computer can all be categorized into one of these four groups. The
keyboard and mouse are examples of input devices. The monitor and speakers are examples of
output devices. The different types of memory (cache, read-only memory (ROM), random-access
memory (RAM), and the disk drive) are all considered part of the memory box in the model. In
this section, the focus is not on the mechanical aspects of the input, output, and storage devices.
Rather, the focus is on the design of the digital circuitry of the microprocessor, the memory, and
other supporting digital logic circuits.
The logic circuit for the microprocessor can be divided into two parts: the datapath and
the control unit, as shown in Figure below. Figure 1.2 shows the details inside the control unit
and the datapath. The datapath is responsible for the actual execution of all data operations
performed by the microprocessor, such as the addition of two numbers inside the arithmetic logic
unit (ALU). The datapath also includes registers for the temporary storage of your data. The

40
functional units inside the datapath, which in our example includes the ALU and the register, are
connected together with multiplexers and data signal lines. The data signal lines are for
transferring data between two functional units. Data signal lines in the circuit diagram are
represented by lines connecting two functional units. Sometimes, several data signal lines are
grouped together to form a bus.
Multiplexers, also known as MUXes, are for selecting data from two or more sources to
go to one destination. In the sample circuit, a 2-to-1 multiplexer is used to select between the
input data and the constant ‗0‘ to go to the left operand of the ALU. The output of the ALU is
connected to the input of the register. The output of the register is connected to three different
destinations: (1) the right operand of the ALU, (2) an OR gate used as a comparator for the test
―not equal to 0,‖ and (3) a tri-state buffer. The tri-state buffer is used to control the output of the
data from the register.

Von Neumann model of a computer.

Internal parts of a microprocessor

41
 Even though the datapath is capable of performing all of the data operations of the
microprocessor, it cannot, however, do it on its own. In order for the datapath to execute the
operations automatically, the control unit is required. The control unit, also known as the
controller, controls all of the operations of the datapath, and therefore, the operations of the
entire microprocessor. The control unit is a finite state machine (FSM) because it is a machine
that executes by going from one state to another and that there are only a finite number of states
for the machine to go to. The control unit is made up of three parts: the next-state logic, the state
memory, and the output logic. The purpose of the state memory is to remember the current state
that the FSM is in. The next-state logic is the circuit for determining what the next state should
be for the machine. And the output logic is the circuit for generating the actual control signals for
controlling the datapath.
Every digital logic circuit, regardless of whether it is part of the control unit or the
datapath, is categorized as either a combinational circuit or a sequential circuit. A combinational
circuit is one where the output of the circuit is dependent only on the current inputs to the circuit.
For example, an adder circuit is a combinational circuit. It takes two numbers as inputs. The
adder evaluates the sum of these two numbers and outputs the result.
A sequential circuit, on the other hand, is dependent not only on the current inputs, but
also on all the previous inputs. In other words, a sequential circuit has to remember its past
history. For example, the up-channel button on a TV remote is part of a sequential circuit.
Pressing the up-channel button is the input to the circuit. However, just having this input is not
enough for the circuit to determine what TV channel to display next. In addition to the upchannel
button input, the circuit must also know the current channel that is being displayed, which is the
history. If the current channel is channel 3, then pressing the up-channel button will change the
channel to channel 4.
Since sequential circuits are dependent on the history, they must therefore contain
memory elements for remembering the history; whereas combinational circuits do not have
memory elements. Examples of combinational circuits inside the microprocessor include the
next-state logic and output logic in the control unit, and the ALU, multiplexers, tri-state buffers,
and comparators in the datapath. Examples of sequential circuits include the register for the state
memory in the controller and the registers in the datapath. The memory in the Von Neuman
computer model is also a sequential circuit.
Regardless of whether a circuit is combinational or sequential, they are all made up of the
three basic logic gates: AND, OR, and NOT gates. From these three basic gates, the most
powerful computer can be made. Furthermore, these basic gates are built using transistors — the
fundamental building blocks for all digital logic circuits. Transistors are just electronic binary
switches that can be turned on or off. The on and off states of a transistor are used to represent
the two binary values: 1 and 0.

Analysis of Combinational Circuits

42
 Very often, we are given a digital logic circuit, and we would like to know the operation
of the circuit. The analysis of combinational circuits is the process in which we are given a
combinational circuit, and we want to derive a precise description of the operation of the circuit.
In general, a combinational circuit can be described precisely either with a truth table or with a
Boolean function.

Using a Boolean Function of logic circuits

Boolean algebra provides a concise way to express the operation of a logic circuit formed
by a combination of logic gates so that the output can be determined for various combinations of
input values.
Boolean Expression for a Logic Circuit
To derive the Boolean expression for a given logic circuit, begin at the left-most inputs
and work toward the final output, writing the expression for each gate. For the example circuit,
in the Figure below, the Boolean expression is determined as follows:
1. The expression for the left-most AND gate with inputs C and D is CD.
2. The output of the left-most AND gate is one of the inputs to the OR gate and B is the other
input. Therefore, the expression for the OR gate is B + CD.
3. The output of the OR gate is one of the inputs to the right-most ANDgate and A is the other
input. Therefore, the expression for this AND gate is A(B + CD), which is the final output
expression for the entire circuit.

Constructing a Truth Table for a Logic Circuit

Once the Boolean expression for a given logic circuit has been determined, a truth table
that shows the output for all possible values of the input variables can be developed. The
procedure requires that you evaluate the Boolean expression for all possible combinations of
values for the input variables. In the case of the circuit in Figure above, there are four input
variables (A. B, C, and D) and therefore sixteen (24 = 16) combinations of values are possible.
Evaluating the Expression: To evaluate the expression A(B + CD), first find the values
of the variables that make the expression equal to 1, using the rules for Boolean addition and

43
multiplication. In this case, the expression equals 1 only if A = 1 and B + CD = 1 because A(B +
CD) = 1 • 1= 1
Now determine when the B + CD term equals 1.The term B + CD = 1 if either B = 1 or
CD = 1 or if both B and C + D equal I because
B + CD =1+0=1
B + CD = 0+1= 1
B + CD =1 + 1 = 1
The term CD = 1 only if C = 1 and D= 1.
To summarize the expression A(B + CD) = I when A = 1 and B = 1 regardless of the
values of C and D or when A = I and C = 1 and D = I regardless of the value of B. The
expression A(B + CD) = 0 for all other value combinations of the variables.
Putting the Results in Truth Table Format: To analyses combinational circuit using
Truth Table Format we start by first listing all of the inputs found in the circuit, one input per
column, followed by all of the outputs found in the circuit. The next step is to enumerate all
possible combinations of 0‘s and 1‘s for all of the input variables. In general, for a circuit with n
inputs, there are 2n combinations. Next, place a 1 in the output column for each combination of
input variables that was determined in the evaluation. This is done by substituting the values for
the input variables and tracing through the circuit to the output. Finally, place a 0 in the output
column for all other combinations of input variables.

44
Sample combinational circuit

Figure 3.2 Deriving the truth table for the sample circuit in Figure

Continuing in this fashion for all of the input combinations, we can complete the final
truth table for the circuit, as shown in Figure 3.2(e).

Exercise 3.1: Deriving a truth table from a circuit diagram

45
Derive the truth table for the following circuit with three inputs, A, B and C, and two outputs, P
and Q:

To derive a Boolean function that describes a combinational circuit below, we simply write
down the Boolean logical expressions at the output of each gate (instead of substituting actual
values of 0‘s and 1‘s for the inputs) as we trace through the circuit from the primary input to the
primary output. Using the sample combinational circuit of Figure 3.1, we note that the logical
expression for the output of the top AND gate is x'y'z. The logical expressions for the following
AND gates are, respectively x'yz, xy'z, and xyz. Finally, the outputs from these AND gates are
all ORed together. Hence, we get the final expression

f = x'y'z + x'yz + xy'z + xyz

To help keep track of the expressions at the output of each logic gate, we can annotate the
outputs of each logic gate with the resulting logical expression as shown here.

Example 3.2: Deriving a Boolean function from a circuit diagram

If a circuit has two or more outputs, then there must be one equation for each of the outputs. All
the equations are then derived totally independent of each other.

46
Synthesis of Combinational Circuits

Synthesis of combinational circuits is just the reverse procedure of the analysis of

combinational circuits. In synthesis, we start with a description of the operation of the circuit.
From this description, we derive either the truth table or the Boolean logical function that
precisely describes the operation of the circuit. Once we have either the truth table or the logical
function, we can easily translate that into a circuit diagram.
For example, let us construct a 3-bit comparator circuit that outputs a 1 if the number is
greater than or equal to 5 and outputs a 0 otherwise. In other words, construct a circuit that
outputs a 0 if the input is a number between 0 and 4 inclusive and outputs a 1 if the input is a
number between 5 and 7 inclusive. The reason why the maximum number is 7 is because the
range for an unsigned 3-bit binary number is from 0 to 7. Hence, we can use the three bits, x2,
x1, and x0, to represent the 3-bit input value to the comparator. From the description, we obtain
the following truth table:

In constructing the circuit, we are interested only in when the output is a 1 (i.e., when the
function f is a 1).
Thus, we only need to consider the rows where the output function f = 1. From the
previous truth table, we see that there are three rows where f = 1, which give the three AND
terms x2x1'x0, x2x1x0', and x2x1x0. Notice that the variables in the AND terms are such that it is
inverted if its value is a 0, and not inverted if its value is a 1. In the case of the first AND term,
we want f = 1 when x2 = 1 and x1 = 0 and x0 = 1, and this is satisfied in the expression x2x1'x0.
Similarly, the second and third AND terms are satisfied in the expressions x2x1x0' and x2x1x0
respectively. Finally, we want f = 1 when either one of these three AND terms is equal to 1. So
we ORed the three AND terms together giving us our final expression:

f = x2x1'x0 + x2x1x0' + x2x1x0

47
In drawing the schematic diagram, we simply convert the AND operators to AND gates and OR
operators to OR gates. The equation is in the sum-of-products format, meaning that it is
summing (ORing) the product (AND) terms.

Synthesizing a combinational circuit from a truth table

Synthesize a combinational circuit from the following truth table. The three variables, a,
b, and c, are input signals, and the two variables, x, and y, are output signals.

abcxy

00010

00100

01011

01110

10001

10111

11010

11100

We can either first derive the Boolean equation from the truth table, and then derive the
circuit from the equation, or we can derive the circuit directly from the truth table. For this
example, we will first derive the Boolean equation. Since there are two output signals, there will
be two equations; one for each output signal.

y = a'bc' + ab'c' + ab'c

The combinational circuit constructed from these two equations is shown in Figure
3.3(a). Each 3-variable AND term is replaced by a 3-input AND gate. The three inputs to these
AND gates are connected to the three input variables a, b, and c, either directly if the variable is
not primed or through a NOT gate if the variable is primed. For output x, a 5-input OR gate is
used to connect the outputs of the five AND gates for the corresponding five AND terms. For
output y, a 3-input OR gate is used to connect the outputs of the three AND gates.

Notice that the two AND terms, a'bc', and ab'c, appear in both the x and the y equations.
As a result, we do not need to generate these two signals twice. Hence, we can reduce the size of
the circuit by not duplicating these two AND gates, as shown in Figure 3.3(b).

48
Types of Sequential Logic Circuits

Asynchronous Sequential Circuits − Do not use clock signals, instead the circuit is driven by the
pulses of input signal.

Synchronous Sequential Circuits − A digital circuit in which the change in the state of memory
element is synchronised by the clock signal.

Examples of sequential circuits − Counters, Registers, etc.

As the name suggests both Synchronous and Asynchronous Sequential Circuits are the
type of sequential circuits which uses feedback for the next output generation however on the
basis of the type of this feedback both circuits can be get differentiated.

Following are the important differences between Synchronous and Asynchronous Sequential
Circuits −

S/ Synchronous Sequential
Key Asynchronous Sequential Circuits
No. Circuits

Synchronous sequential circuits

On other hand Asynchronous sequential
are digital sequential circuits in
circuits are digital sequential circuits in which
1 Definition which the feedback to the input
the feedback to the input for next output
for next output generation is
generation is not governed by clock signals.
governed by clock signals.

In Synchronous sequential
On other hand unclocked flip flop or time
Memory circuits, the memory unit which
2 delay is used as memory element in case of
Unit is being get used for
Asynchronous sequential circuits.
governance is clocked flip flop.

On other hand there are chances for the

The states of Synchronous Asynchronous circuits to enter into a wrong
3 State sequential circuits are always state because of the time difference between
predictable and thus reliable. the arrivals of inputs. This is called as race
condition.

However on other hand the presence of

It is easy to design Synchronous feedback among logic gates causes instability
4 Complexity
sequential circuits issues making the design of Asynchronous
sequential circuits difficult.

5 Performance Due to the propagation delay of Since there is no clock signal delay, these are

49
S/ Synchronous Sequential
Key Asynchronous Sequential Circuits
No. Circuits

clock signal in reaching all fast compared to the Synchronous Sequential

elements of the circuit the Circuits
Synchronous sequential circuits
are slower in its operation speed

On other hand Asynchronous circuits are used

in low power and high speed operations such
Synchronous circuits are used
as simple microprocessors, digital signal
6 Example in counters, shift registers,
processing units and in communication
memory units.
systems for email applications, internet access
and networking.

50