EE303: Digital System Design

Number Systems

Kyeongha Kwon
School of EE, KAIST
Decimal Numbers (I)
 Represented as a set of decimal digits from 0 to 9: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9

 Called base 10 (∵ it uses ten digits and multiplies a factor by a power of 10)
− As an example,

7392 = 7x103 + 3x102 + 9x101 + 2x100

In formal notation, (7392)10

− Another example with fractions,

97654.35 = 9x104 + 7x103 + 6x102 + 5x101 + 4x100 + 3x10-1 + 5x10-2

In formal notation, (97654.35)10

2
Decimal Numbers (II)
 Represented by a series of coefficients: aj
− The coefficients aj are any of the 10 digits (0, 1, 2, …, 9)
− The subscript j gives the place value → aj x 10j

 The general convention:

− (anan-1…a1a0.a-1a-2…a-(m-1)a-m)10
= anx10n + an-1x10n-1 + … + a1x101 + a0x100 + a-1x10-1 + a-2x10-2 + … + a-(m-1)x10-(m-1) + a-mx10-m

 Why do many numbering systems use ten digits and its powers?

3
Binary Numbers (I)
 Made of binary digits (bits): 0 and 1

 Called base 2 (∵ it uses binary digits and multiplies a factor by a power of 2)

− As an example,

(1011)2 = 1x23 + 0x22 + 1x21 + 1x20 = (11)10

− Another example with fractions,

(11010.11)2 = 1x24 + 1x23 + 0x22 + 1x21 + 0x20 + 1x2-1 + 1x2-2 = (26.75)10

4
Binary Numbers (II)
 The first 24 numbers obtained from 2n
In computer-related works,
210 (K), 220 (M), 230 (G), 240 (T)

4K = 22 X 210 = 212 = 4096

 A binary digit (bit) is the minimum unit of binary information stored in a computer
− Groups of eight bits are called bytes: e.g. (11001001)2

 A computer memory is given in bytes (B)

− For example, 4GB = 22 X 230 B = 232 bytes
5
Different Number Systems
 A number expressed in a base-r system:
(anan-1…a1a0.a-1a-2…a-(m-1)a-m)r = an x rn + an-1 x rn-1 + … + a1 x r1 + a0 x r0 +
a-1 x r-1 + a-2 x r-2 + … + a-(m-1) x r-(m-1) + a-m x r-m

− The coefficient aj : 0 ≤ aj ≤ r-1

 An example of an octal number (base-8):

(127.4)8 = 1 x 82 + 2 x 81 + 7 x 80 + 4 x 8-1 = (87.5)10

6
Hexadecimal Numbers
 For the base greater than 10, we use A, B, C… for digits 10, 11, 12…
 An example of a hexadecimal number (base-16):
(B65F)16 = 11 x 163 + 6 x 162 + 5 x 161 + 15 x 160
= (46687)10

 Convenient to represent long strings of bits in digital systems.

(B65F)16 = 11 x 163 + 6 x 162 + 5 x 161 + 15 x 160
= (1011011001011111)2

Hexadecimal numbers represent a byte with two digits!

7
Number-base Conversions
 Numbers in different bases are said to be “equivalent” if they have
the same decimal representation.

 For example,
− (0011)8 = 1 x 81 + 1 x 80 = (9)10
(0011)8 and (1001)2 are equivalent!
− (1001)2 = 1 x 23 + 1 x 21 = (9)10

 The conversion of a number in base r to decimal

− By expanding the number in a power series and adding all the terms

Decimal: Binary:
base 10 base r
8
Decimal to Base-r
 If the number includes a radix point
− Separate the number into an integer part and a fraction part

− Example for (41.6875)10

(41)10 (0.6875)10
Integer part Fraction part

 The conversion of a decimal integer to a number in base r

− By dividing the number and all successive quotients by r and accumulating the remainders.

Decimal: Binary:
base 10 base r
9
Decimal Integer to Base-r (I)
 The conversion of a decimal integer to a number in base r
− By dividing the number and all successive quotients by r and accumulating the remainders.

− Example for converting (41)10 to base-2 Terms

divisor quotient
2 41 dividend remainder

2 20 1
41 ÷ 2 = 20 ··· 1
2 10 0
2 5 0
∴ (41)10 = (101001)2
2 2 1
2 1 0 Decimal Binary:
0 1 Integer base r
Quotient Remainder 10
Decimal Integer to Base-r (II)
 Steps:
1. Divide a decimal number by the base (e.g. 2)

2. The remainder is the lowest-order digit

3. Have the quotient as a new dividend

4. Repeat above until the quotient becomes 0

Decimal Binary:
Integer base r
11
Decimal Fraction to Base-r (I)
 The conversion of a decimal fraction to a number in base r
− By a method similar to that used for integers
• Multiplication is used instead of division
Terms
• Integers instead of remainders are accumulated multiplier
multiplicand product
− Example for converting (0.6875)10 to base-2

Integer Fraction 0.6875 x 2 = 1.3750

0.6875 x 2 = 1 + 0.3750
0.3750 x 2 = 0 + 0.7500 ∴ (0.6875)10 = (0.1011)2
0.7500 x 2 = 1 + 0.5000
0.5000 x 2 = 1 + 0.0000 Decimal Binary:
Fraction base r
until the fraction becomes 0 or
until the number of digits has sufficient accuracy 12
Decimal Fraction to Base-r (II)
 Steps:
− Multiply a decimal number by the base (e.g. 2)
− The integer is the highest-order digit ( 0 ≤ integers ≤ r-1)
− Have the fraction as a new multiplicand
− Repeat above until the fraction becomes zero
or
until the number of digits has sufficient accuracy

 Example for converting (0.3)10 to base-2

0.3 x 2 = 0 + 0.6
0.6 x 2 = 1 + 0.2
0.2 x 2 = 0 + 0.4 ∴ (0.3)10 ≃ (0.010011…)2 Decimal Binary:
0.4 x 2 = 0 + 0.8 Fraction
0.8 x 2 = 1 + 0.6
base r
0.6 x 2 = 1 + 0.2 13
Binary Addition/Multiplication
 Same as decimal addition/multiplication we know
− except that the digits can be only 0 or 1

Binary Addition Binary Multiplication

Multiplicand

Shifted-left copy of
the multiplicand

14
Binary Subtraction
 Same as decimal subtraction we know
− except that the borrow in a given significant position adds 2 to a minuend digit

Binary Subtraction

1 2 borrows
0 2 2 0 0 2

1 0
0 1 1 0 1
- 1 0 1 1 1
------------------------
1 1 0 1 1 0

15
Signed Binary Numbers
 For decimal numbers, plus (+) and minus (-) sign used (e.g. +25, -25)
 Computers need to represent everything as binary digits (bits) : 0 or 1
 Three types of signed binary number representations:
- Signed magnitude
- 1’s complement
- 2’s complement

16
Signed Magnitude
 The sign with a bit placed in the leftmost position of the number,
− Making the sign bit 0 for positive and 1 for negative.

Sign bit Signed binary number

Magnitude
0110012 = + 2510 1110012 = - 2510

1 1 0 0 1
Sign bit Magnitude Sign bit Magnitude

0 for positive
Unsigned Binary Numbers
1 for negative 1110012 = 5710

Magnitude

17
Signed Complement
 A negative number is indicated by its complement
 Since positive numbers always start with 0 (plus) in the leftmost position,
the complement will always start with a 1, indicating a negative number

Signed magnitude Signed complement (1’s complement)

000011002 = 1210 000011002 = 1210

Sign bit Magnitude Sign bit Magnitude

100011002 = - 1210 111100112 = - 1210

Sign bit Magnitude Sign bit Magnitude

18
One’s Complement Representation
 The 1’s complement of a binary number involves inverting all bits
+3 -3 0
- 1’s complement of 0011 is 1100  0011 + 1100 = 1111 The sum of two 1’s complement
numbers is always 1111
- 1’s complement of 0101 is 1010  0101 + 1010 = 1111
+5 -5 0

 For an n-bit number K, the 1’s complement is (2n-1) – K

1’s complement Sum of two 1’s complement numbers (= zero)

+5 -5
01012 = 510 10102 = - 510 01012 + 10102
= 11112
= 010 2 ways to represent 0
in 1’s complement
= 00002
19
Two’s Complement Representation
 The two’s complement of a binary number involves inverting all bits and plus 1
+3 -3 0
− 2’s complement of 0011 is 1101  0011 + 1101 = (1)0000 The sum of two 2’s complement
numbers is always 0000
− 2’s complement of 0101 is 1011  0101 + 1011 = (1)0000
+5 -5 0

 For an n-bit number K, the 2’s complement is (2n-1) - K + 1 = 2n - K

1’s complement 2’s complement

000011002 = 1210 000011002 = 1210

Sign bit Magnitude Sign bit Magnitude

111100112 = - 1210 111101002 = -1210

Sign bit Magnitude Sign bit Magnitude 20

4-bit Signed Binary Numbers

The positive numbers in three

representations are identical and
have 0 in the leftmost position

Representing zero

The negative numbers have 1

in the leftmost position

21
Two’s Complement Rules
 For an n-bit number N, machines that use 2’s complement can represent integers
− -2n-1 ≤ N ≤ 2n-1-1, which are 2n continuous numbers.

− Note that -2n-1 = (100..00)2 and 2n-1-1 = (011..11)2

 2’s complement has more negative numbers than positive

− While 1’s complement has two representations for zero

22
Two’s Complement Addition
 To add numbers represented in 2’s complement,
1. Add two numbers, including sign bits
2. Discard a carry out of the sign-bit position

 For example, (-12)10 + (-3)10

− (+12)10 = (01100)2  (-12)10 = (10100)2 in 2’s comp.

− (+3)10 = (00011)2  (-3)10 = (11101)2 in 2’s comp.

1 0 1 0 0
Add + 1 1 1 0 1
-------------- Invert Plus 1
Final 1 1 0 0 0 1 (10001)2  (01110) 2  (01111) 2 = (15)10.
Result
23
Two’s Complement Subtraction
 Subtraction is same as addition
− Convert subtraction into addition: +A - +B = +A + (-B)
1. Take the 2’s complement of the subtrahend, including the sign bit : B  -B
0 1 1 0 0
2. Add : A + (-B)
- 0 0 0 0 1
 For example, (12)10 - (1)10 = (11)10 --------------
− (12)10 = (01100)2 = (01100)2 in 2’s comp 2’s comp
0 1 1 0 0
− (1)10 = (00001)2 , (11110)2 , (11111)2 = (-1)10 Add + 1 1 1 1 1
Invert Plus 1 --------------
Final
Result 1 0 1 0 1 1

24
Two’s Complement Subtraction
 Another example of a negative result, (5)10 - (12)10 = (-7)10
− (5)10 = (00101)2 in 2’s comp
− (12)10 = (01100)2 , (10011)2  (10100)2 in 2’s comp
Invert Plus 1

0 0 1 0 1
+ 1 0 1 0 0
-------------- Does this works for a negative result? Yes!

1 1 0 0 1

-7
25
Binary Codes
 Digital systems use signals that have two distinct values and circuit elements
that have two stable states: 0 or 1

 Digital systems store and process many other discrete elements of

information with a binary code : a pattern of 0’s and 1’s

 Binary codes : Gray code, ASCII code, …

26
Gray Code
 Many physical systems output continuous quantities
 Analog information must be converted into digital form to be applied to a digital system
 Gray code
− Represents digital data that have been converted from analog data.

− Only one bit changes from one decimal digit to the next

Analog (A) information Digital (D) information

analog‐to‐digital
conversion
27
Gray Code
 A binary code but not a number system
− Example of the gray code of 4-bit data

 Only one bit changes from one decimal digit to the next 1-bit diff.
1-bit diff.
− Useful for reducing errors

− Especially when the original data is continuous

4-bit diff. 1-bit diff.

28
ASCII Code
 American Standard Code for Information Interchange
 A standard binary code to represent the alphanumeric characters in binary format
7 bits

uppercase letters

128 characters
(27) lowercase letters

numerals

printable characters
29
Binary Data Storage
 A binary cell
− A device that possesses two stable states and is capable of
storing one bit of information
• e.g. a SRAM cell, a DRAM cell

 A resister
SRAM cell
− A group of binary cells which store any discrete quantity of
information that contains n bits
8-bit Register

0 0 1 0 1 0 1 1 28 = 256 possible states

Assuming the content represents a binary integer,
…
the 8-bit register can store any binary numbers 0 ~255
8 Binary Cells e.g. 00101011 = (43)10 DRAM cell
30
Building a Computer (Memory + Logic)
 Registers
− Basic elements for storing and holding the binary information
 Digital logic circuits
− Process the binary information stored in the registers.
 Memory unit
− Stores information in millions of registers
− Has no capability of processing data
 Processor unit
− Processes digital data using digital logic
− Has limited, temporal memory elements

31
Building a Computer (Memory + Logic)
 An example of binary information processing
① The contents of two operands transferred from memory registers into R1 and R2

② The digital logic circuits produce the sum, which is transferred to R3

③ The contents of R3 transferred back to one of the memory registers

③
Chapters 2-6 : digital logic circuits and registers

②
Chapter 7 : memory unit
Chapter 8 : register operations at the register transfer level

32
Binary Logic
 Binary logic consists of binary variables and logic operations
 Binary variables
− A,B,C, x, y, z, …, taking on two possible values (1 or 0)

 Logical operations
− AND, OR, NOT, …, producing a binary result (z)

x
Logical Operation z
y

x, y, z are binary variables

33
Logical Operation: AND
 Represented by a dot (·) or by the absence of an operator
− “x AND y equals to z” → “x · y = z” or “xy = z”

− z = 1 only if x = y = 1; otherwise z = 0.

Truth Table

Similar to multiplication!

z = 1 only if x = y = 1
34
Logical Operation: OR
 Represented by a plus sign (+)
− “x OR y equals to z” → “x + y = z”

− z = 0 only if x = y = 0; otherwise z = 1.

Truth Table

Similar to addition! (but, 1 + 1 = 1)

z = 0 only if x = y = 0

35
Logical Operation: NOT
 Represented by a prime (') or by an overbar (‾)
− “NOT x is equal to z” → “x' = z” or “x‾ = z”

− z = 0 if x = 1; z = 1 if x = 0.

Truth Table

Also referred to as the complement operation!

36
Truth Table
 A table of all possible combinations of the variables
− It shows the relation btw the values that the variables may take and the
result of the operation

Truth Tables

x·y=z x+ y = z x' = z
37
Logic Gates (I)
 Basic building blocks of any digital system
− Electronic circuits that perform logical operations on one or more binary inputs and
produce one binary output

x
Logic Gates z
y (performing logical operations)

 Symbols

2-input AND gate 2-input OR gate NOT gate

(inverter)
38
Logic Gates (II)
 AND and OR gates may have more than two inputs

2-input AND gate 2-input OR gate NOT gate

(inverter)

3-input AND gate 4-input OR gate

39
Input-Output for Gates
 Let’s draw the timing diagrams!
− Horizontal axis → time

− Vertical axis → logic 1 (high level), logic 0 (low level)

40
Notice
 HW1 will be posted on the KLMS webpage this Friday.
− Due date/time : next Friday, 11PM

− Please upload your solutions to the KLMS webpage before the due date/time

− Late submissions will not be accepted

41
Need Discussion or Help?
 [Mandatory] Video Lectures:
− Watch two video lectures by 11 PM this Friday.

 [Non-mandatory] Participation in Live Discussion (English):

− If you are interested in participating in the discussion:

− Send an email to the Head TA by the following Monday.

− We will have a live discussion session in English at 2:30 PM next Thursday.

 [Non-mandatory] Participation in Live Help Session (Korean):

− If you find it challenging to grasp the English lectures:

− Send an email to the PI by the following Monday.

− We will have a live help session in Korean at 3 PM next Thursday.

42