Transcript Chapter # 1: Introduction Contemporary Logic Design Randy

Chapter 1: Number
Systems and Codes
CS 3402-- Digital Logic
Design
7/21/2015
A. Berrached
1
Numbers Systems and Codes
How is information represented at the gate-level?
Only two symbols: 0 and 1
Information is coded using string combinations of
0s and 1s.
A code is a standard set of rules for representing
and interpreting information
Information:
» Numerical: unsigned and signed numbers
» Binary Coded Decimal codes
» Characters (textual information)
Positional Number Systems
Positional Notation (polynomial notation)
a number is represented with a string
(sequence) of digits
the position of each digit in the sequence
carries a weight
Example: decimal system
base 10 => 10 digits 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
4175.86 =
0
1
2
3
-1
5*10 + 7* 10 + 1* 10 +4* 10 + 8* 10 +6* 10
-2
Positional Number Systems
In base 10:
If a number N =dn-1dn-2 ….d1d0 . d-1… d-m
then
n-1
n-2
1
0
N = dn-1*10 + dn-2*10 +….+ d1*10 + d0*10
-1
-m
+ d-1*10 + ...
+ d-m*10
In any base r:
If a number (N)r = dn-1dn-2 ….d1d0 . d-1… d-m
then
(N)r = dn-1*r
n-1
-1
+ dn-2*r
n-2
+ d-1*r + ...+ d-m*r
1
+….+ d1*r + d0*r
-m
0
Binary Number System
N = 1101101.1012
N = (1*26) + (1*25) + (0*24) + (1*23) + (1*22) + (0*21) + (1*20) +
(0*2-1) + (1*2-2) + (1*2-3)
N = 64 + 32 + 0 + 8 + 4 + 0 + 1 + 1/2 + 0/4 + 1/8
N = 109.625
in base 10
in base 10
=> N = (109.625)10
To convert a number N from base b to base 10 use
method as shown above (series substitution method)
Base Conversion
From base b to base 10
• use series substitution method
• do arithmetic in base 10.
From base 10 to base b
• Integer part
» use successive divisions by b, until quotient is 0
» collect remainders: first remainder is the least
significant digit
• fraction part
» use successive multiplication by b
» collect integer part of each product
Base Conversion
Conversion from base A to base B
• convert number from base A to base 10
• covert resulting number from base 10 to base B.
Special cases
•
•
•
•
Conversion from binary to octal
Conversion from octal to binary
Conversion from binary to hexadecimal
Conversion from hexadecimal to binary
Binary Number Systems
Unsigned Binary Code
Signed Binary Codes
• 2’s Complement System
• BCD Code
• Excess Codes
Floating-Point System
Unsigned Binary Code
Given a number N in Unsigned Binary code,
find the value of N in the decimal system
Use series substitution method
Given a number N in the decimal system, find
the value of N in the Unsigned Binary Code.
Use successive division method (for integer part)
Use successive multiplication method (for fraction
part)
Unsigned Binary Code
Example 1: Represent (26)10 in Unsigned
Binary Code
2610 =
11010
Example 2: Represent (26)10 in Unsigned
Binary Code using 8 bits.
2610 = 00011010
Example 3: Represent (26)10 in Unsigned
Binary Code using 4 bits.
Can’t do. Not enough bits.
Unsigned Binary Code ( 4 bits)
Unsigned
Decimal
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Unsigned Binary Code
The Unsigned Binary Code is used to
represent positive integer numbers.
What is the range of values that can be
represented with n bits in the Unsigned Binary
Code?
[0, 2n-1]
How many bits are required to represent a
given number N?
number of bits = smallest integer greater than or equal to
log(N)
Unsigned Binary Code: Arithmetic &
Logic Operations
Arithmetic Operations:
•
•
•
•
Addition
Subtraction
Multiplication
Division
Logic Operations
•
•
•
•
AND
OR
NOT
XOR
CONJUNCTION
DISJUNCTION
NEGATION
EXCLUSIVE OR
Signed Binary Codes
These are codes used to represent positive and
negative numbers.
 Sign and Magnitude Code
 1’s Complement Code
 2’s Complement Code
Sign & Magnitude Code
The leftmost bit is the sign bit
• 0 for positive numbers
• 1 for negative numbers
The remaining bits represent the magnitude
of the number
Example:
Sign & Mag. Code
Decimal
01101
+13
11101
-13
00101
+5
10101
-5
Sign &Magnitude (4 bits)
Unsigned
Decimal
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
0
1
2
3
4
5
6
7
-0
-1
-2
-3
-4
-5
-6
-7
What is the range of values that can be represented in S&M
code with n bits?
Sign&Magnitude
Example 1: Represent (26)10 in Sign &
Magnitude Code.
2610 =
011010
Example 2: Represent (26)10 in Sign &
Magnitude Code using 8 bits
2610 =
0001 1010
Example 3: Represent (26)10 in Sign &
Magnitude Code using 5 bits.
• Need at least 6 bits.
Sign&Magnitude
Example 1: Represent (-26)10 in Sign & Magnitude
Code.
• 26
=
11010
• -2610 =
111010
Example 2: Represent (-26)10 in Sign & Magnitude
Code using 8 bits
• 26
=
00011010
• - 2610 =
10011010
Example 3: Represent (-26)10 in Sign & Magnitude
Code using 5 bits.
• Need at least 6 bits.
1’s Complement Code
Positive numbers:
• same as in unsigned binary code
• pad a 0 at the leftmost bit position
Negative numbers:
1. Represent the magnitude of the number in
unsigned binary system
2. pad a 0 at the leftmost bit position
3. complement every bit
1’s Complement Code
Example: represent 2610 in 1’s complement code
•
2610 =
11010
=
011010
• Pad a 0:
Example: Represent (-26)10 in 1’s complement
code.
1.
2. Pad a 0:
26
3. Complement:
=
11010
011010
100101
(-26)10 = (100101)1’s comp
1’s Complement Code
Example: Represent (-26)10 in 1’s comp. code
using 8 bits
1. Represent magnitude in unsigned binary using 8
bits
26 = 0001 1010
2. Complement every bit
11100101
-2610 = (1110 0101) 1’s comp
1’s Complement Code (4 bits)
Unsigned
Decimal
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
0
1
2
3
4
5
6
7
-7
-6
-5
-4
-3
-2
-1
-0
What is the range of values that can be represented in S&M
code with n bits?
[ -(2
(n-1)
-1) , 2
(n-1)
-1]
2’s Complement Code
This is the code commonly used to represent
integer numbers.
Positive Numbers:
• same as in unsigned binary code
• pad with a 0 leftmost bit position
Negative Numbers
1. represent magnitude in unsigned binary code
2. pad leftmost positions with 0s
3. complement every bit
4. add 1
2’s Complement Code
Example 1: Represent 26 in 2’s complement
code.
26 =
011010
Example 2: Represent 26 in 2’s complement
code using 8 bits
26 = 00011010
Example 3: Represent 26 in 2’s complement
code using 5 bits
• Need at least 6 bits.
2’s Complement Code
Example 3: Represent - 26 in 2’s comp.
Code
1.
2. Pad with a 0:
3. Complement:
4. Add 1:
+26 =
11010
011010
100101
+
1
--------------100110
2’s Complement Code
Example 4: Represent - 26 in 2’s comp.
Code using 8 bits
1.
2. Pad 0s:
3. Complement:
4. Add 1:
+26 =
11010
00011010
11100101
+
1
--------------11100110
2’s Complement Code
More example: represent 65 in 2’s comp.
Code.
• 65 =
(0100 0001)2’s comp
Represent - 65 in 2’s comp
• 65 = 0100 0001
• -65 = 1011 1111
Conversion from 2’s comp code to
decimal code
How to convert a number in 2’s Comp. Code
into the decimal code.
There 2 cases:
Case 1: If leftmost bit of the number is 0
=> number is positive
=> conversion is the same as in unsigned
binary code
Conversion from 2’s comp code to
decimal code
Case 2: If leftmost bit is 1
=> the number is negative
step1: complement every bit
step2: add 1
step3: convert result to decimal code using
same method as in unsigned binary
code.
Answer = the negative of the result of step 3.
2’s Complement Code (4 bits)
Unsigned
Decimal
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
0
1
2
3
4
5
6
7
-8
-7
-6
-5
-4
-3
-2
-1
Range of values with n bits:
[ -2
(n-1)
, 2
(n-1)
-1]
2’s Complement Arithmetic
Addition
Subtraction
Overflow
Hexadecimal Notation
 Hexadecimal system: base 16
 There are 16 digits:
• 0 123456789ABCDEF
 Each Hex digit represents a group of 4 bits
(i.e. half of a byte) 0000 thru 1111
 Generally used as shorthand notation for
binary numbers => easier to read
• Binary:
• Decimal:
• Hex:
0101 1010
5
10
5
A
1001
9
9
1110
14
E
Hexadecimal Notation
Examples:
• Binary:
• Hex:
1111 0110
F6
• Binary:
• Hex:
1001 1101 0000 1010
9D0A
• Hex:
• Binary
F6E7
1111 0110 1110 0111
Binary Coded Decimal Codes
A number is a sequence of decimal digits
Each digit is represented with a 4-bit number.
» BCD codes allow easy conversion to/from
decimal system
Natural Binary Coded Decimal Code (the BCD
code)
each decimal digit is represented with 4 bits in
base 2
e.g. 0 = 0000 3 = 0011 5= 0101 9 = 1001
N = 856.3710
N = 1000 0101 0110 . 0011 0111BCD
Excess-k Codes
Excess-3
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
Decimal
-3
-2
-1
0
1
2
3
4
5
6
7
8
9
10
11
12
Excess-8
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
Decimal
-8
-7
-6
-5
-4
-3
-2
-1
0
1
2
3
4
5
6
7