SMS COLLEGE OF ARTS AND

SCIENCE

DEPARTMENT OF COMPUTER SCIENCE

 DIGITAL FUNDAMENTALS AND COMPUTER ARCHITECTURE

UNIT I:
Number System and Binary Codes: Decimal, Binary, Octal, Hexadecimal – Binary addition,
Multiplication, Division – Floating point representation, Complements, BCD, Excess3, Gray Code.
Arithmetic Circuits: Half adder, Full adder, Parallel binary adder, BCD adder, Half subtractor, Full
subtractor, Parallel binary subtractor - Digital Logic: the Basic Gates – NOR, NAND, XOR Gates.

UNIT II:
Combinational Logic Circuits: Boolean algebra – Karnaugh map – Canonical form 1 – Construction and
properties – Implicants – Don‘t care combinations - Product of sum, Sum of products, simplifications.
Sequential circuits: Flip-Flops: RS, D, JK, and T - Multiplexers – Demultiplexers – Decoder Encoder –
shift registers-Counters.

UNIT III:
Input – Output Organization: Input – output interface – I/O Bus and Interface – I/O Bus Versus Memory
Bus – Isolated Versus Memory – Mapped I/O – Example of I/O Interface. Asynchronous data transfer:
Strobe Control and Handshaking
Priority Interrupt: Daisy- Chaining Priority, Parallel Priority Interrupt. Direct Memory Access: DMA
Controller, DMA Transfer. Input – Output Processor: CPU-IOP Communication.

UNIT IV: Memory Organization: Memory Hierarchy – Main Memory- Associative memory: Hardware
Organization, Match Logic, Read Operation, Write Operation. Cache Memory: Associative, Direct, Set-
associative Mapping – Writing into Cache Initialization.

TEXT BOOKS:
1. Digital Electronics Circuits and Systems, V.K. Puri, TMH.
2. Digital principles and applications, Albert Paul Malvino, Donald P Leach, TMH, 1996.
3. Computer System Architecture -M. Morris Mano , PHI.

REFERENCE BOOKS:
1. Computer Architecture -M. Carter, Schaum’s outline series, TMH
 UNIT – I
Number System and Binary Codes

1.Introduction
Definition:
In digital electronics, the number system is used for representing the information.
The number system has different bases and the most common of them are the decimal, binary, octal,
and hexadecimal.

Types of Number Systems

Some of the important types of number system are ,

1.Decimal Number System

2.Binary Number System

3.Octal Number System

4.Hexadecimal Number System

These number systems are explained below in details.

1.1 Decimal Number Systems
The number system is having digit 0, 1, 2, 3, 4, 5, 6, 7, 8, 9; this number system is known as a
decimal number system because total ten digits are involved.The base of the decimal number system is 10.

1.2 Binary Number Systems

The modern computers do not process decimal number; they work with another number system
known as a binary number system which uses only two digits 0 and1.

The base of binary number system is 2 because it has only two digit 0 and 1.The digital electronic
equipments are works on the binary number system and hence the decimal number system is converted into
binary system.

Hexa decimal Binary Decimal

0 0000 0

1 0001 1

2 0010 2

3 0011 3

4 0100 4

5 0101 5

6 0110 6

7 0111 7

8 1000 8

9 1001 9

A 1010 10

B 1011 11
 C 1100 12

D 1101 13

E 1110 14

F 1111 15

1.3. Octal Numbers

The base of a number system is equal to the number of digits used, i.e., for decimal number system
the base is ten while for the binary system the base is two. The octal system has the base of eight as it uses
eight digits 0, 1, 2, 3, 4, 5, 6, 7.

1. 4 Hexadecimal Numbers
The hexadecimal number system has a base of 16, and hence it consists of the following sixteen
number of digits.

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F.

2.Conversions :
2.1 Decimal number to other conversions :
1. Decimal to binary conversion
The radix point splits the number into two parts; the part to the left of the radix point is called the
INTEGER. The part to the right of the radix point is the FRACTION. A number such as 34.62510 is
therefore split into 3410 (the integer)

To convert a decimal number into binary number it requires successive division by 2 writing down
each quotient and its remainder. The remainders are taken in the reverse order, which is the binary
equivalent of the decimal number.

Example : 2510

2 25
2 12 -1
2 6 -0
2 3 -0
1 -1
 Ans : The binary equivalent for 2510 =110012
HW

1. 15010 =?
2. 18610=?

2 .Decimal to octal conversion :

Conversion from decimal to octal can be performed by repeatedly dividing the decimal number by 8
and using each remainder as a digit in the octal number being formed.
The octal number system has a base radix of 8.
The reminders read in the reverse order.
Example : (200)10

8 200
8 25 - 0
3 - 1
Therefore (200)10 = (310)8
HW :
1. (888)10 =?
2. (1993)10 =?
3. Decimal to Hexadecimal conversion :

One way to convert decimal to Hexadecimal is the hex dabbles. The idea is as divide successively
by 16, writing down the remainders.
Example :2429

16 2429

16 154 -15 F

9 - 10 A

Therefore (2429)10 = (9AF)16

HW :
1. (1993)10
2. (198)10

2.2 Binary number to other conversions :

1. Binary to decimal number :

Octal Binary Decimal

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

For converting the value of Binary numbers to decimal equivalent we have to find its quantity,
which is found by multiplying a digit by its place value.

Example :
1)101
=1*23-1 +0*23-2+1*23-3
= 1*22 +0*21+1*20
= 4 + 0 +1
= 5

2)1001
=1*24-1 +0*24-2+0*24-3 + 1*24-4
= 1*23 + 0*22 + 0*21 + 1*20
= 8+1
=9

3)11.011
=1*22-1 +1*22-2+0*22-3 +1*22-4+1*22-5
=1*21 +1*20+0*2-1 +1*2-2+1*2-3
2
= 2+1+0+ 1/2 +1/23
= 2+1+1/4+1/8
=3+1*2/4*2+1/8
=3+2/8+1/8
=3 + 3/8
=24+3/8
=27/8
=3.37
HW :
1. 1. (10110)2 = ?

2.Binary to octal conversion :

There is a simple trick for converting a binary number to an octal number. Simply group the binary
digits into groups of 3, starting at the octal point, and read each set of three binary digits according to above
table.

Example :011101 = 011 101

= 3 5
 = (3 5) 8

HW :
1.(010101110) 2 = ?
2. (010100110) 2 = ?

3.Binary to hexadecimal :

To convert binary to hexadecimal, we simply break a binary number into groups of four
digits and convert each group of four digits according to the preceding code. Here are some
examples:
Example:1
(10111011)2 = 1011 1011
= B B

= (B B)16
Example:2
(10010101)2 = 1001 0101
= 9 5
= (9 5)16

2.3 Octal number to other conversions :

1.Octal to decimal
To convert an octal number to a decimal number, we use the same sort of polynomial as
was used in the binary case, except that we now have a radix of 8 instead of 2.

Example :
1213=?

=1*83+2*82+1*81+3*80
=512 + 128 + 8 + 3
=651

Example :

1.1038 2.1023

2.Octal to binary

The conversion from octal number to binary number is easily accomplished.

Each octal bit is converted to its three digit binary equivalent.
Example:

(2 6 1 5 3. 7 4 0 6)8
 (010 110 001 101 011. 111 100 000 110)2

HW :

1.(1023)

2.125.125

3.Octal to hexadecimal
The method of converting octal to hexadecimal number is to convert the given octal
number to binary number and then arrange the binary digits into groups of 4 starting at the binary
point.
Example :
Convert octal number 714.06 to hexadecimal.
(714.06)8 =(111 001 100.000 110)2
=0001 1100 1100 . 0001 1000
=1 C C . 1 8
The hexadecimal equivalent of (714.06)8 is (1CC.18)16

HW :
1.346 = ?
2.4 Hexadecimal to other conversions :

1.Hexadecimal to binary

To convert a hexadecimal number to a binary number, convert each hexadecimal digit to

its 4-bit equivalent using the code.
Example :1
( 3 0 6 . D)16

( 0011 0000 0110 . 1101)2

Example : 2
9 A F

1001 1010 1111

Example : 3

C 5 E 2

1100 0101 1100 0010

2.Hexadecimal to octal

The conversion of Hexadecimal number to octal number involves two steps. First the
method suggests to go from hexadecimal to binary numbers and second from binary to octal
numbers.

Example: convert Hexadecimal (217) to octal conversion

(217)16 = (0010 0001 0111)2

= (001 000 010 111)
= 1027
The octal equivalent of (217)16 is (1027)8
HW :

1.432 =?

3.Hexadecimal to decimal

The conversion of Hexadecimal to decimal is straightforward but time consuming. In

Hexadecimal number system each digit position corresponds to a power of 16.

Example : BB
BB=B*161 +B*160
=11*16+11*1
=176+11
=187
HW :
1.3246 = ?

3. Binary addition, Multiplication, Division :

3.1 Binary addition
Binary addition is performed in the same manner as decimal addition. The complete table
for binary addition is as follows:
0+0=0
0+1=1
1+0=1
1+1=0 plus a carry over of 1

‘Carry over’ are performed in the same manner as in decimal arithmetic. Since 1 is the
largest digit in the binary system, any sum greater than 1 requires that a digit be carried.

Example :11+10 = ?

1 1

1 0

10 1
HW:
1.111 +100
2.1001+1111

3.2 Binary subtraction :

Subtraction is the inverse operation of addition. To subtract, it is necessary to establish a

procedure for subtracting a larger from a smaller digit. The only case in which this occurs with
binary numbers is when 1 is subtracted from 0. It is necessary to borrow 1 from the next column to
the left.

This is the binary subtraction table.

0-0=0
1-0=1
0- with a borrow of
1=1 1
1-
1=0
Example :

1001 – 101 =?

1 0 0 1
- 1 0 1

1 0 0

HW :
1.11.01111 =01.00110

3.3 Binary Multiplication :

The table for binary multiplication is very short, with only four entries instead of the
many for normal decimal multiplication
0*0=0
0*1=0
1*0=0
1*1=1
Example :

11*10 = ?

1 1 * 1 0

1 0

1 1

1 1 0

HW :
1.101.111 =?
3.4 Binary division :

Binary division as follows :

0/1=0
1/1=1

Example:1 111
110 101010
110
1001
110
110
110
0
Example :2
111 /10
11
` 10 1 1 1
10

1 1
1 0
1

4. Floating point representation :

Floating point numbers consists of two parts.

1.The first part of the number is a signed fixed- point number, which is termed as mantissa.
2.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.
Always mantisa part is an integer part,the number which splits by dots(.) are fraction part.

Example:

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

Sign Sign
 0 1234 0 02

Mantissa(fraction) Exponent

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.
The floating point representation is a must as it is useful in scientific calculations. Real
numbers are normally represented as floating point numbers.

5.Complements:

Complements consist of two parts:

1.1’s complement
2. 2’s complement
5.1 1’s complement :
The 1’s complement of a binary number is obtained by changing each 0 to 1
and each 1 to 0 .
Ex : 010111
1’s complement of given no is :101000

5.2 2’s complement :

The 2’s complement of a binary no is obtained by adding 1 to the least significant bit
of the 1’s complement of that binary number.

Ex:2’s complement of 001

1st take 1’s complement : 110

Then adding 1:110+1
Answer is :111
Perform the following subtraction using 1’s complementary arithmetic
a)11001-10110
1’s complement of subtracted number is – 01001
Add two numbers
11001
01001

100010
Carry last digit and add 1 to above answer
00010
 1

Ans : 00011

HW :
1.1011-0101
Perform the following subtraction using 2’s complementary arithmetic

a)11011 - 11001

Take 1’s complement of subtracted number - 00110

Hear add 1 in the least bit 00110+1 =00111

After add two numbers 11011+00111

11011

00111

100010

Carry is dropped

Thus the answer is 00010 = 10

HW :

1.01011 - 11000
6. BCD :(Binary coded decimal)
In BCD number system a group of binary bit is used to represent each of 10 decimal
digits.

BCD is a way to express each of the decimal digits with a binary code.

A code is certain special group of symbols used to represent numbers,letters Etc

The advantage of the BCD code is an easy mode of conversion from decimal to binary
and binary to decimal.

BINARY CODE DECIMAL DIGIT

0000 0
0001 1
0010 2
0011 3
0100 4
0101 5
0110 6
0111 7
1000 8
1001 9
Table 1.5 Binary Coded Decimal

Examples:

1.Convert decimal 4019 to BCD

4 0 1 9

0100 0000 0001 1001

The BCD equivalent of (4019) 10 is = ( 0100 0000 0001)

1001

2.Convert BCD number 0001 1001 0000 0111 to decimal

0001 1001 0000 0111

1 9 0 7

The decimal equivalent of BCD Number 0001 1001 0000 0111 is 1907. BCD numbers
are useful wherever decimal information is transferred into a computer.
The pocket calculator is one of the best examples for the application of BCD numbers.
 Other examples of BCD system are electronic counters, digital voltmeter and digital clocks.

7. Excess 3:
The Excess-3 code is a decimal code that has been used in older computers.

In the excess-3 code,3 is added to each decimal digit and then each of the resulting digit
is converted to an equivalent binary number.
Excess-3 code in short is abbreviated as XS3.

DECIMAL BCD EXCESS 3

CODE
0 0000 0011
1 0001 0100
2 0010 0101
3 0011 0110
4 0100 0111
5 0101 1000
6 0110 1001
7 0111 1010
8 1000 1011
9 1001 1100
10 0001 0100 0011
0000
11 0001 0100 0100
0001
Table : Excess – 3 code
Example :
Decimal number is 14
Added 3 in each digit 14+33
14
33
47 = (0100 0111)
8.Gray Code:
⮚ Digital systems can process data in discrete form only.
⮚ The data must be converted into digital form before they can be used by a digital computer.
⮚ The reflected binary or gray code is shown in the table is sometimes used for the converted digital
data.
⮚ Gray code also called cyclic or reflected code.
Example :
Convert the following binary numbers to gray code.
To convert a binary number to its equivalent gray code,write the MSB as it is.add this MSB to next binary
position.write the sum and ignore any carry.
Sum : 110100
MSB(Most significant bit) is = 1

1 1 0 1 0 0 LSB(Least significant bit)

MSB 1 0 1 1 1 0
Ans :(110100)2 = 101110 graycode value
Convert the following gray code to binary number.
Sum : 110111
MSB(Most significant bit) is = 1

1 1 0 1 1 1

MSB 1 0 0 1 0 1

Ans :Graycode 110111 = (100101) 2

Arithmetic Circuits
Adder :
⮚ Adder circuit is combinational digital circuit
⮚ It is used for adding two numbers.
⮚ Adder circuit produces a sum bit(s) and carry (c) as the output.
⮚ Adder circuits are two types.
1.Half adder
2.Full adder

9.Half adder:
A basic module used in binary arithmetic elements is the half-adder. The function of the
half-adder is to add two binary digits, producing a sum according to the binary addition rules.

INPUT SUM OF BITS

0+0 0
0+1 1
1+0 1
 1+1 0 With a carry of
1

Table : Addition Table

Block diagram :

⮚ Half adder is a combinational of arithmetic circuit that adds two numbers and produces a
sum bit and carry bit.
⮚ It is conatructed using XOR and AND gate.but only add two inputs.

Truth table :

A B S C
0 0 0 0
1 0 1 0
0 1 1 0
1 1 0 1

10.Full adder:
Full Adder is the adder which adds three inputs and produces two outputs. The first two
inputs are A and B and the third input is an input carry as C-IN.
The output carry is designated as C-OUT and the normal output is designated as S which
is SUM.
A full adder circuit is central to most digital circuits that perform addition or
subtraction.

X Full Adder S
Y C0
Ci

Full adder circuit – Block Diagram

X
Y S

Logic Diagram

INPUT OUTPU
T
X Y C S C
I 0
0 0 0 0 0
0 0 1 1 0
0 1 0 1 0
0 1 1 0 1
1 0 0 1 0
1 1 0 0 1
1 1 1 1 1

Truth Table

11.Parallel binary adder:

⮚ The purpose of this adder is to add two 4-bit binary integers.

⮚ The parallel binary adder is a digital circuit that produces the arithmetic sum of the two binary
numbers in parallel.
 ⮚ It consist of full adder connected in a chain,with output carry from the each full adder.
⮚ When one binary number is added to other,each column generates the sum bit 1(or) 0 carry bit to
the next column to the left.
⮚ Two bit binary number need two adders , 4 bit number need 4 adders.

11.1 4- Bit binary adder :

A basic 4-bit parallel adder is implemented with the four full adders.
In above diagram 4 binary digits are
1.A0 – A3 = 1st 4-bit number
2. B0 – B3 = 2st 4-bit number

12.BCD adder :
⮚ BCD stands for Binary Coded Decimal Adder.
⮚ Addition of two BCD digits requires two 4-bit parallel adder circuit.
⮚ The BCD-Adder is used in the computers and the calculators that perform arithmetic operation
directly in the decimal number system. The BCD-Adder accepts the binary-coded form of decimal
numbers.
 Carry in

X1 X2 X3
X4 Carry out
Augend Digit

Z1
Y1 Y2 Z2 Sum Digit
Addend Y3 Decimal Z3
Digit Y4 Adder Z4
The adder has an augends digit input consisting of four lines, an addend digit input for four lines, a carry-
in and a carryout, and a sum digit with four output lines. The augend digit, addend digit and sum digit with
four-output line.
Example :
X=0100 y=1100

input output carry

x1= 0 y1=1 Z1=1 0
X2=1 y2=1 Z2=0 1
X3=0 y3=0 Z3=1 0
X4=0 y4=0 Z4=0 0

13. Half subtractor :

A half subtractor subtracts a bit from another.

It is a multiple output combinational logic network which subtract two bits of binary data.
The subtraction table (or truth table) of a half subtractor is shown below. The half
subtractor has two input bits A and B two output bits, a difference DIFF = (A-B) and a Borrow.

Rules :
INPUTS
BORROW DIFFERENCE= AB+AB
DIFF BORROW= AB
A
B
0
0
Truth table

Half subtractor :
14.Full subtractor :

A full subtractor subtracts with three bits (A-B-C). The third bit C is the borrow from previous stage.
A full subtractor is a multiple output combinational logic network which performs a subtraction between
two binary bits a and b.
Truth table :

Inputs Outputs
Minuend Subtrahend Borrow Difference Borrow
(A) (B) (Bin) (D) (Bout)
0 0
0 0 0
0
0 1 1 1
1
0 1 0 1
1
0 1 1 0
1
0 0 1 0
0
1 0 1 0
1
1 0 0 0
1 1
1 1 1
Circuit diagram :

Diagram : Full Subtractor

15.Parallel binary subtractor :

In parallel binary subtractor connecting 3 full subtractor and one half subtractor.

Advantages of parallel Adder/Subtractor

1. The parallel adder/subtractor performs the addition operation faster as compared to serial
adder/subtractor.
2. Time required for addition does not depend on the number of bits.
3. The output is in parallel form i.e all the bits are added/subtracted at the same time.
4. It is less costly.
Disadvantages of parallel Adder/Subtractor
1. Each adder has to wait for the carry which is to be generated from the previous adder in chain.
2. The propagation delay( delay associated with the travelling of carry bit) is found to increase with the
increase in the number of bits to be added.

Digital Logic

16.The Basic Gates – NOR, NAND, XOR Gates :

⮚ Gates are digital circuits because input and output signals have only two status.
⮚ Either low(or) high,low means 0 and high means 1.
⮚ Gates are also called logic circuits.
⮚ A gate is actually a circuit with one (or) more than input signal but having only one output signal.
⮚ Digital systems are said to be constructed by using logic gates. The basic gates are the AND, OR,
NOT gates.

1.AND gate :
The AND gate is an electronic circuit that gives a high output (1) only if all its inputs are high. A dot (.) is used to
show the AND operation i.e. A.B. Bear in mind that this dot is sometimes omitted i.e. AB

2. OR gate

The OR gate is an electronic circuit that gives a high output (1) if one or more of its inputs are high. A plus (+) is
used to show the OR operation.

3. NOT gate

The NOT gate is an electronic circuit that produces an inverted version of the input at its output. It is also known as
an inverter. If the input variable is A, the inverted output is known as NOT A.

4.EXOR gate

The 'Exclusive-OR' gate is a circuit which will give a high output if either, but not both, of its two inputs are
high. An encircled plus sign ( ) is used to show the EOR operation.
5.NOR gate :

NOR gate is actually means NOT-OR.

6.NAND gate :
⮚ NAND gate is actually means NOT-AND.
⮚ It allows two or more inputs but only one output , which is complement of the AND product of all
inputs.

UNIT – 2
Combinational Logic Circuits

2. KARNAUGH MAP :

⮚ The k-map provides simple and straight forward method of minimizing Boolean expression.

⮚ k-map used to simplifying four and even six variables.

⮚ k-map also be described as a special arrangement of a truth table.

⮚ The k-map ia made up of squares.

 ⮚ Each square in a map representing one team.

⮚ The k-map is systematic method for combining terms and determining minimal expression.

⮚ Each n variable map consist of 2n cells

3.Canonical form 1 :

⮚ Canonical forms for Boolean functions are sum of products (SOP) form and basic forms.

⮚ Any variable taken in uncompleted form in the product if it has the value 1 and should be
taken in completed form if it has the value 0.

⮚ In three variable function f(A,B,C) the value of A,B and C are 1,0,1 respectively,then the
product term will be ABC.

⮚ Each of all the variables as factors in either completed or uncompleted form is known as
minterm.

⮚ The switching function expressed as the sum of all the minterms is called the canonical sum
of products(SOP).

3.1 Example :

Find the sum of product (SOP) form of switching function f(A,B,C) which is represented by the truth
table given below :

Decimal A B C f
value
0 0 0 0 0
1 0 0 1 1
2 0 1 0 1
3 0 1 1 0
4 1 0 0 1
5 1 0 1 0
6 1 1 0 0
7 1 1 1 1

f(0,3,5,6) = ∑(0,3,5,6)

f(1,2,4,7) = ∑(1,2,4,7)

In the above table that the decimal value for which the function f assumes the value 1 are 1,2,4,7.

Thus the function f(a,b,c) is the sum of the product (i.e)

SOP :

= ∑(1,2,4,7)
 = 001+010+100+111

F(a,b,c)= A B C + A B C + A B C + A B C

4.Construction and properties :

⮚ The k-map is a modified form of the Venn diagram of the switching function with four or less
variables in the canonical sum of products form.

⮚ Each square of the k-map is denoted by a binary number (or) its equivalent decimal.

⮚ If the switching function consists of 3 variables,then the k-map has 8(=23) squares and if the
function consist of four variables , then the map has 16(=24) small squares .

⮚ To construct the k-map of a switching function ,first the function is represented in the sum of
products form.

4.1 Example :

f=ABC+ABC+ABC+ABC+ABC

= 000+ 001 + 010 + 011 + 111

= ∑(0,1,2,3,7)

5.Implicants :

⮚ A switching function of four or less than four variables is represented on a k-map.

⮚ The simpltfied product term obtained by combining the minterms of set are called implicants of the
switching function.

⮚ Implicant is a product/minterm term in Sum of Products (SOP) or sum/maxterm term in Product of

Sums (POS) of a Boolean function. E.g., consider a boolean function, F = AB + ABC +
BC. Implicants are AB, ABC and BC

1.Prime implicants

2.Essential prime implicants

3.Redundant Prime Implicants

4. Selective Prime Implicants

1.Prime implicants :

A group of square or rectangle made up of bunch of adjacent minterms which is allowed by

definition of K-Map are called prime implicants(PI) i.e. all possible groups formed in K-Map.

Example:
2.Essential prime implicants :

These are those subcubes(groups) which cover atleast one minterm that can’t be covered by any other
prime implicant. Essential prime implicants(EPI) are those prime implicants which always appear in final
solution.

Example:

3.Redundant Prime Implicants :

The prime implicants for which each of its minterm is covered by some essential prime implicant
are redundant prime implicants(RPI). This prime implicant never appears in final solution.

Example:
4.Selective Prime Implicants :

The prime implicants for which are neither essential nor redundant prime implicants are
called selective prime implicants(SPI). These are also known as non-essential prime implicants. They may
appear in some solution or may not appear in some solution.

Example:

6.Don‘t care combinations :

⮚ The “Don't Care” conditions allow us to replace the empty cell of a K-Map to form a grouping of
the variables. While forming groups of cells, we can consider a “Don't Care” cell as either 1 or 0 or
we can simply ignore that cell. Therefore, “Don't Care” condition can help us to form a larger group
of cells.

⮚ In digital logic, a don't-care term (abbreviated DC, historically also known as redundancies,
irrelevancies, optional entries, invalid combinations, vacuous combinations,
forbidden combinations, or unused states).

⮚ A function assumes value 1 for some combinations and value 0 for other combinations.
7. Product of sum, Sum of products, simplifications:

⮚ Sum of Products and Product of Sums. The different forms of canonical expression which includes
the sum of products (SOP) and products of the sum (POS), The canonical expression can be defined
as a Boolean expression which has either min term otherwise max term.

⮚ This method is useful when the number of variables two or three.

⮚ The k-map method are useful when we applied for four variables.

⮚ Each minterm is then converted to its equivalent binary number.

Sequential circuits
Flip-Flops :
Introduction

A flip flop is a stable device, that is, it can remain in one of the two stable states which
are designated as “0” and “1” states.
It is the fundamental logic circuit used for storing information in digital systems.
Different types of shift registers and counters are designed only using flip flops, which
can be built using NOR gates or NAND gates.
A flip flop has two outputs, one of which is the complement of the other. They are called
Normal and complement outputs.
A flip-flop is an basic memory element used to share one bit of information.
The basic difference between the various types of flip-flops is the number of inputs and
outputs.

Types of flip-flop :

1.R.S flip-flop
2.D flip-flop
3.J.K flip-flop
4.T flip-flop

9.RS Flip-Flop :(Reset – set)

⮚ The simplest type of flipflop is the reset-set flip flop,which is abbreviated as R-S flip flop.
⮚ Filp-flop are actually an application of logic gates.
Diagram :

A C
S Q

R B D Q’

RS Flip Flop

The above diagram shows an RS Flip Flop constructed with four NAND gates A, B, C and
D. It has two inputs S and R and two outputs Q and Q’. (The state of any flip-flop is known by
the state of a output only).

Truth table

Inpu Input(S) Output(Q) Output(Q’) comments

t (R)
0 0 1 0 Invalid
(or) not
allowed
0 1 1 0 Set
1 0 0 1 Reset
1 1 Qn Qn NC(No
change)

Step 1:
R=0 , S=0 means the value are not allowed so the output value is one.
Step 2:
R=0 ,S=1 means the Q value is 1
Q’ is an opposite to the Q
Step 3:
R=1,S=0 means the value is 0
Q’ value is 1
Step 4:
R=1 , S=1 means the status will not be change.

10. D Flipflop :

⮚ The D-type flip-flop is a modified Set-Reset flip-flop with the addition of an inverter to prevent the
S and R inputs from being at the same logic level.
⮚ The D of D-flip-flop stands for “data”.
⮚ D flip flop is very useful for temporary data storage.
 ⮚ It is modify over the R-S flip flop.
⮚ The D-type flip flop are constructed from a gated SR flip-flop with an inverter added between
the S and the R inputs to allow for a single D (Data) input.
⮚ It is also known as a Data Latch, Delay flip flop, D-type Bistable, D-type Flip Flop .

Circuit diagram :

⮚ Thus this single input is called the “DATA” input. If this data input is held HIGH the flip flop
would be “SET” and when it is LOW the flip flop would change and become “RESET”.
⮚ To avoid this an additional input called the “CLOCK” or “ENABLE” input is used to isolate the
data input from the flip flop’s latching circuitry after the desired data has been stored.
⮚ The “D flip flop” will store and output whatever logic level is applied to its data terminal so long as
the clock input is HIGH.
Truth table :

Clk D Q Q Description

Memory
↓»0 X Q Q no change

↑»1 0 0 1 Reset Q » 0
 ↑»1 1 1 0 Set Q » 1

Note that: ↓ and ↑ indicates direction of clock pulse as it is assumed D-type.

11. JK flip flop :

⮚ The JK Flip Flop is the most widely used flip flop. It is considered to be a universal flip-flop
circuit. The sequential operation of the JK Flip Flop is the same as for the RS flip-flop with the
same SET and RESET input.
⮚ Jk flip flop is otherwise called as positive edge triggered flip flop.
⮚ The JK flipflop is the improved or modified form of the RS flipflop.

Circuit Diagram :
 Truth table

Input Input(K Output(Q) Output(Q’) comments

(J) )
0 0 Qn Qn No change
0 1 0 1 Reset
1 0 1 0 Set
1 1 Qn Qn Toggle

12. T - Flip flop :

⮚ The name T flip-flop is termed from the nature of toggling operation.

⮚ The major applications of T flip-flop are counters and control circuits.

⮚ T flip flop is modified form of JK flip-flop

⮚ Whenever the clock signal is LOW, the input is never going to affect the output state. The clock
has to be high for the inputs to get active.

⮚ A flip-flop is a device which stores a single bit (binary digit) of data; one of its two states represents
a "one" and the other represents a "zero".

Circuit diagram :
In the above diagram they are using four NAND gates and there are two outputs Q and Q’.
Additionally hear we have Clk pulse and input is given as T.
Truth table :

13.Multiplexers :
14. Demultiplexers

15.Decoder :

⮚ The decoder is used to decode the binary information in a digital system.

⮚ A decoder is a combinational logic circuit which converts an n-bit binary input code into a
maximum of 2n unique outputs.
⮚ A decoder has several output lines and control input lines. Based on the value of the control input
(or select input), one of the output lines will become active. If there are four control input lines, then
the decoder can have up to a maximum of sixteen (2 power 4) output lines. The decoder is generally
used to select one among the many devices. It is widely used as address decoder in a computer
system.
Example :
Figure shows a simple decoder with two control inputs and four outputs.
A B

G0 Y0

G1 Y1

G2 Y2

G3 Y3

⮚ In above decoder allows 2 inputs and produce 4 outputs.

⮚ Hear the above circuit connected 2 inverters and 4 AND gates.

⮚ The input as A,B and produced output as a y1,y2,y3,y4.

16 . Encoder :
⮚ A binary encoder encodes information from 2N inputs into an N-bit code. Exactly one of the input
signals should have a value of 1.A priority encoder is an encoder where more than one input can be
activated .
⮚ In general an encoder is a device or process that converts data from one format to another.
⮚ The purpose of encoder is controlling motion parameters such as speed ,
rate,direction,distance,position.
⮚ Encoding information is just reverse process of decoding
⮚ Encoding involves changing decimal signals to equivalent binary signals.

16.1 Octal to binary encoder :

⮚ The octal-to-binary encoder consists of eight inputs, one for each of the eight digits, and three
outputs that generate the corresponding binary number. It is constructed with OR gates .

16.2 Decimal to BCD encoder :

⮚ A decimal to BCD (binary coded decimal) encoder is also known as 10-line to 4-line encoder. It
accepts 10- inputs and produces a 4-bit output corresponding to the activated decimal input.

Limitations With Decimal To BCD Encoder:

A decimal to bcd encoder has limitations similar to octal to binary encoder.

1. For 10 bits input, there can be 210 possible combinations, out of which only 10 are used using 4
output lines.
2. Only one input can be active at any given time.
17. Shift registers :

18.Counters:
⮚ Counter is a sequential circuit. A digital circuit which is used for a counting pulses is known
counter. Counter is the widest application of flip-flops. It is a group of flip-flops with a clock
signal applied.
⮚ A flipflop can store one bit information but counters can store more binary information.
⮚ The counters are used for counting the clock pulses in an application.
⮚ A counter is a device which can count any particular event on the basis of how many times the
particular event(s) is occurred.
⮚ In a digital logic system or computers, this counter can count and store the number of time any
particular event or process have occurred, depending on a clock signal.
⮚ Most common type of counter is sequential digital logic circuit with a single clock input and
multiple outputs. The outputs represent binary or binary coded decimal numbers. Each clock pulse
either increase the number or decrease the number.

Counters are of two types.

● Asynchronous or ripple counters.

● Synchronous counters.
18.1 Asynchronous or ripple counters :

⮚ Asynchronous counters are sometimes called ripple counters because the data appears to
“ripple” from the output of one flip-flop to the input of the next.
⮚ They are simple and easy to design by Toggle flip flop or D flip flop.
⮚ They can be used in low speed circuits.
⮚ They are most reliable because they use the same clock signal for all flip flops.

⮚ A n – bit binary ripple counter can count upto a maximum 2n status.

⮚ Ripple counter is a basic and simple counter.
⮚ Initially all filpflops are in logic state 0.
⮚ Q is a output of all filpflops.Initially all filpflops are in 0.
⮚ First a clock pulse is applied to the filpflop A only..which makes the output of first flipflop change
from 0 to 1 state

Example :
Q = Q3 Q2 Q1 Q0
0 0 0 1

18.2 Synchronous counters :

⮚ In synchronous counters, all flip flops are connected to the same clock signal and all flip flops will
trigger at the same time.Synchronous counters are also known as ' Simultaneous counters .
⮚ The Synchronous Counter, the external clock signal is connected to the clock input of EVERY
individual flip-flop within the counter so that all of the flip-flops are clocked together
simultaneously (in parallel) at the same time giving a fixed time relationship.
⮚ Synchronous counters are easier to design than asynchronous counters , are all clocked together at
the same time with the same clock signal. Due to this common clock pulse all output states switch
or change simultaneously.
 ⮚ It is very fast comparing asynchronous counters.

4 bit Synchronous UP Counter

⮚ The 4 bit up counter shown in below diagram is designed by using JK flip flop. External clock pulse
is connected to all the flip flops in parallel.

⮚ For designing the counters JK flip flop is preferred .

⮚ The inputs of first flip flop are connected to HIGH (logic 1), which makes the flip flop to toggle,
for every clock pulse entered into it.

⮚ So the synchronous counter will work with single clock signal and changes its state with each pulse.

⮚ The output of first JK flip flop (Q) is connected to the input of second flip flop.
⮚ The AND gates (which are connected externally) drives the inputs of other two flip flops .
⮚ The inputs of these AND gates , are supplied from previous stage flip flop outputs.

UNIT III
Input – Output Organization
1.Input – output interface :
⮚ Input output interface provides a method for transferring information between internal storage and external
I/O devices.
⮚ Input output interface connected to the peripheral devices.

1.1 Difference between the central computer peripheral device:

 Central computer Peripheral devices
This is an electronic devices Peripheral devices are electro
mechanical and electromagnetic
devices.
The data transfer is usually The data transfer is usually slower.
faster

⮚ Data codes and formats in peripherals differ from the word format in the CPU and memory.
⮚ The operating modes of peripherals are different from each other and each must be
controlled so as not to disturb the operation of other peripherals connected to the CPU.

There are two types of interface are available :

1.CPU interface
2.I/O interface
⮚ I/O interface depends on the input and output devices.
Main function of the I/O interface as
1.Data conversion - Converted digital to analog signal
2.Device selection – The selection of input output devices by CPU.
Interface :
It means to attach two (or) more components or systems.
It is used for the purpose of data transferring.
2.I/O Bus and Interface :
⮚ A typical communication link between the processor and several peripherals.

The I/O bus consists of Following 3 lines.

1. Data lines
2.Address lines
3.Control lines.
The I/O bus is a collection of wires.
Each peripheral devices associates with interface units.
The I/O bus from the processor is attached to all peripheral interfaces. To communicate with a
particular device, the processor places a device address on the address lines.
Each interface attached to the I/O bus.
2.1Input/Output commands :
There are 4 types of commands
1.control command
2.status command
3.Data input command
4.Data output command
1.control command
A control command is issued to activate the peripheral and to inform it what to do.
Example :
Keyboard
2.Status command:
A status command is used to test various status conditions in the interface and the peripheral.
3.Data input command:
The data input command is the opposite of the data output. In this case the interface receives an
item of data from the peripheral and places it in its buffer register.
4.Data output command:
A data output command causes the interface to respond by transferring data from the bus into one of
its registers.

3.I/O Bus Versus Memory Bus :

The I/O bus and memory bus contain following lines.

1. Dataline
2. Address line
3. Read/write control lines.
Three ways for computer buses that can be used to communicate with memory and I/O:

1. Use two separate buses, one for memory and other for I/O.
2. Use one common bus for both memory and I/O but have separate control lines for each.
3. Use one common bus for memory and I/O with common control lines.

Bus

● A bus is a set of wires connecting multiple modules (processor, memory, IO devices)

● A bus standard provides flexibility it can connect multiple devices from different manufacturers.
● But a bus may be a communications bottleneck.
● A bus may be synchronous or asynchronous.

Internal buses
The internal bus, also known as internal data bus, memory bus, system bus or front-side bus,
connects all the internal components of a computer, such as CPU and memory, to the motherboard.
Internal data buses are also referred to as local buses, because they are intended to connect to local
devices.
External buses
 The external bus, or expansion bus, is made up of the electronic pathways that connect the different
external devices, such as printer etc., to the computer.

1.Dataline:
A data bus can transfer data to the memory of a computer, or into or out of the central processing
unit (CPU) that acts as the device's "engine." A data bus can also transfer information between two
computers.
2.Address line :
An address line usually refers to a physical connection between a CPU/chipset and memory. They
specify which address to access in the memory.
The address bus carries addressing signals from the processor to memory.
3. Read/write control lines:
These control lines running through the data buses and also having control signals, when a DMA
controller places a Bus request input (BR) to CPU and to take the control the over Buses.

4.Isolated Versus Memory :

⮚ Many computers use one common bus to transfer information between memory or I/O and
the CPU. The distinction between a memory transfer and I/O transfer is made through
separate read and write lines.

⮚ The I/O read and I/O writes control lines are enabled during an I/O transfer.

⮚ The memory read and memory write control lines are enabled during a memory transfer.

4.1 Isolated I/O :

⮚ In the isolated I/O configuration, the CPU has distinct input and output instructions and each
of these instructions are associated with the address of an interface register.

⮚ When the CPU fetches and decodes the operation code of an input or output instruction, it
places the address associated with the instruction into the common address lines.

⮚ At the same time, it enables the I/O read (for input) or I/O write (for output) control line.

4.2 Memory mapped I/O :

⮚ Memory-mapped I/O uses the same address space to address both memory and I/O devices

⮚ Both have same address space

⮚ Same instructions can control both I/O and Memory.
⮚ Normal memory address are for both.
⮚ Lesser efficient.
⮚ Smaller in size.
⮚ Simpler logic is used as I/O is also treated as memory only.
Advantage :

Load and store instructions used for reading and writing from memory can be used to input
and output data from I/O registers.

5.Difference between Isolated I/O and Memory I/O :

Isolated I/O Memory mapped I/O

Isolated I/O device have separate Memory mapped I/O device
address space have same address space.
It allocates the address space of It allocates the address space
1mb for memory of less than 1 mb for
memory
Separate instruction are No separate instructions
required. are required.
Isolated I/O use separate Memory mapped I/O uses
memory space. memory from main
memory.
Efficient I/O operation due to Inefficient operation due to
separate bus. simple bus.
Use complex internal logic Common internal logic for
memory and I/O devices
Slower operation Faster operation
The device of I/O are treated in a The device of I/O are treated
separate domain as compared to as a part of the memory
memory. only.

6.Example of I/O Interface :

⮚ Input Output Interface provides a method for transferring information between internal storage and
external I/O devices.
⮚ The main purpose of the I/O interfaces is to transmit and receive data; however, the portion
designated as an I/O interface may contain additional resources, such as voltage translators,
registers, impedances, and buffers.
⮚ It consists of two data registers called ports, a control register, a status register, bus buffers and
timing and control circuits.
⮚ The interface communicates with the CPU through the data bus.
⮚ The I/O read and write are two control lines that specify an input or output respectively.
⮚ The four registers communicate directly with the I/O device attached to the interface.

⮚ The I/O datas can be transferred into either port A or B.

⮚ The chip select and register select used to determine the address assigining to interface.

⮚ The I/O read and I/O write specifies an input and output datas.

⮚ The control register receives control information from the CPU.

⮚ By loading appropriate bits into the control register, the interface and the I/O device attached
to it can be placed in a variety of a operating modes.

⮚ The interface register communicate with the CPU through the bidirectional data bus.

⮚ The interface register select the address and assigned to its registers.

⮚ The CPU transfer binary information to the selected register to the data bus.
 Asynchronous data transfer
7.Strobe Control and Handshaking :

7.1Introduction :
The internal operations in a digital system are synchronized by means of clock pulses
supplied by a common pulse generator. If the interface registers and CPU shares a common
clock, the transfer is said to be synchronous.

Clock pulses are applied to all registers within a unit and all data transfers among internal
registers occur simultaneously during the occurrence of a clock pulse.
Methods

Asynchronous data transfer between two independent units requires that control signals
be transmitted between the communicating units to indicate the time at which data is being
transmitted. Two ways of achieving this,
1. Strobe control
2. Handshaking

Strobe transfer 🡪 data transfer between CPU and an interface unit.

Handshaking 🡪 data transfer between an interface and an I/O device.

7.2 Strobe Control :

⮚ A strobe is a single line that informs the destination unit when a valid data
its available in the bus.

⮚ The strobe control method transfer the data in a single line.

⮚ The strobe control may be activated by anyone of the following method.

1.Source initiated strobe for data transfer

2.Destination initiated strobe for data transfer

7.3 Source initiated strobe for data transfer :

⮚ A data transfer initiated by the destination unit activates the strobe pulse informing the source to
provide the data.
⮚ The source unit responds by placing the requested binary information on the data bus.
⮚ The strobe pulse is actually controlled by the clock pulse in the CPU. The CPU is always in control
of the buses and informs the external units how to transfer data.
⮚ The data bus carries the binary information from source unit to the destination unit.
Typically, the bus has multiple lines to transfer an entire byte or word. The strobe is a single
line that informs the destination unit when a valid data word is available in the bus.
 ⮚ The source unit first places the data on the data bus.

⮚ Actually, the source does not have to change the information in the data bus.

⮚ The fact that the strobe signal is disabled indicates that the data bus does not contain valid
data. New valid data will be available only after the strobe is enabled again.

7.4 Destination initiated strobe for data transfer :

The destination unit receiving the data response with another signal is known as handshaking.

⮚ In this case destination unit activates the clock pluse.

⮚ Destination informing the source to provide the data.
7.5 Handshaking :
⮚ The agreement between two independent units is called handshaking.
⮚ Two control lines are used between two independent units.

1.Source initiated transfer using handshaking

2.Destination initiated transfer using handshaking
Two handshaking lines are,

Data valid 🡪 generated by source unit.

Data accepted 🡪 generated by destination unit.

7.6 Source initiated transfer using handshaking

⮚ Data valid line is generated by the source unit.

⮚ Data accepted by destination unit.
⮚ The timing diagram shows the exchange signals between the two units.
⮚ The source unit transfer by the valid data into two destination unit.
⮚ The source unit disables its data valid signal.
⮚ The destination unit then disables its data accepted signal and then finally the system goes to initial
stage.
7.7 Destination initiated transfer using handshaking :

⮚ The datas are available in the data bus.

⮚ The destination unit is ready to accept the datas.
⮚ Accept the data from the databus.
Disable the connection.

Advantages :

The handshake scheme provides high degree of flexibility and reliability because the
successful completion of a data transfer relies on active participation by both units.
 UNIT IV

1.Priority Interrupt :
⮚ Data transfer between the CPU and I/O devices.
⮚ The CPU cannot start the transfer unless the device is ready to communicate with the CPU.
⮚ A priority interrupt is a system that establishes a priority over the various sources to destination
which condition is to be serviced first when two or more requests arrive simultaneously.

⮚ When two devices interrupt the computer at the same time, the computer services the device,
with the higher priority first.

⮚ Establishing the priority of simultaneous interrupt can be done by software or hardware.

Polling :
⮚ A polling procedure is used to identify the highest-priority source by software means. In this
method there is one common branch address for all interrupts.
⮚ The program that takes care of interrupts begins at the branch address and polls the interrupt
sources in sequence.
⮚ The order in which they are tested determines the priority of each interrupt.
⮚ The highest-priority source is tested first Otherwise the next- lower priority source is tested
and so on.
⮚ The disadvantage of the software method is that if there are many interrupts, the time
required to poll them can exceed the time available to service the I/O device. In this situation
a hardware priority- interrupt unit can be used to speed up the operation.
⮚ Hardware priority-interrupt accepts interrupt requests from many sources, determines which of
the incoming request has the highest priority and issues an interrupt request to the computer based
on this determination.

2.Daisy Chaining Priority :

⮚ The daisy chaining method of establishing priority consists of a serial connection of all
devices that request an interrupt.
⮚ The device with the highest priority is placed in the first position, followed by lower priority
devices up to the device with the lowest priority, which is placed last in the chain.
⮚ This method of connection between these devices and the CPU is known as daisy chain
priority interrupt.

Diagram
 ⮚ The interrupt request line is common to all devices and forms a wired logic connection.
⮚ If any device has to interrupt signal in the low- level state, the interrupt line goes to the low- level
state.
⮚ When no interrupts are pending, the interrupt line stays in the high- level state.
⮚ This signal is received by device 1 at its PI (Priority In) input. The acknowledge signal passes on to
the next device through the PO (Priority out) output only if device 1 is not requesting an interrupt. If
device 1 has a pending interrupt, it blocks the acknowledge signal from the next device by placing a
0 in the PO output.
⮚ A device with a 0 in its PI input generates a 0 in its PO output to inform the next- lower- priority
device that the acknowledge signal has been blocked.
⮚ The daisy chain arrangement gives the highest priority to the device that receives the interrupt
acknowledge signal from the CPU.

3.Parallel Priority Interrupt :

⮚ The parallel priority interrupt method uses a register.

⮚ Priority is established according to the position of the bits in the
register.
⮚ The circuit may include a mask register.
⮚ The purpose is to control the status of each interrupt request.

⮚ The mask register can be programmed to disable lower priority interrupts while a higher
priority device is being serviced. It can also provide a facility that allows a high priority
device to interrupt the CPU while a lower priority device is being serviced.
 ⮚ An interrupt register whose indivual bits are set by external conditions and cleared by
program instructions.
⮚ The magnatic disk is a high speed device so disk having highest priority.
⮚ Printer has the next priority,followed by the character reader and keyboard.
⮚ Program instructions is possible to set or reset in the mask register.
⮚ The priority encoder generates two bits of vector addresses,which is transfer to the CPU such
as x and y.
⮚ Another output from the encoder sets an interrupt status in IST.
⮚ IEN is cleared by the program to provide an overall control over the interrupt system.
Priority Encoder :
⮚ The priority encoder is a circuit.
⮚ The logic of priority encoder is if 2 or more inputs arrive at the same time,which input
having the highest priority will precedence.
 Direct Memory Access
4.DMA Controller:(Direct Memory Access)
⮚ The transfer of data between a fast storage device such as magnetic disk and memory.
⮚ A DMA controller takes over the buses to manage the transfer directly between the
I/O device and memory.

1.Bus request(BR)
2.Bus grant(BG)
3.Burst transfer
4.Cycle stealing

Bus request(BR) :

⮚ The bus request (BR) input is used by the DMA controller to request the CPU to
control of the buses.

⮚ The CPU terminates the execution of the current instruction and read and write lines
into a high independent state.

Bus grant(BG) :

⮚ CPU activates the bus grant (BG) output to inform the external DMA.

⮚ When the DMA terminates the transfer it disables the bus request line.

Burst transfer :

⮚ In DMA burst transfer, a block sequence consisting of a number of memory words is

transferred in a continuous burst.

⮚ This mode of transfer is needed for fast devices such as magnetic disk.

Cycle stealing :

⮚ Cycle stealing allows the DMA controller to transfer one data word at a time.

⮚ This is the alternative method of burst transfer.

⮚ The word count register specifies the number of words that must be transferred. The
 data transfer may be close directly between the device and memory under control of
the DMA.

Diagram :

Block diagram of the DMA controller :

 ⮚ The unit communicates with the CPU via the data bus and control lines.

⮚ The RD (read) and WR (write) inputs are bi-directional. When the BG (bus grant)
input is 0, the CPU can communicate with the DMA registers through the data bus to
read from or write to the DMA registers.

⮚ When BG=1 the CPU can communicate directly with the memory by specifying an
address in the address bus and activating the RD or WR control. The DMA Controller
has three registers.

● 1.Address register
● 2.Word count register
● 3.Control register
ADDRESS REGISTER
Address register contains an address to specify the desired location in
memory.

WORD COUNT REGISTER

Word count register holds the number of words to be transferred.

CONTROL REGISTER
The control register specifies the mode of transfer.

5.DMA Transfer Input :

⮚ The CPU communicates with the DMA through the address and data buses.
⮚ The DMA has its own address, which activates the DS and RS lines.
⮚ The CPU initiates the DMA through the data bus.
Block diagram :
⮚ The CPU responds with its BG line.
⮚ Once the DMA receives the start control command ,it can start the transfer between
peripheral device and the memory.
⮚ The DMA initiates read (or) write signal.
⮚ When BG=0, the RD and WR are input lines allowing the CPU to communicate with the
internal DMA registers.
⮚ When BG=1 the RD and WR are output lines from the DMA controller to the random access
memory to specify the read or write operation for the data.
⮚ The peripheral unit can communicate with memory through the data bus.
⮚ For each word that is transferred, the DMA increments its address registers and
decrements its word count registers.
⮚ If the word count registers reaches zero, the DMA stops any further transfer and
removes its bus request. It also informs the CPU of the termination by means of an
interrupt.
⮚ A DMA controller may have more than one channel. In this case, each channel has a
 request and acknowledges pair of control signals, which are connected to separate
peripheral devices.
⮚ A priority among the channels may be established so that channels with high priority
are serviced before channels with high priority are serviced before channels with
lower priority.
⮚ DMA transfer is very useful in many applications.
⮚ It is used for fast transfer of information between magnetic disks and memory.

6.Input Output Processor:

Introduction :
⮚ The IOP is similar to a CPU.
⮚ It is designed to handle details of input and output processing.
⮚ Each IOP take care of input and output tasks.
⮚ IOP instructions are specifically designed to facilitate I/O transfer.
⮚ IOP can perform other processing also such as arithmetic, logic,branching and code
translation.

⮚ The memory unit occupies a central position and can communicate with each
processor by means of direct access memory.

⮚ The CPU is responsible for processing data needed in the solution of computational
tasks.

Block diagram :
 ⮚ The IOP provides a path for transfer of data between various peripheral devices and
the memory unit.

⮚ The CPU is usually assigned the task of initiating the I/O program.

⮚ In most computer system the CPU is the master while the IOP is a slave processor.

⮚ Commands are prepared by experienced programmers and store in the memory

⮚ The CPU informs the IOP where to find the commands in memory.

7. CPU-IOP Communication :
Introduction :
⮚ The communication between CPU and IOP may take different forms, depending on the
particular computer considered.
⮚ In most cases the memory unit acts as a message center where each processor leaves
information for the other.
⮚ The sequence of operations may be carried out as shown in the following flowchart.

Flow diagram for CPU-IOP Communication :

⮚ The CPU sends an instruction to test the IOP path.
⮚ The IOP responds by inserting a status word in memory for the CPU to check.
⮚ The memory address received with this instruction tells the IOP where to find its program.
⮚ The memory unit act as a message sender.
⮚ IOP response the inserting status word in the memory.
⮚ The CPU continue with another process,when the IOP is busy.
⮚ When the IOP terminates the execution of the program it send an interrupt request to the
CPU.
⮚ The CPU response the interrupt request.
 ⮚ The status word indicate the correct transfer the process will continued.
⮚ The IOP take care of all data transfer between I/O and memory.
⮚ The speed of most devices is much slower than the CPU.

UNIT IV
Memory Organization
1.Memory Hierarchy :
1.1 Introduction :
⮚ The memory unit is an essential component in any digital computer.
⮚ Small computer with a limited application may be able to fulfill its task,without need a
addition storage capacity.
⮚ The memory unit that communicates directly with a CPU is called the main memory.
Diagram :The components in a typical memory hierarchy

1.2 Multiprogramming :
Multiprogramming refers to the existence of many programs in different parts of
main memory at the same time.
For example, suppose a program is being executed in the CPU and the I/O transfer
is required. The CPU initiates the I/O transfer by using I/O processor. This leaves the
CPU free to execute another program.

The part of the operating system that supervises the flow of information between
 all storage devices is called “Memory Management System”. The memory management
system distributes program and data to various levels in the memory hierarchy.

They are
● Batch Mode
● Time sharing mode

In a Batch mode, each user prepares his program off- line and submits it to the
computer center. An operator loads all programs into the computer where they are
executed. The operator retrieves the printed output and returns it to the user.

In a time-sharing mode, many users communicate with the computer via remote
terminals. Because of slow human response compared to computer speeds, the computer
can respond to multiple users at, seemingly at the same time.

1.3 Auxiliary memory :

⮚ Devices that provide backup storage are called auxiliary memory.

⮚ The most common auxiliary memory device are,

o 1.Magnetic tapes
o 2.Magnetic disk

⮚ The above devices used for sharing system programs,large data files and other backup
information.

Magnetic tapes : It is used to store and remove files.

1.4 Cache memory :

⮚ A special very high speed memory is called cache memory.

⮚ It is used to increase the speed of processing.

1.5 Main memory :

⮚ It occupies a central position and able to communicate directly with the CPU.

2.Main Memory :
2.1 Introduction :
⮚ The main memory is the central storage unit in a computer system.
⮚ It is a relatively large and fast memory used to store programs and data during the computer
 operation. The principal technology used for the main memory is based on semiconductor
integrated circuits. Integrated circuit RAM chips are available in two possible operating
modes, static and dynamic.
⮚ The static RAM consists essentially of internal flip- flops that store the binary information.
⮚ The dynamic RAM stores the binary information.
⮚ The static RAM is easier to use and has shorter read and write cycles.
⮚ ROM is used for storing programs that are permanently.
2.2 RAM and ROM chips :

⮚ A RAM chip is better suited for communication with the CPU.

⮚ Another common feature is a bidirectional data bus that allows the transfer of data either
from memory to CPU during a read operation or from CPU to memory during a write
operation.
Diagram :
2.3 Bi-directional bus :
A bidirectional bus constructed with three possible states:
A signal equivalent to logic 1,
A signal equivalent to logic 0,
or high impedance state.
⮚ The logic 1 and 0 are normal digital signals.
⮚ The high impedance state behaves like an open circuit.
Explanation :
The capacity of the memory is 128 words of eight bits per word.
This requires a 7-bit address and an 8-bit bidirectional data bus.
The read and write inputs specify the memory operation.
The read and write inputs are sometimes combined into one line labeled R/W. When the chip
is selected, the two binary states in this line specify the two operations of read or write.

2.4 ROM chip :

A ROM chip is organized externally in a similar manner. However, since a ROM can only read, the
data bus can only be in an output mode.

⮚ RAM and ROM chip are connected to CPU through the data bus and address bus.
⮚ The selection between RAM and ROM is achieved through bus line 10. The RAMs are
selected when the bit in this line is 0 and the ROM when the bit is 1.
⮚ To select one of 128 possible bytes.

3.Associative memory:
1.Introduction
2.Hardware Organization
3.Match Logic
4.Read Operation
5.Write Operation.
3.1 Introduction :
⮚ Associative memory is also known as content addressable memory (CAM) or associative
storage or associative array.
⮚ This type of memory is accessed simultaneously and in parallel based on the data content
 rather than the specific address or location.
⮚ Memory is capable of finding empty unused space to store the word, or part of the word
specified.
⮚ The memory locates all words, which match the specified content, and marks them for
reading. Because of its organization, the associative memory is uniquely suited to do parallel
searches by data association.
⮚ Associative memories are used in applications where the search time is very critical and must
be very short
Applications of Associative memory :-
1. It can be only used in memory allocation format.
2. It is widely used in the database management systems, etc.
Advantages of Associative memory :-
1. It is used where search time needs to be less or short.
2. It is suitable for parallel searches.
3. It is often used to speedup databases.
4. It is used in page tables used by the virtual memory and used in neural networks.
Disadvantages of Associative memory :-
1. It is more expensive than RAM.
2. Each cell must have storage capability .
3.2 Hardware Organization :
⮚ Memory Organization in Computer Architecture, A memory unit is the collection of
storage units or devices together. The memory unit stores the binary information in the form
of bits.
⮚ Associative memory not accessed by address, it is accessed by the content. Whenever a word
is to be read from the associative memory, it's content or a part of that word is specified and
then all the words of the memory which match the specified content are marked for reading .

3.3 Match Logic :

 ⮚ The key register holds a mask that allows searching based on part of argument.
⮚ If a bit in the key register is 1, then the corresponding bit in the argument and each memory
word must be the same to be considered a match.
⮚ If a bit in the key register is 0, then the corresponding bit is considered a match whether or
not the argument and memory word are equal for that bit.
⮚ The match register, M, is m bits wide (could be huge), and will contain a 1 for each word
that matches the masked argument, and a 0 for each word that does not.
3.4 Read operation :
⮚ A memory unit stores binary information in groups of bits called words.
⮚ Data input lines provide the information to be stored into the memory, Data output lines
carry the information out from the memory.
⮚ The control lines Read and write specifies the direction of transfer data.
⮚ If more than one word in memory matches the unmasked argument field, all the
matched words will have 1’s in the corresponding bit position of the match register.
⮚ The matched words are read in sequence by applying a read signal to each word line
whose corresponding Mi bit is a 1.

⮚ If only one word may match the unmasked argument field, then connect output Mi directly to
 the read line in the same word position, the content of the matched word will be presented
automatically at the output lines and no special read command signal is needed.

⮚ Memory read operation transfers the desired word to address lines and activates the read
control line.

3.5 Write operation :

⮚ If the entire memory is loaded with new information at once, then the writing can be
done by addressing each location in sequence.
⮚ The information is loaded prior to a search operation.
⮚ If unwanted words have to be deleted and new words inserted one at a time, there is a
need for a special register to distinguish between active an inactive words. This
register is called “Tag Register”.

⮚ A word is deleted from memory by clearing its tag bit to 0.

4.Cache Memory:
1.Introduction
2.Associative Mapping
3.Direct Mapping
4.Set-associative Mapping
5.Writing into Cache Initialization.
4.1 Introduction :

⮚ A fast small memory is referred to as “Cache Memory”.

⮚ It is placed between the CPU and main memory

⮚ It is the faster component in the hierarchy and approaches the speed of CPU
components.

⮚ The performance of the cache memory is measured in terms of a quality called “Hit
Ratio”. When the CPU refers to memory and finds the word in cache, it produces a
hit. If the word is not found in cache, it counts it as a miss.
 ⮚ The ratio of the number of hits divided by the total CPU references to memory (hits +
misses) is the hit ratio.

⮚ The average memory access time of a computer system can be improved considerably
by use of cache.

⮚ When the CPU needs to access memory, the cache is examined. If it is found in the
cache, it is read very quickly. If it is not found in the cache, the main memory is
accessed.
The basic characteristic of cache memory is its fast access time. Therefore, very little or no
time must be fasted when searching for words in the cache.

The transformation of data from main memory to cache memory is referred to as

a “ Mapping Process ”.

There are three types of mapping procedures are available.

● Associative Mapping
● Direct Mapping
● Self – Associative Mapping.

Consider the following memory organization Figure.5.8 to show mapping procedures of the
cache memory.

Main Memory CPU

32k * 12 Cache Memory 512 * 12

● The main memory can stores 32k word of 12 bits each.

● The cache is capable of storing 512 of these words at any given time.
● For every word stored in cache, there is a duplicate copy in main memory.
● The CPU communicates with both memories
● If 1st sends a 15 – bit address to cache.
● If there is a hit, the CPU accepts the 12 bit data from cache
 ● If there is a miss, the CPU reads the word from main memory and the word is then
transferred to cache.

4.2 Associative mapping :

The associative mapping stores both the address and content (data) of the memory
word.
The diagram, given below shows 3 words presently stored in cache.
The address value of 15 bits it’s shown as a 5 digit octal number and its
corresponding 12 bits is shown as 4 digit octal number.

CPU Address (15

bits)

Argument register

Address Dat
a
01000 3450
02777 6710
22345 1234
Associative Mapping Cache (all numbers in octal)

The address – data pair is transform to the associative cache memory.

If the cache is full an address – data pair must be displaced.
The following two types of procedure are used replacement :
1.Replace cells of the cache
2.Round – robin order

4.3 Direct mapping :

⮚ In Direct mapping, assign each memory block to a specific line in the cache. If a line is
previously taken up by a memory block when a new block needs to be loaded, the old block
is trashed. An address space is split into two parts index field and a tag field.
⮚ Direct mapping maps each block of main memory into only one possible cache line.
 ⮚ The 15-bit CPU address is divided into two fields. The 9 least significant bits constitute the
index field and the remaining 6 bits form the tag fields.
⮚ The main memory needs an address but includes both the tag and the index bits. The cache
memory requires the index bit only i.e., 9.

a)Main memory
Memory address Memory data
1220

2340
3450

4500
5670
 6710
00000

00777
01000

01777
02000

02777

b) Cache memory
Index address Tag data

00 1220

02 6710

000
 777

⮚ In above diagram contains memory data and memory address

⮚ Memory data is an 4-bit octal number and memory address have an 5-bit octal
number.
⮚ Each datas in a cache consist of tag value.
⮚ The word at address zero is presently stored in the cache (index = 000, tag = 00, data
= 1220). The CPU now wants to access the word at address 0200. The index address
is 000. So it is used to access the cache. The two tags are then compared.

⮚ The cache tag is 00 but the address tag is 02, which does not produce match.
Therefore the main memory is accessed and the data word 5670 is transferred to CPU.

⮚ Index address 000 is then replaced with a tag of 02 and data of 5670. The direct
mapping uses a block size of 1 word or 8 words.

4.4 Set-associative memory :

In set – Associative mapping, each word of cache can store two or more words of memory
under the same index address. Each data word is stored together with its tag and the
number of tag – data items in one word of cache is said to form a set.
Index Tag Data Tag Data

01 3450 02 5670

02 6710 00 2340

000

777