UCCD1133
Introduction to Computer Organisation and Architecture
Chapter 2
Number Systems and Data Representation
Disclaimer
• This slide may contain copyrighted material of which has not been specifically authorized by the copyright owner. The use of copyrighted materials are solely for educational purpose. If you wish to use this copyrighted material for other purposes, you must first obtain permission from the original copyright owner.
2
Chapter 2-1
Number systems
3
Outline
• Count in binary, octal and hexadecimal number systems. • Understand the weighting structure of numbers.
• Perform base conversion of various number systems.
• Carry out arithmetic operations with binary numbers.
4
Number System
❑ Digital systems process data in binary format. Need to represent information in binary
For manipulation in electronic hardware
❑ A number system consists of an ordered set of symbols called digits. Total number of digits = base (radix, R) of a number system
The range of numbers is 0 to (R – 1).
The number can have 2 parts:
– Integer
– Fractional
– Separated by a radix point (.)
– E.g. (an-1 an-2 … a1 a0 . a-1 a-2 … a-m)R
• Commonly used number systems in digital electronics field 5
of study
• Decimalnumbersystem:
• Digits{0,1,2,3,4,5,6,7,8,9}
• R=10.
• Binarynumbersystem:
• Digits{0,1}
• R=2.
• Hexadecimalnumbersystem:
• Digits {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F}
• R=16.
• Octalnumbersystem:
• Digits {0, 1, 2, 3, 4, 5, 6, 7} • R=8.
5
Decimal
0
1
2
3
4
6
7
8
9
10
11
12
13
14
15
16
Binary
1000
1001
1010
1011
1100
1101
1110
1111
10000
0
1
10
11
100
101
110
111
Octal
0
1
2
3
4
5
6
7
10
11
12
13
14
15
16
17
20
Hexadecimal
0
1
2
3
4
5
6
7
8
9
a
b
c
d
e
10
f
Counting in Binary
• How to count in binary?
0
First column is full
1
Reset first column and add 1 to second column
10
First two columns are full
11
Reset and add 1 to third column
100
101
110
111
First three columns are full
1000
Reset and add 1 to fourth column
1001
• With N bits, can count up to (2N – 1) for a total of 2N different numbers
6
Weighting Structure of Numbers
• A positive number, N written in positional notation N = (an-1 an-2 … a1 a0 . a-1 a-2 … a-m)R
= an-1 Rn-1 + an-2 Rn-2 + … + a1 R1 + a0 R0 + a-1 R-1 + a-2 R-2 + … + a-m R-m Where
.
= radix point. E.g. binary point, hex point, decimal point. = radix or base – any positive integer where R > 1
= number of integer digits (left of radix pt)
= number of fractional digits (right of radix pt)
R
n
m
an-1= most significant digit (MSD) a-m = least significant digit (LSD)
• Each digit’s position is multiplied by a weighting factor (an integral power of R depending on the position)
• Example, N = 251.4110.
= (2 x 102) + (5 x 101) + (1 x 100) + (4 x 10-1) + (1 x 10-2)
10n-1
…..
102
101
100
.
10-1
10-2
…..
10-n
2
5
1
.
4
1
7
Weighting Structure of Numbers
• Example, binary weight structure 2n-1 … 22 21 20 .2-1 2-2 … 2-n
Positive Powers of 2 (Integer Number)
Negative Powers of 2 (Fractional number)
27
26
25
24
23
22
21
20
2-1
2-2
2-3
2-4
2-5
2-6
128
64
32
16
8
4
2
1
1/2
1/4
1/8
1/16
1/32
1/64
• Right-most bit is the LSB (Least Significant Bit). • Left-most bit is the MSB (Most Significant Bit).
8
Base Conversion:
Convert Base N to Decimal (Base 10)
• Example 1
Convert 1010.1012 to ?10.
Solution 1
1010.1012 = (1 X 23) + (0 X 22) + (1 X 21) + (0 X 20) + (1 X 2-1) + (0 X 2-2) + (1 X 2-3)
= 810 + 0 + 210 + 0 + 0.510 + 0 + 0.12510 = 10.62510
• Example 2
Convert 6278 to ?10.
Solution 2
6278 = (6 X 82) + (2 X 81) + (7 X 80)
= 38410 + 1610 + 710 = 40710
9
1 –
1 = 0 (conversion completed)
49 / 2 24 / 2 12 / 2 6 /2 3 /2 1 /2
= 24 = 12 =6 =3 =1 =0
Base Conversion:
Convert Integer Decimal (Base 10) to Base N
• Example 1: Method 1
Convert 4910 to a binary number.
Solution 1 49 – 32 = 17 17 – 16 = 1
❑ Example 2: Method 2 – Divide-by- radix
Convert 4910 Solution 2
to a binary number.
remainder 1 (LSB) remainder 0 remainder 0 remainder 0 remainder 1 remainder 1 (MSB)
64
32
16
8
4
2
1
1
1
0
0
0
1
Therefore, 4910 = 1100012
Therefore, 4910 = 1100012
10
Base Conversion: Convert Base N to Base M
• Requires an intermediate conversion step • First convert base N to base 10
• Then base 10 to base M.
• Example 1: Convert 189 to ?11.
Solution 1
Convert 189 to base 10:
189 = (1 X 91) + (8 X 90)
=9+8
= 1710
Convert from base 10 to base 11 using the divide-by-radix method: 17 / 11 = 1 remainder 6
1 / 11 = 0 remainder 1
Therefore, 189 = 1611
13
Base Conversion:
Convert Base N to Base M When M = NK
• Example 1:
Convert 1011011 2 to base 8.
Solution 1
Since 8 = 23, we can group three binary digits for each octal digit. Therefore, 1_011_0112 = 1338
• Example 2
Convert AF16 to base 8.
Solution 2
Since 16 is not a power of base 8. But both bases are a power of 2. Therefore, we can convert AF16 to base 2 and then convert to base 8.
Firstly, each hex digit is replaced by 4 bin digits. AF16 = 1010_11112
Then convert the bin number to base 8. 10_101_1112 = 2578
Therefore, AF16 = 2578.
14
Binary Arithmetic
• 4 basic types of binary arithmetic: • Binary addition
• Binary subtraction
• Binary multiplication
• Binary division
15
Binary Addition
• Example 1
Add 11110 and 1100.
Solution 1
11110 Augend
❑ How does the above information relate to circuit?
Understand the process of binary addition leads to constructing an adder circuit for each bit
Then combine the adders to compute two n-bit numbers
Need to capture the info into an intermediate form first e.g. truth table before proceed to adder circuit design.
11 100 0 +01100 Addend
Carries 01010 Sum
Inputs
Outputs
Carry-in
A
B
Carry-out
Sum
0
0
0
0
0
0
0
1
0
1
0
1
0
0
1
0
1
1
1
0
1
0
0
0
1
1
0
1
1
0
1
1
0
1
0
1
1
1
1
1
• When two n-bit numbers are added, the result is a (n+1)-bit number
16
Chapter 2-2
Computer codes
17
Outline
• Understand the concept of computer codes.
• Recognise the commonly used digital codes such as ASCII, Binary
Coded Decimal (BCD) and Gray code.
• Express decimal numbers in BCD form.
• Convert between the binary system and the Gray code.
18
Computer Codes
❑ A code is the use of a number system for representing information
❑ Binary system is widely used as codes to represent numbers, text, pictures, etc.
Since computers process all info in binary – the most efficient electronic form.
❑ Several types of well-known codes.
Codes to represent numeric.
Codes to represent character.
Codes for detecting and correcting errors. Codes for serial data transmission and storage.
19
Binary Coded Decimal (BCD)
❑ BCD code is used to represent the decimal digits 0 – 9.
Always 4 bits.
BCD is a type of weighted code
– Each bit position is weighted with 8, 4, 2, 1 from MSB to LSB
– Hence, also called 8-4-2-1 code
❑ Note that 1010, 1011, 1100, 1101, 1110 and 1111 are not used.
They are invalid in 8421 BCD code.
❑ Example of applications:
Used to encode numbers for output to numerical
displays
Used in processors that performs decimal arithmetic.
❑ BCD system is not binary system. They are not the same.
< BCD to 7 segment display
Decimal Digit
BCD code (8-4-2-1 Code)
0
00 00
1
00 01
2
00 10
3
00 1 1
4
01 00
5
01 01
6
01 10
7
01 1 1
8
10 00
9
10 01
20
Binary Coded Decimal (BCD)
❑ Example 1:
Encode the decimal number N = 975010 in BCD.
Solution 1 9 -> 1001 7 -> 0111 5 -> 0101 0 -> 0000
Then the individual codes are concatenated to give 975010 = 1001011101010000BCD
In binary system, 975010 => 100110000101102
21
Gray Code
❑ Gray code is unweighted
Cannot be used for arithmetic operations Commonly used in data transfer applications Gray code can be any length
Example, a 4- bit Gray code
❑ Gray code important feature:
Its natural sequence exhibits a single bit
change between successive code words.
❑ Useful for reducing error rate in data transfer applications
Lesser bit change while data is being transferring – chances of wrong bit transfer to the other side is lesser.
Gray code G[3:0]
Binary B[3:0]
Decimal Value
0000
0000
0
0001
0001
1
0011
0010
2
0010
0011
3
0110
0100
4
0111
0101
5
0101
0110
6
0100
0111
7
1100
1000
8
1101
1001
9
1111
1010
10
1110
1011
11
1010
1100
12
1011
1101
13
1001
1110
14
1000
1111
15
22
How to Generate Gray Code
How to ensure only one bit changes between two adjacent numbers?
1
0 1
000 0000
001 0001
011 0011 010 0010
110 0110
111 0111
101 0101 100 0100
100 1100
101 1101
111 1111 110 1110
010 1010
011 1011
001 1001 000 1000
45
00 000 01 001 11 011 10 010 10 110 11 111 01 101 00 100
23
0 00 1 01 1 11 0 10
From 2 rows to 4 rows
1. Write the first 2 rows
2. Flip 2 rows vertically
3. Set the 2nd bit of the two new rows to 1
From 4 rows to 8 rows
4. Generate the new 4 rows by flipping
the first 4 rows vertically
5. Set the 3rd bit of the new four rows to 1
Repeat the same procedure for the remaining rows 23
Gray Converters: Binary-to-Gray Converter
• In terms of algorithm:
• The MSB in the Gray code is the same as the MSB in the binary code.
• From left to right, add each adjacent pair of binary code bits to get the next Gray code bit. Discard carries.
• E.g.
MSB LSB
B[3] B[2] B[1] B[0] Binary 0+1+1+0
0101
G[3] G[2] G[1] G[0] Gray
24
Gray Converters: Gray-to-Binary Converter
• In terms of algorithm:
• The MSB in the binary code is the same as the MSB in the Gray code.
• Add each binary code bit generated to the Gray code bit in the next adjacent position. Discard carries.
• E.g.
MSB LSB
G[3] G[2] G[1] G[0] Gray 1011
+++ 1101
B[3] B[2] B[1] B[0] Binary
25
ASCII (American Standard Code for Information Interchange)
• ASCII is a set of binary codes
• Used to represent the alphanumeric symbols.
• Widely used in data communication.
❑ An extra bit (parity bit) is attached to an ASCII code during transmission for error detection purpose
26
ASCII (American Standard Code for Information Interchange)
• Example 1:
ASCII code representation of the word “Digital” is shown
Character
Binary Code
Hexadecimal Code
D
1000100
44
i
1101001
69
g
1100111
67
i
1101001
69
t
1110100
74
a
1100001
61
l
1101100
6C
27
Chapter 2-3
Signed and unsigned numbers
28
Outline
• Represent signed binary numbers in sign-magnitude and 2’s complement format.
29
Unsigned versus Signed Number Representation
❑ So far, we have considered only unsigned binary numbers that represent positive range of numbers.
❑ Sometimes programmers want to deal with both negative and positive range of numbers, which requiring a different binary number system.
❑ Signed binary numbers can be represented using: Sign-magnitude number system.
Two’s complement number system.
❑ You will probably deal with the terms:
• zero extension (for unsigned numbers) • sign extension (for signed numbers)
30
Sign-Magnitude Binary Number System
❑ A number, N is written as:
N = (s an-1 an-2 … a1 a0 . a-1 a-2 … a-m)rsm where s => sign-bit;
a => magnitude
– s = 0: N is positive.
– s = 1: N is negative.
❑ N-bit number correspond to decimal range:
-(2n-1 – 1) to +(2n-1 – 1).
❑ Example
Determine the binary sign-magnitude code for
N = -13, expressed as a 5-bit binary number. Solution:
N= -13
= -11012
= 111012sm
2 possible representations of zero
– can complicate testing for zero – problems for programmers.
Decimal Number System
Sign-Magnitude Number System (4-bit system)
+7
0111
+6
0110
+5
0101
+4
0100
+3
0011
+2
0010
+1
0001
+0
0000
-0
1000
-1
1001
-2
1010
-3
1011
-4
1100
-5
1101
-6
1110
-7
1111
-8
–
To represent negative sign
Sign-magnitude code to represent -13
31
Sign-Magnitude Binary Number System
❑ The implementation of the method is costly in terms of: Circuitry (large arithmetic circuit)
Computation time (takes more time to produce the result).
❑ It is slightly odd to have both +0 and -0 exist.
❑ Ordinary binary addition does not work. For example, -510 + 510 gives
11012 + 01012 = 100102, which is nonsense.
❑ Not popular in practice for representing signed numbers.
32
2’s Complement Number System (2cns)
❑ 2cns consists of: Positive range
– 0N(2n-1 -1)
– Same as sign-magnitude
number system Negative range
– -1N(-2n-1)
– using complement of the
negative numbers
E.g. an 8-bit digital system can only operate on values between – 128 to 127.
❑ Why use 2cns?
Like binary system, natural numbering system for digital circuits.
The codes are arranged in such a way that is easy to build hardware to perform signed arithmetic operations (through complement arithmetic method).
The MSB is sign bit.
0 => pos numbers.
1 => neg numbers. For negative numbers, the rest of the bits DO NOT represent magnitude
E.g. does not represent -6
Decimal Number System
Sign- Magnitude Number System
2’s Complement Number System
+7
0111
0111
+6
0110
0110
+5
0101
0101
+4
0100
0100
+3
0011
0011
+2
0010
0010
+1
0001
0001
+0
0000
0000
-0
1000
–
-1
1001
1111
-2
1010
1110
-3
1011
1101
-4
1100
1100
-5
1101
1011
-6
1110
1010
-7
1111
1001
-8
–
1000
33
Method to Obtain 2’s Complement Representation
❑ Algorithm to obtain the 2’s complement of N:
1. Find the binary equivalent of N.
2. Complement each bit (that is, invert 0’s to 1’s and 1’s to 0’s).
3. Add 1.
❑ Example 1
Find the 2’s complement of -210 as a 4-bit two’s complement number.
Solution
1. +210 is 00102.
2. Inverting 00102 produces 11012.
3. 11012 + 1 = 11102c.
So -210 is 11102c.
❑ Example 2
Find the 2’s complement of N =
-1102 if a 5-bit number is used.
Solution
N2 0 0 1 1 02 11001 +1
[N]2 110102c
Invert (1’s complement) Add 1
(2’s complement)
34
2’s Complement Representation
❑ Example 3
Given an 8-bit digital system, find the decimal number value of N = 1111 10102c. Also find the equivalent sign-magnitude representation.
❑ Solution
First, check if the number is negative or positive by looking at the sign bit. If it is positive, simply convert it to decimal. If it is negative, inverts the bits and add a 1.
From the MSB (sign bit), N is a negative number.
[1111_1010]2c
= 0000_01012 + 1 = 0000_01102
1 1 1 1 1 0 1 02c 00000101 +1
0 0 0 0 0 1 1 02
Invert
Add 1
1111_10102c represents -0000_01102 or -6.
The equivalent sign-mag representation of -6 = 1000_01102sm.
35
Example
• Example 4
Convert the following numbers to the required number system. Show your steps to obtain the
answers.
(i) Convert DA16 to binary, then to decimal
(ii) Find the 2’s complement for -0101 11012 (answer in 8-bit). (iii) Find the BCD equivalence for 8510
(iv) Convert 0110 1100Gray to binary (answer in 8-bit).
(v) Convert 1110 01002 to Gray code (answer in 8-bit).
Solution (i) DA16
(iv) 0110 1100Gray
(v) 1110 01002
= 1101 10102
= (27 + 26 +24 +23 +21)10 = 21810
= 0100 10002 = 1001 0110Gray
(ii) 0101 11012
1’s complement = 1010 0010 2’s complement = 1010 0011
(iii) 8510 = 1000 0101BCD
38
Floating point number systems*
• Floating-point number system allows the representation of very large and very small numbers with a sign, mantissa (M), base (B), and exponent (E).
± MBE ❑ Example: 4000 = 4103
• A single precision floating point value is represented by 32 bits: 1 sign bit, 8 exponent bits , and 23 mantissa bits.
• Example:
Floating-point representation of decimal number 228.
• Solution:
• Convert decimal to binary.
22810 = 111001002 = 1.11001227 Answer:
In reality, floating point representation follows the following form:
IEEE 754 floating-point standard
39