EEE 21

Switching Theory and

Digital Logic Design
Lecture 1
Analog and Digital Systems
Number Systems
19 June 2012

Analog vs. digital

Electronic signals may be

Continuous in amplitude and in time

Continuous in amplitude
and discrete in time

Discrete in amplitude and continuous

in time

Discrete in amplitude
and discrete in time
4 5 4 3 4 6 7 5 3 3 4 4 3

Analog vs. digital

Special case: system that only uses two voltages (HIGH

and LOW). For example, the high voltage may be
considered a logic 1 and the low voltage may be
considered a logic 0

1 0 0 1 0 0 0 1 1 0 1 1

Analog to Digital Conversion

1.

2.

Sample the signal at a

sampling frequency fS

Conversion

Analog signal

Quantize to specified
levels

sample

Digital signal
quantize

Anastacia B. Alvarez

EEE 21

Representing digital systems

Switches
Boolean algebra / equations
Truth tables
Gates / circuits
Block diagrams
Waveforms / timing diagrams
State diagrams
Hardware description languages

Example - switches

Switches connect two points under the control

of a signal

true if the control condition or event occurs

false if the event does not occur
opens or closes based on the state of the signal

Example - switches

IF {car running
AND [car in driveway
OR (car in garage AND NOT garage door closed)]}
THEN car can back out

Two main classes

Combinational logic the output at any given time is a

function solely of the combination of some or all of the
inputs at that given time
The value of any output variable z depends only on the
k
values of the input variables xi
xn-1
xn-2
x1
x0

zm-1
zm-2
z1
z0

System is memoryless, i.e., outputs do not depend on

any history of the inputs or previous state of the system

Two main classes

Sequential logic the output depends not only on the

current input, but also on the systems history.
In response to a given sequence of inputs, the system
also goes through a predictable sequence of states
Outputs

Inputs

Current
State

Combinational
Logic

Next
State

Memory

The current outputs as well as the next state of the

system, depend on the current inputs and current state

Sequential systems

Synchronous sequential circuit a reference signal

called the clock causes the system to change state at a
specific instant in time

Asynchronous sequential circuit the change in state is

not dictated by a reference signal

Number systems

Cardinality

The cardinality of a set S is a measure of the number of

elements of that set
Denoted by |S|

In number systems, we are interested in the set of symbols

D that represent the digits of that system
Binary number system
|D| = 2 D = {0,1}
Octal number system
|D| = 8 D = {0,1,2,3,4,5,6,7}
Hexadecimal number system
|D| = 16 D = {0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F}

Number representation

To represent k discrete quantities in a number system that

uses a set of symbols D to represent digits, you would
need at least n digits to represent each quantity such that
|D|n-1 k |D|n

Number representation

Example: How many digits would you need to be able to

represent at least 5 quantities using the binary system?
D = {0,1}, therefore |D| = 2
2n-1 5 2n
Answer: n = 3, that is, you would need at least 3 bits
(binary digits)

With n = 2, you can only form the numbers 00, 01, 10 and 11
With n = 3, you can form the numbers
000, 001, 010, 011, 100, 101, 110 and 111

Number representation

Example: Let's say you can use colored dots from D =

{RED,GREEN,BLUE} to tag 5 different items. What is the
minimum number of dots that you need on each item to
uniquely identify each one, assuming each item has to be
tagged with the same number of dots?
3n-1 5 3n
Answer: n = 2
How many different items can you tag using this scheme?
Can tag a maximum of 9 items:
BB, BG, BR, GB, GG, GR, RB, RG, GG

Number representation

A group of n digits (or labels) used to represent each

number (or item) is called an n-tuple

A tuple is an ordered list of objects, each of a specified

type. An ordered list of n objects is called an n-tuple

An n-tuple that uses a set of symbols D can represent

up to |D|n items.
For numbers, a system that uses n digits and the set
D as digit symbols can represent up to |D|n quantities

Number representation

Example: How many values can you represent using 4-bit

binary numbers?
Answer:
D = {0,1}, thus |D| = 2

The maximum number of values you can represent using

n = 4 bits (binary digits) is
|D|n = 24 = 16
These are 0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111,
1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111

Number representation

Easy way to remember this:

Given n digits in each number (or tuple) and k symbols
(k = |D|), the maximum number of unique quantities or
values that can be represented is given by
There are k possible symbols for each digit

A digit's
position
in the number

(k) (k) (k) (k)

There are n digit positions

Multiplying k with itself n times gives us kn

Number representation

Example: How many values can you represent using 4-bit

binary numbers?
D = {0,1}, thus |D| = k = 2

The maximum number of values you can represent using

4 bits (binary digits) is
Choice of {0,1}
for each digit

(2) (2) (2) (2)

= 24 = 16

These are 0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111,
1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111

Positional number systems

The number systems we use today are

positional, that is, each digit carries a
weight associated with its position
1,234.56 (in decimal)
=

1 x 1000 = 1 x 103 = 1000

+ 2 x 100 = 2 x 102 = 200
+ 3 x 10 = 3 x 101 = 30
+ 4 x 1 = 4 x 100 = 4
+ 5 x 0.1 = 5 x 10-1 = 0.5
+ 6 x 0.01 = 6 x 10-2 = 0.06

Positional number systems

Example of a non-positional system

Roman numeral MCMLXVII = 1967

In contrast, the current decimal (base-10)

system is positional
103 102 101 100 10-1 10-2 10-3

1234.567

Positional number systems

In general, for a number with

base or radix r,
n digits in the integer part
m digits in the fractional part
integer part

fractional part

an-1an-2...a1a0.a-1a-2...a-m =
radix point: separates
the integer from
fractional part

n-1

i
a
r
i

i = -m

Base conversion

Example: What quantity (in base-10) is

represented by the binary number 101110.0112?
101110.0112
1 x 2-3 = 1 x 1/23 = 1 x 1/8 = 1 x 0.125 = 0.125
1 x 2-2 = 1 x 1/22 = 1 x 1/4 = 1 x 0.25 = 0.25
0 x 2-1 = 0 x 1/21 = 0 x 1/2 = 0 x 0.5 = 0
0 x 20 = 0 x 1 = 0
1 x 21 = 1 x 2 = 2
1 x 22 = 1 x 4 = 4
1 x 23 = 1 x 8 = 8
0 x 24 = 0 x 16 = 0
1 x 25 = 1 x 32 = 32
= 46.37510

Base conversion

Previous procedure essentially describes

how to convert number in base r to the
same number in base 10

How to convert a number in base 10 to its

base r representation?

Multiplication by the radix

Example: 1234.567810

1234.567810 x 1010 = 12345.67810

1234.567810 / 1010 = 123.4567810

In general

Multiplying a base-r number by r moves the

radix point to the right
Dividing a base-r number by r moves the radix
point to the left

Base conversion

Converting a base-10 fraction to base-r

unknown

F = (.a-1a-2...a-m)r
(F)(r) = (a-1.a-2...a-m)r
(F)(r) = some integer + fraction F'
Therefore, (a-1)r = integer
Repeat using F' and (.a-2a-3...a-m)r.
Sometimes this process does not terminate...

Base conversion

Example: 0.710 = (?)2 up to 5 bits after the binary point

unknown

0.710 = (.a-1a-2a-3a-4a-5)2
(0.7)(2) = 1.4 = (a-1.a-2a-3a-4a-5...)2

a-1 = 1

(0.4)(2) = 0.8 = (a-2.a-3a-4a-5...)2

a-2 = 0

(0.8)(2) = 1.6 = (a-3.a-4a-5...)2

a-3 = 1

(0.6)(2) = 1.2 = (a-4.a-5...)2

a-4 = 1

(0.2)(2) = 0.4 = (.a-5...)2

a-5 = 0

0.710 (0.10110)2

Base conversion

Converting an integer in base-10 to base-r

unknown

D = (an-1an-2...a1a0)r
D/r = (an-1an-2...a1.a0)r
D/r = some integer D' + (remainder)/r
Now (.a0)r = a0/r = remainder/r
Therefore

a0= remainder

Base conversion

Repeat with the integer from previous step

D' = (an-1an-2...a1)r
D'/r = (an-1an-2...a2.a1)r
D'/r = some integer D'' + (remainder)/r
Similarly, (.a1)r = a1/r = remainder/r
Therefore

a1= remainder

Base conversion

Example: Convert 1234 to its hex equivalent

Recall 16 hex digit symbols
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F}
Helps to know how many digits in the answer...
2 hex digits? (16)(16) = 162 = 256 < 1234
3 hex digits? (16)(16)(16) = 163 = 4096 > 1234
so n = 3 digits in the answer
1234/16 = 77 remainder 2

a0 = 2

77/16 = 4 remainder 13

a1 = D

4/16 = 0 remainder 4

a2 = 4

So a2a1a0 = 4D216 = 0x4D2 = 4D2H.

Base conversion

DON'T memorize the procedure!

Easy to forget if you need to multiply or divide, or

collect the remainders or integer parts, etc...

DO learn the basic concepts

The strategy is divide and conquer

Divide a number into integer and fractional parts

Isolate and compute (conquer) each unknown digit
either by multiplying or dividing by the radix
Multiplying by the radix moves the radix point to the
... (left or right? -- try it with an example like
123.456 x 10...)
Work with a representation like (.a-1a-2a-3a-4a-5)

Binary arithmetic

Addition
0+0=0
0+1=1
1+0=1
1 + 1 = 0 carry 1

111
1
(carry)
00011001
+ 00101101
01000110

Binary arithmetic

Multiplication
Each bit in the multiplier (starting from the least significant
bit or LSB) is multiplied to each bit of the multiplicand in
much the same way that decimal numbers are multiplied.

Codes
Other ways of representing quantities or objects

Binary coded decimal: each decimal digit is

represented by a 4-bit code. The resulting
codeword cannot be manipulated in the same
manner as a binary number
4510 0100 0101

Codes
Other ways of representing quantities or objects

Reflected code: patented in 1947 by Bell Labs

researcher Frank Gray (thus also called Gray
code)
For reflected binary Gray code, two successive
codewords differ in only one bit position
2-bit Gray code
00
01
11
10

Mirror images (reflection)

Codes
3-bit Gray code
Start with 2-bit Gray code
000
001
011
010
110 Reflect
111
101
100

Codes
Error-correcting and error-detecting codes

Parity check code

Even parity:

11010111

Odd parity:

01010111
parity bit

sum of all bits (including the

parity bit) is even.
sum of all bits (including the
parity bit) is odd.

Codes
Character codes: (Example) ASCII (American
Standard Code for Information Interchange)

Specifies correspondence between a set of bit patterns

and the glyphs (i.e. symbols) of a written language
Binary
100 0000
100 0001
100 0010
100 0011
100 0100
100 0101
100 0110
100 0111
100 1000

Oct
100
101
102
103
104
105
106
107
110

Dec
64
65
66
67
68
69
70
71
72

Hex
40
41
42
43
44
45
46
47
48

Glyph
@
A
B
C
D
E
F
G
H

[Wikipedia]