COA

COMPUTER
ORGANIZATION AND
ARCHITECTURE
CS-09

PREPARED BY: DHVANI VYAS

COA
 COMPUTER ORGANIZATION AND ARCHITECTURE

1. Digital Logic Circuits

PREPARED BY:DHVANI VYAS Page 1

 COMPUTER ORGANIZATION AND ARCHITECTURE

Logic Gates
Binary information is represented in digital computers by physical quantities called signals. Electric
Signals such as voltages in a digital circuit are said to be at state 0 or state 1, depends on whether it
is 0V or 5V. Several other terms are used for the same like LOW, OFF, FALSE for 0 and HIGH, ON,
TRUE for level 1.

The manipulation of binary information is done by logic circuits called gates.

Digital Circuits are also called as Logic circuits, because each type of digital circuit obeys a certain set of
logic rules.

“Logic Gate, the fundamental building blocks of digital system, is an electronic circuit that manipulates the
binary information.”

Gate is the block of hardware that implements the logic operation like AND, OR, NOT and produces the 1
and 0 output signals depending on input signals supplied to them.

Logic Gates are digital circuits constructed using diodes, transistors and resistors in such a way that
their output is the result of a basic logic operation.

There are three categories of Logic Gate:

1. Basic Logic Gate

 AND Gate
 OR Gate
 NOT Gate

2. Universal Gate
 NAND Gate
 NOR Gate
3. Exclusive Gate
 XOR Gate
 XNOR Gate

Each Gate has:

 Name
 Graphic Symbol
 Its operation can be described by means of an Algebraic Expression.
 Truth Table

Truth Table

A table which lists all the possible combinations of the input variables and the corresponding outputs is
called Truth Table.

Truth tables help to understand the behavior of logic gates.

In Truth Table the input signals with all the possible input combinations are shown in the left column(s) of
the table and the output signals are shown in the right hand side column(s).

N Input Variables 2NCombinations (Minterms)

PREPARED BY:DHVANI VYAS Page 2

 COMPUTER ORGANIZATION AND ARCHITECTURE
Basic Logic Gates

AND Gate

 This operation is represented by a dot or by the absence of an operator.

 For example, x= A. B or x= A B is read as “A AND B is equal to x.”
 The logical operation AND is interpreted to mean that x = 1 if and only if A = 1 and B = 1;
otherwise x = 0.
 If all the Input signals are 1 then Output signal is 1, otherwise Output is 0.

Graphic Symbol:

Algebraic Expression:

x = A.B or x = AB x = A.B.C or ABC

Truth Table:

Two Input AND Gate Truth Table Three Input AND Gate Truth Table
A B x A B C x
0 0 0 0 0 0 0
0 1 0 0 0 1 0
1 0 0 0 1 0 0
1 1 1 0 1 1 0
1 0 0 0
1 0 1 0
1 1 0 0
1 1 1 1

OR Gate

 This operation is represented by a plus sign.

 For example, x= A + B is read “A OR B is equal to x,” meaning x = 1 if A = 1 or B =1 or both A =
1 and B = 1.
 If both A = 0 and B = 0 then x=0.
 If any single Input is 1 then the Output is 1, otherwise the Output is 0.

PREPARED BY:DHVANI VYAS Page 3

 COMPUTER ORGANIZATION AND ARCHITECTURE
Graphic Symbol:

Algebraic Expression:

x = A+B x = A+B+C

Truth Table:

Two Input OR Gate Truth Table Three Input OR Gate Truth Table
A B x A B C x
0 0 0 0 0 0 0
0 1 1 0 0 1 1
1 0 1 0 1 0 1
1 1 1 0 1 1 1
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 1

NOT Gate (Inverter)

 This operation is represented by a prime ( ' ) or bar ¯.

 For example x= A' or x=Ā is read “A not is equal to x,” means that x is what A is not.
 Here the output signal is complement of input signal.
 NOT gate is the invert of the input signal so it is called inverter.
 In other words, if A= 1, then x=0 but if A = 0 then x = 1.

Graphic Symbol:

Algebraic Expression:

x = A’ or x = Ā

PREPARED BY:DHVANI VYAS Page 4

 COMPUTER ORGANIZATION AND ARCHITECTURE

Truth Table:

Universal Logic Gates

NAND Gate:

 NAND means NOT AND, so the NAND gate is combination of AND gate and NOT gate
 It is complement of AND gate.
 If all the input signals are 1 then output signal is 0, otherwise the output is 1.

Graphic Symbol:

Algebraic Expression:

x = (AB)’ or x = AB

Truth Table:

Two Inp ut NAND Gate Tr uth Table Three Input NAND Gate Tru th Table
A B x A B C X
0 0 1 0 0 0 1
0 1 1 0 0 1 1
1 0 1 0 1 0 1
1 1 0 0 1 1 1
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 0

PREPARED BY:DHVANI VYAS Page 5

 COMPUTER ORGANIZATION AND ARCHITECTURE
NOR Gate

 NOR gate is combination of OR gate and NOT gate

 It is complement of OR gate.
 If all the input are 0 then output is 1, if any one input signal is 1 then output is 0.

Graphical Symbol:

Algebraic Expression:

x = (A+B)’ or x = A+B

Truth Table:

Two Input NOR Gate Truth Table Three Input NOR Gate Truth Table
A B X A B C X
0 0 1 0 0 0 1
0 1 0 0 0 1 0
1 0 0 0 1 0 0
1 1 0 0 1 1 0
1 0 0 0
1 0 1 0
1 1 0 0
1 1 1 0
Exclusive Gate
Exclusive-OR Gate (XOR Gate)

 If both the input signal are different then output signal is 1, otherwise output is 0.
 XOR operation is an Odd Function, i.e. its output is 1 if an odd number of inputs are 1.
 The graphic symbol of XOR Gate is similar to the OR gate except for the additional curved line
on the input side.

Graphic Symbol:

Algebraic Expression:

x =A  B or x = A’B + AB’

PREPARED BY:DHVANI VYAS Page 6

 COMPUTER ORGANIZATION AND ARCHITECTURE
Truth Table:

Two Input XOR Gate Truth Table Three Input XOR Gate Truth Table
A B x A B C X
0 0 0 0 0 0 0
0 1 1 0 0 1 1
1 0 1 0 1 0 1
1 1 0 0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 0
1 1 1 1
Exclusive-NOR Gate (XNOR)

 XNOR gate is combination of NOT gate and XOR gate.

 If both the input are equal then output is 1, otherwise output is 0.

Graphic Symbol:

Algebraic Expression:

x =A B = A ⊙ Bor x =A’B’+ AB

Truth Table:

Two Input XOR Gate Truth Table Three Input OR Gate Truth Table
A B x A B C x
0 0 1 0 0 0 1
0 1 0 0 0 1 0
1 0 0 0 1 0 0
1 1 1 0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 0

PREPARED BY:DHVANI VYAS Page 7

 COMPUTER ORGANIZATION AND ARCHITECTURE
The Logic Gates and their details are listed in the form of table below:

Boolean Algebra and Boolean Function

Boolean Algebra

 Boolean algebra is the algebra, developed in 1854 by George Boole.

 Boolean algebra is an algebra that deals with Binary Variables and Logic Operations.
 Combination of Boolean variables and Boolean operator for describing logical operation is
called Boolean algebra.

PREPARED BY:DHVANI VYAS Page 8

 COMPUTER ORGANIZATION AND ARCHITECTURE
Boolean Function

Boolean Function is an expression formed with Boolean variables, Boolean operators like + (OR), *(AND),
‘(NOT), parentheses and equal sign (=). Value of Boolean function (F) is either 1 or 0.

F= x + y’zLogic

Diagram

A circuit diagram used to show logical operations of given Boolean function using Logic Gates is called
Logic Diagram.

F = x + y’z

If
x=1
OR => F=1
y’z=1
y’=1 AND z=1
y=0 AND z=1

Truth Table for F = x + y’z

x y Z F
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 0
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 1

Logic Diagram
x
y y’ y’z F
z
The purpose of Boolean Algebra is to facilitate the analysis and design of digital circuits. It provides a
convenient tool to:

1. Express in algebraic form a Truth Table relationship between binary variables.

2. Express in algebraic form the input-output relationship of logic diagram.
3. Find simpler circuits for the same function.

Axioms or Postulates

0.0=0 0+0= 0 0’ = 1
0.1=0 0+1= 1 1’ = 0
1.0=0 1+0= 1
1.1=1 1+1= 1

PREPARED BY:DHVANI VYAS Page 9

 COMPUTER ORGANIZATION AND ARCHITECTURE

Boolean Algebra Theorems (Rules)

AND Laws OR Laws

NULL Law A.0= 0 A+0=A
Identity Law A.1=A A+1=1
Idempotence Law A.A=A A+A=A
Complementation Law A . A’ = 0 A + A’ = 1
Complementation Law (A’)’ = A
Commutative Law AB = BA A+B=B+A
Associative Law A (BC) = (AB) C A + (B + C) = (A + B ) + c
Distributive Law A(B+C) = AB + AC A + BC = (A+B) (A+C)
Absorption Law A + AB = A A(A+B)=A
De Morgan’s Law (AB)’ = A’ + B’ (A + B)’ = A’ B’

Proof:

NULL Law Identity Law

A.0 = 0 A+0 = A A.1 = A A+1 = 1
A 0 A.0 A 0 A+0 A 1 A.1 A 1 A+1
0 0 0 0 0 0 0 1 0 0 1 1
1 0 0 1 0 1 1 1 1 1 1 1
Prove Proved Proved Prove

Idempotence Law Complementation Law

A.A = A A+A = A A.A’ = 0 A+A’ = 1
A A A.A A A A+A A A’ A.A’ 0 A A’ A+A’ 1
0 0 0 0 0 0 0 1 0 0 0 1 1 1
1 1 1 1 1 1 1 0 0 0 1 0 1 1

Prove Proved Prove Prove

Commutative Law Complementation Law

A.B = B.A A+B = B+A (A’)’ = A
A B A.B B.A A B A+B B+A A A’ (A’)’
0 0 0 0 0 0 0 0 0 1 0
0 1 0 0 0 1 1 1 1 0 1
1 0 0 0 1 0 1 1
1 1 1 1 1 1 1 1 Proved

Prove Prove

PREPARED BY:DHVANI VYAS Page 10

 COMPUTER ORGANIZATION AND ARCHITECTURE
Absorption Law
A + AB = A A(A+B)=A
A B A.B A+AB L.H.S. = A+AB A B A+B A(A+B) L.H.S. = A(A+B)
0 0 0 0 =A(1+B) 0 0 0 0 =A.A + A.B
0 1 0 0 =A ( x+1=1) 0 1 1 1 =A + A.B ( x.x=x)
1 0 0 1 = R.H.S. 1 0 1 1 =A(1+B)
1 1 1 1 1 1 1 1 =A ( x+1= 1)
=R.H.S.
Prove Prove

Associative Law
A(BC) = (AB)C A+(B+C) = (A+B)+C

A B C (BC) A(BC) (AB) (AB)C A B C (B+C) A+(B+C) (A+B) (A+B)+C

0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 1 1 1 0 1
0 1 0 0 0 0 0 0 1 0 1 1 1 1
0 1 1 1 0 0 0 0 1 1 1 1 1 1
1 0 0 0 0 0 0 1 0 0 0 1 1 1
1 0 1 0 0 0 0 1 0 1 1 1 1 1
1 1 0 0 0 1 0 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1
Proved Proved

Distributive Law
A(B+C) = AB+AC A+BC = (A+B)(A+C)

A B C (B+C) A(B+C) AB AC AB+AC A B C BC A+BC (A+B) (A+C) r.h.s.

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 0 0 0 0 0 0 1 0 0 0 1 0
0 1 0 1 0 0 0 0 0 1 0 0 0 1 0 0
0 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1
1 0 0 0 0 0 0 0 1 0 0 0 1 1 1 1
1 0 1 1 1 0 1 1 1 0 1 0 1 1 1 1
1 1 0 1 1 1 1 1 1 1 0 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Proved Proved

Prove the following Laws by using Boolean Algebra

Distributive Law
A+BC = (A+B) (A+C)

R.H.S. = (A+B) (A+C)

= AA+AC+BA+BC
= A+AC+BA+BC
= A (1+C+B) + BC
= A+BC (Identity Law)
= L.H.S.

PREPARED BY:DHVANI VYAS Page 11

 COMPUTER ORGANIZATION AND ARCHITECTURE
De Morgan’s Theorems

 DeMorgan's theorem is very useful in dealing with NOR and NAND gates.
 It allows ANDs to be exchanged with ORs by using inverters.
 DeMorgan's Theorem can be extended to any number of variables.

Remember: “Break the bar, change the operator”

Theorem 1:
(x + y)’ = x’.y’

The complement of the sum of two Boolean variables is equal to the products of the complements of
these two variables. Proved

x y x + y (x+y)’ x’ y’ x’ . y’

0 0 0 1 1 1 1

0 1 1 0 1 0 0

1 0 1 0 0 1 0

1 1 1 0 0 0 0

Instead of representing a NOR gate with an OR graphic symbol followed by a circle, we can represent it
by an AND graphic symbol proceeded by circle in all inputs.

OR-Invert

Invert-AND

fig.1

It shows that the NOR gate is equivalent to bubbled AND gate.

Theorem 2:
(x y)’ = x’ + y’

The complement of the products of two Boolean variables is equal to the sum of the complements of
these two variables.

PREPARED BY:DHVANI VYAS Page 12

 COMPUTER ORGANIZATION AND ARCHITECTURE
Proved

x y x.y (x.y)’ x’ y’ x’ + y’

0 0 0 1 1 1 1

0 1 0 1 1 0 1

1 0 0 1 0 1 1

1 1 1 0 0 0 0

Instead of representing a NAND gate with an AND graphic symbol followed by a circle, we can represent
it by an OR graphic symbol proceeded by circle in all inputs.

AND-Invert

Invert-OR

fig.2

It shows that the NAND gate is equivalent to bubbled OR gate.

 NOR gate that perform the (x + y)’ function is equivalent to the function x’.y’
 Similarly, NAND gate can be expressed by (x y)’ or x’ + y’.
 For this reason the NOR & NAND gates have two distinct graphics symbols as shown in figure
1 & 2.

Complement of a Function

In the Boolean Algebraic form, the complement of the function can be derived by means of DeMorgan’s
theorem.

The general form of DeMorgan’s theorem can be expressed as follows:

(x1+x2+x3+..........+xn)’ = x1’x2’x3’ ......... xn’

(x1x2x3………..xn)’ = x1’+x2’+x3’+ .........+xn’

PREPARED BY:DHVANI VYAS Page 13

 COMPUTER ORGANIZATION AND ARCHITECTURE

A simple procedure for obtaining the complement of an algebraic expression is:

 Change all the ANDs to ORs and all the ORs to ANDs.
 Complement each of the individual variables.
For Example,
F = AB+C’D’+B’D

F’ = (AB+C’D’+B’D)’
= (AB)’(C’D’)’(B’D)’
= (A’+B’)(C+D)(B+D’)

Karnaugh Maps (K Map or Map Simplification)

 The expression may be simplified using the basic relations of Boolean Algebra.
 However, this procedure is sometimes difficult because it lacks specific rules for predicting
each succeeding step in the manipulative process.
 Karnaugh maps provide a useful method for simplifying an expression graphically.
 This is important because more complex expressions can be much hard to simplify using the
theorems of Boolean algebra.
 Karnaugh Map (K-map) is a very simple & straight forward method for simplifying Boolean
function.
 A Karnaugh map is a pictorial arrangement of the truth table which allows an easy
interpretation for choosing the minimum number of terms needed to express the function
algebraically. Karnaugh map is also known as K-map.

Minterm

The standard product terms at which the output is 1 or maximum is called Minterm, e.g. ABC or A.B.C.

Maxterm

The standard sum terms at which the output is 0 or minimum is called Maxterm, e.g. A+B+C.

 Each combination of the variables in a truth table is represented either by minterm or

maxterm.
 A Boolean Function is equal to 1 for some minterm and to 0 for others. The information
contained in a truth table may be expressed in the compact form by listing the decimal
equivalent of those minterms that produce 1 for the function. For example,
F(x,y,z)=∑(1,4,5,6,7), here the ∑ stands for the Sum of Minterms that follow the parantheses.
 The minterms that produce 1 for the function are listed in their decimal equivalent. The
missing minterms are the ones that produce 0 for the function.
 The K-map is a diagram made up of squares, with each square representing one minterm.
 The square corresponding to minterms that produce 1 for the given Boolean function are
marked by a 1 and the others are marked by a 0 or are left empty.
 The number of square in map of n variable is 2n.
 The 2nminterms are listed by an equivalent decimal number for easy reference.
 The squares corresponding to minterms that produce 1 for the function are marked by a 1
and the others are marked by a 0 or are left empty.
 By recognizing various patterns and combining squares marked by 1’s in the map, it is
possible to derive alternative algebraic expressions for the function, from which the most
convenient may be selected.
 The variable names are listed across both sides of diagonal line in the corner of the map.
 The minterm represented by a square is determined from the binary assignments of the
variables along the left and top edges in the map.

PREPARED BY:DHVANI VYAS Page 14

 COMPUTER ORGANIZATION AND ARCHITECTURE

The maps for functions of Two, Three, Four variables are shown in the following figures:

2-Variable K-Map 3-Variable K – Map

B BC B
B 0 1 11 10
00 01
A A
0 1 0 1 3 2
0 A’B’ A’B 0 A’B’C A’B’C A’BC A’BC’
2 3 4 5 7 6
A1 A 1
AB’ AB AB’C’ AB’C ABC ABC’

4-Variable K – Map

C
CD 00 01 11 10
AB 0 1 3 2
00 A’B’C’D A’B’C’D A’B’CD A’B’CD’

01 4 5 7 6
A’BC’D’ A’BC’D A’BCD A’BCD’
B
11 12 13 15 14
ABC’D’ ABC’D ABCD ABCD’
A
8 9 11 10
10
AB’C’D’ AB’C’D AB’CD AB’CD’

D
Octet:-
 The Octet is a group of eight 1’s that are horizontally or vertically adjacent.
 First we must find octet.

Quad:-
 A Quad is a group of four 1’s that are horizontally or vertically adjacent.
 If octet is not possible then we have to find Quads.
Pair:-
 A pair is a group of two 1’s that are horizontally or vertically adjacent.
 If quad is not possible then we have to find Pair.

The minterms of adjacent squares in the map are identical except for one variable, which appears
complemented in one square and uncomplemented in the adjacent square.

According to this definition of adjacency, the squares at the extreme ends of the same horizontal row
are also to be considered adjacent.

The same applies to the top and bottom squares of a column. As a result, the four corner squares of a
map must also be considered to be adjacent.

PREPARED BY:DHVANI VYAS Page 15

 COMPUTER ORGANIZATION AND ARCHITECTURE
Sum – of – Products Simplification (SOP)

 A Boolean Function represented by a truth table is plotted into the map by inserting 1’s in those
squares where the function is 1.
 The squares containing 1’s are combined in groups of adjacent squares.
 These groups must contain a number of squares that is an integral power of 2. That is 1, 2, 4, 8,
16…….
 Groups of combined adjacent squares may share one or more squares with one or more groups.
 Each group of squares represents an algebraic term, and the OR of those terms gives the
simplified algebraic expression for the function.
 The aim is to make minimum number of groups with maximum number of minterms.

 Groups may not include any cell containing a zero

 Groups may be horizontal or vertical, but not diagonal.

 Groups must contain 1, 2, 4, 8, or in general 2n cells.

 That is if n = 1, a group will contain two 1's since 2^1 = 2.
 If n = 2, a group will contain four 1's since 2^2 = 4.

PREPARED BY:DHVANI VYAS Page 16

 COMPUTER ORGANIZATION AND ARCHITECTURE
 Each group should be as large as possible.

 Groups may overlap.

 Groups may wrap around the table. The leftmost cell in a row may be grouped with the
rightmost cell and the top cell in a column may be grouped with the bottom cell.

PREPARED BY:DHVANI VYAS Page 17

 COMPUTER ORGANIZATION AND ARCHITECTURE
 There should be as few groups as possible, as long as this does not contradict any of the
previous rules.

Example of K-Map
1. Simplify Boolean function by using K – Map in sum of product.
F(x, y)=∑(0, 2, 3)

y 1
x 0
0 1 F(x, y) = y’+x

1 1 1

2. Simplify boolean function by using K – Map in sum of product.

F (A, B, C) =∑(0, 2, 4, 5, 6)

B
BC 00 01 11 10
A 1 1 F(A, B, C)=C’ + AB’
0
1 1 1
A 1

C
3. Simplify Boolean function by using K – Map in sum of product.
F (w,x,y,z) =∑(0, 1, 2, 6, 8, 9, 10)

C
yz 00 01 11 10
wx 1 1 F (w, x, y, z) = x’z’ + x’y’ +w’yz’
1
00

01 1

B
11
A
10
1 1 1

PREPARED BY:DHVANI VYAS Page 18

 COMPUTER ORGANIZATION AND ARCHITECTURE

4. Simplify boolean function by using K – Map in sum of product.

F(A,B,C,D) = A'B'C'+B'CD'+ A'BCD'+AB'C'

=A’B’C’D+A’B’C’D’+AB’CD’+A’B’CD’+A’BCD’+AB’C’D+AB’C’D’

C
CD 00 01 11 10
AB 1 F (A, B, C, D)= B’D’ + B’C’ + A’BC’
1 1
00
1
01

B
11
A
10 1
1 1

Product – of – Sums Simplification (POS)

 In the Boolean Expressions the sums are OR terms and the product denotes the ANDing of these
terms which results in Product – of – Sums form.
 The procedure for obtaining a Product – of – Sums expression follows from the basic properties
of Boolean Algebra.
 The 1’s in the map represent the minterms that produce 1 for the function.
 The squares not marked by 1 represent the minterms that produce 0 for the function.
 If we mark the empty squares with 0’s and combine them into groups of adjacent squares, we
obtain the complement of the function, F’ in SOP form.
 Taking the complement of F’ produces an expression for F in Product – of – Sums form.

F(A, B, C, D) = ∑(0, 1, 2, 5, 8, 9, 10)

C
Here for
CD 00 01 11 10 Minterm
AB 1 1 0 1 F(A, B, C, D) = ∑( 0, 1,
00 2, 5, 8, 9, 10)
Maxterm is given below,
01 0 1 0 0 Maxterm
F(A, B, C, D) = ∏(3, 4,
B
0 0 0 0 6, 7, 11, 12, 13, 14, 15)
11
D
A
0 1
10 1 1

PREPARED BY:DHVANI VYAS Page 19

 COMPUTER ORGANIZATION AND ARCHITECTURE
SOP Form: POS Form:
By grouping 1’s By grouping 0’s,

F = B’C’ + B’D’ +A’C’D F’ = AB + CD +BD’

F = (AB + CD + BD’)’
F = (AB)’ (CD)’ (BD’)’
F = (A’+B’) (C’+D’) (B’+D)

Logic diagrams of the two simplified expressions are shown in the following figure:

(a) Sum of Products: (b) Product of Sums:

F = B’D’+B’C’+A’C’D F = (A’+B’) (C’+D’) (B’+D)

B’ A’
D’ B’
F C’
C’ D’ F

A’
D D

Logic diagrams with AND and OR gates

Sum – of – Products can also be implemented with NAND gates as shown in the following Figure (a) and
the Product – of – Sums can also be implemented with NOR gates as in the following Figure (b).

Logic diagrams with NAND and NOR gates

(a) With NAND gates (b) With NOR gates

B’ A’
D’ B’

F C’
C’ D’ F

A’
D D

Don’t – Care Conditions

 In a K-map 1's and 0's are used to represent the minterms that make the function equal to 1 or
0.
 There are occasions when it does not matter if the function produces 0 or 1 for the given
minterm. Since the function may be either 0 or 1, we say that we don't care what the output
of the function is for this minterms.
 The minterms may produces either 0 or 1 for the function are said to be don't care conditions.
It is marked with 'X' in the K-map.

PREPARED BY:DHVANI VYAS Page 20

 COMPUTER ORGANIZATION AND ARCHITECTURE
 These Don’t care conditions can be used to provide further simplification of the algebraic
expression.
 When choosing adjacent squares for the function in the map, the X’s may be assumed to be
either 0 or 1, whichever gives the simplest expression.
For Example:
F (A, B, C) = ∑ (0, 2, 6)
d (A, B, C) = ∑ (1, 3, 5)

B
BC
00 01 11 10
A F = A’ + BC’
1 x x 1
0

A 1 x  1
C
With don’t care condition simplified expression is,

F = A’ + BC’

Represents the Boolean function

F (A, B, C) = ∑ (0, 1, 2, 3, 6)

Without don’t care condition the expression is,

F = A’C’ + BC’
So, if we consider don’t care terms then Boolean function can be more simplified.

Universal Gates

 Logic gates are used in the field of digital circuits, basic logic gates are AND, OR and NOT. It is
easy to prepare all the gates form NAND and NOR gates.
 There are two Universal Gates.
o NAND gate.
o NOR gate.
 Any digital circuit can be designed using only NAND or NOR gates. That is why ANAD and NOR
gates are known as Universal Gates.
 In practice, this is advantageous since NAND and NOR gates are economical and easier to
fabricate and are the basic gates used in all IC digital logic families.

By using NAND gate, we can construct all other gate as per the following.

 An AND gate can be replaced by NAND gates as shown in the figure.

Y = ((AB)’. (AB)’)’
Y = ((AB)’)’
Y = AB


PREPARED BY:DHVANI VYAS Page 21

 COMPUTER ORGANIZATION AND ARCHITECTURE


 An OR gate can be replaced by NAND gates as shown in the figure.

Y = (A’B’)’
Y = (A’)’ + (B’)’
Y=A+B

 A NOT gate can be replaced by NAND gates as shown in the figure.

Y = (A.A)’
Y = A’

 A NOR gate can be replaced by NAND gates as shown in the figure

Y = Y = ((A’B’)’(A’B’)’)’
Y = ((A’B’)’)’
Y = A’B’
Y = (A + B)’

 XOR gate can be replaced by NAND gates as shown in the figure

A A’
(A’B)’
B
Y = A B
A
(AB’)’
B B’

Y = ((A’B)’(AB’)’)’
Y = ((A’B)’)’ + ((AB’)’)’
Y = A’B + AB’
Y= AB

PREPARED BY:DHVANI VYAS Page 22

 COMPUTER ORGANIZATION AND ARCHITECTURE
 XNOR gate can be replaced by NAND gates as shown in the figure

A A’
(A’B)’
B Y = A B
Y = A⊙ B
A
(AB’)’
B B’

By using NOR gate, we can construct all other gate as per the following.

 An AND gate can be replaced by NOR gates as shown in the figure.

Y = (A’ + B’)’
Y = (A’)’(B’)’
Y = AB

 An OR gate can be replaced by NOR gates as shown in the figure.

Y = ((A + B)’ + (A + B)’)’

Y = ((A + B)’)’
Y=A+B

 A NOT gate can be replaced by NOR gates as shown in the figure.

Y = (A +A)’
Y = A’

PREPARED BY:DHVANI VYAS Page 23

 COMPUTER ORGANIZATION AND ARCHITECTURE
 An NAND gate can be replaced by NOR gates as shown in the figure.

Y = ((A’ + B’)’ + (A’ + B’)’)’

Y = ((A’ + B’)’)’
Y = (AB)’ (DeMorgan’s Theorem)

 An XOR gate can be replaced by NOR gates as shown in the figure.

Y = (((A’+B)’+ (A+B’)’)’+ ((A’+B)’+ (A+B’)’)’)’

Y = (((A’+B)’+ (A+B’)’)’)’
Y = (A’+B)’+ (A+B’)’
Y = AB’+A’B
Y=AB

 An XNOR gate can be replaced by NOR gates as shown in the figure.

Y = ((A’+B)’+(A+B’)’)’
Y = (A’+B) (A+B’)
Y = A’A+ A’B’+ AB+ BB’
Y = A’B’+ AB ( X.X’ = 0)
Y=A⊙B

PREPARED BY:DHVANI VYAS Page 24

 COMPUTER ORGANIZATION AND ARCHITECTURE
Logic Design
Digital

Combinational Sequential Circuits

Synchronous Asynchronous
Sequential Circuits Sequential Circuits

Combinational Circuits

A combinational circuit is a connected arrangement of the logic gates with a set of inputs and outputs.
At any given time, the binary values of the outputs are the function of the binary combination of the
inputs, e. g. Decoders, Encoders, Multiplexer, De multiplexer, Adder Circuits, etc.

n input Combinational m output

variables Circuit variables

A block diagram of combinational circuit

The n binary input variable come from an external source, the m binary output variable go to an external
destination and in between there is an interconnection of logic gates.

A combinational circuit transforms binary information from the given input data to the required output
data.

In digital computers the Combinational circuits are employed for generating binary control decisions and
for providing digital components required for data processing.

A combinational circuit can be described by a truth-table showing the binary relationship between the n
input variables & the m output variables.

Steps for Achieving Combinational Circuits

1. The Problem is stated
2. The Input and output variables are decided and assigned by letter symbols for ex. x, y, z, A, B,
C etc.
3. The truth table that defines the relationship between inputs and outputs is derived.
4. The simplified Boolean functions for each output are obtained.
5. The Logic Diagram is drawn using Boolean Functions.

Half Adder

The most basic digital arithmetic circuit is the addition of two binary digits.
A combinational circuit that performs the arithmetic addition of two binary bits is called a half adder.

The steps to design the Half Adder:

Step 1:
 A combinational circuit that performs the arithmetic addition of two-bit is called half adder.

PREPARED BY:DHVANI VYAS Page 25

 COMPUTER ORGANIZATION AND ARCHITECTURE

Step 2:
 The input variables of half adder are called the augends and addend bits whereas the output
variables produce the Sum and Carry bit.
 The two input variables are x and y and two output variables are S (Sum) and C (Carry).
 The block diagram of half adder is given below.

Step 3:
 The truth table of half adder is given below :

Step 4:
 The Boolean functions of two outputs Sum and Carry are obtained directly from the truth
table.

S = x’y + xy’ C = xy
=x y

Step 5:
 The logic diagram of half adder is given below.

=xy

 Half Adder consist of an XOR gate and an AND gate.

Full – Adder

The steps to design the Full Adder:

Step 1:
 A combinational circuit that performs the arithmetic addition of three bits is called full adder.
 It consists of three input variables and two output variables.
Step 2:
 Here we define the symbols for three input variables are x, y and z (Previous Carry)
respectively
 Here we define the symbols for output variables are S (Sum) and C (Carry).
 The binary variables S give the value of the least significant bit of the sum.

PREPARED BY:DHVANI VYAS Page 26

 COMPUTER ORGANIZATION AND ARCHITECTURE
 The binary variable C gives the output carry.
 The block diagram of full - adder is given below :

Step 3:
 The truth tableof full adder is given below :

Step 4:
 From the truth table of full adder,the output is 1 when the odd number of inputs are 1, S is an
ODD Function and represents the exclusive – OR relation of the three variables.

S = x’y’z +x’yz’ +xy’z’+xyz

S = x  y  z---------- (1)

K-Map for C(Carry)

According to K-Map
C= xy+yz+xz ----------- (2)

According to Truth Table

C = x’yz + xy’z+ xyz’ +xyz
= xy + (x’y+xy’) z
C = xy + (x  y) z ------- (3)

PREPARED BY:DHVANI VYAS Page 27

 COMPUTER ORGANIZATION AND ARCHITECTURE
Step 5:
 The logic diagram of full-adder using equation (1) and (2):

 The logic diagram of full-adder using equation (1) and (3)

Half Adder
Half Adder

Logic Diagram of a Full – Adder using two Half – Adders

Sequential Circuit

 A Sequential circuit is an interconnection of logic gates (Combinational Circuits) and Memory

elements (Flip- Flops). The memory elements are the devices capable of storing binary
information.
 The binary information stored in the memory elements at any given time defines the state of
the sequential circuits.
 The logic gate itself a combinational circuit, but when it included with the flip flops, the overall
circuit is known as sequential circuit, e.g. Counters, Registers.

PREPARED BY:DHVANI VYAS Page 28

 COMPUTER ORGANIZATION AND ARCHITECTURE

The block diagram of sequential circuit

 As shown in diagram, the combinational circuit block receives binary signals from external
inputs and from the outputs of flip-flops.
 The output of the combinational circuit goes to external outputs and to inputs of flip-flops.
 The gates in the combinational circuit determine the binary value to be stored in the flip-flop
after each clock transition.

Asynchronous Sequential Circuit

The behavior of an asynchronous sequential circuit depends upon the order in which its input signals
change and can be attached at any instant of time. The memory elements used in asynchronous
sequential circuits are time – delay devices.

Synchronous Sequential Circuit

The synchronous circuit is a system whose behavior can be defined from the knowledge of its signals at
discrete instants of time.

These circuits employ signals that affect the storage elements only at discrete instants of time.

Synchronization is achieved by a timing device called a clock pulse generator that produces a periodic
train of Clock Pulse.

The pulses are distributed throughout the system in such a way that storage elements are affected only
with the arrival of synchronization pulse.

Synchronous sequential circuits that use clock pulses in the inputs of memory elements are called
clocked sequential circuits.

The memory elements used in clocked sequential circuits are called flip – flops.

Clock Pulse

In the synchronous systems, the exact time at which any output can change states are determined by a
signal commonly called the Clock.

Flop – Flops

 The storage elements employed in clock sequential circuit are called Flip-Flops
 A flip-flop is a binary cell capable of storing one bit of information. It has two outputs one for
normal value and one for the complement value of the bit stored in it (Q, Q’).
 A flip-flop maintains a binary state until directly by a clock pulse to switch states.

PREPARED BY:DHVANI VYAS Page 29

 COMPUTER ORGANIZATION AND ARCHITECTURE
 The difference among various types of flip-flop is in the number of inputs they passes and in
the manner in which the inputs affect the binary state.
 Flip-flops can be either simple (transparent) or clocked; the transparent ones are commonly
called latches.
 The word latch is mainly used for storage elements, while clocked devices are described as
flip-flops.
 Latch is a level sensitive device while flip-flop is an edge sensitive device while flip-flop is an
edge sensitive device. Latches are faster than flip-flop and take less power.
 The Cross Coupled connection from output of one gate to input of another gate is known as
Feedback Path.
 The common types of flip - flop are given below :
o S-R Flip-Flop
o D Flip-Flop
o J-K Flip-Flop
o T Flip-Flop
o J-K Master Slave Flip-Flop

SR Flip-Flop

 The graphical symbol of the SR flip-flop is shown below :

S Q
C
Q
R
 SR flip-flop has three inputs, S represents Set state and R represents Reset state so it is called
Set- Reset flip-flop. C is for clock, there is an arrowhead – shaped symbol in front of the letter
C to designate a Dynamic Input, that denotes that the flip – flop responds to a positive
transition (from 0 to 1) of the input clock signal.
 SR flip-flop has two outputs, Q and Q'.
 In NOR gatewhen both the inputs are 0 then and then output is 1, otherwise output is 0
 Now assume that S=1 then Q’=0 and so that Q=1 (S=1,R=0 Set)
 Now S=0 and R=0 then the output remains same. (S=0,R=0  No Change)
 When R=1 and we get the output Q=0 and Q'=1, (S=0,R=1 Reset)
 When S=1 and R=1 we get the output for both Q and Q' to 0, it is in the Forbidden State or
indeterminate or invalid state. Because it can’t happen when Q and Q’ are complement to
each other.

Characteristic Table
S R Q (t+1)
0 0 Q(t) (No change)
0 1 0 (Reset)
1 0 1 (Set)
1 1 ? (Indeterminate)
Clocked SR Flip – Flop

PREPARED BY:DHVANI VYAS Page 30

 COMPUTER ORGANIZATION AND ARCHITECTURE
Characteristic Table
Q(t) S R Q (t+1) OR S R Q(t) Q (t+1)
0 0 0 0 0 0 0 0
0 0 1 0 0 0 1 0
0 1 0 1 0 1 0 0
0 1 1 Indeterminate 0 1 1 0
1 0 0 1 1 0 0 1
1 0 1 0 1 0 1 1
1 1 0 1 1 1 0 Indeterminate
1 1 1 Indeterminate 1 1 1 Indeterminate

D flip-flop

 The graphical symbol of D (Data) flip - flop is given below :

D
Q
C
Q

 The D (Data) flip - flop is a slight modification of the clocked SR flip-flop.

 A Clocked S-R flip-flop is converted to a D flip-flop by inserting an inverter between S and R
and assigning the symbol D to the single input.

Characteristic Table
D Q (t + 1)
0 0 (Clear to 0)
1 1 (Set to 1)

Characteristic Table
Q(t) D Q (t + 1)
0 0 0
Clocked D Flip – Flop 0 1 1
1 0 0
1 1 1

 From the characteristic table there are two cases.

1. When cp=0 we get no change state.
2. when cp=1 we construct Boolean function
Q (t+1) =D
Advantages of D flip flop is it uses a single input D and with No Forbidden State.
Disadvantage is that don’t generate No Change State.

The “no change” condition can be accomplished either by disabling the clock signal or by
feeding the output back into the input, so the clock pulses keep the state of the flip-flop
unchanged.

PREPARED BY:DHVANI VYAS Page 31

 COMPUTER ORGANIZATION AND ARCHITECTURE
JK flip-flop

 The graphical symbol of J-K flip-flop is given below :

J Q
C
Q
K
 The J-K flip-flop is refinement of the S-R flip-flop in that the Indeterminate condition of the S-R
type flip-flop is define in J-K type flip-flop.
 Input J and K behave like inputs S and R to set and clear the flip-flop, respectively.
Characteristic Table
J K Q (t+1)
0 0 Q(t) (No change)
0 1 0 (Reset)
1 0 1 (Set)
1 1 Q’(t) (Complement)

Clocked JK flip-flop

Characteristic Table
Q(t) J K Q (t+1) OR S R Q(t) Q (t+1)
0 0 0 0 0 0 0 0
0 0 1 0 0 0 1 0
0 1 0 1 0 1 0 0
0 1 1 1 0 1 1 0
1 0 0 1 1 0 0 1
1 0 1 0 1 0 1 1
1 1 0 1 1 1 0 1
1 1 1 0 1 1 1 0

 From the characteristic table

1) When J=0 & K=1 we get Q(t) No Change Condition
2) When J=0 & K=1 we get Q (t+1) =0. Reset
3) When J=1 & K=0 we get Q (t+1) =1. Set
4) When J=1 & K=1, instead of the indeterminate condition, we get the output of the flip-flop
to their complement state. Q (t+1) =Q’ (t)

PREPARED BY:DHVANI VYAS Page 32

 COMPUTER ORGANIZATION AND ARCHITECTURE
T Flip-flop

 The block diagram of T (Toggle) flip - flop is given below :

T Q
C
Q

 The T (Toggle) flip flop is obtained from a J-K flip-flop, when both inputs J and K are
connected to provide a single input designated by T.
Characteristic Table
T Q (t + 1)
0 Q(t) (No Change)
1 Q’(t) (Complement)

Characteristic Table

Q(t) T Q (t + 1)
0 0 0
0 1 1
1 0 1
1 1 0
 From the characteristic table
1) When T=0 output is Q(t)  No Change
2) When T=1 output is Q’(t)  Reset

Edge – Triggered Flip – Flops

The most common type of flip flop used to synchronize the state change during a clock pulse transition
is the edge triggered flip flop.

For achieving synchronization in a computer a timing device called a clock pulse generator is used, which
produces a periodic train of clock pulses.

The Fig – 1 shows a typical clock waveform. The clock waveform in Fig.1 (a) and Fig.1 (b)is called square
wave. The figure shows two important portions of a square wave: the Leading Edge or Rising Edge or
sometimes Positive – Going – Edge and the Falling Edge, or Negative – Going – Edge.

Most Flip – Flops respond to either (but not both) a Falling Edge or a Rising Edge. In effect, a system
which responds to Rising Edges of the clock ‘reset’ between such edges and changes state only when
such Positive – Going Edges occur.
Positive Going or
(a) Rising Edge of
the Signal
Negative Going
(b) (b) or Falling Edge
of the Signal
Fig. 1 Clock Waveforms

PREPARED BY:DHVANI VYAS Page 33

 COMPUTER ORGANIZATION AND ARCHITECTURE

Since clock signals are used to initiate flip – flop actions, a clock input is included on most flip – flops.
This input is marked with a small triangle, as shown in the following figure (a). It indicates that a flip –
flop can respond to the positive – edge of the clock signal.

If the flip – flop responds to a negative – edge of a signal, a bubble (inverter) is placed at the clock input,
as shown in the following figure (b)
(a) (b)

S Q S Q
C C
This symbol is Q Q
This symbol is
used for R used for Negative R
Positive – going – going – edge
– edge clocked clocked flip -
flip - flop flop

It is important to understand the above convention because most clocked flip-flop actually responds to a
change in clock input level, not to the level itself. This is shown in following figure (a) and (b).

The flip-flop is operated according to these rules:

1. If the S and R inputs are 0’s when the clock edge occurs, the flip – flop does not change states
but remains in its present state.
2. If S = 1 and R = 0, when the clock pulse (Positive/ Negative edge) occurs, the flip – flop goes to
the 1 state.
3. If S = 0 and R = 1, when the clock pulse occurs, the flip – flop is cleared to the 0 state.
4. Both the S and R inputs should not be 1’s when the clock signal’s Positive/ Negative Edge occurs.
Of course, nothing happens to the flip – flop’s state between occurrences of the Positive/
Negative pulses.

Fig. (a) Wave forms for positive edge – triggered

PREPARED BY:DHVANI VYAS Page 34

 COMPUTER ORGANIZATION AND ARCHITECTURE

Fig. (b) Wave forms for Negative edge – triggered

Master – Slave (pulse – triggered) Flip-flop

 Another type of flip flop used in some system is the master slave flip flop.
 This type of circuit consists of two flip flops. The first is the master, which responds to the
positive level of the clock, and the second is the slave, which responds to the negative level of
the clock.
 Master slave JK flip-flop contains two JK flip-flop one is called Master and the other is called
Slave.
 The output of the first JK flip-flop is given to the input in the second JK flip-flop
 When the clock pulse is high (positive transition), the master is active and give the output &the
slave is inactive.
 The master Set or Reset according to the state of the input signals.
 Since the slave is inactive during this period, its output remains steady at the previous state.
 When clock pulse goes low (negative transition), the master flip-flop is inactive & the slave is
active.
 The slave Set or Reset according to the state of the input signals.
 The final output Q of a master-slave flip-flop is the result of the output of the slave flip-flop
 And the output of the slave is available at the end of the clock pulse.

PREPARED BY:DHVANI VYAS Page 35

 COMPUTER ORGANIZATION AND ARCHITECTURE
Master – Slave Flip-flop Circuit

An Example of a Sequential Circuit

Two D flip-flops A and B, two inputs x and y, and one output y. the flip-flop input equations and the
circuit output are as follows:

DA = Ax + Bx
DB = A’x
y = x’(A + B)
Logic Diagram

PREPARED BY:DHVANI VYAS Page 36

 COMPUTER ORGANIZATION AND ARCHITECTURE
State Table

The behavior of a sequential circuit is determinedfrom the inputs, the outputs, and the state of its flip-
flops.

Both the outputs and the next state are a function of the inputs and the present state.

Sequential circuit is specified by a state table that relates outputs and next states as a function of inputs
and present states.
In clocked sequential circuits, the transition from present state to next state is activated by the presence
of a clock signal.

Present Input Next State Output

State
A B x A B y
0 0 0 0 0 0
0 0 1 0 1 0
0 1 0 0 0 1
0 1 1 1 1 0
1 0 0 0 0 1
1 0 1 1 0 0
1 1 0 0 0 1
1 1 0 1 0 0

State Diagram

The information available in a state table can be represented graphically in a state diagram. Here the
state is represented by a circle, and the transition between states is indicated by directed lines
connecting the circles.

The binary number inside each circle identifies the state of the flip-flops.

The directed lines are labeled with two binary numbers separated by a slash. The input value during the
present state is labeled first and the number after the slash gives the output during the present state.

PREPARED BY:DHVANI VYAS Page 37

 COMPUTER ORGANIZATION AND ARCHITECTURE

Characteristics
Analog Signal Digital Signal
Analog signal is a continuous signal
Digital signals are discrete time signals
Signal which represents physical
generated by digital modulation.
measurements.
Waves Denoted by sine waves Denoted by square waves
Uses continuous range of values to Uses discrete or discontinuous values to
Representation
represent information represent information
Human voice in air, analog electronic Computers, CDs, DVDs, and other digital
Example
devices. electronic devices.
Can be used in analog devices only.
Best suited for Computing and digital
Uses Best suited for audio and video
electronics.
transmission.
Applications Thermometer PCs, PDAs
Cost Low cost and portable Cost is high and not easily portable

Figure

PREPARED BY:DHVANI VYAS Page 38

 COMPUTER ORGANIZATION AND ARCHITECTURE

Characteristics
Analog Signal Digital Signal
Analog signal is a continuous signal
Digital signals are discrete time signals
Signal which represents physical
generated by digital modulation.
measurements.
Waves Denoted by sine waves Denoted by square waves
Uses continuous range of values to Uses discrete or discontinuous values to
Representation
represent information represent information
Human voice in air, analog electronic Computers, CDs, DVDs, and other digital
Example
devices. electronic devices.
Analog technology records waveforms Samples analog waveforms into a limited set
Technology
as they are. of numbers and records them.
Subjected to deterioration by noise
Data Can be noise-immune without deterioration
during transmission and write/read
transmissions during transmission and write/read cycle.
cycle.
Response to More likely to get affected reducing Less affected since noise response are
Noise accuracy analog in nature
Digital hardware is flexible in
Flexibility Analog hardware is not flexible.
implementation.
Can be used in analog devices only.
Best suited for Computing and digital
Uses Best suited for audio and video
electronics.
transmission.
Applications Thermometer PCs, PDAs
There is no guarantee that digital signal
Analog signal processing can be done
processing can be done in real time and
Bandwidth in real time and consumes less
consumes more bandwidth to carry out the
bandwidth.
same information.
Memory Stored in the form of wave signal Stored in the form of binary bit
Digital instrument drawS only negligible
Power Analog instrument draws large power
power
Cost Low cost and portable Cost is high and not easily portable
Impedance Low High order of 100 megaohm
Analog instruments usually have a
Digital instruments are free from
scale which is cramped at lower end
Errors observational errors like parallax and
and give considerable observational
approximation errors.
errors.

PREPARED BY:DHVANI VYAS Page 39

 COMPUTER ORGANIZATION AND ARCHITECTURE
2.Digital Component
INTEGRATED CIRCUIT
 Digital Circuits are constructed with integrated circuit.
 An integrated circuit(IC) is a small silicon semiconductor crystal called a chip containing the
Electronic component for the digital gates.
 The chip is mounted in a ceramic or plastic container & connections are welded by thin gold wires
to external pins to form the IC.
 As the technology of IC has improved, the number of gates that can be put in a single chip has
increased.

Levels of Integrations
There are following four different level of Integration depending on number of gates in a single package.

SSI [Small Scale Integration]

 SSI devices contain several independent gates in a single package.
 The number of gates is usually less than 10 and is limited by the number of pin available in the IC.
MSI [Medium Scale Integration]
 MSI devices have a complexity of approximately 10 to 200 gates in a single package.
 They perform specific elementary digital functions such as Decoders, Adder and Registers.
LSI [Large Scale Integration]
 LSI devices contain between 200 and few thousand gates in a single package.
 They include digital systems, such as Processors, Memory Chips and programmable modules.
VLSI [Very Large Scale Integration]
 VLSI devices contain thousands of gates within a single package
 Examples are large Memory Arrays and complex Micro-computer Chips.

Digital Logic Family

Digital Integrated Circuits are classified not only by their logic operation but also by the specific circuit
Technology to which they belong. The circuit Technology is referred to as a Digital Logic Family.

TTL [Transistor Transistor Logic]

 The previous technology DTL used Diodes and Transistors for the basic NAND gate.
 Later the diodes were replaced by transistors to improve the circuit operation and the name of the
logic family was change to TTL (Transistor - Transistor Logic)
 TTL is widespread logic family that has been operation for many years and is considered as
standard.
 The power supply voltage for TTL circuit is 5 volt. Here 0 is represented by 0 Volt and 1 is
represented by 3.5 volt.
ECL [Emitter Coupled Logic]
 It provides highest speed digital circuits in integrated form.
 It is used in systems such as super computer and signal processors where high speed is essential.
MOS [Metal Oxide Semiconductor]
 It uses unipolar transistor that depends on the flow of only one type of carrier, which may be
electrons or holes.
 PMOS:- MOS where holes are responsible for the flow of current.
 NMOS:-MOS where electrons are responsible for the flow of the current.
CMOS [Complementary Metal Oxide Semi Conductor]
 CMOS = PMOS+NMOS
 The CMOS technology uses PMOS and NMOS transistors connected in a complementary fashion in
all circuits.
 The most important advantages of CMOS over bipolar are the high packing density (The number of
devices or gates per unit area of an integrated circuit) of circuits, a simpler processing technique
during fabrication and a more economical operation because of low power consumption.

PREPARED BY:DHVANI VYAS Page 1

 COMPUTER ORGANIZATION AND ARCHITECTURE
DECODER
 A decoder is a combinational circuit that converts binary information from n input lines to a
maximum of 2n unique output lines.
 A decoder has n inputs and m outputs and is also referred to as n X m or n-to-m line decoder,
where m <= 2n.
 Their purpose is to generate the 2n or fewer binary combinations of the n input variables.
 This is used to convert Binary or BCD to Decimal.

(m <= 2n)

Block diagram of Decoder

2 – to – 4 line decoder
 A 2 – to – 4 line decoder with an enable input is constructed with AND Gates.
 The circuit operates when E equal to 1.
 From the truth-table, when E equal to 1 only one output is equal to 1 at any given time the other
outputs are equal to 0.
 The output whose value is equal to 1 represents the equivalent binary number in A1 and A0.
 The circuit is disabled when E is equal to 0, regardless of the values of the other two inputs.

Truth Table
Enable Inputs Outputs
E A1 A0 D0 D1 D2 D3
0 X X 0 0 0 0
1 0 0 1 0 0 0
1 0 1 0 1 0 0
1 1 0 0 0 1 0
1 1 1 0 0 0 1

Logic Diagram

Logic Diagram of 2 – to – 4 line decoder

PREPARED BY:DHVANI VYAS Page 2

 COMPUTER ORGANIZATION AND ARCHITECTURE
3 – to – 8 line Decoder
 The logic diagram of 3 X 8 decoder is shown in figure.
 This decoder has three input lines and eight output lines, hence it is known as 3 × 8 line decoder.
 It is also called binary to octal decoder because it takes a 3-bit binary input code & activates one
of the eight (octal) outputs corresponding to that code.

Logic Diagram of 3 x 8 line DECODER

Truth Table

Enable Inputs Outputs

E A2 A1 A0 D0 D1 D2 D3 D4 D5 D6 D7
0 X X X 0 0 0 0 0 0 0 0
1 0 0 0 1 0 0 0 0 0 0 0
1 0 0 1 0 1 0 0 0 0 0 0
1 0 1 0 0 0 1 0 0 0 0 0
1 0 1 1 0 0 0 1 0 0 0 0
1 1 0 0 0 0 0 0 1 0 0 0
1 1 0 1 0 0 0 0 0 1 0 0
1 1 1 0 0 0 0 0 0 0 1 0
1 1 1 1 0 0 0 0 0 0 0 1

 The three inputs A0, A1, A2 are decoded into 8 outputs.

 Each output representing one of the combinations of the 3 binary input variables.
 The three NOT Gates provide the complement of the inputs and each of the eight AND Gates
generates one of the binary combination.

PREPARED BY:DHVANI VYAS Page 3

 COMPUTER ORGANIZATION AND ARCHITECTURE
Enable input:
 Commercial decoders include one or more enable input to control the operation of the circuit.
 The decoder of 3 X 8 lines has one enable input E.
 The decoder is enabled when E is equal to 1, When the enable input E is equal to 0 i.e. Disabled,
all the outputs are equal to 0 regardless of the values of the others three data inputs. The three
x’s in the table designate Don’t Care conditions.
 When the enable input E is equal to 1, the decoder operates in a normal fashion.

Application
 Decoder is used whenever an output or a group of outputs is to be activated only on the
occurrence of a specific combination of input levels.
 Decoder is used to respond to the address code that is from central processor to activate the
memory storage location.

2 – to – 4 line decoder (using NAND gate)

 A 2 – to – 4 line decoder with an enable input constructed with NAND gate is shown in fig.
 The decoder is enabled when E is equal to 0 and disable when E is equal to 1.
 From the truth table, when the enable input E is equal to 0 only one output is equal to 0 at any
given time the other outputs are equal to 1.
 The output whose value is equal to 0 represents the equivalent binary number in A1 and A0.
 From the truth table, when the enable input E is equal to 1, all other outputs are equal to 1.
 The circuit is disabled when E is equal to 1, regardless of the values of the other two inputs. The
X’s in the table designate Don’t Care conditions.

Truth Table
Enable Inputs Outputs
E A1 A0 D0 D1 D2 D3
1 X X 1 1 1 1
0 0 0 0 1 1 1
0 0 1 1 0 1 1
0 1 0 1 1 0 1
0 1 1 1 1 1 0
Logic Diagram

Logic Diagram of 2 – to – 4 line NAND Gate decoder

PREPARED BY:DHVANI VYAS Page 4

 COMPUTER ORGANIZATION AND ARCHITECTURE
Decoder Expansion
 There are occasions when certain size of decoder is needed but only smaller sizes are available.
 When this occur it is possible to combine two or more decoder with enable input to form a large
decoder.
 Thus if 6-to-64 line decoder is needed, it is possible to construct it with four 4-to-16 line
decoders.
 Two 2-to-4 line decoders are combined to achieve a 3-to-8 line decoder.

Fig. A 3X8 decoder constructed with two 2X4 decoder

 The least significant bit (A0, A1) of input are connected to both decoders.
 The most significant bit (A2) is connected to the enable input of one decoder and through an
inverter to the enable input of the other decoder.
 It is assume that each decoder is enable when its E input is equal to 1, When E is equal to 0, the
decoder is disable and all its output are in the 0 level.
 When A2 = 0, upper decoder is enabled and lower decoder is disabled. The lower decoder
output becomes inactive with all outputs at 0.
 The output of the upper decoder generate outputs D0 through D3, depending on the values of
A1 and A0 (while A2=0).
 When A2 = 1, upper decoder is disabled and lower decoder is enabled. The lower decoder
generates outputs D4 through D7, depending on the values of A1 and A0.

ENCODER
 An Encoder is a device whose inputs are decimal digits and/ or alphabetic characters and whose
outputs are the coded representation of those inputs.
 An encoder is combinational logic circuit that performs reverse operation of decoder.
 Encoding is exactly opposite process of decoding. it’s a process of converting familiar numbers
into a coded format.
 An encoder has 2n (or less) inputs lines and n output lines.
 The output lines generate the binary code corresponding to the input value.
 An example of encoder is the octal-to-binary encoder.
 Decoders has numbers of output lines and at a time only one output of line is high while
encoder has numbers of input lines & only one of its activated (High) input at a given time.

(m <= 2n)
Block diagram of Encoder

PREPARED BY:DHVANI VYAS Page 5

 COMPUTER ORGANIZATION AND ARCHITECTURE
Octal – To – Binary Encoder
 It is also referred to as 8×3 encoder, because it has 8 input lines and 3 output lines.
 This circuit accepts 8 input lines & produces a 3-bit output code corresponding to the activated
input.
 It has eight inputs, one for each of the octal digits, and three outputs that generate the
corresponding binary number.
 Encoder can be implemented with OR gates whose inputs are determined directly from the truth
table.

Truth Table

Inputs Outputs
D0 D1 D2 D3 D4 D5 D6 D7 A2 A1 A0
1 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 1
0 0 1 0 0 0 0 0 0 1 0
0 0 0 1 0 0 0 0 0 1 1
0 0 0 0 1 0 0 0 1 0 0
0 0 0 0 0 1 0 0 1 0 1
0 0 0 0 0 0 1 0 1 1 0
0 0 0 0 0 0 0 1 1 1 1

From the truth table, output A0=1 if the input octal digit is 1 or 3 or 5 or 7.These condition can be
expressed by the following Boolean function.
 Output A0 = 1,if input octal is high i.e. 1, 3, 5 and 7, then A0 = D1+D3+D5+D7
 Output A1 = 1,if input octal digits are 2, 3, 6 and 7, then A1 = D2+D3+D6+D7
 Output A2 = 1,if input octal digits are 4, 5, 6 and 7,then A2 = D4+D5+D6+D7

Logic Diagram
D0
D1
D2
D3
D4
D5
D6
D7

A0 A1 A2

3 x 8 line ENCODER

MULTIPLEXER / DATA SELECTOR

 Multiplexer is a combinational circuit which receives binary information from 2n input data
lines and directs it to a single output line.
 The Selection of a particular input data line for the output is determined by a set of selection
inputs.
 A 2n - to -1 multiplexer has 2n input data & n input selection line for the 1 output.
 The data input which is transferred in the output is decided by n selection input line.

PREPARED BY:DHVANI VYAS Page 6

 COMPUTER ORGANIZATION AND ARCHITECTURE

Block Diagram of Multiplexer/ Many to one/ data selector

4 × 1 Multiplexer
 In 4 X 1 multiplexer, four data input I0 to I3 is applied to one input at an AND Gate. And the two
selection inputs S1 and S0 are decoded to select a particular AND Gate.
 The o/p at the AND Gate are applied to a single OR Gate to provide the single output.

Selection input { S0
S1
4X1
l0 MUX Y
l1
l2
l3

Block diagram of 4 X 1 Multiplexer

Logic Diagram

 A truth table describing the circuit needs 64 rows since six input variable can have 26 binary
combination this is excessively long table and will not be shown here.
 A more convenient way to describe the operation of multiplexer is by means of function table.

PREPARED BY:DHVANI VYAS Page 7

 COMPUTER ORGANIZATION AND ARCHITECTURE
Functional Table
Select Output
S1 S2 y
0 0 I0
0 1 I1
1 0 I2
1 1 I3
 When the selection inputs S1S0 are equal to 00, output y = I 0.
 When the selection inputs S1S0 are equal to 01, output y = I 1.
 When the selection inputs S1S0 are equal to 10, output y = I 2.
 When the selection inputs S1S0 are equal to 11, output y = I 3.

The Multiplexer is also called a Data Selector, since it selects one of many data inputs and steers the
binary information to the output.

Application

Multiplexer find numerous and varied applications like

 Data Selection
 Data Routing
 Operation Sequencing
 Parallel – to – Serial Conversion
 Waveform Generation
 Logic Function Generation.

Multiplexer Expansion (Quadruple Multiplexer)

 As in decoders, multiplexers may have an enable input to control the operation of the unit.
 The enable input is useful for expanding two or more multiplexers to a multiplexer with a larger
number of inputs.
 The selection and the enable inputs in multiple unit construction are usually common to all
multiplexers.
 The block diagram of a Quadruple 2 – to – 1 line multiplexer is shown in the following figure.

Enable E
Select S

A0 Quadruple
A1 2X1 Y0
A2 Multiplexers Y1
A3 Y2
Y3
B0
B1
B2
B3

Quadruple 2 – to – 1 line multiplexers

 The circuit has four multiplexer, each capable of selecting one of two input lines.
 Output Y0 can be selected to come from either input A0 or B0.
 Output Y1 may have the value of A1 or B1, and so on.
 One input selection line S selects one of the lines in each of the four multiplexers.

PREPARED BY:DHVANI VYAS Page 8

 COMPUTER ORGANIZATION AND ARCHITECTURE
DEMULTIPLEXER / DATA DISTRIBUTORS
 A demultiplexer is a combinational circuit in which it takes 1 input and distributes it over 2n
outputs.
 A single data input can be transferred on one at 2n output lines.
 This is also known as one to many demultiplexer or data distributor.

Block diagram of Demultiplexer

1 × 4 Demultiplexer
 The input data line (D) goes to all the AND Gates.
 The two select lines S1 and S0 enable only one gate at a time, & the data appearing on the input
line will pass through the selected gate to the associated output line.

Logic Diagram

Function Table

INPUT OUTPUT
S1 S0 Y0 Y1 Y2 Y3
0 0 D 0 0 0
0 1 0 D 0 0
1 0 0 0 D 0
1 1 0 0 0 D

PREPARED BY:DHVANI VYAS Page 9

 COMPUTER ORGANIZATION AND ARCHITECTURE

 From the truth table it is clear that when D =0, the outputs are zero regardless the values of
input S0 & S1.
 When D =1 & selection lines S1S0=00 then AND gate associated with Y0 gives high output and
Y1, Y2, & Y3 gives low output.
 When D =1 & selection lines S1S0=01 then AND gate associated with Y1 gives high output.
 When D =1 & selection lines S1S0=10 then AND gate associated with Y2 gives high output.
 When D =1 & selection lines S1S0=11 then AND gate associated with Y3 gives high output.

REGISTER
 Register consists of group of flip-flop and gates, where the flip-flop hold the binary information
& gates control when and how new information is transferred into the register.
 Register is a group of flip-flop with each flip-flop capable of storing 1 bit of information.
 An n-bit register has a group of n number of flip-flop and is capable of storing any binary
information of n bits.
 In addition to flip-flop, register may have combinational gates that perform data processing
tasks.
 Data may be available in parallel form or in serial form
o Multi-bit data is said to be in parallel form when all the bits are available
simultaneously.
o The data is said to be in serial form when the data bits appear sequentially i.e. one after
the other, at a single terminal.
 Register may output data either in serial form or in parallel form.

Register Load
The transfer of new information into a register is referred to as Loading the register.

Loading may be serial or parallel.

Serial Loading
In serial loading, data is transferred into the register in serial form, i.e. one bit at a time.

Parallel Loading
If all the bits of the register are loaded simultaneously with a common clock pulse transition, we say
that the loading is done in parallel.

Various types of register is as follows:

 Register with parallel load
 Shift register (serial-in, serial-out)

Buffer Registers (4 Bit Register)

 A simplest register is one that consists of only flip-flop without any external gates.
 The following figure shows such a register constructed with four D type flip- flop.
 The common clock input triggers all flip – flops on the rising edge of each pulse, and binary data
available at the four inputs (I0 through I3) are transferred into the 4-bit register.
 The four outputs can be sampled at any time to obtain the binary information stored in the
register.
 The clear input goes to a special terminal in each flip – flop. When this input goes to 0, all flip –
flops are reset asynchronously.

PREPARED BY:DHVANI VYAS Page 10

 COMPUTER ORGANIZATION AND ARCHITECTURE
Note
The clock signal enables the D input but that the clear input is independent of the clock.
Logic Diagram

l0 D Q A0
Clock
C

l1 D Q A1
C

l2 D Q A2
C

l3 D Q A3
C

Clear

 The clock pulse input, enable all the flip–flop & the inputs of the register load all four inputs I0
through I3 in parallel.
 In this configuration, the clock must be inhibited from the circuit in the content of the register
must be left unchanged.

4 – Bit Register with parallel load

 The master clock acts like a pump that supplies a constant beat to all parts of the system.
 A separate control signal must be used to decide whether the next pulse will accept new
information or leave the information in the register as it is.
 When the separate control signal, the load input is 1 then I inputs are transferred into the
register on the next clock pulse.
 When the load input is 0 the circuit input I0, I1, I2, I3 are inhibited & D inputs of the flip-flops are
connected to their outputs, thus maintaining the content of the register.

PREPARED BY:DHVANI VYAS Page 11

 COMPUTER ORGANIZATION AND ARCHITECTURE

 The feedback connection in each flip flop is necessary when a D type of flip flop is used because
D flip flop does not have nochange input condition.
 To leave the output unchanged, it’s necessary to make D input equal to the present Q output in
each flip flop.

PREPARED BY:DHVANI VYAS Page 12

 COMPUTER ORGANIZATION AND ARCHITECTURE
Shift Register (Serial in, Serial out):-

 A register is capable of shifting its binary information in one or both directions is called
shift register.
 The register capable of shifting its binary information in one direction only is called
unidirectional shift register.
 The logical configuration of a shift register consists of chain of flip- flop in cascade with the
output of one flip flop connected to the input of the next flip flop.
 The entire flip flop receives common clock pulse that causes the shift from one stage to the
next.
4 – bit unidirectional shift (Right) register

4 – bit unidirectional shift (Right) register

 These flip flops are connected in a cascade manner performing shift right operation.
 As shown above, it has four flip flop, thus it can store up to four bits of data that is applied
at the D input of the first flip flop.
 The Q output of the first flip flop is connected to the D input of the second flip flop , the Q
output of the second flip flop is applied to the input(D) of the 3rd flip flop & the Q o/p the
3rd flip flop is connected to the D input of the fourth flip flop.
 The clock is common to all the flip flops.
 The serial input determines what goes into the leftmost position during the shift.
 The serial o/p is from right most flip flop.

4 – bit unidirectional shift (Left) register

4 – bit unidirectional shift (Left) register

 These flip flops are connected in a cascade manner performing shift right operation.
 The serial input determines what goes into the rightmost position during the shift.
 The Q output of the 4th flip flop is connected to the D input of the 3rd flip flop , the Q
output of the 3rd flip flop is applied to the input(D) of the 2nd flip flop & the Q o/p the 2nd
flip flop is connected to the D input of the 1st flip flop.
 The serial o/p is from left most flip flop.
Application
Time Delay, Serial/ Parallel Data Conversion, Ring Counters, Universal Asynchronous Receiver
Transmmiter (UART)

PREPARED BY:DHVANI VYAS Page 13

 COMPUTER ORGANIZATION AND ARCHITECTURE
4 – bit Bidirectional Shift Register with Parallel Load

S0 S0
S1 D A0
S1
4X1 Q
MUX
Serial
Input
0
1
I0 2

S0
D A1
S1
4X1 Q
MUX
0
1
I1 2

S0
D A2
S1
4X1 Q
MUX
0
1
I2 2

S0
D A3
S
01 Q
4X1
1
MUX
2
Serial
Input
I3
Clock
4 – bit Bidirectional shift register with parallel load

 The register capable of shifting its binary information in both the directions (right & left)
is called bi-directional shift register.
 Most general shift register has all the capabilities listed below:
1. An input for clock pulses to synchronize all operations.
2. A shift-right operation and a serial input line associated with the shift-right.
3. A shift-left operation and a serial input line associated with the shift-left.
4. A parallel load operation and n input lines associated with the parallel transfer.
5. N parallel output lines.
6. A control state that leaves the information in the register unchanged even though
clock pulses are applied continuously.
 The above diagram consists of 4-D flip flop & 4X1 multiplexer.
 The two selection inputs S1 & S0 select one of the multiplexer data input for the D flip Flop
 The selection lines control the mode of operation of the register according to the following
function table.

PREPARED BY:DHVANI VYAS Page 14

 COMPUTER ORGANIZATION AND ARCHITECTURE
Function Table of bidirectional shift register

Mode Control
S1 S0 Register Operation
0 0 No change
0 1 Shift Right(down)
1 0 Shift left(up)
1 1 Parallel load
Circuit operations
 When the mode control S1S0 = 00, data input 0 of each multiplexer is selected. The condition
forms a path from the output of each flip-flop into the input of the same flip-flop. The next clock
transition transfers into each flip-flop the binary value it held previously and no change of state
occurs.
 When the control mode S1S0 = 01, the terminal marked 1 in each multiplexer has a path to the D
input of the corresponding flip-flop. This causes a shift-register operation, with the serial input
data transferred into flip-flop A0 and the content of each flip-flop Ai-1 transferred into flip-flop
Ai for i = 1, 2, 3.
 When the control mode S1S0 = 10, a shift left operation results, with the other serial input data
going into flip-flop A3 and the content of flip-flop Ai+1 transferred into flip-flop Ai for i = 0, 1, 2.
 When the control mode S1S0 = 11, the binary information from each input I0 through I3 is
transferred into the corresponding flip-flop, resulting in a parallel load operation.

Note
The way the diagram is drawn, the shift-right operation shifts the contents of the register in the down
direction while the shift left operation causes the contents of the register to shift in the upward
direction.

COUNTER
 A register that goes through a predetermined sequence of states upon the application of
input pulses called a counter.
 In short, it’s a register capable of counting the number of clock pulses that had arrived at
its clock input.
 Counters are used for counting number of occurrence of an event & also useful for the
generating timing signals to the control the sequence of operations in digital computers.
 A counter that follows the binary number sequence is called a binary counter.
 An n bit binary counter is a register of n flip flop & associated gates that follows a
sequence of states according to the binary count of n bit from 0 to 2n -1.

There are two types of Counter

1. Asynchronous Counter/ Serial Counter/ Ripple Counter

 Each flip-flop is triggered by the previous flip-flop and thus the counter has a cumulative setting
time is referred to as Asynchronous Counter.
 In other words, the output of one flip-flop drives the next flip-flop. So it is also called a Serial
Counter.
 It is inherently slow in operation due to series connection. The triggers move through flip-flop
like a ripple in water. So it is also called as Ripple Counter

PREPARED BY:DHVANI VYAS Page 15

 COMPUTER ORGANIZATION AND ARCHITECTURE
2. Synchronous/ Parallel Counter
 Each flip-flop is triggered by the same clock in synchronism, and thus the setting time is simply
equal to the delay time of a single flip-flop. The speed of operation can be achieved by the use of
parallel counter.

Up Counter
A counter that is capable of counting in upward direction is known as Up Counter, it counts from 0 to
2n-1.

Down Counter
A counter that is capable of counting in downward direction is known as Down Counter, it counts from
2n-1 to 0.

4 – bit Asynchronous Binary Up Counter

 A binary ripple counter can be constructed by use of edge – triggered JK flip-flop connected in
cascade.
 The system clock square waves, drives flip-flop A. The output of A drives B, the output of B
drives flip-flop C and the output of C drives flip-flop D.
 All the J and K inputs are tied to count enable input. This means that each flip-flop will change
the state (toggle) when J and K both inputs are high (count enable is high) and the negative
transition of clock pulse is made.
 When count enable is low (0) at that time flip-flop remains in the same state.
 The A flip-flop must change states before it can trigger the B flip-flop, the B flip-flop has to
change its states before it can trigger C flip-flop, and the C flip-flop has to change its states
before it can trigger D flip-flop.
 The waveforms given in following figure shows the action of the counter as the clock runs. Let’s
assume that the flip-flops are all initially reset to produce 0 outputs.
 If we consider A to be the least significant bit (LSB) and D the most significant bit (MSB), we can
say the contents of the counter is DCBA = 0000.

Counter A B C D
Enable

PREPARED BY:DHVANI VYAS Page 16

 COMPUTER ORGANIZATION AND ARCHITECTURE

Time a b c d e f g h i j k l m n o p

 Every time there is a negative clock transition, flip-flop A will change states. Thus at ‘a’ on time
line, A goes high, at point ‘b’ it goes back low, at ‘c’ it goes back high and so on. Notice that the
wave form at the output of flip-flop A is one-half the clock frequency.
 Since A acts as the clock for B, each time the wave form at A goes low, flip-flop B will toggle.
Thus at point ‘b’ on the time line, B goes high it then goes low at point ‘d’ and toggles back high
again at point ‘f’. Notice that the wave forms at the output of flip-flop B is one-half the
frequency of A and one-fourth the clock frequency.
 Since B acts as the clock for C, each time the wave form B goes low, flip-flop C will toggle. Thus C
goes high at point ‘d’ on time line and goes back low again at point ‘h’. The frequency of the
wave form at C is one-half that at B, but it is only one-eighth the clock frequency.
 Since C acts as the clock for D, each time the wave form C goes low, flip-flop D will toggle. Thus D
goes high at point ‘h’ on time line and goes back low again at point ‘p’. The frequency of the
wave form at D is one-half that at C, but it is only one-sixteenth the clock frequency.
Application
Digital Clock, frequency Counter

3 – bit Asynchronous Binary down Counter

 In a 3-bit down counter system clock is used at the clock input to flip-flop A, but the complement
of A, A’ is used to drive flip-flop B likewise B’ is used to drive flip-flop C.
 Flip-flop A simply toggles with each negative clock transition as before. But flip-flop B will toggle
each time A goes high. Notice that each time A goes high, A’ goes low, and it is the negative
transition on A’ that triggers B.
 Similarly, flip-flop C is triggered by B’ and so C will toggle each time B goes high. Thus C toggle
each time B goes high. Thus C toggles when B’ goes low.
 Notice that the counter contents are reduced by one count with each clock transition. In other
words, the counter is operating in count – down mode.

PREPARED BY:DHVANI VYAS Page 17

 COMPUTER ORGANIZATION AND ARCHITECTURE

Modulus
Defines the number of states through which a counter can progress. E.g. A 3 – bit binary counter is also
called MOD – 8 counter.

Combinational Circuit Sequential Circuit

1. A combinational circuit is a connected A Sequential circuit is an interconnection of logic
arrangement of logic gate with set of inputs and gates and flip - flops.
outputs.
2. Every Sequential circuit is a combinational Every combinational circuit is not a Sequential
circuit. circuit.
3. In the combinational circuit, output is In the Sequential circuit output is determined on
determined on the basic operation of current the basis of current input as well as previous
input. output.
4. The combinational circuit does not have features In Sequential circuit there is a feature to store
store previous output. previous output.
5. The combinational circuit can be described by a The Sequential circuit can be described by a state
truth table. table.
6. Clock signal is not applied to the combinational Clock signal is applied to the flip-flop in Sequential
circuit. circuit.
7. Examples: Decoder, Encoder, Multiplexer, Examples: Flip-flop, Register, Counter
Demultiplexer.

PREPARED BY:DHVANI VYAS Page 18

 COMPUTER ORGANIZATION AND ARCHITECTURE
3. DATA REPRESENTATION
Data representation
 The positive integers, including zero can be represented as unsigned numbers, to represent
negative integers we needs a notation for negative values.
 In ordinary arithmetic, a negative number is indicated by a minus (-) sign and a positive number
are indicated by a plus (+) sign.
 Because of hardware limitations, computer must represent everything with 1’s and 0’s including
the sign of a number.
 The left most position of the number is used to represent the sign bit. The sign bit equal to 0 for
the positive number and the sign bit equal to 1 for the negative number.
 In addition to the sign, a number may have a binary (or decimal) point.
 The position of the binary point is needed to represent integers, fractions or mixed integer
fraction numbers.
 The representation of the binary point in a register is complicated. There are two ways of
specifying the position of the binary point in a register.

o Fixed position representation.

o Floating point representation.

Fixed point representation

 Assumes that the binary point is always fixed in one position.
 There are following two position most widely uses:
 A binary point in the extreme left of the register to make the stored number a fraction
 A binary point in the extreme right of the register to make the stored number an integer.
 The floating point representation uses a second register to store a number that
designated the position of the decimal point in the first register.

Integer Representation
 When an Integer binary number is positive the sign is represented by 0 and the magnitude by a
positive binary number.
 When the number is negative, the sign is represented by 1. But the rest of the number may be
represented in one of the following three ways:
 Signed Magnitude Representation
 Signed - 1’s Complement Representation
 Signed - 2’s Complement Representation
 The signed magnitude representation of a negative number consists of the magnitude and
negative sign. In other two representation, the negative number is represented in either 1’s or
2’s Complement of its positive value.
 Example: - Consider the signed. Number 14 stored in an 8 bit register. +14 is represented by a
sign bit of 0 in the left most position followed by the binary number equivalent of +14: 0
0001110.
 Note that each of the eight bits of the register must have a value and therefore 0’s must be
inserted in the most significant positions following the sign bit.
 There are three different ways to represent - 14 with eight bits.


In signed magnitude representation 1 0001110
In signed - 1’s complement representation 1 1110001
In signed - 2’s complement representation 1 1110010

 The signed magnitude representation of -14 is obtained from +14 by complementing only the
sign bit.
 The signed - 1’s complement representation of -14 is obtained by complementing all the bits of
+12, including the sign bit.

PREPARED BY:DHVANI VYAS Page 1

 COMPUTER ORGANIZATION AND ARCHITECTURE
 The signed - 2’s complement representation is obtained by taking the 2’s complement of the
positive number, including its sign bit.

Floating Point Representation

 The floating - point representation of a number has two parts.
 The first part represents a signed fixed point number called the mantissa.
 The second part designates the position of the decimal point and is called the exponent.
 The fixed point mantissa may be a fraction or an integer.
 For example the decimal number +4362.68 is represented in floating point with a mantissa and
an exponent as follows:
o Mantissa: +0.436268
o Exponent: +04
 The value of the exponent indicates that the actual position of the decimal point is four positions
to the rights of the indicated decimal point in the fraction.
 This representation is also equivalent to scientific notation.
+0.436268 X 10+4
 The general form to represent the number in floating-point is as follow:
m x re
Where, m - Mantissa
e - Exponent
r - Radix (Base)
 Mantissa m and exponent e are physically represented in register (including their sign).
 The radix r and the radix point position of the mantissa are always assumed.
 A floating point binary number is represented in a similar manner except that it uses base 2 for
the exponent.
 The binary number +1001. 11 are represented with an 8- bit fraction and 6 bit exponent as
follows:
o Mantissa : 01001110
o Exponent : 000100
 The fraction has a 0 in the left most position to denote positive number.
 The exponent has the equivalent binary number +4.
 The floating point number is equivalent
m x 2e = + (0. 1001110)2 x 2+4
Normalization
 A floating-point number is said to be normalized if the most significant digit of the mantissa is
nonzero.
 A zero cannot be normalized because it does not have a nonzero digit.

Error Detection Code (Parity Bit)

 The binary information are transmitted through some form of communications medium is
subject to external noise that could change bit from 1 to 0 or 0 to 1.
 An error detection code is a binary code that detects digital errors during transmission.
 The detected errors cannot be corrected but their presence is indicated.
 If an error occurs infrequently at random, the particular erroneous information is transmitted
again.
 The most common error detection code used is the parity bit.
 A parity bit is an extra bit included with a binary message to make the total number of 1’s is
either odd or even.

PREPARED BY:DHVANI VYAS Page 2

 COMPUTER ORGANIZATION AND ARCHITECTURE
 The message of three bits and two possible parity bits is shown in following table.

Parity bit generation

 The P (odd) bit is chosen in such a way as to make the sum of 1’s (in all four bits) is odd.
 The P (even) bit is chosen in such a way as to make the sum of 1’s (in all four bits) is even.
 The even - parity scheme has the disadvantage of having a bit combination of all 0’s, while in the
odd parity there is always one bit that is 1.
 Note that the P (odd) is the complement of the P (even)
 During the transmission of information from one location to another location the parity bit is
handled as follows :
 At the sending end, the massage is applied to a parity generator, where the required parity bit is
generated. The message, including the parity bit is transmitted to its destination.
 At the receiving end, all the incoming bits are applied to a parity checker that checks the proper
parity adopted (odd or even)
 An error is detected if the checked parity does not conform to the adopted parity.
 Parity generator and parity checker networks are logic circuits constructed with exclusive OR
functions.
 An odd function is a logic function whose value is binary 1 if and only if an odd number of
variables are equal to 1.
 According to the above definition, the P (even) function is the exclusive OR of X, Y and Z because
it is equal to 1 when either one or all three of the variable are equal to 1.

Example
Consider the 3 - bit message to be transmitted with an odd parity bit.

Error detection with odd parity bit

PREPARED BY:DHVANI VYAS Page 3

 COMPUTER ORGANIZATION AND ARCHITECTURE
 At the sending end, the odd parity bit is generated by a parity generator circuit shown in above
figure.
 This circuit consists of one exclusive OR and one exclusive NOR gate. So p (even) is the exclusive -
OR of X, Y and Z. and p (odd) is the complement of p (even).
 The message and the odd-parity bit are transmitted to their destination where they are applied
to a parity checker.
 An error has occurred during transmission if the parity of the four bits receives is even, since the
binary information transmitted was originally odd.
 The output of the parity checker would be 1, when an error occurs, that is when the number of
1’s in the four inputs is even.
 Since the exclusive OR function of the four inputs is an odd function, we again need to
complement the output by using an exclusive - NOR gate.

PREPARED BY:DHVANI VYAS Page 4

 COMPUTER ORGANIZATION AND ARCHITECTURE
4. Central Processing Unit (CPU)
Introduction of CPU

 The part of computer that perform the bulk of data processing operation is called Central
Processing Unit which is referred a CPU.
 CPU is a brain of computer
 Although its main function lies in executing programs, it’s also controls input devices, output
devices and other components of a computer.
 Under its control, programs and data are stored in memory and displayed on the screen.

Major Component of CPU

CPU is made up of three major parts as given in following figure

 Control Unit (CU)
 Arithmetic and Logic Unit (ALU)
 Register set

Register set

Control
unit (CU)
Arithmetic and
logic unit (ALU)

Major Component of CPU.

Control Unit
 Control Unit controls the entire operation of the computer.
 It controls the memory and input-output device.
 The Control Unit (CU) control the transfer of information from registers set and instruct
the ALU as to which operation to perform.

Register Set
 Register set consist of one or more register used for storing intermediate data during the
execution of information.
 After store entire information, register set redirect the stored information into the ALU.
 It performs the several operations after performing the operation.

Arithmetic and Logic Unit

 The Arithmetic and Logical Unit (ALU) performs the arithmetic and logical operation as per
instructions.
 The Arithmetic and Logic Unit (ALU) performs the required micro operation for executing
the instruction.
 It is again a major component of CPU system which accepts and redirects the information
from register set after completing the operation.

PREPARED BY:DHVANI VYAS Page 1

 COMPUTER ORGANIZATION AND ARCHITECTURE
General Register Organization

 The memory locations are needed for storing pointers, counters, returns addresses, temporary
results and partial products during the multiplication, division or any arithmetic operation.
 Having to refer to memory location for such applications is time consuming because memory
access is most time-consuming operation in computer.
 It is more convenient and more efficient to store this intermediate values in processor register.
 When a large no. of registers is included into the CPU, It is most efficient to connect through a
common bus.
 The registers communicate with each other not only for direct data transfer but also while
performing micro operation.
 Hence it is compulsory provide common unit that perform all arithmetic and logical operation.
 A general organization of seven CPU register is shown in given below figure which have the other
component like Multiplexer, Decoders and Arithmetic & Logical Unit (ALU).

A Bus organization for seven CPU registers

Clock Input

R1
R2
R3
R4
R5
R6
R7

L oad
(7 lines) SEL A MUX MUX SEL B

3 x 8
decoder A bus B bus

SEL D

OPR Arithmetic logic unit

(ALU)

output

 In above figure the output of each register is connected to two multiplexer (MUX) to form the
two buses a bus and B bus.
 The selection lines of each multiplexer selects one register or input data for the particular bus.
 The A-bus and B-bus from the input are given to a common ALU.
 The operation selected in ALU decides the arithmetic or logic micro operation that is to be
performed
 The result of the micro operation is available for output and also goes into the input of all the
register.
 The register that receives the information from the output bus is selected by a Decoder.
 Output line of the Decoder is connected with the Load line of each register (D1 connected to R1
load, D2 connected to the R2 load and so on.).
PREPARED BY:DHVANI VYAS Page 2
 COMPUTER ORGANIZATION AND ARCHITECTURE
 The decoder activates one of the register load inputs and providing the transfer path between
the data in the output bus and the input of the selected destination register.
 To understand the processing of this register organizations consider the following example.
R1 R2 + R3
 In the above example R2 and R3 are the input register and R1 is the output register which give
processed value of R2 and R3.
 The control unit provides the binary selection variables to the following selector inputs:
o MUX A Selector (SELA): Multiplexer A is used to place the value of R2 into the bus A.
o MUX B Selector (SELB): Multiplexer B is used to place the value of R3 into the bus B.
o ALU operation selector (OPR): to provide arithmetic addition of A bus and bus B, that
holds the value of R2 and R3 respectively.
o Selector D (SELD): specifies the destination to transfer the contents of output bus into
the register R1.

Control word

 There is 14-bit binary selection input in the unit and their combine value specifies a control
word.
 The figure of 14-bit control word is as given below.

3 bit 3 bit 3 bit 5 bit

SEL A SEL B SEL D OPR
Control Word

 There are 14-bit control words which define in above figure which consist of four fields.
 The first three fields contain three bit in each field and the fourth field contain 5-bits.
 The first field is SELA, which contains 3-bits.
 The second field is SELB, which contains 3-bits.
 The third field is SELD, which contains 3-bits.
 The fourth field is OPR, which contains 5-bits.
 The 3-bits of SELA select a source register for the A input of the ALU.
 The 3-bits of SELB select a source register for the B input of the ALU.
 The 3-bits of SELD select a destination register using the decoder and its seven load outputs.
 The 5-bits of OPR select one of the operations in the ALU.
 The 14-bits control unit is applied to the selection input to specify a particular micro-operation.
 Selection (encoding) of a specified register is done by referring the following table.

 The register selected by fields SELA, SELB, and SELD is the one whose decimal number is
equivalent to the binary number in the code.
 When SELA or SELB is 000 the corresponding multiplexer selects the external input data.

PREPARED BY:DHVANI VYAS Page 3

 COMPUTER ORGANIZATION AND ARCHITECTURE
 When SELD is 000, no destination register is selected but the contents of the output bus are
available in the external output.
 The ALU provides arithmetic and logic operations. There are some operation codes for each
operation.

Example of Micro Operation

R1R2 – R3
The Binary Control Word:

Field: SELA SELB SELD OPR

Symbol: R2 R3 R1 SUB
Control Word 010 011 001 00101

Arithmetic and Logic Unit

 Arithmetic and Logical Unit is major component of CPU system which accepts and redirects the
information from register set after completing the operation.
 ALU can perform arithmetic and logical operation on a accept instruction format.
 The following logical diagram describes block diagram of 4 bit Arithmetic and Logic Unit.
Input A Input B

A4 A3 A2 A1 B4 B3 B2 B1 S2 Mode Select
Out S1
(Output Function
4 - bit ALU S0 select
carry)
F4 F3 F2 F1 C (Input carry)

Output line

 It has number of selection lines to select a particular operation in the unit.

 The selection lines are decoded within the ALU so that n selection variables can specify up to
2n distinct operation.
 The four data input from A are combined with 4 data input from B to generate an operation at
F output.
 The Mode select input S2 distinguishes between arithmetic and logic operation. S2 is known as
mode-select.
 The two function select input S1 and S2 specify the particular arithmetic or logic operation to
be generated. S0 and S1 are known as function select.
 With 3 select input variables it is possible to specify four arithmetic operations and 4 logical
operations.
 The input and output carries have meaning only during arithmetic operation.

PREPARED BY:DHVANI VYAS Page 4

 COMPUTER ORGANIZATION AND ARCHITECTURE
Accumulator Register (AC Register)
 The block diagram of processor with an Accumulator Register (AC Register) is shown as per
following:
Input data

Select B Processor Register

ALU

Accumulator
Register

Output
Block diagram of processor with AC Register

 Some processor unit has separate register from all other register. This separate register is
known as Accumulator Register, abbreviated as AC.
 AC Register’s initial value is 0.
 Generally, AC Register is used to perform arithmetic operation, but sometimes AC Register is
used to perform multipurpose task in the processor.
 AC Register can perform all the digital function found in ALU.
 All operations are performed with an implied accumulator register.
 In this mode, the operations are specified implicitly in the definition of the instruction. For
example, the instruction “CLEAR Accumulator” is an implied-mode instruction because the
operand in the accumulator register is implied in the definition of the instruction.
 In above logic diagram input B is supply from the external source, this information come from
either processor register or memory unit.
 Input B is controlled by selected B control signal.
 From the AC Register other input is passed to ALU.
 This input AC represents the previous result of the previous operations.
 The sum of two number stored in processor register using AC Register is describe as per
following:
AC  0 ------------- Clear State
AC  AC + R1 ------------- Add R1 to AC
AC  AC + R2 ------------- Add R2 to AC

 Here first statement clear the AC register, so AC=0.

 Second statement add the value of register R1 to AC, so AC=R1.
 Third statement add the value of register R2 to AC, so AC=R1+R2

Processor Registers
 Stack Pointer (SP)
It holds the address of the word that is currently on the top of the stack.
 Address Register (AR)
It points at an array of the data.
 Program Counter (PC)
It holds the address of the next instruction in the program.
 Data Register (DR)
It holds the binary data to be written into or read out of the stack.

PREPARED BY:DHVANI VYAS Page 5

 COMPUTER ORGANIZATION AND ARCHITECTURE
Stack Organization

 A useful feature that is included in the CPU of most computers is stack or Last-In-First-Out
(LIFO) list.
 A stack is a storage device that stores information in such a manner that the item stored last is
the first item retrieved.
 The operation of a stack can be compared to a stack or trays.
 The last tray placed on top of the stack is the first to be taken off.

Stack Pointer
 The stack in digital computers is essentially a memory unit with an address register that
can count only.
 The register that holds the address for the stack is called a Stack Pointer (SP) because its
values always points at the top item in the stack.

Operations
The two operation of stack are insertion and deletion of items which are given below:
 Push: The process of inserting an item into the stack is known as Push and is done by
incrementing stack pointer.
 POP: The process of deleting an item from the stack is known as POP and is done by
decrementing stack pointer.

Application
 When Recursive Functions are called.
 To evaluate the Arithmetic Expression.

Types of stack organization

 Register Stack
 Memory Stack

Register stack

 A stack can be placed in a portion of a large memory or it can be organized as a collection of a

finite number of memory words or registers.
 Fig shows the organization of a 64 word register stack.
 The Stack Pointer (SP) register contains 4 binary numbers whose value is equal to the address
of the word that is currently on top of the stack.
 Three items are placed in the stack: A, B and C in that order.
 Item C is on top of the stack so that the content of SP is now 3.
 To remove the top item, the stack is popped by reading the memory word at address 3 and
decrementing the content of SP.
 Item B is now on top of the stack since SP holds address 2.
 To insert a new item, the stack is pushed by incrementing SP and writing a word in the next -
higher location in the stack.
 Stack Pointer: In a 64 word stack, the Stack Pointer (SP) contain 6 bit because 26 = 64. Since SP
has only 6 bits, it cannot exceed a number greater than 63 (111111).
 FULL: The one bit register FULL is set to 1 when the stack is full of items.
 EMPTY: The one -bit register EMPTY is set to 1 when stack is empty.
 Data Register: DR is the Data Register that holds the binary data to be written into the stack or
read out of the stack.

PREPARED BY:DHVANI VYAS Page 6

 COMPUTER ORGANIZATION AND ARCHITECTURE

PUSH:
 Initially SP is cleared to 0. EMPTY is set to 1 and FULL is cleared to 0, So that SP points to
the word at address 0 and stack is marked empty or not full.
 If the stack is not full (if FULL=0), a new item is inserted with a push operation.
 If the stack is full and user try to insert a new value in the stack, then it is called Stack
Overflow error.
 The push operation is implemented, with the following sequence of micro-operations :

SP  SP + 1 increment stack pointer

M [SP] DR write item on top of the Stack

IF (SP = 0) then (FULL  1) check if stack is full

EMTY  0 mark the stack not empty

 The stack pointer is incremented so that it points to the address of the next-higher word.
 The first item stored in the stack is at address 1 and the last item is stored at address 0.
 If SP reaches 0, the stack is full of items, so FULL is set to 1. And EMTY is cleared to 0.
POP:
 A new item is deleted from the stack if the stack is not empty (if EMPTY=0).
 If the stack is empty and user tries to delete an item from the stack, then it is called
Stack Underflow error.


PREPARED BY:DHVANI VYAS Page 7

 COMPUTER ORGANIZATION AND ARCHITECTURE


 The pop operation consists of the following sequence of micro-operations.

DR  M [SP] Read item from the top of stack

SP  SP –1 Decrement SP

IF (SP = 0) then (EMTY 1) Check if stack is empty

FULL  0 Mark the stack not full.

 The top item is read from the stack into DR the stack
 The stack pointer is then decremented.
 If its value reaches zero, the stack is empty, so EMPTY is set to 1. And FULL is set to 0.

Note: An erroneous operation will result if the stack is pushed when FULL = 1 or popped
when EMTY = 1.

Memory stack
 A stack can exist as a standalone unit or it can be implemented in RAM (Random Access
Memory) attached to CPU.
 The implementation of a stack in CPU is done by assigning a portion of memory to a stack
operation and using a processor register as a stack pointer.
 Figure shows a portion of computer memory partitioned into three segments.
o Program
o Data
o Stack
 The Program Counter (PC) points at the address of the next instruction in the program.
 The Address Register (AR) points at an array of data.
 The Stack Pointer (SP) points at the top of the stack.
 The three register are connected to a common address bus.
 PC is used during fetch phase to read an instruction.
 AR is used during the execute phase to read an operand.
 SP is used to push or pop item into or from the stack.

PREPARED BY:DHVANI VYAS Page 8

 COMPUTER ORGANIZATION AND ARCHITECTURE

 As shown in figure the initial value of SP is 4001 and stack grows with decreasing addresses.
 The first item stored in the stack is at address 4000, the second item is stored at 3999 and the
last address that can be used for the stack is 3000.
 The items in the stack communicate with the data register DR.
 The new item is inserted with the PUSH operation as given below:

PUSH:
SPSP-1
M [SP]DR

PREPARED BY:DHVANI VYAS Page 9

 COMPUTER ORGANIZATION AND ARCHITECTURE
 The stack pointer is decremented so that it points at the address of the next word.
 A memory write operation inserts the word from the DR into the Top of the Stack.
 The item is deleted with the POP operation as given below:

POP:
DRM [SP]
SPSP+1
 The Top item is read from the stack into DR.
 The stack pointer is then incremented to point at the next item in the stack.

Stack Limits:
 Most computers do not provide hardware to check for stack overflow (Full Stack) or underflow
(Empty Stack).

 The stack limits can be checked by using two processor register: one to hold the upper limit and
the other to hold the lower limit.
 After the push operation, SP is compared with the upper-limit register and after a pop operation,
SP is compared with the lower-limit register.

Advantage:

A stack pointer is loaded with an initial value i.e. the bottom address of an assigned stack in memory.
The advantage of a memory stack is that the CPU can refer to it without having to specify an address,
since the address is always available and automatically updated in the stack pointer.

Reverse Polish Notation (RPN)

 A stack organization is very effective for evaluating arithmetic expressions.
 Evolution of arithmetic expressions using computer is difficult and tedious task because
expressions uses parenthesis and brackets.
 To represent the arithmetic expressions, following three types of different notations are used :
o Infix Notation
o Prefix Notation
o Postfix Notation

1. Infix Notation :
 The common arithmetic expressions are written in infix notation with each operator
written between the operands.
 Consider the simple example
A*B
 The multiplication is placed between two operands an A and B.
 The plus is between two products.
2. Prefix Notation:
 The polish mathematician showed the arithmetic expression can be represented in
prefix notation.
 This representation often referred to as polish notation, places the operator before
the operands.
 Consider the example in polish notation - * A B
3. Postfix Notation :
 The postfix notation referred to as Reverse Polish Notation (RPN), places the operator
after the operands.
 Consider the example in polish notation - A B *
 The RPN is in a form suitable for stack manipulation.

PREPARED BY:DHVANI VYAS Page 10

 COMPUTER ORGANIZATION AND ARCHITECTURE

The expression
A*B+C*D

Is written in Reverse Polish Notation is

AB * CD * +

Conversion to RPN
 To convert from infix notation to reverse police notation we first perform all arithmetic
operations inside inner parentheses, then inside outer parenthesis, and do multiplication and
division operation before addition and subtraction operations.
 Consider the expressions
(A + B) * [C * (D + E) + F]

 First we perform the arithmetic operation inside the parentheses (A + B) and (D + E).
 Next multiplication of C * (D + E) must be done prior to the addition of F since multiplication has
precedence over addition.
 Last operation is the multiplication of parenthesis and brackets.
 The converted expressions

AB + DE + C * F + *

Evaluation of Arithmetic Expression

 Reverse Polish Notation, combined with stack arrangement of registers, is the most efficient way
known for evaluating arithmetic expressions.
 The procedure consists of first converting the arithmetic expression into its equivalent Reverse
Polish Notation.
 The operands are pushed in to the stack in the order in which they appear.
 The following micro operations are executed with the stack:
o The two topmost operands into the stack are used for the operation.
o The stack is popped and the result of the operation replaces the lower operand.
 By pushing the operands into the stack continuously and performing the operations, the
expression is evaluated in the proper order and the final result remains on top of the stack.

For Example
(3 * 4) + (5 * 6)
In RPN, it is expressed as,
34*56*+

Stack Operations
 In the following figure each box represents one stack operation and the arrow always points to
the top of the stack.
 Executing from left to right first the number 3 is pushed into the stack, then the number 4.
 The next symbol is the multiplication operator *.
 This causes a multiplication of the two topmost items in the stack. The stack is then popped and
the product is placed on the top of the stack, replacing the two original operands.
 Next 5 and 6 are pushed in to the stack. Again next symbol is the multiplication operator *, that

PREPARED BY:DHVANI VYAS Page 11

 COMPUTER ORGANIZATION AND ARCHITECTURE
replaces these two numbers by their product.
 The last operation causes an arithmetic addition of the two topmost numbers in the stack to
produce the final result of 42.

6
4 5 5 30
3 3 12 12 12 12 42

Stack operations to evaluate 3 * 4 + 5 * 6

PREPARED BY:DHVANI VYAS Page 12

 COMPUTER ORGANIZATION AND ARCHITECTURE
Interrupt
 The concept of program interrupt is used to handle a variety of problems that arise out of
normal program sequence.
 Program interrupt reefers to the transfer of program control from a currently running program
to another service program as a result of an external or internal generated request.
 Control returns to the original program after the service program is executed.
 The interrupt procedure is similar to the subroutine call except for three differences:
o The interrupt is usually initiated by the internal or external signal rather than of the
execution of an instruction.
o The address of the interrupt service program is determined by the hardware rather
than from the address field of an instruction.
o An interrupt procedure usually stores all the information necessary to determine the
state of the CPU rather than storing only the program counter.

State of the CPU

When interrupt is recognized the state of the CPU is determined from:
 The content of the Program Counter
 The content of the Processor Register
 The content of certain Status Conditions (PSW).

Program Status Word (PSW)

The collection of all the status bit conditions in the CPU is called a Program Status Word or PSW. It
includes:
 The status bits from the last ALU operation.
 It specifies the interrupts that are allowed to occur.
 Whether the CPU is operating in a supervisor mode or user mode.
o Supervisor mode:
The OS controls and supervises all other programs in the computer. When CPU is
executing a program that is the part of the operating system, it is said to be in the
Supervisor mode or System mode.
o User mode:
When CPU is executing the user programs then the CPU is said to be in User mode.

 Most computers just store the Program Counter and the PSW
In some cases there exist two sets of processor registers within the computer, one for each CPU
mode.

Interrupt Cycle
 Interrupt procedure is similar to the execution of the subroutine call instruction.
 The state of the CPU is pushed into the memory stack and the beginning address of the service
routine is transferred to the program counter.
 A new PSW is loaded into the status register.
 The beginning address of the service routine is determined by the hardware.
o Some computers assign one memory location where interrupts are always transferred.
The service routine must then determine what caused the interrupt and proceed to
service it.
o Some computers assign a memory location for each possible interrupt. Sometimes, the
hardware interrupt provides its own address that directs the CPU to the desired service
routine.

PREPARED BY:DHVANI VYAS Page 13

 COMPUTER ORGANIZATION AND ARCHITECTURE
 The CPU does not respond to an interrupt until the end of an instruction execution.
 Just before going to the next fetch phase, control checks for any interrupt signals. If an interrupt
is pending, control goes to hardware interrupt cycle.
 The last instruction in the service program is a return from interrupt instruction.
 When this instruction is executed, the stack is popped to retrieve the old PSW and the return
address.
 The PSW is transferred to the status register and the return address to the program counter.
Thus the CPU state is restored and the original program can continue executing.

Types of Interrupt
They can be classified as:
 Internal interrupts
 External interrupts
 Software interrupts

Internal Interrupt:
 It arises from illegal or erroneous use of instruction or data.
 Examples of interrupts caused by internal error condition are register overflow, attempt to
divide by zero, an invalid Operation code and stack overflow.
 This condition usually occurs as a result of premature termination of an instruction.
 The service programs that process the internal interrupt determine the corrective measure to be
taken.
 Internal interrupts are synchronous with the program. If the program is rerun, the internal
interrupts will occur in the same place each time.

External Interrupt:
 External interrupts come from some external devices such as an input-output (I/0) devices when
data needs to be transferred.
 External interrupt also occur when some time out has occurred, from a timing device, from a
circuit monitoring the power supply or from any other external source.
 Example that causes external interrupts are I/O device requesting transfer of data, I/O device
finished transfer of data, elapsed time of an event, or power failure.
 The external interrupts are asynchronous. It depends on external conditions that are
independent of the program being executed at the time.

Software Interrupt:
 It is initiated by executing an instruction.
 It can be used by a programmer to initiate an interrupt procedure at any desired point in the
program.
 Software interrupt take place when an application program called a supervisor program such as
operating system.
 It occurs under such condition when a user program request the operating system for handling
some special operation such as complex input output transfer procedure.

PREPARED BY:DHVANI VYAS Page 14

 COMPUTER ORGANIZATION AND ARCHITECTURE

5. Input Output Organization (IOP)

Peripheral Devices
The input output devices attached to the computer are called Peripheral Devices.

Input-Output Interface
 Input-output interface provides a method for transferring information between internal storage
and external I/O devices.
 Peripherals connected to a computer need special communication links for interfacing them
with the CPU.
 The purpose of the communication link is to restore the differences that exist between the
central computer and each peripheral.
 The major differences are:
o Peripherals are electromechanical and electromagnetic devices and their manner of
operation is difference from the operation of the CPU and memory, which are electronic
devices. Therefore, a conversion of signal values may be required.
o The data transfer rate of peripherals is usually slower than the transfer rate of the CPU,
and as a result, a synchronization mechanism may be needed.
o Data codes and formats in peripherals differ from the word format in the CPU and
memory.
o 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.
 To resolve the differences, computer system includes special hardware components between
the CPU and peripherals to synchronize all input and output transfer.
 These components are called interface units because they interface, between the processor bus
and the peripheral device.

I/O Bus and Interface Module

 The I/O bus consists of three lines: data lines, address line, and control lines.
 Combination of these three lines is known as I/O bus, which is used in data transfer between
processor and peripheral devices.
 The magnetic disk, printer and display terminal are employed in practically and general-purpose
computer.
 Each peripheral has its own Interface for data transfer.
 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 contains an address decoder that monitors the address
line.
 When the interface detects its own address it activates the path between the bus lines and the
device that it controls.
 All peripherals whose address does not correspond to the address in the bus are disabled by
their interface.

PREPARED BY:DHVANI VYAS Page 1

 COMPUTER ORGANIZATION AND ARCHITECTURE
 At the same time that the address is made available in the address lines, the processor provides
a function code in the control line.
 The interface selected responds to the function code and proceeds to execute it.
 The function code is referred to as an I/O command and is in essence an instruction that is
executed in the interface and is attached to the peripheral unit.
 There are four types of command depends on the peripheral that the processor is addressing.
 They are classified as control command, status command, data output command and data input
command.
 A Control Command is issued to activate the peripheral and to inform it what to do.
 A Status Command is used to test various status conditions in the interface and the peripheral.
 A Data Output Command causes the interface to respond by transferring data from the bus into
one of its registers.
 The Data Input Command is the opposite of the data output. Here the interface receives an item
of data from the peripheral and places it in the data bus and sends the data to the processor
register.

Buses
 A Bus is a collection of wires through which data is transmitted from one part of a computer to
another.
 You can think of a bus as a highway on which data travels within a computer. When used in
reference to personal computers, the term bus usually refers to internal bus. This is a bus that
connects all the internal computer components to the CPU and main memory.
 Buses can transmit information line data, address, special instructions and others.
 Information is transmitted on buses as a serials or series of electrical pulses. Each pulses
represented as a binary number 1 or 0.
 There are five types of buses available in a computer system:
o External Bus: This bus is placed outside the processor. It is used to transfer data between
one device to another device of computer.
o Internal Bus: This bus is placed inside the processor. It is used to transfer information
between processor register and internal components of processor.
o System Bus: This bus which is used to connects processor and main memory is called
System Bus.
o Instruction Bus: This bus is “Special data bus” which used to fetch instruction from the
main memory.
o Memory Bus: The memory bus is the set of wires that is used to carry memory addresses
and data to and from the system RAM.

Memory Bus
 Memory and I/O devices are connected to the CPU through a group of lines called a bus.
 These lines are meant to carry information.
 The memory bus is the set of wires that is used to carry memory addresses and data to and from
the system RAM.
 The memory bus in most PCs is also shared with the processor bus, connecting the system
memory to the processor and the system chipset.
The memory bus is further divided into the three buses:
 Data Bus: The portion of the memory bus that carries the actual data to and from the
memory is known as the data bus. The function of the bus speed and width describes how
much data can flow over the bus and is known as bandwidth. Data buses are bidirectional.
 Address Bus: An address bus carries the address of memory location that the CPU wants to
access. The width of the address bus defines how much memory the processor could
potentially address. The address bus is unidirectional.
 Control Bus: Control bus is bidirectional because the signals can flow in either direction from
CPU to memory or memory to CPU. Example of control signals are: RD (Read line), WR
(Write line), etc.

PREPARED BY:DHVANI VYAS Page 2

 COMPUTER ORGANIZATION AND ARCHITECTURE

ADDRESS BUS

DATA BUS
Memory
CPU OR
I/O
CONTROL BUS

I/O or Memory Connection to CPU

Isolated I/O versus Memory-Mapped I/O

1. Isolated I/O
 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 write control lines are enabled during an I/O transfer.
 The memory read and memory write control lines are enabled during a memory transfer.
 This isolates all I/O interface addresses from the addresses assigned to memory and is referred
to as the isolated I/O method for assigning addresses in the common bus.
 When CPU fetches and decodes the operation code for an I/O instruction, it places the address
associated with the instruction at the common address lines.
 And at the same time, it enables the I/O read (for input) or I/O write (for write) control line.
 That informs the external components that the address in the address line is for an interface
register and not for a memory word.
 When CPU fetching the instruction or the operand from memory, it places the memory address
on the address line and enables the memory read or memory write control line.
 This informs the external component that this address is for a memory word and not for an I/O
interface. This isolates the memory and the I/O address.

2. Memory-Mapped I/O

Direct Memory Access

What is DMA?

The transfer of data between fast storage device such as magnetic disk and memory is often
limited by speed of CPU. Removing the CPU from the path and letting the peripheral device
manage memory bus directly would improve the speed of transfer. This Transfer technique is
called Direct Memory Access (DMA).

 During DMA transfer the CPU is idle and has no control of memory buses.
 A DMA controller takes over the buses to manage the transfer directly between I/O devices and
memory.
 The CPU may be placed in an idle state in variety of ways. One common method extensively
used in microprocessor is to disable to buses through special control signals.
 Below figure shows two control signals in the CPU that facilitate the DMA transfer.

PREPARED BY:DHVANI VYAS Page 3

 COMPUTER ORGANIZATION AND ARCHITECTURE
Bus Request (input)
 The Bus request (BR) input is used by the DMA controller to request the CPU to hand over (free)
control of buses.
 When this input is active the CPU terminates the execution of the current instruction and places
the address bus, the data bus, and the read & writes lines into High Impedance State (Open
circuit, i.e. Disconnected).

Bus Grant (Output)

 The CPU activates bus grant output to inform the external DMA that the buses are in High
Impedance State.
 The DMA that originated the bus request can now take the control of buses to conduct memory
transfer without processor interference.
 When DMA terminates the transfer, it disables the bus request line.
 Then the CPU disables the bus grant, takes control of the buses, and returns to its normal
operations.

When the DMA takes the control of the bus system it communicates directly with the memory. The
transfer can be made in several ways.

Burst Transfer
 In burst transfer, a block sequence consisting of a number of memory words is transferred in a
continuous burst while the DMA controller is master of the memory buses.
 This mode of transfer is needed for fast devices such as magnetic disks, where data cannot be
stopped or slowed down until an entire block is transferred.

Cycle Stealing
 This technique allows the DMA controller to transfer one data word at a time, after which it
must return control of the buses to the CPU.
 The CPU merely delays its operation for one memory cycle to allow the direct memory I/O
transfer to “steal” one memory cycle.

DMA Controller

Block Diagram of DMA

 The DMA transfer controller needs the usual circuits of an interface to communicate with the
CPU and I/O devices.
 In addition it needs and address register, a word count register and a set of address lines.
 The address register and address lines are used for direct communication with the memory.
 The word count register specifies the number of words that must be transferred during single
transaction.

PREPARED BY:DHVANI VYAS Page 4

 COMPUTER ORGANIZATION AND ARCHITECTURE
 The data transfer may be done directly between the device and memory under control if the
DMA.
 DS (DMA select) and RS (Register Select) inputs: the registers in the DMA are selected by the
CPU through the address bus by ending the DS and RS inputs.
 The RD (read) WR (write) inputs are bidirectional:
 When BG=0: the CPU can communicate with the DMA controller (CPU initializes the DMA
Controller). Here RD and WR control lines are input lines.
 When BG=1: the DMA can communicate with Memory unit (Direct Memory Access). Here RD
and WR control lines are output lines.
 The DMA communicates with the external peripheral through the request and acknowledge
lines by using a handshaking procedure.
The DMA Controller had following three Registers
1. Address Register
 The address register contains an address to specify the desired location in memory.
 The address bits go through bus buffers into the address bus towards the memory.
 The address register is incremented by one after one word is transferred.
2. Word Count Register
 The word count register holds the number of words to be transferred.
 This register is decremented by one after each word transferred and also tested by zero
after word transferred.
3. Control Register
 The control register specifies the mode of the data transfer.
 It would be either in Read or Write Mode.

 The DMA is first initialized by the CPU.

 After that the DMA starts and continuous to transfer data between memory and peripheral unit
until an entire block is transferred.
 The initialization process is essentially a program consisting of I/O instructions that include the
address for selecting particular register.
 The CPU initializes the DMA by sending the following information through Data Bus:
1. The starting address of the memory block where data is available for read or writes.
2. The Word Count, which is the number of words in memory block.
3. Control to specify the mode of transfer such as read or write.
4. A control to start DMA transfer.
 Once the DMA is initialized, the CPU stops communicating with the DMA.
 As the DMA is complete CPU receives the interrupt signal.
DMA Transfer

PREPARED BY:DHVANI VYAS Page 5

 COMPUTER ORGANIZATION AND ARCHITECTURE
 The CPU communicates with the DMA through the address and data buses as with any interface
unit.
 The DMA has its own address, which activates the DS and RS lines.
 The CPU initializes the DMA through the data bus.
 Once DMA receives the start control command, it can start the transfer between peripheral
device and the memory.
 When peripheral device sends a DMA request, the DMA controller activates the BR line to
inform the CPU.
 The responds with its BG line to inform the DMA for grant.
 The DMA then puts current value of its address register into address bus, initiates the RD or WR
signal and sends the DMA acknowledge to peripheral devices.
o RD and WR signals are bidirectional.
o When BG = 0 (i.e. CPU initialize DMA controller) the RD and WR lines are input lines.
o When BG = 1 (i.e. Direct Memory Access) the RD and WR lines are output lines.
 When peripheral devices receives the DMA acknowledge signal, it puts a word in the Data bus
(for write) or receives a word from the data bus (for read).
 The peripherals can then communicate with memory through the data bus for direct transfer
between the two units.
 For each word that is transferred, the DMA increments its address register and decrements its
word count register.
 If the word count register reaches zero, the DMA stops any further transfer and removes its bus
request.
 It also informs CPU of the termination by means of an interrupt.
 When the CPU responds to the interrupt, it reads the content of the word count register. The
zero value of this register indicates that all the words were transferred successfully.
Application
 It is used for fast transfer of information between magnetic disks and memory.
 It is also used for updating the display in an interactive terminal.

Input-output processor (IOP)

 Instead of having each interface communicate with the CPU, a computer may incorporate one or
more external processors and assign them the task of communicating directly with all I/O
devices.
 An input-output processor (IOP) may be classified as processor with direct memory access
capability that communicates with I/O devices.
 In this configuration, the computer system can be divided into a memory unit, and a number of
processors compared of the CPU and one or more IOPs.
 A processor that communicates with remote terminals over telephone and other
communication media in a serial fashion is called a Data Communication Processor (DCP).

 Unlike the DMA controller that must be set up entirely by the CPU, the IOP can fetch and
execute its own instructions.
 The block diagram of a computer with two processors is given above.
 As shown in figure the memory unit occupies a central position and can communicate with each
processor by means of direct memory access.
 The CPU is responsible for processing the data for computational task.

PREPARED BY:DHVANI VYAS Page 6

 COMPUTER ORGANIZATION AND ARCHITECTURE
 The IOP provides a path for transfer of data between various Peripherals Device (PD) and
memory unit.
 In figure we can see that 4 peripheral devices are connected with the IOP.
 Each I/O devices and its operation with the use of I/O bus.
 The data formats of peripheral devices like keyboard / printer are differ from memory and CPU
data format.
 The IOP must structure data words from many different sources for example, it may be
necessary to take four byte from an input device and drop them into one 32-bit word before the
transfer to memory.
 Data are gathered in the IOP at the device rate and bit capacity while the CPU is executing its
own program.
 An output word transferred from memory to the IOP is directed from the IOP to the output
device at the device rate and bit capacity.
 The communication between the IOP and the devices attached to it is similar to the program
control method of transfer.
 Communication with the memory is similar to the direct memory access method.
 In most computer systems, the CPU is the master while the IOP is slave processor.
 The CPU is assigned the task of initiating all operations, but I/O instructions are executed in the
IOP.
 Instructions that are read from memory by an IOP are sometime called commands.
 Commands are prepared by experienced programmers and are stored in memory.

CPU - IOP Communication

 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 above flow chart.
 The status word indicates whether the transfer has been completed or if any errors occurred
during the transfer.
 From the inspection of the bits in the status word, the CPU determines if the I/O operation was
completed satisfactorily without any errors.
 The IOP takes care of all data transfer between several I/O units and the memory while the CPU
is processing another program.
 The IOP and CPU are completing for the use of memory, so the number of devices that can be in
operation is limited by the access time of the memory.

PREPARED BY:DHVANI VYAS Page 7