Introduction to Computing

(CS111)

Junar A. Landicho

junarlandicho@ustp.edu.ph

“

When we are no longer able to change a situation we are challenged to change ourselves.

Viktor Frankl

Topic 1:

Data Storage

IT 416

Information Systems Development and Management

Learning Outcomes

By the end of this topic, students will be able to: Create a computational artifact for creative expression. Describe the variety of abstractions used to represent data.

Explain how binary sequences are used to represent digital data.

Identify multiple levels of abstractions that are used when writing programs.

CS 111 – Introduction to Computing

Learning Outcomes

Analyze how data representation, storage, security, and transmission of data involve computational manipulation of information.

Use abstraction to manage complexity in programs. Evaluate the correctness of a program.

Employ appropriate mathematical and logical concepts in programming.

CS 111 – Introduction to Computing

Overview

1. Bits and Their Storage

2. Main Memory

3. Mass Storage

4. Representing Information as Bit Patterns 5. The Binary System

6. Storing Integers

7. Storing Fractions

8. Data and Programming

9. Data Compression

10. Communications Errors

CS 111 – Introduction to Computing

Bits and Their Storage Java

PHP

Python

CS 111 – Introduction to Computing

Bits and Their Storage

Bit: Binary Digit (0 or 1)

Bit Patterns are used to represent information

▪ Numbers

▪ Text characters

▪ Images

▪ Sound

▪ And others

CS 111 – Introduction to Computing

Boolean Operations

Boolean Operation: An operation that manipulates one or more true/false values

Specific operations

▪ AND

▪ OR

▪ XOR (exclusive or)

▪ NOT

CS 111 – Introduction to Computing

Boolean Operations

The possible input

and output values of

Boolean operations

AND, OR, and XOR

(exclusive or)

CS 111 – Introduction to Computing

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

CS 111 – Introduction to Computing

Gates

A pictorial representation of AND, OR, XOR, and NOT gates as well as their input and output values

CS 111 – Introduction to Computing

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

CS 111 – Introduction to Computing

Flip-flops

A simple flip-flop circuit

CS 111 – Introduction to Computing

Setting the output of a Flip-flop to 1CS 111 – Introduction to Computing

Setting the output of a Flip-flop to 1 (continued)

CS 111 – Introduction to Computing

Setting the output of a Flip-flop to 1 (continued)

CS 111 – Introduction to Computing

Another way of constructing a flip-flopCS 111 – Introduction to Computing

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

CS 111 – Introduction to Computing

Main Memory Java

PHP

Python

CS 111 – Introduction to Computing

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

CS 111 – Introduction to Computing

Main Memory

The organization of a byte-size memory cell

CS 111 – Introduction to Computing

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

_{Memory cells arranged by address} cells.

CS 111 – Introduction to Computing

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

CS 111 – Introduction to Computing

Measuring Memory Capacity

Kilobyte: 2¹⁰ bytes = 1024 bytes

▪ Example: 3 KB = 3 times1024 bytes

Megabyte: 2²⁰ bytes = 1,048,576 bytes

▪ Example: 3 MB = 3 times 1,048,576 bytes

Gigabyte: 2³⁰ bytes = 1,073,741,824 bytes

▪ Example: 3 GB = 3 times 1,073,741,824 bytes

CS 111 – Introduction to Computing

Measuring Memory Capacity Additional devices:

▪ Magnetic disks ▪ CDs

▪ DVDs

▪ Magnetic tapes ▪ Flash drives

▪ Solid-state drives

Advantages over main memory ▪ Less volatility

▪ Larger storage capacities

▪ Low cost

▪ In many cases can be removed

CS 111 – Introduction to Computing

Mass Storage Java

PHP

Python

CS 111 – Introduction to Computing

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

CS 111 – Introduction to Computing

A Magnetic Disk Storage SystemCS 111 – Introduction to Computing

CD storage

CS 111 – Introduction to Computing

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

CS 111 – Introduction to Computing

Representing Information as Bit Patterns

Python

Java

PHP

CS 111 – Introduction to Computing

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

CS 111 – Introduction to Computing

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

The message “Hello.” in ASCII or UTF-8 encoding

CS 111 – Introduction to Computing

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

CS 111 – Introduction to Computing

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

CS 111 – Introduction to Computing

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

The sound wave represented by the sequence 0, 1.5, 2.0, 1.5, 2.0, 3.0, 4.0, 3.0, 0

▪ Used in music synthesizers

▪ Encodes which instrument, note, and duration

CS 111 – Introduction to Computing

The Binary System Java

PHP

Python

CS 111 – Introduction to Computing

Binary Notation

The traditional decimal system is based on powers of ten. The Binary system is based on powers of two.

CS 111 – Introduction to Computing

Binary Notation

Decoding the binary representation 100101

CS 111 – Introduction to Computing

Binary Notation

An algorithm for finding the binary representation of a positive integer.

CS 111 – Introduction to Computing

Binary Notation

Applying the algorithm in Slide 41 to obtain the binary

representation of thirteen

CS 111 – Introduction to Computing

Binary Addition & Fractions

The binary addition facts _{Decoding the binary representation 101.101}CS 111 – Introduction to Computing

Storing Integers Java

PHP

Python

CS 111 – Introduction to Computing

Two’s Complement

Notation

Two’s complement notation:

The most popular means of

representing integer values

Excess notation: Another

means of representing integer

values

Two’s complement notation systems

CS 111 – Introduction to Computing

Two’s Complement Notation Coding the value -6 in two’s complement notation using four bits

CS 111 – Introduction to Computing

Addition in Two’s Complement Notation

Addition problems converted to two’s complement notation

CS 111 – Introduction to Computing

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

CS 111 – Introduction to Computing

Excess Notation

An excess eight conversion table An excess notation system using bit patterns of length three

CS 111 – Introduction to Computing

Storing Fractions Java

PHP

Python

CS 111 – Introduction to Computing

Floating-Point Notation

Floating-point Notation: Consists of a sign bit, a mantissa field, and an exponent field.

Normalized form: fill the mantissa starting with the left-most 1

Floating-point notation components

CS 111 – Introduction to Computing

Truncation Errors

Encoding the value 2 ⁵⁄₈

CS 111 – Introduction to Computing

Truncation Errors

Occur when part of the value being stored is lost because the mantissa is not large enough

Non-terminating expansions of fractions ▪ This happens more often with binary notation

▪ The value of one-tenth cannot be stored exactly binary notation

▪ Often these values are converted to integers

CS 111 – Introduction to Computing

Numerical Analysis

The study of dealing with problems

when computing large values that

require significant accuracy

The order in which values are added

can lead to two different results

Adding very small values to very

large values can result in errors

CS 111 – Introduction to Computing

Data and Programming Java

PHP

Python

CS 111 – Introduction to Computing

Data and Programing

A programming language is a computer system created to allow humans to precisely express algorithms using a higher level of abstraction.

CS 111 – Introduction to Computing

Programming Languages

CS 111 – Introduction to Computing

Getting Started with Python

Python: a popular programming

language for applications, scientific

computation, and as an introductory

language for students

Freely available from www.python.org

Python is an interpreted language

▪ Typing:

print('Hello, World!')

▪ Results in:

Hello, World!

CS 111 – Introduction to Computing

Getting Started with Python

Variables: name values for later use

Analogous to mathematic variables in

algebra

s = 'Hello, World!'

print(s)

my_integer = 5

my_floating_point = 26.2

my_Boolean = True

my_string = 'characters'

my_integer = 0xFF

CS 111 – Introduction to Computing

Getting Started with Python

Operators and Expressions

print(3 + 4) # Prints 7

print(5 – 6) # Prints -1

print(7 * 8) # Prints 56

print(45 / 4) # Prints 11.25

print(2 ** 10) # Prints 1024

s = 'hello' + 'world'

s = s * 4

print(s)

CS 111 – Introduction to Computing

Getting Started with Python

Currency Conversion

# A converter for currency exchange.

USD_to_GBP = 0.66 # Today's exchange rate

GBP_sign = '\u00A3' # Unicode value for £

dollars = 1000 # Number dollars to convert

# Conversion calculations

pounds = dollars * USD_to_GBP

# Printing the results

print('Today, $' + str(dollars))

print('converts to ' + GBP_sign + str(pounds))

CS 111 – Introduction to Computing

Getting Started with Python

Debugging

Syntax errors

print(5 +)

SyntaxError: invalid syntax

pront(5)

NameError: name 'pront' is not defined

Semantic errors

▪ Incorrect expressions like

total_pay = 40 + extra_hours * pay_rate

Runtime errors

▪ Unintentional divide by zero

CS 111 – Introduction to Computing

Data Compression Java

PHP

Python

CS 111 – Introduction to Computing

Data Compression

Lossy versus lossless

Run-length encoding

Frequency-dependent encoding (Huffman codes)

Relative encoding

Dictionary encoding (includes adaptive dictionary encoding such as LZW encoding)

CS 111 – Introduction to Computing

Compressing Images

GIF: Good for cartoons

JPEG: Good for photographs

TIFF: Good for image archivingCS 111 – Introduction to Computing

Compressing Audio and Video

MPEG

▪ High definition television broadcast

▪ Video conferencing

MP3

▪ Temporal masking

▪ Frequency masking

CS 111 – Introduction to Computing

Communication Errors Java

PHP

Python

CS 111 – Introduction to Computing

Communication Errors

Goal: To reduce errors and increase the reliability of computing

equipment

Parity bits (even versus odd)

Checkbytes

Error correcting codes

Hamming Distance

CS 111 – Introduction to Computing

Parity Bits

The ASCII codes for the letters A and F adjusted for odd parity

CS 111 – Introduction to Computing

Error-Correcting Codes

An error-correcting code Decoding the pattern 010100 using the code CS 111 – Introduction to Computing

CS 111 – Introduction to Computing

</End>