Transcript ECE 3110: Introduction to Digital Systems

ECE 3110: Introduction to Digital
Systems
Review #1
(Chapter 1 ,2)
Chapters 1,2 summary
 Analog<-->Digital: advantages, electronic aspects, software aspects,
digital design levels.
 IC: wafer, die, classifications, PLC,ASIC
 Positional number systems: binary, octal, decimal,hex
 Unsigned numbers: conversions,
addition/subtraction/multiplication/division
 Signed numbers: representations, conversions, addition/subtraction
 Sign extension
 Overflow
 Binary Codes for decimal numbers:BCD,2421,excess-3….
 Gray code
 Other codes
2
Digital Design Basics
Analog vs. Digital
Why we need digital?
Reproducibility, economy, programmability…
Digital Devices
Gates, FFs
Combinational, sequential circuits
3
Electronic and software aspect of digital
design
Digital abstraction
Noise Margin
specification
Examples of software tools
4
Integrated Circuits (IC)
 A collection of one or more gates fabricated on a
single silicon chip.
Wafer, die
 Small-scale integration (SSI): 1-20
DIP: dual in-line-pin package
Pin diagram, pinout
 MSI: 20-200 gates
 LSI: 200-200,000
VLSI: >100,000, 50million (1999)
5
Programmable Logic Device (PLD)
 ICs which Logic function can be programmed
after manufacture.
 2-level AND-OR gates using user-programmable
connections
PLAs: programmable Logic Arrarys.
PALs: programmable array logic devices
Programmable logic devices (PLDs)
 CPLD: complex PLD
 FPGA: Field-Programmable Gate Array
6
Application-Specific ICs (ASIC)
 Semi-custom IC: chips designed for a particular,
limited product/application
 Reducing chip count, size, power consumption
 Higher performance.
 NRE: nonrecurring engineering cost
Standard cells: library
Gate array: an IC with internal structure as an array of
gates, unspecified interconnection
7
Digital Design Levels
 Many representations of digital logic
 Device Physics and IC manufacturing
Moore’s Law [1965, Gordon Moore]:
 Transistor level --->Logic design, functional
building blocks
 Transistor level, Truth table, gate level logic,
prepackaged blocks, equations, HDL
8
Binary Representation
 The basis of all digital data is binary representation.
 Binary - means ‘two’
1, 0
True, False
Hot, Cold
On, Off
 We must be able to handle more than just values
for real world problems
1, 0, 56
True, False, Maybe
Hot, Cold, Warm, Cool
On, Off, Leaky
9
Positional Notation
Base
Radix
Weight
Radix 2, 8, 10,16
10
Unsigned numbers
 N binary digits (N bits) can represent unsigned integers from 0 to 2N-1.
 Conversions:
Hex <----->binary
Octal <-----> binary
 (padded with zero)
Any base <----->decimal
 Operations (binary):
addition/subtraction/multiplication/division
11
Hex to Binary, Binary to Hex
A2F16
= 1010 0010 11112
34516 =
0011 0100 01012
Binary to Hex is just the opposite, create groups of 4 bits
starting with least significant bits. If last group does not
have 4 bits, then pad with zeros for unsigned numbers.
10100012 = 0101 00012 = 5116
Padded with a zero
12
Conversion of Any Base to Decimal
Converting from ANY base to decimal is done by multiplying
each digit by its weight and summing.
Binary to Decimal
1011.112 = 1x23 + 0x22 + 1x21 + 1x20 + 1x2-1 + 1x2-2
= 8
+ 0 + 2 + 1 + 0.5 + 0.25
= 11.75
Hex to Decimal
A2F16 = 10x162 + 2x161 + 15x160
= 10 x 256
+ 2 x 16 + 15 x 1
= 2560 + 32 + 15 = 2607
13
Conversion of Decimal Integer To ANY Base
Divide Number N by base R until
quotient is 0.
Remainder at EACH step is a digit in
base R, from Least Significant digit to
Most significant digit.
14
Conversion of Decimal Integer To ANY Base
Example
Convert 53 to binary
53/2 =
26/2 =
13/2 =
6 /2 =
3/2 =
1/2 =
26,
13,
6 ,
3,
1,
0,
rem = 1
rem = 0
rem = 1
rem = 0
rem = 1
rem = 1
Least Significant Digit
Most Significant Digit
5310 = 1101012
= 1x25 + 1x24 + 0x23 + 1x22 + 0x21 + 1x20
= 32 + 16 + 0 + 4 + 0 + 1 = 53
15
Binary addition/subtraction rules
cin or bin
0
0
0
0
1
1
1
1
X
0
0
1
1
0
0
1
1
Y
0
1
0
1
0
1
0
1
Cout
0
0
0
1
0
1
1
1
s
0
1
1
0
1
0
0
1
Bout
0
1
0
0
1
1
0
1
d
0
1
1
0
1
0
0
1
16
Binary, Decimal addition
Decimal
34
+ 17
-----51
from LSD to MSD:
7+4 = 1; with carry out of 1
to next column
1 (carry) + 3 + 1 = 5.
answer = 51.
Binary
1010112
+ 0000012
--------------1011002
From LSB to MSB:
1+1 = 0, carry of 1
1 (carry)+1+0 = 0, carry of 1
1 (carry)+0 + 0 = 1, no carry
1 +0 = 1
0+0=0
1+0=1
answer = 1011002
17
Subtraction
Binary
Decimal
900
1002
- 001
------899
-
0-1 = 9; with borrow of 1
from next column
0 -1 (borrow) - 0 = 9, with
borrow of 1
9 - 1 (borrow) - 0 = 8.
Answer = 899.
0-1 = 1; with borrow of 1
from next column
0 -1 (borrow) - 0 = 1, with
borrow of 1
1 - 1 (borrow) - 0 = 0.
Answer = 0112.
0012
------0112
18
Representation of Negative Numbers
Signed-Magnitude Representation:
Negates a number by changing its sign.
Complement Number Systems: negates a
number by taking its complement.
Diminished Radix-Complement Representation
One’s-Complement
Radix-Complement Representation
Two’s-Complement
19
NOTE:
Fix number of digits
SM, 1’s complement, 2’s complement may be
different for NEGATIVE numbers, but
for positive numbers, the representations in
SM, 1’s complement, 2’s complement are the
SAME, equals to the unsigned binary
representation.
20
Ranges (N bits)
unsigned binary can represent unsigned integers from 0 to
2N-1.
SM can represent the signed integers
-(2(N-1) - 1) to + (2(N-1) - 1 )
1’s complement can represent the signed integers
-(2(N-1) - 1) to + (2(N-1) - 1 )
2’s complement can represent the signed integers
21
-2(N-1)
to + (2(N-1) - 1)
Sign extension
 For unsigned binary, Just add zeros to the left.
For signed binary (SM,1’s,2’s complement…):
 Take whatever the SIGN BIT is, and extend
it to the left.
22
Conversions for signed numbers
 Hex--->signed decimal
 Given a Hex number, and you are told to convert to a signed integer (either as
signed magnitude, 1s complement, 2s complement)
 Step 1: Determine the sign
 Step 2: determine magnitude
 Step 3: combine sign and magnitude
 Signed decimal ---->hex
 Step 1: Know what format you are converting to!!!
 Step 2: Ignore the sign, convert the magnitude of the number to binary.
 Step 3 (positive decimal number): If the decimal number was positive,
then you are finished no matter what the format is!
 Step 3 (negative decimal number): more work need to do.
23
Hex to Signed Decimal Conversion Rules
STEP 1: Determine the sign! If the Most Significant Bit is
zero, the sign is positive. If the MSB is one, the sign is
negative. This is true for ALL THREE representations: SM, 1s
complement, 2s complement.
STEP 2 (positive sign): If the sign is POSITIVE, then just
convert the hex value to decimal. The representation is the
same for SM, 1s complement, 2s complement.
STEP 2 (negative sign): If the sign is Negative, then need to
compute the magnitude of the number.
If the number is SM format, set Sign bit to Zero
If the number is 1s complement, complement each bit.
If the number is 2s complement, complement and add one.
STEP 3 : Just combine the sign and magnitude to get the result.
24
Signed Decimal to Hex conversion
Step 1: Know what format you are converting to!!! You must
know if you are converting the signed decimal to SM, 1s
complement, or 2s complement.
Step 2: Ignore the sign, convert the magnitude of the number to
binary.
Step 3 (positive decimal number): If the decimal number was
positive, then you are finished no matter what the format is!
Step 3 (negative decimal number): Need to do more if decimal
number was negative.
If converting to SM format, set Sign bit to One:
If converting to 1s complement, complement each bit.
25
If converting to 2s complement, complement each bit and add 1.
signed addition/subtraction
Two’s-complement
Addition rules
Subtraction rules
Overflow:
Out of range
Detecting unsigned overflow (carry out of MSB)
Detecting 2’s complement overflow
26
Detecting Two’s Complement Overflow
Two’s complement overflow occurs is:
Add two POSITIVE numbers and get a NEGATIVE result
Add two NEGATIVE numbers and get a POSITIVE result
We CANNOT get two’s complement overflow if I add a
NEGATIVE and a POSITIVE number together.
The Carry out of the Most Significant Bit means nothing if the
numbers are two’s complement numbers.
27
Codes
 Code: A set of n-bit strings in which different bit strings
represent different numbers or other things.
 Code word: a particular combination of n-bit values
 N-bit strings at most contain 2n valid code words.
 To represent 10 decimal digits, at least need 4 bits.
 Excessive ways to choose ten 4-bit words. Some
common codes:
 BCD: Binary-coded decimal, also known as 8421 code
 Excess-3
 2421…
 Codes can be used to represent numerical numbers,
nonnumeric texts, events/actions/states/conditions
28
How to construct Gray Code
Recursively
A 1-bit Gray Code has 2 code words, 0, 1
The first 2n code words of an (n+1)-bit Gray
code equal the code words of an n-bit Gray
Code, written in order with a leading 0
appended.
The last 2n code words equal the code words of
an n-bit Gray Code, but written in reverse order
with a leading 1 appended.
29
Another method to construct Gray
Code
The bits of an n-bit binary or Gray-code
word are numbered from right to left, from
0 to n-1
Bit i of a Gray code word is
0 if bits i and i+1 of the corresponding binary
code words are the same
1: otherwise
30