Transcript (N) 2

CHAPTER 1: Number
Systems and Codes
Introduction
Digital circuits, processing discrete information,
are found in an astonishingly wide rang of electronic
systems. They have provided system designers with
more functions contained in less space, thereby
improving system reliability and increasing speed.
Digital systems operate on numbers that represent some
real logical or arithmetic function. It is the designer’s
task to establish the relationship between the numbers
and the task being performed. This chapter develops
the use of numbers and how they represent real world
conditions in digital system.
1.1 Digital and Analog: Basic
Concepts
 Continuous: Without breaks, smooth, no
interruptions; a range of values forming a
line or curve without gaps or discontinuities
 Discrete: Broken down into pieces;
opposite of continuous; a single part or
point that can unambiguously be defined
1.1 Digital and Analog: Basic
Concepts
1.1 Digital and Analog: Basic
Concepts
 Analog: Refer to something that is analogous, has a likeness,
or is similar to something else. Analog electronic signals
are continuous, whereas voltage(电压), current(电流), or
some other electrical parameter is used to represent a physical
parameter. For instance, voltage changes may represent
changes in temperature.
 Digital: Refer to digits or numbers in any radix; digital
electronics usually involves binary or base-2 number systems.
Digital signals are discrete, not continuous
1.1 Digital and Analog: Basic
Concepts
Vc(0)=0V, Initial voltage at t0 is 0V
Vc=Va(1-e-t/RC)
1.1 Digital and Analog: Basic
Concepts
Discrete voltage values for time interval
(a) Analog representation
(b)
Discrete representation
1.1 Digital and Analog: Basic
Concepts
Analog volt
meter
Digital volt
meter
Analog VS Digital
Analog VS Digital
 Digital Circuits over Analog Ones:
-- Reproducibility of Results
-- Ease of design, Flexibility and Functionality
-- Programmability
-- Speed, Economy and Steadily Advancing Technology
1.2 Digital Systems Overview
1.2 Digital Systems Overview
SSI (small-scale integration) contains
0-9 gates
MSI (medium-scale integration)
contains 10-99gates
LSI (large-scale integration) contains
100 or more gates
VLSI (very large-scale integration )
contains more than 1000 gates
1.2 Digital Systems Overview
1.2 Digital Systems Overview
1.2 Digital Systems Overview
1.2 Digital Systems Overview
1.2 Digital Systems Overview
1.2 Digital Systems Overview
1.2 Digital Systems Overview
1.2 Digital Systems Overview
1.2 Digital Systems Overview
1.2 Digital Systems Overview
1.2 Digital Systems Overview
1.2 Digital Systems Overview
Kangaroo TV
ARM926EJ-s
Palm Pre
Amazon Kindle2 e-book reader
ARM Powered
Freescale
Freescale i.MX21 Processor
ARM Cortex A8
ARM9 and ARM7 Processors
Texas Instruments OMAP3430
ARM11 Processor
Zoran Corporation Quatro 4230 Processor
APSI M-480 PMP
HP mv5150 Media Vault Pro
ARM11 Processor
TI OMAP2530 Dual-Core CPU
Konica Minolta Magicolor 1650EN Printer
Nintendo DSi
Dell Latitude E4200 Notebook
ARM9 Processorr
ARM Cortex M3
Marvell Orion (88F5182-A2) Processor
iRiver Wave Home (Multimedia Communicator)
ARM Powered
Broadcom BCM5880
TeleNav Shotgun
Zeebo Console
Parrot : Zikmu Wireless speakers by Philppe Starck
ARM926 Processor
ARM11 Processor and ARM9 Processor
Qualcomm
ARM926 Processor
SiRF Atlas III
Samsung LN40A750 40-Inch 1080p DLNA LCD HDTV
ARM Powered
1.3 Introduction to Number System
 Digital systems represented information in a discrete form, and
Number systems provide the means of quantifying information
for processing by digital system.
– Positional Number Systems
– Number system conversion
– Binary Codes
– Arithmetic
Number Systems - Decimal
 “base” 10 (radix is 10)
 10 digits: 0..9
536.15910=(5×102)+(3×101)+(6×100)+(1×10-1)+(5×10-2)+(9×10-3)
Radix or Base
Weight
Number Systems – Decimal (cont.)
 In general, a decimal number with n digits to the left
of the decimal point, and m digits to the right of the
decimal point is written as:
An-1 An-2 … A1 A0 . A-1 A-2 … A-m+1 A-m
where Ai is a coefficient between 0..9,
and i denotes the weight (=10i) of Ai.
Number Systems – General
 “base” r (radix r)
 r digits
 N = An-1 ×r n-1 + An-2 × r n-2 +… + A1 × r + A0 +
A-1 × r -1 + A-2 × r -2 +… + A-m × r -m
Most
Significant
Bit (MSB)
Least
Significant
Bit (LSB)
Positional Number Systems
Let r=radix or base of a number system;
Let c=character from the character set of the radix;
Let N=number to be represented in radix;
Let n=the number of digits in the integer portion of N
Let m=the number of digits in the fractional portion of N
(N)r=(cn-1rn-1+cn-2rn-2+…+c1r1+c0r0+c-1r-1+c-2r-2+…+c-mr-m)
n=1
(N)r=
∑ ciri
i=-m
Number Systems – General (cont.)
 e.g. let r = 6
(312.4)6 = 3 × 62 + 1 × 61 + 1 × 60 + 4 × 6-1
= (116.66)10
 Conversion from n-radix (any system with
radix n) to decimal follows similar process
as above
Number Systems (cont.)
 Most common number systems for computers:
 Binary (r = 2)
 Octal (r = 8)
 Hexadecimal (r = 16)
Binary Numbers--Base 2
 Computers represent all data as “strings of bits”,
each bit being either 0 or 1
 “base” 2, with 2 digits: 0 and 1
e.g.
(101101.10)2 = 1×25 + 0×24 + 1×23 + 1×22 + 0×21 +
1×20 + 1×2-1 + 0×2-2
(in decimal) = 32 + 0 + 8 + 4 + 0 + 1 + ½ + 0
= (45.5)10
Powers of two
Memorize at least through 216
Octal Numbers--Base 8
 “base” 8
 with 8 digits: 0..7
Eg.
231.258=2×82 + 3×81+1×80+2×8-1+5×8-2
(in decimal) =153.32812510
Hexadecimal Numbers--Base 16
 r = 16
 Digits (convention): 0..9, A, B, C, D, E, F
 A=10, B=11, … , F = 15
Hexadecimal
A
B
C
D
E
F
Decimal
10
11
12
13
14
15
e.g1.
(3FB)16 = 3×162 + 15×161 + 11×160
(in decimal) = 768 + 240 + 11
= (1019)10
e.g2.
A59C.3A16 = (A×163)+(5×162)+(9×161)+(C×160)+(3×16-1)+(A×162)
1.3.2 Number System Conversion
Decimal，binary,octal,and
hexadecimal number
Binary  Octal
(011 010 101 000 . 111 101 011 100)2
(3
2
5
0 . 7
5
3
4 )8
E.g. Convert the binary number
010011110111.1101010102to octal
Solution
010,011,110,111.110,101,0102=2367.6528
Binary  Hex
( 0110 1010 1000 . 1111 0101 1100 )2
( 6
A
8 .
F
5
C )16
E.g. Convert the binary number
010011110111.1101010102to hexadecimal
Solution
0100,1111,0111.1101,0101,00002=4F7.D5016
1.3.2 Number System Conversion
 hexadecimal and octal to Binary Conversion
E.g. Convert the numbers F37A.B216,735.58 to binary
Solution F37A.B2=1111,0011,0111,1010.1011,00102
735.58 =111,011,101.1012
Practice problem:
convert 367.2368to binary then
hexadecimal
Solution 367.2368=011,110,111.010,011,1102
011,110,111.010,011,1102=0,1111,0111.0100,1111,02=F7.4F16
1.3.2 Number System Conversion
Binary to decimal Conversion
11001.0112
=(1×24)+(1×23)+(0×22)+(0×21)+(1×20)
+(0× 2-1)+(1×2-2)+(1×2-3)
=16+8+0+0+1+0+0.25+0.125
=25.37510
1.3.2 Number System Conversion
decimal to Binary Conversion
•Successive Division Radix Conversion
E.g. Convert 11910
to binary
Solution
11910=11101112
59
2 119
118
1
2
2
29
59
58
1
14
29
28
1
7
2 14
14
0
2
1 （LSB）
2
1
2
1
0
3
7
6
1
1
1
3
2
1
1
0
1
0
1
1 （MSB）
1.3.2 Number System Conversion
Decimal to Binary Conversion
•Fractional Radix Conversion, Successive Multiplication
E.g. Convert .7510 to binary
Solution
Multiply .75 by 2 (.75)2=1.5
1(MSB)
Multiply .75 by 2
(.5)2=1.0
1
Multiply .75 by 2
(0)2=0.0
0(LSB)
.7510=.110=(1)2-1+(1)2-2
1.3.2 Number System Conversion
 E.g. Convert 95.062510 to binary（con.）
Solution
First, convert the integer part of the decimal number by successive division
1.Devide 95 by 2
2.Devide 47 by 2
3.Devide 23 by 2
4.Devide 11 by 2
47
2 95
94
1
23
2 47
46
1
11
2 23
22
1
5
2 11
10
1
1 (LSB)
2
5
4
1
1
1
1
2
2
0
0
0
1
0
1
1 (MSB)
5.Devide 5 by 2
6.Devide 2 by 2
7.Devide 1 by 2
1
1
2
2
2
9510=1·26+0·25+1·24+1·23+1·22
+1·21+1·20
1.3.2 Number System Conversion
 E.g. Convert 95.062510 to binary（con.）
Second, convert the fraction
1. (.625)2=0.125
0 (MSB)
2.
(.125)2=0.25
0
3.
(.25)2=0.5
0
4.
(.5)2=1.0
1
(LSB)
.062510=.00012
95.062510=1011111.00012
1.3.2 Number System Conversion
Decimal to Any Radix
The conversion of decimal numbers to any other radix applies the
successive division and successive multiplication algorithms
e.g. Convert 23.62510 to octal (base 8)
Solution
Convert the integer portion by
successive division
2
1.Divide 23 by 8 8 23
16
7
2.Divide 2 by 8
8
2310=278
0
2
0
2
7 (LSB)
Convert te fraction portion
by successive multiplication
(.625)8=5.00
5 (MSB)
.62510=.58
2 (MSB)
23.62510=27.58
1.3.2 Number System Conversion
Any Radix to Decimal
e.g. Convert 324.25 to decimal
Solution
3·52+2·51+4·50+2·5-1
=3(25)+2(5)+4(1)+2(1/5)
=75+10+4+2/5
=89.410
1.3.2 Number System Conversion
Practice problem:
1. Convert 345.26 to decimal
2.
Solution:
Convert 34.810 to base 5
1.
137.333……10
2.
114.45
1.3.3 Binary Codes
Natural Binary Coded Decimal
Decimal to natural BCD
e.g.
Convert 9275.610 into BCD
Solution:
9=1001
2=0010
7=0111
5=0101
6=0110
9275.610=1001，0010，0111，0101.0110 in BCD
1.3.3 Binary Codes
Binary Codes (Weighted)
1.3.3 Binary Codes
 Unit Distance Code: Gray code
Timing diagram illustrating potential error when two bits
change sat the same time
1.3.3 Binary Codes
 Unit Distance Code: Gray code
Three-bit and
Four-bit Gray
code
1.3.3 Binary Codes
 Alphanumeric codes
ASCII (American standard
code for information
interchange)
EBCDIC (extended
BCD interchange code)
Partial listing of seven-bit ASCII and eightbit EBCDIC codes in hexadecimal
1.3.3 Binary Codes
 Signed Number Binary
Binary signed magnitude
number convention uses the
most significant bit position
to indicate sign and the
remaining lesser significant
bits to represent magnitude
Sign magnitude
2s complement
1s complement
Sign magnitude and complement
Signed Number Representation
 Signed Magnitude Method
N = (s,an-1 ... a0.a-1 ... a-m)rsm,
where s = 0 if N is positive and s = r -1 otherwise.
– E.g.
N = -(15)10
In binary:
N = -(15)10 = -(1111)2 = (1, 1111)2sm
In decimal:
N = -(15)10 = (9, 15)10sm
 Complementary Number Systems
– Radix complements (r's complements)
[N]r = rn - (N)r
where n is the number of digits in (N)r.
– Diminished radix complements (r-1’s complements)
[N]r-1 = rn - (N) r - 1
Radix Complement Number Systems
 2's complement of (N)2 = (101001)2
[N]2 = 26 - (101001)2 = (1000000)2 - (101001)2 = (010111)2
(N)2 + [N]2 = (101001)2 + (010111)2 = (1000000)2
If we discard the carry, (N)2 + [N]2 = 0.
Hence, [N]2 can be used to represent -(N)2.
[ [N]2 ]2 = [(010111)2]2 = (1000000)2 - (010111)2 = (101001)2 = (N)2.
 2's complement of (N)2 = (1010)2 for n = 6
[N]2 = (1000000)2 - (1010)2 = (110110)2.
 10's complement of (N)10 = (72092)10
[N]10 = (100000)10 - (72092)10 = (27908)10.
Radix Complement Number Systems
 Algorithm： Find [N]r given (N)r .
1.Copy the digits of N, beginning with the LSB and
proceeding toward the MSB until the first nonzero digit, aj,
has been reached
2.Replace aj with r - aj.
3.Replace each remaining digit aj , of N by (r - 1) - aj until the
MSB has been replaced.
– Example: 10's complement of (56700)10 is (43300)10
– Example: 2's complement of (10100)2 is (01100)2.
– Example: 2’s complement of N = (10110)2 for n = 8.
• Put three zeros in the MSB position and apply algorithm
• N = 00010110
• [N]2 = (11101010)2
Radix Complement Number Systems
 Algorithm2： Find [N]r given (N)r .
First replace each digit, ak , of (N)r by (r - 1) - ak and then
add 1 to the resultant.
 Example: Find 2’s complement of N = (01100101)2 .
N = 01100101
10011010 Complement the bits
+1 Add 1
[N]2 = (10011011)2
 Example: Find 10’s complement of N = (40960)10
N = 40960
59039 Complement the bits
+1 Add 1
[N]2 = (59040)10
Radix Complement Number Systems
 2's complement number system
– Positive number :
• N = +(an-2, ..., a0)2 = (0, an-2, ..., a0)2cns,
where
0  N  2n 1 .1
– Negative number:
• N = (an-1, an-2, ..., a0)2
• -N = [an-1, an-2, ..., a0]2 (two's complement of N),
where
1  N  2.n 1
– Example: Two's complement number system representation of ± (N)2
when (N)2 = (1011001)2 for n = 8:
• +(N)2 = (0, 1011001)2cns
• -(N)2 = [+(N)2]2 = [0, 1011001]2 = (1, 0100111)2cns
Diminished Radix Complement
Number systems
 Diminished radix complement [N]r-1 of a number (N)r is:
[N]r-1 = rn - (N)r - 1
 One’s complement (r = 2):
[N]2-1 = 2n - (N)2 - 1
 Example: One’s complement of (01100101)2
[N]2-1 = 28 - (01100101)2 - 1
= (100000000)2 - (01100101)2 - (00000001)2
= (10011011)2 - (00000001)2
= (10011010)2
Radix Complement Number Systems
Quzi：
Find the 2s complement of the binary number 110011
Find the 1s complement code for -1210
Find the 2s complement code for -1810
Answer: 001101
10011
101110
1.3.4 Binary Arithmetic Using
Complement Codes
Subtract
Operation
X>Y
X<Y
X=Y
(+X)+(-Y)
+(X-Y)
-(X-Y)
+(X-Y)
(-X)+(+Y)
-(X-Y)
+(X-Y)
+(X-Y)
+(X-Y)
-(X-Y)
+(X-Y)
-(X-Y)
+(X-Y)
+(X-Y)
(+X)+(+Y)
(-X)+(-Y)
Add
+(X+Y)
-(X+Y)
(+X)-(+Y)
(+X)-(-Y)
+(X+Y)
(-X)-(+Y)
-(X+Y)
(-X)-(-Y)
Addition and subtraction of signed numbers
1.3.4 Binary Arithmetic Using
Complement Codes
e.g.
（-9）+（-3）=-12
1^0111 （-9）
+ 1^1101 （-3）
1 1^0100 （-12）
9+3=12
0^1001
+ 0^0011
0^1100
9-3=6
0^1001
+ 1^1101
1 0^ 0110
9-（-3）=12
0^1001
+ 0^0011
0^1100
3-9=-6
0^0011
+ 1^0111
1^1010
1.3.4 Binary Arithmetic Using
Complement Codes
e.g. 0^1101.1+0^1011.0
0^1101.1
0^01101.1
+ 0^1011.0
+ 0^01011.0
1^1000.1
0^11000.1
The error occurred due to insufficient
bit positions to hold the answer
1.3.4 Binary Arithmetic Using
Complement Codes
 e.g. Add X and Y . Let X=-810 and Y=-1010, both in
2s complement
1^1000
1^11000
+ 1^0110
+ 1^10110
(1)0^1110
(1)1^01110
-810+(-1010)=-1810 , 0^1110 is not -1810 and
1^01110 is the Complement of -1810
1.3.4 Binary Arithmetic Using
Complement Codes
 e.g.
Subtract Y from X. Let X=+810=0^1000 and
Y=-610=1^1010, X-Y=X+(-Y)
0^1000=+810
The 2s complement of -610(1^1010) is 0^0110
0^1000 = +810
+ 0^0110 =(complement of -6 )
0^1110 =+1410
1.3.4 Binary Arithmetic Using
Complement Codes
 exe.
Subtract Y from X. Let X=-1010=1^0110
and Y=-510=1^1011
The radix complement of 1^1011(-510) is 0^0101
1^0110 = -1010
+ 0^0101 =(complement of -510 )
1^1011 =-510
1.3.4 Arithmetic Using Complement
Codes
 Exe：perform the following operations by
finding the radix complement of the
subtrahend(减数) and adding the result to the
minuend(被减数):
23.410
135.78
321.24
- 19.810
- 67.78
- 33.34