Number Systems & Codes

CPE 202
Lecture 2: Number Systems & Codes
Part I: Number Systems
 Information Representations
 Positional Notations
 Decimal (base 10) Number System
 Other Number Systems &
Base-R to Decimal Conversion
 Decimal-to-Binary Conversion
 Sum-of-Weights Method
 Repeated Division-by-2 Method (for whole numbers)
 Repeated Multiplication-by-2 Method (for fractions)

CPE 202
Lecture 2: Number Systems & Codes
 Conversion between Decimal and other Bases
 Conversion between Bases
 Binary-Octal/Hexadecimal Conversion
 Binary Arithmetic Operations
 Negative Numbers Representation
 Sign-and-magnitude
 1s Complement
 2s Complement
 Comparison of Sign-and-Magnitude and Complements

CPE 202
Lecture 2: Number Systems & Codes
 Complements
 Diminished-Radix Complements
 Radix Complements
 2s Complement Addition and Subtraction
 1s Complement Addition and Subtraction
 Overflow
 Fixed-Point Numbers
 Floating-Point Numbers
 Excess Representation
 Arithmetics with Floating-Point Numbers

CPE 202
Information Representation (1/4)
 Numbers are important to computers
 represent information precisely
 can be processed

 For example:
 to represent yes or no: use 0 for no and 1 for yes
 to represent 4 seasons: 0 (autumn), 1 (winter), 2(spring) and 3
(summer)
 NRIC number: a letter, 7 digits, and a check code
 matriculation number (8 alphanumeric) to represent individual
students

CPE 202
Information Representation (2/4)
 Elementary storage units inside computer are electronic
switches. Each switch holds one of two states: on (1) or off
(0).

ON OFF

 We use a bit (binary digit), 0 or 1, to represent the state.

CPE 202
Information Representation (3/4)
 Storage units can be grouped together to cater to larger range
of numbers. Example: 2 switches to represent 4 values.

0 (00)
1 (01)
2 (10)
3 (11)

CPE 202
Information Representation (4/4)
 In general, N bits can represent 2N different values.
 For M values, log 2 M  bits are needed.
1 bit  represents up to 2 values (0 or 1)
2 bits  rep. up to 4 values (00, 01, 10 or 11)
3 bits  rep. up to 8 values (000, 001, 010. …, 110, 111)
4 bits  rep. up to 16 values (0000, 0001, 0010, …, 1111)
32 values  requires 5 bits
64 values  requires 6 bits
1024 values  requires 10 bits
40 values  requires 6 bits
100 values  requires 7 bits

CPE 202
Positional Notations (1/3)
 Position-independent notation
 each symbol denotes a value independent of its position: Egyptian
number system

 Relative-position notation
 Roman numerals symbols with different values: I (1), V (5), X (10),
C (50), M (100)
 Examples: I, II, III, IV, VI, VI, VII, VIII, IX
 Relative position important: IV = 4 but VI = 6

 Computations are difficult with the above two notations

CPE 202
Positional Notations (2/3)
 Weighted-positional notation
 Decimal number system, symbols = { 0, 1, 2, 3, …, 9 }
 Position is important
 Example:(7594)10 = (7x103) + (5x102) + (9x101) + (4x100)
 The value of each symbol is dependent on its type and its position in
the number
 In general,
(anan-1… a0)10 = (an x 10n) + (an-1 x 10n-1) + … + (a0 x 100)

CPE 202
Positional Notations (3/3)
 Fractions are written in decimal numbers after the decimal
point.
 2 3 4 = (2.75)10 = (2 x 100) + (7 x 10-1) + (5 x 10-2)

 In general,
(anan-1… a0 . f1f2 … fm)10 =
(an x 10n) + (an-1x10n-1) + … + (a0 x 100) +
(f1 x 10-1) + (f2 x 10-2) + … + (fm x 10-m)
 The radix (or base) of the number system is the total number
of digits allowed in the system.

CPE 202
Decimal (base 10) Number System

 Weighing factors (or weights) are in powers-of-10:

… 103 102 101 100.10-1 10-2 10-3 10-4 …
 To evaluate the decimal number 593.68, the digit in each
position is multiplied by the corresponding weight:
5102 + 9101 + 3100 + 610-1 + 810-2 =
(593.68)10

CPE 202
Other Number Systems &
Base-R to Decimal Conversion (1/3)
 Binary (base 2): weighs in powers-of-2.
– Binary digits (bits): 0,1.

 Octal (base 8): weighs in powers-of-8.

– Octal digits: 0,1,2,3,4,5,6,7.

 Hexadecimal (base 16): weighs in powers-of-16.

– Hexadecimal digits: 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F.

 Base R: weighs in powers-of-R.

CPE 202
Other Number Systems &
Base-R to Decimal Conversion (2/3)
 (1101.101)2 = 123 + 122 + 120 + 12-1 + 12-3
= 8 + 4 + 1 + 0.5 + 0.125 = (13.625)10
 (572.6)8 = 582 + 781 + 280 + 68-1
= 320 + 56 + 2 + 0.75 = (378.75)10
 (2A.8)16 = 2161 + 10160 + 816-1
= 32 + 10 + 0.5 = (42.5)10
 (341.24)5 = 352 + 451 + 150 + 25-1 + 45-2
= 75 + 20 + 1 + 0.4 + 0.16 = (96.56)10

CPE 202
Other Number Systems &
Base-R to Decimal Conversion (3/3)
 Counting in Binary
Decimal Binary
 Assuming non-negative values, n Number Number
bits  largest value 2n – 1. 0
1
0
0
0
0
0
0
0
1
Examples: 4 bits  0 to 15; 2
3
0
0
0
0
1
1
0
1

6 bits  0 to 63. 4
5
0
0
1
1
0
0
0
1
 range of m values  log2m bits 6
7
0
0
1
1
1
1
0
1
8 1 0 0 0
9 1 0 0 1
10 1 0 1 0
11 1 0 1 1
12 1 1 0 0
13 1 1 0 1
14 1 1 1 0
15 1 1 1 1

CPE 202
Decimal-to-Binary Conversion
 Method 1: Sum-of-Weights Method
 Method 2:
 Repeated Division-by-2 Method (for whole numbers)
 Repeated Multiplication-by-2 Method (for fractions)

CPE 202
Sum-of-Weights Method
 Determine the set of binary weights whose sum is equal to
the decimal number.

(9)10 = 8 + 1 = 23 + 20 = (1001)2
(18)10 = 16 + 2 = 24 + 21 = (10010)2
(58)10 = 32 + 16 + 8 + 2 = 25 + 24 + 23 + 21 = (111010)2
(0.625)10 = 0.5 + 0.125 = 2-1 + 2-3 = (0.101)2

CPE 202
Repeated Division-by-2 Method
 To convert a whole number to binary, use successive
division by 2 until the quotient is 0. The remainders form
the answer, with the first remainder as the least significant
bit (LSB) and the last as the most significant bit (MSB).
(43)10 = (101011)2
2 43
2 21 rem 1  LSB
2 10 rem 1
2 5 rem 0
2 2 rem 1
2 1 rem 0
0 rem 1  MSB

CPE 202
Repeated Multiplication-by-2 Method
 To convert decimal fractions to binary, repeated
multiplication by 2 is used, until the fractional product is 0
(or until the desired number of decimal places). The
carried digits, or carries, produce the answer, with the first
carry as the MSB, and the last as the LSB.
(0.3125)10 = (.0101)2
Carry
0.31252=0.625 0 MSB
0.6252=1.25 1
0.252=0.50 0
0.52=1.00 1 LSB

CPE 202
Conversion between Decimal and
other Bases
 Base-R to decimal: multiply digits with their corresponding
weights.
 Decimal to binary (base 2)
 whole numbers: repeated division-by-2
 fractions: repeated multiplication-by-2

 Decimal to base-R
 whole numbers: repeated division-by-R
 fractions: repeated multiplication-by-R

CPE 202
Conversion between Bases
 In general, conversion between bases can be done via
decimal:
Base-2 Base-2
Base-3 Base-3
Base-4 Decimal Base-4
… ….
Base-R Base-R

 Shortcuts for conversion between bases 2, 4, 8, 16.

CPE 202
Binary-Octal/Hexadecimal
Conversion
 Binary  Octal: Partition in groups of 3
(10 111 011 001 . 101 110)2 = (2731.56)8

 Octal  Binary: reverse

(2731.56)8 = (10 111 011 001 . 101 110)2

 Binary  Hexadecimal: Partition in groups of 4

(101 1101 1001 . 1011 1000)2 = (5D9.B8)16

 Hexadecimal  Binary: reverse

(5D9.B8)16 = (101 1101 1001 . 1011 1000)2

CPE 202
Binary Arithmetic Operations (1/6)
 ADDITION
 Like decimal numbers, two numbers can be added by adding
each pair of digits together with carry propagation.

(11011)2 (647)10
+ (10011)2 + (537)10
(101110)2 (1184)10

CPE 202
Binary Arithmetic Operations (2/6)

 Digit addition table:

(11011)2
BINARY DECIMAL
+ (10011)2
0+0+0=00 0+0+0=00
(101110)2
0+1+0=01 0+1+0=01
1+0+0=01 0+2+0=02
1+1+0=10 …
1 0 0 1 1 0
0+0+1=01 1+8+0=09 0 1 1 0 1 1
0+1+1=10 1+9+0=10 0 1 0 0 1 1
1+0+1=10 … 1 0 1 1 1 0
1+1+1=11 9+9+1=19 0 1 0 0 1 1

Carry in
Carry out

CPE 202
Binary Arithmetic Operations (3/6)
 SUBTRACTION
 Two numbers can be subtracted by subtracting each pair of
digits together with borrowing, where needed.

(11001)2 (627)10
- (10011)2 - (537)10
(00110)2 (090)10

CPE 202
Binary Arithmetic Operations (4/6)
 Digit subtraction table:
(11001)2
BINARY DECIMAL - (10011)2
0-0-0=00 0-0-0=00 (00110)2
0-1-0=11 0-1-0=19
1-0-0=01 0-2-0=18
1-1-0=00 … 0 0 1 1 0 0
0-0-1=11 0-9-1=10 0 1 1 0 0 1
0-1-1=10 1-0-1=00 0 1 0 0 1 1
1-0-1=00 … 0 0 0 1 1 0
1-1-1=11 9-9-1=19 0 0 0 1 1 0

Borrow

CPE 202
Binary Arithmetic Operations (5/6)
 MULTIPLICATION
 To multiply two numbers, take each digit of the multiplier
and multiply it with the multiplicand. This produces a
number of partial products which are then added.

(11001)2 (214)10 Multiplicand

x (10101)2 x (152)10 Multiplier
(11001)2 (428)10
(11001)2 (1070)10 Partial
+(11001)2 +(214)10 products
(1000001101)2 (32528)10 Result

CPE 202
Binary Arithmetic Operations (6/6)
 Digit multiplication table:
BINARY DECIMAL
0X0=0 0 X 0= 0
0 X 1= 0 0 X 1= 0
1X0=0 …
1 X 1= 1 1X8=8
1 X 9= 9
…
9 X 8 = 72
9 X 9 = 81

 DIVISION – can you figure out how this is done?

 Exercise: Think of the division technique (shift & subtract)
used for decimal numbers and apply it to binary numbers.

CPE 202
Negative Numbers Representation
 Unsigned numbers: only non-negative values.
 Signed numbers: include all values (positive and negative).
 Till now, we have only considered how unsigned (non-
negative) numbers can be represented. There are three
common ways of representing signed numbers (positive and
negative numbers) for binary numbers:
 Sign-and-Magnitude
 1s Complement
 2s Complement

CPE 202
Negative Numbers:
Sign-and-Magnitude (1/4)
 Negative numbers are usually written by writing a
minus sign in front.
 Example:
- (12)10 , - (1100)2
 In sign-and-magnitude representation, this sign is
usually represented by a bit:
0 for +
1 for -

CPE 202
Negative Numbers:
Sign-and-Magnitude (2/4)
 Example: an 8-bit number can have 1-bit sign and 7-bit
magnitude.

sign magnitude

CPE 202
Negative Numbers:
Sign-and-Magnitude (3/4)
 Largest Positive Number: 0 1111111 +(127)10
 Largest Negative Number: 1 1111111 -(127)10
 Zeroes: 0 0000000 +(0)10
1 0000000 -(0)10
 Range: -(127)10 to +(127)10
 Question: For an n-bit sign-and-magnitude representation,
what is the range of values that can be represented?

CPE 202
Negative Numbers:
Sign-and-Magnitude (4/4)

 To negate a number, just invert the sign bit.

 Examples:
- (0 0100001)sm = (1 0100001)sm
- (1 0000101)sm = (0 0000101)sm

CPE 202
1s and 2s Complement
 Two other ways of representing signed numbers
for binary numbers are:
 1s-complement
 2s-complement

 They are preferred over the simple sign-and-

magnitude representation.

CPE 202
1s Complement (1/3)
 Given a number x which can be expressed as an n-bit binary
number, its negative value can be obtained in 1s-complement
representation using:
- x = 2n - x - 1

Example: With an 8-bit number 00001100, its negative

value, expressed in 1s complement, is obtained as follows:
-(00001100)2 = - (12)10
= (28 - 12 - 1)10
= (243)10
= (11110011)1s

CPE 202
1s Complement (2/3)
 Essential technique: invert all the bits.
Examples: 1s complement of (00000001)1s = (11111110)1s
1s complement of (01111111)1s = (10000000)1s
 Largest Positive Number: 0 1111111 +(127) 10
 Largest Negative Number: 1 0000000 -(127)10
 Zeroes: 0 0000000
1 1111111
 Range: -(127)10 to +(127)10
 The most significant bit still represents the sign:
0 = +ve; 1 = -ve.

CPE 202
1s Complement (3/3)
 Examples (assuming 8-bit binary numbers):
(14)10 = (00001110)2 = (00001110)1s
-(14)10 = -(00001110)2 = (11110001)1s
-(80)10 = -( ? )2 = ( ? )1s

CPE 202
2s Complement (1/4)
 Given a number x, which can be expressed as an n-bit binary
number, its negative number can be obtained in 2s-
complement representation using:
- x = 2n - x
Example: With an 8-bit number 00001100, its negative value
in 2s complement is thus:
-(00001100)2 = - (12)10
= (28 - 12)10
= (244)10
= (11110100)2s

CPE 202
2s Complement (2/4)
 Essential technique: invert all the bits and add 1.
Examples:
2s complement of
(00000001)2s = (11111110)1s (invert)
= (11111111)2s (add 1)
2s complement of
(01111110)2s = (10000001)1s (invert)
= (10000010)2s (add 1)

CPE 202
2s Complement (3/4)
 Largest Positive Number: 0 1111111 +(127)10
 Largest Negative Number: 1 0000000 -(128)10
 Zero: 0 0000000
 Range: -(128)10 to +(127)10
 The most significant bit still represents the sign:
0 = +ve; 1 = -ve.

CPE 202
2s Complement (4/4)
 Examples (assuming 8-bit binary numbers):
(14)10 = (00001110)2 = (00001110)2s
-(14)10 = -(00001110)2 = (11110010)2s
-(80)10 = -( ? )2 = ( ? )2s

CPE 202
Comparisons of Sign-and-Magnitude
and Complements (1/2)
 Example: 4-bit signed number (positive values)
Important slide!
Value Sign-and- 1s 2s Mark this!
Magnitude Comp. Comp.
+7 0111 0111 0111
+6 0110 0110 0110
+5 0101 0101 0101
+4 0100 0100 0100
+3 0011 0011 0011
+2 0010 0010 0010
+1 0001 0001 0001
+0 0000 0000 0000

CPE 202
Comparisons of Sign-and-Magnitude
and Complements (2/2)
 Example: 4-bit signed number (negative values)
Important slide!
Value Sign-and- 1s 2s Mark this!
Magnitude Comp. Comp.
-0 1000 1111 -
-1 1001 1110 1111
-2 1010 1101 1110
-3 1011 1100 1101
-4 1100 1011 1100
-5 1101 1010 1011
-6 1110 1001 1010
-7 1111 1000 1001
-8 - - 1000

CPE 202
Complements (General)
 Complement numbers can help perform subtraction. With
complements, subtraction can be performed by addition.
Hence, A – B can be performed by A + (-B) where (-B) is
represented as the complement of B.
 In general, for Base-r numbers, there are:
(i) Diminished Radix (or r-1’s) Complement
(ii) Radix (or r’s) Complement
 For Base-2 numbers, we have seen:
(i) 1s Complement
(ii) 2s Complement

CPE 202
Diminished-Radix Complements
 Given an n-digit number, xr, its (r-1)’s complement is:
(rn - 1) - x
E.g.: (r-1)’s complement, or 9s complement, of (22)10 is:
(102 - 1) - 22 = (77)9s [This means –(22)10 is (77)9s]
(r-1)’s complement, or 1s complement, of (0101)2 is:
(24- 1) - 0101 = (1010)1s [This means –(0101)2 is (1010)1s]
Same as inverting all digits:
(102 - 1) - 22 = 99 - 22 = (77)9s
(24 - 1) - 0101 = 1111 - 0101 = (1010)1s

CPE 202
Radix Complements
 Given an n-digit number, xr, its r’s-complement is:
rn - x
E.g.: r’s-complement, or 10s complement, of (22) 10 is:
102 - 22 = (78)10s [This means –(22)10 is (78)10s]
r’s-complement, or 2s complement, of (0101) 2 is:
24 - 0101 = (1011)2s [This means –(0101)2 is (1011)2s]
Same as inverting all digits and adding 1:
(102) - 22 = (99+1) - 22 = 77 + 1 = (78) 10s
(24) - 0101 = (1111+1) - 0101 = 1010 +1 = (1011)2s

CPE 202
2s Complement Addition/Subtraction
(1/3)
 Algorithm for addition, A + B:
1. Perform binary addition on the two numbers.
2. Ignore the carry out of the MSB (most significant bit).
3. Check for overflow: Overflow occurs if the ‘carry in’ and ‘carry out’
of the MSB are different, or if result is opposite sign of A and B.

 Algorithm for subtraction, A – B:

A – B = A + (–B)
1. Take 2s complement of B by inverting all the bits and adding 1.
2. Add the 2s complement of B to A.

CPE 202
2s Complement Addition/Subtraction
(2/3)
 Examples: 4-bit binary system

+3 0011 -2 1110
+ +4 + 0100 + -6 + 1010
---- ------- ---- -------
+7 0111 -8 11000
---- ------- ---- -------
+6 0110 +4 0100
+ -3 + 1101 + -7 + 1001
---- ------- ---- -------
+3 10011 -3 1101
---- ------- ---- -------
 Which of the above is/are overflow(s)?

CPE 202
2s Complement Addition/Subtraction
(3/3)
 More examples: 4-bit binary system

-3 1101 +5 0101
+ -6 + 1010 + +6 + 0110
---- ------- ---- -------
-9 10111 +11 1011
---- ------- ---- -------

 Which of the above is/are overflow(s)?

CPE 202
1s Complement Addition/Subtraction
(1/2)
 Algorithm for addition, A + B:
1. Perform binary addition on the two numbers.
2. If there is a carry out of the MSB, add 1 to the result.
3. Check for overflow: Overflow occurs if result is opposite sign of A
and B.

 Algorithm for subtraction, A – B:

A – B = A + (–B)
1. Take 1s complement of B by inverting all the bits.
2. Add the 1s complement of B to A.

CPE 202
1s Complement Addition/Subtraction
(2/2)
 Examples: 4-bit binary system
+3 0011 +5 0101
+ +4 + 0100 + -5 + 1010
---- ------- ---- -------
+7 0111 -0 1111
---- ------- ---- -------

-2 1101 -3 1100
+ -5 + 1010 + -7 + 1000
---- ------ ---- -------
-7 10111 -10 10100
---- + 1 ---- + 1
------ -------
1000 0101

CPE 202
Overflow (1/2)
 Signed binary numbers are of a fixed range.
 If the result of addition/subtraction goes beyond this range,
overflow occurs.
 Two conditions under which overflow can occur are:
(i) positive add positive gives negative
(ii) negative add negative gives positive

CPE 202
Overflow (2/2)
 Examples: 4-bit numbers (in 2s complement)
 Range : (1000)2s to (0111)2s or (-810 to 710)
(i) (0101)2s + (0110)2s= (1011)2s
(5)10 + (6)10= -(5)10 ?! (overflow!)

(ii) (1001)2s + (1101)2s = (10110)2s discard end-carry

= (0110)2s
(-7)10 + (-3)10 = (6)10 ?! (overflow!)

CPE 202
Fixed Point Numbers (1/2)
 The signed and unsigned numbers representation given are
fixed point numbers.
 The binary point is assumed to be at a fixed location, say, at
the end of the number:

binary point

 Can represent all integers between –128 to 127 (for 8 bits).

CPE 202
Fixed Point Numbers (2/2)
 In general, other locations for binary points possible.

integer part binary point fraction part

 Examples: If two fractional bits are used, we can represent:

(001010.11)2s = (10.75)10
(111110.11)2s = -(000001.01)2
= -(1.25)10

CPE 202
Floating Point Numbers (1/5)
 Fixed point numbers have limited range.
 To represent very large or very small numbers, we use
floating point numbers (cf. scientific numbers). Examples:
0.23 x 1023 (very large positive number)
0.5 x 10-32 (very small positive number)
-0.1239 x 10-18 (very small negative number)

CPE 202
Floating Point Numbers (2/5)
 Floating point numbers have three parts:
sign, mantissa, and exponent
 The base (radix) is assumed (usually base 2).
 The sign is a single bit (0 for positive number, 1 for negative).

sign mantissa exponent

CPE 202
Floating Point Numbers (3/5)
 Mantissa is usually in normalised form:
(base 10) 23 x 1021 normalised to 0.23 x 1023
(base 10) -0.0017 x 1021 normalised to -0.17 x 1019
(base 2) 0.01101 x 23 normalised to 0.1101 x 22
 Normalised form: The fraction portion cannot begin with
zero.
 More bits in exponent gives larger range.
 More bits for mantissa gives better precision.

CPE 202
Floating Point Numbers (4/5)
 Exponent is usually expressed in complement or excess form
(excess form to be discussed later).
 Example: Express -(6.5)10 in base-2 normalised form
-(6.5)10 = -(110.1)2 = -0.1101 x 23
 Assuming that the floating-point representation contains 1-bit
sign, 5-bit normalised mantissa, and 4-bit exponent.
 The above example will be represented as

1 11010 0011

CPE 202
Floating Point Numbers (5/5)
 Example: Express (0.1875)10 in base-2 normalised form
(0.1875)10 = (0.0011)2 = 0.11 x 2-2
 Assuming that the floating-pt rep. contains 1-bit sign, 5-bit
normalised mantissa, and 4-bit exponent.
 The above example will be represented as

0 11000 1101 If exponent is in 1’s complement.

0 11000 1110 If exponent is in 2’s complement.

0 11000 0110 If exponent is in excess-8.

CPE 202
Excess Representation (1/2)
 The excess representation
allows the range of values to be Excess-4
Value
Representation
distributed evenly among the
positive and negative value, by a 000 -4
simple translation 001 -3
(addition/subtraction). 010 -2
 Example: For a 3-bit 011 -1
representation, we may use 100 0
excess-4. 101 1
110 2

111 3

CPE 202
Excess Representation (2/2)
 Example: For a 4-bit representation, we may use excess-8.

Excess-8 Excess-8
Value Value
Representation Representation
0000 -8 1000 0
0001 -7 1001 1
0010 -6 1010 2
0011 -5 1011 3
0100 -4 1100 4
0101 -3 1101 5
0110 -2 1110 6
0111 -1 1111 7

CPE 202
Arithmetics with Floating Point
Numbers (1/2)
 Arithmetic is more difficult for floating point numbers.
 MULTIPLICATION
Steps: (i) multiply the mantissa
(ii) add-up the exponents
(iii) normalise
 Example:
(0.12 x 102)10 x (0.2 x 1030)10
= (0.12 x 0.2)10 x 102+30
= (0.024)10 x 1032 (normalise)
= (0.24 x 1031)10

CPE 202
Arithmetics with Floating Point
Numbers (2/2)
 ADDITION
Steps: (i) equalise the exponents
(ii) add-up the mantissa
(iii) normalise
 Example:
(0.12 x 103)10 + (0.2 x 102)10
= (0.12 x 103)10 + (0.02 x 103)10 (equalise exponents)
= (0.12 + 0.02)10 x 103 (add mantissa)
= (0.14 x 103)10
 Can you figure out how to perform SUBTRACTION and
DIVISION for (binary/decimal) floating-point numbers?

CPE 202
Number Systems & Codes
Part II: Codes
 Binary Coded Decimal (BCD)
 Gray Code
 Binary-to-Gray Conversion
 Gray-to-Binary Conversion

 Other Decimal Codes

 Self-Complementing Codes
 Alphanumeric Codes
 Error Detection Codes

CPE 202
Binary Coded Decimal (BCD) (1/3)
 Decimal numbers are more natural to humans. Binary
numbers are natural to computers. It is quite expensive to
convert between the two.
 If little calculation is involved, we can use some coding
schemes for decimal numbers.
 One such scheme is BCD, also known as the 8421 code.
 Represent each decimal digit as a 4-bit binary code.

CPE 202
Binary Coded Decimal (BCD) (2/3)
Decimal digit 0 1 2 3 4
BCD 0000 0001 0010 0011 0100
Decimal digit 5 6 7 8 9
BCD 0101 0110 0111 1000 1001

 Some codes are unused, eg: (1010)BCD, (1011) BCD, …,

(1111) BCD. These codes are considered as errors.
 Easy to convert, but arithmetic operations are more
complicated.
 Suitable for interfaces such as keypad inputs and digital
readouts.

CPE 202
Binary Coded Decimal (BCD) (3/3)
Decimal digit 0 1 2 3 4
BCD 0000 0001 0010 0011 0100
Decimal digit 5 6 7 8 9
BCD 0101 0110 0111 1000 1001

 Examples:
(234)10 = (0010 0011 0100)BCD
(7093)10 = (0111 0000 1001 0011)BCD
(1000 0110)BCD = (86)10
(1001 0100 0111 0010)BCD = (9472)10
Notes: BCD is not equivalent to binary.
Example:(234)10 = (11101010)2

CPE 202
The Gray Code (1/3)
 Unweighted (not an arithmetic code).
 Only a single bit change from one code number to the next.
 Good for error detection.

Decimal Binary Gray Code Decimal Binary Gray code

0 0000 0000 8 1000 1100
1 0001 0001 9 1001 1101
2 0010 0011 10 1010 1111
3 0011 0010 11 1011 1110
4 0100 0110 12 1100 1010
5 0101 0111 13 1101 1011
6 0110 0101 14 1110 1001
7 0111 0100 15 1111 1000

Q. How to generate 5-bit standard Gray code?

Q. How to generate n-bit standard Gray code?

CPE 202
The Gray Code (2/3)
0000 1100
0100
0001 0101
1101
0011
0001 0111
1111
0010
0000 0110
1110
0010
0110 0010
1010
0111
0011 0011
1011
0101
0001 0001
1001
0100
0000 0000
1000

Generating 4-bit standard Gray code.

CPE 202
The Gray Code (3/3)

sensors

mis-aligned mis-aligned
sensors sensors

Binary coded: 111  110  000 Gray coded: 111  101

CPE 202
Binary-to-Gray Code Conversion
 Retain the most significant bit.
 From left to right, add each adjacent pair of binary code bits
to get the next Gray code bit, discarding carries.
 Example: Convert binary number 10110 to Gray code.
1 0 1 1 0 Binary 1 + 0 1 1 0 Binary 1 0 + 1 1 0 Binary
  
1 Gray 1 1 Gray 1 1 1 Gray

1 0 1 + 1 0 Binary 1 0 1 1 + 0 Binary
 
1 1 1 0 Gray 1 1 1 0 1 Gray

(10110)2 = (11101)Gray

CPE 202
Gray-to-Binary Conversion
 Retain the most significant bit.
 From left to right, add each binary code bit generated to the
Gray code bit in the next position, discarding carries.
 Example: Convert Gray code 11011 to binary.

1 1 0 1 1 Gray 1 1 0 1 1 Gray 1 1 0 1 1 Gray

 +  + 
1 Binary 1 0 Binary 1 0 0 Binary

1 1 0 1 1 Gray 1 1 0 1 1 Gray
+  + 
1 0 0 1 Binary 1 0 0 1 0 Binary

(11011)Gray = (10010)2

CPE 202
Other Decimal Codes
Decimal Digit BCD Excess-3 84-2-1 2*421 Biquinary
8421 5043210
0 0000 0011 0000 0000 0100001
1 0001 0100 0111 0001 0100010
2 0010 0101 0110 0010 0100100
3 0011 0110 0101 0011 0101000
4 0100 0111 0100 0100 0110000
5 0101 1000 1011 1011 1000001
6 0110 1001 1010 1100 1000010
7 0111 1010 1001 1101 1000100
8 1000 1011 1000 1110 1001000
9 1001 1100 1111 1111 1010000

 Self-complementing codes: excess-3, 84-2-1, 2*421 codes.

 Error-detecting code: biquinary code (bi=two, quinary=five).

CPE 202
Self-Complementing Codes
 Examples: excess-3, 84-2-1, 2*421 codes.
 The codes that represent the pair of complementary digits are
complementary to each other.
Excess-3 code
0: 0011
1: 0100
2: 0101
3: 0110
4: 0111 241: 0101 0111 0100
5: 1000
758: 1010 1000 1011
6: 1001
7: 1010
8: 1011
9: 1100

CPE 202
Alphanumeric Codes (1/3)
 Apart from numbers, computers also handle textual data.
 Character sets frequently used include:
alphabets: ‘A’ .. ‘Z’, and ‘a’ .. ‘z’
digits: ‘0’ .. ‘9’
special symbols: ‘$’, ‘.’, ‘,’, ‘@’, ‘*’, …
non-printable: SOH, NULL, BELL, …

 Usually, these characters can be represented using 7 or 8

bits.

CPE 202
Alphanumeric Codes (2/3)
 ASCII: 7-bit, plus a parity bit for error detection
(odd/even parity).
Character ASCII Code
0 0110000
1 0110001
... ...
9 0111001
: 0111010
A 1000001
B 1000010
... ...
Z 1011010
[ 1011011
\ 1011100

CPE 202
Alphanumeric Codes (3/3)
 ASCII table:
MSBs
LSBs 000 001 010 011 100 101 110 111
0000 NUL DLE SP 0 @ P ` p
0001 SOH DC1 ! 1 A Q a q
0010 STX DC2 “ 2 B R b r
0011 ETX DC3 # 3 C S c s
0100 EOT DC4 $ 4 D T d t
0101 ENQ NAK % 5 E U e u
0110 ACK SYN & 6 F V f v
0111 BEL ETB ‘ 7 G W g w
1000 BS CAN ( 8 H X h x
1001 HT EM ) 9 I Y i y
1010 LF SUB * : J Z j z
1011 VT ESC + ; K [ k {
1100 FF FS , < L \ l |
1101 CR GS - = M ] m }
1110 O RS . > N ^ n ~
1111 SI US / ? O _ o DEL

CPE 202
Error Detection Codes (1/4)
 Errors can occur data transmission. They should be
detected, so that re-transmission can be requested.
 With binary numbers, usually single-bit errors occur.
Example: 0010 erroneously transmitted as 0011, or 0000, or 0110, or
1010.

 Biquinary code uses 3 additional bits for error-detection.

For single-error detection, one additional bit is needed.

CPE 202
Error Detection Codes (2/4)
 Parity bit.
 Even parity: additional bit supplied to make total number of ‘1’s
even.
 Odd parity: additional bit supplied to make total number of ‘1’s odd.

 Example: Odd parity. Character ASCII Code

0 0110000 1
1 0110001 0
... ...
Parity bits
9 0111001 1
: 0111010 1
A 1000001 1
B 1000010 1
... ...
Z 1011010 1
[ 1011011 0
\ 1011100 1
CPE 202
Error Detection Codes (3/4)
 Parity bit can detect odd number of errors but not even
number of errors.
Example: For odd parity numbers,
10011  10001 (detected)
10011  10101 (non detected)

 Parity bits can also be

applied to a block of data: 0110 1
0001 0
1011 0
1111 1
1001 1
0101 0 Column-wise parity

Row-wise parity

CPE 202
Error Detection Codes (4/4)
 Sometimes, it is not enough to do error detection. We may
want to do error correction.
 Error correction is expensive. In practice, we may use only
single-bit error correction.
 Popular technique: Hamming Code (not covered).

CPE 202