Binary Number Systems
Part 1: Polynomial Evaluation
Symbols and their values used in positional number systems
Copyright By PowCoder代写 加微信 powcoder
Digit Symbols
Corresponding Digit Values
0,1,2,3,4, 5,6,7,8,9
0,1,2,3,4, 5,6,7,8,9
0,1,2,3,4,5,6,7, 8,9,A,B,C,D,E,F
0,1,2,3,4,5,6,7, 8,9,10,11,12,13,14,15
POLYNOMIAL EVALUATION
Representation: 𝒔𝒏−𝟏 ⋯ 𝒔𝟏𝒔𝟎
where: 𝑠𝑖 are the digit symbols
Ex: 365210 These are the digit symbols
Subscript used to identify radix
Interpretation: 𝒗𝒏−𝟏𝑹𝒏−𝟏 + ⋯ + 𝒗𝟏𝑹𝟏 + 𝒗𝟎𝑹𝟎 where: 𝑣𝑖 are the corresponding digit values
and: 𝑅 is the radix (number base) 3210
Ex: 3×10 +6×10 +5×10 +2×10
representation
(What we write) 547
Subscript used to indicate the radix (number base)
POLYNOMIAL EVALUATION
Digit values (coefficients)
5×102 + 4×101 + 7×100 Positional weights (powers of the radix)
= 500 + 40 + 7 = 547
The result of polynomial evaluation is always a decimal number, regardless of the radix used in the original representation.
Numeric interpretation (What we understand)
Converting from ANY Radix to Decimal Example: Converting from Radix 5 to Decimal
31245 = 3×53 + 1×52 + 2×51 + 4×50 = 3×125 + 1×25 + 2×5 + 4×1
= 375 + 25 + 10 + 4 = 41410
NOTE: Polynomial evaluation may be used to convert from ANY radix to decimal. The positional weights simply become powers of the radix.
CONVERT BINARY TO DECIMAL
(Using Polynomial Evaluation)
10112 = 1×23 + 0×22 + 1×21 + 1×20 = 1×8 + 1×2 + 1×1
=8 +2 +1 = 1110
EXTENDING POLYNOMIAL EVALUATION TO NUMBERS WITH A FRACTIONAL PART
10.0101112
= 1×21 + 0×20 + 0×2-1 + 1×2-2 + 0×2-3
+ 1×2-4 + 1×2-5 + 1×2-6
= 1×21 + 1×2-2 + 1×2-4 + 1×2-5 + 1×2-6
= 2 + 1/4 + 1/16 + 1/32 + 1/64
= 2 + 0.25 + 0.0625 + 0.03125 + 0.015625 = 2.35937510
Tedious! Four divisions and long decimal fractions!
AN EASIER METHOD
10.0101112 = 100101112 / 26 6 fractional digits
= (1×27 + 0×26 + 0×25 + 1×24 + 0×23 + 1×22 + 1×21 + 1×20)/26
= (128 + 16 + 4 + 2 + 1)/64 = 151/64
= 2.35937510
Only a single division!
Converting Fractions
Sometimes a fractional value has a finite representation in one number base, but not in another:
This happens for the reduced fraction k/N iff there is any prime factor P of N such that the destination radix is not divisible by P.
=.13 = .333333333333⋯10 =.110 = .0001100110011⋯2
Representation Error
• Computers store numbers using a fixed number of digits (aka, “fixed precision”)
• Some values may not have a finite representation in binary (e.g., 1 )
• Limiting the number of digits introduces a representation error:
= .110 ≈. 000110012 (8 bits) = .0976562510 11
Calculating Representation Error
Consider the representation of one tenth from the previous slide, using 8 fractional bits:
Desired value
AbsoluteError= 1 −000110012 10 28
Value Represented
= 1 − 25 = 1×256−25×10 = 6 = 0.0023437510 10 256 10×256 2560
% Relative Error =100 × 𝐴𝑏𝑠𝑜𝑙𝑢𝑡𝑒 𝐸𝑟𝑟𝑜𝑟 = 100 × 0.00234375 = 2.34% 𝐷𝑒𝑠𝑖𝑟𝑒𝑑 𝑉𝑎𝑙𝑢𝑒 0.1
Binary Number Systems
Part 2: Unsigned Decimal to Binary Conversion
UNSIGNED DECIMAL TO BINARY CONVERSION
Method 1: Separate problem into two parts:
• Integer Part: Use repeated division
• Fractional Part: Use repeated multiplication
Method 2: Decompose the decimal number into a corresponding sum of powers of 2.
REPEATED DIVISION
Consider what happens when you repeatedly divide a decimal integer by 10:
123/10 Quotient = 12, Remainder = 3 (1’s digit) 12/10 Quotient = 1, Remainder = 2 (10’s digit)
1/10 Quotient = 0, Remainder = 1 (100’s digit)
1. 0 ≤ Remainder ≤ 9 (a single decimal digit)
2. Digits are produced in Right-to-Left order
UNSIGNED DECIMAL TO BINARY Method 1: Integer Part (Repeated Division)
N N÷2 Remainder Result
1361 1. 6 3 0 01. 3 1 1 101. 1 0 STOP 1 1101.
Digits are produced right-to-left starting from the radix point.
NOTE: Repeated division may be used to convert from decimal to ANY radix. Simply divide by the radix.
REPEATED MULTIPLICATION
Consider what happens when you repeatedly multiply a decimal fraction by 10:
10×.123 = 1.23 10×.23 = 2.3
Whole Part = 1, Fractional Part = .23 Whole Part = 2, Fractional Part = .3 Whole Part = 3, Fractional Part = .0
0 ≤ Whole Part ≤ 9 (a single decimal digit) Digits are produced in Left-to-Right order
UNSIGNED DECIMAL TO BINARY Method 1: Fractional Part (Repeated Multiplication)
Product Whole Fractional
.4 0.8 .8 1.6 .6 1.2
Part Part Result 0 .2 .0
1 .6 .0001 1 .2 .00011
Begins to repeat!
Digits are produced left-to-right starting from the radix point.
NOTE: Repeated multiplication may be used to convert from decimal to ANY radix. Simply multiply by the radix.
UNSIGNED DECIMAL TO BINARY Method 2: Decomposition
Convert 75.310 to Binary:
Whole Part:
75 = 64 + 8 + 2 + 1
= 10010112
Fractional Part (approximation): .3 = .25 + .0625
Binary Number Systems
Part 3: Number Representations that use a Fixed Number of Digits
Resolution, Precision, Accuracy
• Resolution: Refers to how finely we can represent a value – usually determined by the number of digits in the representation.
• Precision: Refers to the reproducibility of a measurement – i.e., how many digits remain the same every time you measure the same value.
• Accuracy: Refers to the correctness of a measurement.
INFINITE PRECISION
Placing an infinite number of values on the number line requires a representation that imposes no limit on the number of digits.
Incrementing any number always moves to the right, producing a result that is always one greater than the previous.
THE EFFECT OF FIXED PRECISION
(Using a number circle instead of a line)
Labels inside the circle are symbolic representations.
Wrap Around
Fixed Precision
Fixed # of digits Finite # of values min and max limits
Overflow: Occurs when an arithmetic result is beyond the min or max limits.
Labels outside the circle are the corresponding numeric interpretations.
TWO’S COMPLEMENT REPRESENTATION OF SIGNED BINARY INTEGERS
There are several possible ways to represent signed binary numbers.
Two’s complement is the most common.
Most-Significant Bit: 0 if positive, 1 if negative.
Wrap Around
Negative Values: Not simply a 1 followed by magnitude bits.
Overflow: No longer occurs between 0000 and 1111.
Binary Number Systems
Part 4: Signed Number Conversions
Changing the Sign of a Two’s Complement Number (Method 1)
If +1.2510 = 0001.01002 Then -1.2510 = ????.????2
1. Change every bit: 0001.0100 . ..
2. Then add 1 to the +1 least-significant 1110.1100 bit position.
Simply changing the most- significant bit is NOT the same and doesn’t work!
Consider what happens when the starting value is a full-scale negative value, such as -12810 = 100000002
Changing the Sign of a Two’s Complement Number (Method 2)
If +1.2510 = 0001.01002 Then -1.2510 = ????.????2
Copy right-to-left through first 1:
Copy opposite of all remaining bits:
CONVERTING SIGNED DECIMAL TO TWO’S COMPLEMENT
• Positivevalues:
1. Convert as if unsigned
2. Zero extend (add 0’s on the left) to fill out the representation to the desired number of bits
Note: Most-significant bit must be 0
• Negativevalues:
1. Find corresponding positive representation as above
2. Find the “2’s complement” of the result.
CONVERTING SIGNED DECIMAL TO TWO’S COMPLEMENT
Example: Find the 8-bit 2’s complement representation of -2510
1. Convert the magnitude to unsigned binary: 2510 = 16 + 8 + 1110012
2. Zero extend to 8 bits: 11001 00011001
3. Find the 2’s complement: 00011001 111001112
CONVERTING TWO’S COMPLEMENT TO SIGNED DECIMAL
• Positive values (most-significant bit is 0)
– Same as unsigned (use polynomial evaluation)
• Negative values (most-significant bit is 1)
1. Use Two’s Complement procedure to find the
representation of the corresponding positive value.
2. Find decimal magnitude using polynomial evaluation
3. Add a leading minus sign
Converting Two’s Complement to Signed Decimal (Method 1)
Original 2’s complement number: 100011002
1. Negativefind positive equivalent: 011101002
2. Polynomial evaluation:
3. Add a leading minus sign:
64+32+16+4 = 11610
CONVERTING TWO’S COMPLEMENT TO SIGNED DECIMAL
• Use polynomial evaluation, but make the weight of the most-significant bit position negative.
Converting Two’s Complement to Signed Decimal (Method 2)
Original 2’s complement number: 100011002
Polynomial evaluation: −128+8+4 = −11610
Extending Representation Width
Unsigned – Just add leading zeroes: 000000112 = 310 000000112 = 310
2’s Complement Signed:
• If positive, add leading zeroes: 00000112 = +310
000000112 = +310
• If negative, add leading ones: 000011012 = −310 111111012 = −310
“Zero-Extending”
“Sign-Extending”
Binary Number Systems
Part 5: Worked Examples
Convert unsigned 256 to decimal
Base R to Decimalpolynomial evaluation:
256 = 2×61 + 5×60 = 2×6 + 5×1
= 12 + 5 = 1710
Convert unsigned 2510 to base 7
Whole #10 to Base Rrepeated division (by 7): 25÷7Q=3, R=4 347
23÷7 Q=0, R=3 STOP
Convert unsigned .310 to base 7
Fractional #10 to Base Rrepeated multiplication:
7 x .3 = 2.1 .2
7 x .1 = 0.7 .20
7 x .7 = 4.9 .204 7 x .9 = 6.3 .2046
Repeats! .20462046···
Converting -25.7510 to 2’s Comp.
-25: 25 = 16 + 8 + 1 011001
-25 = 100111 .75: .75 = .5 + .25
.11 Combining results:
100111.112
Checking (poly eval): = -24.2510
Correct Method:
+25.75 = 16 + 8 + 1 + .5 + .25 = 011001.112
Find the negative representation:
100110.01 Check:
= 10011001/22
= (-128+16+8+1)/4 = -103/4
= -25.7510
Convert -75.7510 to 2’s complement
1st: Get Binary Magnitude
7510 = 64 + 8 + 2 + 1
= 26 + 23 + 21 + 20
= 10010112
.7510 = .5 + .25 = 2-1 + 2-2
75.7510 = 1001011.112
2nd: Convert to 2’s Complement
+75.7510 = 01001011.112 Find ─75.7510:
10110100.01
Make sure the most- significant bit is 0.
The most-significant bit must be “1” (negative), so the minimum number of bits is 10.
Convert 2’s Comp. 1001.01102 to decimal
1001.0110 (< 0) - Find pos. equiv:
Use poly. eval. w/neg. 1st term: 1001.0110:
= -8 + 1 + .25 + .125 = -7 + .375
= -6.62510
2’s Comp: Get decimal
Add minus sign
= 4+2+.5+.125 = 6.62510
Binary Number Systems
Part 6: Power Relationships
MOTIVATION
Hexadecimal is a convenient short-hand for binary:
• Hex (radix 16) numbers require 1/4th as many digits than their equivalent binary (radix 2) representation
• Easier for humansreduces transcription errors
Conversion is trivial due to power relationship (16 = 24):
• Each hex digit corresponds to a group of 4 binary digits.
• Easy to convert: Groups are independent of each other.
Hex/Binary Table
Example: Hex to Binary
Convert F1.2C16 to Binary: F1.2C
1111 0001 . 0010 11002
Example: Binary to Hex
Original binary number: 1011010.10010112
1. Split into groups of 4, starting at radix point: 101 1010 . 1001 011
Form groups working outward from the radix point!
2. Pad with 0’s to complete the groups: 0101 1010 . 1001 0110
3. Replace each group by equivalent hex digit: 5 A . 9 616
Example: 110101.0101012 to Hex
Use power relationship (16 = 24)
Form groups of 4 bits, starting at radix point: 0011 0101 . 0101 0100
0011 0101 . 0101 0100
Use Table to convert each group: 0011 0101 . 0101 0100
Converting Octal (Base 8) to Hex
1. Convert octal to decimal (polynomial evaluation)
2. Convert decimal to hex (repeated division/multiplication)
1. Convert octal to binary using short-cut (8 = 23) 2. Convert binary to hex using short-cut (16 = 24)
Example: 12.658?16
1. 12.658 = 001 010 . 110 1012 = 001010.1101012
2. 001010.1101012 = 0000 1010 . 1101 01002 = 0A.D416
Convert FA.CE16 to base 8
1st: Base 16 to base 2 (16=24)
F A . C E16 1111 1010 . 1100 11102
11111010.110011102
2nd: Base 2 to base 8 (8=23)
11111010.110011102 011 111 010 . 110 011 100
011 111 010.110 011 100 3 7 2 . 6 3 48
Convert 7849 to base 3
Use power relationship (9 = 32)
Each base 9 digit corresponds to 2 base 3 digits
Use table to convert each digit: 7 8 49
Review Problems
• Convert 110101.0101012 to hex (base 16)
• Convert unsigned FA.CE16 to base 8
• Convert unsigned 7849 to base 3
• Convert unsigned 256 to decimal
• Convert unsigned 2510 to base 7
• Convert -75.7510 to signed 2’s complement
• Convert 1001.01102 from 2’s comp. to decimal
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com