Transcript 211Lec02-NumberRepAndOverflow

CSCE 211 Digital Design
Lecture 2
Number Representation,
Overflow and Logic
Topics



Adders
Math Behind Excess-3
Overflow
 Unsigned, signed-magnitude
 Two’s Complement


August 26, 2015
Gray Code
Boolean Logic
Last Time:!

Base R  Base 10 conversions
 Base R  Base 10
 Base 10  Base R
 Base 10 fractions  Base R fractions



Ripple carry adder
Signed Magnitude
Two’s complement
New:

Things from last Lecture: Slides 20-31
 Two’s Complement arithmetic
 Basic Gates: AND, OR, NOT, XOR, NOR, NAND





Adders
Binary Coded Decimal
Two’s Complement Overflow
Gray Code
Boolean Logic
Homework

1) Two’s complement of 87, and 2) Two’s complement of -43,
3) 2.26 (sign extension), and 4) 2.29,
Email:
mm @ sc.edu
–2–
CSCE 211H Fall 2015
–3–
CSCE 211H Fall 2015
–4–
CSCE 211H Fall 2015
–5–
CSCE 211H Fall 2015
Octal Arithmetic
1776
8432
+ 1432
- 1776
–6–
CSCE 211H Fall 2015
Ripple Carry Adder
–7–
CSCE 211H Fall 2015
Excess n code
Excess-3 code
Excess-127 code for IEEE 754 floating point
–8–
CSCE 211H Fall 2015
Excess-3 Code for Decimals Justification
ex3[7] =
1010
+ ex3[4] =
0111
10001
// excess-3 representation
// carry=1, sum=0001 not correct ex3
// it should be 0100 which is 0001+0011
So if there is a carry then we should correct the sum by adding 3.
The math behind this is
If x + y >= 10 then ex3[x] +ex3[y] = bcd[x] + 3 + bcd[y] + 3
But since x+y =bcd[x] + bcd[y] >= 10 we have
ex3[x] +ex3[y] = bcd[x]+bcd[y] + 6 >= 10 + 6 = 16
So the carry is correct but the sum digit =
(ex3[x] +ex3[y]) mod 16 = (bcd[x]+bcd[y] +6) - 16
So the sum digit is the correct bcd of (x+y) but not excess-3 so we need
to add 3.
–9–
CSCE 211H Fall 2015
Excess-3 Code for Decimals Justification
ex3[2] =
0101
+ ex3[6] =
1001
// excess-3 representation
1110
So if there is no carry then we should correct the sum by ...
And the math in this case:
If x + y < 10 then
ex3[x] + ex3[y] =
– 10 –
CSCE 211H Fall 2015
Why Excess-3 Code for Decimals ?
– 11 –
CSCE 211H Fall 2015
IEEE 754 floating pt – Excess 127
IEEE 754 single-precision binary floating-point format:
binary32
The IEEE 754 standard specifies a binary32 as having:
Sign bit: 1 bit
Exponent width: 8 bits
Significand precision: 24 bits (23 explicitly stored)
– 12 –
http://en.wikipedia.org/wiki/Single_precision
CSCE 211H Fall 2015
One more example
0 11110000 10101 0000 …000
– 13 –
http://en.wikipedia.org/wiki/Single_precision
CSCE 211H Fall 2015
Special Exponents
Expfield = e  expField = 1111 1111
expField = 0000 0000
– 14 –
CSCE 211H Fall 2015
Floating point demographics
How many 32 bit IEEE754 floats are there?
Easier question first how many positive floats with
expField = 1000 0000?
– 15 –
CSCE 211H Fall 2015
Floating point operations
Addition
Multiplication
– 16 –
CSCE 211H Fall 2015
What is overflow?
In general what does overflow mean?
For unsigned integers?
Examples
For signed magnitude or two’s complement what does
overflow mean?
For floats? Underflow?
– 17 –
CSCE 211H Fall 2015
Overflow in Two’s Complement
xn xn-1 xn-2 …
x2 x1 x0
+ yn yn-1 yn-2 …
y2 y1 y0
sn+1sn sn-1 sn-2 …
s2 s1 s0
Overflow
Case 1 positive + positive = negative !?

Meaning of course that the sign bits of both addends is 0
and the sign bit of the sum is 1
Case 2 …
– 18 –
CSCE 211H Fall 2015
Gray Code
In some mechanical devices you want to encode
positions as binary strings in such a way that
positions close to each other are represented by
strings that are close together.
Gray code – adjacent positions differ in only one bit








000
001
011
010
110
111
101
100
Figure 2-6 encoding disk
– 19 –
CSCE 211H Fall 2015
Construction of Gray Codes
Gray Codes are reflective
Algorithm for construction of Gray Codes on n-bits
1. A 1-bit Gray code has two words 0 and 1.
2. The first 2n words of an (n+1)-bit gray code are the
words of the n-bit gray code with a leading 0 added.
3. The next 2n words of an (n+1)-bit gray code are the
words of the n-bit gray code but written in reverse
order with a leading 1 added.
– 20 –
CSCE 211H Fall 2015
Construction of Gray Codes
1-bit gray code


0
1
4-bit gray code

0 000
2-bit gray code




00
01
11
10
3-bit gray code








0 00
0 01
0 11
0 10
1 10
1 11
1 01
1 00
– 21 –
CSCE 211H Fall 2015
Representations of Characters
How many characters do we need to represent?
How many bits does this take ?
ASCII
UNICODE
– 22 –
CSCE 211H Fall 2015
Codes representing characters
ASCII - American Standard Code for Information Interchange



8 bits = 7 + parity
ASCII table in chapter 2, (Table 2-11)
32 Control characters + 96 printable characters
Unicode 16 bits
– 23 –
http://en.wikipedia.org/wiki/ASCII
CSCE 211H Fall 2015
N-cubes
1-cube
2-cube
3-cube
Traversing in gray-code order
– 24 –
CSCE 211H Fall 2015
Parity Bits
Even parity bit – parity bit is set so that the number of
ones is even
Odd parity bit
– 25 –
CSCE 211H Fall 2015
Error Correcting codes
For an n-bit code, consider the hypercube of dimension n
Choose some subset of the nodes as code words.
Suppose the distance between any two two code words is at least 3.
Now consider transmission errors.
Then if there is an error in transmitting just one bit then the distance
from the received word to one code word is one, distances to
other code words are at least two.
Single error correcting, double error detecting.
Such codes are called Hamming codes after their inventor Richard
Hamming.
– 26 –
CSCE 211H Fall 2015
Boolean Algebra
George Boole (1854) invented a two valued algebra
To “give expression … to the fundamental laws of
reasoning in the symbolic language of a Calculus.”
1938 Claude Shannon at Bell Labs noted that this
Boolean logic could be used to describe switching
circuits. (Switching Algebra)
In Shannon’s view a relay has two positions open and
closed representing 1 and 0. Collections of relays
satisfied the properties of Boolean algebra.
– 27 –
CSCE 211H Fall 2015
Homework Set 2
1. What is the representation of the maximum unsigned integer using
12 bits?
a)
Representation (string of 12 bits) (b) value in decimal
2. What is the representation of the maximum two’s complement
integer using 12 bits?
a)
b)
c)
Representation (string of 12 bits) (b) value in decimal
What is the representation of -37 in two’s complement using 12 bits?
Representation (string of 12 bits) (b) value in decimal
3. IEEE-754 32 bit float
a)
What is the representation and value of the largest (non infinite) float?
b)
What is the representation of 212.375 as a IEEE 754 float?
How many floats are there >= 16 ?
Are there more positive floats > 16 or < 16?
c)
d)
– 28 –
CSCE 211H Fall 2015