Transcript ECE 301 – Digital Electronics

ECE 301 – Digital Electronics
Representation of Negative Numbers,
Binary Arithmetic of Negative Numbers,
and
Binary Codes
(Lecture #11)
The slides included herein were taken from the materials accompanying
Fundamentals of Logic Design, 6th Edition, by Roth and Kinney,
and were used with permission from Cengage Learning.
Representation of Negative Numbers
(continued)
Spring 2011
ECE 301 - Digital Electronics
2
Signed Binary Numbers
Representations for signed binary numbers:
1. Sign and Magnitude
2. 1's Complement
3. 2's Complement
Spring 2011
ECE 301 - Digital Electronics
3
Signed Binary Numbers




Arithmetic circuits are difficult to design for Sign and
Magnitude binary numbers.
Consequently, this number system is not typically
used in digital (computer) systems.
Instead other number systems, namely the 1's and
2's Complements, are more commonly used.
As we will see, it is rather easy to design arithmetic
circuits for binary numbers represented in these
number systems.
Spring 2011
ECE 301 - Digital Electronics
4
1's Complement


A positive number, N, is represented in the
same way as in the Sign and Magnitude
representation.
For an n-bit number,

The leftmost bit (sign bit) = 0.


Spring 2011
Indicating a positive number.
The remaining n-1 bits represent the
magnitude.
ECE 301 - Digital Electronics
5
1's Complement

A negative number, -N, is represented by the
“1's complement” of the positive number, N.

N' = 1's complement representation for -N.

For an n-bit signed binary number,
N' = (2n – 1) – N

Spring 2011
The leftmost bit (sign bit) = 1 for all negative
numbers in the 1's Complement system.
ECE 301 - Digital Electronics
6
1's Complement: Examples
Using 8 bits, determine the 1's Complement
representation for the following negative
numbers:
-15
-102
Spring 2011
ECE 301 - Digital Electronics
7
1's Complement

The 1's Complement representation for -N can
also be determined by taking the bit-wise
complement of N.

N' = 1's Complement representation for -N.

For an n-bit signed binary number,
N' = bit-wise complement of N

Spring 2011
i.e. complement N, bit-by-bit
ECE 301 - Digital Electronics
8
1's Complement: Examples
Using 8 bits, determine the 1's Complement
representation for the following negative
numbers:
-15
-102
(Use the bit-wise complement)
Spring 2011
ECE 301 - Digital Electronics
9
1's Complement

For an n-bit 1's Complement binary number,
- (2n-1 – 1) <= N <= + (2n-1 – 1)
Spring 2011

Includes a representation for +0 and -0.

Represents an equal number of positive and
negative values.
ECE 301 - Digital Electronics
10
1's Complement

To determine the magnitude of a negative
number, -N, that is represented by its 1's
Complement, N', simply take the “1's
complement” of the 1's Complement.
N = (2 – 1) – N'
n
positive #
1's complement rep.
for negative #
or
N = bit-wise complement of N'
Spring 2011
ECE 301 - Digital Electronics
11
2's Complement


A positive number, N, is represented in the
same way as in the Sign and Magnitude
representation.
For an n-bit number,

The leftmost bit (sign bit) = 0.


Spring 2011
Indicating a positive number.
The remaining n-1 bits represent the
magnitude.
ECE 301 - Digital Electronics
12
2's Complement

A negative number, -N, is represented by the
“2's complement” of the positive number, N.

N* = 2's complement representation for -N.

For an n-bit signed binary number,
N* = (2n) – N

Spring 2011
The leftmost bit (sign bit) = 1 for all negative
numbers in the 2's Complement system.
ECE 301 - Digital Electronics
13
2's Complement: Examples
Using 8 bits, determine the 2's Complement
representation for the following negative
numbers:
-12
-95
Spring 2011
ECE 301 - Digital Electronics
14
2's Complement
The 1's and 2's Complement representations for
a negative number, -N, are related as follows:
N' = (2 - 1) – N
N* = (2n) – N
n
N* = N' +1
Spring 2011
ECE 301 - Digital Electronics
15
2's Complement


Thus, the 2's Complement representation for N can also be determined by adding 1 to the
1's Complement representation for -N.

N' = 1's Complement representation for -N.

N* = 2's Complement representation for -N.
For an n-bit signed binary number,
N* = N' + 1
Spring 2011
ECE 301 - Digital Electronics
16
2's Complement: Examples
Using 8 bits, determine the 2's Complement
representation for the following negative
numbers:
-12
-95
(Use the 1's complement)
Spring 2011
ECE 301 - Digital Electronics
17
2's Complement

For an n-bit 2's Complement binary number,
- (2n-1) <= N <= + (2n-1 – 1)
Spring 2011

Includes only one representation for 0.

Represents an additional negative value.
ECE 301 - Digital Electronics
18
2's Complement

To determine the magnitude of a negative
number, -N, that is represented by its 2's
Complement, N*, simply take the “2's
complement” of the 2's Complement.
N = (2 ) – N*
n
positive #
2's complement rep. for negative #
or
N = (N*)' + 1
bit-wise complement of 2's complement
Spring 2011
ECE 301 - Digital Electronics
19
Signed Binary Numbers
Spring 2011
ECE 301 - Digital Electronics
20
Binary Arithmetic
of
Signed Binary Numbers
Spring 2011
ECE 301 - Digital Electronics
21
2's Complement Addition




Addition of n-bit signed binary numbers is
straightforward using the 2's Complement
number system.
Addition is carried out in the same way as for
n-bit positive numbers.
Carry from the sign bit (leftmost bit) is ignored.
Overflow occurs if the correct result (including
the sign bit) cannot be represented in n bits.
Spring 2011
ECE 301 - Digital Electronics
22
2's Complement Addition: Example
Using 2's Complement addition and 8-bit
representation, add the following numbers:
-47 + 83
Did overflow occur?
Spring 2011
ECE 301 - Digital Electronics
23
2's Complement Addition: Example
Using 2's Complement addition and 8-bit
representation, add the following numbers:
-32 + -105
Did overflow occur?
Spring 2011
ECE 301 - Digital Electronics
24
2's Complement Addition: Example
Using 2's Complement addition and 8-bit
representation, add the following numbers:
19 + 52
Did overflow occur?
Spring 2011
ECE 301 - Digital Electronics
25
2's Complement Addition: Example
Using 2's Complement addition and 8-bit
representation, add the following numbers:
64 + 78
Did overflow occur?
Spring 2011
ECE 301 - Digital Electronics
26
2's Complement Subtraction

Subtraction can be implemented using addition.
A – B = A + (-B)
Spring 2011

Determine the 2's Complement representation
for the negative number -B.

Use 2's Complement addition to add A and -B.
ECE 301 - Digital Electronics
27
2's Complement Subtraction: Example
Subtract the following numbers, using 2's
Complement addition and 8-bit representation:
64 – 78
Did overflow occur?
Spring 2011
ECE 301 - Digital Electronics
28
2's Complement Subtraction: Example
Subtract the following numbers, using 2's
Complement addition and 8-bit representation:
-35 – 62
Did overflow occur?
Spring 2011
ECE 301 - Digital Electronics
29
2's Complement Subtraction: Example
Subtract the following numbers, using 2's
Complement addition and 8-bit representation:
14 – (-59)
Did overflow occur?
Spring 2011
ECE 301 - Digital Electronics
30
2's Complement Subtraction: Example
Subtract the following numbers, using binary
subtraction and 8-bit representation:
27 – 45
Can this subtraction be carried out?
Spring 2011
ECE 301 - Digital Electronics
31
1's Complement Addition


Similar to 2's Complement Addition of n-bit
signed binary numbers.
However, rather than ignore the carry-out from
the sign (leftmost) bit, add it to the least
significant bit (LSB) of the n-bit sum.

Spring 2011
Known as the end-around carry.
ECE 301 - Digital Electronics
32
1's Complement Addition: Example
Using 1's Complement addition and 8-bit
representation, add the following numbers:
-31 + -84
Did overflow occur?
Spring 2011
ECE 301 - Digital Electronics
33
1's Complement Addition: Example
Using 1's Complement addition and 8-bit
representation, add the following numbers:
52 + 73
Did overflow occur?
Spring 2011
ECE 301 - Digital Electronics
34
Overflow

The general rule for detecting overflow when
performing 2's Complement or 1's Complement
Addition:
Spring 2011

An overflow occurs when the addition of two
positive numbers results in a negative number.

An overflow occurs when the addition of two
negative numbers results in a positive number.

Overflow cannot occur when adding a positive
number to a negative number.
ECE 301 - Digital Electronics
35
Binary Codes
Spring 2011
ECE 301 - Digital Electronics
36
Binary Codes


Weighted Codes

Each position in the code has a specific weight

Decimal value of code can be determined
Unweighted Codes
Spring 2011

Positions of code do not have a specific weight

Decimal value assigned to each code
ECE 301 - Digital Electronics
37
Binary Codes

n-bit Weighted Codes

Code:
an-1an-2an-3...a1a0

Weights:
wn-1, wn-2, wn-3, ..., w1, w0

Decimal Value: an-1 x wn-1 + an-2 x wn-2 + …
+ a1 x w1 + a0 x w0

4-bit Weighted Code

Spring 2011
Code:
a 3a 2a 1a 0
ECE 301 - Digital Electronics
38
Binary Codes

Examples of 4-bit weighted codes

8-4-2-1



6-3-1-1


4 bits → 16 code words
Excess-3 (obtained from 8-4-2-1)

Spring 2011
4 bits → 16 code words
Only 10 code words required to represent
decimal digits
4 bits → 16 code words
ECE 301 - Digital Electronics
39
Binary Codes

Examples of unweighted codes

2-out-of-5 Code



Gray Code


Spring 2011
Exactly 2 of the 5 bits are “1” for a valid code word.
10 valid code words.
Code values for successive decimal digits differ in
exactly one bit.
4 bits → 16 code words.
ECE 301 - Digital Electronics
40
Binary Codes
Decimal
Digit
0
Spring 2011
8-4-2-1
6-3-1-1
Code
Code
(BCD)
0000
0000
Excess-3 2-out-of-5
Code
Code
Gray
Code
0011
00011
0000
1
0001
0001
0100
00101
0001
2
0010
0011
0101
00110
0011
3
0011
0100
0110
01001
0010
4
0100
0101
0111
01010
0110
5
0101
0111
1000
01100
1110
6
0110
1000
1001
10001
1010
7
0111
1001
1010
10010
1011
8
1000
1011
1011
10100
1001
9
1001
1100
1100
11000
1000
ECE 301 - Digital Electronics
41
Binary Coded Decimal (BCD)



4-bit binary number used to represent each
decimal digit.
Weighted code: 8-4-2-1
Binary values 0000 … 1001 used to represent
decimal values 0 … 9.

Binary values 1010 … 1111 not used.

Very different from binary representation.
Spring 2011
ECE 301 - Digital Electronics
42
Binary Coded Decimal

In BCD, each decimal digit is replaced by its
binary equivalent value.

Example:

Binary:
Spring 2011
937.2510 = 1110101001.012
ECE 301 - Digital Electronics
43
ASCII



American Standard Code for Information Interchange
Common code for the storage and transfer of
alphanumeric characters.
7-bit Weighted Code



Can represent 128 characters
Used to represent letters, numbers, and other
characters
Any word or number can be represented using its
ASCII code.
Spring 2011
ECE 301 - Digital Electronics
44
ASCII Code (incomplete)
Spring 2011
ECE 301 - Digital Electronics
45
Questions?
Spring 2011
ECE 301 - Digital Electronics
46