Numbering Systems, Arithmetic Operations, and Logic Gates PDF

Numbering Systems, Arithmetic Operations, and Logic Gates CPS213 Computer Organization I Fall 2024 © Ali Miri 1 Representation of Information Two key functions of any computing system: How to repr...

Numbering Systems, Arithmetic Operations, and Logic Gates CPS213 Computer Organization I Fall 2024 © Ali Miri 1 Representation of Information Two key functions of any computing system: How to represent Discrete Elements of information? Storing information Manipulation of information Possible Answer: Use Electrical Signals 3 Example: The result of a coin flip Is it tail? Available tool: A light bulb that can be turned on or off 4 Example: The result of a coin flip Is it tail? No Yes 0= =1 5 Example: Suit on a playing card Available tool: Two light bulbs that can be turned on or off 6 Example: Suit on a playing card 00 01 10 11 7 Example: Role of a dice How? What is the minimum number of ‘light bulb’ use? 8 Storing information All kind of information can be coded in binary! 9 ASCII Table Storing information Numbers 12  Numbers Unsigned integers 0, 1, 2, 3, … …., -3, -2, -1, 0, 1, 2, 3, … Signed integers …, -7/9, -1/3, …, 0, 1/13, 2/5, … Floating points …., -6.349, -2.1, …, 0, 0.23, 3.14, …. …, -2 – 3j, 0, 1+j, 3+4j, …. 13 Example: Representing {0,1,2,3} 0)10 00)2 1)10 01)2 2)10 10)2 3)10 11)2 14 Important Facts We can only represent a finite set of information depending on the number of available ‘light bulbs’ All information (including instructions) have to be coded in binary How a binary code is interpreted “depends” on the context/information it represents 15 Numbering Systems  Decimal Numbers Decimal numbers – Base 10 Use a set of 10 digits 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 17  Decimal System – Counting Up 0)10 1)10 2)10 3)10 4)10 5)10 6)10 7)10 8)10 9)10 10)10 11)10 … … … 99)10 100)10 18  Expanded Form 3 2 1 0 7 7 7 7)10 = 7 x 103 + 7 x 102 + 7 x 101 + 7 x 100 = 7000 + 700 + 70 + 7 3 2 1 0 9 7 5 3)10 = 9 x 103 + 7 x 102 + 5 x 101 + 3 x 100 = 9000 + 700 + 50 + 3 4 3 2 1 0 8 1 3 5 2)10 = 8 x 104 + 1 x 103 + 3 x 102 + 5 x 101 + 2 x 100 = 80000 + 1000 + 300 +50 +2 19  Expanded Form This can also be used for an expanded form of real numbers 1 0 -1 -2 -3 8 1.3 5 2)10 = 8 x 101 + 1 x 100 + 3 x 10-1 + 5 x 10-2 + 2 x 10-3 = 80 + 1 + 0.3 + 0.05 + 0.002 20  Place Value MSD: Most Significant Digit LSD: Least Significant Digit 73819 MSD.….……. LSD 7 381 9 21  Octal System – Base 8 0, 1, 2, 3, 4, 5, 6, 7 0)8 1)8 2)8 3)8 4)8 5)8 6)8 7)8 10)8 11)8 22  Octal System – Based 8 0, 1, 2, 3, 4, 5, 6, 7 60)8 70)8 100)8 61)8 71)8 101)8 62)8 72)8 102)8 63)8 73)8 103)8 64)8 74)8 104)8 65)8 75)8 105)8 66)8 76)8 106)8 67)8 77)8 107)8 23  Octal Expanded Form 102)8 = 1 x 82 + 0 x 81 + 2 x 80 = 64 + 0 + 2 = 66)10 6351)8 = 6 x 83 + 3 x 82 + 5 x 81 + 1 = 6 x 512 + 3 x 64 + 5 x 8 + 1 = 3072 + 192 + 40 + 1 = 3305)10 24  Examples 240)8 = 2 x 82 + 4 x 81 + 0 x 80 = 128 + 32 + 0 = 160)10 713)8 =? 25  Conversion Oct to Decimal 43210  order of significance 7 6 2 5 1)8 7 6 2 5 1)8 = 7 x 84 + 6 x 83 + 2 x 82 + 5 x 81 + 1 x 80 = 7 x 4096 + 6 x 512 + 2 x 64 +5x8+1 = 28672 + 3072 +128 + 40 + 1 = 31913)10 26  Octal System - Exercise Q) Obtain counts from 275)8 to 310)8. Q) What is the largest 5 digits number in base 8? 27  Hexadecimal System – Base 16 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F 0)16 1)16 2)16 3)16 4)16 5)16 6)16 7)16 8)16 9)16 A)16 B)16 C)16 D)16 E)16 F)16 28  Hex Expanded Form 23)16 = 2 x 161 + 3 x 160 = 32 + 3 = 35)10 6A51)16 = 6 x 163 + A x 162 + 5 x 161 + 1 = 6 x 4096 + 10 x 256 + 5 x 16 + 1 = 24576 + 2560 + 80 + 1 = 27217)10 29  Examples BAD)16 = B x 162 + A x 161 + D x 160 = B x 256 + A x 16 + D x 1 = 11 x 256 + 10 x 16 + 13 A 10 = 2816 + 160 + 13 B 11 = 2989)10 C 12 D 13 E 14 F 15 30  Conversion Hex to Decimal 3210  order of significance 6 2 5 1)16 6 2 5 1)16 = 6 x 163 + 2 x 162 + 5 x 161 + 1 x 160 = 6 x 4096 + 2 x 256 + 5 x 16 + 1 = 24576 + 512 + 80 + 1 = 25169)10 31  Hex System - Exercise Q) Obtain counts from 197)16 to 1A2)16. Q) What is the largest 5 digits number in base 16? 32  Binary System – Base 2 0, 1 0)2 1)2 10)2 11)2 100)2 101)2 110)2 111)2 1000)2 1001)2 33  Conversion Binary to Decimal 43210  order of significance 1 1 0 1 1)2 1 1 0 1 1)2 = 1 x 24 + 1 x 23 + 0 x 22 + 1 x 21 + 1 x 20 = 1 x 16 + 1 x 8 + 0 x 4 +1x2+1 = 16 + 8 + 0 + 2 + 1 = 27)10 34  Binary Expanded Form 1 1000)2 = 1 x 24 + 1 x 23 = 16 + 8 = 24)10 10 0101 0010)2 = 29 + 26 + 24 + 21 = 512 + 64 + 16 + 2 = 594)10 35 Powers of 2 are your friends 36  Expanded Form 0100 1011)2 = 26 + 23 + 21 + 20 = 64 + 8 + 2 + 1 = 75)10 37  Binary System - Exercise Q) Count from 10101)2 to 11101)2. Q) What is the largest 5-digit number in base 2? 38  Largest & Smallest Numbers 1 bit: 0, 1 Using 1 bit, we can represent 2 numbers (21) 0 1 39  Largest & Smallest Numbers 2 bits: 00, 01, 10, 11 Using 2 bits, we can represent 4 numbers (22) 0 0 0 1 1 0 1 1 40  Largest & Smallest Numbers 3 bits: 000, 001, 010, 011, 100, 101, 110, 111 Using 3 bits, we can represent 8 numbers (23) 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 41  Largest & Smallest Numbers What if we have n bits? How many numbers can we represent? 2n What is the smallest number? 0 What is the largest number? 2n-1 42  Largest & Smallest Numbers - Example What if we have 5 bits? How many numbers can we represent? 25 = 32 What is the smallest number? 0 What is the largest number? 25-1 = 31 43  Other Numbering Systems Could we have numbers in other bases? For example, would base 3 be acceptable? If so, what do numbers look like in base 3? 44 Binary, Oct, Hex, Decimal Numbers 45 Conversion from Decimal: Motivation 25 blocks 2 5 46 Conversion from Decimal: Motivation 25 blocks 3 1 47  Conversion from Decimal Using repetitive division (by the base) Keep dividing your number, or the resulting quotient by the base Use the remainder in reverse order (When converting fractional part of a real number, multiply it by the base repeatedly, and use the integer part in order) 48  Conversion from Decimal to Oct 3305)10 = ?)8 remainder 3305 1 413 5 51 3 6 6 49  Conversion from Decimal to Hex 3305)10 = ?)16 remainder 3305 9 206 14 (E) 12 12 (C) 50  Conversion from Decimal to Binary 33)10 = ?)2 remainder 33 1 16 0 8 0 4 0 2 0 1 1 51  Conversion - Binary  Oct Can convert from Binary to Decimal And then from Decimal to Oct 10 0001)2 = ?)8 10 0001)2 = 33)10 33)10 = 41)8 10 0001)2 = 41)8 52  Conversion - Binary  Oct Every 3 bits in Binary represents a digit in Oct 23 = 8 10 0001)2 = ?)8 Divide the binary number into groups of 3 bits (add 0’s to the left, if necessary) Start from the least significant bit (LSB) Each group represent an Oct digit 10 0001)2  100 001)2 4 1 )8 53  Conversion - Binary  Hex Can convert from Binary to Decimal And then from Decimal to Hex 10 0001)2 = ?)16 10 0001)2 = 33)10 33)10 = 21)16 10 0001)2 = 21)16 54  Conversion - Binary  Hex Every 4 bits in Binary represents a digit in Hex 24 = 16 10 0001)2 = ?)16 Divide the binary number into groups of 4 bits Start from the least significant bit (LSB) Each group represent a Hex digit 10 0001)2  10 0001)2 2 1 )16 55  Conversion - Oct  Hex Can convert from Oct to Binary Every digit in Oct is replaced by 3 bits in Binary And then from Binary to Hex 123)8 = ?)16 123)8 = 001 010 011)2 =0 0101 0011)2 =0 5 3)16 = 53)16 56  Conversion - Hex   Oct Can convert from Hex to Binary Every digit in Hex is replaced by 4 bits in Binary And then from Binary to Oct 123)16 = ?)8 123)16 = 0001 0010 0011)2 = 000 100 100 011)2 =0 4 4 3)8 = 443)8 57  Examples of Binary Addition, Subtraction and Multiplication Grade school style Work the same as decimal operation, except the resulting digits are 1 and 0 Can use carry or borrow concepts, but we need a better, efficient implementation (later) Also, need to decide how to represent negative numbers. 58 Representation of Signed Numbers Signed Numbers Discussion so far has been related to Unsigned numbers (positive numbers) only Signed numbers (positive & negative numbers) How to represent signed numbers? – Signed & Magnitude (S&M) – 1’s Complement (1’s Comp) – 2’s Complement (2’s Comp) 60  Signed & Magnitude Need to have a sign bit Use the MSB as the sign bit 0  + 1  - Use the remaining bits to show the magnitude 61  Signed & Magnitude (S & M) Sign bit + magnitude Sign bit magnitude 1-bit (n-1) bits 62 Signed & Magnitude - 2-bit representation 2-bit representation 01  + 1)10 00  + 0)10 Problem: 10  - 0)10 2 representations for 0 11  - 1)10 00 10 Most positive number: +1 Most negative number: -1 63 Signed & Magnitude - 3-bit representation 3-bit representation 011  + 3)10 010  + 2)10 001  + 1)10 000  + 0)10 100  - 0)10 101 - 1)10 110  - 2)10 111  - 3)10 Most positive number: +3 Most negative number: -3 64 Signed & Magnitude - 4-bit representation POSITIVE NUMBERS NEGATIVE NUMBERS 0111  + 7)10 1111  - 7)10 0110  + 6)10 1110  - 6)10 0101  + 5)10 1101  - 5)10 0100  + 4)10 1100  - 4)10 0011  + 3)10 1011  - 3)10 0010  + 2)10 1010  - 2)10 0001  + 1)10 1001  - 1)10 0000  + 0)10 1000  - 0)10 Most positive number: +7 Most negative number: -7 65 Signed & Magnitude - n-bit representation Most positive number: +[ (2 n-1) – 1 ] Most negative number: - [ (2 n-1) – 1 ] 2-bit: n=2 Most positive number: + [(22-1) -1] = +1 Most negative number: - [(22-1) -1] = -1 3-bit: n=3 Most positive number: + [(23-1) -1] = +3 Most negative number: - [(23-1) -1] = -3 4-bit: n=4 Most positive number: + [(24-1) -1] = +7 Most negative number: - [(24-1) -1] = -7 66  S&M - Examples Show +7)10 and -7)10 using S&M. How many bits do we need? Min number of bits needed to show +7)10: 4 bits Min number of bits needed to show -7)10: 4 bits +7)10: 0 111 (sign: 0, magnitude: 111) -7)10: 1 111 (sign: 1, magnitude: 111) Could we use more than 4 bits? +7)10: 0 0111 (sign: 0, magnitude: 0111) -7)10: 1 0111 (sign: 1, magnitude: 0111) +7)10: 0 00111 (sign: 0, magnitude: 00111) -7)10: 1 00111 (sign: 1, magnitude: 00111) 67  S&M - Examples Q) Show +12)10 and -12)10 using S&M. Min number of bits needed to show +12)10: 5 bits Min number of bits needed to show - 12)10: 5 bits +12)10: 0 1100 (sign: 0, magnitude: 1100) -12)10: 1 1100 (sign: 1, magnitude: 1100) Could we use more than 5 bits? +12)10: 0 01100 -12)10: 1 01100 +12)10: 0 001100 -12)10: 1 001100 68  S&M - Examples Q) Show +67)10 and -67)10 using S&M. Min number of bits needed to show +67)10: 8 bits Min number of bits needed to show - 67)10: 8 bits +67)10: 0 1000011 (sign: 0, magnitude: 1000011) -67)10: 1 1000011 (sign: 1, magnitude: 1000011) Could we use more than 8 bits? +67)10: 0 01000011 -67)10: 1 01000011 +67)10: 0 001000011 -67)10: 1 001000011 69  Conversion from S&M to Decimal 0 010 1111 Sign bit is 0  + The magnitude is: 010 1111  47 + 47)10 1 000 1100 Sign bit is 1  - The magnitude is: 000 1100  12 - 12)10 70 S&M Representation Summary Intuitive to understand Has two representation for zero Need to treat the ‘sign’ bit differently than the ‘magnitude’ bits in an arithmetic operation – Example n=4 bits, and adding -1)10 and -2)10 May have overflow in an arithmetic operation – Example n=4, and adding +5)10 and +3)10 May result in wrong answer in an arithmetic operation – Example n=4, and adding +2)10 and -1)10 71 1’s and 2’s Complements Basic idea: Positive numbers are represented similar to S&M, i.e. the MSB is ‘0’, and the remaining bits are the magnitude Different patterns of bits (to that of S&M) are used to represent negative numbers. 72  How to - 1’s Complement To obtain the 1’s complement of a binary number, simply flip all the bits – 0’s will become 1’s – 1’s will become 0’s 1’s complement of 100 1011 is 011 0100 73  1’s Complement - 2-bit representation 2-bit representation 01  + 1)10 00  + 0)10 Problem: 11  - 0)10 2 representations for 0 10  - 1)10 00 11 Most positive number: +1 Most negative number: -1 74  1’s Complement - 3-bit representation 3-bit representation 011  + 3)10 010  + 2)10 001  + 1)10 000  + 0)10 111  - 0)10 110  - 1)10 101  - 2)10 100  - 3)10 Most positive number: +3 Most negative number: -3 75  1’s Complement - 4-bit representation 0111  + 7)10 1000  - 7)10 0110  + 6)10 1001  - 6)10 0101  + 5)10 1010  - 5)10 0100  + 4)10 1011  - 4)10 0011  + 3)10 1100  - 3)10 0010  + 2)10 1101  - 2)10 0001  + 1)10 1110  - 1)10 0000  + 0)10 1111  - 0)10 Most positive number: +7 Most negative number: -7 76  1’s Complement - n-bit representation Most positive number: + [(2n-1) -1] Most negative number: - [(2n-1) -1] 2-bit: n= 2 Most positive number: + [(22 -1) -1] = + 1 Most negative number: - [(22 -1) -1] = - 1 3-bit: n= 3 Most positive number: + [(23 -1) -1] = + 3 Most negative number: - [(23 -1) -1] = - 3 77  1’s Complement - n-bit representation Most positive number: + [(2n-1) -1] Most negative number: - [(2n-1) -1] 4-bit: n= 4 Most positive number: + [(24 -1) -1] = + 7 Most negative number: - [(24 -1) -1] = - 7 5-bit: n= 5 Most positive number: + [(25 -1) -1] = + 15 Most negative number: - [(25 -1) -1] = - 15 78  1’s Comp - Examples Q) Show +7)10 and -7)10 using 1’s comp. How many bits do we need? Min number of bits needed to show +7)10: 4 bits Min number of bits needed to show -7)10: 4 bits +7)10: 0 111 (sign: 0, magnitude: 111) - 7)10: 1 000 (sign: 1, magnitude: 111 1’s comp: 000) 79  1’s Comp - Examples Q) Show +7)10 and -7)10 using 1’s comp. Q) Could we use more than 4 bits? +7)10: 0 0111 - 7)10: 1 1000 (sign: 1, magnitude: 0111 1’s comp: 1000) +7)10: 0 00111 - 7)10: 1 11000 (sign: 1, magnitude: 00111 1’s comp: 11000) 80  1’s Comp - Examples Q) Show +12)10 and -12)10 using 1’s comp. Min number of bits needed: 5 bits Min number of bits needed: 5 bits +12)10: 0 1100 - 12)10: 1 0011 (sign: 1, magnitude: 1100 1’s comp: 0011) 81  1’s Comp - Examples Q) Show +12)10 and -12)10 using 1’s comp. Q) Could we use more than 5 bits? +12)10: 0 01100 - 12)10: 1 10011 +12)10: 0 001100 - 12)10: 1 110011 82  1’s Comp - Examples Q) Show +67)10 and -67)10 using 1’s comp. Min number of bits needed: 8 bits Min number of bits needed: 8 bits +67)10: 0 1000011 - 67)10: 1 0111100 (sign: 1, magnitude: 1000011 1’s comp: 0111100) 83  1’s Comp - Examples Q) Show +67)10 and -67)10 using 1’s comp. Q) Could we use more than 8 bits? +67)10: 0 0100 0011 - 67)10: 1 1011 1100 +67)10: 0 0 0100 0011 - 67)10: 1 1 1011 1100 84 Conversion from 1’s Comp to Decimal 0 010 1111 MSB bit is 0  + The magnitude is: 010 1111  47 +47)10 1 000 1100 MSB bit is 1  - The remaining bits (000 1100) are 1’s comp of the magnitude Flip the bits to get the magnitude The magnitude is: 111 0011  115 -115)10 85  2’s Complement Positive numbers are represented similar to S&M, i.e. the MSB is ‘0’, and the remaining bits are the magnitude To get the negative of a positive number, compute its 1’s complement and add 1 to the result 86  How to - 2’s Complement To obtain the 2’s complement :Simply flip all the bits, and add 1 2’s complement of 1001011 ? 1’s complement: 0110100 Add 1 + 1 ------------- 2’s complement 0110101 87  2’s Complement - 2-bit representation 2-bit representation 01  + 1)10 00  + 0)10 11  - 1)10 10  - 2)10 Most positive number: +1 Most negative number: -2 88  2’s Complement - 3-bit representation 3-bit representation 011  + 3)10 010  + 2)10 001  + 1)10 000  + 0)10 111  - 1)10 110  - 2)10 101  - 3)10 100  - 4)10 Most positive number: +3 Most negative number: -4 89  2’s Complement - 4-bit representation 0111  + 7)10 1001  - 7)10 0110  + 6)10 1010  - 6)10 0101  + 5)10 1011  - 5)10 0100  + 4)10 1100  - 4)10 0011  + 3)10 1101  - 3)10 0010  + 2)10 1110  - 2)10 0001  + 1)10 1111  - 1)10 0000  + 0)10 1000  - 8)10 Most positive number: +7 Most negative number: -8 90  2’s Complement - n-bit representation Most positive number: + [ (2 n - 1 ) – 1 ] Most negative number: - [ (2 n - 1) ] 2-bit: n= 2 Most positive number: + [(22-1) -1] = + 1 Most negative number: - [(22-1)] = - 2 3-bit: n= 3 Most positive number: + [(23-1) -1] = + 3 Most negative number: - [(23-1)] = - 4 4-bit: n= 4 Most positive number: + [(24-1) -1] = + 7 Most negative number: - [(24-1)] = - 8 91  2’s Comp - Examples Q) Show +7)10 and -7)10 using 2’s comp. How many bits do we need? Min number of bits needed to show +7)10: 4 bits Min number of bits needed to show - 7)10: 4 bits +7)10: 0 111 - 7)10: 1 001 92  2’s Comp - Examples Q) Show +7)10 and -7)10 using 2’s comp. Q) Could we use more than 4 bits? +7)10: 0 0111 - 7)10: 1 1001 +7)10: 0 00111 - 7)10: 1 11001 93  2’s Comp - Examples Q) Show +12)10 and -12)10 using 2’s comp. Min number of bits needed to show +12)10: 5 bits Min number of bits needed to show - 12)10: 5 bits +12)10: 0 1100 - 12)10: 1 0100 94  2’s Comp - Examples Q) Show +12)10 and -12)10 using 2’s comp. Q) Could we use more than 5 bits? +12)10: 0 01100 - 12)10: 1 10100 +12)10: 0 001100 - 12)10: 1 110100 95  2’s Comp - Examples Q) Show +67)10 and -67)10 using 2’s comp. Min number of bits needed to show +67)10: 8 bits Min number of bits needed to show - 67)10: 8 bits +67)10: 0 100 0011 - 67)10: 1 011 1101 96  2’s Comp - Examples Q) Show +67)10 and -67)10 using 2’s comp. Q) Could we use more than 8 bits? +67)10: 0 0100 0011 - 67)10: 1 1011 1101 +67)10: 0 00100 0011 - 67)10: 1 11011 1101 97 2’s Complement Summary Has a unique representation for zero Does not nto treat the ‘sign’ bit differently – Example n=4 bits, and adding -1)10 and -2)10 May have overflow in an arithmetic operation – Example n=4, and adding +5)10 and +3)10 – But we can set up indicator of occurrence Consistent with the expected arithmetic operation results – Example n=4, and adding +2)10 and -1)10 Complement of complement of a binary number is that number itself* 98  Note Choice of representation should always be known (Default: 2’s Complement) Number of bits used for the representation should always be known Representations of positive numbers is the same in all three methods: MSB 0 -> + , i.e. `sign’, with the remaining bits representing the magnitude Only representations of negative numbers are different, but the MSB is always 1 -> ‘sign’ 99  Sign Extension For 1’s and 2’s complement representation only We can show the numbers using more bits simply by extending the sign bits Extension always in the MSB position 100  Sign Extension – 2’s Comp Example +12)10: 0 1100 + 12)10 +12)10: 00 1100 +12)10: 000 1100 Sign: 0 Magnitude: 1100 +12)10: 0000 1100 +12)10: 00000 1100 0 1100 101  Sign Extension – 2’s Comp. Example -12)10: 1 0100 + 12)10 -> 0 1100)2 -12)10: 11 0100 1’s comp rep of -12)10 -12)10: 111 0100 1 0011)2 -12)10: 1111 0100 Add ‘1’ to get 2’s comp -12)10: 11111 0100 1 0100)2 102 Conversion from 2’s Comp to Decimal 0 010 1111)2 MSB (Sign) bit is 0  + The magnitude is: 010 1111  47 +47)10 1 000 1100)2 MSB (Sign) bit is 1  - Compute its 2’s complement*  0 111 0100)2 Non MSB bits represent the magnitude, i.e. The magnitude is: 111 0100  116 So, the decimal rep of 1 000 1100)2 is -116)10 103  4-bit Representation S&M, 1’s Comp, 2’s Comp 104 Binary Arithmetic Math Operations Addition – Unsigned numbers – Signed numbers Subtraction Overflow 107  Basic Math Operations 4 basic operations Addition Subtraction Multiplication Division 108  Basic Math Operations Important operations Addition – Subtraction is a form of addition – Multiplication is repetitive addition – Division is repetitive subtraction 109  Decimal Addition 1 1 1  carry 7 6 3 2 + 6 4 8 9 Two 4-digit numbers are added The result is a 4-digit number -------------------------- There can be a final carry 1 4 1 2 1 Final Final Carry Sum 110  Binary Addition – Unsigned Numbers 0 0 1  carry 1 0 0 1 + 0 1 0 1 Two 4-digit numbers are added The result is a 4-digit number -------------------------- There can be a final carry 0 1 1 1 0 Final Final Carry Sum 111  Example Perform the following addition in Binary: 3E)16 + 75)16 How many bits do we need for this operation? 0 1 1 1 1 1 0 0  carry 0 0 1 1 1 1 1 0  3E16 + 0 1 1 1 0 1 0 1  7516 --------------------------------- 0 1 0 1 1 0 0 1 1 Final Final Carry Sum 112  Example Perform the same addition in Hex: 3E)16 + 75)16 Are you getting the same result? Why? A 10 0 1 B 11 3 E C 12 + 7 5 D 13 ------------------- E 14 0 B 3 F 15 113  Signed Addition in 2’s Comp A + B ------------------ Four cases: I) A and B are both positive II) positive number and a smaller negative number III) positive number and a larger negative number IV) A and B are both negative 114  Case I: 2 Positive Numbers Assume a 5-bit operation 910 + 410 --------------- +1310 Sign Bit 0 1 0 0 1 Note: both numbers are + 0 0 1 0 0 positive and are shown ---------------------------- using 2’s comp rep 0 1 1 0 1 + 13 115  Case II: Positive Number & a Smaller Negative Number Assume a 5-bit operation 910 + -410 ------------------- +510 116  Case II: Positive Number & a Smaller Negative Number Before performing the binary addition operation we need to convert these two numbers 910 and -410 to binary using 2’s comp representation: 910 sign bit: 0 magnitude of 9 is 1001 0 1001 -410  sign bit: 1 magnitude of 4 is 0100 complement of this is 1011 after adding 1, it is 1100 1 1100 117  Case II: Positive Number & a Smaller Negative Number Assume a 5-bit operation 1 1 0 0 0  carry Sign Bit 0 1 0 0 1 Note: a positive number + 1 1 1 0 0 & a negative number ---------------------------- Both numbers are shown using 2’s comp rep 1 0 0 1 0 1 Final Carry Disregard + 5 118  Sign Bit & Addition Note: Similar to other bits, the Sign Bit also participates in the addition process 119  Case III: Positive Number & a Larger Negative Number Assume a 5-bit operation -910 + 410 ------------------- -510 120  Case III: Positive Number & Larger Negative Number Before performing the binary addition operation we need to convert these two numbers 410 and -910 to binary using 2’s comp representation: 410 sign bit: 0 magnitude of 4 is 0100 0 0100 -910  sign bit: 1 magnitude of 9 is 1001 complement of this is 0110 after adding 1, it is 0111 1 0111 121  Case III: Positive Number & a Larger Negative Number Assume a 5-bit operation 0 0 1 0 0  carry Sign Bit 0 0 1 0 0 Note: a positive number + 1 0 1 1 1 & a negative number ---------------------------- Both numbers are shown using 2’s comp rep 0 1 1 0 1 1 Final Carry Disregard - 5 122  Case III: Positive Number & a Larger Negative Number How do have we have to interpret the result? 1 1011 Remember that we have Sign bit 1011 used 2’s comp method to 0100 represent the negative 0101 number - 5 123  Case IV: Two Negative Numbers Assume a 5-bit operation -910 + -410 ------------------- - 1310 124  Case IV: 2 Negative Numbers Before performing the binary addition operation we need to convert these two numbers -410 and -910 to binary using 2’s comp representation: -410 sign bit: 1 magnitude of 4 is 0100 complement of this is 1011 after adding 1, it is 1100 1 1100 -910  sign bit: 1 magnitude of 9 is 1001 complement of this is 0110 after adding 1, it is 0111 1 0111 125  Case IV: 2 Negative Numbers Assume a 5-bit operation 1 1 1 0 0  carry Sign Bit 1 0 1 1 1 + 1 1 1 0 0 Both numbers are shown using 2’s comp rep ---------------------------- 1 1 0 0 1 1 Final Carry Disregard - 13 126  Case IV: 2 Negative Numbers How do have we have to interpret the result? 1 0011 Remember that we have used 2’c comp method to Sign bit 0011 represent the negative 1100 number 1101 - 13 127  Signed Subtraction in 2’s Comp A - B ------------------- How many cases? 128  Signed Subtraction in 2’s Comp Subtraction is really is a case of addition Therefore, as long as we know how to add we are able to do subtraction the same way A  A - B + (-B) ----------- -------------- 129  Example 910 910 - 410  + -410 ---------- ----------- Or 01001 01001 - 00100  + 11100 ----------------- ----------------- 130  Example Assume a 5-bit operation 1 1 0 0 0  carry 0 1 0 0 1 Note: a positive number & + 1 1 1 0 0 a negative number Both numbers are shown ---------------------------- using 2’s comp rep 1 0 0 1 0 1 Final Carry + 5 Disregard 131  Example -410 -410 - 910  + -910 ----------- ----------- Or 11100 11100 - 01001  + 10111 ----------------- ----------------- 132  Example Assume a 5-bit operation 1 1 1 0 0  carry 1 1 1 0 0 + 1 0 1 1 1 Note: Both numbers are shown ---------------------------- using 2’s comp rep 1 1 0 0 1 1 Final Carry - 13 Disregard 133  Example Assume a 5-bit operation Perform the following addition: 910 + 810 -------------- 134  Example Assume a 5-bit operation 910 + 810 --------------- 0 1 0 0 1 Note: both numbers are + 0 1 0 0 0 positive and are shown ---------------------------- using 2’s comp rep 1 0 0 0 1 - ??? 135  Overflow When adding two numbers of the same sign (both positive or both negative) If the results cannot be shown in the number of bits available (in case of the previous example a 5-bit representation) Then an overflow will occur showing that the result is wrong 136 Logic Gates and Timing Diagrams  Logic Gates (Symbolic, Algebraic, Truth Table Representation) – AND, OR, NOT, BUFFER, NAND, NOR, XOR, XNOR – Gates with n-input Timing Diagram 138 Truth Tables of Logical Operations (Fundamental Set) 139 Symbols for digital logic circuits 140 Truth Tables for the 16 Functions of Two Binary Variables 0 AND xy’ x x’y y XOR OR NOR XNOR y’ x+y’ x’ x+y NAND 1 141 Boolean Expressions for the 16 Functions of Two Variables 142 Digital logic gates - AND The output is 1 if all the inputs are 1 What about 3-input AND? What about n-input AND? Do we need to know all the inputs to determine the output? 143 Digital logic gates - OR The output is 1 if one of the inputs is 1 What about 3-input OR? What about n-input OR? Do we need to know all the inputs to determine the output? 144 Digital logic gates – INVERTER (NOT, COMPLEMENT) The output is the complement of the input What about 2-input NOT? 145 Digital logic gates – BUFFER (TRANSFER) The output is a copy of the input What about 2-input AND? 146 Digital logic gates – NAND (NOT AND) The output is 1 if one of the inputs is 0 What about 3-input NAND? What about n-input NAND? Do we need to know all the inputs to determine the output? 147 Digital logic gates – NOR (NOT OR) The output is 1 if all the inputs are 0 What about 3-input NOR? What about n-input NOR? Do we need to know all the inputs to determine the output? 148 Digital logic gates – XOR X or Y but not both The output is 1 if X and Y are not the same (not equal) What about 3-input XOR? What about n-input XOR? Do we need to know all the inputs to determine the output? 149 Digital logic gates – XNOR (EQUIVALENCE) The output is 1 if X and Y are the same (equal) What about 3-input XNOR? What about n-input XNOR? Do we need to know all the inputs to determine the output? 150 Multiple-input and cascaded NOR, NAND gates 151 Gates with multiple inputs 152 Three-input exclusive-OR gate 153 Digital Logic Families Most popular families Standard TTL Transistor-Transistor Logic High speed operation ECL Emiter-Coupled Logic High component density MOS Metal-Oxide Semiconductor Low power consumption CMOS Complementary Metal-Oxide Semiconductor 154 Characteristic of Gates Fan-Out: # of standard loads that the output of a typical gate can drive without impairing its normal operation Power Dissipation: Power consumed by the gate Propagation Delay: average transition delay for a signal to propagate from input to output Speed is inversely proportional with delay Noise Margin: min. external noise voltage that causes an undesirable change in circuit output 155 Signal assignment and logic polarity 156 Signal levels for binary logic values 157 Input signal for gates - Timing Diagram ❷ ❶ ❸ x is “ZERO” x is “ONE” x is “ZERO” 158  Input signals for gates - Timing Diagram x and y are inputs and are given 159  Input signals for gates - Timing Diagram x and y are inputs and are given 160 Input–output signals for gates - AND Timing Diagram 161 Input–output signals for gates - OR Timing Diagram 162 Input–output signals for gates - NOT Timing Diagram 163 Timing Diagram - AND, OR, NOT 164