Transcript Lecture Notes on ``Number Systems`` (PPT Slides)

ENG241
Digital Design
Week #1
Digital Computers and Information
Resources

Chapter #1, Mano Sections





1.1
1.2
1.3
1.4
1.5
Digital Computers
Number Systems
Arithmetic Operations
Decimal Codes
Alphanumeric Codes
2
Topics








Computing Devices and VLSI Design
Signals (Digital vs. Analog)
Digital Systems and Computers
Number systems [binary, octal, hex]
Base Conversion
Arithmetic Operations
Decimal Codes [BCD]
Alphanumeric Codes
3
Computing Devices Everywhere!
Car
PDA
PC
Home Networking
Game console
Household
Body
Super Computer
Entertainment
Medicine
Communication
4
The Transistor Revolution
First transistor
Bell Labs, 1948
Bipolar logic
1960’s
• Intel 4004 processor
• Designed in 1971
• Almost 3000 transistors
• Speed:1 MHz operation
5
VLSI Design Styles
Vdd
Contact
Metal layer
Vdd
IN2
OUT
IN1
IN1
Poly layer
OUT
Diffusion layer
p-type
transistor
GND
GND
n-type
transistor
OUT
Power (Vdd)-Rail
Ground (GND)-Rail
6
Lienig
IN1
IN2
IN2
© KLMH
1.3
The VLSI Design Cycle
Specification
SYSTEM
Functional design
MODULE
+
Logic design
GATE
Circuit design
CIRCUIT
Physical design
Test/Fabrication
G
S
n+
D
n+
DEVICE
Signals

An information variable represented by
a physical quantity (speech, Temp,
humidty, noise, …)
8
Signals
Signals can be analog or digital:
1. Analog signals can have an infinite number of values in a
range;
2. Digital signals can have only a limited number of values.
9
Analog Signals
Time
Analog
Continuous in
value & time
10
Digital Signals

For digital systems, the variable takes
on discrete values (i.e., not continuous)
Time
Digital
Discrete in
value
11
Signal Examples Over Time

Digital (Binary) values are represented by:



digits 0 and 1 / False (F) and True (T)
words (symbols) Low (L) and High (H)
words On and Off.
DigitalTime
Asynchronous
Synchronous
Discrete in
value &
continuous
in time
Discrete in
value & time
12
Binary Values: Other Physical Quantities

What are other physical
quantities represent 0 and 1?
CPU
Voltage
Magnetic Field Direction
 HDisk
Surface Pits/Light
 CD
Electrical Charge
 Dynamic RAM

13
Digital System Example:
A Digital Counter (e. g., odometer):
Count Up
Reset
0 0 1 3 5 6 4
Inputs: Count Up, Reset
Outputs: Visual Display
"Value" of stored digits
State:
14
A Digital Computer Example
Data/Instructions/code
Memory
clock
CPU
Inputs:
Keyboard,
mouse, modem,
microphone
Control
unit
Datapath
Input/Output
Outputs: CRT,
LCD, modem,
speakers
15
Number Systems – Representation

A number with radix r is represented by a
string of digits:
A n - 1A n - 2 … A 1A 0 . A - 1 A - 2 … A - m + 1 A - m
in which 0 Ai < r and “.” is the radix point.

The string of digits represents the power series:
(
i=n-1
(Number)r =
i=0
Ai
r )+( 
j=-1
i
Aj
r)
j
j=-m
(Integer Portion) + (Fraction Portion)
16
Decimal Number System
 Base (also called radix) = 10
● 10 digits { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
 Digit Position
● Integer & fraction
 Digit Weight
2
1
0
5 1 2
100
-1
-2
7 4
10
1
0.1 0.01
10
2
0.7 0.04
● Weight = (Base) Position
 Magnitude
● Sum of “Digit x Weight”
 Formal Notation
500
d2*B2+d1*B1+d0*B0+d-1*B-1+d-2*B-2
(512.74)10
17
Octal Number System
 Base = 8
● 8 digits { 0, 1, 2, 3, 4, 5, 6, 7 }
 Weights
● Weight = (Base) Position
 Magnitude
● Sum of “Digit x Weight”
 Formal Notation
64
8
1
1/8 1/64
5 1 2
7 4
2
-1
1
0
-2
5 *8 2+1 *8 1+2 *8 0+7 *8- 1+4 *8 -2
=(330.9375)10
(512.74)8
18
Octal Number System: Example

For Example,

(27)8 can be expressed as: (

(17.1)8 can be expressed as:
(
)10
)10
19
Hexadecimal Number System
 Base = 16
● 16 digits { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F }
 Weights
● Weight = (Base) Position
 Magnitude
● Sum of “Digit x Weight”
 Formal Notation
256
16
1
1/16 1/256
1 E 5
7 A
2
-1
1
0
-2
1 *162+14 *161+5 *160+7 *16-1+10 *16-2
=(485.4765625)10
(1E5.7A)16
20
Hex to Decimal

Just multiply each hex digit by
decimal value, and add the
results.
(2ac)16
2 • 256
+ 10 • 16 + 12 • 1 = (684)10




163
162
161
160
4096
256
16
1
Dec Hex
0
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
10
a
11
b
12
c
13
d
14
e
15
f
21
Binary Number System
 Base = 2
● 2 digits { 0, 1 }, called binary digits or “bits”
4
 Weights
● Weight = (Base)
Position
 Magnitude
1
1/2 1/4
1 0 1
0 1
2
-1
1
0
-2
1 *22+0 *21+1 *20+0 *2-1+1 *2-2
● Sum of “Bit x Weight”
 Formal Notation
 Groups of bits
2
=(5.25)10
(101.01)2
4 bits = Nibble
1011
8 bits = Byte
11000101
22
Binary  Decimal: Example
7
6
5
4
3
2
1
0
27
26
25
24
23
22
21
20
128
64
32
16
8
4
2
1
position
value
What is 10011100 in decimal?
7
6
1
0
5
0
4
3
2
1
0
position
1
1
1
0
0
Binary #
128 + 0 + 0 + 16 + 8 + 4 + 0 + 0 = 156
23
Why Binary?
This is easier to implement in hardware than a unit
that can take on 10 different values.
● For instance, it can be represented by a transistor being
off (0) or on (1).
● Alternatively, it can be a magnetic stripe that is
magnetized with North in one direction (0) or the
opposite (1).
Binary also has a convenient and natural
association with logical values of:
● False (0) and
● True (1).
24
Binary Numbers
 Examples:
(00)2  (0)10
 (01)2  (1)10
 (10)2  (2)10
 (010)2  (2)10
 (11)2  (3)10
 (100)2  (4)10
 (1001010101000)2

 Strings
of binary digits (“bits”)
 One
bit can store a number from 0 to 1
 n bits can store numbers from 0 to 2n-1
25
The Power of 2
n
2n
n
2n
0
20=1
8
28=256
1
21=2
9
29=512
2
22=4
10
210=1024
3
23=8
11
211=2048
4
24=16
12
212=4096
5
25=32
20
220=1M
Mega
6
26=64
30
230=1G
Giga
7
27=128
40
240=1T
Tera
Kilo
26
Number Base Conversions
Evaluate
Magnitude
Octal
(Base 8)
Evaluate
Magnitude
Decimal
(Base 10)
Binary
(Base 2)
Hexadecimal
(Base 16)
Evaluate
Magnitude
27
Conversion Between Bases
 To convert from one base to another:
1) Convert the Integer Part
2) Convert the Fraction Part
3) Join the two results with a radix point
28
Decimal (Integer) to Binary Conversion
 Divide the number by the ‘Base’ (=2)
 Take the remainder (either 0 or 1) as a coefficient
 Take the quotient and repeat the division
Example: (13)10
Quotient
Remainder
Coefficient
6
3
1
0
1
0
1
1
a0 = 1
a1 = 0
a2 = 1
a3 = 1
13/ 2 =
6 /2=
3 /2=
1 /2=
Answer:
(13)10 = (a3 a2 a1 a0)2 = (1101)2
MSB
LSB
29
Decimal to Binary Conversion
Decimal (Fraction) to Binary Conversion
 Multiply the number by the ‘Base’ (=2)
 Take the integer (either 0 or 1) as a coefficient
 Take the resultant fraction and repeat multiplication
Example: (0.625)10
Integer
0.625 * 2 =
0.25 * 2 =
0.5
*2=
Answer:
1
0
1
.
.
.
Fraction
Coefficient
25
5
0
a-1 = 1
a-2 = 0
a-3 = 1
(0.625)10 = (0.a-1 a-2 a-3)2 = (0.101)2
MSB
LSB
31
Decimal to Octal Conversion
Example: (175)10
Quotient
175 / 8 =
21 / 8 =
2 /8=
Remainder
Coefficient
7
5
2
a0 = 7
a1 = 5
a2 = 2
21
2
0
Answer:
(175)10 = (a2 a1 a0)8 = (257)8
Example: (0.3125)10
Integer
0.3125 * 8 = 2
0.5
*8= 4
Answer:
.
.
Fraction
Coefficient
5
0
a-1 = 2
a-2 = 4
(0.3125)10 = (0.a-1 a-2 a-3)8 = (0.24)8
32
Decimal to Hex
(684)10
c
684/16 = 42 rem 12=c
ac
42/16 = 2 rem 10=a
2/16 = 0
rem 2
2ac




163
162
161
160
4096
256
16
1
Dec Hex
0
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
10
a
11
b
12
c
13
d
14
e
15
f
33
Hexadecimal (Base 16)
Strings of 0’s and 1’s too hard to write
 Use base-16 or hexadecimal – 4 bits

Dec
Bin
Hex
Dec
Bin
Hex
0
0000
0
8
1000
8
1
0001
1
9
1001
9
2
0010
2
10
1010
a
3
0011
3
11
1011
b
4
0100
4
12
1100
c
5
0101
5
13
1101
d
•Power of 2
6
0110
6
14
1110
e
•Size of byte
7
0111
7
15
1111
f
Why use
base 16?
34
Hex to Binary
Convention – write 0x (prefix)
before number
 Hex to Binary – just convert digits

0x2ac
0010
(2ac)16
1010 1100
0x2ac = (001010101100)2
No magic – remember hex digit = 4 bits
Bin
Hex
0000
0
0001
1
0010
2
0011
3
0100
4
0101
5
0110
6
0111
7
1000
8
1001
9
1010
a
1011
b
1100
c
1101
d
1110
e
1111
f
35
Binary − Hexadecimal Conversion
 16 = 24
 Each group of 4 bits represents
a hexadecimal digit
Assume Zeros
Example:
( 1 0 1 1 0 . 0 1 )2
(1
6
. 4 )16
Hex
Binary
0
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
Works both ways (Binary to Hex & Hex to Binary)
36
Binary to Hex

Just convert groups of 4 bits
(101001101111011)2
0101  0011  0111  1011
5
3
7
b
101001101111011 = 0x537b = (537b)16
Bin
Hex
0000
0
0001
1
0010
2
0011
3
0100
4
0101
5
0110
6
0111
7
1000
8
1001
9
1010
a
1011
b
1100
c
1101
d
1110
e
1111
f
37
Octal − Hexadecimal Conversion
 Convert to Binary as an intermediate step
Example:
( 2
6
.
2 )8
Assume Zeros
Assume Zeros
( 0 1 0 1 1 0 . 0 1 0 )2
(1
6
.
4 )16
Works both ways (Octal to Hex & Hex to Octal)
38
Addition
 Decimal Addition
1
+
1
1
Carry
5
5
5
5
1
0
= Ten ≥ Base
 Subtract a Base
39
Binary Addition
 Column Addition
1
1
1
1
1
1
1
1
1
1
0
1
= 61
1
0
1
1
1
= 23
1
0
1
0
0
= 84
+
1
0
≥ (2)10
40
Binary Subtraction
 Borrow a “Base” when needed
0
1
2
2
0
0
2
1
0
0
1
1
0
1
= 77
1
0
1
1
1
= 23
1
0
1
1
0
= 54
−
0
1
2
= (10)2
41
Binary Multiplication
 Bit by bit
1
0
1
1
1
1
0
1
0
0
0
0
0
0
1
0
1
1
1
0
0
0
0
0
1
0
1
1
1
1
1
1
0
0
x
1
1
0
42
Binary Numbers and Binary Coding

Flexibility of representation


Within constraints below, can assign any
binary combination (called a code word) to
any data as long as data is uniquely encoded.
Information Types

Numeric




Must represent range of data needed
Very desirable to represent data such that
simple, straightforward computation for
common arithmetic operations permitted
Tight relation to binary numbers
Non-numeric


Greater flexibility since arithmetic operations
not applied.
Not tied to binary numbers
43
Non-numeric Binary Codes



Given n binary digits (called bits), a binary code is a
mapping from a set of represented elements to a subset of
the 2n binary numbers.
Example: A
Color
Binary Number
binary code
Red
000
for the seven
Orange
001
colors of the
Yellow
010
rainbow
Green
011
Code 100 is
Blue
101
not used
Indigo
110
Violet
111
44
Number of Bits Required

Given M elements to be represented by a
binary code, the minimum number of bits, n,
needed, satisfies the following relationships:
2n > M > 2(n – 1)
n = log2 M where x , is called the ceiling
function, i.e the integer greater than or
equal to x.
45
Number of Bits Required
 Given M elements to be represented by a binary
code, the minimum number of bits, n, needed,
satisfies the following relationships:
2 n  M  2 n 1 , where
n  log 2 M   ceiling (log 2 M )
 Example: How many bits are required to represent
decimal digits with a binary code?
• M = 10, hence n = ceiling (log2 10) = ceiling (3.3219) = 4
• Checking:
2 4  16  10  23  8
46
Binary Codes
 Group of n bits
n
● Up to 2 combinations
● Each combination represents an element of information
Binary Coded Decimal (BCD)
● Each Decimal Digit is represented
by 4 bits
● (0 – 9)  Valid combinations
● (10 – 15)  Invalid combinations
Decimal
0
1
2
3
4
5
6
7
8
9
BCD
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
47
Gray Code
 One bit changes from
one code to the next
code
 Different than Binary
Decimal Gray
00
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
0000
0001
0011
0010
0110
0111
0101
0100
1100
1101
1111
1110
1010
1011
1001
1000
Binary
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
48
Binary Representations

A bit is the most basic unit of information in a computer.
 It is a state of “on” or “off” in a digital circuit.
 Sometimes these states are “high” or “low” voltage instead
of “on” or “off..”

A group of four bits is called a nibble (or nybble).

Bytes, therefore, consist of two nibbles: a “high-order
nibble,” and a “low-order” nibble.
A byte is a group of eight bits.
 A byte is the smallest possible addressable (can be found
via its location) unit of computer storage.

A word is a contiguous group of bytes.


Words can be any number of bits (16, 32, 64 bits are
common).
49
Conversion or Coding?

Do NOT mix up conversion of a decimal
number to a binary number with coding a
decimal number with a BINARY CODE.

(13)10 = (1101)2 (This is conversion)

(13)BCD  (0001|0011)BCD (This is coding)
Advantages/Disadvantages?
50
BCD: Advantages/Disadvantages

Disadvantage:
 It is obvious that a BCD number needs
more bits than its equivalent binary
value



(26)10 = (11010)2
(26)10 = (0010 0110)BCD
Advantages:

Computer input/output data are handled by
people who use the decimal system. So it is
easier to convert back/forth to BCD.
51
Character Codes


From numbers to letters
ASCII



Stands for American Standard Code
for Information Interchange
Only 7 bits defined
Unicode
52
ASCII Code
American Standard Code for Information Interchange
Info
7-bit Code
A
B
1000001
1000010
Z
1011010
a
b
1100001
1100010
z
1111010
@
?
+
1000000
0111111
0101011
.
.
.
.
.
.
.
.
.
.
.
.
53
ASCII table
54
Error Detecting Codes
 Parity
One bit added to a group of bits to make the total number
of ‘1’s (including the parity bit) even or odd
4-bit Example
7-bit Example
● Even
1
0 1 1 1
0
1 0 0 0 0 0 1
● Odd
0
0 1 1 1
1
1 0 0 0 0 0 1
 Good for checking single-bit errors
55
Reading

Read Chapter 1



Make sure you’re comfortable with
material
Check the lecture notes from the
Web site.
Solve the assignment.
56
Homework


See Assignment #1 On Web
I expect you to know number
systems well and be able to do
conversions and arithmetic





Decimal – Binary
Binary – Decimal
Decimal – Hex
Hex – Decimal
Will be on test!
57
58