CAP College Self-Learning Series

for

Computer Science 1
(Computer Organization and Architecture)

Module 1
(Introduction to Computer Architecture)

Contents

Lesson 1. Basic Computer Architecture Models

Lesson 2. Binary Circuit Encoding
Lesson 3. Basic Unsigned Numeric Encoding
Lesson 4. Logic Gates and Circuits

i
 Computer Science 1

Computer Organization and Architecture

Module 1. Introduction to Computer Architecture

CAP College

149 Legaspi Street

Makati City

All rights reserved

CAP COLLEGE FOUNDATION, INC.

The Distance Learning Alternative System
149 Legaspi Street, Legaspi Village, 1229 Makati City, Philippines

ii
 INSTRUCTIONS TO THE STUDENT

At CAP College you learn through self-instructional modules, otherwise

known as CAPsels (short for CAP College Self-Learning Series), such as
the one you are now reading. It is important that you observe the
following instructions.
1. Every subject or course has an average of five modules, each
one of which contains two to five or more lessons. You must
satisfy the work prescribed by each module before you can sit
for the final examination that will determine whether you pass
or fail the course.
2. Make an effort to do some extra reading. The titles under Suggested
Readings are neither exclusive nor conclusive. Any reference book
on the subject will do.
3. Test your own progress by performing the Self-Progress Check
Tests (SPCTs) at the end of each lesson. Read the test
instructions carefully and understand them well. Do not look at
the answers while taking the test. Keep all answer sheets for
SPCTs in a particular module and send them to CAP COLLEGE
together with the Module Test. (See no. 5 below).
4. Check your answers with the key at the end of the module.
Unless there is specific instruction on how to score your paper,
compute it by dividing the correct answers with the total number
of points and multiply the quotient by 100. Keep your scores. If
you get 70% or higher, you pass; otherwise, you have to review the
lesson and do the re-test, if any, before advancing to the next one.
Take note that in some cases, the lesson tests are presented as
Activities. Do them the same way.
5. At the end of the module, perform the Module Test. Clip the
question sheet from the module and submit them with the answer
sheet to: The Dean of Studies, CAP College, 149 Legaspi Street,
Legaspi Village, Makati, for correction and grading. Do not forget
to enclose all accomplished SPCTs in each Module Test. (See
no. 3 above). Corrected tests will be returned to you with the
corresponding grade or further instruction, if needed. While
waiting, go on to the next module and observe the same study
procedure.
6. When you have accomplished all the modules of the subject
in which you are enrolled, you have to come to the College
to take the final tests in person. If you are in the province or
abroad, arrangements will be made for you to take them at a
pre-designated place or center nearest your residence.

iii
Module 1: Introduction to Computer Architecture

Lesson 1: Basic Computer Architecture Models

Basic Computer Architecture Models
The 5 Component Model
Hardware
Software
Data
Data vs. Information

The IPO(S) Model

Input:
Processing:
Output:
Storage:

Historical Progression of Computer Hardware and Software

1
The 5 Component Model
A computer system can be divided into 5 components:

1. Hardware
2. Software
3. Data
4. Procedures
5. Personnel

In studying Computer Systems' Architecture, only the first 3 of these are of direct
interest.

Hardware

• Processor
o a.k.a. CPU / Central Processing Unit
o Components:
1. ALU / Arithmetic Logic Unit: arithmetic & Boolean logic
operations
2. CU / Control Unit: instruction processing sequencing and
control
3. Interface Unit: (internal) bus structure
o Alternate View
1. Execution Unit: instruction circuits (including ALU)
2. Control Unit: instruction retrieval, sequencing, and EU sub-
circuit selection
3. Registers: limited, quick-access data "containers" and "flags"
4. Internal Bus Interface
• Input & Output Devices
o Actual electrical or electro-mechanical IO devices (e.g. keyboards,
printers, video monitor) will not be considered as significant in our
study of Computer Systems' Architectures.
• Input & Output Interface

External Bus Structure

collection of "wires" that carries power and signals between different
computer components
Channel
separate, special purpose IO processor connecting an IO device to the CPU (or
"main memory"); may perform signal conversion, timing control, buffering,
etc.
Communications
direct/indirect connection to other computer systems based on pre-agreed upon
"protocol" (shared rules for how communication is to take place

• Storage / Memory
o (Main) Memory / Primary Storage

addressed cells

2
 each containing a binary pattern
units:
byte
(typically 8 "bits") - character
word
(typically 32 "bits" but many different sizes are found on different computer
systems) - basic numeric unit; basic unit of data transfer
Kbytes
10
2 bytes (1024)
Mbytes
20
2 bytes (1,048,576)
Gbytes
30
2 bytes (1,300,109,824)
usage:

"active" data and instructions (i.e. instructions and data

currently being processed
John vonNeumann & stored program concept vs. Babbage's
engine with separate data and instruction stores

RAM vs. ROM

ROM is non-modifiable (by normal computer operation)

o (Secondary) Storage
long-term (inactive) data and program storage
examples: disk, tape, CD
units: typically stored in "blocks" of multiple words/bytes
(physical records)
o

MAIN SECONDARY
REGISTERS
MEMORY STORAGE
SPEED very fast fast slow
short-term
very short- (while
DURATION long-term
term program is
active)
RAM- data
POWER DOWN lost; ROM
data lost maintained
EFFECT - data
maintained
SIZE OF UNIT bit, byte, or byte or physical record
TRANSFERRED word word most common
indirect
ALU ACCESS yes no
only

Software

3
 • System Software
o Operating System
o Utilities (may be built into OS or external programs)
• Application Software
o Application tools: word processors, spreadsheet managers, etc.
o Corporate applications: in-house systems e.g. inventory management
• High-level vs. Machine-level Software
o High-level: "source" instructions in a language such as COBOL
o Machine-level: binary patterns with no immediate human meaning
o High-level instructions must be converted into Machine-level
instructions before they can be processed by a "processor"; this
conversion is a one-to-many process
• Instruction Classes
o data transfer (copying data)
o data transform (modifying data)
o instruction flow control (changing the default sequence)

Data
One of the major requirements of any computer system is the ability to represent and
manipulate values ("data").

In general, digital computers (the only type considered in this course) represent values
as patterns of "off" and "on" signals. Each value requires a different pattern (or, at
least, a pattern which is different from any other value of the same type). Different
types of values generally are represented using different "encoding schemes". An
"encoding scheme" specifies how many "off" and "on" signals are required for each
value, and provides a unique pattern of signals for each possible value.

Data vs. Information

Two terms common in any discussion of computer systems are "data" and
"information". The difference in meaning between these two terms is based on the
concept that "information" is "data" which has "meaning" to someone (or something)
outside of the computer system.

"Information" is "data" which has meaning. The most common task of a computer
system (especially when the input source and the output destination are the same) is to
transform data into information. In fact, this is sometimes used as the basis for
alternative definitions of a computer system .

The concept of "meaning" can be difficult. Generally, we think of "meaning" as

implying that something with intelligence exists for which the "data" has meaning.
When the output of a computer system is the automated control of some other system
(as in CAD, Computer Aided Manufacturing), we end up debating, the unresolved
question of what is meant by "intelligence".

4
The IPO(S) Model
A computer system can be thought of as a collection of components which together
are capable of 3 operations: Input, Processing, and Output. A fourth operation,
Storage, is also required for practical computer systems.

Note that the IPO(S), Input-Process-Output(-Storage), model is applied to at least two

different areas:

1. the collection of "equipment" that makes up a computer system

2. the "actions" that a computer system is capable of performing.

Input:
A computer system must include a method for accepting "data" and "instructions"
from outside the system.

Power or energy sources required to enable operation of the computer system are not
"inputs".

Processing:
A computer system must include the ability to change or "transform" data which has
been input. These "transformations" typically include (but are not limited to)

• selecting subsets of the data

• counting and accumulating totals of selected data values
• re-arranging the sequence or "format" of data

Output:
A computer system must include the ability to send processed data to outside the
system in a form that can be used by the "outside world". This "outside world" might
be the human "users" of the computer system, but alternatively could be electrical or
mechanical controls for automated equipment, or the "inputs" for some other system.
Storage:
We would not normally consider a collection to be a computer system unless it
included some form of memory of previous input or processed data. For example,
system composed of an electrical power supply, an on/off switch, a light bulb, and
appropriate wiring to connect the other three components would not normally be
considered to be a computer system (although it contains IPO elements of a basic
form). Replacing the on/off switch with a "toggle button", which would reverse the
current on/off "state" of the light, would give us something closer to a computer
system.

For the purposes of this course memory (or "storage") will be considered to be an
essential element of any computer system.

Historical Progression of Computer Hardware and Software

• Hardware

5
 1. mechanical (pre-computer)
2. electro-mechanical (hardwired with mechanical toggle switches)
3. vacuum tube (reduced hardwiring and mechanical toggles)
4. transistors (further reduction in hardwiring / mechanical toggles)
5. integrated circuits, LSI, VLSI (minimal hardwiring / mechanical
toggles)
issues of speed, heat, density, power consumption, reliability
RAM - Static (SRAM) & Dynamic (DRAM)
ROM - Programmable (PROM); Erasable (EPROM);
Electronically Erasable (EEPROM)

• Software
1. fixed application (no software)
2. direct load / wiring of application
3. re-usable "subroutines" (typically on hand-wired plug boards)
4. program loader (toggled routine / plug board) to load application to
RAM
5. operating system auto-loaded from secondary storage; "batch"
processing
6. multi-programming: overlapping concurrent IO operations with
processing; "batch" processing
7. interactive / multi-user / on-line processing
8. virtual tasking
9. distributed processing

6
Module 1: Introduction to Computer Architecture

Lesson 1: Basic Computer Architecture Models

Questions

Question 1
Describe the IPO(S) model associated with a computer system

Question 2
Describe the different categories of software

Question 3
What is meant by secondary storage

7
Module 1: Introduction to Computer Architecture

Lesson 1: Basic Computer Architecture Models

Answers

Question 1
Describe the IPO(S) model associated with a computer system

A computer system can be thought of as a collection of components which together

are capable of 3 operations: Input, Processing, and Output. A fourth operation,
Storage, is also required for practical computer systems.

Note that the IPO(S), Input-Process-Output(-Storage), model is applied to at least two

different areas:

1. the collection of "equipment" that makes up a computer system

2. the "actions" that a computer system is capable of performing.

Question 2
Describe the different categories of software

ok • System Software
o Operating System
o Utilities (may be built into OS or external programs)
ok • Application Software
o Application tools: word processors, spreadsheet managers, etc.
o Corporate applications: in-house systems e.g. inventory management
ok • High-level vs. Machine-level Software
o High-level: "source" instructions in a language such as COBOL
o Machine-level: binary patterns with no immediate human meaning
o High-level instructions must be converted into Machine-level
instructions before they can be processed by a "processor"; this
conversion is a one-to-many process
ok • Instruction Classes
o data transfer (copying data)
o data transform (modifying data)
o instruction flow control (changing the default sequence)

Question 3
What is meant by secondary storage

long-term (inactive) data and program storage

examples: disk, tape, CD
units: typically stored in "blocks" of multiple words/bytes (physical
records)

32
Module 1: Introduction to Computer Architecture

Lesson 2: Binary Circuit Encoding

What is a "code"?
Coding Schemes: Encoding and Decoding
Binary Codes

8
Digital Computers and Binary Circuits
There are two basic types of computers:
digital computers, and
analog computers.

Analog computers tend to be used for special purpose applications which involve
controlling manufacturing or similar "real-time" processes. They measure values
using a continuous range (typically, a continuous range of electrical voltages) to
manipulate environmental characteristics such as temperature and gas pressure. There
has been a tendency over the past 10 or 20 years to replace this type of computer with
digital computers which are connected to the "real-world" with "analog-to-digital"
interface devices.

Digital computers are, by far, the more common type. They are the only type which
we will consider in this course.

The main idea behind a digital computer is that, at least at a low level, values are
represented using "descrete", rather than "continuous" units. Instead of a value being
represented by any possible voltage between 0 volts and 5 volts (for example), a
digital computer might require that the value be represented by one of the voltages: 0
volts, 1.5 volts, 3.0 volts, or 4.5 volts.

Some early digital computer systems used a 10-level representation scheme (which
made working with our "normal" base 10 number system easy). Various other
numbers of levels have been attempted with varying degrees of success. Modern
digital computers, however, are restricted to a simple 2-level, or "binary" system.

As currently implemented, a "digital computer" is synonymous with a "computer

which uses a binary system for value representation".

What is a "code"?
A "code" is a symbol which represents something else, where the "something else"
could be any "real" or "abstract" entity. The "code symbol" has no meaning unless the
relationship between the symbol and the represented entity (called the coding system)
is known.

There are 3 main reasons for using codes:

1. communication: When we talk to someone-else, we use "words" which are

really codes for ideas (we actually use varying frequencies of sound waves as
codes for words, which are in turn codes for ideas). Alternately, we might use
flashes of light of different duration to send messages using Morse code.
Typically, computer components use patterns of "off" and "on" electrical
signals to transmit information to other components.
2. internal representation: When we remember or think about some object, that
object is represented in our brain as some complex collection of connections
of neurons (it is interesting to note that the neurological connections used to
represent the same object in the brains of two different people will be quite

9
 different). In a computer information is internally represented using the same
kind of "off"/"on" patterns used for communication.
3. encryption: Encryption can be thought of as a method of limiting
communication. By using a system of codes known only to the originator and
the intended receiver, the ability of someone (or something) else
understanding the message is avoided.

Codes are used to identify a particular entity (or value) from within a larger collection
of possible values. This "collection of possible values" is called the domain. The
Morse code, for example, provides a collection of "code values" for letters and other
character symbols. The domain of the Morse code is the collection of "character
symbols". Any code system has a limited domain of things it can represent. When
information is to be represented using a code, it is important to classify the
information in terms of an appropriate domain, in order to select an appropriate code
system.

A code system which assigned the collection of symbols:

@#$%
to the entities:
spring summer fall winter
respectively, has a domain which would be appropriate if the information to be
encoded were "my favourite season"; its domain would not be appropriate if the
information were "my age".

Within any particular domain, we usually think of the relationship between codes and
represented entities as being one-to-one; that is, each code stands for only one entity
and each entity is only represented by a unique code. Note, however, that in certain
situations, one-to-many or many-to-one relationships between codes and entities may
be appropriate.

Coding Schemes: Encoding and Decoding

An encoding scheme is a method for determining the code to be used to represent
some specific entity. With a "proper" encoding scheme, a single entity may only be
"encoded" into one, unique code value.

A decoding scheme is a method for determing the entity being represented by a

particular code. With a "proper" decoding scheme, a single code can represent only
one, unique entity.

A coding system is a combination of encoding and decoding schemes.

Entities may belong to many "proper" coding systems (same entity, different codes)
provided that there is a unique relationship between the entity and its code in each
system.

Similarly, codes may belong to many ("proper") coding systems (same code
representing a different entity in a different system).

10
Coding systems are often defined using a tabular representation. For example, the
Morse code could be defined by the table:

A .- N -. 0 -----
B -... O --- 1 .----
C -.-. P .--. 2 ..---
D -.. Q --.- 3 ...--
E . R .-. 4 ....-
F ..-. S ... 5 .....
G --. T - 6 -....
H .... U ..- 7 --...
I .. V ...- 8 ---..
J .--- W .-- 9 ----.
K -.- X -..- Fullstop .-.-.-
L .-.. Y -.-- Comma --..--
M -- Z --.. Query ..--..

Although it might, at first, seem useless, it is possible to have an encoding system

with no corresponding decoding system, a system whereby entities can be
transformed into codes, with no ability to perform the reverse transformation. A
simple example of where this is often used is in "password systems"; the original
password is encoded and stored in its encoded form; when someone wants to use the
"passworded" system, he/she enters the password which is encoded and compared to
the encoded original password; in this way the real password is never stored in a form
which could be accessed by an illegal "hacker".

Binary Codes
Although a single binary code system (one with only two code values) is extremely
restrictive, very complex code systems can be developed using sequences or patterns
of binary code values.

Almost all computer systems employ only code systems in which the codes are
composed of multiple binary values.

11
Module 1: Introduction to Computer Architecture

Lesson 2: Binary Circuit Encoding

Questions

Question 1
What is the main concept behind a digital computer

Question 2
Discuss the main reasons for using code

Question 3
What is the difference between a coding and decoding scheme

12
Module 1: Introduction to Computer Architecture

Lesson 2: Binary Circuit Encoding

Answers

Question 1
What is the main concept behind a digital computer

Digital computers are, by far, the more common type. They are the only type which
we will consider in this course.

The main idea behind a digital computer is that, at least at a low level, values are
represented using "descrete", rather than "continuous" units. Instead of a value being
represented by any possible voltage between 0 volts and 5 volts (for example), a
digital computer might require that the value be represented by one of the voltages: 0
volts, 1.5 volts, 3.0 volts, or 4.5 volts.

Question 2
Discuss the main reasons for using code

There are 3 main reasons for using codes:

1. communication: When we talk to someone-else, we use "words" which are

really codes for ideas (we actually use varying frequencies of sound waves as
codes for words, which are in turn codes for ideas). Alternately, we might use
flashes of light of different duration to send messages using Morse code.
Typically, computer components use patterns of "off" and "on" electrical
signals to transmit information to other components.
2. internal representation: When we remember or think about some object, that
object is represented in our brain as some complex collection of connections
of neurons (it is interesting to note that the neurological connections used to
represent the same object in the brains of two different people will be quite
different). In a computer information is internally represented using the same
kind of "off"/"on" patterns used for communication.
3. encryption: Encryption can be thought of as a method of limiting
communication. By using a system of codes known only to the originator and
the intended receiver, the ability of someone (or something) else
understanding the message is avoided.

Question 3
What is the difference between a coding and decoding scheme

An encoding scheme is a method for determining the code to be used to represent

some specific entity. With a "proper" encoding scheme, a single entity may only be
"encoded" into one, unique code value.

33
A decoding scheme is a method for determing the entity being represented by a
particular code. With a "proper" decoding scheme, a single code can represent only
one, unique entity.

A coding system is a combination of encoding and decoding schemes.

34
Module 1: Introduction to Computer Architecture

Lesson 3: Basic Unsigned Numeric Encoding

Binary Encoding
Number of Circuits Required for Encoding
Unsigned Binary Encoding
Multi-Column Addition
Multi-Column Subtraction
The "Carry" Flag
· Addition
· Subtraction
The "Zero" Flag
Multiplication - Double Word Result
Division - 2 Results

13
In order to represent and manipulate numeric values within the circuits of a computer
system it is necessary to use some coding scheme whereby each number can be
represented or "encoded" by the pattern of electrically on/off states in a collection of
circuits. For a computer, the simplest and fastest scheme for encoding numeric values
is the Unsigned Binary Encoding scheme.

Binary Encoding

• replacement or representation of some discrete data object (number, character,

etc.) by an on/off circuit pattern
• a "binary encoding system" is a one-to-one function for encoding a set of
related data object (for example, all integer values between 0 and 100
inclusive, or all the letters of the alphabet) into unique binary patterns.

Number of Circuits Required for Encoding

• each circuit will be in either one of two states : "on" or "off" (for convenience
we will write these using 1 for "on" and 0 for "off")
• only two possible patterns are possible for a single circuit: 0 and 1
• with two circuits, four patterns become possible: 00, 01, 10, and 11
• each time another circuit is added, the number of patterns doubles; half of the
new patterns will have this additional circuit turned on and the other half will
have it turned off.
•

Number of Number of
Circuits Patterns

1 2

2 4

3 8

4 16

.... ....

8 256

10 1024 (1K)

16 65536 (64K)

20 1048576 (1M)

n 2n

14
 • in order to encode a collection of data objects, the encoding scheme must have
at least as many patterns available as there are objects to be encoded
• for example, if we wished to encode the integer values from 0 to 9, a
minimum of 4 circuits (providing 16 patterns) would be required

The Decimal Odometer Analogy

• most cars have an odometer which records the total distance traveled (in either
kilometres or miles)
• a typical odometer might have 6 digit "wheels" with the right most wheel
rotating most rapidly from 0 up to 9 and back to 0 again every 10 kilometers
(or miles); the next wheel to the left would only make this change every 100
kilometers; etc.
• a 6 digit odometer only has 1,000,000 different values (0 to 999999 inclusive);
a car driven 6,372,945 kilometers and one driven 7,372,945 kilometers would
have the same odometer reading
• notice that the 6 digit wheels are built-into the car, and do not automatically
expand to 7 digit wheels once the car passes 999,999 kilometers
• because the decimal positional notation is so familiar to use, we recognize
without much thought that an odometer reading of 372945 means
o 3 x 100000
o +7 x 10000
o +2 x 1000
o +9 x 100
o +4 x 10
o +5 x 1
• each digit wheel of an odometer is analogous to a single circuit
• where each digit has 10 different values (0 to 9), a single circuit only has 2 ( 0
and 1)
• the odometer within a car is analogous to a "word" in a computer system (i.e. a
word in a computer system is the basic unit for representation of a simple
numeric value)
• different makes of cars may have a different number of wheels in their
odometers; different makes of computers may have a different number of
circuits (bits) in their words
• the number of circuits (bits) in a specific computer's word unit is "fixed" and
can not be modified just because all the patterns have been used up
• a 6-bit word with a pattern of 100101, if viewed as a positional system
analogous to the 6-digit odometer, would mean
o 1 x 32 (2 x 2 x 2 x 2 x 2)
o +0 x 16(2 x 2 x 2 x 2)
o +0 x 8(2 x 2 x 2)
o +1 x 4(2 x 2)
o +0 x 2
o +1 x 1

Unsigned Binary Encoding

15
 • notice that to this point we have not been concerned with representing
negative values; we have been dealing with "unsigned" (i.e. assumed to be 0
or positive) numbers
• the "bits" or circuits of a computer "word" are imagined to be lined up in a
horizontal row regardless of their actual physical positioning
• each bit has its own "weight" with the right-most bit having a weight of 1 and
every other bit having a weight which is double that of the bit to its immediate
right
• notice that the sum of the weights of all bits to the right of any specific bit is
always one less that the weight of that bit
• in the (unsigned) binary encoding scheme, the numeric value being encoded is
the sum of the weights of the bits which are turned on
• for example using an 8-bit "word"

pattern in word: off on off off on on off off

(0) (1) (0) (0) (1) (1) (0) (0)

weight 128 64 32 16 8 4 2 1

the value of this encoded word (01001100) would be 64 + 8 + 4 = 76

• conversely to encode a particular value, for example 137, in an 8-bit word

using the (unsigned) binary encoding scheme
• the bit with weight 128 must be on (since the sum of all the remaining bits
only adds up to 127)
• if the bit with weight 128 is on, then the remaining bits must contain a pattern
that adds up to 137 - 128 = 9
• the bits with weights 64, 32, and 16 must be off, since if any of them were on
the total would add up to too much
• the bit with weight 8 must be on, leaving 9 - 8 = 1 to be represented by the
remaining bits
• the bits with weights 4 and 2 must be off
• the bit with weight 1 must be on
• therefore, the 8-bit (unsigned) binary encoded pattern for 137 is 10001001

weight 128 64 32 16 8 4 2 1

pattern 1 0 0 0 1 0 0 1

Multi-Column Addition

• multi-column addition is done one column at a time, starting with the right-
most column

16
 • the addition of a column of digits results in two values: the "column result"
and a "carry" value which must be included when adding the next column to
the left.
• when adding two numbers, each column except for the right-most, requires the
addition of three digits, two from the numbers and a (possibly zero) carry from
the column to its right
• therefore, the addition of two (unsigned) binary values requires the ability to
add three single bits at a time

3-Bit Addition: The 8 Possible Input Combinations and Their Outputs

bit values being added 0 0 0 0 1 1 1 1

0 0 1 1 0 0 1 1

(carry in from previous column) 0 1 0 1 0 1 0 1

column result 0 1 1 0 1 0 0 1

carry to next column 0 0 0 1 0 1 1 1

Examples:
(4-bit "words")

Multi-Column Subtraction

• although not always taught in primary school in this fashion, subtraction can
be done in a similar manner, one column at a time (primary school subtraction
often teaches children to skip over several (zero valued) columns when
"borrowing" enough to perform a "proper subtraction

3-Bit Subtraction: The 8 Possible Input Combinations and Their Outputs

"Subtrahend" 0 0 0 0 1 1 1 1
minus "minuend" 0 0 1 1 0 0 1 1

minus borrow from previous 0 1 0 1 0 1 0 1

column result 0 1 1 0 1 0 0 1

borrow from next column 0 1 1 1 0 0 0 1

17
Examples:
(4-bit "words")

The "Carry" Flag

• Addition
o as we have already seen, every column in a (binary) addition produces
a "carry" signal for the next column
o for the left-most column, there is no subsequent column for this signal
to go to
o if there is a carry (i.e. the carry signal is 1 / the Carry flag is on) out of
the left-most column for an addition of two (unsigned) binary encoded
values, it means that the actual result is two large to fit into the number
of bits/circuits available (for this computer)
o the Carry flag should be checked following any addition of (unsigned)
binary values, to ensure that the results are correct; the "checking"
requires execution of a separate instruction following the addition. For
some mythical processor this sequence might look like:
LOAD A FROM @3054 'copy value from memory at address
3054 to ALU working "register" A
LOAD A FROM @4190 'copy value from memory at address
4190 to ALU working "register" B
ADD_TO A FROM B 'replace value in "register" A with sum
of original values
IF_CARRY_GOTO ERROR_ROUTINE 'go somewhere else
to handle error if it occurred
...value in "register" A is OK
• Subtraction
o Subtraction works the same way as Addition except that we use a
"borrow from next column" signal instead of a "carry to next column"
o rather than implement a separate "Borrow" flag, most systems re-use
the "Carry" flag to record the final column "need to borrow" indicator
o following an (unsigned) binary subtraction, if the Carry flag is on, then
1. the result is wrong (as an unsigned binary value)
2. an attempt was made to subtract a larger number from a smaller
number
o Subtracting and then checking the Carry flag can therefore be used as a
method for determining the relative size of two numbers

The "Zero" Flag

• in addition to a "Carry" flag, all computer processors have a "Zero" flag (or
some functional equivalent).

18
 • the "Zero" flag is turned on, when all "result" output bits are turned "off" i.e.
when the result is zero; the "Zero" flag will be turned off if any of the result
bits are "on"
• this flag is set/reset by the bit manipulation operations (OR, AND, XOR,
NOT) and by the basic ADD and SUBTRACT operations; other instructions
may set/reset the Zero flag, but these vary among different processors.
• to test to determine if two values are equal, subtract one from the other and
then check the zero flag; if it is on, the values are equal

Multiplication - Double Word Result

• binary multiplication is performed as a series of left shifts and additions

• notice that when multiplying two 3-digit (decimal) numbers, the result may
require as many a 6 digits
• similarly when multiplying two 16-bit (unsigned binary encoded) words, the
computer's ALU must allow for as many as 32 bits in the result
• a simple single-bit flag is not sufficient to handle this problem

Example:
(4-bit "words"
8-bit "double-word" result)

Division - 2 Results

• unlike addition, subtraction, and multiplication, Division produces two results:

a Quotient and a Remainder when dealing with integers values (such as
unsigned binary encoded values)
• a computer's execution unit must make some provision for handling this
double result; however, the specific method for handling this varies from
computer to computer, and otten within a single computer, different
instructions may handle this problem in different ways.

19
Module 1: Introduction to Computer Architecture

Lesson 3: Basic Unsigned Numeric Encoding

Questions

Question 1
Describe the term binary encoding

Question 2
How does multi column addition operate

Question 3
What is the “zero” flag

20
Module 1: Introduction to Computer Architecture

Lesson 3: Basic Unsigned Numeric Encoding

Answers

Question 1
Describe the term binary encoding

replacement or representation of some discrete data object (number, character, etc.) by

an on/off circuit pattern

a "binary encoding system" is a one-to-one function for encoding a set of related data
object (for example, all integer values between 0 and 100 inclusive, or all the letters
of the alphabet) into unique binary patterns.

Question 2
How does multi column addition operate

• multi-column addition is done one column at a time, starting with the right-
most column
• the addition of a column of digits results in two values: the "column result"
and a "carry" value which must be included when adding the next column to
the left.
• when adding two numbers, each column except for the right-most, requires the
addition of three digits, two from the numbers and a (possibly zero) carry from
the column to its right
• therefore, the addition of two (unsigned) binary values requires the ability to
add three single bits at a time

Question 3
What is the “zero” flag

• in addition to a "Carry" flag, all computer processors have a "Zero" flag (or
some functional equivalent).
• the "Zero" flag is turned on, when all "result" output bits are turned "off" i.e.
when the result is zero; the "Zero" flag will be turned off if any of the result
bits are "on"
• this flag is set/reset by the bit manipulation operations (OR, AND, XOR,
NOT) and by the basic ADD and SUBTRACT operations; other instructions
may set/reset the Zero flag, but these vary among different processors.
• to test to determine if two values are equal, subtract one from the other and
then check the zero flag; if it is on, the values are equal

35
Module 1: Introduction to Computer Architecture

Lesson 4: Logic Gates and Circuits

Basic Gates
Basic Binary Encoding
Basic Binary Addition
Logic Gate Application for Binary Addition
Multiplexor
Memory Circuits
Application of Logic Gates to Basic Binary Encoding
Fast Operations That Require No Operational Logic Gates
· Shift
· Rotate
Bit Manipulation with a Single Layer of Operational Gates
Unsigned Binary Addition - Multiple Layers of Gates
· Addition of 2 Bits
· Addition of 2 Multi-Bit Words
More Complex Instructions and CISC Computers
o CISC - Complex Instruction Set Computer
o Factors Which Reduce Instruction Execution Speed
o Alternative: RISC - Reduced Instruction Set Computer
Binary Operation Flags

21
The functionality of even the most complex computer is achieved by connecting
simple logic gates into operational circuits.

Basic Gates
There are four basic logic gates. The symbols used for these gates and their "truth
tables" are given below (note that these are not the "standard" electrical engineering
symbols for these gates).

• NOT : unary input; output is reverse of input

OUTPUT

INPUT

0 1

1 0

• AND : binary inputs: output is "on" only if both inputs are "on"

INPUT OUTPUT
S

Input- Input-2
1

0 0 0

0 1 0

1 0 0

1 1 1

• OR : binary inputs: output is "off" only if both inputs are "off"

22
 INPUT OUTPUT
S

Input- Input-2
1

0 0 0

0 1 1

1 0 1

1 1 1

• XOR : binary inputs: output is "on" only if the inputs are different

INPUT OUTPUT
S

Input- Input-2
1

0 0 0

0 1 1

1 0 1

1 1 0

Basic Binary Encoding

• requires a collection of circuits making up a "word"

• circuits are typically pictured a arranged in a horizontal row

23
 • each circuit has a unique "weight" within the word

• right-most circuit has a weight of one (1)

• each remaining circuit has a weight which is twice as much as the weight of
the circuit to its right.

• the number represented by a "word" is the sum of the weights of the circuits
which are turned on.

Example (by common convention "0" is used to represent a circuit which is

"off" and "1" is used to represent a circuit which is "on"):

• a "word" composed of 5 circuits (a 5 "bit" word) would have circuit weights of

16, 8, 4, 2, and 1 as viewed from left to right respectively

• if this word had a circuit pattern of 01001, then only the two circuits with
weights 8 and 1 would be "on" and the number represented by the pattern in
this word would be 9 (8+1)

Basic Binary Addition

0+0 = 0

0+1 = 1

1+0 = 1

1+1 = 10 (i.e. the result in this "column" is 0 with a "carry" of 1 that needs to be
added to the next position to the left)

Logic Gate Application for Binary Addition

Truth Table for Single Bit Addition:

INPUTS OUTPUTS

A B C R

0 0 0 0

24
 0 1 0 1

1 0 0 1

1 1 1 0

Addition of "words" with multiple "bits" extends this logic.

Selector

A collection of input wires or "bits" is "decoded" to turn on ("select") exactly one

(output) circuit. (This is contrary to Englander's definition in "The Architecture of
Computer Hardware and Software", page 720).

Multiplexor
A single input wire (at any one time) from a collection of possible inputs, is
"encoded" into a pattern on a smaller collection of wires. A multiplexor performs the
reverse function of a "selector". (The 2-input to 1-output ciruit described by
Englander, as noted above, is a multiplexor).

25
Memory Circuits
A single memory "bit" must have the ability

• to have a data value of either 0 or 1 "written" to it,

• to retain that value after the "write" request is done, and
• to return that retained value at a later time in response to a "read" request.

As another way of thinking about it:

• Sometimes the memory bit is Enabled (to be read from / written to); other
times it is in a "passive" remembering state
• When enabled, a signal must indicate if we are trying to Read from it (the
alternative being, write to it)
• If we are writing to it, an Input data value (0/1) must be provided
• If we are reading from it, an Output path must be provided

Of course, to be very useful, we need many (millions) of these memory bits. A

"Selector" circuit is then required to permit us to access a particular bit (or collection
of bits) based on an input "address".

Application of Logic Gates to Basic Binary Encoding

Simple binary logic gates operate on one pair of single bits at a time, but most basic
computer operations work on pairs of multiple bits. In general this increases the speed
at which the computer operates. For example, comparing two patterns of 16 bits each
in parallel should be 16 times faster than performing 16 separate comparisons on pairs
of single bits.

26
Each logic gate takes a certain (small) amount of time to respond to a change in its
inputs; this is called the gate switching time. The time required to perform any basic
computer instruction depends upon the maximum number of logic gates signals must
pass through to complete the instructional operation (plus some other "overhead"
factors.

The fastest instructions should therefore be those which involve no operational logic
gates: the shifts and rotates, followed by those which involve only one level of
operational logic gates: the bit level logical operators, and so on.

In actual practice, computer instructions are organized so as to start on regular internal

clock pulses (a 200MHz clock, for example, providing 200 million pulses per
second). Even at today's high clock speeds, modern gate switching times in VLSI is
fast enough that multiple logic gates can be managed within a single clock pulse
"frame"; however, when the instruction becomes complex enough that the number of
logic gates on the longest path reaches a certain level, the instruction will require
multiple clock pulse "frames" to complete.

Fast Operations That Require No Operational Logic Gates

• Shift
o Left Shift - each input bit is reproduced as an output bit one position
further to the left except for the left-most input bit which is ignored (or
copied to a status flag); the right-most output bit is set to 0.

For example, LeftShift of (00110101) would be (01101010)

Note, as a result of this "shift" each bit gets moved to a position with
double the weight of its original position, and (provided no 1-valued
bit is lost off the left-end) the result for an unsigned binary encoded
number is twice the original value.

o Right Shift (Logical) - same as the Left Shift except for the direction
of the shift; RightShift of (00110101) would be (00011010), with the
right-most 1 being lost (or copied to a status flag).

For an unsigned binary encoded number, the RightShift is a fast

method for dividing by 2.

o Right Shift (Arithmetic) - many computers also include another

version of the RightShift in which the left-most output bit is a copy of
the left-most input bit (instead of being automatically 0).

This is sometimes called the "Arithmetic" Right Shift because of its

use with a signed binary encoding scheme, called 2's Complement.

27
 • Rotate
o Left Rotate and Right Rotate are identical to the corresponding
"Shift" operations except that the input bit which is lost in the Shift
result is "rotated" to the other end of the output pattern and used
instead of the automatic 0.

For example, RightRotate of (00110101) would be (10011010).

Bit Manipulation with a Single Layer of Operational Gates

Note that while these computer operations have the same names as the logic gates on
which they are based, they operate on two words in parallel and not on a pair of bits.

• OR - Turning Selected Bits of a Word "On"

o If we wish to force the right-most two bits of a 6-bit word to be "on"
(we want the result to look like xxxx11, where the x's represent the
original bit values),OR the original pattern with 000011

• AND - Turning Selected Bits of a Word "Off"

o If we wish to force the middle two bits of a 6-bit word to be "off" (we
want the result to look like xx00xx)AND the original pattern with
110011

• XOR - "Toggling" Selected Bits of a Word

o If we wish to reverse the left-most bits of a 6-bit wordXOR the original
pattern with 110000

• NOT - Reversing All Bits of a Word

o NOT the original pattern (which is the same as XOR'ing with 111...1)

Unsigned Binary Addition - Multiple Layers of Gates

• Addition of 2 Bits

28
 o note that although there are two logic gates there is only one layer of
gates required
• Addition of 2 Multi-Bit Words

o note that because of the carry requirement from each column to the
next, the number of layers of gates increases with the number of bits in
a word; effectively, from a gate switching point of view, addition of
32-bit words should take 4 times longer than addition of 8-bit words.

More Complex Instructions and CISC Computers

o CISC - Complex Instruction Set Computer
o Factors Which Reduce Instruction Execution Speed
larger number of logic gate layers in the instruction circuit
requirements to access data value in external memory (with
sub-factors:
the number of accesses required, and the type/speed of the
external memory)
o Alternative: RISC - Reduced Instruction Set Computer

Binary Operation Flags

Performing arithmetic operations produce results which require more space

(more circuits/bits) than were provided by individual input data values.

29
For simple operations, such as addition and subtraction, this "extra" space is
only one bit and can be handled by the use of a "Carry/Borrow" (single-bit)
flag. Other operations, such a multiplication and division, require different
methods for handling this problem; these methods are much less standard and
vary considerably from computer to computer.

30
Module 1: Introduction to Computer Architecture

Lesson 4: Logic Gates and Circuits

Questions

Question 1
Describe and illustrate the basic logic gates

Question 2
Describe the function of a multiplexor

Question 3
What abilities must a memory have

31
Module 1: Introduction to Computer Architecture

Lesson 4: Logic Gates and Circuits

Answers

Question 1
Describe and illustrate the basic logic gates

There are four basic logic gates. The symbols used for these gates and their "truth
tables" are given below (note that these are not the "standard" electrical engineering
symbols for these gates).

• NOT : unary input; output is reverse of input

OUTPUT

INPUT

0 1

1 0

• AND : binary inputs: output is "on" only if both inputs are "on"

INPUT OUTPUT
S

Input- Input-2
1

0 0 0

0 1 0

1 0 0

1 1 1

36
 • OR : binary inputs: output is "off" only if both inputs are "off"

INPUT OUTPUT
S

Input- Input-2
1

0 0 0

0 1 1

1 0 1

1 1 1

• XOR : binary inputs: output is "on" only if the inputs are different

INPUT OUTPUT
S

Input- Input-2
1

0 0 0

0 1 1

1 0 1

1 1 0

Question 2
Describe the function of a multiplexor

A single input wire (at any one time) from a collection of possible inputs, is
"encoded" into a pattern on a smaller collection of wires. A multiplexor performs the
reverse function of a "selector". (The 2-input to 1-output ciruit described by
Englander, as noted above, is a multiplexor).

37
Question 3
What abilities must a memory have

A single memory "bit" must have the ability

• to have a data value of either 0 or 1 "written" to it,

• to retain that value after the "write" request is done, and
• to return that retained value at a later time in response to a "read" request.

As another way of thinking about it:

• Sometimes the memory bit is Enabled (to be read from / written to); other
times it is in a "passive" remembering state
• When enabled, a signal must indicate if we are trying to Read from it (the
alternative being, write to it)
• If we are writing to it, an Input data value (0/1) must be provided
• If we are reading from it, an Output path must be provided

38