COMPUTER ARCHITECTURE

UNIT I

DESCRIBING THE COMPUTER ARCHITECTURE AND ORGANIZATION,

COMPUTER ARITHMETIC, AND CPU DESIGN
LEARNING OUTCOMES

Describe computer architecture and organization, computer arithmetic, and CPU design

COURSE CONTENT

1. Data Representation in digital design

2. Data Types

3. Complements (signed and unsigned numbers)

4. Binary Codes

5. Signed and unsigned numbers

6. Binary Addition, Subtraction, Multiplication, Division

7. Logic Gates, Boolean algebra, Map Simplification (up to 4 variable maps): SOP, POS,
Don’t Care conditions
INTRODUCTION TO COMPUTER ORGANIZATION AND ARCHITECTURE (COA)

Introduction

Computer Organization and Architecture provides an in-depth knowledge of internal workings,

structuring, and implementation of a computer system.

It includes many foundational concepts and knowledge used in the design of a computer system.

In order to build a computer system, the first step is to design and develop the system architecture.

The next step in the system design process is to finalize the computer organization details

It is necessary to make a distinction between computer organization and architecture.

For example, it is an architectural issue whether a computer will have a multiply and division
instructions.

It is an organizational issue whether to implement multiplication and division by special unit or by

a mechanism that makes repeated use of the add and subtract unit to perform multiplication and
division, respectively.

The organizational issue may be based on which approach to be used depending on the speed of
operation, cost and size of the hardware and the memory required to perform the operation.

Many computer manufactures offer a family of computer models with different price and
performance characteristics.

These computers have the same architecture but different organizations.

Their architectures have survived for many years, but their organizations change with changing
technology.
For example, IBM has introduced many new computer models with improved technology to
replaced older models, offering the customer greater speed, lower cost or both.

These newer models have the same architecture with advance computer organizations.

In microcomputers, the relationship between computer architecture and organization is very close.

In which, changes in technology not only influence organization but also result in the introduction
of new powerful architecture.

The RISC (Reduced Instruction Set) machine is good example of this.

Computer Architecture

In order to understand the term computer architecture, let us first discuss what an architecture is.

The term architecture can be defined as an art and science of designing an object.

We generally relate the term architecture with the building because the building is one of the most
common object in the human world.

The architecture helps us to define the functional, physical and the performance standards for any
object.

Computer architecture refers to those

attributes of a system visible to a
programmer.

In other words, we can also say that the

computer architecture refers to the
attributes that have a direct impact on
the logical execution of the program.

The architectural attributes include the instruction set, data types, number of bits used to represent
data types, and techniques for addressing memory

Computer Organization
The computer organization is based on the computer architecture.

It is defined as the actual

implementation of a
computer in hardware

It refers to the operational

units and their
interconnections that realize
the architectural
specifications.

The organizational attributes

include those hardware
details transparent to
programmer, such as control
signals, interfaces between
the computer, memory and I/O peripherals

Computer Architecture vs Computer Organization

The following are some of the important differences between Computer Architecture and
Computer Organization.

No. Key Computer Architecture Computer Organization

1 Purpose Computer architecture explains what Computer organization explains how a
a computer should do. computer works.
2 Target Computer architecture provides Computer organization provides structural
functional behavior of computer relationships between parts of computer
system. system.
3 Design Computer architecture deals with Computer organization deals with low level
high level design. design.
4 Actors Actors in Computer architecture are Actor in computer organization is
hardware parts. performance.
5 Order Computer architecture is designed Computer organization is started after
first. finalizing computer architecture.

BASIC ORGANIZATION OF COMPUTER

The computer consists of five functionally independent unit: input, memory, arithmetic and logic,
output and control units.

The below shows these five functional units of a computer, and there physical locations in the
computer
1. Input Unit

The main function of the input unit is to provide the

data that will be operated on by the CPU as per the
program instructions

The most commonly used input devices for any

general purpose computer system include keyboard
and mouse.

The computer system can accept the input from a

number of input devices such as scanner, camera,
mouse or any other input devices connected to the
computer system.

2. Output Unit

The main function of the output unit is to present the data to the user that is processed by
the CPU as per the program instructions.
The most commonly used output devices for any
general purpose computer system include display
monitor, speaker and printer.

The computer system can send the output to a number

of output devices connected to the computer system
such as projector, speaker and disk memory.

3. Central Processing Unit (CPU)

The central
processing unit
(CPU) is said
to be the brain
of the
computer
system.

It is the CPU
that provides
the processing
power to the
computer.

The main function of the CPU is to execute the computer program.

The CPU executes the program by fetching program instructions one by one from the
main memory.

The basic function of control unit is to fetch the instructions stored in the main memory,
identify the operations and the devices involved in it, and accordingly generate control
signals to execute the desired operations. \

The CPU executes the program instructions by repetitively performing the instruction
cycle.

The instruction cycle consists of four steps that include;

 Fetch,
 Decode,
 Execute and
 Store

The CPU internally consists of three important units.

The three units together are referred as CPU.

These three units are

a) Control Unit (CU)

The control unit co-ordinates and controls the activities amongst the functional units.

The basic function

of control unit is to
fetch the
instructions stored
in the main memory,
identify the
operations and the
devices involved in
it, and accordingly
generate control
signals to execute
the desired operations.

The control unit uses control signals to determine when a given action is to take place.

It controls input and output operations, data transfers between the processor, memory
and input/output devices using timing signals.

The control and the arithmetic and logic units of a computer are usually many times
faster than other devices connected to a computer system.

This enables them to control a number of external input/output devices.

b) Arithmetic and Logic Unit (ALU)

The arithmetic and logic unit (ALU) is responsible for performing arithmetic operations
such as add, subtract, division and multiplication, and logical operations such as
ANDing, ORing, Inverting etc.
To perform these operations operands
from the main memory are brought into
high speed storage element called
registers of the processor.

Each register can store one word of data

and they are used to store frequently
used operands.

The access times to registers are

typically 5 to 10 times faster than access
times to memory.

After performing operation the result is either stored in the register or memory location.

c) CPU Registers

In the CPU, registers are very high speed memory placed inside the processor chip.

In memory hierarchy, the register is

the smallest in size but has the
highest data access speed.

The registers are used by the CPU

during the execution of program
instruction cycle.

Therefore, the registers are used by

the processor as temporary memory during the program execution.

Depending upon the processor architecture, the CPU can have a number of registers.

4. Memory Unit (MU)

The memory unit is used to store programs and data.

Usually, two types of memory devices are used to form a memory unit: primary storage
memory device and secondary storage memory device.

The primary memory, commonly called main memory is a fast memory used for the storage
of programs and active data (the data currently in process).

The main memory consists of a large number of semiconductor storage cells, each capable
of storing one bit of information.
These cells are read or
written by the central
processing unit in a group
of fixed size called word.

The main memory is

organized such that the
content of one word
containing n bits, can be
stored or retrieved in one
write or read operation,
respectively.

To access data from a particular word from main memory each word in the main memory
has a distinct address.

This allows access to any word from the main memory by specifying corresponding
address.

The number of bits in each word is referred to as the word length of the computer.

Typically, the word length varies from 8 to 64 bits.

The number of such word in the main memory decides the size of memory or capacity of
the memory.

This is one of specification of the computer.

The size of computer main memory varies from few million words to tens of million words.

An important characteristic of a memory is an access time (the time required to access one
word).

The access time for main memory should be as small as possible.

Typically, it is of the order of 10 to 100 nanoseconds.

This accessed time also depend on the type of memory.

In randomly accessed memories (RAMs), fixed time is required to access any word in the
memory.

However, in sequential access memories this time is not fixed.

The main memory consists of only randomly accessed memories.

These memories are fast but they are small in the capacities and expensive.

Therefore, the computer user the secondary storage memories such a magnetic tapes,
magnetic disks for the storage of large amount of data.

Factors affecting computer system performance

Factors that affect performance of a computer system includes

a) Number of processors (cores)

A computer can contain one or more processing units.

Each unit is called a core.

A core contains an ALU, control unit and registers.

It is common for computers to have two (dual), four (quad) or even more cores.

Computers with multiple cores have more power to run multiple programs at the same time.

However, doubling the number of cores will not simply double a computer's speed.

CPU cores have to communicate with each other through channels and this uses up some of
the extra speed.

Therefore, if we increase the number of cores in a processor, there will be an increase in the
number of channel.

b) Width of the data bus

The data bus is a set of parallel wires or connectors that transports data between the processor
and main memory.

By increasing the data bus from 32-bit to 64-bit, the computer can transfer twice as much
information at one time.

Therefore, increasing the size of the data bus improves the system performance of the
computer.

c) Cache memory

Cache is a small amount of memory which can either be part of the CPU or closer to the CPU
than RAM.

It is used to temporarily hold instructions and data that the CPU is likely to reuse.

The CPU control unit automatically checks cache for instructions before requesting data from
RAM.

This saves fetching the instructions and data repeatedly from RAM - a relatively slow process
which might otherwise keep the CPU waiting.

Transfers to and from cache take less time than transfers to and from RAM.

The more cache there is, the more data can be stored closer to the CPU.

Cache is graded as Level 1 (L1), Level 2 (L2) and Level 3 (L3):

 L1 is usually part of the CPU chip itself and is both the smallest and the fastest to
access.

Its size is often restricted to between 8 KB and 64 KB.

 L2 and L3 caches are bigger than L1.

They are extra caches built between the CPU and the RAM.

Sometimes L2 is built into the CPU with L1.

L2 and L3 caches take slightly longer to access than L1.

The more L2 and L3 memory available, the faster a computer can run.

d) Clock speed
The clock speed also known as clock rate indicates how fast the CPU can run.

This is measured in megahertz (MHz) or gigahertz (GHz) and corresponds with how
many instruction cycles the CPU can deal with in a second.

A 2 gHz CPU performs two billion cycles a second.

A faster CPU uses more energy and creates more heat.

A computer will normally have a maximum clock speed set by default, but it is possible to
change this speed in the computer BIOS.

Some people increase a CPU clock speed to try to make their computer run faster - this is
called overclocking.

There are limits to how fast a CPU can run and its circuitry cannot always keep up with an
overclocked speed.

If the CPU cannot keep up with the pace of the clock, the data is corrupted.

CPUs can also overheat if they are forced to work faster than they were designed to work.

DATA REPRESENTATION IN DIGITAL DESIGN

Introduction

Data and instructions cannot be entered and processed directly into computers using human
language.

Any type of data entered be it numbers, letters, special symbols, sound or pictures must first be
converted into machine-readable form i.e. binary form.

Digitization is the process of converting information, such as text, numbers, photo, or music, into
digital data that can be manipulated by electronic devices like computers.

Computers handle data by electrical components e.g. transistors, semiconductors, integrated

circuits or wires.

The operation of these components can be seen to be essentially bi stable, or binary in nature;
that is, either on (1) or off (0).

Inside the computer, data is represented by storage cells, which are either electronically charged
or discharged.

Example;
 In RAM, the cells can be charged and discharged at will, and this can be used to store
different data items.

The charged state of the cell can be represented by 1 (or ON), while the uncharged state
by 0 (or OFF).

 A transistor may be conducting or non-conducting

 A magnetic material may be magnetized in one direction or the other.

 A wire may or may not be carrying current.

Data representation in digital circuits

 Electronic components, such as

microprocessor, are made up of
millions of electronic circuits.

 The availability of high voltage

(on) in these circuits is interpreted
as ‘1’ while a low voltage (off) is
interpreted as ‘0’.

 This concept can be compared to switching on and off an electric circuit.

 When the switch is closed the high voltage in the circuit causes the bulb to light (‘1’ state).
On the other hand, when the switch is open, the bulb goes off (‘0’ state).

 This forms a basis for describing data representation in digital computers using the binary
number system.

Data representation on magnetic media

 The presence of a magnetic field in one

direction on magnetic media is interpreted as
1; while the field in the opposite direction is
interpreted as “0”.

 Magnetic technology is mostly used on

storage devices that are coated with special
magnetic materials such as iron oxide.

 Data is written on the media by arranging the magnetic dipoles of some iron oxide particles
to face in the same direction and some others in the opposite direction
Data representation on optical media

 In optical
devices, the
presence of light
is interpreted as
‘1’ while its
absence is
interpreted as ‘0’.

 Optical devices
use this
technology to read or store data.

 Take example of a CD-ROM, if the shiny surface is placed under a powerful microscope,
the surface is observed to have very tiny holes called pits.

 The areas that do not have pits are called land.

The laser beam reflected from the land is interpreted, as 1.

 The laser entering the pot is not reflected.

This is interpreted as 0.

 The reflected pattern of light from the rotating disk falls on a receiving photoelectric
detector that transforms the patterns into digital form.

 Optical devices use this technology to read or store data.

Data representation in computer

It has proved difficult to develop devices that can understand natural language directly due to the
complexity of natural languages.

However, it is easier to construct electric circuits based on the binary or ON and OFF logic.

All forms of data can be represented in binary system format.

Bits, bytes, nibble and word

The terms bits, bytes, nibble and word are used widely in reference to computer memory and data
size.
 Bits: can be defined as either a binary, which can be 0, or 1.
It is the basic unit of data or information in digital computers.

 Byte: a group of bits (8 bits) used to represent a character.

A byte is considered as the basic unit of measuring memory size in computer.

 A nibble: is half a byte, which is usually a grouping of 4 bit.

 Word: is a unit of data of a defined bit length that can be addressed and moved between
storage and the computer processor.

 The term word length is used as the measure of the number of bits in each word.
For example, a word can have a length of 16 bits, 32 bits, 64 bits etc.

DATA TYPES

Data is a term used to describe a set of facts.

A single fact is known as Datum.

Data type is an attribute associated with a piece of data that tells a computer system how to interpret
its value.

A data type constrains the values that an expression, such as a variable or a function, might take.

Data can be in three types or forms

1. Numerical/Numbers

Numbers can be expressed as either;

 Integers – whole numbers e.g. 124, -26, 0, or 1

 Real numbers – numbers with decimal points e.g. 1.23, -2.6.

 Note: A whole number is real if it is written with a decimal point e.g. 25 is an

integer, but 25.0 is real

2. Alphabetic data

This is data made from combination of symbols and alphabetic characters, such as names,
titles, marital status e.g. John
 Character (char) - It is used to store a single letter, digit, punctuation mark, symbol,
or blank space.

3. Alphanumeric Data (strings)

This is data made from combination of alphabetic characters, numerals and/or special
characters e.g. names – Simon Band, Address – P.O.BOX 37000, Lusaka, Date – 15-
September 2021, Account

 String (str or text) - It is a sequence of characters, numbers and symbols.

 It is the most commonly used data type to store text.

Additionally, a string can also include digits and symbols, however, it is always
treated as text.

A phone number is usually stored as a string (+1-999-666-3333) but can also be

stored as an integer (9996663333) .

BINARY CODES

Binary code, code used in digital computers, based on a binary number system in which there are
only two possible states, off and on, usually symbolized by 0 and 1.

The group of symbols is called as a code.

In the coding, when numbers, letters or words are represented by a specific group of symbols, it is
said that the number, letter or word is being encoded.

The digital data is represented, stored and transmitted as group of binary bits.

The binary code is represented by the number as well as alphanumeric letter.

The coding and decoding of data in a computer is done by the Input/Output devices.

The number of bits per character depends on the coding scheme used.
Advantages of Binary Code

The following is the list of advantages that binary code offers.

 Binary codes are suitable for the computer applications.

 Binary codes are suitable for the digital communications.

 Binary codes make the analysis and designing of digital circuits easy if we use the binary
codes.

 Since only 0 and 1 are being used, implementation becomes easy.

Classification of binary codes

The coding schemes can be put into the following four categories.

1. Weighted Codes

Weighted binary codes are those binary codes which obey the positional weight principle.

Each position of the number represents a specific weight.

In these codes each decimal digit is represented by a group of four bits.

Weighted codes are used in:

 Data manipulation during arithmetic operation.

 For input/output operations in digital circuits
 To represent the decimal digits in calculators, volt meters etc.

2. Non-Weighted Codes

In this type of binary codes, the positional weights are not assigned.

The examples of non-weighted codes are Excess-3 code and Gray code.

Non weighted codes are used in:

 To perform certain arithmetic operations.
 Shift position encodes.
 Used for error detecting purpose

Excess-3 code

The excess-3 codes are obtained as follows

Example

Gray Code

It is the non-weighted code and it is not arithmetic codes.

That means there are no specific weights assigned to the bit position.

It has a very special feature that, only one bit will change each time the decimal number is
incremented as shown in fig.

As only one bit changes at a time, the gray code is called as a unit distance code.

Gray code cannot be used for arithmetic operation.

Application of Gray code

 Gray code is popularly used in the shaft position encoders.

 A shaft position encoder produces a code word which represents the angular
position of the shaft.

3. Binary Coded Decimal (BCD) code

BCD is a 4-bit code used to represent numeric data only.

For example, a number like 3 can be represented using binary coded decimal as 00112.

BCD is mostly used in simple electronics devices like calculators

In the BCD, with four bits we can represent sixteen numbers (0000 to 1111).

But in BCD code only first ten of these are used (0000 to 1001).

The remaining six code combinations i.e. 1010 to 1111 are invalid in BCD.

Advantages of BCD Codes

 It is very similar to decimal system.

 We only need to remember binary equivalent of decimal numbers 0 to 9 only.

Disadvantages of BCD Codes

 The addition and subtraction of BCD have different rules.

 The BCD arithmetic is little more complicated.

 BCD needs more number of bits than binary to represent the decimal number.

So BCD is less efficient than binary.

4. Alphanumeric codes

The alphanumeric codes are the codes that represent numbers and alphabetic characters.
An alphanumeric code should at least represent 10 digits and 26 letters of alphabet i.e. total
36 items.

The following three alphanumeric codes are very commonly used for the data
representation.

a) Extended Binary Coded Decimal Interchange Code (EBCDIC)

 It is an 8-bit character coding scheme used in IBM computers.

 A total of 256 (28) characters can be coded using this scheme.

 For example, the symbolic representation of letter A using Extended Binary Coded
Decimal Interchange code is 110000012.

b) American Standard Code for Information Interchange (ASCII).

 ASCII is a 7-bit code, which means that only 128 characters i.e. 27 can be
represented.

 There is an 8th bit to this coding scheme which can provide for 256 characters

 This 8-bit coding scheme is referred to as an 8-bit American standard code for
information interchange.

 For example, the symbolic representation of letter A using this scheme is 10000012

NUMBER SYSTEM

The design and organization of a computer depends on the number system

A number system is a set of symbols used to represent values derived from a common base or
radix.

The four number systems are;

1. Binary number system

 Binary is the representation of data by only two possible conditions, either 0 and 1.

 It has a base of 2, and is therefore called Base two system

 In the binary number system, the digits 0 and 1 are referred to as Bits (binary digits)
 Unlike in decimal numbers where the place value goes up in factors of ten, in binary
system, the place values increase by the factor of 2.

 Binary numbers are written as X2.

Consider a binary number such as 10112.

 The right most digit has a place value of 1×20 while the left most has a place value
of 1×23.

Exponential Value 25 24 23 22 21 20

Integer value 32 16 8 4 2 0

2. Decimal number system

 The term decimal is derived from a Latin prefix deci, which means ten.

 The decimal number system consists of 10 digits, 0 to 9

 In decimal system, each digit has

 A digit value (0 to 9)

 A position value, which is determined by how many places to the left or the
right of the decimal point the digit is written

 Note: The digital value and position value for each number system depends on the
base of the number system

 Powers of the base increase as we move to the left and decrease as we move to the
right

 The magnitude of a number can be considered using these parameters.

 The absolute value is the magnitude of a digit in a number.

For example, the digit 5 in 7458 has an absolute value of 5 according to its
value in the number line.

 The place value of a digit in a number refers to the position of the digit in
that number i.e. whether; tens, hundreds, thousands etc.
 The total value of a number is the sum of the place value of each digit
making the number.

 The base value of a number also known as the radix, depends on the type
of the number systems that is being used.

The value of any number depends on the radix.

For example, the number 10010 is not equivalent to 1002.

7th 6th 5th 4th 3rd 2nd 1st Position

106 105 104 103 102 101 100 Power base

1000000 100000 10000 1000 100 10 1 Value

3. Octal number system

 In Octal number system, there are only 8 possible digits (0 to 7)

 Each digit (number) in base 8 has its place value determined by 8.

 The position value of a digit increases to the left of the octal point in ascending
powers of 8

 For example, 21638 can be expressed as

Assign the power to base 8

83 82 81 80

2 1 6 3

4. Hexadecimal number system

 In Hexadecimal number system, the base is 16 and there must be 16 digits.

 The sixteen symbols used in the Hexadecimal system are; digits 0 to 9 and alpha A
to F

 The equivalence between hexa-numbers and decimal numbers is shown below

Decimal Hexadecimal

10 A
11 B
12 C
13 D
14 E
15 F

 Each digit in the Hex number system has its place value expressed in terms of E.g.
the value 12A0 can be expressed as

Assign the powers to base 16

163 163 161 160

1 2 A 0

Base Conversions

Human beings normally work with base 10 notation, i.e. all the data passed to go as input into
computer is usually in decimal notation.

Subsequently, the results of the computer operations are communicated to the users in a form they
can understand, i.e. base 10 (decimal) notations.

The base conversion is therefore used to help computer users understand how data and information
is communicated between the computer and the user.

There are many methods or techniques which can be used to convert numbers from one base to
another.

We'll demonstrate here the following

1. Decimal to Binary

 To convert from decimal (base 10) to a binary number (base 2), the decimal is
repeatedly divided by 2, until the number cannot be further divided by two.

 On each division, the remainder is noted/.

 Then, the remainder are copied from the bottom upwards to give the binary
equivalent of the decimal number.

Example

Convert a decimal no. such as 12110 to its binary equivalent

 Fractional numbers

 For a fractional number, the no. is divided into two parts; the whole part and
the fraction part

 The whole no. is then converted to binary individually.

 The fraction part is repetitively multiplied by 2, noting the complete units

of two

 This is done until the fraction becomes a 0 or starts recurring

 The complete units of the fraction part are then copied downwards

Example

Convert a decimal number such as 26.2510 to its binary equivalent

2. Binary to Decimal

 To convert a binary number to decimal system, the number in binary is assigned

weighting factors (place values) for each digit
 The partial products (i.e. The product of each digit and its corresponding weight)
are obtained, and then added to give a decimal number equivalent of the binary
number

Example

Convert the binary number 10110 to decimal

 Explanation

- Note that the binary number 10110 has 5 digits

- Starting with the rightmost digit, the most significant digits (MSD)
is the 5th position

- So, it is multiplied by the 24 and each digit on its right will be half
of its positional value

- The products obtained are added together to get the required decimal

 Fractional Part

 For a fractional number, the whole no. is converted to decimal as above

 The digits in the fraction part are divided by multiples of 2, starting from
decimal

Example

Convert a binary no. such as 11010.012 to its decimal equivalent

3. Decimal to Octal
 To convert a decimal number to its octal equivalent, divide the decimal number
given repeatedly by 8 until the quotient obtained is zero

Example

Convert 69110 to octal

 Fractional numbers

 To convert decimal fractions into their equivalent octal fractions, the whole
part of the decimal is repeatedly divided by 8

 The fractional part is repeatedly multiplied by 8, noting the complete unit

of 8, until the fractional part becomes zero or upto the required number of
digits.

 The complete units are then copied downwards

 Example

Convert a decimal number such as 98.12310 to its octal equivalent

4. Octal to Decimal

 The octal number is assigned the weights in terms of 8’s

 Example

Covert 12638 to decimal

 Fractional number

 For a fractional octal number, the whole number is converted to decimal as

above

 The digits in the fraction part are divided by multiples of 8

 Example

Convert 142.18 to decimal

5. Decimal to Hexadecimal

 The decimal no. is repeatedly divided by 16

 Example

Convert 12210 to hexadecimal equivalent

 Fractional numbers

 For a fractional decimal number, the fractional part is repeatedly multiplied

by 16, noting the complete units of 16’S.

 The complete units are then copied downwards

 Example

Convert 32.12510 to hexadecimal

6. Hexadecimal to Decimal

 Assign the hexadecimal number given to the weights in terms of 16’s

 Example

Convert 7A16 to decimal

 Fractional numbers

 For a fractional hexadecimal value, the whole part is converted to decimal

as above

 The digits in the fraction part are divided by multiples of 16

 Example

Convert 20.216 to decimal

7. Binary to Octal
 To convert from binary to octal, the binary digits are grouped into 3’s and each
group is used to represent an individual octal digit

 Example

Convert the binary number 100011100112 to Octal

8. Binary to Hexadecimal

 To convert from binary to hexadecimal, the binary digits are grouped into 4’s and
each group is used to represent an individual octal digit

 Example

Convert the binary number 0110110010001111 to its equivalent hexadecimal

number

9. Octal to Binary

 First convert the given number to base 10 (decimal)

 Then convert the resulting decimal number to the binary

 Example

Convert 3478 to binary

10. Hexadecimal to Binary

 First convert the given number to base 10 (decimal)

 Then convert the resulting decimal number to the binary

 Example

Convert 6DC16 to binary equivalent

Signed and Unsigned Numbers

Both positive and negative numbers can be represented in binary form in the computer memory
during processing.
The negative numbers are used to carry out subtraction in the computers arithmetic operations.

This is based on the fact that subtracting a number is the same as adding its negative to the other.

The following are the various methods used to represent negative numbers in the computer

a) One’s Complement (1C) method

In 1C method, the binary digits representing the negative numbers are negated.

The 1’s in number are changed to 0’s, and the 0’s are changed to 1’s.

In 1C, we add the overflow to the answer

Example

-1710 can be represented in binary as a negative value as,

Step 1: Convert -1710 to binary (base 2)

Therefore, -1710 becomes 011102 after complimenting each

b) Two’s Complement (2C) method

In 2C method, the negative number is represented into binary form, and then complemented
as in 1C method, but a ‘1’ is added to the Least Significant Digit (LSD) of the complement
value

In case we get an extra digit that is not required, we call it an overflow i.e.., if you want
four digits and then you get five, digit number five will be called an overflow.

In 2C, we ignore the overflow

Example

-1710 can be represented as

c) Signed Magnitude Method

In signed magnitude method, the number is divided into two parts; the sign part and the
data part.

Usually, a ‘1’ is used to represent a negative sign and a ‘0’ to represent a positive sign.

The magnitude part is expressed in binary but not complimented.

Example

-1710 can be represented in binary as 100012

FLOATING POINT REPRESENTATION

Floating point numbers consists of two parts.

The first part of the number is a signed fixed-point number, which is termed as mantissa, and the
second part specifies the decimal or binary point position and is termed as an exponent.

The mantissa can be an integer or a fraction.

A floating-point number (or real number) can represent a very large (1.23×1088) or a very small
(1.23×10-88) value.

It could also represent very large negative number (-1.23×1088) and very small negative number (-
1.23×10^88), as well as zero, as illustrated:

Example
A decimal +12.34 in a typical floating-point notation is 12.34 = 0.1234 * 102

12.34= 0.1234 * 10-2

This number in any of the above form (if represented in BCD) requires 17 bits for
mantissa (1 for sign and 4 each decimal digit as BCD) and 9 bits for exponent (1 for sign and 4
for each decimal digit as BCD).

Exponent indicates the correct decimal location.

In the first case where exponent is +2, indicates that actual position of the decimal point is 2 places
to the right of the assumed position, while exponent –2 indicates that the assumed position of the
point is 2 places towards the left of assumed position.

The assumption of the position of the point is normally the same in a computer resulting in a
consistent computational environment.

Floating-point numbers are often represented in normalized form.

A floating-point number whose mantissa does not contain zero as the most significant digit of the
number is considered to be in a normalized form.

For example, a BCD mantissa +370 which is 0 0011 0111 000 is in normalized form because these
leading zero’s are nor part of a 0 digit.

On the other hand a binary number 0 01100 is not in a normalized form.

The normalized form of this number will be 0 1100

Arithmetic operations involved with floating point numbers are more complex in nature,
takes longer time for execution and require complex hardware.

Yet the floating point representation is a must as it is useful in scientific calculations.

Real numbers are normally represented as floating point numbers.

BINARY ADDITION, SUBTRACTION, MULTIPLICATION, DIVISION

Binary arithmetic is an essential part of all the digital computers and many other digital systems.

There are three basic reasons for which a computer uses binary number system for arithmetic
operations instead of decimal number system.

These are as follows:

1. The first and foremost reason is that electronic and electrical components operate in a
binary mode by their nature.

Information is handled in a computer by electrical components.

These components are transistors, semiconductors and wires.

These electrical components can only indicate two states.

These states are either on (1) or off (0).

A transistor can be either be conducting represented by state 1 or non-conducting

represented by state 0.

Similarly magnetic materials are either magnetized (1) or non-magnetized (0).

All information is represented within a computer by the presence or absence of these

signals.

Since the binary number system which has only two digits, 0 and 1, is most suitable.

Thus it is used to express the two possible states.

2. The second reason is that computer circuits only have to handle two binary digits rather
than ten decimal digits.

The result is that the internal circuit design of the computers is simplified to a great extent.

This ultimately results in less expensive and more reliable circuits for computers.

3. Finally, the binary system is used because everything that can be done with a base of 10
can also be done in binary.
Binary Arithmetic:

Here we will learn how the four basic arithmetic operations such as binary addition, subtraction,
multiplication and division are performed inside a computer using binary number system.

Binary arithmetic is much simpler to learn because it uses only two digits 0 and 1.

All binary numbers are made up using 0 and 1 only and when arithmetic operations are performed
on these numbers then the results are also obtained in the same form.

a) Binary Addition:

Binary addition is performed in the same manner as decimal addition.

However, since binary number system has only two digits, the binary addition table is
very simple consisting of only four entries.

The complete table for binary addition is given below.

0+0 0

0+1 1

1+0 1

1 + 1 0 and a carry 1 to next higher column

In binary number addition carry-overs are performed in the same manner as in decimal
Addition.

Since 1 is the largest digit in the binary number system, any sum greater than 1 requires
that a digit to be carried over.

For instance, the sum of 10 plus 10 binary numbers requires the addition of two 1’s in the
second position.

Since 1 + 1 = 0 plus a carry of 1 therefore the sum of 10 + 10 is 100 in binary system.

By the repeated use of the above rules any two binary numbers can be added together by
adding two bits at a time.
Example

Question 1: Add the binary numbers 1011 and 1001?

Question 2: Add the numbers 100111 and 11011?

b) Binary Subtraction:

The principles of decimal subtraction can as well be applied to subtraction of numbers in

binary in other cases.

It consists of two steps, which are repeated for each column of the numbers.

 The first step is to determine if it is necessary to borrow.

o If the subtractend (the lower digit) is larger than the minuend (the upper
digit), it is necessary to borrow from the column to the left.

o It is also important to note here that the valued borrowed depends upon the
base of the number.

o Thus, in decimal number subtraction 10 is borrowed, in binary number

subtraction 2 is borrowed; in octal number subtraction 8 is borrowed and in
hexadecimal number system 16 is borrowed.

 The second step is simply to subtract the lower value from the upper value.

The complete table for binary subtraction is given below.

0–0 0

1–0 1

1–1 0
0-1 1 with a borrow from next column

Example

Question 3: Subtract the binary number 01110 from 10101?

In the first column, 0 is subtracted from 1 and no borrow is required in this case and the
result is 1.

In the second column we have to subtract 1 from 0.

 As we have seen in the above binary subtraction table borrowing of 1 is necessary

to perform this subtraction.

 So a 1 is borrowed from the third column which becomes 2 in the second column
because the base is 2.

 Now in the second column, we subtract 1 from 2 which gives result 1.

 The borrow performed in the second column reduces the 1 in the third column to
0.

Now in the third column, once again we have to subtract 1 from 0 for which borrowing is
required.

 The fourth column contains a 0 and thus has nothing to borrow.

 Therefore, we have to borrow from the fifth column.

 Borrowing 1 from the fifth column gives 2 in the fourth column.

 Now the fourth column has something to borrow when 1 of the 2 in the fourth
column is borrowed, it becomes 2 in the third column.

 Now in the third column we subtract 1 from 2 giving a result of 1.

Borrowing performed in the third column reduces the 1 in the fifth column to 0 and in the
fourth column to 1.

 Thus subtraction of the fourth column is now 1 from 1 and it gives result 0.

Now in the fifth column 0 is subtracted from 0 which gives result 0.

Thus the final result is 00111

Complementary Method of Binary Subtraction:

The direct method of subtraction using borrow concept seems to be easy when people
perform subtraction with paper and pencil.

However, when subtraction is implemented by means of digital components this method is

found to be less efficient than the complementary method of subtraction.

There are two complementary methods, one is by taking 1’s complement of subtrahend
and other is by taking 2’s complement of subtrahend.

Binary Subtraction of Unsigned Binary Number Using 1’s Complement:

Unsigned Binary numbers are the numbers which have no signs.

If there are two unsigned binary numbers, then there will be two different cases of
subtraction.

And each of them is explained below with examples.

We will take help of 1’s complement to subtract these two binary numbers.

Case One: When Minuend is greater than Subtractend

We must follow the following given steps to do the binary subtraction of unsigned numbers
using 1’s compliment.

1. Find the 1’s complement of number subtrahend.

2. Add minuend and 1’s complement of subtrahend.

3. Discard end carry from the sum obtained in second step.

The most significant bit of the result of addition is the end carry.

4. Finally add 1 to least significant bit and that is the result of subtraction.

Example

Question 5: Subtract the unsigned Binary numbers 11010 from 11100 using 1’s
complement method.

Step 1: First we are going to find the 1’s complement of 11010.

1’s Complement of a binary number is obtained by changing 0’s to 1’s and 1’s to 0’s.

Thus 1’s complement of 11010 is 00101.

Step 2: Now adding 11100 and 00101 gives result 100001.

Step 3: Now we will discard the end carry of 100001.

Thus 100001 becomes 00001.

Step 4: Finally adding 1 to 00001 gives result 00010.

Hence the required value of subtraction is 00010.

Case Two: When Minuend is less than Subtrahend

The following steps are used to get the result of subtraction when minuend is less than
subtrahend using 1’s complement.

1. Find out the 1’s complement of subtrahend.

2. Find the sum of minuend and 1’s complement of subtrahend.

3. In this case there is no end carry.

So the result is 1’s complement of the sum obtained in second Step with a negative
sign.

Example

Question 6: Subtract unsigned Binary number 11000 from unsigned binary number 10010.

Step 1: First we will find 1’s complement of subtrahend.

1’s complement of 11000 is 00111.

Step 2: Now adding 10010 and 00111 gives result 11001.

Step 3: Now the 1’s complement of 11001 is 00110.

We will write the number 00110 followed by a negative sign.

Hence the required value of subtraction is – 00110.

Binary Subtraction of Unsigned Binary Number Using 2’s Complement:

Rules for Binary subtraction of unsigned Binary number using 2’s complement is given
below.

Here, there will be two cases depending upon the values of minuend and subtrahend.

Case One: When Minuend is greater than Subtrahend

The following steps are used to find the result of subtraction using 2’s complement
method.

1. Find out the 2’s complement of subtrahend.

2. Add minuend and 2’s complement of subtrahend.

3. Discard end carry from the sum obtained in Step two.

After discarding end carry from sum the rest number will be the required value of
subtraction.

Example

Question 7: Subtract 01111 from 10100 using 2’s complement method.

Step 1: 2’s complement of 01111 is 10001

Step 2: By adding 10100 and 10001, we get 100101.

Step 3: 100101 becomes 00101 after removing end carry.

And hence the required value of subtraction is 00101.

Case Two: When minuend is less than subtrahend

The following steps are used to get the result of subtraction when minuend is less than
subtrahend by using 2’s complement method.

1. First we need to find the 2’s complement of subtrahend.

2. Now we have to add minuend and 2’s complement of subtrahend.

3. Since there would be no end carry, therefore the result is the 2’s complement of
the sum with a negative sign.

Example
Question 8: Subtract the binary number 10001 from 00101

Step 1: 2’s complement of 10001 is 01111.

Step 2: By adding 00101 and 01111.

It gives 10100. 01011

Step 3: So the required answer is 2’s complement of 10100 with a negative sign.

Hence the required answer is – 01100.

Binary Subtraction of Signed Binary Number Using 2’s Complement:

A signed number is written either with a positive or negative sign.

There will be two cases of subtraction depending upon the numbers.

Case One: When minuend is greater than subtrahend

The following steps are used to subtract a signed Binary number from another signed
Binary number.

1. Represent the given numbers into signed form.

2. Find the 2’s complement of subtrahend.

3. Find the sum of minuend and 2’s complement of subtrahend.

4. Discard end carry from the number obtained in step three.

5. After discarding end carry, the most significant bit of the rest number is used to
present plus sign and rest of the digits make up the number.

Thus the final answer is written with a sign.

Example

Question 9: Subtract signed binary number + 011010 from signed binary number +
101001.

Step 1: Signed representation of binary number +101001 is 0101001 and signed

representation of + 011010 is 0011010.

Zero at most significant bit represents + sign.

Step 2: Now finding 2’s complement of 0011010.

2’s complement of a Binary number is obtained by changing 1’s with 0’s and 0’s with 1
and then adding 1 to least significant bit.

Thus 2’s complement of 0011010 is 1100110.

Step 3: Now adding 0101001 and 1100110 gives 10001111.

Step 4: Now the end carry from the sum obtained in third step is removed.

Step 5: Therefore, the result is 0001111 or 001111.

The most significant bit 0 of 0001111 will be used to represent plus sign.

Case Two: When minuend is less than subtrahend

The following steps are used to get the result of subtraction of two signed binary numbers
when minuend is less than subtractend by using 2’s complement method.

1. Represent the given numbers in signed binary form.

2. Find out the 2’s complement of subtrahend.

3. Add minuend and binary number obtained step two.

4. In this case there would be no end carry, the required answer will be the 2’s
complement of the sum except signed bit.

Example

Question 10: Subtract +101001 from +011010.

Step 1: Signed representation of + 011010 is 0011010 and + 101001 is 0101001.

Step 2: 2’s complement of 0 101001 is 1010111.

Step 3: sum of 0011010 and 1010111 is 1110001.

Step 4: The required answer is 2’s complement of 110001 (Sign bit is not included).

Hence the required answer is 1001111 or – 001111.

Most significant bit 1 represents minus sign.

Binary Multiplication:
Multiplication in the binary system follows the same general rules as decimal multiplication.

However, learning the binary multiplication is a trivial task because the table for binary
multiplication is very short, with only four entries instead of the 100 necessary for decimal
multiplication.

The complete table for binary multiplication is given below.

0*0 0

0*1 0

1*0 0

1*1 1

Example

Question 11: Multiply the binary numbers 1010 and 1001?

We can see that in the above example that the multiplicand is simply copied when multiplier digit
is 1 and when the multiplier digit is 0 then the partial product is a string of zeros.

As in decimal multiplication, each partial product is shifted one place to the left from the previous
partial product.

Finally, all the partial products are added according to the binary addition rule to get the final result
of multiplication.

Additive method of Binary Multiplication:

Most of the computers perform multiplication operation by the way of addition only.
This can be easily seen by considering an example, say 5 ✕ 8.

The result of this product can be calculated by evaluating 8 + 8 + 8 + 8 + 8.

The result is simply obtained by adding the digit 8 five times.

Similarly, computers perform all multiplication operation in binary using the additive approach.

Binary Division:

Binary division is again very simple.

As in the decimal system or any other number system, division by 0 is meaningless.

Hence, the complete table for binary division is given below.

Binary Division Table:

0/1 0

1/1 1

The division process is performed in a manner similar to decimal division.

The rules for binary division are:

1. Start from the left of the dividend.

2. Perform a series of subtraction in which the divisor is subtracted from the dividend.

3. If subtraction is possible, put a 1 in the quotient and subtract the divisor from the
corresponding digits of dividend.

4. If subtraction is not possible (divisor is greater than dividend), record a 0 in the quotient.

5. Bring down the next digit to add to the remainder digits.

Proceed as before in a manner similar to long division.

Example

Question 12: Divide 100001 by 110?

Step 1: Divisor greater than 100, so put 0 in quotient.
Step 2: Add digit from dividend to group used above.
Step 3: Subtraction possible so put 1 in the quotient.
Step 4: Remainder from subtraction plus digit from dividend
Step 5: Divisor greater, so put 0 in quotient.
Step 6: Add digit from dividend to group.
Step 7: Subtraction possible, so put 1 in quotient.

LOGIC GATES, BOOLEAN ALGEBRA, MAP SIMPLIFICATION (UP TO 4 VARIABLE

MAPS): SOP, POS, DON’T CARE CONDITIONS

Introduction

We begin with an overview of logic gates, logic circuits implementations using gates, boolean
function simplification of using boolean laws and map simplification using k-maps.

Positive and Negative Logic

The binary variables can have either of the two states, i.e. the logic ‘0’ state or the logic ‘1’ state.

These logic states in digital systems such as computers, for instance, are represented by two
different voltage levels or two different current levels.

If the more positive of the two voltage or current levels represents a logic ‘1’ and the less positive
of the two levels represents a logic ‘0’, then the logic system is referred to as a positive logic
system.

If the more positive of the two voltage or current levels represents a logic ‘0’ and the less positive
of the two levels represents a logic ‘1’, then the logic system is referred to as a negative logic
system.

If the two voltage levels are 0 V and +5 V, then in the positive logic system the 0 V represents
logic ‘0’ and the +5 V represents logic ‘1’.
In the negative logic system, 0 V represents logic ‘1’ and 5 V represents logic ‘0’.

If the two voltage levels are 0 V and −5 V, then in the positive logic system the 0 V represents a
logic ‘1’ and the −5 V represents a logic ‘0’.

In the negative logic system, 0 V represents logic ‘0’ and −5 V represents logic ‘1’.

Logic Gates

Logic gates are the basic building blocks of digital systems that can be used to implement the most
elementary logic expressions, also known as boolean expressions.

A logic gate performs a boolean logic operation on one or more binary inputs and then outputs a
single binary output.

Basic logic gates are AND gate, OR gate, NOT gate etc.

Other logic gates that are derived from these basic gates are the NAND, the NOR, the
EXCLUSIVE-OR and the EXCLUSIVE-NOR gate.

 OR Gate

An OR gate is a logic circuit with two or more inputs and one output.

It is used to perform operations of logical addition.

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.

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.

The truth table below lists all possible combinations of input binary variables and the
corresponding outputs of a logic system.

 AND Gate

An AND gate is a logic circuit having two or more inputs and one output.
It is used to perform operations of logical multiplication.

The output of an AND gate is HIGH only when all of its inputs are in HIGH state.

The AND operation on two independent logic variables A and B is written as Y = A.B and
reads as Y equals A AND B.

The logic symbol and truth table of a two-input AND gate is shown in figure.

 NOT Gate

A logic gate used to perform logical inversion is known as a 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.

If X is the input to a NOT circuit, then its output Y is given by Y = X or and reads as Y
equals NOT.

The logic symbol and truth table of a NOT gate is shown in figure.

 NAND Gate

NAND stands for NOT AND.

An AND gate followed by a NOT circuit makes it a NAND gate.

The output of a NAND gate is logic ‘0’ when all its inputs are logic ‘1’.

For all other input combinations, the output is logic ‘1’.

NAND gate operation is logically expressed as Y = AB

The symbol and truth table of a NAND gate is as shown below.

 NOR Gate

NOR stands for NOT OR.

An OR gate followed by a NOT circuit makes it a NOR gate.

The output of a NOR gate is logic ‘1’ when all its inputs are logic ‘0’.

For all other input combinations, the output is logic ‘0’.

The output of a two-input NOR gate is logically expressed as Y=A+B

The symbol and truth table of a NOR gate is as shown.

 EXCLUSIVE-OR Gate

The EXCLUSIVE-OR gate, commonly written as EX-OR gate, is a two-input, one-output

gate.

The output of an EX-OR gate is logic ‘1’ when the inputs are unlike and logic ‘0’ when the
inputs are like.

The output of a two input EX-OR gate is logically expressed as

The symbol and truth table of an EX-OR gate is shown in figure.

 EXCLUSIVE-NOR Gate

EXCLUSIVE-NOR (commonly written as EX-NOR) means NOT of EX-OR.

The logic gate that we get by complementing the output of an EX-OR gate.

The truth table of an EXNOR gate is obtained from the truth table of an EX-OR gate by
complementing the output entries as shown in figure.

Logically,

The output of a two-input EX-NOR gate is logic ‘1’ when the inputs are like and logic ‘0’
when they are unlike.

Logical Circuits

A logic circuit is an electronic circuit used in computers to perform a logical operation on its two
or more input signals.

These circuits are termed as logic circuits, as their operation obeys a definite set of logic rules.

The logic circuits are categorized into two types (based on whether they contain memory or not):

1. Combinational Logic Circuits

In a combinational logic circuit, the output at any instant of time depends only on present
input at that particular instant of time.

These circuits do not have any memory devices.

The logic gates are a building block of combinational logic circuits.

Combinational circuits are used in microprocessor and microcontroller for designing the
hardware and software components of a computer.

Combinational digital logic circuits are classified into three major parts - arithmetic or
logical functions, data transmission and code converter.

Examples of combinational circuits are half adder and full adder, encoder, decoder,
multiplexer, de-multiplexer, code converter etc.

2. Sequential logic circuits.

In sequential circuit the output of the logic device is not only dependent on the present
inputs to the device, but also on past inputs.

In other words, output of a sequential logic circuit depends on present input as well as
present state of the circuit.

Unlike combinational circuits, the sequential circuits have memory devices in order to store
the past outputs.

In fact, sequential logic circuits are nothing but combinational circuit with memory as
shown in figure below.

Examples of sequential logic circuits are counters, flip flops

Types of sequential logic circuits

As standard logic gates are the building blocks of combinational circuits, bistable latches
and flip-flops are the basic building blocks of sequential logic circuits.

Sequential logic circuits can be constructed to produce either simple edge-triggered flip-
flops or more complex sequential circuits such as storage registers, shift registers, memory
devices or counters.

The sequential circuits can be event driven, clock driven and pulse driven.

There are two main types of sequential circuits: (a) Synchronous and (b) Asynchronous.

a) Asynchronous Sequential circuits

Asynchronous circuits do not synchronize with positive edge or negative edge of

the clock signal that means, the outputs of asynchronous sequential circuits do not
change or affect at the same time and change their state immediately when there is
a change in the input signal.

So, these circuits are faster and independent of the internal clock pulses.

But these circuits have uncertainty in the outputs and are difficult to design.
b) Synchronous Sequential circuits

Synchronous circuits synchronize with either positive edge or negative edge of the
clock signal that means, the outputs of synchronous sequential circuits change or
affect at the same time.

These circuits use clock signal and level input (or pulsed with restrictions on pulse
width and circuit propagation).

Since they wait for the next clock pulse to arrive to perform the next operation, so
these circuits are a bit slower compared to asynchronous.

Level output changes state at the start of an input pulse and remains in that until the
next input or clock pulse.

The synchronous sequential circuit can be locked or unlocked (or pulsed).

Boolean Algebra

The logical symbol 0 and 1 are used for representing the digital input or output in digital circuits.

These digital circuit are made up of several logic gates in order to perform logic operations.

To perform logical operation with minimum logic gates, a set of rules were invented, known as
the Laws of Boolean Algebra.

Boolean algebra Characteristics

i. Only two values (1 for high and 0 for low) are possible for the variable used in Boolean
algebra.

ii. The overbar (-) is used for representing the complement variable.
iii. The plus (+) operator is used to represent the ORing of the variables.

iv. The dot(.) operator is used to represent the ANDing of the variables

Properties of Boolean algebra

The properties of Boolean algebra are:

1) Annulment Law

When the variable is AND with 0, it will give the result 0, and when the variable is OR
with 1, it will give the result 1, i.e.

B.0 = 0

B+1 = 1

2) Identity Law

When the variable is AND with 1 and OR with 0, the variable remains the same, i.e.,

B.1 = B

B+0 = B

3) Idempotent Law

When the variable is AND and OR with itself, the variable remains same or unchanged,
i.e.

B.B = B

B+B = B

4) Complement Law

When the variable is AND and OR with its complement, it will give the result 0 and 1
respectively.

B.B' = 0

B+B' = 1

5) Double Negation Law

This law states that if you negate a negation (i.e. if you have a NOT within a NOT) they
effectively cancel each other out.

((A)')' = A

6) Commutative Law

This law states that the order of terms for an expression (or part of an expression within
brackets) may be reordered and the end result will not be affected.

This law states that the order of variables doesn't matter.

A.B = B.A

A+B = B+A

7) Associative Law

This law looks at brackets (or groupings) within an expression and how they may be
reorganized or even removed.

If all the operators within an expression (or part of an expression) are the same then this
may be done. So:

(A.B).C = A.(B.C)

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

8) Distributive Law

This law is similar to distributivity in normal mathematics and has to do with expanding
or simplifying brackets.

This may be done when one of AND or OR is inside the brackets and the other is outside

A+(B.C) = (A+B).(A+C)

A.(B+C) = (A.B)+(A.C)

9) Absorption Law

This law enables a reduction in a complicated expression to a simpler one by absorbing the
similar variables.

B+(B.A) = B
B.(B+A) = B

10) De Morgan Law

The operation of an OR and AND logic circuit will remain same if we invert all the
inputs, change operators from AND to OR and OR to AND, and invert the output.

(A.B)' = A'+B'

(A+B)' = A'.B'

Summary of the Ten Basic Rules of Boolean Algebra

1. Anything ANDed with a 0 is equal to 0. A * 0 = 0

2. Anything ANDed with a 1 is equal to itself. A * 1 = A

3. Anything ORed with a 0 is equal to itself. A + 0 = A

4. Anything ORed with a 1 is equal to 1. A + 1 = 1

5. Anything ANDed with itself is equal to itself. A * A = A

6. Anything ORed with itself is equal to itself. A + A = A

7. Anything ANDed with its own complement equals 0.

8. Anything ORed with its own complement equals 1.

9. Anything complemented twice is equal to the original.

Implementing Circuits from Boolean Expression

If the operation of a circuit is defined by a Boolean expression, a logic-circuit diagram can he

implemented directly from that expression.

The steps for Implementation of Boolean Functions are below:

 Operator precedence from highest to lowest is: Bracket, NOT (’), AND (.) and OR (+)

 Using the truth table, we can write Boolean expressions for the output.

 Then we can define reduced expressions using logic gates.

 For any output signal is to be written from the truth table only those input combinations
are written for which the output is high.

Example:

Write Boolean expression for following truth table:

X Y Z F1 F2 F2
0 0 0 0 0 0
0 0 1 0 1 1
0 1 0 0 0 0
0 1 1 0 0 1
1 0 0 0 1 1
1 0 1 0 1 1
1 1 0 1 1 0
1 1 1 0 1 0

F1 output have high value only when input xyz has value 1 1 0.

Hence Boolean expression for F1 is,

F1 = x . y. z’

Similarly we can write Boolean expression for rest of the output as follow:

F2 = x’ . y’ . z + x . y’ . z’ + x . y’ . z + x . y . z’ + x . y . z

F3 = x’ . y’ . z + x’ . y . z + x . y’ . z’ + x . y’ . z

Now we can reduce the above expression using boolean algebra.

F2 = x’ . y’ . z + x . y’ . z’ + x . y’ . z + x . y . z’ + x . y . z

= x’ . y’ . z + x . y’ . (z’ + z ) + x . y .( z’ + z)

= x’ . y’ . z + x . y’ + x . y

= x’ . y’ . z + x . (y’ + y)

= x’ . y’ . z + x

= (x’ + x) . ( y’ . z + x) ……………. Absorption law

= 1. ( y’ . z + x) = ( y’ . z + x)

Constructing a circuit from Boolean Expression

Suppose that we wanted to construct a circuit whose output is y = AC+BC' + A'BC.

This Boolean expression contains three terms (AC, BC', A'BC), which are ORed together.

This tells us that a three-input OR gate is required with inputs that are equal to AC, BC', and
A'BC, respectively.

Each OR-gate input is an AND product term, which means that an AND gate with appropriate
inputs can be used to generate each of these terms.

Note the use of inverters to produce the A' and C' terms required in the expression.

Standard Form

The following are two standard canonical forms for writing Boolean expression:

1. Sum-Of-Product (SOP) - It is a product term or logical sum (OR) operation of several

product terms which produce high output.

Write the input variables if the value is 1, and write the complement of the variable if its
value is 0.

2. Product-Of-Sum (POS) - It is a sum term or logical product (AND) operation of several

sum terms which produce low output.

Writing the input variables if the value is 0, and write the complement of the variable if its
value is 1.

The Karnaugh Map

Karnaugh maps also known as K-map minimize Boolean expressions of 2,3, 4 variables very easily
without using any Boolean algebra theorems.

 K-map can take two forms Sum of Product (SOP) and Product of Sum (POS) according to
the need of the problem.
 It is a graphical method, which consists of 2n cells for ‘n’ variables.

 It gives more information than TRUTH TABLE.

 Fill a grid of K-map with 0’s and 1’s then solve it by making groups.

Advantages of K-Maps

i. The K-map simplification technique is simpler and less error-prone compared to the
method of solving the logical expressions using boolean laws.

ii. It prevents the need to remember each and every boolean algebraic theorem.

iii. It involves fewer steps than the algebraic minimization technique to arrive at a
simplified expression.

iv. K-map simplification technique always results in minimum expression if carried out
properly.

Disadvantages of K-Maps

i. As the number of variables in the logical expression increases, the K-map

simplification process becomes complicated.

ii. The minimum logical expression arrived at by using the K-map simplification
procedure may or may not be unique depending on the choices made while forming the
groups.

Steps to solve expression using K-map

1. Select K-map according to the number of variables.

2. Identify minterms or maxterms. .

3. For SOP put 1’s in blocks of K-map respective to the minterms (0’s elsewhere).

4. For POS put 0’s in blocks of K-map respective to the maxterms(1’s elsewhere).

5. Make rectangular groups containing total terms in power of two like 2,4,8..(except 1) and
try to cover as many elements as you can in one group.

6. From the groups made in step 5 find the product terms and sum them up for
7. SOP form.

Minterms and Maxterm

A boolean function can be represented in the form of sum of minterms or the product of maxterms,
which enable the designer to make a truth table more easily.

Minterm

A minterm is a product term in boolean function in which every element is present either in normal
or in complemented form.

For example if F(a,b,c) is a boolean function then the possible minterms would be abc, abc’, ab’c,
ab’c’, a’bc, ab,c, a’b’c, a’b’c’.

That is for n variable boolean function there would be 2n possible minterms.

Minterms are used for sum of product(SOP) canonical forms, which is also called disjunctive
normal form(DNF).

The value that correspond to 1 or true is selected as minterm.

It is denoted by small m.

We generally use the ∑m (sigma) notation to represent minterms

If a function has n variables, then it has 2n minterms.

a) Two variable minterms

Consider two Boolean variables, X and Y.

There are four different possible combinations that can be generated from X AND Y, and
they are 𝑋 𝑌, 𝑋Y,X 𝑌, and XY.

These four combinations are called the minterms for X AND Y.

Table below shows the minterms and their designations for F(X,Y) = (X AND Y).
In Table above,

𝑋 𝑌 = 1, if X = 0 and Y= 0 then 𝑋 𝑌 is represented by m0;

XY = 1 if X= 0 and Y = 1 then 𝑋Y is represented by m1;

X 𝑌 = 1 if X = 1 and Y = 0 and X𝑌 is represented by m2;

XY = 1 if X = 1 and Y = 1 then XY is represented by m3.

Example of two variable minterms.

It is simple to generate a truth table from minterms and vice versa.

Consider the function F (X,Y) = X𝑌 + 𝑋Y and its truth table below;

The function can be represented as F(X,Y) = m1 +m2 or each minterm that represents a 1
in the truth table.

This may also be rewritten as F(X, Y) = ∑(1,2).

b) Three-Variable Minterms

The three variables X, Y, and Z generate eight minterms as shown in table below.

Example of 3 variable minterm

Find the truth table for the following function

F(X,Y,Z) = 𝑋𝑌Z + 𝑋YZ + XYZ

The function F can be represented by a sum of the minterms (or where F = 1):

F(XYZ) = m1 + m3 + m7 or

F(X,Y,Z) = Σ(1, 3, 7)

The truth table for function F(X,Y,Z) = 𝑋𝑌Z + 𝑋YZ + XYZ

The truth table for this function contains a one in row 1, row 3, and row 7.

The rest of the rows are zeros as shown in table.

The function for a truth table can also be determined from the sum of the minterms

Maxterms

A maxterm is a sum term in boolean function in which every element present is either in normal
or in complemented form.

For example if F(a,b,c) is a boolean function then the possible maxterms would be (a+b+c),
(a+b+c’), (a+b’+c), ( a+b’+c’), (a’+b+c), ( a+b’+c), ( a’+b’+c), (a’+b’+c’).

That is for n variable boolean function there would be 2n possible maxterms.

There are used for product of sum(POS) canonical forms, which is also called conjunctive normal
form(CNF).

The value correspond to 0 or false is selected as maxterm.

It is denoted by small M.

We generally use ∏ (pi) notation to represent the max terms.

Maxterm is complement of a minterm.

If the minterm m0 is 𝑋𝑌𝑍, then the maxterm M0 is

Table below shows the maxterms for three variables.

In a truth table, an output of one represents minterms, and an output of zero represent maxterms.

Example of Maxterm

Consider the truth table below, where the function F can be expressed as the product of maxterms.
(Please note: the product of maxterms, as opposed to the sum of minterms.)

F(X,Y,Z) = M0M2M4M5M6, or it can represented by

F(X,Y,Z) = π (0,2,4,5,6)

Substituting each designated maxterm with the corresponding maxterm results in:

F(X,Y,Z = (X + Y + Z)(X + 𝑌 + Z)(𝑋 + Y + Z)(𝑋 + Y +𝑍)(𝑋 + 𝑌 + Z)

Grouping of K-map variables

The K-map simplification technique is simpler and less error-prone compared to the method of
solving the logical expressions using Boolean laws

There are some rules to follow while we are grouping the variables in K-maps.
a) The square that contains ‘1’ should be taken in simplifying, at least once.

b) The square that contains ‘1’ can be considered as many times as the grouping is possible
with it.

c) Group shouldn’t include any zeros (0).

d) A group should be as large as possible.

e) Groups can be horizontal or vertical.

Grouping of variables in diagonal manner is not allowed.

 If the square containing ‘1’ has no possibility to be placed in a group, then it should be
added to the final expression.

 Groups can overlap.

 The number of squares in a group must be equal to powers of 2, such as 1, 2, 4, 8 etc.

 Groups can wrap around.

As the K-map is considered as spherical or folded, the squares at the corners (which are at
the end of the column or row) should be considered as they adjacent squares.

 The grouping of K-map variables can be done in many ways, so the obtained simplified
equation need not to be unique always.

 The Boolean equation must be in canonical form (the simplest form of something
specifically), in order to draw a K-map.
Karnaugh map method for simplifying expressions

We have examined the derivation of a Boolean algebra expression for a given function by using a
table of combinations to list desired function values.

To derive a sum of products expression for the function, a set of product terms was listed, and
those terms for which the function was to have a value 1 were selected and logically added to form
the desired expressions.

The table of combinations provides a nice, natural way to list all values of Boolean function.

There are several other ways to represent or list function values, and the use of certain minds of
maps, which we will examine, also permits minimization of the expression formed in a nice
graphic way.

For example, if the function has only two variables, the number of squares will be 2n, i.e.,22 = 4.

Similarly, for a three input variable function the number of squares in the karnaugh map will be
23=8 and for four variable functions, 24=16 square will be present.

1. 2 variable K-maps

There are 4 cells (22) in the 2-variable k-map.

The most significant bits of the minterm are the line and the least significant the column.

The possible min terms with 2 variables (A and B) are A.B, A.B’, A’.B and A’.B’.

The conjunctions of the variables (A’, B’) and (A, B’) are represented in the cells of the
top row and (A’, B) and (A, B) in cells of the bottom row.
The following table shows the positions of all the possible outputs of 2-variable Boolean
function on a K-map.

A general representation of a 2 variable K-map plot is shown below.

When we are simplifying a Boolean equation using Karnaugh map, we represent each cell
of K-map containing the conjunction term with 1.

After that, we group the adjacent cells with possible sizes as 1,2 or 4.

In case of larger k-maps, we can group the variables in larger sizes like 8 or 16.

The groups of variables should be in rectangular shape that means the groups must be
formed by combining adjacent cells either vertically or horizontally.

Diagonal shaped or L-shaped groups are not allowed.

The following example demonstrates a K-map simplification of a 2-variable Boolean

equation.

Example

Simplify the given 2-variable Boolean equation by using K-map.

F = X Y’ + X’ Y + XY

First, let’s construct the truth table for the given equation,
We put 1 at the output terms given in equation.

In this K-map, we can create 2 groups by following the rules for grouping, one is by
combining (X’, Y) and (X’, Y’) terms and the other is by combining (X, Y’) and (X’, Y’)
terms.

Here the lower right cell is used in both groups.

After grouping the variables, the next step is determining the minimized expression.

By reducing each group, we obtain a conjunction of the minimized expression such as by

taking out the common terms from two groups, i.e. X’ and Y’.

So the reduced equation will be X’ +Y’.

2. 3 variable K-maps

For a 3-variable boolean function, there is a possibility of 8 output minterms.

The general representation of all the minterms using 3-variables is shown below.

A typical plot of a 3-variable K-map is shown below.

It can be observed that the positions of columns 10 and 11 are interchanged so that there is
only change in one variable across adjacent cells.

This modification will allow in minimizing the logic.

Up to 8 cells can be grouped in case of a 3-variable K-map with other possibilities being
1, 2 and 4.

Example

Simplify the given 3-variable Boolean equation by using k-map.

F = X’ Y Z + X’ Y’ Z + X Y Z’ + X’ Y’ Z’ + X Y’ Z + X Y’ Z’

First, let’s construct the truth table for the given equation,

We put 1 at the output terms given in equation.

There are 8 cells (23) in the 3-variable k-map.

The largest group size will be 8 but we can also form the groups of size 4 and size 2.

In the 3 variable Karnaugh map, we consider the left most column of the k-map as the
adjacent column of rightmost column.

So the size 4 group is formed as shown below.

And in both the terms, we have ‘Y’ in common.

So the group of size 4 is reduced as the conjunction Y.

To consume every cell which has 1 in it, we group the rest of cells to form size 2 group, as
shown below

The 2 size group has no common variables, so they are written with their variables and its
conjugates.

So the reduced equation will be X Z’ + Y’ + X’ Z.

In this equation, no further minimization is possible.

3. 4 variable K-maps

There are 16 possible min terms in case of a 4-variable Boolean function.

The general representation of minterms using 4 variables is shown below.

A typical 4-variable K-map plot is shown below.

It can be observed that both the columns and rows of 10 and 11 are interchanged.
The possible number of cells that can be grouped together are 1, 2, 4, 8 and 16.

Example

Simplify the given 4-variable Boolean equation by using k-map.

F (W, X, Y, Z) = (1, 5, 12, 13)

By preparing k-map, we can minimize the given Boolean equation as

F = W Y’ Z + W X Y’

Karnaugh Map Simplification of Sum of Product (SOP) Expressions

After a SOP expression has been mapped, there are three steps in the process of obtaining a
minimum SOP expression:

The following rules are applied to find the minimum product terms and the minimum SOP
expression:

1. Group the cells that have 1s.

Each group of cells containing 1s creates one product term composed of all
variables that occur in only one form (either uncomplemented or complemented)
within the group.

Variables that occur both uncomplemented and complemented within the group are
eliminated.

These are called contradictory variables.

2. Determine the minimum product terms for each group.

For a 3-variable map:

a) A 1-cell group yields a 3-variable product term

b) A 2-cell group yields a 2-variable product term

c) A 4-cell group yields a 1-variable term

d) An 8-cell group yields a value of 1 for the expression

For a 4-variable map

a) A 1-cell group yields a 4-variable product term

b) A 2-cell group yields a 3-variable product term

c) A 4-cell group yields a 2-variable product term

d) An 8-cell group yields a 1-variable term

e) A 16-cell group yields a value of 1 for the expression

3. Summing the resulting product terms.

When all the minimum product terms are derived from the Karnaugh map, they are
summed to form the minimum SOP expression

Example One

Simplify the Boolean expression: F(x,y,z) = Σ (0,1,6,7)

Solution
Example Two

Simplify the Boolean expression: F(x,y,z) = Σ (0,2,5,7)

Example Three

Group the 1's in each of the following Karnaugh maps:

Karnaugh Map Product of Sum (POS) Simplification

The minimized Boolean functions derived from the map in all previous examples were expressed
in the sum of products form.

With a minor modification, the product of sums form can be obtained.

The procedure for obtaining a minimized function in product of sums follows from the basic
properties of Boolean functions.

The 1's placed in the squares of the map represent the minterms of the function.

The minterms not included in the function denote the complement of the function.

From this we see that the complement of a function is represented in the map by the squares not
marked by 1's.
If we mark the empty squares by 0's and combine them into valid adjacent squares, we obtain a
simplified expression of the complement of the function (F).

The complement of F' gives us back the function F.

Because of Demorgan's theorem, the function so obtained is automatically in the product of sums
form.

Example

Simplify the following Boolean function in (a) sum of products and (b) product of sums.

F(w,x,y,z) = Σ (0,1,2,3,10,11,14,15)

Don't Care Conditions

Sometimes a situation arises in which some input variable combinations are not allowed.

For example, in the BCD code, there are six invalid combinations: 1010, 1011, 1100, 1101, 1110,
and 1111.

Since these unallowed states will never occur in an application involving the BCD code, they can
be treated as "don't care" terms with respect to their effect on the output.

That is, for these "don't care" terms either a 1 or a 0 may be assigned to the output; it really does
not matter since they will never occur.

The "don't care" terms can be used to advantage on the Karnaugh map.

The following figure shows that for each "don't care" term, an X is placed in the cell.
When grouping the 1's, Xs can be treated as 1's to make a larger grouping or as 0s if they cannot
be used to advantage.

The larger a group, the simpler the resulting term will be.

Be careful not to make a group entirely of x's.

The following truth table describes a logic function that has a 1 output only when the BCD code
for 7, 8, or 9 is present on the inputs.

Taking advantage of the "don't cares" and using them as 1's, the resulting expression for the
function is w + xyz, as indicated.

If the "don't cares" are not used as 1s, the resulting expression is w'xyz + wx'y'.

So you can see the advantage of using "don't care" terms to get the simplest expression.

Example

Simplify the following Boolean function F, where d represents the set of do not care conditions.

F(w,x,y,z) = Σ (0,1,2,8,10,11)

d(w,x,y,z) = Σ (4,6,12,13)
Canonical Form

It is a unique way of representing boolean expressions.

Any boolean expression can be represented in the form of sum of minterm and sum of maxterm.

The Σ symbol is used for showing the sum of minterm and ℿ symbol is used for showing product
of maxterm.

Example:

Consider the given truth table where x,y are input variables and F1,F2, F3 are output.

x y F1 F2 F3
0 0 0 0 1
0 1 0 1 0
1 0 1 1 0
1 1 0 0 1

Sum of minterms can be obtained by summing the minterms of the function where result is a 1 as
follows:

F1 =x.y’ = Σ m(2)

F2 =x’.y+x.y’ = Σ m(1,2)

F3 =x’.y’+x.y = Σ m(0,3)

Product of maxterms can be obtained by the maxterms of the function where result is a 0 as follows:

F1 =(x’+y’).(x’+y).(x+y) = ℿ M(0,1,3)

F2 =(x’+y’).(x+y) = ℿ M(0,3)
F3 =(x’+y).(x+y’) = ℿ M(1,2)

Steps for conversion of canonical forms:

Sum of minterms to product of maxterms

 Rewrite minterm to maxterm

 Replace minterm indices with indices not already used.

Product of maxterms to sum of minterms

 Rewrite maxterm using minterm

 Replace maxterm indices with indices not already used.

Example:

From the above truth table,

F1 = Σ m(2) = ℿ M(0,1,3)

F3 = ℿ M(1,2) = Σ m(0,3)

Floating Point Number Representation

A floating-point number (or real number) can represent a very large (1.23×10^88) or a very

small (1.23×10^-88) value. It could also represent very large negative number (-1.23×10^88) and

very small negative number (-1.23×10^88), as well as zero, as illustrated: