Computer Science Fundamentals - Basic Theory on Discrete Mathematics (Part 1) PDF

Computer Science Fundamentals - Basic Theory on Discrete Mathematics (Part 1) - AWS Internal Use Only Objectives Understand the numeric representations handled by the computer, including the radix, radix conversion, and arithm...

Computer Science Fundamentals - Basic Theory on Discrete Mathematics (Part 1) - AWS Internal Use Only Objectives Understand the numeric representations handled by the computer, including the radix, radix conversion, and arithmetic operations and precision Understand the basic rules of and techniques for sets, logical operations, and Karnaugh-map Page ▪ 2 AWS Internal Use Only 1  Data Representation in Computers UNIT OF REPRESENTATION Inside computers, data is recorded as electrical signals. Electric signals can basically represent only two states: Is electric current flowing? Is it not flowing? Is voltage high? Is it low? 0 and 1 are linked to these two states, and they are recorded and saved as data inside computers. In other words, data recorded by computers is represented with 0 or 1. The minimum unit that represents this 0 or 1 is called a bit. Various meanings are formed by combining 0 and 1 represented by this bit, and they are recorded as data. At this time, one unit formed by collecting 8 bits is called a byte. Page ▪ 3 AWS Internal Use Only Data Representation in Computers Word is a unit that is formed by collecting more bits than in a byte. It is the unit of processing inside computers, and there are 16 bits, 32 bits, 64 bits, etc. according to the model of computer used. If more bits can be processed at a time, then more information can be processed in a certain time. Therefore, the higher the number of bits in one word, the higher the processing speed of the computer. In most present-day computers, 1 word is 32 bits or 64 bits. Page ▪ 4 AWS Internal Use Only 2  Data Representation in Computers INFORMATION AMOUNT There are two types (0,1) of information that can be represented with 1 bit, and the number of bit combinations is referred to as the information amount. The information amount that can be represented with 2 bits is of 4 types (00, 01, 10, 11), the information amount that can be represented with 3 bits of 8 types (000, 001, 010, 011, 100, 101, 110, 111), … and so on. As shown in the figure, branches increase with the increase of every one bit used, and the information amount that can be represented keeps on doubling. In other words, the information amount that can be represented with n bits is of 2n types (2n shows the power of 2, and means multiplying 2 by itself n times). Page ▪ 5 AWS Internal Use Only Data Representation in Computers Using the concept discussed in previous slide, a summary of the information amount that can be represented with byte and word (16 bits) is given below. Page ▪ 6 AWS Internal Use Only 3  Data Representation in Computers PREFIX When data is handled, rather large numbers are handled as they are. However, it is very difficult to handle very large numbers or very small numbers without modification. Therefore, they are represented in combination with a prefix (auxiliary unit) representing a certain value. [Prefixes used for representing large numbers] [Prefixes used for representing small numbers] Symbol Reading Decimal value Binary value Symbol Reading Decimal value k Kilo 103 210 m Milli 10 -3 M Mega 106 220 μ Micro 10 -6 9 30 -9 G Giga 10 2 n Nano 10 T Tera 1012 240 p Pico 10 -12 P Peta 1015 250 For prefixes that represents large numbers, binary values are also shown. This is because for representing information in binary form by using two numbers 0 and 1, prefixes are also represented in binary form when numbers related to computers are represented. Example: 1k byte = 1 x 210 bytes = 1,024 bytes However, representation would almost equally related to 103 ≈ 210, 106 ≈ 220, … and therefore it is often treated as 1k byte = 1,000 bytes these days. Page ▪ 7 AWS Internal Use Only Radix Systems ❑ Radix is the number that forms a unit of weight for each digit in a numeration system such as binary, octal, decimal, and hexadecimal notations. ❑ Base Systems or Radix Systems: ✓ Decimal system (base 10) 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ✓ Binary system (base 2) 0, 1 ✓ Octal system (base 8) 0, 1, 2, 3, 4, 5, 6, 7 ✓ Hexadecimal (base 16) 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F where A=10, B=11, C=12, D=13, E=14, F=15 Page ▪ 8 AWS Internal Use Only 4  Radix Systems ❑ Decimal numbers that we normally use are numbers that are obtained by raising each digit to the power of 10 by using ten numbers from 0 through 9. Here, the weight (10) of the decimal digit is called radix, and numbers represented with radix n are referred to as n-adic numbers. n-adic numbers are represented by using n numbers from 0 through (n-1) that are carried over when n is reached. Page ▪ 9 AWS Internal Use Only Radix Systems ❑ BINARY NUMBERS Binary numbers are represented by using two numbers 0 and 1 that are carried over when 2 is reached. The smallest unit of information handled inside computers is a bit, and only two numbers of 0 and 1 can be used. Converting a binary number to decimal is multiplying each bit by the weight of the radix (2) then get the sum. Starting from the radix point, in the integer part, the exponent starts from 0. In the fractional part, the exponent starts from -1. Decimal numbers and their corresponding binary numbers are as shown below. Binary numbers can use only two numbers of 0 and 1 for one digit. Therefore, the number of digits quickly becomes large, compared with decimal numbers. Page ▪ 10 AWS Internal Use Only 5  Radix Systems DECIMAL number 2 1 9 9 8 (Radix/Base = 10) Weight 104 103 102 101 100 Value 2*104 1*103 9*102 9*101 8*100 Final (true) value 20000 + 1000 + 900 + 90 + 8 = 2199810 BINARY number 1 1 0 0 1 (Radix/Base = 2) Weight 24 23 22 21 20 Value 1*24 1*23 0*22 0*21 1*20 Final (true) value 16 + 8 + 0 + 0 + 1 = 2510 Page ▪ 11 AWS Internal Use Only Radix Systems ❑ OCTAL NUMBERS Octal numbers are numerical values that are represented by using eight numbers from 0 through 7 and that are carried over when 8 is reached. Converting an octal number to decimal is multiplying each digit by the weight of the radix (8) then get the sum. Starting from the radix point, in the integer part, the exponent starts from 0. In the fractional part, the exponent starts from -1. Page ▪ 12 AWS Internal Use Only 6  Radix Systems ❑ HEXADECIMAL NUMBERS Hexadecimal numbers are numerical values that are represented by using sixteen numbers from 0 through 9, and A(10), B(11), C(12), D(13), E(14), and F(15) and that are carried over when 16 is reached. Converting a hexadecimal number to decimal is multiplying each digit by the weight of the radix (16) then get the sum. Starting from the radix point, in the integer part, the exponent starts from 0. In the fractional part, the exponent starts from -1. Page ▪ 13 AWS Internal Use Only Radix Systems OCTAL number 2 1 7 7 2 (Radix/Base = 8) Weight Value Final (true) value HEXA number A 2 5 7 C (Radix/Base = 16) Weight Value Final (true) value Page ▪ 14 AWS Internal Use Only 7  Radix Systems OCTAL number 2 1 7 7 2 (Radix/Base = 8) Weight 84 83 82 81 80 Value 2 * 84 1 * 83 7 * 82 7 * 81 2 * 80 Final (true) value 8192 + 512 + 448 + 56 + 2 = 921010 HEXA number A 2 5 7 C (Radix/Base = 16) Weight 164 163 162 161 160 Value 10 * 164 2 * 163 5 * 162 7 * 161 12 * 160 Final (true) value 655360 + 8192 + 1280 + 112 + 12 = 66495610 Page ▪ 15 AWS Internal Use Only Radix Conversion ❑ Radix conversion Radix conversion means changing the radix of a numerical value. It is also radix conversion to convert a binary number (radix 2) into an octal number (radix 8) or a hexadecimal number (radix 16). Radix conversion from a BINARY number into a DECIMAL number This can be performed by adding the weight of each digit that is 1 in the binary number. This is the same as adding the results that are obtained by multiplying the weight of each digit with the number (0 or 1) of each digit. Page ▪ 16 AWS Internal Use Only 8  Radix Conversion Radix conversion from a DECIMAL number into a BINARY number This is performed separately for the integer part and the fractional part. The integer part can be converted by repeatedly dividing by 2 until the quotient becomes 0, and then arranging the remainder of calculation results in sequence from the last calculation upwards. A fractional part can be converted by continuously multiplying by 2 until the fractional part in calculation result becomes 0, and then arranging the integer part of each calculation result in sequence from the first calculation downwards. Page ▪ 17 AWS Internal Use Only Radix Conversion Shortcut method of converting decimal (integer) to binary: Descending Powers of 2 and Subtraction 1. List the powers of 2 in a “base 2 table” from right to left. Start at 20, evaluating it as “1”. Increment the exponent by one for each power. Make the list up until you’ve reached a number very near the decimal system number you’re starting with. For this example, let’s convert the decimal number 15610 to binary. 2. Look for the greatest power of 2. Choose the biggest number that will fit into the number you are converting. 128 is the greatest power of 2 that will fit into 156, so write a 1 beneath it for the leftmost binary digit. Then, subtract 128 from your initial number. You now have 28. 3. Move to the next lower power of 2. Using your new number (28), move down the list marking how many times each power of 2 can fit into your dividend. 64 does not go into 28, so write a 0 beneath it for the next binary digit to the right. Continue until you reach a number that can go into 28. 4. Subtract each successive number that can fit, and mark it with a 1. 16 can fit into 28, so you will write a 1 beneath it and subtract 16 from 28. You now have 12. 8 does go into 12, so write a 1 beneath 8’s box and subtract it from 12. You now have 4. 5. Continue until you reach the end of your chart. Remember to mark a 1 beneath each number that does go into your new number, and a 0 beneath those that don’t. 6. Write out the binary answer. The number will be exactly the same from left to right as the 1’s and 0’s beneath your list. You should have 10011100. Page ▪ 18 AWS Internal Use Only 9  Radix Conversion ❑ Summary of radix conversion between decimal numbers and n-adic numbers ❖ Procedure of radix conversion from an n-adic number into a decimal number: Add all results obtained by multiplying the weight (power of n) of each digit by the number {from 0 through (n-1)} of each digit. ❖ Procedure of radix conversion from a decimal number into an n-adic number: Integer part: Repeatedly divide by n until the quotient becomes 0, and then arrange the remainder of calculation results in sequence from the last calculation upwards. Fractional part: Continuously multiply the fractional part by n until the fractional part in calculation result becomes 0, and then arrange the integer part of each calculation result in sequence from the first calculation downwards. For example, this is radix conversion of the decimal number (67.6875)10 into an octal number. Page ▪ 19 AWS Internal Use Only Radix Conversion Note: When the radix conversion from decimal to octal or hexadecimal is performed, it may be easier to convert from decimal to binary, and then convert the result into octal or hexadecimal. ❑ Fractional number that cannot be represented by the infinite number of digits When the fractional part of a decimal number is converted into an n-adic number, it gets into a loop as the fractional part of calculation results does not become 0, and it may not be converted into a finite fraction. For example, converting the decimal number (0.2)10 into a binary number gives the following: In this manner, when the results of radix conversion become an infinite fraction (or recurring fraction), numerical values are handled as approximate values inside the computer. Page ▪ 20 AWS Internal Use Only 10  Radix Conversion ❑ Relation between binary numbers, octal numbers, and hexadecimal numbers Binary numbers have an extremely large number of digits compared with decimal numbers. Although computers can handle binary numbers without problems, it is very difficult for a human being to understand when the internal status of computers is concerned. Therefore, octal numbers and hexadecimal numbers are used so that people can understand more easily. Octal numbers use the power of 8 (=23) as the weight of each digit, and therefore the information of 3 digits of binary numbers corresponds to 1 digit of octal numbers. Page ▪ 21 AWS Internal Use Only Radix Conversion Hexadecimal numbers use the power of 16 (=24) as the weight of each digit, and therefore the information of 4 digits of binary numbers corresponds to 1 digit of hexadecimal numbers. Page ▪ 22 AWS Internal Use Only 11  Arithmetic of Number Systems Binary Addition Binary Subtraction 0 + 0 = 0 (or 010) 0–0=0 0 + 1 = 1 (or 110) 0 – 1 = -1 1 + 0 = 1 (or 110) 1–0=1 1 + 1 = 10 (or 210) 1–1=0 Page ▪ 23 AWS Internal Use Only Arithmetic of Number Systems Hexadecimal Addition Addition is performed starting at the first digit (from the right). When the addition result is higher than 16, a carry to the upper digit is performed. Page ▪ 24 AWS Internal Use Only 12  Arithmetic of Number Systems Hexadecimal Subtraction Subtraction is performed starting at the first digit (from the right), and when the subtraction result is negative, a borrow from the upper order column is performed. Page ▪ 25 AWS Internal Use Only Arithmetic of Number Systems Hexadecimal Multiplication 25 50/16 = 3 (3x16 = 48) x 3A The quotient 3 will carry-over to the next operand (35), making it 38 20 50 38/16 = 2 (2x16=32) + 6 15 The quotient 2 will carry-over to the next operand (6), making it 8 2 3 8/16 = 0 6 35 50 - 0 32 48 8 6 2 base 16 Same procedure applies in Octal multiplication. Just remember to use the radix 8 when doing the integer division, and when multiplying with the quotient. Page ▪ 26 AWS Internal Use Only 13  Arithmetic of Number Systems Exercise: ▪ SET 1: Compute the following a) 2710 + 1510 b) 110112 + 11112 c) 338 + 178 d) 1B16 + F16 ▪ SET 2: Compute the following a) 5010 – 2210 b) 1100102 - 101102 c) 628 – 268 d) 3216 - 1616 Page ▪ 27 AWS Internal Use Only Arithmetic of Number Systems Exercise: ▪ SET 1: Compute the following Answers: a) 2710 + 1510 a) 4210 b) 110112 + 11112 b)1010102 c) 338 + 178 c) 528 d) 1B16 + F16 d) 2A16 ▪ SET 2: Compute the following a) 5010 – 2210 a) 2810 b) 1100102 - 101102 b)111002 c) 628 – 268 c) 348 d) 3216 - 1616 d) 1C16 Page ▪ 28 AWS Internal Use Only 14  END OF 1ST PART Page ▪ 29 AWS Internal Use Only 15