Lecture 2: Number Systems

COE 221: Digital Systems

Dr. Fadi Aloul. COE 221. Page 1

Now What?
Mon Sep 16 24 Oct 1 8 15 22 29 Nov 5 12 19 26
COE221: Digital Systems Dr. Fadi Aloul

Wed 18 26 3 10 17 24 31 7 14 21 28 1 2 3 4 5 6 7 8 9 10 11
American University of Sharjah Page 2

Introduction Number Systems and Codes Boolean Algebra & Logic Circ. Midterm Exam #1 Simplification of Switching Fcn. Modular Combinational Logic Introduction to Sequential Dev. Midterm Exam #2 M d l S Modular Sequential ti l L Logic i Memory and Prog. Logic Final Exam

Multiple Languages & Multiple Number Systems

Arabic

English

Decimal

Octal

French

Spanish

Binary

HexaDecimal

Can easily translate one language or number system to another

COE221: Digital Systems Dr. Fadi Aloul American University of Sharjah Page 3

Multiple Languages

Used in the Middle East

Arabic

English

Used in the United States

French
Used in the France

Spanish
Used in Mexico

COE221: Digital Systems Dr. Fadi Aloul

American University of Sharjah Page 4

Multiple Number Systems

Used by Humans

Decimal

Octal

Used by ???

Binary
Used by Computers

HexaDecimal
Used by ???

COE221: Digital Systems Dr. Fadi Aloul

American University of Sharjah Page 5

Decimal System
Decimal system composed of 10 numerals or symbols
0, 1, 2, 3, 4, 5, 6, 7, 8, 9 Known as Base 10 or Radix 10, since it has 10 numbers

Example
9735 = 9000 + 700 + 30 + 5 = 9 x 1000 + 7 x 100 + 3 x 10 + 5 = 9 x 103 + 7 x 102 + 3 x 101 + 5 x 100 2745.214 = 2 x 103 + 7 x 102 + 4 x 101 + 5 x 100 + 2 x 10-1 + 1 x 10-2 + 4 x 10-3
Coefficient Base

COE221: Digital Systems Dr. Fadi Aloul

American University of Sharjah Page 6

Binary System
Unfortunately, decimal number system is not convenient for digital system implementations
Imagine electrical equipment working with 10 different levels of voltage Much easier with two voltages only

Binary system composed of 2 numerals or symbols

0, 1 Known as Base 2 or Radix 2, since it has 2 numbers
Coefficient Base

Example
1011.1012 = 1 x 23 + 0 x 22 + 1 x 21 + 1 x 20 + 1 x 2-1 + 0 x 2-2 + 1 x 2-3 = 8 + 0 + 2 + 1 + 0.5 + 0 + 0.125 = 11.62510
COE221: Digital Systems Dr. Fadi Aloul American University of Sharjah Page 7

Decimal Counting

000 001 002 003 004 005 006 007 008 009

010 011 012 013 014 015 016 017 018 019

020 021 022 023 024 025 026 027 028 029

090 091 092 093 094 095 096 097 098 099

100 101 102 103 104 105 106 107 108 109

COE221: Digital Systems Dr. Fadi Aloul

American University of Sharjah Page 8

Binary Counting
0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
COE221: Digital Systems Dr. Fadi Aloul

What is the largest number that can be represented with 4 bits? 2N (N is the number of bits) = 24 = 16

American University of Sharjah Page 9

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

Binary Numbers

Decimal Numbers

What is the largest number that can be represented with 4 bits? 2N (N is the number of bits) = 24 = 16

COE221: Digital Systems Dr. Fadi Aloul

American University of Sharjah Page 10

Binary To Decimal Conversions

Example
10102 = 1 x 23 + 0 x 22 + 1 x 21 + 0 x 20 =8+0+2+0 = 1010

Exercise
Convert 1001.102 to decimal

COE221: Digital Systems Dr. Fadi Aloul

American University of Sharjah Page 11

Decimal To Binary Conversions

Use repeated division Example
2910 = 111012 Number Quotient Remainder 29 / 2 14 / 2 7/2 3/2 1/2 14 7 3 1 0 1 0 1 1 1

Exercise
Convert 3710 to binary

1 1 1 0 1

COE221: Digital Systems Dr. Fadi Aloul

American University of Sharjah Page 12

Base Conversion Summary

Decimal Binary 10102 = 1 x 23 + 0 x 22 + 1 x 21 + 0 x 2 = 8+0+2+0 = 1010

Decimal

Binary

2910 = 111012 29 / 2 14 / 2 7/2 3/2 1/2 14 7 3 1 0 1 0 1 1 1

COE221: Digital Systems Dr. Fadi Aloul

American University of Sharjah Page 13

Octal System
Often used in digital computer work Octal system composed of 8 numerals or symbols
0, 1, 2, 3, 4, 5, 6, 7 Known as Base 8 or Radix 8, since it has 8 numbers

Example Octal to Decimal Conversion

17358 = 1 x 83 + 7 x 82 + 3 x 81 + 5 x 80 = 512 + 448 + 24 + 5 = 98910

COE221: Digital Systems Dr. Fadi Aloul

American University of Sharjah Page 14

Decimal To Octal Conversions

Use repeated division Example
26610 = 4128 Number Quotient Remainder 266 / 8 33 / 8 4/8 33 4 0 2 1 4

4 1 2

COE221: Digital Systems Dr. Fadi Aloul

American University of Sharjah Page 15

Base Conversion Summary

Decimal Binary Octal 1010B = 1 x B3 + 0 x B2 + 1 x B1 + 0 x B =8+0+2+0 = 1010

Decimal

Binary Octal

2910 = 11101B 29 / B 14 / B 7/B 3/B 1/B 14 7 3 1 0 1 0 1 1 1

COE221: Digital Systems Dr. Fadi Aloul

American University of Sharjah Page 16

Hexadecimal System
Hex system composed of 16 numerals or symbols
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F Known as Base 16 or Radix 16, since it has 16 numbers

Example Hexadecimal to Decimal Conversion

A3216 = 10 x 162 + 3 x 161 + 2 x 160 = 2560 + 48 + 2 = 261010

COE221: Digital Systems Dr. Fadi Aloul

American University of Sharjah Page 17

Decimal To Hexadecimal Conversions

Use repeated division Example
23410 = EA16 Number Quotient Remainder 234 / 16 14 / 16 14 0 A E

E A

COE221: Digital Systems Dr. Fadi Aloul

American University of Sharjah Page 18

Base Conversion Summary

Decimal Binary Octal Hexadecimal 1010B = 1 x B3 + 0 x B2 + 1 x B1 + 0 x B =8+0+2+0 = 1010

Decimal

Binary Octal Hexadecimal

2910 = 11101B 29 / B 14 / B 7/B 3/B 1/B 14 7 3 1 0 1 0 1 1 1

COE221: Digital Systems Dr. Fadi Aloul

American University of Sharjah Page 19

Number Relationships
Decimal
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
COE221: Digital Systems Dr. Fadi Aloul

Binary
0 1 10 11 100 101 110 111 1000 1001 1010 1011 1100 1101 1110 1111

Octal
0 1 2 3 4 5 6 7 10 11 12 13 14 15 16 17

Hexadecimal
0 1 2 3 4 5 6 7 8 9 A B C D E F
American University of Sharjah Page 20

10

Conversions Between Binary / Octal / Hexadecimal

Convert from Hexadecimal to Binary (523D)16 = 0101 0010 0011 1101 (0101001000111101)2

Binary Decimal Octal

Hexadecimal

Convert from Binary to Hexadecimal (0010101100110)2 = 0 0101 0110 0110 0000 0101 0110 0110 0 5 6 6 (0566)16

COE221: Digital Systems Dr. Fadi Aloul

American University of Sharjah Page 21

Conversions Between Binary / Octal / Hexadecimal

Convert from Hexadecimal to Octal (523D)16 = 0101 0010 0011 1101 0 101 001 000 111 101 000 101 001 000 111 101 0 5 1 0 7 5 (051075)8 Convert from Octal to Hexadecimal (437)8 = 100 011 111 0001 0001 1111 1 1 F (11F)16

Binary Decimal Octal

Hexadecimal

COE221: Digital Systems Dr. Fadi Aloul

American University of Sharjah Page 22

11

Conversions Between Different Bases

Convert a number from Base X to Base Y
Convert Base X to Base 10 Convert Base 10 to Base Y

Example
11012 = (??) 3 = 1 x 23 + 1 x 22 + 0 x 21 + 1 x 20 = 8+4+0+1 Number Quotient Remainder = 1310 13 / 3 4 1 1310 = 1113 4/3 1 1 1/3 0 1 1 1 1
COE221: Digital Systems Dr. Fadi Aloul American University of Sharjah Page 23

Why Hexadecimal or Octal Numbers?

Usefulness of Hexadecimal or Octal Numbers
Hex and Octal numbers are easier to read than binary numbers In memory, a 16-bit number such as (0010001101010001)2 0010 0011 0101 0001 2 3 5 1 (2351)16 or 010 001 101 010 001 2 1 5 2 1 (21521)8
COE221: Digital Systems Dr. Fadi Aloul

Difficult to memorize

Easier to memorize

Easier to memorize
American University of Sharjah Page 24

12

Decimal To Binary Conversions - Fractions

Use repeated multiplication, until you get a 0 fraction Example
0.687510 = 0.10112 Fraction x Base = Integer Integer.Fraction Fraction 0.6875 x 2 = 1.375 0.375 x 2 0.75 x 2 0.5 x 2 = 0.75 = 1.5 = 1.0

1 0 1 1

COE221: Digital Systems Dr. Fadi Aloul

American University of Sharjah Page 25

Binary / Octal / Hex Conversions - Fractions

Convert from Hexadecimal to Binary (52.3D)16 = 0101 0010 . 0011 1101 (01010010 . 00111101)2

Binary Decimal Octal

Hexadecimal

Convert from Binary to Hexadecimal (0010101100.110)2 = 00 1010 1100 . 110 0000 1010 1100 . 1100 0 A C. C (0AC.C)16

COE221: Digital Systems Dr. Fadi Aloul

American University of Sharjah Page 26

13

Binary Addition
Similar to Decimal addition
0 + 0 = 00 0 + 1 = 01 1 + 1 = 10

0011 (3) + 0010 (2) ---------------0101 (5)

1101 (13) + 0011 (3) -----------------10000 (16)

COE221: Digital Systems Dr. Fadi Aloul

American University of Sharjah Page 27

Signed Numbers
Digital systems handle positive and negative numbers
Need to be able to represent sign

Three ways for representing signs

Sign magnitude system 1s complement 2s complement

COE221: Digital Systems Dr. Fadi Aloul

American University of Sharjah Page 28

14

Sign Magnitude System

Add an extra sign bit (most significant bit)
0 : Positive 1 : Negative +0 +1 000 001 010 011 111 110 101 100
American University of Sharjah Page 29

Not preferred

+2 +3 -3 -2 -1 -0

COE221: Digital Systems Dr. Fadi Aloul

1s Complement
Flip each bit in binary number (includes sign bit)
0 -> 1 1 -> 0 +0 000 001 010 011 100 101 110 111
American University of Sharjah Page 30

Not preferred

+1 +2 +3 -3 -2 -1 -0

COE221: Digital Systems Dr. Fadi Aloul

15

2s Complement
Another way of representing negative numbers
Positive numbers represented normally Negative numbers two steps Flip Fli each h bit (find (fi d 1st complement) l t) Add a 1 (ignore overflow) Sign bit within the 7 bits

Example
Represent (-45)10 in 2s complement system 0101101 1010010 + 1 -------------1010011 (45) flip [find 1st complement] add 1 0 101101 1 010011 + 45 - 45

2s complement of original binary number

COE221: Digital Systems Dr. Fadi Aloul

American University of Sharjah Page 31

2s Complement
Preferred Allows the user to perform subtraction by actually performing addition! Great! ... Will see that later
Use same hardware for subtraction and addition Save hardware! +0 +1 +2 +3 -3 -2 -1 -0
COE221: Digital Systems Dr. Fadi Aloul

000 001 010 011 101 110 111 000

American University of Sharjah Page 32

16

Signed Numbers
Exercise
Find (-20)10 using: sign magnitude, 1st complement 2nd complement Convert (33)10 to binary in less than 5 seconds [counting hint]

COE221: Digital Systems Dr. Fadi Aloul

American University of Sharjah Page 33

2s Complement
Must include of sign bit Example p
1000 0111 + 1 -------------1000 01000 10111 + 1 -------------11000
COE221: Digital Systems Dr. Fadi Aloul

Confusing! 1000 represents 8 or -8 ?! (8) st flip [find 1 complement] add 1

2s complement of original binary number (8) Better! 01000 represents 8 st 11000 represents -8 flip [find 1 complement] add 1 2s complement of original binary number
American University of Sharjah Page 34

17

Faster Way to Find 2s Complement

Starting from right to left
Stop after first encounter of 1 Flip everything after that
Sign g bit within the 8 bits

Example
Represent (-45)10 in 2s complement system using 8 bits 00101101 11010011 (45) 2s complement of original binary number

Represent (-56)10 in 2s complement system 00111000 11001000

COE221: Digital Systems Dr. Fadi Aloul

(56) 2s complement of original binary number

American University of Sharjah Page 35

Verify Correctness of 2s Complement

Consider Most Significant Bit negative, others positive
00101101 (45) 11010011 2s complement of original binary number -128 + 64 + 16 + 2 + 1 = -45

00111000 (56) 11001000 2s complement of original binary number -128 + 64 + 8 = -56

COE221: Digital Systems Dr. Fadi Aloul

American University of Sharjah Page 36

18

Range of Numbers
An N-bit number
Unsigned : 0 2N -1 Signed : -2N-1 +1 2N-1 -1

Example - 3 bit
Unsigned : 0 7 Signed : -3 3
Unsigned numbers 000 (0) 111 (7)

101 (-3)

011 (3)

Signed numbers
COE221: Digital Systems Dr. Fadi Aloul American University of Sharjah Page 37

Arithmetic in the 2s Complement System

Guidelines
Ignore overflow Consistent sign bits Enough bits for result

Five cases to consider

Two positive numbers +9 0 1001 +4 0 0100 ------------------+13 0 1101
Sign Bit
COE221: Digital Systems Dr. Fadi Aloul

Positive + Small Negative +9 0 1001 -4 1 1100 -----------------5 0 0101

Ignore Overflow
American University of Sharjah Page 38

19

Arithmetic in the 2s Complement System

Positive + Large Negative -9 1 0111 +4 0 0100 -------------------5 1 1011 Two Negative -9 9 1 0111 -4 1 1100 -------------------13 1 0011
COE221: Digital Systems Dr. Fadi Aloul

Equal and Opposite

+9 0 1001 -9 1 0111 ------------------0 0 0000

Arithmetic Overflow

+9 0 1001 +8 0 1000 ------------------17 1 0001

-15? Wrong!
American University of Sharjah Page 39

Arithmetic in the 2s Complement System

Exercise
Find (20) 10 + (-3)10 using 2s complement system.

COE221: Digital Systems Dr. Fadi Aloul

American University of Sharjah Page 40

20

Binary-Coded-Decimal (BCD) Code

Not a new number system Decimal system, but with each digit encoded in its binary equivalent Example
Represent (6839)10 in BCD (6839)10 6 8 3 9 0110 1000 0011 1001 (0110100000111001)bcd Decimal BCD 0 1 2 3 4 5 6 7 8 9
1010 1111 is invalid
COE221: Digital Systems Dr. Fadi Aloul American University of Sharjah Page 41

0000 0001 0010 0011 0100 0101 0110 0111 1000 1001

BCD vs Binary Example

(6839)10

BCD
(0110100000111001)bcd

Binary
(1101010110111)2 Complex conversion to Decimal Simpler Circuits Efficient encoding

Easy conversion to Decimal Complex Circuits Inefficient encoding

COE221: Digital Systems Dr. Fadi Aloul

American University of Sharjah Page 42

21

BCD Arithmetic
Rules:
Ordinary Binary addition If sum is <= 9, done If sum > 9, add 0110 carry is taken to next position

Example
6 0110 +7 0111 --------------13 1101

Invalid in BCD! Sum exceeds 9

Example
6 0110 +3 0011 --------------9 1001 + 0110 add 6 for correction --------------- ( (count skipped pp # #s) ) 0001 0011 1 3

COE221: Digital Systems Dr. Fadi Aloul

American University of Sharjah Page 43

BCD Arithmetic
Example
47 0100 0111 +35 0011 0101 ------------------------82 0111 1100 0110 ------------------------1000 0010 8 2

Example
59 0101 1001 +38 0011 1000 ------------------------97 1001 0001 0110 ------------------------1001 0111 9 7

Sum is 10001

COE221: Digital Systems Dr. Fadi Aloul

American University of Sharjah Page 44

22

ASCII Code
American Standard Code for Information Interchange Consists of 7-bit code
27 = 128 possible codes

Example
Character A B $ = ASCII 100 0001 100 0010 010 0100 011 1101 Octal 101 102 044 075 Hex 41 42 24 3D

COE221: Digital Systems Dr. Fadi Aloul

American University of Sharjah Page 45

Now What?
Mon Sep 16 24 Oct 1 8 15 22 29 Nov 5 12 19 26
COE221: Digital Systems Dr. Fadi Aloul

Wed 18 26 3 10 17 24 31 7 14 21 28 1 2 3 4 5 6 7 8 9 10 11
American University of Sharjah Page 46

Introduction Number Systems and Codes Boolean Algebra & Logic Circ. Midterm Exam #1 Simplification of Switching Fcn. Modular Combinational Logic Introduction to Sequential Dev. Midterm Exam #2 M d l S Modular Sequential ti l L Logic i Memory and Prog. Logic Final Exam

23