UNIT 1 – Introduction: Number Systems

and Conversion

This chapter in the book includes:

Objectives
Study Guide
1.1 Digital Systems and Switching Circuits
1.2 Number Systems and Conversion
1.3 Binary Arithmetic
1.4 Representation of Negative Numbers
1.5 Binary Codes
Problems

Spring 2022
Objectives

Topics introduced in this chapter:

• Difference between Analog and Digital System
• Difference between Combinational and Sequential Circuits
• Binary number and digital systems
• Number systems and Conversion
• Add, Subtract, Multiply, Divide Positive Binary Numbers
• 1’s Complement, 2’s Complement for Negative binary number

• BCD code, 6-3-1-1 code, excess-3 code

1.1 Digital Systems and Switching Circuits
1.1 Digital Systems and Switching Circuits

Digital systems

computation, data processing, control, communication, measurement..

Analog – Continuous
- Natural Phenomena (Pressure, Temperature, Speed…)
- It is difficult to realize and process using electronics
Digital – Discrete
- Binary Digit è Signal Processing with “Bit” unit
- It is easy to realize and process using electronics
- High performance due to Integrated Circuit (IC) Technology
 Binary Digit?
Binary

• Two values(0, 1)
• Each digit is called a “bit”

Advantages with Binary Numbers

• Number representation with only two values (0,1)

• Can be implemented with simple electronic devices
(ex: Voltage High(1), Low(0) ; Switch On (1) Off(0)…)
 Switching Circuit

• Combinational Circuit :
• Outputs depend on only present inputs, not on past inputs
• Sequential Circuit:
• Outputs depend on both present inputs and past inputs (i.e. sequence)
• Have “memory” elements

Discrete number Figure 1-1: Switching circuit Discrete number

Combinational & Sequential Circuits in this Class
UNIT1 – Introduction Number Systems and Conversion
UNIT2 – Boolean Algebra
UNIT3 – Boolean Algebra (continued)
UNIT4 – Applications of Boolean Algebra

UNIT5 – Karnaugh Maps

UNIT6 – Quine-McCluskey Method

UNIT7 – Multi-Level Gates Circuits NAND and NOR Gates

UNIT8 – Combinational Circuit Design and Simulation using Gates
UNIT9 – MUXs, Decoders, and PLDs

UNIT11 – Latches and Flip-Flops

UNIT12 – Registers and Counters
UNIT13 – Analysis of Clocked Sequential Circuits

UNIT14 – Derivation of State Graphs and Tables

UNIT15 – Reduction of State Tables, State Assignment (optional)
 1.2 Number Systems and Conversion

Decimal: 953 .7810 = 9 ´10 2 + 5 ´101 + 3 ´10 0 + 7 ´10 -1 + 8 ´10 -2

Binary: 1011.112 = 1´ 23 + 0 ´ 2 2 + 1´ 21 + 1´ 2 0 + 1´ 2 -1 + 1´ 2 -2
1 1 3
= 8 + 0 + 2 +1+ + = 11 = 11.7510
2 4 4

Radix(=Base): N = (a4 a3a2 a1a0 .a-1a-2 a-3 ) R

N à expanded as
Here, “R” is = a4 ´ R 4 + a3 ´ R 3 + a2 ´ R 2 + a1 ´ R1 + a0 ´ R 0 a power series for R
a positive integer
+ a-1 ´ R -1 + a-2 ´ R -2 + a-3 ´ R -3

3
Octal-Decimal: 147.38 = 1´ 82 + 4 ´ 81 + 7 ´ 80 + 3 ´ 8-1 = 64 + 32 + 7 +
8
= 103.37510
Hexa-Decimal: A2 F16 = 10 ´16 2 + 2 ´161 + 15 ´16 0 = 2560 + 32 + 15 = 260710

0,1,2,3,…,9, A, B, C, D, E, F

à The above examples show how to convert a Base-R number into a decimal number (N)
 1.2 Number Systems and Conversion

How to convert a decimal number (N) into a Base-R number (anan-1…a2a1a0)

N = (an an -1 × × × a2 a1a0 ) R = an R n + an -1 R n -1 + × × × + a2 R 2 + a1 R1 + a0
unknown

N
= an R n -1 + an -1R n -2 + ××× + a2 R1 + a1 = Q1 , remainder a0
R
Q1
= an R n -2 + an -1R n -3 + ××× + a3R1 + a2 = Q2 , remainder a1
R
Q2
= an R n -3 + an -1 R n - 4 + × × × + a3 = Q3 , remainder a2
R
. . .
. . .
. . .
(n+1)th division remaninder an
1.2 Number Systems and Conversion

Example: Decimal to Binary Conversion N = 53, R = 2

2 53

2 26 rem. = 1 = a0
2 13 rem. = 0 = a1

2 6 rem. = 1 = a2 5310 = 1101012

2 3 rem. = 0 = a3

2 1 rem. = 1 = a4

0 rem. = 1 = a5
 1.2 Number Systems and Conversion

Conversion of a decimal fraction (F) to Base-R (e.g. 0.625)

F = (.a-1a- 2 a-3 × × × a-m ) R = a-1 R -1 + a-2 R -2 + a-3 R -3 + × × × + a-m R - m

FR = a-1 + a- 2 R -1 + a-3 R -2 + × × × + a- m R - m +1 = a-1 + F1 Each multiplication

leaves a decimal fraction Fi
F1 R = a- 2 + a-3 R -1 + × × × + a-m R - m + 2 = a-2 + F2
with an integer a-i representing
F2 R = a-3 + × × × + a- m R - m +3 = a-3 + F3 each digit in the base R.

Example: F = .625 F1 = .250 F2 = .500

´ 2 ´ 2 ´ 2 .62510 = .1012
1.250 0.500 1.000
( a-1 = 1) (a- 2 = 0) ( a-3 = 1)
 1.2 Number Systems and Conversion

Example: Convert 0.7 to binary

.7
2
(1).4
2
( 0).8
2
(1).6
2
(1).2
2
( 0).4 Once 0.4 appears in the process, then the sequence of 8-6-2-4 is
2 generated repeatedly
( 0).8 0.710 = 0.10110 0110 0110 × × ×2
 1.2 Number Systems and Conversion

Example: Convert 231.34 to base-7 3

231.34 = 2 ´16 + 3 ´ 4 + 1 + = 45.7510
4
One arbitrary base to another
arbitrary base:
7 45 .75
Base Ra 7 6 rem.3 7
à Base 10 (i.e. decimal) (5).25 45.7510 = 63.5151× × ×7
0 rem.6
à Base Rb 7
(1).75
7
(5).25
7
(1).75
Conversion of Binary to Hexa-decimal

4 digits of base 2
1001101.0101112 = 0100 1101 . 0101 1100 = 4D.5C16
à 1 digit of base 16
 1.2 Number Systems and Conversion

EXAMPLES : Conversion of Binary to Octal, Hexa-decimal

l (101011010111)2
=( )8, octal

l (10111011.11)2
=( )8, octal

l (1010111100100101)2
=( )16, Hexadecimal

l (1111101000.011)2
=( )16, Hexadecimal
1.3 Binary Arithmetic

Addition
0+0=0
0 +1 = 1
1+ 0 =1
1 + 1 = 0 and carry 1 to the next column

Example: 1111 carries

1101 + 1011 1310 = 1101
1110 = 1011
11000 = 2410
 1.3 Binary Arithmetic

column 2 column 1
Subtraction with Decimal Numbers

205
- 18
205 - 18 = [2 ´ 10 2 + 0 ´ 101 + 5 ´ 10 0 ] 187
-[ 1´ 101 + 8 ´ 10 0 ]
borrow from column 1
= [2 ´ 10 2 + (0 - 1) ´ 101 + (10 + 5) ´ 10 0 ]
-[ 1´ 101 + 8 ´ 10 0 ]
borrow from column 2
= [(2 - 1) ´ 10 2 + (10 + 0 - 1) ´ 101 + 15 ´ 10 0 ]
-[ 1) ´ 101 + 8 ´ 10 0 ]
= [1´ 10 2 + 8 ´ 101 + 7 ´ 10 0 ] = 187
1.3 Binary Arithmetic

Subtraction
0-0 = 0
0 - 1 = 1 and borrow 1 from the next column
1- 0 =1
1 -1 = 0

Example:

1 (indicates 1111 borrows 111 borrows

a borrow
11101 10000 111001
from the
- 10011 3rd column) - 11 - 1011
1010 1101 101110
 1.3 Binary Arithmetic

Multiply: 13 x11(10) 1101

Multiplication 0´0 = 0 ´ 1011
0 ´1 = 0 1101
1´ 0 = 0 1101
1´ 1 = 1 0000
1101
10001111 = 14310
1111 multiplicand
1101 multiplier
1111 first partial product
0000 second partial product
Addition in each step
(01111) sum of first two partial products
to avoid carries
1111 third partial product
greater than 1
(1001011) sum after adding third partial product
1111 fourth partial product
11000011 final product (sum after adding fourth partial product)
1.3 Binary Arithmetic

Division Example: 14510 by 1110 (i.e. 100100012 by 10112)

Begin from high digits

(1) Compare 1001 and 1011
1101 à 1001 < 1011
1011 10010001 à Moves one place
à quotient 0
1011 (2) Compare 10010 and 1011
(1) and (2)
1110 à 10010 > 1011
1011 à quotient 1
(3) (3) Compare 1110 and 1011
1101 à 1110 > 1011
1011 à quotient 1
.
10
(4) .
.
(4) Done with a remainder of 10
1.4 Representation of Negative Numbers

(1) So far, binary numbers have been all positive (unsigned).

(2) Let’s consider negative binary numbers.

These can be represented by using:

§ Signed Magnitude

§ 1’s Complement

§ 2’s Complement
1.4 Representation of Negative Numbers
bn – 1 b1 b0

Magnitude

(a) Unsigned number

bn – 1 bn – 2 b1 b0

Magnitude
Sign
0 denotes +
1 denotes – (b) Signed number (i.e. signed magnitude)
1.4 Representation of Negative Numbers

Table 1-1: Signed Binary Integers (word length n = 4)

Notes:
Expressions by 2’s and 1’s complements can also allow
a “unique” set of binary numbers, signifying negative numbers.
1.4 Representation of Negative Numbers

1’s Complement System N = (2 n - 1) - N

à identical with switching 0 to 1 and 1 to 0

Example: N = 010101 2 n - 1 = 111111

N = 010101
N = 101010

Positive numbers in 1’s Complement System

à identical with positive integers

 1.4 Representation of Negative Numbers
2’s Complement System

à -N is represented by N * = 2 - N
n

Negative 2' s Complement

negative number
number Positive number
-1 1111 16 - 1
-2 1110 16 - 2
-3 1101 16 - 3
Example: -4 1100
n=4 . Note :
-5 1011 .
( -0) = 0* = 24 - 0
-6 1010 .
= 16 = 100002
-7 1001
-8 1000 16 - 8
1.4 Representation of Negative Numbers

Positive numbers in 2’s Complement System

(identical with those of 1’s Complement System)

Positive 2' s Complement
number Positive number
0 0000
+1 0001
+2 0010
+3 0011
+4 0100
+5 0101
+6 0110
+7 0111
1.4 Representation of Negative Numbers

2’s complement can be easily obtained by (1’s complement + 1)

N * = 2n - N
N * = 2 n - N = (2 n - 1 - N ) + 1 = N + 1
N = (2 n - 1) - N
1.4 Representation of Negative Number

Addition of 2’s complement numbers

+3 0011
Case 1
+4 0100
+7 0111 (correct answer)
Case 2 +5 0101
+6 0110
1011 wrong answer because of overflow (+11 requires
5 bits including sign)
Case 3 +5 0101
-6 1010
1111 (correct answer)
Case 4 -5 1011
+6 0110
(1)0001 correct answer when the carry from the sign bit
is ignored (this is not an overflow)
1.4 Representation of Negative Numbers

Addition of 2’s complement numbers

Case 5 -3 1101
-4 1100
-7 (1)1001 correct answer when the last carry is ignored
(this is not an overflow)
Case 6

-5 1011
-6 1010
(1)0101 wrong answer because of overflow
(-11 requires 5 bits including sign)

(i.e. -11 is out of range in a system of n=4)

1.4 Representation of Negative Numbers

The last carry is not discarded

Addition of 1’s complement numbers à added as an ‘end-around carry’

Case 3 +5 0101
-6 1001
-1 1110 (correct answer)

Case 4 -5 1010
+6 0110
(1) 0000
1 (end-around carry)
0001 (correct answer, no overflow)

Case 5 -3 1100
-4 1011
(1) 0111
1 (end-around carry)
1000 (correct answer, no overflow)
 1.4 Representation of Negative Numbers

Addition of 1’s complement numbers

Case 6 -5 1010
-6 1001
(1) 0011
1 (end-around carry)
0100 (wrong answer because of overflow) (i.e. out of range)

Proof End-around carry means that

2n is replaced with 1
Case 4: - A + B (where B > A)
A + B = (2 n - 1 - A) + B = 2 n + ( B - A) - 1 =B–A

Case 5: - A - B (where A + B < 2n -1 )

A + B = (2n - 1 - A) + (2n - 1 - B) = 2 n + [2 n - 1 - ( A + B)] - 1 = - ( A + B)
1.4 Representation of Negative Numbers

Examples: Addition of 1’s Complement Numbers

11110100 ( -11)
11101011 + ( -20)
(1) 11011111
1 (end-around carry)
11100000 = -31

Addition of 2’s Complement Numbers

11111000 ( -8)
00010011 + 19
(1)00001011 = +11

(discard last carry)

1.5 Binary Codes
9 3 7.2 5 Example of
BCD code
representation
1001 0011 0111 . 0010 0101
8-4-2-1
Decimal 6-3-1-1 Excess-3 2-out-of-5 Gray
Code
Digit Code Code Code Code
(BCD)
0 0000 0000 0011 00011 0000
1 0001 0001 0100 00101 0001
2 0010 0011 0101 00110 0011
3 0011 0100 0110 01001 0010
4 0100 0101 0111 01010 0110
5 0101 0111 1000 01100 1110
6 0110 1000 1001 10001 1010
7 0111 1001 1010 10010 1011
8 1000 1011 1011 10100 1001
9 1001 1100 1100 11000 1000

Requirement for codes: Each decimal digit on the left column should be
represented by a distinct combination of binary digits
1.5 Binary Codes

6-3-1-1 Code

N = w3a3 + w2 a2 + w1a1 + w0 a0

e.g. 1011 in 6-3-1-1 code N = 6 ×1 + 3 × 0 + 1 ×1 + 1 ×1 = 8

Decimal digit value
ASCII Code*

1010011 1110100 1100001 1110010 1110100

S t a r t

* The ASCII (American Standard Code for Information Interchange) code is

a 7-bit code that has 27 different code combinations as shown in Table 1-3.