wuzhihong@scu.edu.cn 3 / 1 / 16 / John M. Yarbrough: Digital Logic Applications and Design + + 30% 70%
1 CHAPTER 1 Digital Concepts and Number Systems
1.1 Digital and Analog: Basic Concepts P1
1.1
1.1 V c (0)=0V, Initial voltage at t 0 is 0V V c =V a (1-e -t/rc ) P1
1.1 Discrete voltage values for time interval (a) Analog representation (b) Discrete representation P2
1.1
1.1 Analog volt meter Digital volt meter P2/3
1.2 Some History of Digital Systems 1642 Blaise Pascal 1820 Charles Babbage P4
1.2 1847 George Boole The Mathematical Analysis of Logic 0 1
1.2 1947 Walter Brattain John Bardeen William Shockley 1956 50 1958 Jack Kilby(Texas Instruments) Robert Noyce(Fairchild Semiconductor) ) (IC )
1.2 1965 1968 Noyce 1971 2,300 1989 i486 1,200,000 2000 4200 45 8.2
1.3 Impact of Digital Technology on Society 4
1.3 2010 3G MID PMP / LED / LED / (HEV)
1.4 Defining the Problem, an Introduction to Algorithms Algorithm P5
1.5 Digital Systems Overview P6
1.5 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 P6
1.6 Introduction to Number Systems 10 2 8 16 P7
1.7 Positional Number Systems P7
Decimal Numbers 10 10 0 1 2 3 4 5 6 7 8 9 536.159 10 =(5 10 2 )+(3 10 1 )+(6 10 0 )+(1 10-1 )+(5 10-2 )+(9 10-3 ) Radix or Base Weight P7
r ( r) r N = A n-1 r n-1 + A n-2 r n-2 + + A 1 r +A 0 + A -1 r -1 + A -2 r -2 + + A -m r -m Most Significant Bit (MSB) Least Significant Bit (LSB)
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 ( ) m m n n n n r r c r c r c r c c r r c r c N + + + + + + + + =...... 2 2 1 1 0 0 1 1 2 2 1 1 ( ) = = 1 n m i i i r r c N P7 P7
1 e.g. let r = 6 (312.4) 6 = 3 6 2 + 1 6 1 + 1 6 0 + 4 6-1 = (116.66) 10 Conversion from r-radix (any system with radix r) to decimal follows similar process as above
2 Most common number systems for computers: Binary (r = 2) Octal (r = 8) Hexadecimal (r = 16)
Binary Numbers 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 2 5 + 0 2 4 + 1 2 3 + 1 2 2 + 0 2 1 + 1 2 0 + 1 2-1 + 0 2-2 (in decimal) = 32 + 0 + 8 + 4 + 0 + 1 + ½ + 0 = (45.5) 10 P8
Powers of two Memorize at least through 2 16
Octal Numbers base 8 with 8 digits: 0..7 Eg. 231.25 8 =2 8 2 + 3 8 1 +1 8 0 +2 8-1 +5 8-2 (in decimal) =153.328125 10 P8
Hexadecimal Numbers r = 16 Digits (convention): 0..9, A, B, C, D, E, F A=10, B=11,, F = 15 P8
e.g1. (3FB) 16 = 3 16 2 + 15 16 1 + 11 16 0 (in decimal) = 768 + 240 + 11 = (1019) 10 e.g2. A59C.3A 16 = (A 16 3 )+(5 16 2 )+(9 16 1 )+(C 16 0 )+(3 16-1 )+(A 16-2 )
1.8 Number System Conversion Decimal binary octal and hexadecimal number P9
0 0000 0 0 1 0001 1 1 2 0010 2 2 3 0011 3 3 4 0100 4 4 5 0101 5 5 6 0110 6 6 7 0111 7 7 8 1000 10 8 9 1001 11 9 10 1010 12 A 11 1011 13 B 12 1100 14 C 13 1101 15 D 14 1110 16 E 15 1111 17 F P10
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.110101010 2 to octal Solution 010,011,110,111.110,101,010 2 =2367.652 8
Binary Hex ( 0110 1010 1000. 1111 0101 1100 ) 2 ( 6 A 8. F 5 C ) 16 E.g. Convert the binary number 010011110111.110101010 2 to hexadecimal Solution 0100,1111,0111.1101,0101,0000 2 =4F7.D50 16
hexadecimal and octal to Binary Ex 1.9/1.11 Convert the numbers F37A.B2 16, 735.5 8 to binary Solution F37A.B2=1111,0011,0111,1010.1011,0010 2 735.5 8 =111,011,101.101 2 Practice problem: convert 367.236 convert 367.236 8 to binary then hexadecimal Solution 367.236 8 =011,110,111.010,011,110 2 011,110,111.010,011,110 2 =0,1111,0111.0100,1111,0 2 =F7.4F 16 P10/11
Binary to decimal Conversion 11001.011 2 =(1 2 4 )+(1 2 3 )+(0 2 2 )+(0 2 1 )+(1 2 0 ) +(0 2-1 )+(1 2-2 )+(1 2-3 ) =16+8+0+0+1+0+0.25+0.125 =25.375 10 P11
Decimal to Binary Conversion 2 0 E.g. Convert 119 10 to binary LSB Solution 119 10 =1110111 2 MSB P12
. 39 39 D = 100111 B 2 39 1 b 0 2 19 1 b 1 2 9 1 b 2 2 4 0 b 3 2 2 0 b 4 2 1 1 b 5 0
(215) D =(? ) B 1=b 0 1=b 1 1=b 2 2 215 2 107 2 53 2 26 2 13 2 6 2 3 2 1 2 0 0=b 3 1=b 4 0=b 5 1=b 6 1=b 7 ( 215 ) D =( 11010111 ) B (215) D = 1 2 = 7 + 1 2 (11010111) 6 B + 1 2 4 + 1 2 2 + 1 2 1 + 1 2 0
Decimal to Binary Conversion 2 Ex 1.13 Convert.75 10 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) (.75) 1 =.110 = 1 2 + 1 2 D 2 P12/13
1.14 Convert 95.0625 10 to binary Solution First, convert the integer part of the decimal number by successive division 1.Devide 95 by 2 5.Devide 5 by 2 (LSB) 2.Devide 47 by 2 6.Devide 2 by 2 3.Devide 23 by 2 7.Devide 1 by 2 4.Devide 11 by 2 (MSB) 95 10 =1 2 6 +0 2 5 +1 2 4 +1 2 3 +1 2 2 + 1 2 1 +1 2 0 =1011111 P13
1.14 Convert 95.0625 10 to binary Solution Second, convert the fraction 95 10 =1011111 1. (.0625) 2 = 0.125 0 (MSB) 2. (.125) 2 = 0.25 0 3. (.25) 2 = 0.5 0 4. (.5) 2 = 1.0 1 (LSB).0625 10 =.0001 2 95.0625 10 =1011111.0001 2 P13
Decimal to Any Radix Conversion The conversion of decimal numbers to any other radix applies the successive division and successive multiplication algorithms Ex 1.15 Convert 23.625 10 to octal (base 8) Solution Convert the integer portion by successive division 1.Divide 23 by 8 (LSB) Convert te fraction portion by successive multiplication (.625) 8 =5.00 5 (MSB) 2.Divide 2 by 8 23 10 =27 8 (MSB).625 10 =.5 8 23.625 10 =27.5 8 P14
Any Radix to Decimal Conversion e.g. Convert 324.2 5 to decimal Solution 3 5 2 +2 5 1 +4 5 0 +2 5-1 =3(25)+2(5)+4(1)+2(1/5) =75+10+4+2/5 =89.4 10 P15
Any Radix Conversion Practice problem: 1. Convert 345.2 6 to decimal 2. Convert 34.8 10 to base 5 Solution: 1. 137.333 10 2. 114.4 5
4. 8. 11. 14. 18. 20. P33/34
1.9 Binary Codes 1. 0 1 n 2 n N 2 n N P16
1.9.1 Natural Binary Coded Decimal 4 0~9 e.g. Convert 9275.6 10 into BCD Solution: 9=1001 2=0010 7=0111 5=0101 6=0110 9275.6 10 =1001,0010,0111,0101.0110 in BCD P16
1.9.2 Binary Codes (Weighted) 8421 2421 5421 3 3 0 0000 0000 0000 0011 0010 1 0001 0001 0001 0100 0110 2 0010 0010 0010 0101 0111 3 0011 0011 0011 0110 0101 4 0100 0100 0100 0111 0100 5 0101 1011 1000 1000 1100 6 0110 1100 1001 1001 1101 7 0111 1101 1010 1010 1111 8 1000 1110 1011 1011 1110 9 1001 1111 1100 1100 1010 P17
(10010000) 8421BCD =(90) 3 : 10 16 0 9, 1 8,..6 4 3 10 3 3
BCD BCD 0111 = 0 8+ 1 4+ 1 2+ 1 1= ( 7) D [ ] 8421BCD [ 1101 ] 2421BCD = 1 2 + 1 4 + 0 2 + 1 1 = () 7 D
BCD BCD ( 463.5) ( 863.2) 10 10 = = 0100 4 1110 8 0110 6 1100 6 0011. 3 0011. 3 0101 5 0010 2 8421BCD 2421BCD
11111111 377 255 FF H = B = O = D 001001010101 = 8421BCD 1001110111110001 B = 9DF1 H
1.9.3 BCD BCD Self-Complementing Codes P17
1.9.4 Unit Distance Code P18
1.9.4 2 P18
1.9.5 Alphanumeric Codes ASCII (American standard code for information interchange) 128 EBCDIC (extended BCD interchange code) P19
b 3 b 2 b 1 b 0 b 6 b 5 b 4 000 001 010 011 100 101 110 111 0000 NUL DLE SP 0 @ P p 0001 SOH DC1! 1 A Q a q 0010 STX DC2 2 B R b r 0011 ETX DC3 # 3 C S c s 0100 EOT DC4 $ 4 D T d t 0101 ENQ NAK % 5 E U e u 0110 ACK SYN & 6 F V f v 0111 BEL ETB 7 G W g w 1000 BS CAN ( 8 H X h x 1001 HT EM ) 9 I Y i y 1010 LF SUB * : J Z j z 1011 VT ESC + K [ k { 1100 FF FS L \ l 1101 CR GS = M ] m } 1110 SO RS N n 1111 SI US / O _ o DEL
1.9.6 Signed Number Binary +11 (0000 1011) B 11 (1000 1011) B P20/21
1.9.7 Signed Magnitude Codes 0 1 +127 01111111-127 11111111 +7 00000111-7 10000111 +126 01111110-126 11111110 +6 00000110-6 10000110 +125 01111101-125 11111101 +5 00000101-5 10000101 +124 01111100-124 11111100 +4 00000100-4 10000100 +123 01111011-123 11111011 +3 00000011-3 10000011 + 0-1 +2 00000010-2 10000010 +9 00001001-9 10001001 +1 00000001-1 10000001 +8 00001000-8 10001000 +0 00000000-0 10000000 P20/21
1.9.8 Complement Codes Sign magnitude 2s complement 1s complement 0 1 1 +1 +1 2 D 1 2 +127 01111111 01111111 01111111 +126 01111110 01111110 01111110 + 0 0 0 +1 00000001 00000001 00000001 +0 00000000 00000000 00000000-0 10000000 11111111 00000000-1 10000001 11111110 11111111-2 10000010 11111101 11111110-1 1 1-126 11111110 10000001 10000010-127 11111111 10000000 10000001-128 10000000
12 12 (mod) 9 5 2 1 4 9-4=5 2 8 9+8=12+5=5 9-4=(9 + 8)mod12 12 8 4 4 8 12 4 8 8 8 8 256
1.9.8 1 1 10s 9s 8s 8s 2s 0 10 9 0 10 7 0 10 1 1 9 8 1 7 6 1 1 0 2 8 7 3 7 6 4 6 5 5 5 4 6 4 3 7 3 2 8 2 1 9 1 0 2 3 4 5 6 7 6 5 4 3 2 1 5 4 3 2 1 0 1s P21
[0,M) M M a,b [0, M) f(a-b)==f(a+c) c= M-b b f 0<=x< M, f(x)=x; x>= M,f(x)=x % M; x<0,f(x)=f(m +x). % ( ) f ab==a+c -b c n M=2 n c=2 n -b 2 n -b 2 n 1 n 0 b 2 n -1 n 1 b 1 2 n -b 1
1.9.8 2 Ex: Find 2 s complement of 01100101 01100101 101 10 +101 10 10011010 Complement the bits + 1 Add 1 10011011 155 10 101 10 [N] 10 =10 n -(N) 10 [N] 2 = 2 n -(N) 2 [N] 2 (N) 2 [N] 2 = 2 6 - (101001) 2 = (1000000) 2 - (101001) 2 = (010111) 2 (N) 2 + [N] 2 = +0
Radix Complement Number Systems Quzi Find the 2s complement of the binary number 110011 Find the 1s complement code for -12 10 Find the 2s complement code for -18 10 Answer: 001101 10011 101110
1.10 Arithmetic Arithmetic 1.10.1 1 0 + 0 = 0 0 + 1 = 1 1 + 1 = 10 1010 0101 1 0 1 0 1 0 0 1 + 0 1 0 1 + 0 0 1 1 1 1 1 1 1 1 0 0 P22
1.10.1 1 2 0 0 = 0 1 1 = 0 1 0 = 1 0 1 = 11 1010 0101 1 0 1 0 0 1 0 1 0 1 0 1
1.10.1 2 3 1010 0101 1 0 1 0 0 1 0 1 1 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 1 0 0 1 0 P24
1.10.1 3 4 1010 111 1. 0 1 1 1 1 1 1 0 1 0 1 1 1 0 1 1 1 1 1 0 1 0 1 0 1 1 1 0 1 1 0 P24
1 1 = 1 + ( 1) = 0 (00000001 2 00000001 2 ) 8bits 00000001 2 + 10000001 2 = 10000010 2 2 00000001 2 + 11111110 2 = 11111111 2 + 0 0 0? 1 2 00000001 2 + 11111101 2 = 11111110 2 1-128~0~127 00000001 2 00000001 2 = 00000001 2 + 11111111 2 = 00000000 2 0!
1.10.2 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) - (X-Y) +(X-Y) - (X-Y) +(X-Y) +(X-Y) +(X-Y) +(X-Y) +(X-Y) P25
1.10.2 1 9 + 3 = 12 0^1001 9 + 0^0011 3 0^1100 12 9 3 = 6 0^1001 9 + 1^1101-3 10^0110 6-3 -100000 3 9 = -6 0^0011 3 + 1^0111-9 1^1010-6 (-9) + (-3) = -12 1^0111-9 + 1^1101-3 11^0100-12 9 (-3) = 12 0^1001 9 + 0^0011 3 0^1100 12
1.10.2 2 1-32/31 0^1101.1+0^1011.0 (+X )+(+Y ) 0^1101.1 + 0^1011.0 1^1000.1 0^01101.1 + 0^01011.0 0^11000.1 The error occurred due to insufficient bit positions to hold the answer P25
1.10.2 3 1-35 Add X and Y. Let X= 8 10 and Y= 10 10, both in 2s complement. 1^1000 + 1^0110 10^1110 1^11000 + 1^10110 11^01110 8 10 +( +( 10 10 )= 18 10, 0^1110 is not 18 10 and 1^01110 is the Complement of 18 18 10 P26
1.10.2 4 1-38 Subtract Y from X. Let X=+8 10 and Y=-6 10, X-Y=X+(-Y) +8 10 =0^1000 The 2s complement of -6 10 (1^1010) is 0^0110 0^1000 = +8 10 + 0^0110 =(complement of -6 ) 0^1110 =+14 10 P27
1.10.2 5 1-39 Subtract Y from X. Let X= 10 10 = 1^0110 and Y= 5 10 = 1^1011 The radix complement of 1^1011(-5 10 ) is 0^0101 1^0110 = -10 10 + 0^0101 =(complement of -5 10 ) 1^1011 =-5 10 P27
1.10.2 6 perform the following operations by finding the radix complement of the subtrahend( ) and adding the result to the minuend( ): 23.4 135.7 10 8 321.2 4 19.8 67.7 10 8 33.3 4
22. 24. 30. 32. 34. 38. P35/36