Digital Engineering Lecture 01 PDF

Digital Engineering Fall 2023 Lecture 01 - Data Representation Instructor: Dr. Tarek Abdul Hamid Why Binary?  Early computer design was decimal  Mark I and ENIAC  John von Neumann proposed binary data processing (1945)  Simplified computer design  Used fo...

Digital Engineering Fall 2023 Lecture 01 - Data Representation Instructor: Dr. Tarek Abdul Hamid Why Binary?  Early computer design was decimal  Mark I and ENIAC  John von Neumann proposed binary data processing (1945)  Simplified computer design  Used for both instructions and data  Natural relationship between on/off switches and calculation using Boolean logic On Off True False Yes No 1 0 2-2 Dr. Tarek Abdul Hamid Digital Engineering Counting and Arithmetic  Decimal or base 10 number system  Origin: counting on the fingers  “Digit” from the Latin word digitus meaning “finger”  Base: the number of different digits including zero in the number system  Example: Base 10 has 10 digits, 0 through 9  Binary or base 2  Bit (binary digit): 2 digits, 0 and 1  Octal or base 8: 8 digits, 0 through 7  Hexadecimal or base 16: 16 digits, 0 through F  Examples: 1010 = A16; 1110 = B16 2-3 Dr. Tarek Abdul Hamid Digital Engineering Keeping Track of the Bits  Bits commonly stored and manipulated in groups  8 bits = 1 byte  4 bytes = 1 word (in many systems)  Number of bits used in calculations  Affects accuracy of results  Limits size of numbers manipulated by the computer 2-4 Dr. Tarek Abdul Hamid Digital Engineering Positional Notation: Base 10 43 = 4 x 101 + 3 x 100 10’s place 1’s place Place 101 100 Value 10 1 Evaluate 4 x 10 3 x1 Sum 40 3 2-5 Dr. Tarek Abdul Hamid Digital Engineering Positional Notation: Base 10 527 = 5 x 102 + 2 x 101 + 7 x 100 100’s place 10’s place 1’s place Place 102 101 100 Value 100 10 1 Evaluate 5 x 100 2 x 10 7 x1 Sum 500 20 7 2-6 Dr. Tarek Abdul Hamid Digital Engineering Positional Notation: Octal 6248 = 40410 64’s place 8’s place 1’s place Place 82 81 80 Value 64 8 1 Evaluate 6 x 64 2x8 4x1 Sum for 384 16 4 Base 10 2-7 Dr. Tarek Abdul Hamid Digital Engineering Positional Notation: Hexadecimal 6,70416 = 26,37210 4,096’s place 256’s place 16’s place 1’s place Place 163 162 161 160 Value 4,096 256 16 1 Evaluate 6x 7 x 256 0 x 16 4x1 4,096 Sum for 24,576 1,792 0 4 Base 10 2-8 Dr. Tarek Abdul Hamid Digital Engineering Positional Notation: Binary 1101 01102 = 21410 Place 27 26 25 24 23 22 21 20 Value 128 64 32 16 8 4 2 1 Evaluate 1 x 128 1 x 64 0 x 32 1 x16 0x8 1x4 1x2 0x1 Sum for 128 64 0 16 0 4 2 0 Base 10 2-9 Dr. Tarek Abdul Hamid Digital Engineering Estimating Magnitude: Binary 1101 01102 = 21410 1101 01102 > 19210 (128 + 64 + additional bits to the right) Place 27 26 25 24 23 22 21 20 Value 128 64 32 16 8 4 2 1 Evaluate 1 x 128 1 x 64 0 x 32 1 x16 0x8 1x4 1x2 0x1 Sum for 128 64 0 16 0 4 2 0 Base 10 2-10 Dr. Tarek Abdul Hamid Digital Engineering Range of Possible Numbers  R = BK where  R = range  B = base  K = number of digits  Example #1: Base 10, 2 digits  R = 102 = 100 different numbers (0…99)  Example #2: Base 2, 16 digits  R = 216 = 65,536 or 64K  16-bit PC can store 65,536 different number values 2-11 Dr. Tarek Abdul Hamid Digital Engineering Decimal Range for Bit Widths Bits Digits Range 1 0+ 2 (0 and 1) 4 1+ 16 (0 to 15) 8 2+ 256 10 3 1,024 (1K) 16 4+ 65,536 (64K) 20 6 1,048,576 (1M) 32 9+ 4,294,967,296 (4G) 64 19+ Approx. 1.6 x 1019 128 38+ Approx. 2.6 x 1038 2-12 Dr. Tarek Abdul Hamid Digital Engineering Base or Radix  Base:  The number of different symbols required to represent any given number  The larger the base, the more numerals are required  Base 10: 0,1, 2,3,4,5,6,7,8,9  Base 2: 0,1  Base 8: 0,1,2, 3,4,5,6,7  Base 16: 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F 2-13 Dr. Tarek Abdul Hamid Digital Engineering Number of Symbols vs. Number of Digits  For a given number, the larger the base  the more symbols required  but the fewer digits needed  Example #1:  6516 10110 1458 110 01012  Example #2:  11C16 28410 4348 1 0001 11002 2-14 Dr. Tarek Abdul Hamid Digital Engineering Counting in Base 2 Binary Equivalent Decimal Number 8’s (23) 4’s (22) 2’s (21) 1’s (20) Number 0 0 x 20 0 1 1 x 20 1 10 1 x 21 0 x 20 2 11 1 x 21 1 x 20 3 100 1 x 22 4 101 1 x 22 1 x 20 5 110 1 x 22 1 x 21 6 111 1 x 22 1 x 21 1 x 20 7 1000 1 x 23 8 1001 1 x 23 1 x 20 9 1010 1 x 23 1 x 21 10 2-15 Dr. Tarek Abdul Hamid Digital Engineering Base 10 Addition Table 310 + 610 = 910 + 0 1 2 3 4 5 6 7 8 9 0 0 1 2 3 4 5 6 7 8 9 1 1 2 3 4 5 6 7 8 9 10 2 2 3 4 5 6 7 8 9 10 11 3 3 4 5 6 7 8 9 10 11 12 4 4 5 6 7 8 9 10 11 12 13 etc 2-16 Dr. Tarek Abdul Hamid Digital Engineering Base 8 Addition Table 38 + 68 = 118 + 0 1 2 3 4 5 6 7 0 0 1 2 3 4 5 6 7 1 1 2 3 4 5 6 7 10 (no 8 or 9, 2 2 3 4 5 6 7 10 11 of course) 3 3 4 5 6 7 10 11 12 4 4 5 6 7 10 11 12 13 5 5 6 7 10 11 12 13 14 6 6 7 10 11 12 13 14 15 7 7 10 11 12 13 14 15 16 2-17 Dr. Tarek Abdul Hamid Digital Engineering Base 10 Multiplication Table 310 x 610 = 1810 x 0 1 2 3 4 5 6 7 8 9 0 0 1 1 2 3 4 5 6 7 8 9 2 2 4 6 8 10 12 14 16 18 3 3 6 9 12 15 18 21 24 27 4 0 4 8 12 16 20 24 28 32 36 5 5 10 15 20 25 30 35 40 45 6 6 12 18 24 30 36 42 48 54 7 7 14 21 28 35 42 49 56 63 etc. 2-18 Dr. Tarek Abdul Hamid Digital Engineering Base 8 Multiplication Table 38 x 68 = 228 x 0 1 2 3 4 5 6 7 0 0 1 1 2 3 4 5 6 7 2 2 4 6 10 12 14 16 3 0 3 6 11 14 17 22 25 4 4 10 14 20 24 30 34 5 5 12 17 24 31 36 43 6 6 14 22 30 36 44 52 7 7 16 25 34 43 52 61 2-19 Dr. Tarek Abdul Hamid Digital Engineering Addition Base Problem Largest Single Digit 6 Decimal 9 +3 6 Octal 7 +1 6 Hexadecimal F +9 1 Binary 1 +0 2-20 Dr. Tarek Abdul Hamid Digital Engineering Addition Base Problem Carry Answer 6 Decimal Carry the 10 10 +4 6 Octal Carry the 8 10 +2 6 Hexadecimal Carry the 16 10 +A 1 Binary Carry the 2 10 +1 2-21 Dr. Tarek Abdul Hamid Digital Engineering Binary Arithmetic 1 1 1 1 1 1 1 0 1 1 0 1 + 1 0 1 1 0 1 0 0 0 0 0 1 1 2-22 Dr. Tarek Abdul Hamid Digital Engineering Binary Arithmetic  Addition  Boolean using XOR and 0 1 + AND  Multiplication 0 0 1  AND 1 1 10  Shift  Division x 0 1 0 0 0 1 0 1 2-23 Dr. Tarek Abdul Hamid Digital Engineering Binary Multiplication  Boolean logic without performing arithmetic  AND (carry bit)  Output is “1” if and only both inputs are a “1”  Shift  Shifting a number in any base left one digit multiplies its value by the base  Shifting a number in any base right one digit divides its value by the base  Examples:  1010 shift left = 10010  1010 shift right = 110  102 shift left = 1002  102 shift right = 12 2-24 Dr. Tarek Abdul Hamid Digital Engineering Binary Multiplication 1 1 0 1 1 0 1 1 1 0 1 1’s place 0 2’s place 1 1 0 1 4’s place (bits shifted to line up with 4’s place of multiplier) 1 0 0 0 0 0 1 Result (AND) 2-25 Dr. Tarek Abdul Hamid Digital Engineering Binary Multiplication 1 1 0 1 1 0 1 x 1 0 0 1 1 0 1 1 0 1 1 0 1 2’s place (bits shifted to line up with 2’s place of multiplier) 1 1 0 1 1 0 1 4’s place 1 1 0 1 1 0 1 32’s place 1 0 0 0 0 0 0 1 0 1 1 1 0 Result (AND) Note the 0 at the end, since the 1’s place is not brought down. Note: multiple carries are possible. 2-26 Dr. Tarek Abdul Hamid Digital Engineering Converting from Base 10  Powers Table Power 8 7 6 5 4 3 2 1 0 Base 2 256 128 64 32 16 8 4 2 1 8 32,768 4,096 512 64 8 1 16 65,536 4,096 256 16 1 2-27 Dr. Tarek Abdul Hamid Digital Engineering From Base 10 to Base 2 4210 = 1010102 Power 6 5 4 3 2 1 0 Base 2 64 32 16 8 4 2 1 1 0 1 0 1 0 Integer 42/32 10/16 10/8 2/4 2/2 0/1 =1 =0 =1 =0 =1 =0 Remainder 10 10 2 2 0 0 2-28 Dr. Tarek Abdul Hamid Digital Engineering From Base 10 to Base 2 Base 10 42 Remainder Quotient 2 ) 42 ( 0 Least significant bit 2 ) 21 ( 1 2 ) 10 ( 0 2) 5 (1 2) 2 (0 2) 1 Most significant bit Base 2 101010 2-29 Dr. Tarek Abdul Hamid Digital Engineering From Base 10 to Base 16 5,73510 = 166716 Power 4 3 2 1 0 Base 16 65,536 4,096 256 16 1 1 6 6 7 Integer 5,735 /4,096 1,639 / 256 103 /16 7 =1 =6 =6 Remainder 5,735 - 4,096 1,639 –1,536 103 – 96 = 1,639 = 103 =7 2-30 Dr. Tarek Abdul Hamid Digital Engineering From Base 10 to Base 16 Base 10 5,735 Remainder Quotient 16 ) 5,735 ( 7 Least significant bit 16 ) 358 ( 6 16 ) 22 ( 6 16 ) 1 ( 1 Most significant bit 16 ) 0 Base 16 1667 2-31 Dr. Tarek Abdul Hamid Digital Engineering From Base 10 to Base 16 Base 10 8,039 Remainder Quotient 16 ) 8,039 ( 7 Least significant bit 16 ) 502 ( 6 16 ) 31 ( 15 16 ) 1 ( 1 Most significant bit 16 ) 0 Base 16 1F67 2-32 Dr. Tarek Abdul Hamid Digital Engineering From Base 8 to Base 10 72638 = 3,76310 Power 83 82 81 80 512 64 8 1 x7 x2 x6 x3 Sum for Base 10 3,584 128 48 3 2-33 Dr. Tarek Abdul Hamid Digital Engineering From Base 8 to Base 10 72638 = 3,76310 7 x8 56 + 2 = 58 x8 464 + 6 = 470 x8 3760 + 3 = 3,763 2-34 Dr. Tarek Abdul Hamid Digital Engineering From Base 16 to Base 2  The nibble approach  Hex easier to read and write than binary Base 16 1 F 6 7 Base 2 0001 1111 0110 0111  Why hexadecimal?  Modern computer operating systems and networks present variety of troubleshooting data in hex format 2-35 Dr. Tarek Abdul Hamid Digital Engineering Binary Subtraction  Have previously looked at the subtraction operation. A quick review.  Just like subtraction in any other base  Minuend 10110  Subtrahand - 10010  Difference 00100  And when a borrow is needed. Note that the borrow gives us 2 in the current bit position. . 2-36 Dr. Tarek Abdul Hamid Digital Engineering And a full example  And more ripple - 2-37 Dr. Tarek Abdul Hamid Digital Engineering In General  When there is no borrow into the msb position, then the subtrahend in not larger than the minuend and the result is positive and correct.  If a borrow into the msb does occur, then the subtrahend is larger than the minuend. This was seen back in lecture 2. 2-38 Dr. Tarek Abdul Hamid Digital Engineering Two’s compliment  But how do you represent a minus sign electronically in a computer?  How can you represent it such that arithmetic operations are manageable?  There are two types of compliments for each number base system.  Have the r’s complement  Have the (r-1)’s complement  For base 2 have 2’s complement and 1’s complement 2-39 Dr. Tarek Abdul Hamid Digital Engineering 1’s Complement  1’s complement of N is defined as (2n -1)-N.  If n=4 have (2n -1) being 1 0000 - 1 = 1111  So for n=4 would subtract any 4-bit binary number from 1111.  This is just inverting each bit.  Example: 1’s compliment of 1011001  is 0100110 2-40 Dr. Tarek Abdul Hamid Digital Engineering 2’s complement  The 2’s complement is defined as 2n-N  Can be done by subtraction of N from 2n or adding 1 to the 1’s complement of a number.  For 6 = 0110  The 1’s complement is 1001  The 2’s complement is 1010 2-41 Dr. Tarek Abdul Hamid Digital Engineering Operation with 2’s complement  Add 4 and -6  Will use the 2’s complement of -6 or 1010  4 0100  -6 1010  1110  And taking the 2’s complement of 1110 get 0001 + 1 = 0010 2-42 Dr. Tarek Abdul Hamid Digital Engineering A 2’s complement table for 4 bits  Listing the values represented. 2-43 Dr. Tarek Abdul Hamid Digital Engineering Binary Division 1001ten Quotient Divisor 1000ten | 1001010ten Dividend -1000 10 101 1010 -1000 10ten Remainder At every step, shift divisor right and compare it with current dividend if divisor is larger, shift 0 as the next bit of the quotient if divisor is smaller, subtract to get new dividend and shift 1 as the next bit of the quotient 2-44 Dr. Tarek Abdul Hamid Digital Engineering Binary Division 2-45 Dr. Tarek Abdul Hamid Digital Engineering