2 of 57

Number Systems (1)

Positional Notation

N = (a_n-1a_n-2 ... a₁a₀ . a_-1a_-2 ... a_-m)_r (1.1)

where . = radix point

r = radix or base

n = number of integer digits to the left of the radix point

m = number of fractional digits to the right of the radix point

a_n-1 = most significant digit (MSD)

a_-m = least significant digit (LSD)

Polynomial Notation (Series Representation)

N = a_n-1 x r^n-1 + a_n-2 x r^n-2 + ... + a₀ x r⁰ + a_-1 x r^-1 ... + a_-m x r^-m

= (1.2)

N = (251.41)₁₀ = 2 x 10² + 5 x 10¹ + 1 x 10⁰ + 4 x 10^-1 + 1 x 10^-2

Chapter 1

3 of 57

Number Systems (2)

Binary numbers

Digits = {0, 1}
(11010.11)₂ = 1 x 2⁴ + 1 x 2³ + 0 x 2² + 1 x 2¹ + 0 x 2⁰ + 1 x 2^-1 + 1 x 2^-2

= (26.75)₁₀

1 K (kilo) = 2¹⁰ = 1,024, 1M (mega) = 2²⁰ = 1,048,576,

1G (giga) = 2³⁰ = 1,073,741,824

Octal numbers

Digits = {0, 1, 2, 3, 4, 5, 6, 7}
(127.4)₈ = 1 x 8² + 2 x 8¹ + 7 x 8⁰ + 4 x 8^-1 = (87.5)₁₀

Hexadecimal numbers

Digits = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F}
(B65F)₁₆ = 11 x 16³ + 6 x 16² + 5 x 16¹ + 15 x 16⁰ = (46,687)₁₀

Chapter 1

4 of 57

Number Systems (3)

Important Number Systems (Table 1.1)

Chapter 1

5 of 57

Arithmetic (1)

Binary Arithmetic

Addition

111011 Carries

101011 Augend

+ 11001 Addend

1000100

Subtraction

0 1 10 0 10 Borrows

1 0 0 1 0 1 Minuend

- 1 1 0 1 1 Subtrahend

1 0 1 0

Chapter 1

6 of 57

Arithmetic (2)

Multiplication Division

1 1 0 1 0 Multiplicand

x 1 0 1 0 Multiplier

0 0 0 0 0

1 1 0 1 0

0 0 0 0 0

1 1 0 1 0

1 0 0 0 0 0 1 0 0 Product

Chapter 1

7 of 57

Arithmetic (3)

Octal Arithmetic (Use Table 1.4)

Addition

1 1 1 Carries

5 4 7 1 Augend

+ 3 7 5 4 Addend

11445 Sum

Subtraction

6 10 4 10 Borrows

7 4 5 1 Minuend

- 5 6 4 3 Subtrahend

1 6 0 6 Difference

Chapter 1

8 of 57

Arithmetic (4)

Multiplication Division

326 Multiplicand

x 67 Multiplier

2732 Partial products

2404

26772 Product

Chapter 1

9 of 57

Arithmetic (5)

Hexadecimal Arithmetic (Use Table 1.5)

Addition

1 0 1 1 Carries

5 B A 9 Augend

+ D 0 5 8 Addend

1 2 C 0 1 Sum

Subtraction

9 10 A 10 Borrows

A 5 B 9 Minuend

+ 5 8 0 D Subtrahend

4 D A C Difference

Series Substitution Method

Expanded form of polynomial representation:

N = a_n-1r^n-1 + … + a₀r⁰ + a_-1r^-1 + … + a_-mr^-m (1.3)

Conversion Procedure (base A to base B)

Represent the number in base A in the format of Eq. 1.3.
Evaluate the series using base B arithmetic.

Examples:
(11010)₂ → ( ? )₁₀

(627)₈ → ( ? )₁₀

(11110.101)₂ → ( ? )₈

(2AD.42)₁₆ → ( ? )₁₀

Chapter 1

10 of 57

Arithmetic (6)

Multiplication Division

B9A5 Multiplicand

x D50 Multiplier

3A0390 Partial products

96D61

9A76490 Product

Chapter 1

11 of 57

Base Conversion (1)

Series Substitution Method

Expanded form of polynomial representation:

N = a_n-1r^n-1 + … + a₀r⁰ + a_-1r^-1 + … + a_-mr^-m (1.3)

Conversation Procedure (base A to base B)

Represent the number in base A in the format of Eq. 1.3.
Evaluate the series using base B arithmetic.

Examples:

(11010)₂ →( ? )₁₀

N = 1×2⁴ + 1×2³ + 0×2² + 1×2¹ + 0×2⁰

= (16)₁₀ + (8)₁₀ + 0 + (2)₁₀ + 0

= (26)₁₀

(627)₈ → ( ? )₁₀

N = 6×8² + 2×8¹ + 7×8⁰

= (384)₁₀ + (16)₁₀ + (7)₁₀

= (407)₁₀

Chapter 1

12 of 57

Base Conversion (2)

Radix Divide Method

Used to convert the integer in base A to the equivalent base B integer.
Underlying theory:

(N_I)_A = b_n-1B^n-1 + … + b₀B⁰ (1.4)

Here, b_i’s represents the digits of (N_I)_B in base A.

N_I / Β = (b_n-1B^n-1 + … + b₁B¹ + b₀B⁰ ) / B

= (Quotient Q₁: b_n-1B^n-2 + … + b₁B⁰ ) + (Remainder R₀: b₀)

In general, (b_i)_A is the remainder R_i when Q_i is divided by (B)_A.

Conversion Procedure

1. Divide (N_I)_B by (B)_A, producing Q₁ and R₀. R₀ is the least significant digit, d₀, of the result.

2. Compute d_i, for i = 1 … n - 1, by dividing Q_i by (B)_A, producing Q_i+1 and R_i, which represents d_i.

3. Stop when Q_i+1 = 0.

Chapter 1

13 of 57

Base Conversion (3)

Examples

(315)₁₀ = (473)₈

(315)₁₀ = (13B)₁₆

Chapter 1

14 of 57

Base Conversion (4)

Radix Multiply Method

Used to convert fractions.
Underlying theory:

(N_F)_A = b_-1B^-1 + b_-2B^-2+ … + b_-mB^-m (1.5)

Here, (N_F)_A is a fraction in base A and b_i’s are the digits of (N_F)_B in base A.

B × N_F = B × (b_-1B^-1 + b_-2B^-2+ … + b_-mB^-m )

= (Integer I_-1: b_-1) + (Fraction F_-2: b_-2B^-1+ … + b_-mB^-⁽^m-1⁾)

In general, (b_i)_A is the integer part I_-i, of the product of F_-₍_i+1₎ × (B_A).

Conversion Procedure

1. Let F_-1 = (N_F)_A.

2. Compute digits (b_-i)_A, for i = 1 … m, by multiplying F_i by (B)_A,

producing integer I_-i, which represents (b_-i)_A, and fraction F_-₍_i+1₎.

3. Convert each digits (b_-i)_A to base B.

Chapter 1

15 of 57

Base Conversion (5)

Examples

(0.479)₁₀ = (0.3651…)₈

MSD 3.832 ← 0.479 × 8

6.656 ← 0.832 × 8

5.248 ← 0.656 × 8

LSD 1.984 ← 0.248 × 8

…

(0.479)₁₀ = (0.0111…)₂

MSD 0.9580 ← 0.479 × 2

1.9160 ← 0.9580 × 2

1.8320 ← 0.9160 × 2

LSD 1.6640 ← 0.8320 × 2

…

Chapter 1

16 of 57

Base Conversion (6)

General Conversion Algorithm
Algorithm 1.1

To convert a number N from base A to base B, use

(a) the series substitution method with base B arithmetic, or

(b) the radix divide or multiply method with base A arithmetic.

Algorithm 1.2

To convert a number N from base A to base B, use

(a) the series substitution method with base 10 arithmetic to convert N from base A to base 10, and

(b) the radix divide or multiply method with decimal arithmetic to convert N from base 10 to base B.

Algorithm 1.2 is longer, but easier and less error prone.

Chapter 1

17 of 57

Base Conversion (7)

Example

(18.6)₉ = ( ? )₁₁

(a) Convert to base 10 using series substitution method:

N₁₀ = 1 × 9¹ + 8 × 9⁰ + 6 × 9^-1

= 9 + 8 + 0.666…

= (17.666…)₁₀

(b) Convert from base 10 to base 11 using radix divide and multiply

method:

7.326 ← 0.666 × 11

3.586 ← 0.326 × 11

6.446 ← 0.586 × 11

N₁₁ = (16.736 …)₁₁

Chapter 1

18 of 57

Base Conversion (8)

When B = A^k
Algorithm 1.3

(a) To convert a number N from base A to base B when B = A^k and k is a positive integer, group the digits of N in groups of k digits in both directions from the radix point and then replace each group with the equivalent digit in base B

(b) To convert a number N from base B to base A when B = A^k and k is a positive integer, replace each base B digit in N with the equivalent k digits in base A.

Examples

(001 010 111. 100)₂ = (127.4)₈ (group bits by 3)
(1011 0110 0101 1111)₂ = (B65F)₁₆ (group bits by 4)

Chapter 1

19 of 57

Signed Number Representation

Signed Magnitude Method

N = ± (a_n-1 ... a₀.a_-1 ... a_-m)_r is represented as

N = (sa_n-1 ... a₀.a_-1 ... a_-m)_rsm, (1.6)

where s = 0 if N is positive and s = r -1 otherwise.

N = -(15)₁₀
In binary: N = -(15)₁₀ = -(1111)₂ = (1, 1111)_2sm
In decimal: N = -(15)₁₀ = (9, 15)_10sm

Complementary Number Systems

Radix complements (r's complements)

[N]_r = rⁿ - (N)_r (1.7)

where n is the number of digits in (N)_r.

Positive full scale: r^n-1 - 1
Negative full scale: -rⁿ - 1
Diminished radix complements (r-1’s complements)

[N]_r-1 = r_n - (N)_r - 1

Chapter 1

20 of 57

Radix Complement Number Systems (1)

Two's complement of (N)₂ = (101001)₂

[N]₂ = 2⁶ - (101001)₂ = (1000000)₂ - (101001)₂ = (010111)₂

(N)₂ + [N]₂ = (101001)₂ + (010111)₂ = (1000000)₂

If we discard the carry, (N)₂ + [N]₂ = 0.

Hence, [N]₂ can be used to represent -(N)₂.

[ [N]₂ ]₂ = [(010111)₂]₂ = (1000000)₂ - (010111)₂ = (101001)₂ = (N)₂.

Two's complement of (N)₂ = (1010)₂ for n = 6

[N]₂ = (1000000)₂ - (1010)₂ = (110110)₂.

Ten's complement of (N)₁₀ = (72092)₁₀

[N]₁₀ = (100000)₁₀ - (72092)₁₀ = (27908)₁₀.

Chapter 1

21 of 57

Radix Complement Number Systems (2)

Algorithm 1.4 Find [N]_r given (N)_r .

Copy the digits of N, beginning with the LSD and proceeding toward the MSD until the first nonzero digit, a_i, has been reached
Replace a_i with r - a_i .
Replace each remaining digit a_j , of N by (r - 1) - a_j until the MSD has been replaced.

Example: 10's complement of (56700)₁₀ is (43300)₁₀
Example: 2's complement of (10100)₂ is (01100)₂.
Example: 2’s complement of N = (10110)₂ for n = 8.

Put three zeros in the MSB position and apply algorithm 1.4
N = 00010110
[N]₂ = (11101010)₂

The same rule applies to the case when N contains a radix point.

Chapter 1

22 of 57

Radix Complement Number Systems (3)

Algorithm 1.5 Find [N]_r given (N)_r .

First replace each digit, a_k , of (N)_r by (r - 1) - a_k and then add 1 to the resultant.

For binary numbers (r = 2), complement each digit and add 1 to the result.

Example: Find 2’s complement of N = (01100101)₂ .

N = 01100101

10011010 Complement the bits

+1 Add 1

[N]₂ = (10011011)₁₀

Example: Find 10’s complement of N = (40960)₁₀

N = 40960

59039 Complement the bits

+1 Add 1

[N]₂ = (59040)₁₀

Chapter 1

23 of 57

Radix Complement Number Systems (4)

Two's complement number system (See Table 1.6):

Positive number :

N = +(a_n-2, ..., a₀)₂ = (0, a_n-2, ..., a₀)_2cns,

where .

Negative number:

N = (a_n-1, a_n-2, ..., a₀)₂
-N = [a_n-1, a_n-2, ..., a₀]₂ (two's complement of N),

where .

Example: Two's complement number system representation of ± (N)₂

when (N)₂ = (1011001)₂ for n = 8:

+(N)₂ = (0, 1011001)_2cns
-(N)₂ = [+(N)₂]₂ = [0, 1011001]₂ = (1, 0100111)_2cns

Chapter 1

24 of 57

Radix Complement Number Systems (5)

Example: Two's complement number system representation of -(18)₁₀ , n = 8:

+(18)₁₀ = (0, 0010010)_2cns
-(18)₁₀ = [0, 0010010]₂ = (1, 1101110)_2cns

Example: Decimal representation of N = (1, 1101000)_2cns

N = (1, 1101000)_2cns = -[1, 1101000]₂ = -(0, 0011000)_2cns = -(24)₂ .

Chapter 1

25 of 57

Radix Complement Arithmetic (1)

Radix complement number systems are used to convert subtraction to addition, which reduces hardware requirements (only adders are needed).
A - B = A + (-B) (add r’s complement of B to A)

Range of numbers in two’s complement number system:

, where n is the number of bits.

2^n-1 -1 = (0, 11 ... 1)_2cns and -2^n-1 = (1, 00 ... 0)_2cns
If the result of an operation falls outside the range, an overflow condition is said to occur and the result is not valid.

Consider three cases:

A = B + C,
A = B - C,
A = - B - C,

(where B ≥ 0 and C ≥ 0.)

Chapter 1

26 of 57

Radix Complement Arithmetic (2)

Case 1: A = B + C

(A)₂ = (B)₂ + (C)₂
If A > 2^n-1 -1 (overflow), it is detected by the nth bit, which is set to 1.

Example: (7)₁₀ + (4)₁₀ = ? using 5-bit two’s complement arithmetic.

+ (7)₁₀ = +(0111)₂ = (0, 0111)_2cns
+ (4)₁₀ = +(0100)₂ = (0, 0100)_2cns
(0, 0111)_2cns + (0, 0100)_2cns = (0, 1011)_2cns = +(1011)₂ = +(11)₁₀
No overflow.

Example: (9)₁₀ + (8)₁₀ = ?

+ (9)₁₀ = +(1001)₂ = (0, 1001)_2cns
+ (8)₁₀ = +(1000)₂ = (0, 1000)_2cns
(0, 1001)_2cns + (0, 1000)_2cns = (1, 0001)_2cns (overflow)

Chapter 1

27 of 57

Radix Complement Arithmetic (3)

Case 2: A = B - C

A = (B)₂ + (-(C)₂) = (B)₂ + [C]₂ = (B)₂ + 2ⁿ - (C)₂ = 2ⁿ + (B - C)₂
If B ≥ C, then A ≥ 2ⁿ and the carry is discarded.
So, (A)₂ = (B)₂ + [C]|_{carry discarded}
If B < C, then A = 2ⁿ - (C - B)₂ = [C - B]₂ or A = -(C - B)₂ (no carry in this case).
No overflow for Case 2.

Example: (14)₁₀ - (9)₁₀ = ?

Perform (14)₁₀ + (-(9)₁₀)
(14)₁₀ = +(1110)₂ = (0, 1110)_2cns
-(9)₁₀ = -(1001)₂ = (1, 0111)_2cns
(14)₁₀ - (9)₁₀ = (0, 1110)_2cns + (1, 0111)_2cns = (0, 0101)_2cns + carry

= +(0101)₂ = +(5)₁₀

Chapter 1

28 of 57

Radix Complement Arithmetic (4)

Example: (9)₁₀ - (14)₁₀ = ?

Perform (9)₁₀ + (-(14)₁₀)
(9)₁₀ = +(1001)₂ = (0, 1001)_2cns
-(14)₁₀ = -(1110)₂ = (1, 0010)_2cns
(9)₁₀ - (14)₁₀ = (0, 1001)_2cns + (1, 0010)_2cns = (1, 1011)_2cns

= -(0101)₂ = -(5)₁₀

Example: (0, 0100)_2cns - (1, 0110)_2cns = ?

Perform (0, 0100)_2cns + (- (1, 0110)_2cns)
- (1, 0110)_2cns = two’s complement of (1,0110)_2cns

= (0, 1010)_2cns

(0, 0100)_2cns - (1, 0110)_2cns = (0, 0100)_2cns + (0, 1010)_2cns

= (0, 1110)_2cns = +(1110)₂ = +(14)₁₀

+(4)₁₀ - (-(10)₁₀) = +(14)₁₀

Chapter 1

29 of 57

Radix Complement Arithmetic (5)

Case 3: A = -B - C

A = [B]₂ + [C]₂ = 2ⁿ - (B)₂ + 2ⁿ - (C)₂ = 2ⁿ + 2ⁿ - (B + C)₂ = 2ⁿ + [B + C]₂
The carry bit (2ⁿ) is discarded.
An overflow can occur, in which case the sign bit is 0.

Example: -(7)₁₀ - (8)₁₀ = ?

Perform (-(7)₁₀) + (-(8)₁₀)
-(7)₁₀ = -(0111)₂ = (1, 1001)_2cns , -(8)₁₀ = -(1000)₂ = (1, 1000)_2cns
-(7)₁₀ - (8)₁₀ = (1, 1001)_2cns + (1, 1000)_2cns = (1, 0001)_2cns + carry

= -(1111)₂ = -(15)₁₀

Example: -(12)₁₀ - (5)₁₀ = ?

Perform (-(12)₁₀) + (-(5)₁₀)
-(12)₁₀ = -(1100)₂ = (1, 0100)_2cns , -(5)₁₀ = -(0101)₂ = (1, 1011)_2cns
-(7)₁₀ - (8)₁₀ = (1, 0100)_2cns + (1, 1011)_2cns = (0, 1111)_2cns + carry
Overflow, because the sign bit is 0.

Chapter 1

30 of 57

Radix Complement Arithmetic (6)

Example: A = (25)₁₀ and B = -(46)₁₀

A = +(25)₁₀ = (0, 0011001)_2cns , -A = (1, 1100111)_2cns
B = -(46)₁₀ = -(0, 0101110)₂ = (1, 1010010)_2cns , -B = (0, 0101110)_2cns

A + B = (0, 0011001)_2cns + (1, 1010010)_2cns = (1, 1101011)_2cns = -(21)₁₀
A - B = A + (-B) = (0, 0011001)_2cns + (0, 0101110)_2cns

= (0, 1000111)_2cns = +(71)₁₀

B - A = B + (-A) = (1, 1010010)_2cns + (1, 1100111)_2cns

= (1, 0111001)_2cns + carry = -(0, 1000111)_2cns = -(71)₁₀

-A - B = (-A) + (-B) = (1, 1100111)_2cns + (0, 0101110)_2cns

= (0, 0010101)_2cns + carry = +(21)₁₀

Note: Carry bit is discarded.

Chapter 1

31 of 57

Radix Complement Arithmetic (7)

Summary

When numbers are represented using two’s complement number system:

Addition: Add two numbers.
Subtraction: Add two’s complement of the subtrahend to the minuend.
Carry bit is discarded, and overflow is detected as shown above.

Radix complement arithmetic can be used for any radix.

Chapter 1

32 of 57

Diminished Radix Complement Number systems (1)

Diminished radix complement [N]_r-1 of a number (N)_r is:

[N]_r-1 = rⁿ - (N)_r - 1 (1.10)

One’s complement (r = 2):

[N]_2-1 = 2ⁿ - (N)₂ - 1 (1.11)

Example: One’s complement of (01100101)₂

[N]_2-1 = 2⁸ - (01100101)₂ - 1

= (100000000)₂ - (01100101)₂ - (00000001)₂

= (10011011)₂ - (00000001)₂

= (10011010)₂

Chapter 1

33 of 57

Diminished Radix Complement Number systems (2)

Example: Nine’s complement of (40960)

[N]_2-1 = 10⁵ - (40960)₁₀ - 1

= (100000)₁₀ - (40960)₁₀ - (00001)₁₀

= (59040)₁₀ - (00001)₁₀

= (59039)₁₀

Algorithm 1.6 Find [N]_r-1 given (N)_r .

Replace each digit a_i of (N)_r by r - 1 - a. Note that when r = 2, this simplifies

to complementing each individual bit of (N)_r .

Radix complement and diminished radix complement of a number (N):

[N]_r = [N]_r-1 + 1 (1.12)

Chapter 1

34 of 57

Diminished Radix Complement Arithmetic (1)

Operands are represented using diminished radix complement number system.
The carry, if any, is added to the result (end-around carry).

Example: Add +(1001)₂ and -(0100)₂ .

One’s complement of +(1001) = 01001

One’s complement of -(0100) = 11011

01001 + 11011 = 100100 (carry)

Add the carry to the result: correct result is 00101.

Example: Add +(1001)₂ and -(1111)₂ .

One’s complement of +(1001) = 01001

One’s complement of -(1111) = 10000

01001 + 10000 = 11001 (no carry, so this is the correct result).

Chapter 1

35 of 57

Diminished Radix Complement Arithmetic (2)

Example: Add -(1001)₂ and -(0011)₂ .

One’s complement of the operands are: 10110 and 11100

10110 + 11100 = 110010 (carry)

Correct result is 10010 + 1 = 10011.

Example: Add +(75)₁₀ and -(21)₁₀ .

Nine’s complements of the operands are: 075 and 978

075 + 978 = 1053 (carry)

Correct result is 053 + 1 = 054

Example: Add +(21)₁₀ and -(75)₁₀ .

Nine’s complements of the operands are: 021 and 924

021 + 924 = 945 (no carry, so this is the correct result).

Chapter 1

36 of 57

Computer Codes (1)

Code is a systematic use of a given set of symbols for representing information.
Example: Traffic light (Red: stop, Yellow: caution, Blue: go).

Numeric Codes

To represent numbers.
Fixed-point and floating-point number.

Fixed-point Numbers

Used for signed integers or integer fractions.
Sign magnitude, two’s complement, or one’s complement systems are used.
Integer: (Sign bit) + (Magnitude) + (Implied radix point)
Fraction: (Sign bit) + (Implied radix point) + (Magnitude)

Chapter 1

37 of 57

Computer Codes (2)

Excess or Biased Representation

An excess-K representation of a code C: Add K to each code word C.
Frequently used for the exponents of floating-point numbers.
Excess-8 representation of 4-bit two’s complement code: Table 1.8

Chapter 1

38 of 57

Floating Point Numbers (1)

N = M × r^E, where (1.13)

M (mantissa or significand) is a significant digits of N
E (exponent or characteristic) is an integer exponent.

In general, N = ± (a_n-1 ... a₀.a_-1 ... a_-m)_r is represented by

N = ± (.a_n-1 ... a_-m)_r × rⁿ

M is usually represented in sign magnitude:

M = (S_M.a_n-1 ... a_-m)_rsm , where (1.14)
(.a_n-1 ... a_-m)_r represents the magnitude
S_M = (0: positive, 1: negative) (1.15)

Chapter 1

39 of 57

Floating Point Numbers (2)

E is usually coded in excess-K two’s complement.
K is called a bias and usually selected to be 2^e-1 (e is the number of bits).
So, biased E is:

-2^e-1 ≤ Ε ≤ 2^ε−1
0 ≤ Ε + 2^ε−1 ≤ 2^ε

Excess-K form of E is written as: E = (b_e-1, b_e-2 ... b₀)_excess-_K (1.16)

where b_e-1 is the sign bit.

Combining Eqs. (1.14) and (1.16), we have

N = (S_Mb_e-1b_e-2 ... b₀a_n-1 ... a_-m)_r (1.17)

representing N = (1.18)

The number 0 is represented by an all-zero word.

Chapter 1

40 of 57

Floating Point Numbers (3)

Multiple representations of a given number:

N = M × r^E (1.19)

= (M ÷ r) × r^E+1 (1.20)

= (M × r) × r^E-1 (1.21)

Example: M = +(1101.0101)₂

M = +(1101.0101)₂

= (0.11010101)₂ × 2⁴ (1.22)

= (0.011010101)₂ × 2⁵ (1.23)

= (0.0011010101)₂ × 2⁶ (1.24)

…

Normalization is used for a unique representation: mantissa has a nonzero value in its MSD position.
Eq. 1.22 gives the normalization representation of M.

Chapter 1

41 of 57

Floating Point Numbers (4)

Floating-point Number Formats

Typical single-precision format

Typical extended-precision format

Chapter 1

42 of 57

Floating Point Numbers (5)

Example: N = (101101.101)₂, where n + m = 10 and e = 5. Assume that a normalized sign magnitude fraction is used for M and that Excess-16 two’s complement is used for E.

N = (101101.101)₂ = (0.101101101)2 × 2⁶
M = +(0.1011011010)₂ = (0.1011011010)_2sm

E = +(6)₁₀ = +(0110)₂ = (00110)_2cns
Add the bias 16 = (10000)₂ to E

E = 00110 + 10000 = 10110

So, E = (1, 0110)_excess-16

Combining M and E, we have

N = (0, 1, 0110, 1011011010)_fp

Chapter 1

43 of 57

Characters and Other Codes (1)

To represent information as strings of alpha-numeric characters.

Binary Coded Decimal (BCD)

Used to represent the decimal digits 0 - 9.
4 bits are used.
Each bit position has a weight associated with it (weighted code).
Weights are: 8, 4, 2, and 1 from MSB to LSB (called 8-4-2-1 code).
BCD Codes:

0: 0000 1: 0001 2: 0010 3: 0011 4: 0100

5: 0101 6: 0110 7: 0111 8: 1000 9: 1001

Used to encode numbers for output to numerical displays
Used in processors that perform decimal arithmetic.

Example: (9750)₁₀ = (1001011101010000)_BCD

Chapter 1

44 of 57

Characters and Other Codes (2)

ASCII (American Standard Code for Information Interchange)

Most widely used character code.
See Table 1.11 for 7-bit ASCII code.
The eighth bit is often used for error detection (parity bit)
Example: ASCII code representation of the word Digital

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

Chapter 1

45 of 57

Characters and Other Codes (3)

Gray Code

Cyclic code: A circular shifting of a code word produces another code word.
Gray code: A cyclic code with the property that two consecutive code words differ in only 1 bit (the distance between the two code words is 1).
Gray code for decimal numbers 0 - 15: See Table 1.12

Chapter 1

46 of 57

Error Detection Codes and Correction Codes(1)

An error: An incorrect value in one or more bits.
Single error: An incorrect value in only one bit.
Multiple error: One or more bits are incorrect.
Errors are introduced by hardware failures, external interference (noise), or other unwanted events.

Error detection/correction code: Information is encoded in such a way that a particular class of errors can be detected and/or corrected.

Let I and J be n-bit binary information words

w(I): the number of 1’s in I (weight)
d(I, J): the number of bit positions in which I and J differ (distance)

Example: I = (01101100) and J = (11000100)

w(I) = 4 and w(J) = 3
d(I, J) = 3.

Chapter 1

47 of 57

Error Detection Codes and Correction Codes(2)

General Properties

Minimum distance, d_min, of a code C: for any two code words I and J in C,

d(I, J) ≥ d_min

A code provides t error correction plus detection of s additional errors if and only if the following inequality is satisfied.

2t + s + 1 ≤ d_min (1.25)

Example:

Single-error detection (SED): s = 1, t = 0, d_min = 2.
Single-error correction (SEC): s = 0, t = 1, d_min = 3.
Single-error correction and double-error detection (SEC and DED):

s = t = 1, d_min = 4.

Chapter 1

48 of 57

Error Detection Codes and Correction Codes(3)

Relationship between the minimum distance between code words and the ability to detect and correct errors:

Chapter 1

49 of 57

Error Detection Codes and Correction Codes(4)

Simple Parity Code

Concatenate (|) a parity bit, P, to each code word of C.

Odd-parity code: w(P|C) is odd.
Even-parity code: w(P|C) is even.

Parity coding on magnetic tape:

Chapter 1

50 of 57

Error Detection Codes and Correction Codes(5)

Example: Odd-parity code for ASCII code characters:

Error detection: Check whether a code word has the correct parity.
Single-error detection code (d_min = 2).

Two-out-of-Five Code

Each code word has exactly two 1’s and three 0’s.
Detects single errors and multiple errors in adjacent bits.

Chapter 1

51 of 57

Hamming Codes (1)

Multiple check bits are employed.
Each check bit is defined over (or covers) a subset of the information bits.
Subsets overlap so that each information bit is in at least two subsets.
d_min is equal to the weight of the minimum-weight nonzero code word.

Hamming Code 1 (Table 1.14)

d_min = 3, single error correction code.
Let the set of all code words: C

an error word with single error: c_e

the correct code word for the error word: c

then, d(c_e,c) = 1 and d(c_e, w) > 1 for all other w ∈ C (see Table 1.15)

So, a single error can be detected and corrected by finding out the code word which differs in 1 bit position from the error word.

Chapter 1

52 of 57

Hamming Codes (2)

A code word consists of 4 information bits and 3 check bits:

c = (i₃ i₂ i₁ i₀ c₂ c₁ c₀)

Each check bit covers:

c₂: i₃, i₂, i₁c₁: i₃, i₂, i₀ c₀: i₃, i₁, i₀

This relationship is specified by the generating matrix, G:

(1.26)

Encoding of an information word i to produce a code word, c:

c = iG (1.27)

Chapter 1

53 of 57

Hamming Codes (3)

Decoding can be done using the parity-check matrix, H:

(1.28)

H matrix is can be derived from G matrix.

An n-tuple c is a code word generated by G if and only if

Hc^T = 0 (1.29)

Let d be a data word corresponding to a code word c, which has been corrupted by an error pattern e. Then

d = c + e (1.30)

Decoding:

Compute the syndrome, s, of d using H matrix.
s tells the position of the erroneous bit.

Chapter 1

54 of 57

Hamming Codes (4)

Computation of the syndrome:

s = Hd^T (1.31)

= H(c + e)^T

= Hc^T + He^T

= 0 + He^T

= He^T (1.32)

Note: All computations are performed using modulo-2 arithmetic.

See Table 1.16 for the syndromes and error patterns.

Chapter 1

55 of 57

Hamming Codes (5)

Hamming Code 2 (Table 1.14)

d_min = 4, single error correction and double-error detection.
The generator and parity-check matrices are:

(1.33) (1.34)

Odd-weight-column code:

H matrix has an odd number of ones in each column.
Example: Hamming Code 2.
Has many properties; single-error correction, double-error detection, multiple-error detection, low cost encoding and decoding, etc.

Chapter 1

56 of 57

Hamming Codes (6)

Hamming codes are most easily designed by specifying the H matrix.
For any positive integer m ≥ 3, there exists an (n, k) SEC Hamming code with the following properties:

Code length: n = 2^m - 1
Number of information bits: k = 2^m - m - 1
Number of check bits: n - k = m
Minimum distance: d_min = 3

The H matrix is an n × m matrix with all nonzero m-tuples as its column.
A possible H matrix for a (15, 11) Hamming code, when m = 4:

(1.35)

Chapter 1

57 of 57

Hamming Codes (7)

Example: A Hamming code for encoding five (k = 5) information bits.

Four check bits are required (m = 4). So, n = 9.
A (9, 5) code can be obtained by deleting six columns from the (15,11) code shown above.
The H and G matrices are:

(1.36) (1.37)

Chapter 1