Transcript Chapter 1 - PPT - Mano & Kime

SYEN 3330
Digital Systems
Chapter 1
SYEN 3330 Digital Systems
Jung H. Kim Chapter 1
1
Digital System
Takes a set of discrete information inputs and discrete
internal information (system state) and generates a set of
discrete information outputs.
Discrete
Inputs
Discrete
Information
Processing
System
Discrete
Outputs
System State
SYEN 3330 DIGITAL SYSTEMS
Chapter 1 2
Types of Systems
No state present
Combinatorial Logic System

Output = Function(Input)

State present
State updated at discrete times:

=> Synchronous Sequential System
State updated at any time:

=>Asynchronous Sequential System.
SYEN 3330 DIGITAL SYSTEMS
Chapter 1 3
Digital System Example:
A Digital Counter (e. g., odometer):
UP
RESET
0
0
1
3
5
6
4
Inputs: Count Up, Reset
Outputs: Visual Display
"Value" of stored digit
State:
Synchronous or Asynchronous?
SYEN 3330 DIGITAL SYSTEMS
Chapter 1 4
A Digital Computer Example
Synchronous or
Asynchronous?
Inputs:
Keyboard,
mouse, modem,
microphone
SYEN 3330 DIGITAL SYSTEMS
Outputs: CRT,
LCD, modem,
speakers
Chapter 1 5
Signals
A collection of information variables
mapped to some physical quantity.
For digital systems, the quantities take on
discrete values. Two level, or binary
values are the most prevalent values in
digital systems.
The binary values are represented
abstractly by digits 0 and 1.
SYEN 3330 DIGITAL SYSTEMS
Chapter 1 6
Physical Signal Example - Voltage
Threshold
Region
SYEN 3330 DIGITAL SYSTEMS
Chapter 1 7
Threshold in the News!
• Punched = 1
• Not punched = 0
• What about the rest?
SYEN 3330 DIGITAL SYSTEMS
Chapter 1 8
Other Physical Signals
• What are other physical signals
represented by 1 and 0?
 CPU Voltage
 Disk Magnetic Field Direction
 CD Surface Pits/Light
 Dynamic RAM Electrical Charge
SYEN 3330 DIGITAL SYSTEMS
Chapter 1 9
Signal Examples Over Time
Analog
Asynchronous
(Time)
Synchronous
SYEN 3330 DIGITAL SYSTEMS
Chapter 1 10
Number Systems
Decimal Numbers
5634 => 5 x 103
+ 6 x 102
+ 3 x 101
+ 4 x 100
SYEN 3330 DIGITAL SYSTEMS
= 5,000
= 600
= 30
=
4
5,634
Chapter 1 11
Powers of Ten
Exponent
6
5
4
3
2
1
0
-1
-2
-3
-4
SYEN 3330 DIGITAL SYSTEMS
Value
1,000,000
100,000
10,000
1,000
100
10
1
1/10
=
0.1
(Definition)
1/100 = 0.01
1/1000 = 0.001
1/10000 = 0.0001
Chapter 1 12
Positive Powers of 2
Exponent Value
Exponent
Value
0
1
11
2,048
1
2
12
4,096
2
4
13
8,192
3
8
14
16,384
4
16
15
32,768
5
32
16
65,536
6
64
17
131,072
7
128
18
262,144
8
256
19
524,288
9
512
20
1,048,576
10
1024
21
2,097,152
SYEN 3330 DIGITAL SYSTEMS
Chapter 1 13
Important Powers of 2
10
2
20
2
30
2
is referred to as Kilo, called "K"
is referred to as Mega, called "M"
is referred to as Giga, called "G"
SYEN 3330 DIGITAL SYSTEMS
Chapter 1 14
Number Digits
• Decimal number digits are 0 through
9
• Binary number digits are 0 through
1
• Base (radix) r number digits are 0
through r - 1
SYEN 3330 DIGITAL SYSTEMS
Chapter 1 15
Converting Binary to Decimal
• To convert to decimal, use decimal arithmetic
to sum the weighted powers of two:
4 = 16
1
x
2
• 110102 =>
+ 1 x 23 = 8
+ 0 x 22 = 0
+ 1 x 21 = 2
+ 0__________
x 20 = 0
= 2610
SYEN 3330 DIGITAL SYSTEMS
Chapter 1 16
Converting Decimal to Binary
• Method 1 (Method 2, Repeated Division Later)
 Subtract the largest power of 2 that gives a positive
result and record the power.
 Repeat subtracting from the prior result until the
remainder is zero.
 Place 1’s in the positions in the binary result
corresponding to the powers recorded; in all other
positions place 0’s.
• Example: 62510 – 29 = 625 – 512 = 113 => 9
113 – 26 = 113 – 64 = 49 => 6
49 – 25 = 49 – 32 = 17 => 5
17 – 24 = 17 – 16 = 1 => 4
=
0 => 0
1 – 20 = 1 – 1
Result
from the listed powers: 10011100012Chapter 1
SYEN 3330 DIGITAL SYSTEMS
17
Commonly Occurring Bases
Name
Radix
Digits
Binary
2
0,1
Octal
8
0,1,2,3,4,5,6,7
Decimal
10
0,1,2,3,4,5,6,7,8,9
Hexadecimal
16
0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F
SYEN 3330 DIGITAL SYSTEMS
Chapter 1 18
Numbers in Different Bases
Decimal
(Base 10)
00
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
SYEN 3330 DIGITAL SYSTEMS
Binary
(Base 2)
00000
00001
00010
00011
00100
00101
00110
00111
01000
01001
01010
01011
01100
01101
01110
01111
10000
Octal
Hexa-decimal
(Base 8)
(Base 16)
00
00
01
01
02
02
03
03
04
04
05
05
06
06
07
07
10
08
11
09
12
0A
13
0B
14
0C
15
0D
16
0E
17
0F
20
10
Chapter 1 19
General Base Conversion
Given a number of radix r of with:
"n" integer digits, an-1  a0
and
"m" fraction digits a-1  a-m
written as:
an-1an-2  a2a1a0 • a-1a-2  a-m
has value:

i  n 1
i 0
 
ai  r 
i
j  1
j
a

r
j m j

(Number)r =
(Integer Portion) + (Fraction Portion)
SYEN 3330 DIGITAL SYSTEMS
Chapter 1 20
Radix 10 Example
2,345  6710 => a3a2a1a0  a-1a-2 =
2*1000 + 3*100 +4*10 + 5 + 6*(1/10) + 7*(1/100)
(Integer part)
+
(Fraction part)
Term
Actual
Product
Values
a3*r3 =
2 * 1000
=
2000
a2*r2 =
3 * 100
=
300
a1*r1 =
4 * 10
=
40
a0*r0 =
5*1
=
5
a-1*r-1 =
6 * 01
=
06
a-2*r-2 =
7 * 001
=
007
Sum =>
SYEN 3330 DIGITAL SYSTEMS
2,34567
Chapter 1 21
Conversion Between Bases
To convert from one base to another:
1) Convert the Integer Portion
2) Convert the Fraction Portion
3) Join the two with a radix point
SYEN 3330 DIGITAL SYSTEMS
Chapter 1 22
Conversion Details
To Convert the Integer Portion:
Repeatedly divide the number by the radix you want to
convert to and save the remainders. The new radix digits
are the remainders in reverse order of computation.
To Convert the Fraction Portion:
Repeatedly multiply the fraction by the radix and save the
integer digits that result. The new radix fraction digits are
the integer digits in computed order.
SYEN 3330 DIGITAL SYSTEMS
Chapter 1 23
Convert 46.687510 To Base 2
Convert 46 to Base 2
Convert 0.6875 to Base 2
Join them together with
the radix point.
SYEN 3330 DIGITAL SYSTEMS
Chapter 1 24
Convert Integer 46 To Base 2
Step 1
Step 2
Step 3
Step 4
Step 5
Step 6
46 / 2 = 23 remainder = 0
23 / 2 = 11 remainder = 1
11 / 2 = 5 remainder = 1
5 / 2 = 2 remainder = 1
2 / 2 = 1 remainder = 0
1 / 2 = 0 remainder = 1
Result
4610 = 23 => 1011102
SYEN 3330 DIGITAL SYSTEMS
Chapter 1 25
Convert Fraction 0.687510 to Base 2
Step 1
Step 2
Step 3
Step 4
Step 5
Result
0.6875 * 2 = 1.3750 integer = 1
0.3750 * 2 = 0.7500 integer = 0
0.7500 * 2 = 1.5000 integer = 1
0.5000 * 2 = 1.0000 integer = 1
0.0000 * 2 = 0.0000 integer = 0
0.687510 => 0.101102
SYEN 3330 DIGITAL SYSTEMS
Chapter 1 26
Join Integer and Fraction
Integer: 4610 = 1011102
Fraction: 0.687510 = 0.101102
Join two parts:
46687510 = 101110101102
SYEN 3330 DIGITAL SYSTEMS
Chapter 1 27
Checking the Conversion
To convert back, use weighted coefficients
in the base you are converting to.
Example:
1011102 = 1*32 + 0*16 +1*8 +1*4
+ 1*2 +0*1
= 32 + 8 + 4 + 2
= 4610
0.101102 = 1/2 + 1/8 + 1/16
= 05000 + 0.1250 + 0.0625
= 0687510
SYEN 3330 DIGITAL SYSTEMS
Chapter 1 28
Octal to Binary and Back
Octal to Binary:
Restate the octal as three binary digits;
Start at the radix point and go both ways,
padding with zeros as needed.
Binary to Octal:
Group the binary digits into three bit groups
starting at the radix point and going both ways,
padding with zeros as needed.
Convert each group of three bits to an octal
digit.
SYEN 3330 DIGITAL SYSTEMS
Chapter 1
29
Octal to Hexadecimal via Binary
Use groups of four bits and
convert as above to/from
hexadecimal digits.
Example: Octal to Binary to Hexadecimal
6 3 5  1 7 68
110|011|101  001|111|1102
Regroup and Pad:
0001|1001|1101  0011|1111|2
1 9
D  3
F 16
SYEN 3330 DIGITAL SYSTEMS
Chapter 1 30
A Final Conversion Note
You can use other radix arithmetic if you
are careful:
Example: Convert 1011102 to Base 10
using binary arithmetic:
0 r
100 

0100
1010
Step 1 101110 
 100 r
0110
1010
Converted Digits are 01002 | 01102
Step 2
or
SYEN 3330 DIGITAL SYSTEMS
4610
Chapter 1 31
Binary Numbers and Coding
Number of representable elements:
Given n digits in radix r, there are
rn distinct elements that can be represented.
Examples:
For r = 10, n = 2 (2 decimal digits):
We can represent 102 or 100 elements
( 00, 01, 02, .... , 10, 11, 12, ...., 19, 20, ....., 95, 96, 97,
98, 99)
For r = 2, n = 3 (3 binary digits):
We can represent 23 or 8 elements
(000, 001, 010, 011, 100, 101, 110, 111)
SYEN 3330 DIGITAL SYSTEMS
Chapter 1 32
Enumerating elements
To enumerate all rn elements of n-digit, radix r
numbers we do the following:
1). Initialize all digits to some fixed element (say
"0")
2). Repeat (rn -1 times)
Begin
Add one to the previous element
and write down the new number.
End Repeat;
Note: addition of one is performed modulo(rn) in
base r, ignoring the carry.
SYEN 3330 DIGITAL SYSTEMS
Chapter 1 33
Example: Radix 2, 3 digits
Step 1: Write 000 as an element of the set.
Repeat (23 -1 = 7 times)
Step 2: Add 001 to get 001; write it down.
Step 3: Add 001 to get 010; write it down.
Step 4: Add 001 to get 011; write it down.
Step 5: Add 001 to get 100; write it down.
Step 6: Add 001 to get 101; write it down.
Step 7: Add 001 to get 110; write it down.
Step 8: Add 001 to get 111; write it down.
End;
SYEN 3330 DIGITAL SYSTEMS
Chapter 1 34
Representing Numeric Information
We have complete freedom of choice to assign numeric
meanings to the rn distinct patterns of n radix r digits.
Some examples are:
 Unsigned integers
 Signed integers
 Floating point numbers
It is highly desirable that the representation chosen can:
1.
2.
Represent the expected range of data, and
Allow simple, straightforward computation under
common arithmetic operations.
SYEN 3330 DIGITAL SYSTEMS
Chapter 1 35
Binary Coding
Given n binary digits (called bits), a Binary Coding is
a mapping from a subset of the 2n binary numbers
to some set of represented elements.
Example:
A binary coding
for the seven
colors of the
rainbow
SYEN 3330 DIGITAL SYSTEMS
Binary Number
000
001
010
011
100
101
110
111
Color
Red
Orange
Yellow
Green
(Not mapped)
Blue
Indigo
Violet
Chapter 1 36
Number of Bits Required
Given M elements to be represented by a binary code,
the minimum number of bits, n, needed satisfies the
following relationships:
2n  M and
M  2(n-1)
Example: How many bits are required to represent
decimal digits with a binary code?
M = 10, therefore n = 4 since:
3
2 = 8 is < 10
and
4
2 =16 is  10
SYEN 3330 DIGITAL SYSTEMS
Chapter 1 37
Min. and Max. Digits Required
Given n digits in radix r, there are rn distinct
elements that can be represented.
Conversely, it takes at least n digits in radix r to
represent rn distinct elements.
 You can use more than n digits if you want!
Example:
You can represent 4 elements in radix 2 with 2
digits:
(00, 01, 10, 11).
Four base 2 digits might also be used:
(0001, 0010, 0100, 1000).
This code is called a "one hot" code.
SYEN 3330 DIGITAL SYSTEMS
Chapter 1 38
Binary Codes for Decimal Digits
There are over 8,000 ways that you can chose 10 elements
from the 16 binary numbers of 4 bits. A few are useful:
Decimal
8,4,2,1
0
1
2
3
4
5
6
7
8
9
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
SYEN 3330 DIGITAL SYSTEMS
Excess3 8,4,-2,-1
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
0000
0111
0110
0101
0100
1011
1010
1001
1000
1111
Chapter 1 39
Binary Coded Decimal (BCD)
Binary Coded Decimal or 8,4,2,1 Code.
This code is the simplest, most intuitive binary
code for decimal digits and uses the same
weights as a binary number, but only encodes
the first ten values from 0 to 9.
Examples: 1001 is 8 + 1 = 9
0011 is 2 + 1 = 3
0100 is 4
1010 is an illegal code.
SYEN 3330 DIGITAL SYSTEMS
Chapter 1 40
Other Decimal Codes
The Excess-3 Code adds binary 0011 to the BCD
code.
The BCD (8,4, 2, 1) Code,
and the (8,4,-2,-1) Code are examples of weighted
codes.
Each bit has a "weight" associated with it and you can
compute the decimal value by adding the weights
where a 1 exists in the code-word.
Example: 1111 in (8,4,-2,-1) is 8 + 4 + (-2) + (-1) = 9
SYEN 3330 DIGITAL SYSTEMS
Chapter 1 41
Warning: Conversion or Coding?
DO NOT mix up CONVERSION of a decimal
number to a binary number with CODING a
decimal number with a BINARY CODE.
1310 = 11012
(This is CONVERSION)
13  00010011 (This is CODING)
SYEN 3330 DIGITAL SYSTEMS
Chapter 1 42
Binary Addition
Given two binary digits (X,Y), a carry in (Z) we get the
following sum (S) and carry (C):
Carry in (Z) of 0:
Carry in (Z) of 1:
SYEN 3330 DIGITAL SYSTEMS
Z
X
+Y
0
0
+0
0
0
+1
0
1
+0
0
1
+1
CS
00
01
01
10
Z
X
+Y
1
0
+0
1
0
+1
1
1
+0
1
1
+1
CS
01
10
10
11
Chapter 1 43
Binary Addition (Extended)
• Extending this to multiple digits:
Carries
Augend
Addend
Sum
0000 00 10110 0
01100 10110
+10001 +10111
11101 1 011 01
Note: The underlined “0” is a Carry-In
to the least digit.
SYEN 3330 DIGITAL SYSTEMS
Chapter 1 44
Binary Subtraction
• Given two binary digits (X,Y), a borrow in (Z) we
get the following difference (S) and borrow (B):
0
0
0
0
• Borrow in (Z) of 0: Z
X
-Y
BS
• Borrow in (Z) of 1: Z
X
-Y
BS
SYEN 3330 DIGITAL SYSTEMS
0
-0
00
1
0
-0
11
0
-1
11
1
0
-1
10
1
1
-0
-1
01 00
1
1
1
1
-0
-1
0Chapter
0 1 451 1
Binary Subtraction (Extended)
• Extending this to multiple digits:
Borrows
0000 00 0 0 0110
Minuend
10110 10110
Subtrahend - 10010 - 10011
0010 0 00011
Difference
Note: If the Subtrahend is larger than the Minuend,
interchange and append a – to the result. The
underlined “0” is a Borrow-In to the least digit.
SYEN 3330 DIGITAL SYSTEMS
Chapter 1 46
Binary Multiplication
The binary multiplication table is simple:
00=0 | 10=0 | 01=0 | 11=1
Extending multiplication to multiple digits:
Multiplicand
Multiplier
Partial Products
Product
SYEN 3330 DIGITAL SYSTEMS
1011
x 101
1011
0000 1011 - 110111
Chapter 1 47
BCD Arithmetic
Given a BDC code, we use binary arithmetic to add the digits:
8
1000 Eight
+5
+0101 Plus 5
13
1101 is 13 (> 9)
Note that the result is MORE THAN 9, so must be two digits!
To correct the digit, subtract 10 by adding 6 modulo 16.
8
1000 Eight
+5
+0101 Plus 5
13
1101 is 13 (> 9)
+0110 so add 6
carry = 1 0011 leaving 3 + cy
0001 | 0011 Final answer (two digits)
If the digit sum is > 9, add one to the next significant digit.
SYEN 3330 DIGITAL SYSTEMS
Chapter 1 48
BCD Addition Example
• Add 1897BCD to 2905BCD
1
0
1
1
0001 1000 1001 0111
+ 0010 1001 0000 0101
0100 10010 1010 1100
+ 0000 + 0110 + 0110 + 0110
0100 1000 0000 0010
SYEN 3330 DIGITAL SYSTEMS
Chapter 1 49
Error-Detection Codes
Redundancy (e.g. extra information) can be added to a binary
code word for the purpose of detecting and correcting errors.
One simple form of redundancy is parity where an extra bit is
appended onto the code word to make the number of bits
come out odd or even. Parity can be used to detect all singlebit errors and some multiple-bit errors.
We say a code word has even parity if the number of ones in
the code word is even.
We say a code word has odd parity if the number of ones in
the code word is odd.
SYEN 3330 DIGITAL SYSTEMS
Chapter 1 50
3-Bit Parity Code Example
Even Parity
Odd Parity
Message - Parity Message - Parity
000 - 0
000 - 1
001 - 1
001 - 0
010 - 1
010 - 0
011 - 0
011 - 1
100 - 1
100 - 0
101 - 0
101 - 1
110 - 0
110 - 1
111 - 1
111 - 0
The binary code "1111" has even parity and the
binary code "1110" has odd parity. Both could be
used to represent data.
SYEN 3330 DIGITAL SYSTEMS
Chapter 1 51
ASCII Character Codes
American Standard Code for Information
Interchange
This code is the most popular code used to represent
information sent as character-based data. It uses 7-bits to
represent:
94 Graphic printing characters.
34 Non-printing characters
Some non-printing characters are used for text format (e.g. BS
= Backspace, CR = carriage return)
Other non-printing characters are used for record marking
and flow control (e.g. STX and ETX start and end text areas).
SYEN 3330 DIGITAL SYSTEMS
Chapter 1 52
ASCII Properties
(Refer to Table 1-4 in the book)
ASCII has some interesting properties:
Digits 0 to 9 consecutive and span Hexadecimal values
3016 to 3916.
Upper case A-Z consecutive and span 4116 to 5A16.
Lower case a-z consecutive and span 6116 to 7A16 .
Lower to upper case translation (and vice versa) occurs
by complementing bit 6.
Delete (DEL) is all bits set-- a carryover from when
punched paper tape was used to store messages.
Punching all holes erased a mistake.
SYEN 3330 DIGITAL SYSTEMS
Chapter 1 53
Other Character Codes
 EBCDIC "Eb See Dick" is a similar
code used mostly by large IBM
mainframes.
 UNICODE extends ASCII to 65,536
universal characters codes

For encoding characters in
world languages
SYEN 3330 DIGITAL SYSTEMS
Chapter 1 54
Other Character Codes
• UNICODE extends ASCII to 65,536
universal characters codes




For encoding characters in world languages
Available in many modern applications
2 byte (16-bit) code words
See Supplement in Chapter 1 on Companion
Website http://www.prenhall.com/mano if
you are interested
SYEN 3330 DIGITAL SYSTEMS
Chapter 1 55