Chapter 1

Digital Systems and Binary Numbers

Dr.Ahmed Awad
 Overview

° The design of computers

• It all starts with numbers
• Building circuits
• Building computing machines

° Digital systems
° Understanding decimal numbers
° Binary and octal numbers
• The basis of computers!

° Conversion between different number systems

 Digital Systems

° Digital age.
° Applications:
• Communications.
• Business transactions.
• Medical treatment
• ….
• Digital computers.

° Most devices have embedded special purpose

computers.
° Key feature of digital computers is generality and
flexibility to be programmed.
 Digital Computer Systems

° Digital systems consider discrete amounts of data.

° Examples
• 26 letters in the alphabet
• 10 decimal digits

° Larger quantities can be built from discrete values:

• Words made of letters
• Numbers made of decimal digits (e.g. 239875.32)

° Computers operate on binary values (0 and 1)

° Easy to represent binary values electrically
• Voltages and currents.
• Can be implemented using circuits
• Create the building blocks of modern computers
 What is a Digital System?

° A system that manipulates discrete elements of

information represented internally using binary
numbering system.
° Binary system can be implemented easily with
electronic components.
° Discrete quantities of information can be obtained by:
• The nature of the data being processed.
• Quantized from a continuous process (require ADC)
Architecture of a Digital Computer
 Why Digital Circuits?

° Most digital devices are programmable.

° Complex functions are produced with low cost with the
advances in integrated circuit technology.
° Equipments built with digital integrated circuits can
perform at a speed of hundreds of millions of
operations per second.
° Digital circuits can be made to operate with extreme
reliability using error-correction codes.
 Understanding Decimal Numbers

° Decimal numbers are made of decimal digits:

(0,1,2,3,4,5,6,7,8,9)
° But how many items does a decimal number
represent?
• 8653 = 8x103 + 6x102 + 5x101 + 3x100

° What about fractions?

• 97654.35 = 9x104 + 7x103 + 6x102 + 5x101 + 4x100 + 3x10-1 + 5x10-2
• In formal notation -> (97654.35)10

° Why do we use 10 digits, anyway?

 Understanding Octal Numbers

° Octal numbers are made of octal digits:

(0,1,2,3,4,5,6,7)
° How many items does an octal number represent?
• (4536)8 = 4x83 + 5x82 + 3x81 + 6x80 = (2398)10

° What about fractions?

• (465.27)8 = 4x82 + 6x81 + 5x80 + 2x8-1 + 7x8-2

° Octal numbers don’t use digits 8 or 9

° Who would use octal number, anyway?
 Understanding Binary Numbers

° Binary numbers are made of binary digits (bits):

• 0 and 1

° How many items does an binary number represent?

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

° What about fractions?

• (110.10)2 = 1x22 + 1x21 + 0x20 + 1x2-1 + 0x2-2

° Groups of eight bits are called a byte

• (11001001) 2

° Groups of four bits are called a nibble.

• (1101) 2
The Growth of Binary Numbers
n 2n n 2n
0 20=1 8 28=256
1 21=2 9 29=512

2 22=4 10 210=1024

3 23=8 11 211=2048

4 24=16 12 212=4096

5 25=32 20 220=1M
Mega

6 26=64 30 230=1G
Giga

7 27=128 40 240=1T Tera

Why Use Binary Numbers?

° Easy to represent 0 and 1 using

electrical values.
° Possible to tolerate noise.
° Easy to transmit data
° Easy to build binary circuits.

AND Gate

1
0
0
 Conversion Between Number Bases

Octal(base 8)

Decimal(base 10) Binary(base 2)

Hexadecimal
(base16)
° Learn to convert between bases.
° Already demonstrated how to convert
from binary to decimal.
° Hexadecimal described in next
lecture.
 Convert an Integer from Decimal to Another Base

For each digit position:

1. Divide decimal number by the base (e.g. 2)
2. The remainder is the lowest-order digit
3. Repeat first two steps until no divisor remains.

Example for (13)10:

Integer Remainder Coefficient
Quotient
13/2 = 6 + ½ a0 = 1
6/2 = 3 + 0 a1 = 0
3/2 = 1 + ½ a2 = 1
1/2 = 0 + ½ a3 = 1

Answer (13)10 = (a3 a2 a1 a0)2 = (1101)2

 Convert an Fraction from Decimal to Another Base

For each digit position:

1. Multiply decimal number by the base (e.g. 2)
2. The integer is the highest-order digit
3. Repeat first two steps until fraction becomes
zero.
Example for (0.625)10:
Integer Fraction Coefficient

0.625 x 2 = 1 + 0.25 a-1 = 1

0.250 x 2 = 0 + 0.50 a -2 = 0
0.500 x 2 = 1 + 0 a-3 = 1

Answer (0.625)10 = (0.a-1 a-2 a-3 )2 = (0.101)2

Binary Addition

° Binary addition is very simple.

° This is best shown in an example of adding two
binary numbers…

1 11 1 1 1 carries
11 1 1 0 1
+ 1 0 1 1 1
---------------------
1 0 1 0 1 0 0
Binary Subtraction

° We can also perform subtraction (with borrows in place of

carries).
° Let’s subtract (10111)2 from (1001101)2…

1 10 borrows
0 10 10 0 0 10

1 0
0 1 1 0 1
- 1 0 1 1 1
------------------------
1 1 0 1 1 0
 Binary Multiplication

° Binary multiplication is much the same as decimal

multiplication, except that the multiplication
operations are much simpler…

10 1 1 1
X 1 0 1 0
-----------------------
0 0 0 0 0
1 0 1 1 1
0 0 0 0 0
1 0 1 1 1
-----------------------
1 1 1 0 0 1 1 0
 Convert an Integer from Decimal to Octal

For each digit position:

1. Divide decimal number by the base (8)
2. The remainder is the lowest-order digit
3. Repeat first two steps until no divisor remains.

Example for (175)10:

Integer Remainder Coefficient
Quotient
175/8 = 21 + 7/8 a0 = 7
21/8 = 2 + 5/8 a1 = 5
2/8 = 0 + 2/8 a2 = 2

Answer (175)10 = (a2 a1 a0)2 = (257)8

 Convert an Fraction from Decimal to Octal

For each digit position:

1. Multiply decimal number by the base (e.g. 8)
2. The integer is the highest-order digit
3. Repeat first two steps until fraction becomes
zero.
Example for (0.3125)10:
Integer Fraction Coefficient

0.3125 x 8 = 2 + 5 a-1 = 2
0.5000 x 8 = 4 + 0 a -2 = 4

Answer (0.3125)10 = (0.24)8

° Hexadecimal numbers
• Related to binary and octal numbers

° Conversion between hexadecimal, octal and binary

° Value ranges of numbers
° Representing positive and negative numbers
° Creating the complement of a number
• Make a positive number negative (and vice versa)

° Why binary?
 Understanding Binary Numbers

° Binary numbers are made of binary digits (bits):

• 0 and 1

° How many items does an binary number represent?

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

° What about fractions?

• (110.10)2 = 1x22 + 1x21 + 0x20 + 1x2-1 + 0x2-2

° Groups of eight bits are called a byte

• (11001001) 2

° Groups of four bits are called a nibble.

• (1101) 2
 Understanding Hexadecimal Numbers

° Hexadecimal numbers are made of 16 digits:

• (0,1,2,3,4,5,6,7,8,9,A, B, C, D, E, F)

° How many items does an hex number represent?

• (3A9F)16 = 3x163 + 10x162 + 9x161 + 15x160 = 1499910

° What about fractions?

• (2D3.5)16 = 2x162 + 13x161 + 3x160 + 5x16-1 = 723.312510

° Note that each hexadecimal digit can be represented

with four bits.
• (1110) 2 = (E)16

° Groups of four bits are called a nibble.

• (1110) 2
Putting It All Together

° Binary, octal, and

hexadecimal similar
° Easy to build circuits to
operate on these
representations
° Possible to convert
between the three
formats
Converting Between Base 16 and Base 2

3A9F16 = 0011 1010 1001 11112

3 A 9 F

° Conversion is easy!
 Determine 4-bit value for each hex digit
° Note that there are 24 = 16 different values of four
bits
° Easier to read and write in hexadecimal.
° Representations are equivalent!
Converting Between Base 16 and Base 8

3A9F16 = 0011 1010 1001 11112

3 A 9 F

352378 = 011 101 010 011 1112

3 5 2 3 7

1. Convert from Base 16 to Base 2

2. Regroup bits into groups of three starting from right
3. Ignore leading zeros
4. Each group of three bits forms an octal digit.
 How To Represent Signed Numbers

• Plus and minus sign used for decimal

numbers: 25 (or +25), -16, etc.
• For computers, desirable to represent
everything as bits.
• Three types of signed binary number
representations: signed magnitude, 1’s
complement, 2’s complement.
• In each case: left-most bit indicates sign:
positive (0) or negative (1).

Consider signed magnitude:

000011002 = 1210 100011002 = -1210

Sign bit Magnitude Sign bit Magnitude

 One’s Complement Representation

• The one’s complement of a binary number

involves inverting all bits.
• 1’s comp of 00110011 is 11001100
• 1’s comp of 10101010 is 01010101
• For an n bit number N the 1’s complement is
(2n-1) – N.
• Called diminished radix complement by Mano
since 1’s complement for base (radix 2).
• To find negative of 1’s complement number
take the 1’s complement.
000011002 = 1210 111100112 = -1210

Sign bit Magnitude Sign bit Magnitude

 Two’s Complement Representation

• The two’s complement of a binary number

involves inverting all bits and adding 1.
• 2’s comp of 00110011 is 11001101
• 2’s comp of 10101010 is 01010110
• For an n bit number N the 2’s complement is
(2n-1) – N + 1.
• Called radix complement by Mano since 2’s
complement for base (radix 2).
• To find negative of 2’s complement number
take the 2’s complement.
000011002 = 1210 111101002 = -1210

Sign bit Magnitude Sign bit Magnitude

Two’s Complement Shortcuts
° Algorithm 1 – Simply complement each bit and
then add 1 to the result.
• Finding the 2’s complement of (01100101)2 and of its 2’s
complement…
N = 01100101 [N] = 10011011
10011010 01100100
+ 1 + 1
--------------- ---------------
10011011 01100101

° Algorithm 2 – Starting with the least significant bit,

copy all of the bits up to and including the first 1
bit and then complementing the remaining bits.
• N =01100101
[N] =10011011
Finite Number Representation

° Machines that use 2’s complement arithmetic can

represent integers in the range
-2n-1 <= N <= 2n-1-1
where n is the number of bits available for
representing N. Note that 2n-1-1 = (011..11)2
and –2n-1 = (100..00)2
o For 2’s complement more negative numbers than
positive.
o For 1’s complement two representations for zero.
o For an n bit number in base (radix) z there are zn
different unsigned values.
(0, 1, …zn-1)
Finite Number Representation
Subtraction with Complements

M-N
Subtraction with Complements
Subtraction with Complements
Arithmetic Addition
Arithmetic Addition
 2’s Complement Addition
° Using 2’s complement numbers, adding numbers
is easy.
° For example, suppose we wish to add +(1100)2
and +(0001)2.
° Let’s compute (12)10 + (1)10.
• (12)10 = +(1100)2 = 011002 in 2’s comp.
• (1)10 = +(0001)2 = 000012 in 2’s comp. 0 1 1 0 0
Add + 0 0 0 0 1
Step 1: Add binary numbers --------------
Step 2: Ignore carry bit Final 0 0 1 1 0 1
Result

Ignore
 2’s Complement Subtraction
° Using 2’s complement numbers, follow steps for
subtraction
° For example, suppose we wish to subtract
+(0001)2 from +(1100)2.
0 1 1 0 0
° Let’s compute (12)10 - (1)10. - 0 0 0 0 1
• (12)10 = +(1100)2 = 011002 in 2’s comp. --------------
• (-1)10 = -(0001)2 = 111112 in 2’s comp.
2’s comp
0 1 1 0 0
Step 1: Take 2’s complement of 2nd operand Add + 1 1 1 1 1
Step 2: Add binary numbers --------------
Step 3: Ignore carry bit Final
Result 1 0 1 0 1 1

Ignore
Carry
2’s Complement Subtraction: Example #2

° Let’s compute (13)10 – (5)10.

• (13)10 = +(1101)2 = (01101)2
• (-5)10 = -(0101)2 = (11011)2

° Adding these two 5-bit codes…

0 1 1 0 1
carry + 1 1 0 1 1
--------------
1 0 1 0 0 0
° Discarding the carry bit, the sign bit is seen to be
zero, indicating a correct result. Indeed,
(01000)2 = +(1000)2 = +(8)10.
2’s Complement Subtraction: Example #3

° Let’s compute (5)10 – (12)10.

• (-12)10 = -(1100)2 = (10100)2
• (5)10 = +(0101)2 = (00101)2

° Adding these two 5-bit codes…

0 0 1 0 1
+ 1 0 1 0 0
--------------
1 1 0 0 1
° Here, there is no carry bit and the sign bit is 1.
This indicates a negative result, which is what we
expect. (11001)2 = -(7)10.
 ° Binary Codes

° Digital systems use signals that have two distinct

values and circuit elements that have two states.
° A binary number of n digits may be represented
by n circuit elements, each having an output
signal equivalent to 0 or 1.
° Digital systems represent and manipulate not only
binary numbers, but also other discrete elements
of information encoded with bits.
° n-bit binary code is a group of n bits that assumes
up to 2^n distinct combinations of 1’s and 0’s
° No maximum number of bits.
° Binary coded decimal
° Gray codes for binary numbers
° ASCII characters
° Moving towards hardware
• Storing data
• Processing data
 Binary Coded Decimal
Digit BCD Digit BCD
Code Code
0 0000 5 0101
1 0001 6 0110
2 0010 7 0111
3 0011 8 1000
4 0100 9 1001

° Binary coded decimal (BCD) represents each decimal

digit with four bits
• Ex. 0011 0010 1001 = 32910
3 2 9

° This is NOT the same as 0011001010012

° Why do this? Because people think in decimal.
 BCD Addition
° If the binary sum is greater than or equal to 1010,
we add 0110 to obtain the correct BCD sum and a
carry.
Putting It All Together

° BCD not very efficient

° Used in early
computers (40s, 50s)
° Used to encode
numbers for seven-
segment displays.
° Easier to read?
Other Decimal Codes
Gray Code
Digit Binary Gray
Code ° Gray code is not a number
0 0000 0000 system.
1 0001 0001 • It is an alternate way to represent
2 0010 0011 four bit data
3 0011 0010
4 0100 0110 ° Only one bit changes from
5 0101 0111
one decimal digit to the next
6 0110 0101 ° Useful for reducing errors in
7 0111 0100 communication.
8 1000 1100
9 1001 1101 ° Can be scaled to larger
numbers.
10 1010 1111
11 1011 1110
12 1100 1010
13 1101 1011
14 1110 1001
15 1111 1000
 ASCII Code
° American Standard Code for Information
Interchange
° ASCII is a 7-bit code, frequently used with an 8th bit
for error detection (more about that in a bit).
ASCII Codes and Data Transmission

° ASCII Codes
° A – Z (26 codes), a – z (26 codes)
° 0-9 (10 codes), others (@#$%^&*….)
° Complete listing in Mano text
° Transmission susceptible to noise
° Typical transmission rates (1500 Kbps, 56.6 Kbps)
° How to keep data transmission accurate?
 Binary Data Storage

• Binary cells store individual bits of data

• Multiple cells form a register.
• Data in registers can indicate different values
• Hex (decimal)
• BCD
• ASCII

0 0 1 0 1 0 1 1

Binary Cell
Register Transfer

° Data can move from register to register.

° Digital logic used to process data
° We will learn to design this logic

Register A Register B

Digital Logic
Circuits

Register C
 Transfer of Information

° Data input at keyboard

° Shifted into place
° Stored in memory

NOTE: Data input in ASCII

Building a Computer
° We need processing
° We need storage
° We need communication

° You will learn to use and

design these components.
Binary Logic
Binary Logic Truth Table & Logic Gates
Binary Logic Gates

° Electronic circuits that operate on one or more

input signals to produce an output signal.
° Voltages are interpreted to be either of two
recognizable values, 0 or 1.
Binary Logic Gates