Transcript 1 + d - Help-A-Bull

Lecture 3
• Last Lecture
– The Computer Level Hierarchy
– The Von Neumann Model
– Non-Von Neumann Model
• Today’s Topics
– Definitions: bit, nibble, byte, word
– Positional Numbering Systems
– Converting Between Bases
1
Divide and Conquer
•
•
•
•
Divide a problem into modules.
Design each module separately.
Each module performs a specific task
Modules need only know how to interface with other
modules to make use of them.
• Computer system organization can be approached in a
similar manner?
– Abstraction:
•
•
•
•
The machine is built from a hierarchy of levels,
Each level has a specific function,
Each level exists as a distinct hypothetical machine, also called virtual machine.
Each level’s virtual machine executes its own particular set of instructions,
calling upon machines at lower levels to carry out the tasks when necessary.
2
The Computer Level Hierarchy
• Divide and Conquer
–
–
–
–
Divide a problem into modules.
Design each module separately.
Each module performs a specific task
Modules need only know how to
interface with other modules to make
use of them.
• Each virtual machine layer is an
abstraction of the level below it.
• The machines at each level
execute their own particular
instructions, calling upon
machines at lower levels to
perform tasks as required.
3
The von Neumann Model
• Today’s stored-program machine architecture:
– Three hardware systems:
• A central processing unit (CPU) with a control unit, an arithmetic
logic unit (ALU), registers (small storage areas)
• A main memory system
– Holds the programs that control the computer’s operation
• An I/O system
– The capacity to carry out sequential instruction
processing.
– A single data path between the CPU and main memory.
• This single path is known as the von Neumann bottleneck.
4
The von Neumann Model
• A general depiction
of a von Neumann
system.
• Employ a fetchdecode-execute
cycle to run
programs
5
Non-von Neumann Models
• Improvements to conventional stored-program computers
– adding specialized buses, floating-point units, and cache memories.
• But enormous improvements in computational power require
departure from the classic von Neumann architecture.
• Some of today’s systems have separate buses for data and
instructions (Called a Harvard architecture)
• Other non-von Neumann systems provide special-purpose
processors to offload work from the main CPU.
• Parallel processing refers to a collection of different
architectures:
– Multiple separate computers working together
– Multiple processors sharing memory
– Multiple cores integrated onto the same chip: each core has its own
ALU and set of registers, but all processors share memory and
other resources.
6
Bit, Nibble, Byte & Word
• Bit: the most basic unit of information in a computer.
– Binary Digit
– 1/0, True/False, closed/open, off/on, high/low;
• Nibble: A group of four bits
– 1 nibble = 4 bits
• Byte: a group of eight bits.
– 1 byte = 8 bits
• Word:
– a contiguous group of bytes.
– Word sizes of 16, 32, or 64 bits are most common.
7
Positional Number Systems
• A Number 𝐷 consists of 𝑛 digits with each digit has a particular position.
• Every digit position is associated with a fixed weight.
• Weight 𝑤𝑖 for digit position 𝑖: powers of some constant value, called
radix or the base, such that 𝒘𝒊 = 𝒓𝒊 .
𝑫 = 𝒅𝒏−𝟏 𝒓𝒏−𝟏 + 𝒅𝒏−𝟏 𝒓𝒏−𝟐 + ⋯ + 𝒅𝟐 𝒓𝟐
+ 𝒅𝟏 𝒓𝟏 + 𝒅𝟎 𝒓𝟎
• A number system of radix 𝑟, typically has a set of 𝒓 allowed digits
{0, 1, ⋯ , 𝑟 − 1}.
• Most Significant Digit (MSD): the leftmost digit with the highest weight
• Least significant Digit (LSD): the rightmost digit with the lowest weight
Representing Fractions
• A number Nr in radix r can also have a fraction part:
Nr = dn-1dn-2 … d1d0 . d-1 d-2 … d-m+1 d-m
MSD
Integer Part
Fraction Part
Radix Point
• The number Nr represents the value:
Nr = dn-1 × rn-1 + … + d1 × r + d0 +
0 ≤ di < r
LSD
(Integer Part)
d-1 × r -1 + d-2 × r -2 … + d-m × r –m
(Fraction Part)
Popular Number Systems
• Decimal Number System: Radix = 10
– Ten digit values: 0, 1, 2, …, 9
• Binary Number System: Radix = 2
– Only two digit values: 0 and 1
– Numbers are represented as 0s and 1s
• Octal Number System: Radix = 8
– Eight digit values: 0, 1, 2, …, 7
• Hexadecimal Number Systems: Radix = 16
– Sixteen digit values: 0, 1, 2, …, 9, A, B, …, F
– A = 10, B = 11, …, F = 15
• Octal and Hexadecimal numbers can be converted easily to
Binary and vice versa
Decimal Numbers
• Radix 𝑟 = 10
• 10 possible digits {0, 1, 2, 3,
4, 5, 6, 7, 8, 9}
• Weight of position 𝑖: 𝑤𝑖 = 10𝑖
4
0.04
Binary Numbers
• Each binary digit (called a bit) is either 1 or 0
• Bits have no inherent meaning, they can represent …
–
–
–
–
Unsigned and signed integers
Most
Fractions
Significant Bit
Characters
7 6
5
Images, sound, etc.
• Bit Numbering
Least
Significant Bit
4
3
2
1
0
1
0
0
1
1
1
0
1
27
26
25
24
23
22
21
20
– Least significant bit (LSB) is rightmost (bit 0)
– Most significant bit (MSB) is leftmost (bit 7 in an 8-bit number)
• The largest 𝑛 bits binary number is 2𝑛 − 1 in decimal number
Weight Structure of Binary Numbers
• Each bit represents a power of 2
• The weight structure of a binary number is:
2𝑛−1 2𝑛−2 ⋯ 23 22 21 20 . 2−1 2−2 ⋯ 2−𝑚
Binary Point
Binary-to-Decimal Conversion
•
Every binary number is a sum of powers of 2
•
Decimal Value = (dn-1  2n-1) + ... + (d1  21) + (d0  20)
•
Binary (10011101)2 = 27 + 24 + 23 + 22 + 1 = 157
•
Binary (0.1011) 2 = 2-1 + 2-3 + 2-4 = 0.6875
Some common powers of 2
7
6
5
4
3
2
1
0
1
0
0
1
1
1
0
1
27
26
25
24
23
22
21
20
-1 -2
-3 -4
1
1
0
1
2-1 2-2 2-3 2-4
Binary-to-Decimal Conversion
Exercise
Convert the binary number 100101.01 to
decimal
Solution:
1 0 0 1 0 1. 0 1
25 24 23 22 21 20. 2-1 2-2
32 16 8 4 2 1 . ½ ¼
32
+4
+1
+¼ = 37¼
Octal and Hexadecimal Numbers
• Octal = Radix 8
• Only eight digits: 0 to 7
• Digits 8 and 9 not used
• Hexadecimal = Radix 16
• 16 digits: 0 to 9, A to F
• A=10, B=11, …, F=15
• First 16 decimal values (0
to15) and their values in
binary, octal and hex.
Memorize table
Decimal
Radix 10
Binary
Radix 2
Octal
Radix 8
Hex
Radix 16
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
0
1
2
3
4
5
6
7
10
11
12
13
14
15
16
17
0
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F
Octal/Hex-to-Decimal Conversion
• Octal to Decimal: N8 = (dn-1  8n-1) +... + (d1  8) + d0
• Hex to Decimal: N16 = (dn-1  16n-1) +... + (d1  16) + d0
• Examples:
(7204)8 = (7  83) + (2  82) + (0  8) + 4 = 3716
(3BA4)16 = (3  163) + (11  162) + (10  16) + 4 = 15268
Important Properties
 How many possible digits can we have in Radix 𝑟 ?
r digits: 0 to 𝑟 – 1
 What is the result of adding 1 to the largest digit in Radix 𝑟?
Since digit r is not represented, result is (10)𝑟 in Radix 𝑟
Examples: 12 + 1 = (10)2
78 + 1 = (10)8
910 + 1 = (10)10
F16 + 1 = (10)16
 Adding 1 to the largest digit in any number system always
has a result of (10) in that number system.
Important Properties – cont’d
 What is the largest value using 3 digits in Radix r?
In binary: (111)2 = 23 – 1
In Radix r:
In octal: (777)8 = 83 – 1
3 – 1
largest
value
=
r
In decimal: (999)10 = 103 – 1
• How many possible values can be represented …
n values: 0 to 2n – 1
2
Using n binary digits?
8n values: 0 to 8n – 1
Using n octal digits
n values: 0 to 10n – 1
10
Using n decimal digits?
Using n hexadecimal digits 16n values: 0 to 16n – 1
rn values: 0 to rn – 1
Using n digits in Radix r ?
• Total number of values (patterns) representable in 𝑛 digits
with radix 𝑟?
𝑟𝑛
Important Properties of Fractions
• How many fractional values exist with m fraction bits?
2m fractions, because each fraction bit can be 0 or 1
• What is the largest fraction value if m bits are used?
Largest fraction value = 2-1 + 2-2 + … + 2-m = 1 – 2-m
Because if you add 2-m to largest fraction you obtain 1
• In general, what is the largest fraction value if m fraction
digits are used in radix r?
Largest fraction value = (r-1)(r -1 + r -2 + … + r -m)= 1 – r -m
For decimal, largest fraction value = 1 – 10-m
For hexadecimal, largest fraction value = 1 – 16-m
What is the largest value that can be expressed in 𝑛 integral
digits and 𝑚 fractional digits?
𝑟𝑛 − 𝑟𝑚
Summary of Number Systems Properties
Lecture 3
• Today’s Topics
– Definitions: bit, nibble, byte, word
– Positional Numbering Systems
– Converting Between Bases
• Converting Integer Numbers
• Converting Fractional Numbers
22
Converting Integer Numbers
Dividing 𝑋𝐵 by 𝐴, the remainder will be 𝑎0 .
Converting Integer Numbers
𝑄0 = 𝑄1 𝐴 + 𝑎0
𝑄1 = 𝑄2 𝐴 + 𝑎1
⋮
𝑄𝑚−1 = 𝑄𝑚 𝐴 + 𝑎𝑚−1
where 𝑄𝑚 = 0
• This division procedure can be used for number
base conversion.
Decimal-To-Binary Conversion - 1
• Repeated Division-by-2 Method
– Repeatedly divide the decimal integer by 2
• Each remainder is a binary digit in the translated value
• Example: Convert 3710 to Binary
least significant bit
37 = (100101)2
most significant bit
stop when quotient is zero
Decimal to Binary Conversion - 2
• N = (dn-1  2n-1) + ... + (d1  21) + (d0  20)
• Dividing N by 2 we first obtain
– Quotient1 = (dn-1  2n-2) + … + (d2  2) + d1
– Remainder1 = d0
– Therefore, first remainder is least significant bit of binary number
• Dividing first quotient by 2 we first obtain
– Quotient2 = (dn-1  2n-3) + … + (d3  2) + d2
– Remainder2 = d1
• Repeat dividing quotient by 2
– Stop when new quotient is equal to zero
– Remainders are the bits from least to most significant bit
Exercise
• Convert (45)10 to binary using repeated
division-by-2 method.
Decimal-To-Binary Integer
Conversion - 3
• Sum-of-Weights Methods
– Determine the set of binary weights whose
sum is equal to the decimal number.
– Place 1s in the appropriate weight positions.
𝟗 = 𝟖 + 𝟏 = 𝟐𝟑 +𝟐𝟎
𝟐𝟑
𝟐𝟐
𝟐𝟏
𝟐𝟎
1
0
0
1
• Exercise: (58)10 = (
?
)2
Decimal-to-Hexadecimal Conversion
 Repeatedly divide the decimal integer by 16
 Each remainder is a hex digit in the translated value
 Example: convert 422 to hexadecimal
least significant digit
most significant digit
422 = (1A6)16
stop when
quotient is zero
 To convert decimal to octal divide by 8 instead of 16
Decimal-to-Octal Conversion
 Repeatedly divide the decimal integer by 8
 Each remainder is a hex digit in the translated value
 Example: convert 359 to octal
Division
Quotient
Remainder
359/8
44
7
44/8
5
4
5/8
0
5
359 = (547)8
stop when
quotient is zero
least significant digit
most significant digit
Converting Fractions
Converting Fractions
⋮
Converting Fraction to any Radix r
• To convert fraction N to any radix r
Nr = (0.d-1 d-2 … d-m)r = d-1 × r -1 + d-2 × r -2 … + d-m × r –m
• Multiply 𝑁𝑟 by r to obtain d-1
Nr × r = d-1 + d-2 × r -1 … + d-m × r –m+1
• The integer part is the digit d-1 in radix r
• The new fraction is d-2 × r -1 … + d-m × r –m+1
• Repeat multiplying the new fractions by r to obtain d-2 d-3 ...
• Stop when new fraction becomes 0.0 or enough fraction
digits are obtained
Converting Decimal Fractions to Binary
• Sum-of-weights
0.625 = 0.5 + 0.125 = 2−1 + 2−3 = 0.101
• Repeated Multiplication by 2
– Repeatedly multiplying the fractional results of
successive multiplications by 2.
– Stop when new fraction = 0.0, or when enough
fraction bits are obtained
– The carries form the binary number.
Converting Decimal Fraction to Binary - 2
• Repeated Multiplication by 2 example
– Convert N = 0.6875 to Radix 2
Multiplication
New Fraction Bit
0.6875 × 2 = 1.375
0.375
1
0.375 × 2 = 0.75
0.75
0
0.75 × 2 = 1.5
0.5
1
0.5 × 2 = 1.0
0.0
1
• Therefore, N = 0.6875 = (0.1011)2
• Check (0.1011)2 = 2-1 + 2-3 + 2-4 = 0.6875
First fraction bit
Last fraction bit
Converting Decimal Fractions to Octal
Conversion Procedure to Radix r
• To convert decimal number N (with fraction) to radix r
• Convert the Integer Part
– Repeatedly divide the integer part of number N by the radix r and
save the remainders. The integer digits in radix r are the
remainders in reverse order of their computation. If radix r > 10,
then convert all remainders > 10 to digits A, B, … etc.
• Convert the Fractional Part
– Repeatedly multiply the fraction of N by the radix r and save the
integer digits that result. The fraction digits in radix r are the
integer digits in order of their computation. If the radix r > 10,
then convert all digits > 10 to A, B, … etc.
• Join the result together with the radix point
Examples
• Convert N = 139.6875 to Octal (Radix 8)
• Solution: N = 139 + 0.6875 (split integer from fraction)
• The integer and fraction parts are converted separately
Division
Quotient Remainder
Multiplication
New Fraction Digit
139 / 8
17
3
0.6875 × 8 = 5.5
0.5
5
17 / 8
2
1
0.5 × 8 = 4.0
0.0
4
2/8
0
2
• Therefore, 139 = (213)8 and 0.6875 = (0.54)8
• Now, join the integer and fraction parts with radix point
N = 139.6875 = (213.54)8
Binary-to-Octal/Hex Conversion
 Binary, Octal, and Hexadecimal are related:
Radix 16 = 24 and Radix 8 = 23
 Hexadecimal digit = 4 bits and Octal digit = 3 bits
 Starting from least-significant bit, group each 4 bits into
a hex digit or each 3 bits into an octal digit
 Example: Convert 32-bit number into octal and hex
3
5
3
0
5
5
2
3
6
2
4 Octal
1 1 1 0 1 0 1 1 0 0 0 1 0 1 1 0 1 0 1 0 0 1 1 1 1 0 0 1 0 1 0 0 32-bit binary
E
B
1
6
A
7
9
4
Hexadecimal
Octal/Hex-to-Binary Conversion
• Hex-to-Binary Conversion
– Replace each hexadecimal symbol with the appropriate
four bits.
• Octal-to-Binary Conversion
– Replace each octal symbol with the appropriate three bits.
• Example:
– (10𝐴4)16 = (0001 0000 1010 0100)2
– (7526)8 = (111 101 010 110)2
Simplified Conversions
 Converting fractions between Binary, Octal, and
Hexadecimal can be simplified
 Starting at the radix pointing, the integer part is
converted from right to left and the fractional part is
converted from left to right
 Group 4 bits into a hex digit or 3 bits into an octal digit
integer: right to left
7
2
6
1
fraction: left to right
3 . 2
4
7
4
5
2 Octal
1 1 1 0 1 0 1 1 0 0 0 1 0 1 1 . 0 1 0 1 0 0 1 1 1 1 0 0 1 0 1 0 1 Binary
7
5
8
B
.
5
3
C
A
8 Hexadecimal
 Use binary to convert between octal and hexadecimal