Computer Organization and Architecture (InSy2054)

Chapter 1
Overview and history of Computer Architecture
Introduction:
Computer organization and architecture is
 The study of the structure, behavior and design of computer.
 The interface between the hardware and the lowest level of software.

Classification of computer by its operating principle:

1. Analog computer  provide continuous information,
Data is not a number, it is a physical quantity: like pressure, speed, voltage,
temperature.
Ex: analog clock, car speedometer
Medical/electronic equipments, Radio/TV signal.

2. Digital computer >provides discrete information,

Data in the form of numbers, symbols.
Ex: calculator, automobile dashboard components, mini, micro, mainframe, super
computers.

3. Hybrid computer exhibit features of both analog and Digital.

Ex: cement plant, gas pumping station.

History of Computer Architecture:

First Generation (1945-1958) (ENIAC)
 Vacuum tubes based processing
 Assembly language programming
 Drum/magnetic core memory for storage

Two models of design:

(1) Harvard Architecture: (relay-based computer)
 Physically separate storage and signal pathways for instruction and data.
 Stored instruction on punched tape, data in relay latches.

(2) Von-Neumann Architecture: (stored-program computer)

 Single storage structure to hold both the set of instructions and the data
 Bottleneck is data transfer rate between CPU and memory is very low.

Modern CPU design incorporate aspects of both architectures:

Harvard architecture is used as the CPU accesses the cache – on chip cache memory is
divided into an instruction cache and data cache.
Von-Neumann architecture is used for off chip memory access.

Second Generation: (1958-1964) (IBM 709)

 Transistors based processing
 First OS – handled one program at a time
 High-level languages
 Reduced the computational time from milliseconds to microseconds.

Third Generation: (1964-1974) (IBM 360)

 Integrated Circuits(IC) based processing
 Semi-conductor memory
  Time sharing, graphics, structured programming
 Cache memory

Fourth Generation: (1974 – present)

 VLSI(Very Large Scale ICs) based processing
 Single chip processor, and single board computer
 Personal computer
 Object Oriented Programming
 Artificial Intelligence

Computer organization: focuses on Physical aspects of computer systems

Ex: circuit design, control signals, memory types
How does a computer work?

Computer Architecture: focuses on Logical aspects of system as seen by the programmer

Ex: instruction set, instruction formats, data types, addressing modes.
How do I design a computer?

Why Study computer organization and architecture?

 Design better program, including system software such as compilers, OS, device drivers, embedded
system.
 Optimize program behavior,
 Evaluate computer system performance,
 Understand time, space and price tradeoffs.

Major components of computer:

Layers of Abstraction(Software/Hardware):

Application

Operating
Compiler System
Instruction Set
Architecture
Instr. Set Proc. I/O system
Digital Design
Circuit Design
Integrated Circuits(IC) is made up of logic gates, memory cells and path to interconnect both.

Moore Law: (Goordin moore 1965)- cofounder of intel

 The number of transistors that could be part of a single chip was doubling every year.

Digital – implies that the information in the computer is represented by variables that take a limited number of
discrete values. Digital components that are constrained to take discrete values are further constrained
to take only two values and are said to be binary.

Binary digit: Digital computer uses the binary number system, which has two digits: 0 and 1. A binary digit is
called a bit.

Binary Logic: True or False, Yes or No, 1 or 0.

Logic Gates: Binary information is represented in digital computers by physical quantities called signals.
An electrical signal such as voltages exists to represent two states: 3 volt. for binary 1; 0.5 volt. for binary 0.

The manipulation of binary information is done by logic circuits called gates. Gates are blocks of hardware that
produce signals of binary 1 or 0 when input logic requirements are satisfied.

The input-output relationship of the binary variables for each gate can be represented in tabular form by a truth
table. Each gate has a distinct graphic symbol and its operation can be detected by means of an algebraic
expression.
Boolean Algebra:
A Boolean Algebra is an algebra (set, operations, elements) consisting of a set B with >= 2 elements, together
with three operations – (AND, OR, NOT) – defined on the set.

Two elements Boolean algebra: B2= ({0, 1}; ., +, '; 0, 1)

(also known as switching algebra)

Basic identities of Boolean Algebra:

All the identities can be proven by means of truth tables. Identities apply to single variables or Boolean
functions expressed in terms of binary variables.

Boolean Function: can be expressed algebraically with binary variables, the logic operation symbols,
parenthesis and equal sign
Ex: F = x + y'z -for a given value of variables, the Boolean function can be either 1 or 0.

Truth Table: The relationship between a function and its binary variables can be represented in a truth table.
F1 = xyz'
Logic Diagram: A Boolean function can be transformed from an algebraic expression into a logic diagram
composed of AND, OR, NOT gates.

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 relationships of logic diagrams.
3. Find simpler circuits for the same function.

NOR/NAND Gates: have alternate graphic symbols, based on Demorgan’s theorem

Universal Gates: NAND and NOR gates can be used to implement any Boolean function, including basic gates
such as AND, OR, and NOT. hence, NAND and NOR gates are called as Universal gates.

Complement of a Function (F): Is obtained by interchanging 1’s and 0’s in the values of F, in the truth table.

When the function is expressed in algebraic form, the complement of the function can be derived by means of
Demorgan’s theorem.
Ex: F = AB+C’D’+B’D
Complement function: F’ = (A’+B’).(C+D).(B+D’)

A Boolean function specified by a truth tale can be expressed algebraically in many different ways.
Two ways are,
1. Canonical form
2. Non-canonical form

Canonical form: express all binary variables in every product (AND) or sum (OR) form of the Boolean
Function, from the truth table.
Ex: F = A’BC+A’BC’+ABC’+AB’C’+A’B’C’+ABC

Non-canonical form: express some (or) all binary variables in product (AND) or sum (OR) form of the
Boolean function, from the truth table.
Ex: F=A’B+C’+ABC

Minterm and Maxterm:

Minterm: consider three binary variables x, y and z combined with AND operation is called minterm or
standard product.
Maxterm: consider three binary variables x, y and z combined with OR operation is called maxterm or
standard sum.

Standard Forms: Another way to express Boolean function is in standard form. In this form, the terms that
form the function may contain one, two, or any number of variables.
1. The sum of products,
2. The product of sums.

Sum of products form: is a Boolean expression containing AND terms, called product terms, of one or more
variables each. The sum denotes the ORing of these terms.
Ex: F = y’ + xy + x’yz’

Product of sum form: is a Boolean expression containing OR terms, called sum terms. Each term may have
any number of variables. The product denotes the ANDing of these terms.
Ex: F = x(y’ +z)(x’ + y + z’)
MAP Simplification:
The complexity of the logic diagram that implements a Boolean function is related directly to the complexity of
the algebraic expression from which the function is implemented.

Limitation of Boolean algebra:

It lacks specific rules for predicting each succeeding step in the manipulative process.

Two methods of simplifying Boolean algebraic expression:

1. Map method (Karnaugh map method)
2. Tabular method (Quinc-McCluskey method)

 Map method is used for functions up to six variables.

 To manipulate function of a large number of variables the tabular method is used.
o If a function to be minimized is not in a canonical form, it must first be converted into canonical
form before applying Quinc-McChuskey tabular procedure.
 Another tabular method, known as the iterative consensus method, begin the simplification process even
if the function is not in a canonical form.

K-Map method:
This method provides a simple, straightforward procedure for simplifying Boolean expression. This method
may be regarded as 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.

The information contained in a truth table may be expressed in compact form by limiting the decimal equivalent
of those minterm that produce a 1 for the function.

Ex: the following truth table is expressed as F(x, y, z) = ∑(2,3,6,7)

Is equivalent to F = x’yz’ + x’yz + xyz’ + xyz

K-Map:
The map is a diagram made up of squares, with each square representing one minterm. The squares
corresponding to minterms that produce 1 for the function are marked by a 1 and others are marked by a 0 or
one left empty.

By recognizing various pattern and combining squares marked by 1, in the map, it is possible to derive
alternative algebraic expressions for the function, from which most convenient may be selected.

Two variables K-map:

 Ex: (a) F = xy (b) F = x+y

Three variables K-map:

Four variables K-map:

 The number of squares in a map of n variables is 2n.

 The minterm numbers are assigned in an orderly arrangement such that adjacent squares represent
minterms that differ by only one variable.
 Each variables under bracket contains half of the squares in the map where that variable appears
unprimed-1 (uncomplemented). The variable appears with a prime-0 (complemented) in the remaining
half of the squares.

Adjacent squares:Minterms of adjacent squares in the map are identical except for one variable, which appears
complemented (O) in one square and uncomplemented (1) in the adjacent square.

According to this definition of adjacency, the squares at the extreme ends of the same horizontal row are also to
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.

K-map Simplification procedure:

1. 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.

2. 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.(Give preference to largest possible group)
Groups of combined adjacent squares may share one or more squares with one or more groups.

3. Each group of squares represents an algebraic form, and the OR of those terms gives the simplified
algebraic expression for the given function.

Example (1): Simplify the Boolean function F(x, y, z) = ∑(3, 4, 6, 7)

 simplified function F = yz + xz’
Note:
 Two adjacent squares are combined in the third column. This column belongs to both Y and Z , so
produces the term YZ.
 The remaining two squares with 1’s in the two corners of the second row one adjacent and belong to row
X and the two column’s of Z’, so they produce the term XZ’.

Example (2): Simplify the following Boolean function: F (x, y, z) = ∑(0,2,4,5,6)

simplified function F = z’ + xy’

Note:
 The four squares in the first and fourth columns are adjacent and represent the term Z’.
 The remaining square marked with a 1 belongs to minterm 5 and can be combined with the square of
minterm 4 to produce the term XY’.

Example (3): Simplify F(w, x, y, z) = ∑(0,1,2,4,5,6,8,9,12,13,14)

simplified function F = y’ + w’z’ + xz’

Note:
 The function contain 1’s in the first two columns, when taken as a group, give the term y’.
 The two 1’s on the top first column are combined with the two 1’s on the top last column, to give the
term w’z’.
 The remaining 1 in the square of minterm 14 is combined with minterm 6 to give the term xz’.

Don’t Care conditions: The 1’s and 0’s in the map represent the minterms that make the function equal to 1 or
0. These are occasions when it does not matter if the function produces 0 or 1 for a given minterm.

Since the function may be either 0 or 1, we say that we don’t care what the function output is to be for this
minterm. Minterms that may produce either 0 or 1 for the function are said to be don’t care conditions and are
marked with an X in the map.
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. In addition, an X need not be used at all if it does not contribute to be
simplification of the function.

Example: Simplify: F(w, x, y ,z) = ∑(1, 3, 7, 11, 15)

d(w, x, y, z) = ∑(0, 2, 5)

The 1’s and x’s are combined in any convenient manner so as to enclose the maximum number of adjacent
squares.

Note that don’t care minterm 5 was not included in the first case (a) and minterm 0 was not included in the
second case (b), because it does not contribute to the simplification of the expression.

Fundamental building blocks of digital logic circuit design:

1. Combinational circuit:
A combinational circuit consists of logic gates whose outputs, at any time, are determined by combining the
values of the inputs. It means that output depends only on its current inputs.

Some useful combinational circuits are:

1. Multiplexer(MUX): A MUX is a digital switch that has multiple inputs (sources) and a single output
(destination). The select lines determine which input is connected to the output.
 MUX Types:
 2-to-1 (1 select line)
 4-to-1 (2 select lines)
 8-to-1 (3 select lines)
 16-to-1 (4 select lines)

2. Demultiplexer(DEMUX): A DEMUX is a digital switch with a single input (source) and a multiple outputs
(destinations). The select lines determine which output the input is connected to.

DEMUX Types
 1-to-2 (1 select line)
 1-to-4 (2 select lines)
 1-to-8 (3 select lines)
 1-to-16 (4 select lines)

3. Arithmetic Logic Unit circuits:

a. Adder
b. Subtractor
c. Multiplier
d. Comparator

4. Decoder: A decoder is a logic circuit that accepts a set of inputs that represents a binary number and
activates only the output that corresponds to the input number.

In other words, a decoder circuit looks at its inputs, determines which binary number is present there,
and activates the one output that corresponds to that number; all other outputs remain inactive

There are 2N possible input combinations, from A0 to AN1. For each of these input combinations only
one of the M outputs will be active HIGH (1), all the other outputs are LOW (0).
5. Encoder: An encoder is a combinational logic circuit that essentially performs a “reverse” of decoder
functions. An encoder accepts an active level on one of its inputs, representing digit, such as a decimal
or octal digits, and converts it to a coded output such as BCD or binary.

Encoders can also be devised to encode various symbols and alphabetic characters.
The process of converting from familiar symbols or numbers to a coded format is called encoding.

6. Programmable Logic Array: it is a cost-effective method of realizing very large combinational circuits.
It consists of array of AND gates and followed by array of OR gates. The OR array is fixed and AND
array is programmable.

There are n input variables both the true and the complement form of the variables are fed to an AND
array. The maximum number of product terms which can be generated by the AND array with n
variables is 2n.. If m Boolean functions are to be realized as a sum of at most k products then an array of
m OR gates, each with k inputs, are required.

2. Sequential Circuit:
Sequential circuits consist of combinational logic as well as memory elements (used to store certain
circuit states). Outputs depend on BOTH current input values and previous input values (kept in the
storage elements).

1. Flip-Flops: it is a storage element, capable of storing 1-bit of information.

Types: S-R Flip-Flop

D-Flip-Flop
J-K Flip-Flop
T-Flip-Flop
 2. Counters: A counter is a sequential circuit consisting of a set of flip-flops which go through a sequence
of states on the application of clock pulses.

A counter that follows the binary number sequence is called a binary counter
n-bit binary counter: n flip-flops, count in binary from 0 to 2ⁿ-1

Counters are available in two types:

a. Synchronous Counters
b. Ripple Counters

3. Registers: A register is an extension of a flip-flop that can store multiple bits.

Registers are commonly used as temporary storage in a processor. They are faster and more convenient
than main memory.
Ex: 4-bit register
Shift register

Physical considerations in Integrated Circuits:

Fan In: The fan-in defined as the maximum number of inputs that a logic gate can accept. If number of input
exceeds, the output will be undefined or incorrect.

Fan Out: The fan-out is defined as the maximum number of inputs (load) that can be connected to the output of
a gate without degrading the normal operation.

Propagation delay: the propagation delay, or gate delay, is the length of time which starts when the input to
a logic gate becomes stable and valid to change, to the time that the output of that logic gate is stable and valid
to change.

Register transfer notation:

[R1]  [R2] + [R3], Where R1, R2, R3 are registers

Exercises:
Simplify: the following expression using Boolean Algebra:

1. xy + x'z + yz+ xy + x'z

2. (x+y).(xz+z).(y'+xz)'.(x'yz)
3. xy'+yz'+ x'z+x'y+y'z+xz'

Simplify the following Boolean function using K-map:

a. F(x,y,z) = ∑(1,2,3,6,7)
b. F(A,B,C) = ∑(0,2,3,4,6)
c. F(W,X,Y,Z) = ∑(0,1,2,4,5,7,11,15)
d. F(w, x,y,z) = ∑(0,1,2,3,6,7)
e. F(A,B,C,D) = ∑(0,4,6, 10,11,13)
f. F(A,B,C,D) = ∑(2,3,6, 7,14,15)
g. F(A,B,C,D) = ∑(1,3,5,8,9,11,15)+ d(A,B,C,D) = ∑(2,13)
h. F(A,B,C,D) = ∑(0,2,5,9,10,11,14,15) – Find SOP form
i. F(W,X,Y,Z) = ∑(2,3,4,5,6,7,11,14,15) – Find POS form
j. F(W,X,Y,Z) = ∑(0,1,2,3,7,8,10) – Find SOP, POS form
d(W,X,Y,Z) = ∑(5,6,11,15)