Transcript 211Lec01-Overview - Computer Science & Engineering

CSCE 211H Digital Design
Lecture 1
Binary Representation
Topics






August 24, 2015
Terminology
Base 10, Hex, binary
Fractions Base-r to decimal
Unsigned Integers
Signed magnitude
Two’s complement
Overview
Readings Chapter 1









–2–
Overview of Course
Analog vs Digital
Conversion Base-r to decimal
Conversion decimal to Base-r
Conversion of Fractions base-r  decimal
Unsigned Arithmetic
Signed Magnitude
Two’s Complement
Excess-1023
CSCE 211H Fall 2015
Chapter 1
Introduction
Click to edit Master
subtitle
style Companies, Inc. Permission required for reproduction or
Copyright
© The McGraw-Hill
display.
Course Outcomes
1.
Represent numbers and perform arithmetic in bases 2, 8, and 16
2.
Encode symbols and numbers in binary codes
3.
Add and subtract using 2’s complement code
4.
Evaluate and simplify logical functions using Boolean algebra
5.
Represent logical functions in Canonical form and with Gates
6.
Analyze and design combinatorial
7.
Simplify combinatorial circuits using Karnaugh
8.
Implement functions with NAND-NAND and NOR-NOR logic
9.
Analyze and design modular combinatorial logic circuits containing
decoders, multiplexers, demultiplexers, 7-segments display decoders and
adders
10. Use the concepts of state and state transition for analysis and design of
sequential circuits
11. Use the functionality of flip-flops for analysis and design of sequential
circuits
12. Software-hardware co-design (Arduino)
–4–
CSCE 211H Fall 2015
Performance Growth since 1978
–5–
Comp. Arch. Quantitative Approach - H&P Chapter 1: Figure1.1 CSCE 211H Fall 2015
Analog vs digital: Why Binary
–6–
CSCE 211H Fall 2015
Other bases
 Binary = Base 2
 Hexadecimal = Base 16
 Octal = Base 8
 Notations


Subscript
In C
 Conversions between bases
–7–
CSCE 211H Fall 2015
Note that the number one less than 2n consists of n 1’s (for example,
24 – 1 = 1111 = 15 and 25 – 1 = 11111 = 31).
–8–
CSCE 211H Fall 2015
Base-r to Decimal Conversions
Converting base-r to decimal by definition
dndn-1dn-2…d 2d 1d 0(base r) = dnrn + dn-1rn-1… d2r2 +d 1r1 + d 0r0
Example
4F0C16
–9–
=
4*163 + F*162 + 0*161 + C*160
=
4*4096 + 15*256 + 0 + 12*1
=
16384
=
20236
+ 3840 + 12
CSCE 211H Fall 2015
Decimal to Base-r Conversion
Repeated division algorithm
Justification:
dndn-1dn-2…d 2d 1d 0 = dnrn + dn-1rn-1… d2r2 +d 1r1 + d 0r0
Dividing each side by r yields
(dndn-1dn-2…d 2d 1d 0) / r = dnrn-1 + dn-1rn-2… d2r1+d 1r0 + d 0r-1
So d 0 is the remainder of the first division
((q1) / r = dnrn-2 + dn-1rn-3… d3r1+d 2r0 + d 1r-1
So d 1 is the remainder of the next division
and d 2 is the remainder of the next division
…
– 10 –
CSCE 211H Fall 2015
Decimal to Base-r Conversion Example
Repeated division algorithm Example
Convert 4343 to hex
4343/16 = 271 remainder = 7
271/16 =
16 remainder = 15
16/16 =
1 remainder = 0
1/16 =
0 remainder = 1
So 434310 = 10F716
To check the answer convert back to decimal
10F7 = 1*163 + 15*16 + 7*1 = 4096 + 240 + 7 = 4343
– 11 –
CSCE 211H Fall 2015
Hex to Binary
One hex digit = four binary digits
Example
3FAC = 0011 1111 1010 1100
(spaces just for readability)
Binary to hex

four binary digits  one hex digit (group from right!!!)
Example
101101001111010 = 0010 1101 0011 1010
=
– 12 –
2
D
3
A
CSCE 211H Fall 2015
Hex to Decimal Fractions
.d-1d-2d-3…d –(n-2)d –(n-1)d -n= d-1r-1 + d-2r-2…d-(n-1)r-(n-1) +d 1r-n
Example
.1EF16
= 1*16-1 + E*16-2 + F*16-3
= 1*.0625 + 14*.003906025 + 15*2.4414e-4
= .117201… (probably close but not right)
– 13 –
CSCE 211H Fall 2015
Example: Hex Fractions to decimal
Convert .3FA to decimal
.3FA16 = 3*16-1 + F*16-2 + A*16-3
= 3*.0625 + 15*.00390625 +10* (1/4096)
= .191162109
– 14 –
CSCE 211H Fall 2015
Decimal Fractions to hex
.d-1d-2d-3…d –(n-2)d –(n-1)d -n= d-1r-1 + d-2r-2…d-(n-1)r-(n-1) +d 1r-n
Multiplication by r yields
r *(.d-1r-1 + d-2r-2…d-(n-1)r-(n-1) +d 1r-n )
= d-1r0 + d-2r-1…d-(n-1)r-(n-2) +d 1r-(n-1)
Whole number part = d-1r0
Multiplying again by r yields d-2r0 as the whole number
part
… till fraction = 0
– 15 –
CSCE 211H Fall 2015
Example Decimal Fraction to hex
By repeated multiplication
– 16 –
CSCE 211H Fall 2015
Unsigned integers
What is the binary representation of the biggest integer
representable using n-bits(n binary digits)?
What is its value in decimal?
Special cases
8 bits
16 bits
32 bits
– 17 –
CSCE 211H Fall 2015
Arithmetic with Binary Numbers
10010110
10010110
1101
+00110111
- 00110111
x 101
Problems with 8 bit operations
10010110
+ 10010110
– 18 –
CSCE 211H Fall 2015
– 19 –
CSCE 211H Fall 2015
Signed integers
How do we represent?
Signed-magnitude
Excess representations
w bits  0 <= unsigned_value < 2w
In excess-B we subtract the bias (B) to get the value.
example
– 20 –
CSCE 211H Fall 2015
Complement Representations of
Signed integers
One’s complement
Two’s complement
– 21 –
CSCE 211H Fall 2015
Two’s Complement Operation
One’s complement + 1 or
Find rightmost 1, complement all bits to the left of it.
Examples
01001110
– 22 –
00000001
00000000
00000010
CSCE 211H Fall 2015
Two’s Complement Representation
Consider a two’s complement binary number
dndn-1dn-2…d 2d 1d 0
If dn , the sign bit = 0 the number is positive and its
magnitude is given by the other bits.
If dn , the sign bit = 1 the number is negative and take its
two’s complement to get the magnitude.
Weighted Sum Interpretation
0
1
1
2
…
n-1 2 n-2
n
– 23 –
-2 n-1
CSCE 211H Fall 2015
Two’s Complement Representation
Consider a two’s complement binary number
dndn-1dn-2…d 2d 1d 0
If dn , the sign bit = 0 the number is positive and its
magnitude is given by the other bits.
If dn , the sign bit = 1 the number is negative and take its
two’s complement to get the magnitude.
Weighted Sum
0
1
1
2
Example 10010011 =
…
n-1 2 n-2
n
– 24 –
-2 n-1
CSCE 211H Fall 2015
Two’s Complement Representation
What is the 2’s complement representation in 16 bits of
–5?
+7?
-1?
0
-2
– 25 –
CSCE 211H Fall 2015
– 26 –
CSCE 211H Fall 2015
Arithmetic with Signed Integers
Signed Magnitude Addition
if the signs are the same add the magnitude
if the signs are different subtract the smaller from the
larger and use the sign of the larger
Subtraction?
Two’s complement
Just add signs take care of themselves
– 27 –
CSCE 211H Fall 2015
Overflow in Two’s Complement
– 28 –
CSCE 211H Fall 2015
– 29 –
CSCE 211H Fall 2015
Binary Code Decimal
– 30 –
Floating point – IEEE 754
CSCE 211H Fall 2015
Representations of Characters
– 31 –
CSCE 211H Fall 2015
– 32 –
CSCE 211H Fall 2015
ASCII Message on the Wall
Princeton CS Building West Wall Bricks
This brick pattern is located on the west wall of the
Computer Science building, and dates back to 1989,
when the building was constructed. The pattern is
read top to bottom and consists of five 7-bit ASCII
values. The vertical lines to the left and right are
"framing" bits. (Table 1.8 page 18 previous slide)
x1010000x
x0111101x
x1001110x
x1010000x
x0111111x
– 33 –
This pattern asks _________?
http://www.cs.princeton.edu/general/bricks
CSCE 211H Fall 2015
– 34 –
CSCE 211H Fall 2015
Basic Gates
AND
OR
NOT
– 35 –
CSCE 211H Fall 2015
Basic Gates
NAND
NOR
XOR
– 36 –
CSCE 211H Fall 2015
Half Adder Circuit; Full Adder
– 37 –
CSCE 211H Fall 2015
Homework Due at the start of class
Wednesday
Page 25
1. 1.*a, b,f
2. 2h
3. 3b
4. 4b
5. 5a, 5c
6. 7a,b
7. Convert 137.125 to hex and then to binary
8. Convert 137.1 to hex, rounding to 6 hex digits after the
“decimal” point.
– 38 –
CSCE 211H Fall 2015