CENG105
Copyright © 2019 Pearson Education, Ltd. All Rights Reserved.
Computer Science An Overview
13th Edition, Global Edition
Chapter 1
Data Storage
Copyright © 2019 Pearson Education, Ltd. All Rights Reserved.
Chapter 1: Data Storage
• 1.1 Bits and Their Storage
• 1.2 Main Memory
• 1.3 Mass Storage
• 1.4 Representing Information as Bit Patterns
• 1.5 The Binary System
• 1.6 Storing Integers
• 1.7 Storing Fractions
• 1.8 Data and Programming
• 1.9 Data Compression
• 1.10 Communications Errors
Copyright © 2019 Pearson Education, Ltd. All Rights Reserved.
Binary vs. Decimal
• Binary is a base two system which works just like our
decimal system.
• Considering the decimal number system, it has a set of
values which range from 0 to 9.
• The binary number system is base 2 and therefore
requires only two digits, 0 and 1.
Copyright © 2019 Pearson Education, Ltd. All Rights Reserved.
Why binary?
•This question can be answered by a series
of relevant questions!
– How to store the values in hardware?
– How to automatically perform arithmetic operations on numbers?
–…
•The fundamental question is can we find
out a physical material to stably maintain n
different status?
Copyright © 2019 Pearson Education, Ltd. All Rights Reserved.
How to store?
• Advancement in material science guarantees that binary status can
be represented with no ambiguity.
• Silicon and many other semiconductor materials can present one of
two status at any given time, and can retain a status for a long time.
• Generally speaking, the more status to maintain, the more difficult to
find out such a material.
• Basically speaking, binary system simplifies information
representation and information processing in electronic world.
• Binary number system is the easiest one to
implement from the hardware point of view.
• So computers use binary numbers.
Copyright © 2019 Pearson Education, Ltd. All Rights Reserved.
1.1 Bits and Their Storage
• Bit: Binary Digit (0 or 1)
• Bit Patterns are used to represent information
– Numbers
– Text characters
– Images
– Sound
– And others
Copyright © 2019 Pearson Education, Ltd. All Rights Reserved.
Boolean Operations
• Boolean Operation: An operation that manipulates
one or more true/false values
• Specific operations
– AND
– OR
– XOR (exclusive or)
– NOT
Copyright © 2019 Pearson Education, Ltd. All Rights Reserved.
Figure 1.1 The possible input and output
values of Boolean operations AND, OR, and
XOR (exclusive or)
Copyright © 2019 Pearson Education, Ltd. All Rights Reserved.
Gates
• Gate: A device that computes a Boolean operation
– Often implemented as small electronic circuits called
transistors
– Can be constructed from a variety of other
technologies
– Provide the building blocks from which computers
are constructed
Copyright © 2019 Pearson Education, Ltd. All Rights Reserved.
Figure 1.2 A pictorial representation of AND, OR,
XOR, and NOT gates as well as their input and
output values
Copyright © 2019 Pearson Education, Ltd. All Rights Reserved.
Flip-flops
• Circuits built from gates that act as a fundamental unit
of computer memory
– One input line is used to set its stored value to 1
– One input line is used to set its stored value to 0
– While both input lines are 0, the most recently stored
value is preserved
– Basically we maintain the last state of the component
(unless we maintain the electricity to system)
Copyright © 2019 Pearson Education, Ltd. All Rights Reserved.
Figure 1.3 A simple flip-flop circuit
Copyright © 2019 Pearson Education, Ltd. All Rights Reserved.
A ‘bit’ (from Binary + digIT) is the smallest unit of memory, also the
unit of measurement of data information.
WHY 8 bit?
• To some extend,
8-bit is enough
to represent all
1 bit English
characters and
1 byte Arabic numbers.
A byte used to
be the basic unit
to hold an
4 bytes = 1 word individual
System dependent. character in a
text document.
Generally register sizes:
in 32 bit system -> 4 bytes
in 64 bit system -> 8 bytes
In windows legacy 2 bytes
Copyright © 2019 Pearson Education, Ltd. All Rights Reserved.
• 1 bit
• 1 byte = 8 bits
• 1 KB = 210 bytes = 1024 bytes (!=1000)
• 1 MB = 1 k k bytes = 210 * 210 bytes
• 1 GB = 210 * 210 * 210 bytes
• 1 Terabyte = 210 * 210 * 210 * 210 bytes
• 1 petabyte = 210 * 210 * 210 * 210 * 210 bytes
(2 to the 50th power )
• 1 exabyte= 260
• 1 zettabyte = 270
• 1 yottabyte = 280
Copyright © 2019 Pearson Education, Ltd. All Rights Reserved.
Hexadecimal Notation
• Hexadecimal notation: A shorthand notation for long
bit patterns
– Divides a pattern into groups of four bits each
– Represents each group by a single symbol
• Example: 10110101 becomes 0xB5
– 1011 = B (Eleven in decimal)
– 0101 = 5
Copyright © 2019 Pearson Education, Ltd. All Rights Reserved.
Hex decimal binary
0x10 16 10000
0xF0 240 11110000
0xFF 255 11111111
Copyright © 2019 Pearson Education, Ltd. All Rights Reserved.
Figure 1.6 The hexadecimal coding system
Copyright © 2019 Pearson Education, Ltd. All Rights Reserved.
1.2 Main Memory
• Cell: A unit of main memory (typically 8 bits which is
one byte)
– Most significant bit: the bit at the left (high-order)
end
– Least significant bit: the bit at the right (low-order)
end
Copyright © 2019 Pearson Education, Ltd. All Rights Reserved.
Main Memory Addresses
• Address: A “name” that uniquely identifies one cell in
the computer’s main memory
– The names are actually numbers.
– These numbers are assigned consecutively starting
at zero.
– Numbering the cells in this manner associates an
order with the memory cells.
Copyright © 2019 Pearson Education, Ltd. All Rights Reserved.
Memory Terminology
• Random Access Memory (RAM): Memory in which
individual cells can be easily accessed in any order
• Dynamic Memory (DRAM): RAM composed of volatile
memory
Copyright © 2019 Pearson Education, Ltd. All Rights Reserved.
1.3 Mass Storage
• Additional devices:
– Magnetic disks – Magnetic tapes
– CDs – Flash drives
– DVDs – Solid-state drives
• Advantages over main memory
– Less volatility
– Larger storage capacities
– Low cost
– In many cases can be removed
Copyright © 2019 Pearson Education, Ltd. All Rights Reserved.
Mass Storage Performance
• Bandwidth: The total amount of bits that can be
transferred in a unit of time
• Latency: The total time between the request for data
transfer and its arrival
Copyright © 2019 Pearson Education, Ltd. All Rights Reserved.
Flash Drives
• Flash Memory – circuits that traps electrons in tiny
silicon dioxide chambers
• Repeated erasing slowly damages the media
• Mass storage of choice for:
– Digital cameras – Smartphones
• SD Cards provide GBs of storage
Copyright © 2019 Pearson Education, Ltd. All Rights Reserved.
1.4 Representing Information as Bit
Patterns
• Many different kinds of information can be encoded as
bit patterns
• Systems for encoding information have been
established for
– Text
– Numeric Data
– Images
– Sound
– Other data
Copyright © 2019 Pearson Education, Ltd. All Rights Reserved.
Representing Text
• Each character (letter, punctuation, etc.) is
assigned a unique bit pattern.
– ASCII: Uses patterns of 7-bits to represent most
symbols used in written English text
– ISO developed a number of 8 bit extensions to
ASCII, each designed to accommodate a major
language group
– Unicode: Uses patterns up to 21-bits to represent
the symbols used in languages world wide, 16-bits
for world’s commonly used languages
Copyright © 2019 Pearson Education, Ltd. All Rights Reserved.
Image from: Jbwyatt.com
Copyright © 2019 Pearson Education, Ltd. All Rights Reserved.
Figure 1.11 The message “Hello.” in
ASCII or UTF-8 encoding
Copyright © 2019 Pearson Education, Ltd. All Rights Reserved.
Representing Numeric Values
• Binary notation: Uses bits to represent a number in
base two
– All numeric values in a computer are stored in
sequences of 0s and 1s
– Counting from 0 to 8:
– 0000, 0001, 0010, 0011, 0100, 0101, 0110,
0111, 1000
Copyright © 2019 Pearson Education, Ltd. All Rights Reserved.
Representing Images
• Bit map techniques
– Pixel: “picture element” represents one dot
– RGB: Red, Green, and Blue components
– Luminance and chrominance
– Problems with scaling up images
• Vector techniques
– Represent images with geometric structures
– Scalable
– TrueType and PostScript
Copyright © 2019 Pearson Education, Ltd. All Rights Reserved.
Representing Sound
• Sampling techniques that record actual audio
– Long-distance telephone: 8000 samples/sec
– CD sound: 44,100 samples/sec
• MIDI stores directions for making sound
– Used in music synthesizers
– Encodes which instrument, note, and duration
Copyright © 2019 Pearson Education, Ltd. All Rights Reserved.
Figure 1.12 The sound wave represented by the
sequence 0, 1.5, 2.0, 1.5, 2.0, 3.0, 4.0, 3.0, 0
Copyright © 2019 Pearson Education, Ltd. All Rights Reserved.
1.5 The Binary System
The traditional decimal system is based on powers of ten.
The Binary system is based on powers of two.
Copyright © 2019 Pearson Education, Ltd. All Rights Reserved.
Figure 1.13 The base ten and binary
systems
Copyright © 2019 Pearson Education, Ltd. All Rights Reserved.
Figure 1.14 Decoding the binary
representation 100101
Copyright © 2019 Pearson Education, Ltd. All Rights Reserved.
Figure 1.15 An algorithm for finding the
binary representation of a positive integer
Copyright © 2019 Pearson Education, Ltd. All Rights Reserved.
Figure 1.16 Applying the algorithm in Figure
1.15 to obtain the binary representation of
thirteen
Copyright © 2019 Pearson Education, Ltd. All Rights Reserved.
Decimal to binary
• Keep dividing by 2
• Ex : 23710
237 / 2 = 118 Remainder 1------------------------------------------------------|
118 / 2 = 59 Remainder 0---------------------------------------------------| |
59 / 2 = 29 Remainder 1------------------------------------------------| | |
29 / 2 = 14 Remainder 1------------------------------------------------| | |
14 / 2 = 7 Remainder 0---------------------------------------------| | | |
7 / 2 =3 Remainder 1------------------------------------------| | | | |
3/ 2=1 Remainder 1-----------------------------------| | | | | | |
1/ 2=0 Remainder 1--------------------------------| | | | | | | |
v v v v v v v v
1 1 1 0 1 1 0 1
Copyright © 2019 Pearson Education, Ltd. All Rights Reserved.
Figure 1.17 The binary addition facts
Copyright © 2019 Pearson Education, Ltd. All Rights Reserved.
Figure 1.18 Decoding the binary
representation 101.101
Copyright © 2019 Pearson Education, Ltd. All Rights Reserved.
1.6 Storing Integers
• Two’s complement notation: The most popular
means of representing integer values
• Excess notation: Another means of representing
integer values
Copyright © 2019 Pearson Education, Ltd. All Rights Reserved.
Figure 1.19 Two’s complement notation
systems
Copyright © 2019 Pearson Education, Ltd. All Rights Reserved.
Figure 1.20 Coding the value -6 in two’s
complement notation using four bits
Copyright © 2019 Pearson Education, Ltd. All Rights Reserved.
If you have -30, and want to represent it in 2's
complement,
you take the binary representation of 30:
0000 0000 0000 0000 0000 0000 0001 1110
Invert the digits.
1111 1111 1111 1111 1111 1111 1110 0001
And add one.
1111 1111 1111 1111 1111 1111 1110 0010
Hexadecimal equivalent is 0xFFFFFFE2.
Copyright © 2019 Pearson Education, Ltd. All Rights Reserved.
The Problem of Overflow
• There is a limit to the size of the values that can be
represented in any system
• Overflow
– occurs when a computation produces a value that
falls outside the range of values that can be
represented in the machine
– If the resulting sign bit is incorrect, an overflow has
occurred
– 16 bit systems have been upgraded to 32 bit
systems
Copyright © 2019 Pearson Education, Ltd. All Rights Reserved.
Computer Science An Overview
13th Edition, Global Edition
Chapter 2
Data Manipulation
Copyright © 2019 Pearson Education, Ltd. All Rights Reserved.
Chapter 2: Data Manipulation
• 2.1 Computer Architecture
• 2.2 Machine Language
• 2.3 Program Execution
• 2.4 Arithmetic/Logic
• 2.5 Communicating with Other Devices
• 2.6 Program Data Manipulation
• 2.7 Other Architectures
Copyright © 2019 Pearson Education, Ltd. All Rights Reserved.
2.1 Computer Architecture
• Central Processing Unit (CPU)
– Arithmetic/Logic Unit
– Control Unit
– Register Unit
▪ General purpose registers
▪ Special purpose registers
• Bus
• Main Memory
Copyright © 2019 Pearson Education, Ltd. All Rights Reserved.
Von Neumann architecture
(simplified)
49
Copyright © 2019 Pearson Education, Ltd. All Rights Reserved.
Figure 2.1 CPU and main memory
connected via a bus
Copyright © 2019 Pearson Education, Ltd. All Rights Reserved.
Memory Hierarchy
Copyright © 2019 Pearson Education, Ltd. All Rights Reserved.
How your programs run on a Computer
Image from: https://www.astateofdata.com/
Copyright © 2019 Pearson Education, Ltd. All Rights Reserved.
How your programs run on a Computer (2)
Image from:https://taylor.git-pages.mst.edu/index_files/Security/Content/13b-ReverseEngineering.html
Copyright © 2019 Pearson Education, Ltd. All Rights Reserved.
How your programs run on a Computer (3)
• Write a source code (ex: C prog. Language)
• Compile your source code and create an object file
(Stored Program Concept)
• Run your object file (ex: exe file in Windows)
• Operating system loads your program from secondary
memory (HDD) to primary memory (RAM).
• CPU executes the machine code of your program line by
line. (Fetch Decode Execute Cycle)
Copyright © 2019 Pearson Education, Ltd. All Rights Reserved.
Stored Program Concept
A program can be encoded as bit patterns and stored in
Main Memory. From there, the Control Unit can extract,
decode, and execute instructions.
Instead of rewiring the CPU, the program can be altered
by changing the contents of Main Memory.
Copyright © 2019 Pearson Education, Ltd. All Rights Reserved.
2.2 Machine Language
• Machine instruction: An instruction encoded as a bit
pattern recognizable by the CPU
• Machine language: The set of all instructions
recognized by a machine
Copyright © 2019 Pearson Education, Ltd. All Rights Reserved.
Machine Language Philosophies
• Reduced Instruction Set Computing (RISC)
– Few, simple, efficient, and fast instructions
– Examples: PowerPC from Apple/IBM/Motorola
and ARM
• Complex Instruction Set Computing (CISC)
– Many, convenient, and powerful instructions
– Example: Intel
Copyright © 2019 Pearson Education, Ltd. All Rights Reserved.
Machine Instruction Types
• Data Transfer: copy data from one location to another
(e.g. LOAD, STORE)
• Arithmetic/Logic: operations on bit patterns
(e.g. +, -, *, /, AND, OR, SHIFT, ROTATE)
• Control: direct the execution of the program
(e.g. JUMP, BRANCH)
Copyright © 2019 Pearson Education, Ltd. All Rights Reserved.
Figure 2.2 Adding values stored in
memory
Equivalent C Code:
x = y + z;
Copyright © 2019 Pearson Education, Ltd. All Rights Reserved.
Figure 2.3 Dividing values stored in
memory
Equivalent C Code:
x = y / z;
Copyright © 2019 Pearson Education, Ltd. All Rights Reserved.
Figure 2.4 The architecture of the Vole, as
described in Appendix C
Copyright © 2019 Pearson Education, Ltd. All Rights Reserved.
Parts of a Machine Instruction
• Op-code: Specifies which operation to execute
• Operand: Gives more detailed information about the
operation
– Interpretation of operand varies depending on op-
code
Copyright © 2019 Pearson Education, Ltd. All Rights Reserved.
Figure 2.5 The composition of a Vole
instruction
ADD value of register 0x5 and 0xA and store in 0x7
Copyright © 2019 Pearson Education, Ltd. All Rights Reserved.
Figure 2.6 Decoding the instruction
0x35A7
Copyright © 2019 Pearson Education, Ltd. All Rights Reserved.
Figure 2.7 An encoded version of the
instructions in Figure 2.2
Copyright © 2019 Pearson Education, Ltd. All Rights Reserved.
2.3 Program Execution
• Controlled by two special purpose registers
– Instruction register
▪ holds current instruction
– Program counter
▪ holds address of next instruction
• Machine Cycle: (repeat these 3 steps)
– Fetch, Decode, Execute
Copyright © 2019 Pearson Education, Ltd. All Rights Reserved.
Figure 2.8 The machine cycle
Copyright © 2019 Pearson Education, Ltd. All Rights Reserved.
2.4 Arithmetic/Logic Instructions
• Logic Operations:
– AND, OR, XOR
– often used to mask an operand
• Rotation and Shift Operations:
– circular shift, logical shift, arithmetic shift
• Arithmetic Operations:
– add, subtract, multiply, divide
– two’s complement versus floating-point
Copyright © 2019 Pearson Education, Ltd. All Rights Reserved.
That’s All Folks
• Questions?
Copyright © 2019 Pearson Education, Ltd. All Rights Reserved.
