COMPUTER MEMORY

A memory is just like a human brain. It is used to store data and instructions. Computer
memory is the storage space in the computer, where data is to be processed and
instructions required for processing are stored. The memory is divided into large number
of small parts called cells. Each location or cell has a unique address, which varies from
zero to memory size minus one. For example, if the computer has 64k words, then this
memory unit has 64 * 1024 = 65536 memory locations. The address of these locations
varies from 0 to 65535.

Memory is primarily of three types −

1. Cache Memory
2. Primary Memory/Main Memory
3. Secondary Memory

Cache Memory

Cache memory is a very high speed semiconductor memory which can speed up the CPU.
It acts as a buffer between the CPU and the main memory. It is used to hold those parts of
data and program which are most frequently used by the CPU. The parts of data and
programs are transferred from the disk to cache memory by the operating system, from
where the CPU can access them.

Advantages

The advantages of cache memory are as follows −

i. Cache memory is faster than main memory.

1
 ii. It consumes less access time as compared to main memory.
iii. It stores the program that can be executed within a short period of time.
iv. It stores data for temporary use.

Disadvantages

The disadvantages of cache memory are as follows −

i. Cache memory has limited capacity.

ii. It is very expensive.

Primary Memory (Main Memory)

Primary memory holds only those data and instructions on which the computer is
currently working. It has a limited capacity and data is lost when power is switched off. It
is generally made up of semiconductor device. These memories are not as fast as
registers. The data and instruction required to be processed resides in the main memory. It
is divided into two subcategories RAM and ROM.

Characteristics of Main Memory

i. These are semiconductor memories.

ii. It is known as the main memory.
iii. Usually volatile memory.
iv. Data is lost in case power is switched off.
v. It is the working memory of the computer.

2
 vi. Faster than secondary memories.
vii. A computer cannot run without the primary memory.

Secondary Memory

This type of memory is also known as external memory or non-volatile. It is slower than
the main memory. These are used for storing data/information permanently. CPU directly
does not access these memories, instead they are accessed via input-output routines. The
contents of secondary memories are first transferred to the main memory, and then the
CPU can access it. For example, disk, CD-ROM, DVD, etc.

Characteristics of Secondary Memory

i. These are magnetic and optical memories.

ii. It is known as the backup memory.
iii. It is a non-volatile memory.
iv. Data is permanently stored even if power is switched off.
v. It is used for storage of data in a computer.
vi. Computer may run without the secondary memory.
vii. Slower than primary memories.

MAIN MEMORY (RAM/ROM)

RAM (Random Access Memory) is the internal memory of the CPU for storing data,
program, and program result. It is a read/write memory which stores data until the
machine is working. As soon as the machine is switched off, data is erased.

3
Access time in RAM is independent of the address, that is, each storage location inside
the memory is as easy to reach as other locations and takes the same amount of time. Data
in the RAM can be accessed randomly but it is very expensive.

RAM is volatile, i.e. data stored in it is lost when we switch off the computer or if there is
a power failure. Hence, a backup Uninterruptible Power System (UPS) is often used with
computers. RAM is small, both in terms of its physical size and in the amount of data it
can hold.

RAM is of two types −

1. Static RAM (SRAM)

2. Dynamic RAM (DRAM)

Static RAM (SRAM)

The word static indicates that the memory retains its contents as long as power is being
supplied. However, data is lost when the power gets down due to volatile nature. SRAM
chips use a matrix of 6-transistors and no capacitors. Transistors do not require power to
prevent leakage, so SRAM need not be refreshed on a regular basis.

There is extra space in the matrix, hence SRAM uses more chips than DRAM for the
same amount of storage space, making the manufacturing costs higher. SRAM is thus
used as cache memory and has very fast access.

Characteristic of Static RAM

i. Long life
ii. No need to refresh
iii. Faster
iv. Used as cache memory
v. Large size
vi. Expensive

4
 vii. High power consumption

Dynamic RAM (DRAM)

DRAM, unlike SRAM, must be continually refreshed in order to maintain the data. This
is done by placing the memory on a refresh circuit that rewrites the data several hundred
times per second. DRAM is used for most system memory as it is cheap and small. All
DRAMs are made up of memory cells, which are composed of one capacitor and one
transistor.

Characteristics of Dynamic RAM

i. Short data lifetime

ii. Needs to be refreshed continuously
iii. Slower as compared to SRAM
iv. Used as RAM
v. Smaller in size
vi. Less expensive
vii. Less power consumption

ROM

ROM stands for Read Only Memory. The memory from which we can only read but
cannot write on it. This type of memory is non-volatile. The information is stored
permanently in such memories during manufacture. A ROM stores such instructions that
are required to start a computer. This operation is referred to as bootstrap. ROM chips
are not only used in the computer but also in other electronic items like washing machine
and microwave oven.

5
TYPES OF ROMs

1. MROM (Masked ROM): The very first ROMs were hard-wired devices that
contained a pre-programmed set of data or instructions. These kind of ROMs are
known as masked ROMs, which are inexpensive.
2. PROM (Programmable Read Only Memory): PROM is read-only memory that
can be modified only once by a user. The user buys a blank PROM and enters the
desired contents using a PROM program. Inside the PROM chip, there are small
fuses which are burnt open during programming. It can be programmed only once
and is not erasable.
3. EPROM (Erasable and Programmable Read Only Memory) :EPROM can be
erased by exposing it to ultra-violet light for a duration of up to 40 minutes.
Usually, an EPROM eraser achieves this function. During programming, an
electrical charge is trapped in an insulated gate region. The charge is retained for
more than 10 years because the charge has no leakage path. For erasing this
charge, ultra-violet light is passed through a quartz crystal window (lid). This
exposure to ultra-violet light dissipates the charge. During normal use, the quartz
lid is sealed with a sticker.
4. EEPROM (Electrically Erasable and Programmable Read Only Memory):
EEPROM is programmed and erased electrically. It can be erased and
reprogrammed about ten thousand times. Both erasing and programming take
about 4 to 10 ms (millisecond). In EEPROM, any location can be selectively
erased and programmed. EEPROMs can be erased one byte at a time, rather than
erasing the entire chip. Hence, the process of reprogramming is flexible but slow.

6
Advantages of ROM

The advantages of ROM are as follows −

i. Non-volatile in nature
ii. Cannot be accidentally changed
iii. Cheaper than RAMs
iv. Easy to test
v. More reliable than RAMs
vi. Static and do not require refreshing
vii. Contents are always known and can be verified

CONCEPT OF MEMORY MANAGEMENT

Memory management is the functionality of an operating system which handles or

manages primary memory and moves processes back and forth between main memory
and disk during execution. Memory management keeps track of each and every memory
location, regardless of either it is allocated to some process or it is free. It checks how
much memory is to be allocated to processes. It decides which process will get memory at
what time. It tracks whenever some memory gets freed or unallocated and
correspondingly it updates the status.

Process Address Space

The process address space is the set of logical addresses that a process references in its
code. For example, when 32-bit addressing is in use, addresses can range from 0 to
0x7fffffff; that is, 2^31 possible numbers, for a total theoretical size of 2 gigabytes.

The operating system takes care of mapping the logical addresses to physical addresses at
the time of memory allocation to the program. There are three types of addresses used in
a program before and after memory is allocated −

S.N. Memory Addresses & Description

7
 1 Symbolic addresses

The addresses used in a source code. The variable names, constants, and
instruction labels are the basic elements of the symbolic address space.

2 Relative addresses

At the time of compilation, a compiler converts symbolic addresses into relative

addresses.

3 Physical addresses

The loader generates these addresses at the time when a program is loaded into
main memory.

Virtual and physical addresses are the same in compile-time and load-time address-
binding schemes. Virtual and physical addresses differ in execution-time address-binding
scheme.

The set of all logical addresses generated by a program is referred to as a logical address
space. The set of all physical addresses corresponding to these logical addresses is
referred to as a physical address space.

The runtime mapping from virtual to physical address is done by the memory
management unit (MMU) which is a hardware device. MMU uses following mechanism
to convert virtual address to physical address.

The value in the base register is added to every address generated by a user process,
which is treated as offset at the time it is sent to memory. For example, if the base register

8
value is 10000, then an attempt by the user to use address location 100 will be
dynamically reallocated to location 10100.

The user program deals with virtual addresses; it never sees the real physical addresses.

Static vs Dynamic Loading

The choice between Static or Dynamic Loading is to be made at the time of computer
program being developed. If you have to load your program statically, then at the time of
compilation, the complete programs will be compiled and linked without leaving any
external program or module dependency. The linker combines the object program with
other necessary object modules into an absolute program, which also includes logical
addresses.

If you are writing a Dynamically loaded program, then your compiler will compile the
program and for all the modules which you want to include dynamically, only references
will be provided and rest of the work will be done at the time of execution.

At the time of loading, with static loading, the absolute program (and data) is loaded into
memory in order for execution to start.

If you are using dynamic loading, dynamic routines of the library are stored on a disk in
relocatable form and are loaded into memory only when they are needed by the program.

Static vs Dynamic Linking

As explained above, when static linking is used, the linker combines all other modules
needed by a program into a single executable program to avoid any runtime dependency.

When dynamic linking is used, it is not required to link the actual module or library with
the program, rather a reference to the dynamic module is provided at the time of
compilation and linking. Dynamic Link Libraries (DLL) in Windows and Shared Objects
in Unix are good examples of dynamic libraries.

9
Swapping

Swapping is a mechanism in which a process can be swapped temporarily out of main

memory (or move) to secondary storage (disk) and make that memory available to other
processes. At some later time, the system swaps back the process from the secondary
storage to main memory.

Though performance is usually affected by swapping process but it helps in running

multiple and big processes in parallel and that's the reason Swapping is also known as a
technique for memory compaction.

The total time taken by swapping process includes the time it takes to move the entire
process to a secondary disk and then to copy the process back to memory, as well as the
time the process takes to regain main memory.

10
Let us assume that the user process is of size 2048KB and on a standard hard disk where
swapping will take place has a data transfer rate around 1 MB per second. The actual
transfer of the 1000K process to or from memory will take

2048KB / 1024KB per second

= 2 seconds

= 2000 milliseconds

Now considering in and out time, it will take complete 4000 milliseconds plus other
overhead where the process competes to regain main memory.

Memory Allocation

Main memory usually has two partitions −

Low Memory − Operating system resides in this memory.

High Memory − User processes are held in high memory.

Operating system uses the following memory allocation mechanism.

S.N. Memory Allocation & Description

1 Single-partition allocation

In this type of allocation, relocation-register scheme is used to protect user

processes from each other, and from changing operating-system code and data.
Relocation register contains value of smallest physical address whereas limit
register contains range of logical addresses. Each logical address must be less than
the limit register.

11
 2 Multiple-partition allocation

In this type of allocation, main memory is divided into a number of fixed-sized

partitions where each partition should contain only one process. When a partition
is free, a process is selected from the input queue and is loaded into the free
partition. When the process terminates, the partition becomes available for another
process.

Fragmentation

As processes are loaded and removed from memory, the free memory space is broken
into little pieces. It happens after sometimes that processes cannot be allocated to memory
blocks considering their small size and memory blocks remains unused. This problem is
known as Fragmentation.

Fragmentation is of two types −

S.N. Fragmentation & Description

1 External fragmentation

Total memory space is enough to satisfy a request or to reside a process in it, but it
is not contiguous, so it cannot be used.

2 Internal fragmentation

Memory block assigned to process is bigger. Some portion of memory is left

unused, as it cannot be used by another process.

The following diagram shows how fragmentation can cause waste of memory and a
compaction technique can be used to create more free memory out of fragmented memory

12
External fragmentation can be reduced by compaction or shuffle memory contents to
place all free memory together in one large block. To make compaction feasible,
relocation should be dynamic.

The internal fragmentation can be reduced by effectively assigning the smallest partition
but large enough for the process.

Paging

A computer can address more memory than the amount physically installed on the
system. This extra memory is actually called virtual memory and it is a section of a hard
that's set up to emulate the computer's RAM. Paging technique plays an important role in
implementing virtual memory.

Paging is a memory management technique in which process address space is broken into
blocks of the same size called pages (size is power of 2, between 512 bytes and 8192
bytes). The size of the process is measured in the number of pages.

Similarly, main memory is divided into small fixed-sized blocks of (physical) memory
called frames and the size of a frame is kept the same as that of a page to have optimum
utilization of the main memory and to avoid external fragmentation.

13
Address Translation

Page address is called logical address and represented by page number and the offset.

Logical Address = Page number + page offset

Frame address is called physical address and represented by a frame number and
the offset.

Physical Address = Frame number + page offset

A data structure called page map table is used to keep track of the relation between a
page of a process to a frame in physical memory.

14
When the system allocates a frame to any page, it translates this logical address into a
physical address and create entry into the page table to be used throughout execution of
the program.

When a process is to be executed, its corresponding pages are loaded into any available
memory frames. Suppose you have a program of 8Kb but your memory can
accommodate only 5Kb at a given point in time, then the paging concept will come into
picture. When a computer runs out of RAM, the operating system (OS) will move idle or
unwanted pages of memory to secondary memory to free up RAM for other processes
and brings them back when needed by the program.

This process continues during the whole execution of the program where the OS keeps
removing idle pages from the main memory and write them onto the secondary memory
and bring them back when required by the program.

Advantages and Disadvantages of Paging

Here is a list of advantages and disadvantages of paging −

i. Paging reduces external fragmentation, but still suffer from internal

fragmentation.

15
 ii. Paging is simple to implement and assumed as an efficient memory
management technique.
iii. Due to equal size of the pages and frames, swapping becomes very easy.
iv. Page table requires extra memory space, so may not be good for a system
having small RAM.

Segmentation

Segmentation is a memory management technique in which each job is divided into

several segments of different sizes, one for each module that contains pieces that perform
related functions. Each segment is actually a different logical address space of the
program.

When a process is to be executed, its corresponding segmentation are loaded into non-
contiguous memory though every segment is loaded into a contiguous block of available
memory.

Segmentation memory management works very similar to paging but here segments are
of variable-length where as in paging pages are of fixed size.

A program segment contains the program's main function, utility functions, data
structures, and so on. The operating system maintains a segment map table for every
process and a list of free memory blocks along with segment numbers, their size and
corresponding memory locations in main memory. For each segment, the table stores the
starting address of the segment and the length of the segment. A reference to a memory
location includes a value that identifies a segment and an offset.

16
THE EVOLUTION OF THE PROCESSOR

Early History

The first processors were enormous machines that were quite slow by today's standards,
though they represented an unprecedented leap in computational power, which previously
had to be done by hand. Development on the first digital computers occurred along three
main independent paths during World War II. These resulted in Germany's Zuse Z3,
Turing Complete computers with no conditional branches, England's Colossus Mark 1
and Mark 2, and America's ENIAC -- known as the first fully-functional computer.

First Generation: Vacuum Tube Processors

After World War II, development of computers took off. UNIVAC, designed by the
principle architects of the ENIAC, was the first computer made for commercial purposes.
Only 46 were built and delivered. Its processor was capable of 19,000 operations per
second w/2.25 Mhz clock, and sold for millions of dollars. Another early computer was
the IBM 650, which shipped first in 1954. Nearly 2,000 were produced over the next
decade and a half, for businesses, schools and governments.

Second Generation: Transistors

17
Transistors, invented in 1947, began replacing vacuum tubes as early as 1955. Smaller in
size, they were known as "minicomputers," but still required several components and a
dedicated room. One example of such computers was the IBM 1401. Another feature of
this era was the PDP-1, released in 1946 with a processor comparable to 2 kilohertz --
100,000 operations per second. This computer was released in limited quantities, but it
had a large impact on various educational institutions, notably MIT.

Third Generation: Integrated Circuits/Microprocessors

Integrated circuits place many individual units of a processor on a single chip, known as
"microchips" in practice. The amount of transistors per chip increased rapidly from tens
in the early '60s to ten-thousands in the mid '70s. In addition, the average price per
integrated circuit dropped from $50 in 1962 to $2.33 in 1968, leading to the rapid
adoption of computers in various businesses. The final step in the development process,
starting in the 1980s and continuing through the present, was "very large-scale
integration." The development started with hundreds of thousands of transistors in the
early 1980s, and continues beyond several billion transistors at the end of the first decade
in the 21st century.

Embedded Systems And Multiple Core Processors

As microprocessors proliferated at the end of the 20th century, processor design has
continued to evolve. Multiple core processors have two or more processing units working
in parallel on a single chip. In addition, cell phones and other small devices have
pioneered the "microcontroller:" a chip that contains a tiny processing unit as well as a
small amount of memory and integrated I/O interfaces. These microcontrollers can be the
size of a fingernail or even smaller.

The Evolution of the Computer Processor

18
The evolution of the computer processor began with the understanding of the principles
of electricity. Although there were ideas on how this technology could be implemented
for much of the 1900s, it was not until the 1960s and early 1970s that scientists were able
to put those ideas into practice.

Intel 4004

The Intel 4004 was released in 1971 and was the first stand-alone computer processor. It
was a 4-bit chip and had 2,300 transistors. Both the Central Air Data Computer and the
Texas Instruments TMS 1000 were created around this time, but neither were sold as an
individual processor.

Intel 8088

Intel released the 8088 chip in 1979. The 8088 was a 16-bit processor and contained
29,000 transistors. This was the chip that was chosen for the first IBM PC.

Intel Pentium and AMD

The Intel Pentium was released in 1993 as a 32-bit processor with 3.21 million
transistors. Two years later Intel's competitor, AMD, released their AM5x86 chip which
performed comparably to Pentium processors, but was able to be installed on older 486
boards.

Intel Pentium M

19
The Intel Pentium M was released in 2003 and was designed specifically with mobile
devices in mind. It integrated with the Intel PRO/Wireless 2100 network and used less
power to allow for longer battery life.

IBM POWER 7

IBM's POWER7 was released in 2009 and contained 1.2 billion transistors on one large
chip that contains between 4 and 8 cores.

The Summary of the Evolution of CPU

Intel Approx.
Generation CPU Year

1st Generation 8086 (1) 1980

. 80186 1981

. 80286 1982

2nd Generation 80286 (2) 1982

3rd Generation 80386 (3) 1987

4th Generation 80486 (4) 1990

5th Generation Pentium (5) 1993

6th Generation Pentium Pro (6) 1995

. Pentium II 1996

. Pent. MMX 1997

. Celeron 1998

. Pentium 3 1999

20
 7th Generation Pentium 4 (7) 2000

. Celeron II 2000

. Duron 2000

8th Generation Intel Core (8) 2006

DX= w/ math copro.

SX= without
SLC= low power

CPU DESIGN: RISC and CISC

RISC

Reduced Instruction Set Computer (RISC) is a type of processor architecture that uses
a small, highly-optimized set of instructions, rather than a more specialized set of
instructions often found in other types of designs or architectures.

The following features are characteristic of most RISC processors:

1. One cycle execution time: RISC processors have a CPI (clock per instruction) of
one cycle. This is due to the optimization of each instruction on the CPU.
2. Pipelining: a technique that allows for simultaneous execution of parts, or stages,
of instructions to more efficiently process instructions.
3. Large number of registers: the RISC design philosophy generally incorporates a
larger number of registers to prevent in large amounts of interactions with
memory.

21
CISC

Complex Instruction Set Computer (CISC) is a type of processor design or architecture

that contains a large set of computer instructions that range from very simple to very
complex and specialized. The design was intended to compute complex instructions in the
most efficient way. Intel Pentium processors are mainly CISC-based.

THE DIFFERENCE BETWEEN RISC AND CISC

RISC CISC
1. Simple instructions, few in Many complex instructions
Number
2. Fixed length instructions Variable length instructions
3. Complexity in compiler Complexity in microcode
4. Only LOAD/STORE Many instructions can
Instructions access memory access memory
5. Few addressing modes Many addressing modes

FUNCTION OF CPU

The CPU processes instructions it receives in the process of decoding data. In processing
this data, the CPU performs four basic steps:

1. Fetch: Each instruction is stored in memory and has its own address. The
processor takes this address number from the program counter, which is
responsible for tracking which instructions the CPU should execute next.
2. Decode: All programs to be executed are translated into assembly instructions.
Assembly code must be decoded into binary instructions, which are
understandable to your CPU. This step is called decoding.

22
 3. Execute: While executing instructions, the CPU can do one of three things: Do
calculations with its ALU, move data from one memory location to another, or
jump to a different address.
4. Store: The CPU must give feedback after executing an instruction, and the output
data is written to the memory.

COMPONENTS OF CPU

CPU itself has following three components.

a. Memory or Storage Unit

b. Control Unit
c. ALU (Arithmetic Logic Unit)

Memory or Storage Unit

This unit can store instructions, data, and intermediate results. This unit supplies
information to other units of the computer when needed. It is also known as internal
storage unit or the main memory or the primary storage or Random Access Memory
(RAM).

Its size affects speed, power, and capability. Primary memory and secondary memory are
two types of memories in the computer. Functions of the memory unit are −
23
 i. It stores all the data and the instructions required for processing.
ii. It stores intermediate results of processing.
iii. It stores the final results of processing before these results are released to an
output device.
iv. All inputs and outputs are transmitted through the main memory.

Control Unit

This unit controls the operations of all parts of the computer but does not carry out any
actual data processing operations.

Functions of this unit are −

i. It is responsible for controlling the transfer of data and instructions among

other units of a computer.
ii. It manages and coordinates all the units of the computer.
iii. It obtains the instructions from the memory, interprets them, and directs the
operation of the computer.
iv. It communicates with Input/output devices for transfer of data or results from
storage.
v. It does not process or store data.

ALU (Arithmetic Logic Unit)

This unit consists of two subsections namely,

1. Arithmetic Section
2. Logic Section

Arithmetic Section

Function of arithmetic section is to perform arithmetic operations like addition,

subtraction, multiplication, and division. All complex operations are done by making
repetitive use of the above operations.

24
Logic Section

Function of logic section is to perform logic operations such as comparing, selecting,

matching, and merging of data.

LOGIC GATES

Digital electronic circuits operate with voltages of two logic levels namely Logic Low
and Logic High. The range of voltages corresponding to Logic Low is represented with
‘0’. Similarly, the range of voltages corresponding to Logic High is represented with ‘1’.

The basic digital electronic circuit that has one or more inputs and single output is known
as Logic gate. Hence, the Logic gates are the building blocks of any digital system. We
can classify these Logic gates into the following three categories.

 Basic gates
 Universal gates
 Special gates

Basic Gates

In earlier chapters, we learnt that the Boolean functions can be represented either in sum
of products form or in product of sums form based on the requirement. So, we can
implement these Boolean functions by using basic gates. The basic gates are AND, OR &
NOT gates.

AND gate

An AND gate is a digital circuit that has two or more inputs and produces an output,
which is the logical AND of all those inputs. It is optional to represent the Logical
AND with the symbol ‘.’.

The following table shows the truth table of 2-input AND gate.

25
 A B Y = A.B

0 0 0

0 1 0

1 0 0

1 1 1

Here A, B are the inputs and Y is the output of two input AND gate. If both inputs are ‘1’,
then only the output, Y is ‘1’. For remaining combinations of inputs, the output, Y is ‘0’.

The following figure shows the symbol of an AND gate, which is having two inputs A, B
and one output, Y.

This AND gate produces an output Y, which is the logical AND of two inputs A, B.
Similarly, if there are ‘n’ inputs, then the AND gate produces an output, which is the
logical AND of all those inputs. That means, the output of AND gate will be ‘1’, when all
the inputs are ‘1’.

OR gate

An OR gate is a digital circuit that has two or more inputs and produces an output, which
is the logical OR of all those inputs. This logical OR is represented with the symbol ‘+’.

The following table shows the truth table of 2-input OR gate.

A B Y=A+B

26
 0 0 0

0 1 1

1 0 1

1 1 1

Here A, B are the inputs and Y is the output of two input OR gate. If both inputs are ‘0’,
then only the output, Y is ‘0’. For remaining combinations of inputs, the output, Y is ‘1’.

The following figure shows the symbol of an OR gate, which is having two inputs A, B
and one output, Y.

This OR gate produces an output Y, which is the logical OR of two inputs A, B.

Similarly, if there are ‘n’ inputs, then the OR gate produces an output, which is the logical
OR of all those inputs. That means, the output of an OR gate will be ‘1’, when at least
one of those inputs is ‘1’.

NOT gate

A NOT gate is a digital circuit that has single input and single output. The output of NOT
gate is the logical inversion of input. Hence, the NOT gate is also called as inverter.

The following table shows the truth table of NOT gate.

A Y = A’

0 1

27
 1 0

Here A and Y are the input and output of NOT gate respectively. If the input, A is ‘0’,
then the output, Y is ‘1’. Similarly, if the input, A is ‘1’, then the output, Y is ‘0’.

The following figure shows the symbol of NOT gate, which is having one input, A and
one output, Y.

This NOT gate produces an output Y, which is the complement of input, A.

Universal gates

NAND & NOR gates are called as universal gates. Because we can implement any
Boolean function, which is in sum of products form by using NAND gates alone.
Similarly, we can implement any Boolean function, which is in product of sums form by
using NOR gates alone.

NAND gate

NAND gate is a digital circuit that has two or more inputs and produces an output, which
is the inversion of logical AND of all those inputs.

The following table shows the truth table of 2-input NAND gate.

A B Y = A.B’

0 0 1

28
 0 1 1

1 0 1

1 1 0

Here A, B are the inputs and Y is the output of two input NAND gate. When both inputs
are ‘1’, the output, Y is ‘0’. If at least one of the input is zero, then the output, Y is ‘1’.
This is just opposite to that of two input AND gate operation.

The following image shows the symbol of NAND gate, which is having two inputs A, B
and one output, Y.

NAND gate operation is same as that of AND gate followed by an inverter. That’s why
the NAND gate symbol is represented like that.

NOR gate

NOR gate is a digital circuit that has two or more inputs and produces an output, which is
the inversion of logical OR of all those inputs.

The following table shows the truth table of 2-input NOR gate

A B Y = A+B’

0 0 1

0 1 0

29
 1 0 0

1 1 0

Here A, B are the inputs and Y is the output. If both inputs are ‘0’, then the output, Y is
‘1’. If at least one of the input is ‘1’, then the output, Y is ‘0’. This is just opposite to that
of two input OR gate operation.

The following figure shows the symbol of NOR gate, which is having two inputs A, B
and one output, Y.

NOR gate operation is same as that of OR gate followed by an inverter. That’s why the
NOR gate symbol is represented like that.

SPECIAL GATES

Ex-OR & Ex-NOR gates are called as special gates. Because, these two gates are special
cases of OR & NOR gates.

Ex-OR gate

The full form of Ex-OR gate is Exclusive-OR gate. Its function is same as that of OR
gate except for some cases, when the inputs having even number of ones.

The following table shows the truth table of 2-input Ex-OR gate.

A B Y = A⊕B

0 0 0

30
 0 1 1

1 0 1

1 1 0

Here A, B are the inputs and Y is the output of two input Ex-OR gate. The truth table of
Ex-OR gate is same as that of OR gate for first three rows. The only modification is in the
fourth row. That means, the output Y is zero instead of one, when both the inputs are one,
since the inputs having even number of ones.

Therefore, the output of Ex-OR gate is ‘1’, when only one of the two inputs is ‘1’. And it
is zero, when both inputs are same.

Below figure shows the symbol of Ex-OR gate, which is having two inputs A, B and one
output, Y.

Ex-OR gate operation is similar to that of OR gate, except for few combinations of inputs.
That’s why the Ex-OR gate symbol is represented like that. The output of Ex-OR gate is
‘1’, when odd number of ones present at the inputs. Hence, the output of Ex-OR gate is
also called as an odd function.

Ex-NOR gate

The full form of Ex-NOR gate is Exclusive-NOR gate. Its function is same as that of
NOR gate except for some cases, when the inputs having even number of ones.

The following table shows the truth table of 2-input Ex-NOR gate.

31
 A B Y = A⊙B

0 0 1

0 1 0

1 0 0

1 1 1

Here A, B are the inputs and Y is the output. The truth table of Ex-NOR gate is same as
that of NOR gate for first three rows. The only modification is in the fourth row. That
means, the output is one instead of zero, when both the inputs are one.

Therefore, the output of Ex-NOR gate is ‘1’, when both inputs are same. And it is zero,
when both the inputs are different.

The following figure shows the symbol of Ex-NOR gate, which is having two inputs A, B
and one output, Y.

Ex-NOR gate operation is similar to that of NOR gate, except for few combinations of
inputs. That’s why the Ex-NOR gate symbol is represented like that. The output of Ex-
NOR gate is ‘1’, when even number of ones present at the inputs. Hence, the output of
Ex-NOR gate is also called as an even function.

From the above truth tables of Ex-OR & Ex-NOR logic gates, we can easily notice that
the Ex-NOR operation is just the logical inversion of Ex-OR operation.

32
DIGITAL CIRCUITS - TWO-LEVEL LOGIC REALIZATION

The maximum number of levels that are present between inputs and output is two in two
level logic. That means, irrespective of total number of logic gates, the maximum number
of Logic gates that are present cascaded between any input and output is two in two level
logic. Here, the outputs of first level Logic gates are connected as inputs of second level
Logic gates.

Consider the four Logic gates AND, OR, NAND & NOR. Since, there are 4 Logic gates,
we will get 16 possible ways of realizing two level logic. Those are AND-AND, AND-
OR, ANDNAND, AND-NOR, OR-AND, OR-OR, OR-NAND, OR-NOR, NAND-AND,
NAND-OR, NANDNAND, NAND-NOR, NOR-AND, NOR-OR, NOR-NAND, NOR-
NOR.

These two level logic realizations can be classified into the following two categories.

1. Degenerative form
2. Non-degenerative form

Degenerative Form

If the output of two level logic realization can be obtained by using single Logic gate,
then it is called as degenerative form. Obviously, the number of inputs of single Logic
gate increases. Due to this, the fan-in of Logic gate increases. This is an advantage of
degenerative form.

Only 6 combinations of two level logic realizations out of 16 combinations come under
degenerative form. Those are AND-AND, AND-NAND, OR-OR, OR-NOR, NAND-
NOR, NORNAND.

In this section, let us discuss some realizations. Assume, A, B, C & D are the inputs and
Y is the output in each logic realization.

AND-AND Logic

33
In this logic realization, AND gates are present in both levels. Below figure shows an
example for AND-AND logic realization.

We will get the outputs of first level logic gates as Y1=AB and Y2=CD

These outputs, Y1 and Y2 are applied as inputs of AND gate that is present in second
level. So, the output of this AND gate is

Y=Y1Y2

Substitute Y1and Y2 values in the above equation.

Y= (AB)(CD)

⇒Y=ABCD

Therefore, the output of this AND-AND logic realization is ABCD. This Boolean
function can be implemented by using a 4 input AND gate. Hence, it is degenerative
form.

AND-NAND Logic

In this logic realization, AND gates are present in first level and NAND gates are present
in second level. The following figure shows an example for AND-NAND
logic realization.

34
Previously, we got the outputs of first level logic gates as Y1=AB and Y2=CD

These outputs, Y1 and Y2 are applied as inputs of NAND gate that is present in second
level. So, the output of this NAND gate is

Y= (Y1Y2)′

Substitute Y1 and Y2 values in the above equation.

Y=((AB)(CD))′

⇒Y=(ABCD)′

Therefore, the output of this AND-NAND logic realization is (ABCD)′. This Boolean
function can be implemented by using a 4 input NAND gate. Hence, it is degenerative
form.

OR-OR Logic

In this logic realization, OR gates are present in both levels. The following figure shows
an example for OR-OR logic realization.

35
We will get the outputs of first level logic gates as Y1=A+B and Y2=C+D.

These outputs, Y1 and Y2 are applied as inputs of OR gate that is present in second level.
So, the output of this OR gate is

Y=Y1+Y2

Substitute Y1 and Y2 values in the above equation.

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

⇒Y=A+B+C+D

Therefore, the output of this OR-OR logic realization is A+B+C+D. This Boolean
function can be implemented by using a 4 input OR gate. Hence, it is degenerative form.

Similarly, you can verify whether the remaining realizations belong to this category or
not.

Non-degenerative Form

If the output of two level logic realization can’t be obtained by using single logic gate,
then it is called as non-degenerative form.

The remaining 10 combinations of two level logic realizations come under non-
degenerative form. Those are AND-OR, AND-NOR, OR-AND, OR-NAND, NAND-
AND, NANDOR, NAND-NAND, NOR-AND, NOR-OR, NOR-NOR.

Now, let us discuss some realizations. Assume, A, B, C & D are the inputs and Y is the
output in each logic realization.

AND-OR Logic

In this logic realization, AND gates are present in first level and OR gates are present in
second level. Below figure shows an example for AND-OR logic realization.

36
Previously, we got the outputs of first level logic gates as Y1=AB and Y2=CD.

These outputs, Y1 and Y2 are applied as inputs of OR gate that is present in second level.
So, the output of this OR gate is

Y=Y1+Y2

Substitute Y1 and Y2 values in the above equation

Y=AB+CD

Therefore, the output of this AND-OR logic realization is AB+CD. This Boolean
function is in Sum of Products form. Since, we can’t implement it by using single logic
gate, this AND-OR logic realization is a non-degenerative form.

AND-NOR Logic

In this logic realization, AND gates are present in first level and NOR gates are present in
second level. The following figure shows an example for AND-NOR logic realization.

We know the outputs of first level logic gates as Y1=AB and Y2=CD

37
These outputs, Y1 and Y2 are applied as inputs of NOR gate that is present in second
level. So, the output of this NOR gate is

Y=(Y1+Y2)′

Substitute Y1 and Y2values in the above equation.

Y=(AB+CD)′

Therefore, the output of this AND-NOR logic realization is (AB+CD)′. This Boolean
function is in AND-OR-Invert form. Since, we can’t implement it by using single logic
gate, this AND-NOR logic realization is a non-degenerative form

OR-AND Logic

In this logic realization, OR gates are present in first level & AND gates are present in
second level. The following figure shows an example for OR-AND logic realization.

Previously, we got the outputs of first level logic gates as Y1=A+B and Y2=C+D.

These outputs, Y1and Y2 are applied as inputs of AND gate that is present in second
level. So, the output of this AND gate is

Y=Y1Y2

Substitute Y1 and Y2 values in the above equation.

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

38
Therefore, the output of this OR-AND logic realization is A+B, C+D. This Boolean
function is in Product of Sums form. Since, we can’t implement it by using single logic
gate, this OR-AND logic realization is a non-degenerative form.

Similarly, you can verify whether the remaining realizations belong to this category or
not.

DIGITAL COMBINATIONAL CIRCUITS

Combinational circuits consist of Logic gates. These circuits operate with binary values.
The outputs of combinational circuit depends on the combination of present inputs. The
following figure shows the block diagram of combinational circuit.

This combinational circuit has ‘n’ input variables and ‘m’ outputs. Each combination of
input variables will affect the outputs.

Design procedure of Combinational circuits

 Find the required number of input variables and outputs from given specifications.
 Formulate the Truth table. If there are ‘n’ input variables, then there will be 2n
possible combinations. For each combination of input, find the output values.
 Find the Boolean expressions for each output. If necessary, simplify those
expressions.
 Implement the above Boolean expressions corresponding to each output by
using Logic gates.

39
Code Converters

We have discussed various codes in the chapter named codes. The converters, which
convert one code to other code are called as code converters. These code converters
basically consist of Logic gates.

Example

Binary code to Gray code converter

Let us implement a converter, which converts a 4-bit binary code WXYZ into its
equivalent Gray code ABCD.

The following table shows the Truth table of a 4-bit binary code to Gray code converter.

Binary code WXYZ WXYZ Gray code ABCD

0000 0000

0001 0001

0010 0011

0011 0010

0100 0110

0101 0111

0110 0101

0111 0100

1000 1100

1001 1101

40
 1010 1111

1011 1110

1100 1010

1101 1011

1110 1001

1111 1000

From Truth table, we can write the Boolean functions for each output bit of Gray code as
below.

A=∑m(8,9,10,11,12,13,14,15)

B=∑m(4,5,6,7,8,9,10,11)

C=∑m(2,3,4,5,10,11,12,13)

D=∑m(1,2,5,6,9,10,13,14)

Let us simplify the above functions using 4 variable K-Maps.

The following figure shows the 4 variable K-Map for simplifying Boolean function, A.

By grouping 8 adjacent ones, we got A=W

The following figure shows the 4 variable K-Map for simplifying Boolean function, B.

41
There are two groups of 4 adjacent ones. After grouping, we will get B as

B=W′X+WX′=W⊕X

Similarly, we will get the following Boolean functions for C & D after simplifying.

C=X′Y+XY′=X⊕Y

D=Y′Z+YZ′=Y⊕

The following figure shows the circuit diagram of 4-bit binary code to Gray code
converter.

Since the outputs depend only on the present inputs, this 4-bit Binary code to Gray code
converter is a combinational circuit. Similarly, you can implement other code converters.

Parity Bit Generator

42
There are two types of parity bit generators based on the type of parity bit being
generated. Even parity generator generates an even parity bit. Similarly, odd parity
generator generates an odd parity bit.

Even Parity Generator

Now, let us implement an even parity generator for a 3-bit binary input, WXY. It
generates an even parity bit, P. If odd number of ones present in the input, then even
parity bit, P should be ‘1’ so that the resultant word contains even number of ones. For
other combinations of input, even parity bit, P should be ‘0’. The following table shows
the Truth table of even parity generator.

Binary Input WXY Even Parity bit P

000 0

001 1

010 1

011 0

100 1

101 0

110 0

111 1

From the above Truth table, we can write the Boolean function for even parity bit as

P=W′X′Y+W′XY′+WX′Y′+WXY

⇒P=W′(X′Y+XY′)+W(X′Y′+XY)

43
⇒P=W′(X⊕Y)+W(X⊕Y)′=W⊕X⊕Y

The following figure shows the circuit diagram of even parity generator.

This circuit consists of two Exclusive-OR gates having two inputs each. First Exclusive-
OR gate having two inputs W & X and produces an output W ⊕ X. This output is given
as one input of second Exclusive-OR gate. The other input of this second Exclusive-OR
gate is Y and produces an output of W ⊕ X ⊕ Y.

Odd Parity Generator

If even number of ones present in the input, then odd parity bit, P should be ‘1’ so that the
resultant word contains odd number of ones. For other combinations of input, odd parity
bit, P should be ‘0’.

Follow the same procedure of even parity generator for implementing odd parity
generator. The circuit diagram of odd parity generator is shown in the following figure.

The above circuit diagram consists of Ex-OR gate in first level and Ex-NOR gate in
second level. Since the odd parity is just opposite to even parity, we can place an inverter
at the output of even parity generator. In that case, the first and second levels contain an
ExOR gate in each level and third level consist of an inverter.

Parity Checker

44
There are two types of parity checkers based on the type of parity has to be
checked. Even parity checker checks error in the transmitted data, which contains
message bits along with even parity. Similarly, odd parity checker checks error in the
transmitted data, which contains message bits along with odd parity.

Even parity checker

Now, let us implement an even parity checker circuit. Assume a 3-bit binary input, WXY
is transmitted along with an even parity bit, P. So, the resultant word data contains 4 bits,
which will be received as the input of even parity checker.

It generates an even parity check bit, E. This bit will be zero, if the received data
contains an even number of ones. That means, there is no error in the received data. This
even parity check bit will be one, if the received data contains an odd number of ones.
That means, there is an error in the received data.

The following table shows the Truth table of an even parity checker.

4-bit Received Data WXYP Even Parity Check bit E

0000 0

0001 1

0010 1

0011 0

0100 1

0101 0

0110 0

0111 1

45
 1000 1

1001 0

1010 0

1011 1

1100 0

1101 1

1110 1

1111 0

From the above Truth table, we can observe that the even parity check bit value is ‘1’,
when odd number of ones present in the received data. That means the Boolean function
of even parity check bit is an odd function. Exclusive-OR function satisfies this
condition. Hence, we can directly write the Boolean function of even parity check bit as

E=W⊕X⊕Y⊕P

The following figure shows the circuit diagram of even parity checker.

This circuit consists of three Exclusive-OR gates having two inputs each. The first level
gates produce outputs of W⊕X & Y⊕P. The Exclusive-OR gate, which is in second level
produces an output of W⊕X⊕Y⊕P

Odd Parity Checker

46
Assume a 3-bit binary input, WXY is transmitted along with odd parity bit, P. So, the
resultant word data contains 4 bits, which will be received as the input of odd parity
checker.

It generates an odd parity check bit, E. This bit will be zero, if the received data
contains an odd number of ones. That means, there is no error in the received data. This
odd parity check bit will be one, if the received data contains even number of ones. That
means, there is an error in the received data.

Follow the same procedure of an even parity checker for implementing an odd parity
checker. The circuit diagram of odd parity checker is shown in the following figure.

The above circuit diagram consists of Ex-OR gates in first level and Ex-NOR gate in
second level. Since the odd parity is just opposite to even parity, we can place an inverter
at the output of even parity checker. In that case, the first, second and third levels contain
two Ex-OR gates, one Ex-OR gate and one inverter respectively.

47