Representing Information Digitally (Number systems)

Nell Dale & John Lewis

(adapted by Erin Chambers,

Michael Goldwasser, Andrew Harrington)

Analog vs. Digital Information

Analog data is a continuous representation, analogous to the actual information it represents. A mercury thermometer is an analog device. The mercury rises in a continuous flow in the tube in direct proportion to the temperature.

Digital data is a discrete representation, breaking the information up into separate elements.

The “bit” (binary digit)

All of the historical computing devices we discussed last time were inherently digital, since the mechanisms had fixed number of states.

Modern computers are based on storing information using physical means that can be in one of two distinct states.

We call such a physical unit a bit.

Two-state Representation of Data

“thumbs up” vs. “thumbs down”

Flag can be raised or lowered

dots/dashes in Morse Code

light switch with circuit opened/closed

“cores” (electromagnets - positive/negative field)

“capacitor” (two small metallic plates with a small separation; can be statically charged/discharged)

“flip/flop” (electronic circuit with output as high/low voltage signal)

Pros/Cons for Data Storage

Varying level of power usage, cost, volatility:

Core will keep its charge even after power is shutoff (but not as quick to access)

Flip-Flop will lose its data when power is turned off (but extremely quick/cheap)

Capacitors use such small charges, they sometimes lose their charge while running unless recharged regularly (“dynamic memory”)

As bits have many physical realizations,

they also have many symbolic representations.

22

Binary and Computers

‘closed’

‘open’

‘on’

‘off’

‘true’

‘false’

‘1’

‘0’

High voltage

Low voltage

Orders of Magnitude

One bit can be in one of two distinct states (0,1)

Two bits can be in one of four distinct states

Three bits can be in one of eight distinct states

n bits can be in one of 2n distinct states

Orders of Magnitude

Common Quantities of Storage

= 250 bytes

= 210 TB

1 Petabyte

= 1trillion+ bytes

= 210 GB

1 Terabyte (TB)

= 1billion+ bytes

= 210 MB

1 Gigabyte (GB)

= 1048576 bytes

= 210 KB

1 Megabyte (MB)

= 1024 bytes

= 210 bytes

1 Kilobyte (KB)

(thus 256 distinct settings)

= 8 bits

1 byte

3

Natural Numbers (0, 1, 2, 3, ….)

Integers (…, -3, -2, -1, 0, 1, 2, 3, …)

Rational Numbers (e.g., -249, -1, 0, ¼ , - ½ )

An integer or the quotient of two integers

Irrational Numbers (e.g., ,  2 )

Values not expressable as quotient of integers

Let’s just focus on Natural Numbers for now…

Representing Numbers

4

How many ones are there in 642?

600 + 40 + 2

Natural Numbers

Or is it

384 + 32 + 2

Or maybe…

1536 + 64 + 2

5

Aha!

642 is 600 + 40 + 2 in BASE 10

The base of a number determines the number of digits and the value of digit positions

(Why was base 10 chosen by humans?)

Natural Numbers

6

Continuing with our example…

642 in base 10 positional notation is:

6 x 102 = 6 x 100 = 600

+ 4 x 101 = 4 x 10 = 40

+ 2 x 10º = 2 x 1 = 2 = 642 in base 10

This number is in

base 10

The power indicates

the position of

the number

Positional Notation

6

8

What if 642 was a numeral in base 8?

6 x 82 = 6 x 64 = 384

Positional Notation

642 in base 8 is equivalent to 418 in base 10

= 418 in base 10

+ 2 x 8º = 2 x 1 = 2

+ 4 x 81 = 4 x 8 = 32

9

Decimal is base 10 and has 10 symbols:	0,1,2,3,4,5,6,7,8,9

Octal is base 8 and has 8 symbols:

0,1,2,3,4,5,6,7

For a number to exist in a given number system, the number system must include those digits.

For example:

The number 284 only exists in base 9 and higher.

Octal

9

Decimal is base 10 and has 10 digits:	0,1,2,3,4,5,6,7,8,9

Binary is base 2 and has 2 digits:

0,1

For a number to exist in a given number system, the number system must include those digits.

For example:

The number 284 only exists in base 9 and higher.

Binary

What is the decimal equivalent of the binary number 1101100?

1 x 26 = 1 x 64 = 64

+ 1 x 25 = 1 x 32 = 32

+ 0 x 24 = 0 x 16 = 0

+ 1 x 23 = 1 x 8 = 8

+ 1 x 22 = 1 x 4 = 4

+ 0 x 21 = 0 x 2 = 0

+ 0 x 2º = 0 x 1 = 0

= 108 in base 10

13

Converting Binary to Decimal

10

How are digits in bases higher than 10 represented?

Base 16:

0,1,2,3,4,5,6,7,8,9,A,B,C,D,E, and F

Bases Higher than 10

What is the decimal equivalent of the hexadecimal number DEF?

D x 162 = 13 x 256 = 3328

+ E x 161 = 14 x 16 = 224

+ F x 16º = 15 x 1 = 15

= 3567 in base 10

Remember, base 16 is 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F

Converting Hexadecimal to Decimal

10

12

1010

09

11

1001

08

10

1000

07

07

0111

06

06

0110

05

05

0101

04

04

0100

03

03

0011

02

02

0010

01

01

0001

00

00

0000

Decimal

Octal

Binary

16

Power of 2 Number System

(Note: Loop stated differently in the book)

Repeat:

1. Divide the decimal number by the new base

2. Make the remainder the next digit

to the left in the answer

3. Replace the decimal number with the quotient

Until the quotient is zero

Algorithm for converting base 10 to other bases:

19

Converting Decimal to Other Bases

Let’s convert 59 (base 10) to base 3:

20

Why does this method work?

19 R 2

59

2

6 R 1

3 19

1

2 R 0

3 6

0

0 R 2

3 2

2

222

16 3567 start

32

36

32

47

32

15

F

13

16 222

16

62

48

14

E

0

16 13

0

13

D

21

Converting Decimal to Hexadecimal

Try another Conversion:

3567 (base 10) is what number in base 16?

done

Try another Conversion:

The base 10 number 108

is what number in base 5?

20

Converting Decimal to Other Bases

Groups of Three (from right)

Convert each group

10101011	10 101 011

2 5 3

10101011 is 253 in base 8

17

Converting Binary to Octal

Groups of Four (from right)

Convert each group

10101011	1010 1011

A B

10101011 is AB in base 16

18

Converting Binary to Hexadecimal

Let’s start with base 10:

Carry Values

1 1 1

3 5 7 2 5 7

+ 6 2 5 4 5

4 1 9 8 0 2

14

Arithmetic in Decimal

What if this is in base 8?

Carry Values

3 5 7 2 5 7

+ 7 2 5 4 5

14

Arithmetic in Other Bases

4

1

2

1

0

1

1

2

5

1

4

5+7 = 8+4 = “14” (8)

4+5+1 = 8+2 = “12” (8)

5+2+1 = 8+0 = “10” (8)

2+7+1 = 8+2 = “12” (8)

7+5+1 = 8+5 = “15” (8)

Carry Values

14

Arithmetic in Binary

Remember: there are only 2 digits in binary: 0 and 1

Position is key, carry values are used:

1 0 1 0 1 1 1

+1 0 0 1 0 1 1

1

0

1

1

1

0

1

0

1

0

1

1

0

1

1+1 = 2 = 2 + 0 = 10 (2)

1+1+1 = 3 = 2 + 1 = 11 (2)

0+1+1 = 2 = 2 + 0 = 10 (2)

1+0+1 = 2 = 2 + 0 = 10 (2)

0+1+1 = 2 = 2 + 0 = 10 (2)

1+1 = 2 = 2 + 0 = 10 (2)

Remember borrowing? Apply that concept here:

1 0 1 0 1 1 1

- 1 1 1 0 1 1

15

Subtracting Binary Numbers

1 0 0

0 2

1

0 2

1 2

1

0

0

Can mention the varying level of power usage, cost and volatility.

* Core will keep its charge even after power is shut off.

* flip-flop will lose its data when power is turned off

* Capacitors use such small charges, they sometimes lose their charge while running, unless recharged regularly (“dynamic memory”)

Fix the animation for this one.

PowerPoint Presentation

theresad

2001-11-27T14:47:45