Bnf - MyIoT



CSCI 1802Computer Systems and NetworksPart 1: Computer Number SystemsReferences and further reading:Blundell B: Computer Systems and NetworksPatt & Patel: Introduction to Computing Systems pp 1 – 50Ceri, Mandroli, Sbattella: The Art & Craft of ComputingComputer Number Systems1MotivationAt the lowest level a computer has an electronic component that stores either a high voltage, or a low voltage. We take a high voltage to represent the digit 1, and a low voltage to represent the digit 0. So now we have a very simple and very limited counting device. With two such components we have four states: 00,01,10 and 11. These four states can represent the numbers 0, 1, 2, 3. Similarly with 3 components we can represent eight states: 000,001,010,011,100,101,110 and 111. These eight states can represent the numbers 0, 1, 2, 3, 4, 5, 6 and 7.1.1QuestionHow many states are there with:four components?five components?six components?seven components?eight components?What is the pattern?When computer scientists and engineers work at the level of the computer, they represent numbers using binary digits 0, 1. As shorthand they use octal digits (0,1,2,3,4,5,6,7) to represent a group of 3 binary digits; or hexadecimal digits (0,1,2,3,4,5,6,7,8,9,A, B, C, D, E, F) to represent a group of 4 binary digits.The first section explains how to work with these number systems.First, we must be able to understand raising a number to a power.Can you do the following (without a calculator!)? (Note that any number to the power 0 equals 1 i.e. n0 = 1) 22 = 23 = 32 = 33 = 104 =20 = 50 =10-2 = 2-2 = 10-5 = 3-3 = 21/2 = 20.5 = 21/3 = 2Radix (or Base)Numbers are written using a place system, e.g. Hundreds, Tens and Units. For example, 123 is the number where 1 represents one 100, 2 represents 2 tens, and 3 represents 3 units (or ones). Altogether the number is 100+20+3. Each place in the number system is 10 times larger than the previous place. This idea can be extended to other number bases.Decimal is base 10 (or radix 10) and uses the symbols 0 1 2 3 4 5 6 7 8 9 The number 271 is 2×102 + 7×101 + 1×100Binary is base 2 (or radix 2) and uses the symbols 0 1 The number 011012 is 0×24 + 1×23 + 1×22 + 0×21 + 1×20 Octal is base 8 (or radix 8) and uses the symbols 0 1 2 3 4 5 6 7 The number 51728 is 5×83 + 1×82 + 7×81 + 2×80Hexadecimal is base 16 (or radix 16) and uses the symbols 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 The number 5A1B16 is 5×163+ 10×162+ 1×161+ 11×160= 20480+ 2560 + 16 + 11 = 2306710 Ref: Blundell pp10-13, pp36-39 Exercises1. List some of the different number bases you use in everyday life. Hint: think about time …3To Translate from one base to another3.1Binary to Decimal As illustrated above, starting at the right hand side, the digits represent increasing powers of 2. 111010012= 1×27 + 1×26 + 1×25 + 0×24 + 1×23 + 0×22 + 0×21 + 1×20 = 128 + 64 + 32 + 0 + 8 + 0 + 0 + 1 = 23310 The easiest way is to use a table. e.g. to convert 111010012Powers of 22726252423222120Decimal value of each bit1286432168421Example binary number11101001Value of each bit in the exampleSum of the valuesHere’s a more complicated example:01011011111010012 = 0+16384+0+4096+2048+0+512+256+128+64+32+0+8+0+0+1=?2352910 We can write this as a table as shown below.Powers of 221521421321221121029282726252423222120Decimal value of each bit327681638481924096204810245122561286432168421Example binary number0101101111101001Value of each bit in the example0163840409620480512256128643208001Sum of the values= 16384 + 4096 + 2048 + 512 + 256 + 128 + 64 + 32 + 8 + 1 = 235293.2Binary to OctalStarting from the right hand side, divide the number into groups of 3 digits, and then convert each group into an octal value. This works because 3 binary digits represent the range of values from 0 to 7, i.e. all the octal digits.01011011111010012= 0 101 101 111 101 0012 = 0 5 5 7 5 1 = 0557518 3.3Binary to Hexadecimal Starting from the right hand side, divide the number into groups of 4 digits, and then convert each group into a hexadecimal value. This works because 4 binary digits represent the range of values from 0 to 15, i.e. all the hexadecimal digits.01011011111010012= 0101 1011 1110 10012= 5 B E 9 = 5BE916 3.4Decimal to Binary 3.4.1Either... Subtract from the original number the highest power of 2 that does not exceed the value of the number, put a 1 in the corresponding bit position.? Then continue down through the powers of 2 inserting 1's or 0's in the corresponding positions. (A table of powers of 2 helps here.)Powers of 22726252423222120Example: To convert 75 to binary:Decimal value of each bit128643216842164 is the highest power of 2 not greater than 75 64 = 26? 0100000075 - 64 = 11Using 6418 is the highest power of 2 not greater than 11 8 = 23? 0100100011 - 8 = 3Using 811then, following on in the same way 2 = 21 010010103 - 2 = 1 Using 2111 1 =?20 010010111 - 1?= 0Using 11111Put 0 in gaps010010113.4.2...Or Successively divide the number by 2 and use the remainders as the binary digits (from right to left) Thus75/2 gives 37 remainder 1???? ???? 137/2 gives 18 remainder 1???????? 1118/2 gives? 9 remainder 0????????011 9/2 gives? 4 remainder 1???????1011 4/2 gives? 2 remainder 0??????01011 2/2 gives? 1 remainder 0?????001011 1/2 gives? 0 remainder 1??? 1001011Pad out with 0's (on the left hand side) to make the binary number the width you require.7510= 01001011Note: If you use this method, it is a good idea to always check your answer by converting your result back to decimal.3.5Decimal to Octal Convert the number to binary then convert the binary number to octal. 3.6Decimal to Hexadecimal Convert the number to binary then convert the binary number to hexadecimal. 3.7ExerciseWhat are the smallest and largest positive whole numbers represented by:4 bits? i.e. 0000 to 1111 ? 8 bits?16 bits?32 bits?4Representation of Negative numbers So far when looking at binary numbers we have been looking at unsigned integers. We have to be able to handle negative numbers. In decimal notation we use the minus symbol (-) to denote a negative number. But a computer can only use binary symbols i.e. 0's and 1's. There is no extra symbol to represent a minus sign. So we must use one of the bits to represent or indicate a negative value.There are four common ways of representing negative binary numbers. Signed magnitudeOne's complementTwo's complementBiased value4.1Signed magnitude (or Sign/modulus). The leftmost bit is the sign bit. It is 0 for positive, or 1 for negative. +29 is represented by? 000111012 sign6432168421(+)00011101(+) 0×64 + 0×32 + 1×16 +1×8+ 1×4 + 0×2 + 1×1-29 is represented by? 100111012 sign6432168421(-)10011101 (-) 0×64 + 0×32 + 1×16 +1×8+ 1×4 + 0×2 + 1×14.2One's complement. The leftmost bit represents a negative value. But instead of representing the minus symbol, in an 8-bit one’s complement binary number, a 1 in the leftmost place represents the value, -127.-29 is represented by 111000102 -127643216842111100010i.e.1×-127 + 1×64 + 1×32 + 0×16 + 0×8+ 0×4 + 1×2 + 0×1 = -127 + 98= -29This system is popular because it is easy to change a binary number to a negative equivalent.To negate a binary number in one’s complement,- just work out the positive representation- then flip the bits. i.e. change all 0's to 1's and all 1's to 0's. A computer can do this very quickly.Example: -84 in 1’s complement: +84 is represented by = 010101002 -84 is represented by = 101010112 i.e. -84 = -127 + 43Of course this will only work for numbers in the appropriate range you need to know how many bits are being used.4.3Two's complement. This is very similar to one's complement. The only difference is that the leftmost bit is -2n rather than -2n +1, e.g. for an 8-bit number it is -128 rather than -127. This is a little more consistent with the place value system, so that the leftmost place value represents a negated power of two.e.g. -29 is represented by? -127 + 98 = 111000102 in one's complement. = -128 + 99 = 111000112 in two's complement.Another example: +84 and -841. Using the place values methodIn One’s complement (and in Two’s complement):+84 is represented by 64+16+4= 010101002-127643216842101010100. In One’s complement:-84 is represented by -127+43 = -127+32+8+2+1 = 101010112-127643216842110101011In Two’s complement:-84 is represented by -128+44= -128+32+8+4= 101011002 -128643216842110101100 2. An easier way to get a negative value in two’s complement is to use the algorithm:- create the positive binary number using one's complement- convert it to negative by flipping the bits - then add one to the result to get the two’s complement valueFind +84 in 1’s Comp1’s Comp-1276432168421+8401010100Flip the bits to get –ve value in 1’s complement 1’s Comp-1276432168421-8410101011Add one to get –ve value in 2’s complement2’s Comp -1286432168421-84101011004.4Biased value (Excess 127)Excess 127 is usually used for 8 bit representations, other values can be used for different numbers of bits. (e.g. Excess 1023 for 11 bits.) In Excess 127, we represent every number by a value that is 127 larger. i.e. (the number + 127) For example: -127 is represented by -127 + 127 = 0-50 is represented by -50 + 127 = 77,+20 is represented by 20 + 127 = 147This means that numbers from -127 upwards will be represented by a positive value. So, in Excess 127 the binary representation is always 127 larger than it really is. We need to remember this when converting back from binary to decimal !!-29 is represented by -29 + 127 = 9810 = 011000102 -84 is represented by -84 + 127 = 4310 = 001010112 +29 is represented by +29 + 127 = 15610 = 100111002 4.5Exercise1. Give five different interpretations of the binary number 101010102 . 2. Complete the table below to show the smallest and largest values of 8-bit binary numbers using each of the four representations stated.8 bitsSmallest valueLargest valueBinaryDecimal Binary Decimal1. Signed magnitude 01111111 = 1272. One's complement 10000000 = -1273. Two's complement4. Excess 1273. Repeat this for 16-bit numbers. [Hints: 215 = 32768 ; Would we use Excess 127 or something else?]5Addition and Subtraction in Binary5.1Simple addition of positive integersIn decimal addition we 'carry' when the result is greater than 9. 'Carrying' works because when we get ten values in the 10n place then we have 10×10n which is the same as 1×10n+1 . e.g. 10×102 =1×103 .In binary addition we 'carry' when the result is greater than 1, e.g. 1 + 1 + 1 + 0 1 1 1 1 0 11 1Thus,27 26 25 24 23 22 21 20102 101 1000 1 0 1 1 0 0 1 + 8 9 +0 1 1 1 0 1 0 1 1 1 7 =1 1 0 0 1 1 1 0 2 0 6 This works well for unsigned positive numbers. 5.2Arithmetic using positive and negative integersFirst, try the following simple decimal additions and subtractions. Note we are using the convention here that a raised minus sign indicates a negative number e.g. –3 means negative 3, whereas -3 means subtract 31 + 3 =3 – 1 =1 – 3 =–1 + 3 =1 – –3 =3 + –1 =1 + –3 = –1 – –3 =1 + – (–3) = Question: Is subtracting X the same as adding –X?Yes. Extending this to binary arithmetic we can simplify subtraction of binary numbers by adding a negative representation of the number (e.g. two's complement). Using two’s complement representation we can add and subtract both positive and negative numbers by always using the add operation.REMEMBER: In 2’s complement:a positive value is unchanged e.g. +40 = 32 + 8 = 00101000a negative value has the positive value changed to the negative value by the process we’ve just learnt e.g. -40 = - (32 + 8) = - 00101000= 11010111+1 = 110110005.3Addition and subtraction examplesExample 1: adding 2 positive valuese.g. 5 + 12decimal2’s complement +500000101 +1200001100 + +1700010001Check the answer is correctExample 2: subtracting second number from first numbere.g. 5 – 12 = 5 + –12decimal2’s complement +500000101 –1211110100 + –711111001Check the answer is correctExample 3:Here is an example where there is a decimal 2’s complement‘carry’ on the left hand side of the result. –5 11111011Because the two operands have different +12 00001100 +signs, the carried 1 is simply ignored. +7 [1]00000111 sum = +7Example 4:However, in this example, where the decimal 2’s complementtwo operands both have the same sign, –80 10110000the carried 1 on the left hand side of the –64 11000000 +result and the fact that result is a different –144 [1]01110000 sum= +112sign to both operands indicates that there has been an overflow and the result is wrong.5.4ExerciseBy considering the column values, (i.e. –128, 64, 32 etc) explain what has occurred in the last two examples.6Some effects when using finite-precision numbers (i.e. using computers)6.1Overflow, Underflow and RoundingSay a computer uses 8 bits to represent integers then the range of values that can be stored (assuming we use 2's complement) is -128 to +127.Thus a computer using 8 bits to store integers cannot do every arithmetic calculation you might want to give it.Examples:2 + 2=4(correct)70 + 70=140(too big to be represented: integer overflow)5 × 5=25(correct)5 × 50=250(too big: integer overflow)50 – 95=-45(correct)-50 – 95= -145 (too big negative: negative overflow)4 / 2=2(correct)5 / 2=2.5(not an integer, so cannot be stored as an integer except by rounding or truncating it)6.2DefinitionsInteger overflow: Result too big (+ve)Negative overflow: Result too big (–ve)Rounding:Result cannot be stored exactly, so nearest valid value is stored.Rounding error: Difference between correct value and calculated value.Relative error: Rounding error(i.e. Rounding error divided by Correct value) Correct value6.3Effect of order of calculations when using finite-precision numbers (i.e. using computers)In these examples, assume 8-bit two's complement representation of integers. (Therefore, the range of values is -128 to +127)6.3.1Example 1: Calculate a + b – cMethod 1)calculate b – c then add aMethod 2)calculate a + b then subtract c[ Associative law states: a + ( b – c ) = ( a + b ) – c]Using a = 80, b = 50, c = 30Method 1) 80 + (50 – 30) = 80 + 20 = 100Method 1 gives correct answerMethod 2) (80 + 50) – 30 = (overflow) – 30 = ?Method 2 gives wrong answer!6.3.2Example 2: Calculate a * ( b – c )Method 1)calculate b – c then multiply by aMethod 2)calculate a * b then subtract a * c[ Distributive law says: a * ( b – c ) = ( a * b ) – ( a * c )]Using a = 8, b = 40, c = 30Method 1) a * ( b – c ) = 8 * (40 – 30 ) = 8 * 10 = 80Method 1 gives correct answer.Method 2) ( a * b ) – ( a * c )= ( 8 * 40 ) – ( 8 * 30 )= 320 – 240 (overflow) – (overflow)= (garbage) ?Method 2 gives wrong answer!6.4Arithmetic – computers vs humansThe conclusions from section 6 of this booklet are:1. Arithmetic using computers is not the same as arithmetic done by people.2. It is important to understandhow computers work their limitations7Binary Representation of Characters7.1ASCII Character codesCharacters like 'a', 'b', 'c', '2', '!' are represented by number codes. ASCII (American Standard Code for Information Interchange) is a code used to encode characters. Standard ASCII uses 7 bits and allows 128 characters to be represented. Extended ASCII uses 8 bits and allows 256 characters to be represented. An additional 8th or 9th bit might be used as a parity bit, which is used to detect errors. odd parity - the parity bit is set to 0 or 1 to give an odd number of 1's in total.even parity – the parity bit is set to 0 or 1 to give an even number of 1's in total.Standard characters that can be encoded are:Command charactersNon-printing transmission and printer control codes 00..1F HexAlphanumeric characters{0 .. 9} codes 30.. 39 Hex{A .. Z} codes 41..5A Hex{a .. z} codes 61..6A HexSymbolspunctuation and arithmetic characterse.g. the space character is 20 in HexASCII codes for printable characters (Note that the codes are given here in Hexadecimal - why is that?)Hex0123456789ABCDEF2!"#$%&'()*+,-./30123456789:;<=>?4@ABCDEFGHIJKLMNO5PQRSTUVWXYZ[\]^_6`abcdefghijklmno7pqrstuvwxyz{|}~Example: To get the ASCII binary code for the letter Q1. Get the hex code for Quse the value down the left = 5use the value along the top = 1this gives the value 51 in hex2. Convert the hex value 51 into binary5 is 01011 is 0001put them together to get 010100013. Hence the ASCII code for the letter Q is 01010001 in binary.7.2ExampleAssuming 8-bit extended ASCII encoding, give the binary pattern that represents the sequence of characters "Hello Joe".Answer:CharHelloJoeHex48656C6C6F204A6F65Binary010010000110010101101100011011000110111100100000010010100110111101100101Doing the same example using 'odd parity' we would get:CharHelloJoeHex48656C6C6F204A6F65Binary010010000110010101101100011011000110111100100000010010100110111101100101Parity bit1111100117.3ExerciseFill in the gaps to do the same example using 'even parity'CharHelloJoeHex48656C6C6F204A6F65Binary010010000110010101101100011011000110111100100000010010100110111101100101Parity bit7.4Discussion questionHow do you know whether a number in a computer's memory cell represents a number or a character code?7.5UnicodeHere is a brief timeline showing character representation developmentsASCIIdominant since 1970’s7 bits -> 128 charactersISO 646 (in 1972)national variants e.g $, ?, é but ? in UK .. # in US8-bit ASCIIuse all 8 bits for character representationdata transmission more reliablebetter ways of transmission error checksso don’t need parity bitbut manufacturers developed their own extensions to the standardstandard ASCII characters + extra characters – non-compatible!Multi-part ISO 8859 (1980’s)ISO 8859-1: (ISO Latin-1): most W EuropeISO 8859-2: E Europe ) Czech, SlovakISO 8859-7: Greek, etcISO 10646ISO standard32 bit character set => 232 charactershypercube groups, planes, rows, columnscharacter -> (g,p,r,c)Unicodeindustry consortium16 bit character set => 65,536 charactersCJK Consolidation (Chinese, Japanese, Korean)contemporary major languagessymbols, maths, dingbats …mechanism to build composite characters reserved codes for expansion & private symbolsIn 1991: Unicode & ISO 10646 made compatibleISO agreed BMP (Basic Multilingual Plane) (0,0,*,*) identical to UnicodeCurrent:Unicode 5.1 provided codes for 100,713 characters.Now matches ISO 10646 standard 32 bit representationThe 8 bit character representation on most computers is now Latin-1. However this misses out large chunks of the world. For this reason other coding formats based on the Unicode/ISO 10646 standard are used. In order to save storage space a 32 bit coding is not in standard use. Instead people tend to use multi-byte encoding schemes such as UTF-8. In some areas of computing (HTML, XML, Java … ) direct reference to Unicode is made via expressions like &#xABCD, &#140 or \uXXXX.7.6 UTF-8Rules for UTF-8 are designed to reduce the size of files in order to save both storage and transmission time over networks. The way it does this is to store the ASCII range of characters as themselves and store other characters as 2, 3 or 4 bytes as needed. The formats look like this:0XXXXXXXThis represents the ascii char 0XXXXXXX.110XXXXX10YYYYYY represents the Unicode character 00000XXXXXYYYYYY1110XXXX10YYYYYY10ZZZZZZ represents the Unicode character XXXXYYYYYYZZZZZZ.An important property of Unicode encodings like UTF-8 is that there are no overlaps – when searching for a character if you encounter a matching byte-sequence you know that it is the character you are searching for. In some coding schemes you might have found part of another character.Here is how the coding is described in the Unicode UTF-8 specification.Notice how the first byte gives the information on how many bytes are used to code the character. The saving in file size is obviously dependant on the language used (and for some languages it will have a negative effect). Other encodings are also available (UTF-16 and UTF-32).8Storage of data in computer memory8.1Bits, Bytes and WordsThe examples of rounding errors and overflow described in Section 6 arise because of the way that data is stored in computer memory.We are already familiar with binary digits (called bits). One bit is one binary digit which can take a value of 0 or 1. Another unit of data is the byte which is a sequence of 8 bits. Thus one byte can produce 28 (= 256) different values (0 to 255). These values can be used as codes. Different representations are used to code different kinds of data.A word is the smallest addressable unit of computer memory, and depending on the machine and software might be 16 or 32 or 48 or 60 or 64 bits.1 Kilobyte (1Kb) = 1024 bytes = 210 bytes1 Megabyte = 1,048,576 bytes = a kilobyte of kilobytes = 1024 x 1024 bytes = 220 bytes1 Kilobyte is approximately 1000 bytes, 1 Megabyte is approximately 1 000 000 bytesWe now frequently use Gigabytes and Terabytes as measures of size. How big are they?8.2Representation of primitive C typesThe C programming language has several primitive data types. The way they are represented is machine- and implementation-dependent. However, typical descriptions (ref: Kernighan & Ritchie: The C Programming Language) are given below.DatatypeDescriptionDescription/Typical valuescharCharacter, not necessarily printable1 byte ASCII codeintInteger value-32767 to +32767 i.e. -215-1..215-1shortA short int but …often the same as intlongA long int-2147483647 to +2147483647 i.e. -231-1..231-1floatReal (or floating point) value6 decimal digits of precision, min value 1E-37, max value 1E+37,smallest value x such that 1+x 1 is 1E-5doubleDouble precision floating point value10 decimal digits of precision,min value 1E-37, max value 1E+37,smallest value x such that 1+x 1 is 1E-9long doubleExtended precision floating pointmachine/implementation dependent 8.3ExerciseHow many bytes are required for each of these data types? Use the final column to help you fill in the blanks.DatatypeNo of bytes requiredDescription/Typical valueschar1 byte ASCII codeint-32767 to +32767 i.e. -215...215-1shortoften the same as intlong-2147483647 to +2147483647 i.e. -231...231-1floatto be discussed in the next section6 decimal digits of precision, min value 1E-37, max value 1E+37,smallest value x such that 1+x 1 is 1E-5doubleto be discussed in the next section10 decimal digits of precision,min value 1E-37, max value 1E+37,smallest value x such that 1+x 1 is 1E-9long doublemachine/implementation dependentmachine/implementation dependent8.4Further reading Blundell, B: pp 67-82Ceri, Mandroli, Sbattella: The Art & Craft of Computing, Sections 13.1-13.4.1, pp 312-3209Representation of Fractional NumbersFractional numbers are numbers between 0 and 1. Their representation in decimal or binary simply uses negative powers of the base. Recall that a-n = 1/anFor example:10-1 = 1/101 = 1/10 = 0.12-1 = 1/21 = 1/2 = 0.510-2 = 1/102 = 1/100 = 0.012-2 = 1/22 = 1/4 = 0.2510-3 = 1/103 = 1/1000 = 0.0012-3 = 1/23 = 1/8 = 0.12510-4 = 1/104 = 1/10000 = 0.00012-4 = 1/24 = 1/16 = 0.062510-5 = 1/105 = 1/100000 = 0.000012-5 = 1/25 = 1/32 = 0.03125etc.The number 0.42610 is 4×10-1 + 2×10-2 + 6×10-3 + 1×10-4 The number 0.011012 is 0×2-1 + 1×2-2 + 1×2-3 + 0×2-4 + 1×2-59.1To translate fractional binary to fractional decimalSimply work out the sum using the decimal or fractional values of the bits.e.g.0.011012= 0×2-1 + 1×2-2 + 1×2-3 + 0×2-4 + 1×2-5 = 0 + 0.25 + 0.125 + 0 + 0.03125 = 0.40625(or 0.011012= 1/4 + 1/8 + 1/32 = 13/32 = 0.40625)A table can be used, similar to the one used to work out integer values.Powers of 2.2-12-22-32-42-52-62-72-8Fractional value of each bit1/21/41/81/161/321/641/1281/256Decimal value of each bit0.50.250.1250.06250.031250.0156250.00781250.00390625Example binary number.01101000Value of each bit in the example00.25or1/40.125or 1/800.03125or1/32000Sum of the values0.25 + 0.125 + 0.03125 = 0.40625 or 1/4 + 1/8 + 1/32 = 13/32 ( = 0.40625 )9.2To translate fractional decimal to fractional binary9.2.1Either...Successively subtract the highest possible value of negative power of 2e.g.0.42510 - 0.25 = 0.175(2-2= 0.012)0.175 - 0.125 = 0.05(2-3= 0.0012)0.05 - 0.03125 = 0.01875(2-5= 0.000012)etcwhich gives 0.01101 to an accuracy of 5 binary digits after the point.This can be done using a table as before:To convert 0.425 to binaryPowers of 2.2-12-22-32-42-52-62-7Decimal valueof each bit0.50.250.1250.06250.031250.0156250.00781250.425 - 0.25 = 0.175Using 0.2510.175 - 0.125 = 0.05Using 0.12510.05 -0.03125 = 0.00875Using 0.0312510.00875 - ? etcPut 0 in gaps.011019.2.2...OrSuccessively multiply the fractional part of the decimal value by 2 and move the integer part of the result onto the end of the binary number (from left to right after the point)e.g.0.425 × 2 = 0.85gives0.00.85 × 2 = 1.7gives0.010.7 × 2 = 1.4gives0.0110.4 × 2 = 0.8gives0.01100.8 × 2 = 1.6gives0.01101etcNote: If you use this method, it is a good idea to always check your answer by converting your result back to decimal.(Exercise: explain why this method works!).9.2.3Rounding ErrorThis example also demonstrates that it is not always possible to translate a decimal value exactly into a specific number of binary digits. (Continue with the conversion until you convince yourself that this is the case.) The result of the translation here, if left with 5 binary digits, will have a rounding error of 0.0187510.We tried to convert 0.42510 and the result was 0.011012 (to 5 binary digits)We can calculate that 0.011012 = 0.4062510Therefore, the rounding error is:0.425 - 0.40625 = 0.018751010Representation of Real NumbersReal numbers (or rational numbers) contain both an integer part and a fractional part. For example, 23.714 has an integer part of 23 and a fractional part of 0.714 .A binary fractional number may look like 01101.10012. How can this 'real' binary number be stored in a computer which does not have a decimal point symbol?10.1Fixed point representationOne solution is to assume that the decimal point is in a fixed position. This is called a fixed point representation with a fixed number of bits each for the integer and fractional part. For example, we could assume that in an eight bit number the decimal point is always such that there are 5 bits for the integer part and the remaining 3 bits for the fractional part. So if we put the point in, then 10011101 represents 10011.101, Integer part 10011 gives 19, Fractional part 0.101 gives 0.625Thus 10011101 would represent the real number 19.62510.2Exercise1. What number would 10011101 represent if the (integer, fractional) split is (6, 2) ?(4, 4) ?2. What are the smallest and largest values that can be represented with each possible split:(0,8), (1,7), (2,6), etc.10.3Normalised floating point representationThe more usual encoding of real numbers in binary is using a normalised floating point representation. We will explain the term ‘floating point’ using both decimal and binary notation and then go on to explain ‘normalized floating point representation’ of binary real numbers.10.3.1Floating point representationIn decimal we can write values as a number multiplied by 10 to some power.e.g. –241.65 = –0.0024165 × 105= –0.024165 × 104= –0.24165 × 103= –2.4165 × 102= –24.165 × 101= –241.65 × 100= –2416.5 × 10-1= –24165.0 × 10-2etcThus the position of the decimal point can ‘float around’, giving the term ‘floating point’.In binary, we are now working on powers of 2 instead of powers of 10. Thus,110.11= 1.1011 × 22= 0.11011 × 23 = 0.011011 × 24= 0.0011011 × 25= 11011.0 × 2-2= 1101100 × 2-3etcWe are interested in the value that starts with a single 1 followed by the decimal point (or more correctly the binary point). This is what we call the normalized binary value.10.3.2Mantissa and ExponentFloating point representation uses 2 values to represent a number and these are given the names: the mantissa and the exponent.The mantissa (sometimes called the fraction) is the fractional part of the number.The exponent (sometimes called the characteristic) is the power of 2 the mantissa must be multiplied by to get the original value.10.3.3Binary Normalised Floating PointFirst, we normalize our binary numbers so that they always start with 1.Because they always start with 1. , for efficiency of storage, the 1 and the point don’t have to be stored (but the system has to know that they have to be replaced when extracted from storage).Binary valueNormalised valueMantissaExponent11.010 1.1010 × 2+1 1010+1 0.00011 1.1 × 2-4 1000-4 0.010101 1.0101 × 2-2 0101-2 1.101 1.101 × 20 10100Thus, each of the values in the table above can be stored using the values of the mantissa and the exponent.This is the basis of how real numbers are stored in computers using the IEEE 754 standard.10.4IEEE 754 Standard Representation of Real NumbersThis is now the standard way of representing real (binary) numbers in computers. For single precision, there are a total of 32 bits used as shown here.No of bits1823ComponentS(sign)E (exponent)F (fraction or mantissa)Bit Number(s)3130 -------- 2322 -------------------------- 0S - the sign of the number, is 0 for positive or 1 for negativeE - the exponent, uses Excess 127 representation (i.e. Excess 27-1) and can take values between 1 and 254, equivalent to a range of -126 to 127. (The values 0 and 255 are reserved for special cases.)F - the mantissa, uses a normalised representation as described above. The leading one and the decimal point are omitted (because they can be assumed to be present). F should more correctly be called the significand.Zero is a special number and is represented by values of E=0 and F=0 (with S taking the value of either 0 or 1).For more detailed understanding of the IEEE 754 Standard Representation of Real Numbers you are recommended to read the reprint of a web article which is given after the following exercises.This article will also help you with the tutorial exercises.10.5Exercises: A reprint of a web article is included next. Read this to find out what is meant by NaN and how NaN is represented in the IEEE standard.Use the example given to help you to represent the decimal value 132.2 as a single precision IEEE 754 number.Find out if there is a C library that allows you to use infinity and NaN.Representing Real Numbers1. BackgroundReal number representation in a fixed-size word represents a challenge because they can have a varying number of decimals and an enormous range. As early as 1945, John von Neumann realised that, because of round-off errors, it would be impossible to represent real numbers exactly, as was done for integers, and he even suggested that computers should not deal with such numbers! On the hardware side, designers were reluctant to incorporate real number support in their processors because that would have a severe impact on performance and occupy valuable real estate on the processor chip. The evolution of real number representation went through a number of controversies and backward steps before a standard (IEEE 754 / 854) finally emerged in 1985. And while so many people contributed to this development over the years, it is widely believed that the work of William Kahan, which started at the University of Toronto in 1953, was instrumental, and for that, he was awarded the Turing Award in 1989.2. ObjectivesThe goals of the IEEE standard are twofold:Strike a compromise between range and accuracyMinimize floating-point hardware by exploiting the integer unit h/w.3. Single-Precision IEEE 754The number is represented in 32 bits (4 bytes) using the following format:S is the sign of the number (1=minus, 0=plus), contributing (-1)S. E is the biased exponent, contributing 2(E-127). It is represented as an 8-bit unsigned integer, and thus, have the range 0 through 255. F is the binary fraction (mantissa or significand), contributing 1.F; i.e. an implicit 1 and a binary point are not represented but assumed present. Together with the implicit 1, 24 bits are thus significant. Since a decimal digit can be represented in between 3 and 4 bits, we can see that this single-precision representation produces about 7 significant digits. This standard achieves the 1st goal by using powers of 2 instead of 10. It also realises the 2nd goal because of the way it orders the field and represents the exponent: Since S is in the most significant bit, it is easy to perform a test of less than, greater than, or equal to 0 using integer unit hardware. Placing the exponent E before the mantissa also allows us to sort floating-point numbers using integer comparison instructions, as long as all exponents are non-negative. In fact, this is why the standard uses biased (or excess 127) notation instead of 2's complement.The exponent E ranges between 0 and 255 but the end points of this interval are reserved for special values (see below). Hence, the allowed range of E is 1 though 254 which gives a magnitude range (in absolute value) of about:2(1-127) = 2-126 = 10-38 to 2(254-127) = 2(127) = 10+38Special Values:The fact that 1. is implicit means that the number zero cannot be represented and, hence, a special value must be set aside for zero. This (zero) value is: E = F = 0 (regardless of S). Furthermore, instead of issuing an exception when a divide by 0 is attempted, the standard allows software to set special values to indicate plus or minus infinity, thus providing for topological closure in real arithmetic. These (infinity) values are: E = 255, F = 0, S = 0 / 1. The results of invalid operations (such as 0/0 or infinity minus infinity) are indicated by a special value in the standard known as NaN (Not a Number), thus allowing program to proceed with a number of operations and postpone some tests and decisions to a later time in the program.This (NaN) value is: E = 255, F not = 0 (regardless of S). The standard realises that there is a gap between 0 and the smallest positive (and largest negative) number that can be represented, and allows some numbers in this gap to be represented. Supporting such a gradual underflow means that we abandon our implicit 1. premise and replace it by 0. Such numbers are denormalized and can be as small (in absolute value) as about 2-23 x 2-126 = 2-149 = 10-45. Due to their departure from the premise, most processor makers do not support this optional feature of the standard.These (denormalized) numbers have: E = 0, F not = 0, S = 0 / 1.4. Double-Precision IEEE 754This 64-bit (8 bytes) representation provides added accuracy and increased range but uses the same idea as single-precision. Here are the differences:11 bits for E (with a bias of 1023) and 52 bits for F. Aside from special values, E ranges between 1 and 2046. The range is thus: 2-1022 (about 10-308) to 2-1023 (about 10+308). Based on 52+1 significant bits, the accuracy is about 15 (decimal) digits. Special Values:E = 0, F = 0 (zero)E = 0, F not 0 (denormalized)E = 2047, F = 0 (infinity)E = 2047, F not 0 (NaN)5. ExampleRepresent 19.2 as a single-precision IEEE 754 number:19 / 2 = 9 R 1 9 / 2 = 4 R 1 4 / 2 = 2 R 0 2 / 2 = 1 R 0 1 / 2 = 0 R 1Hence 19 = 100110.2 * 2 = 0.40.4 * 2 = 0.80.8 * 2 = 1.60.6 * 2 = 1.20.2 * 2 = 0.40.4 * 2 = 0.8Hence 0.2 = 001100110011..19.2 = + 10011 . 001100110011... = + 1. 0011 0011 0011 0011 0011 001 X 24S = 0, E = 4+127 = 131 = 10000011 and F = 00110011001100110011011Discreteness of real number representation11.1Range and accuracyNot all possible values can be represented by floating point representation of numbers. Only a discrete set of values can be represented. This has implications on the accuracy of computer arithmetic. e.g. try adding together a large number and a very small number.However, the big advantage of using floating point representation is that a vast range of numbers can be represented with both very small and very large values being possible. This is because the exponent can take both positive values (to represent large values) and negative values (to represent small values).A sign bit is used to represent the sign of the number, so both positive and negative values are possible.The accuracy of the number represented depends on the number of bits used to represent the mantissa and real numbers will usually contain some rounding error (the difference between the correct value and its nearest expressible value).11.2ErrorsOverflow will occur when the number is too big to be represented. This is when the exponent does not contain enough bits to hold the power of 2 that is required.e.g, in decimal if the exponent could hold 2 digits, then there would be overflow for any value greater than 1099.Underflow will occur when the number is too small to be represented. This is when the exponent does not contain enough bits to hold the negative power of 2 that is required.e.g, in decimal if the exponent could hold 2 digits, then there would be underflow for any value smaller than 10-99.The spacing between adjacent expressible numbers is not constante.g (using decimal notation)0.999 × 10+99 –0.998 × 10+99 ( = 0.001 × 10+99)is much greater than0.999 × 10+01 – 0.998 × 10+01 (= 0.001 × 10+01)but the relative error (caused by rounding) is approximately constant throughout the range of expressible numbers.11.3Further ReadingFloating-Point Fallacies by Dan Zuras: article starts with the following:The puzzling behavior of some programs that use floating-point arithmetic to solve problems can often elicit some interesting questions. "Why is it that 0.2 x 5.0 results in 0.9999999 not 1.0?" "Why is sin(3.14159265) equal to -8.742276e-8 not 0.0 ?" "How can the total system usage be 100.1% ?"In the next paragraph it continues with:Those who use and write programs that use floating-point to solve problems have a common problem. Floating point numbers and operations are expected to behave like real numbers and operations. This quite reasonable expectation is, unfortunately, never true.Download and read the whole article!This page intentionally left blankTutorial Work Sheet 1Binary, Octal, HexThese exercises should be attempted during the staffed tutorial session. You can ask for help at any time during the tutorial.If you do not finish the exercises during the tutorial, you should complete them in your own time before the next tutorial. If you have any questions, ask at the start of the next tutorial.Tutorial Exercises1. Convert the binary numbers below to decimal.(a) 1010(b) 1111(c) 00010000(d) 00010101(e) 00000101(f) 110001102. Convert each decimal number below to binary.(a) 64(b) 15(c) 234(d) 1(e) 100(f) 4563. Perform the following binary additions. (Hint: write each pair of numbers one below the other and, if necessary, extend both to 8 bits by adding extra 0’s at the left hand side.)(a) 1+1(b) 00110100 + 00001011 (c) 001010 + 001111(d) 00110111 + 110004. Perform the following binary subtractions. Difficult isn’t it! Don’t worry if you can’t do this question, you’ll learn a better way of doing this soon.(a) 0111 - 0101(b) 1101 - 1010(c) 1111 - 0110(d) 01110110 - 010011015. What are the 16 digits of the hexadecimal system? Now convert the hex numbers below to binary.(a) FFFF(b) AF12(c) 34576. Convert the following decimal numbers to binary and then to hexadecimal.(a) 59(b) 29(c) 842(d) 3595(e) 32/ continues on next page7. Convert the binary numbers below to their octal and hex equivalents. (Hint: you may need to put extra 0’s on the left hand side to get the right number of bits.)(a) 1110(b) 11011(c) 110110101(d) 10101111011100108. Some computers represent numeric data using Binary Coded Decimal (BCD) where 4 bits are used to represent each decimal digit. For example, 0010 1001 is the BCD form of the decimal number 29. What decimal numbers do each of the following BCDs represent?(a) 0101 0001(b) 1000 1000 1000(c) 0110 0011(d) 0111 0001 0010Questions from Blundell: Activities 1.4 to 1.8Discussion Questions1. Given a binary number, is it true that the 1's complement of its 1's complement is the original number? Can you give a reason? Is the same true for 2's complement?2. Assume that X, Y and Z are digits. Discuss whether it is always true that XYZ8 <= XYZ10. Explain your reasoning. Tutorial Work Sheet 2Negative Numbers and Binary ArithmeticThese exercises should be attempted during the tutorial. You can ask for help at any time during the tutorial. If you do not finish the exercises during the tutorial, you should complete them in your own time before the next tutorial. If you have any questions, ask at the start of the next tutorial.Exercises1. Represent -105 (negative 105) as an 8-bit binary number using: (a) Signed magnitude (b) One's complement (c) Two's complement (d) Excess 1272. Perform the following subtractions using 8-bit two's complement binary arithmetic. Show you have checked your answers.(a) 75 - 30(b) 22 - 54(c) -85 - 10(d) -100 -503. Assume that a machine uses 4 digits to store integers in binary form. Complete the following table.Decimal valueSigned MagnitudeTwo's Complement-8-7-6-5-4-3-2-11001000000000+1+2+3+4+5+6 +7/ continues on next pageQuestions from BlundellActivity 4.2Discussion Questions1. Given a binary number, is it true that the 1's complement of its 1's complement is the original number? Can you give a reason? Is the same true for 2's complement? Discuss the meaning of the following terms: (a) Data(b) Information (c) Interpretation(d) Meaning(e) Representation What sort of items would you expect to find in the memory of a computer?Are all of them data?Tutorial Work Sheet 3ASCII, Parity, Real Numbers, Floating PointExercisesASCII & ParityWhat is the internal bit pattern representation (i.e. the binary representation) of (a) the number 13(b) the characters 13Produce the binary representation of the message: My name’s Ada!For the binary representation of the message in Q2, show what the parity bit for each character would be if using (a) odd parity and (b) even parity. UnicodeCode the following short strings using UTF-8 and indicate the number of bytes used to encode each string (you will need to look some symbols up before the tutorial). fred ?+? ???? (These symbols appear in the range 0A80 to 0AFF of the Unicode code-charts)Real Numbers and Floating Point RepresentationConvert these fractional binary numbers to decimal.(a) 0.101(b) 0.1111(c) 101.11(d) 110.1011Convert each decimal number below to binary.(a) 0.5(b) 0.875(c) 0.2(d) 2.25 (e) 100.01Calculate the relative error between 0.310 and 0.010012 What is the decimal value of binary 0.101000 x 24 ?Use the binary value 0.101000 x 24 to explain what are the mantissa and exponent of a floating point number.Represent the following values as single precision IEEE 754 numbers.decimal value 132.2binary value 0111010101.10011 decimal value -16.25Questions from BlundellActivities 4.3 to 4.6Discussion Questions and Further ReadingExplain underflow and overflow in floating point numbers. Read Section 11 in this booklet on ‘Discreteness of real number representation’ and then discuss the concept of relative errors in the representation of floating point numbers. Earlier in these notes there is a reprint of a very interesting article written by Dan Zuras (who was a researcher with Hewlett Packard and who did a lot of excellent work on computation and the representation of numbers). Use the article to help you explain what is meant by NaN and how NaN is represented in the IEEE standard.Using decimal notation, and assuming we can store the sign of the mantissa, 3 digits for the mantissa, the sign of the exponent,2 digits for the exponentWhat is the range of numbers we can represent?Mark on the diagram below the ranges of (for numbers represented as described at the start of question 4) :expressible positive numbersexpressible negative numberspositive overflownegative overflow+ve underflow-ve underflow.--10100-10-100010-10010100+Computer ExercisesUsing a spreadsheet, experiment to find out the maximum and minimum values of integer and real numbers that can be displayed.Using your spreadsheet, find the smallest value x such that (1.0+x) is not equal to 1.puter Number Systems – Sample TestNote: This is an example of the format and types of questions that might be included in a test on Computer Number Systems. In an actual test or examination there could be questions on any part of the group of topics covered in that section of the syllabus.No calculators are allowed.Number conversions.Convert binary 00011011 to decimal.Convert decimal 278 to binary.Convert decimal 0.625 to binary.Convert 19B116 to binary.Convert 00110111110111112 to hexadecimal.Convert decimal 8.58 to binaryConvert binary 0.00110011 to decimalNegative numbers. Express the negative number: –19, in each of the following binary representations of negative numbers (using 8 bits). Explain how you have done the conversions.Signed magnitude (sometimes called ‘sign and modulus’).Two’s complement.Binary arithmetic using 2’s complement.Do the following sums, showing your working. Also show you have checked your answers.01001010 + 0000111100010001 + 1000101000001010 - 00110011Character codes.The ASCII code for the letter ‘A’ is 4116, the letter ‘a’ is 6116, the space character is 2016. Code the binary representation of the message ‘Hi Ada’ using 9 bits for each character including an odd parity bit. Encode A????into Utf-8 given that ? has code point 00DB.Floating point numbers. Select the correct answers:Floating Point Overflow occurs whenThe value in the mantissa is too big and positive The value in the exponent is too big and positive Floating Point Underflow occurs whenThe value in the mantissa is too small and positive The value in the mantissa is too large and negative The value in the exponent is too small and positiveThe value in the exponent is too large and negativeErrors.Convert the decimal number 0.56 to binary using 4 binary digits after the point.Using your answer to part (a) as an example, explain the concept of rounding errors.IEEE Standard Representation of Real NumbersConvert 12.5 to a standard binary fractional numberNormalise the result (so that it starts with 1. and has a multiplier of 2 to some power)Assuming the IEEE standard uses - excess 127 representation of the exponent, - the fraction without the leading 1 and binary point give the values of S (the sign bit), E (the exponent) and F (the fraction or mantissa)CSCI1802 - Lab Worksheet 1If you need help with any of these exercises, ask your lab tutor or the person sitting next to you.1. Log on and change passwordLog on to a computer in your laboratory. If you haven’t already done so, change your password to something you can remember, but which is not obvious to anyone else. (Use cntl/alt/del to get to change password.)2. myDMU – Managed Learning EnvironmentKnowing about the MLE is useful because this is where you will get your end of year results from ….. and many other things too.(a) Go to the MLE (Managed Learning Environment) at:(b) Save the site as one of your ‘favourites’ or ‘bookmarks’.(c) Log in using your ‘P number’ as your ID and your date of birth (dd/mm/yy) as your password.(d) Change your myDMU password (to something you can remember!).(e) Log out of myDMU and then log in again using your new password.(f) Explore the site and see what it offers.3. EmailIt is vital that you can use your DMU email and that you check it regularly. We use email as a means of communicating with you.Your university email is available via the web from DMU or at home.Check that you can send and read emails by sending an email to the person sitting next to you, asking them to reply to you. Use your university email account not hotmail or any other account.4. Blackboard Knowing how to use Blackboard is very useful because this is the main source of information about this module. It will be used as the only ‘Notice Board’ for the module. Other notes and handouts will also be published here. You should check this site regularly for announcements and other information about the modules you are studying.(a) Go to the Blackboard site via the link from myDMU.(b) Save the site as one of your ‘favourites’ or ‘bookmarks’.(c) Log in the same way as for the MLE.(d) Find this laboratory worksheet on the site./continues on next page(e) You will be required to take tests using Blackboard during this module. So, to give you some experience of the way tests are done in this system, there is a short ‘diagnostic’ test using the different types of questions you may encounter during the course.Find and take the test. Check your result and the feedback.(f) Explore the Blackboard site and see what else it offers.CSCI1802 - Lab Worksheet 2If you haven’t use Microsoft Excel before, you can get a tutorial booklet called 'Excel 2007 Quick Guide' from the CSE Student Advice Centre on the ground floor of Gateway House. Or your tutor may have a copy for you. The document is also available on the web, from inside DMU only, at training.dmu.ac.uk then follow the link to office 2007documents.If you are new to Excel, It’s a good idea to work through this booklet before trying the exercises below.1. (a) Using a spreadsheet program (such as Microsoft Excel) enter the following headings and the data in the left hand column.x2x10x 01 2Note: 2x is 2 to the power of x and 10x is 10 to the power of x. The x's are raised up using the superscript option: Format/Font/superscript(b) Now insert formulae to calculate 2x and 10x in the first row. (You can either use the symbol ^ for raising to a power, or the function POWER). To find out more use the ‘help’ function. (And then ask your tutor if you need more help.) Check the results you get in your spreadsheet are correct.Copy the formulae down into the rows below. Again check the results carefully.Extend the table to include the values of x up to 10. Check it !Extend the table to include negative values of x. Check it !!2. Use the Excel Chart Wizard (following the instructions below) to produce a graph of the function y = 2x from your table of values. The finished graph should look like this:3106420132715a) Select all the data, including the headings, in the first 2 columns.b) Click on the Chart Wizard c) Select XY (Scatter) and the middle left-hand chart sub-type, which is 'scatter with data points connected by smoothed lines'.d) Click on the Next button until you get to Step 3 of 4 – Chart Optionse) To make the layout look like the example here, you will need to use the tabs:Titles: to enter the chart title and x and y axis labelsGridlines: to draw the horizontal and vertical gridlinesLegend: to remove the legend which we don't want, since we've given the chart a titlef) Click on Finish and the graph will be drawn in your spreadsheet.g) You'll notice that the y axis label is not as in the illustration. To rotate the label, right click on it, then select 'format axis title', click on alignment and then adjust as required. You can also change the font and size of the title in a similar way. CSCI1802 - Lab Worksheet 31. DEC2BIN is an Excel function that converts values from decimal to binary. Use the help button to see exactly how it works.2. Using a similar step by step development technique to that used in Lab Worksheet 2, produce a table to convert between the different bases. Start by entering the following headings, values and the function DEC2BIN in your spreadsheet:ABC1Decimal valueBinary value20= DEC2BIN(A2,8)31425Cell B2 should then display the value 000000003. Extend the decimal value column to value 32 and copy the formula from B2 all the way down. You will now have a lookup table for converting between decimal and binary for decimal values between 0 and 32. You can extend this still further.4. Now work out how to convert decimal or binary to hexadecimal (you can use help if necessary) and extend your spreadsheet to calculate the hexadecimal values. Your spreadsheet might now look like:ABC1Decimal valueBinary valueHexadecimal value20000000000031000000010142000000100253You can now use your spreadsheet to check your answers to most of the questions in the first tutorial.5. Experiment to find out what happens if you enter negative decimal values. How do the answers differ from your tutorial answers? (Hint: count the number of bits)6. Look up the functions CHAR and CODE in 'help'. Might one of these functions help you check the answers to the ASCII tutorial worksheet? Would using the DEC2HEX and HEX2BIN functions help?Produce a spreadsheet that uses these functions to give you a lookup table to convert between characters and their ASCII codese.g.ABCD1CharacterAscii value (decimal)Ascii value (hex)Ascii value (binary)2A6541010000013B/continues on next pageThese last two exercises illustrate some of the limitations of computers in being able to represent numbers.7.Using a spreadsheet, experiment to find out the maximum and minimum values of integer and real numbers that can be displayed.Using your spreadsheet, find the smallest value x such that (1.0+x) is not equal to 1.0.Open the file UnicodeExample.html in a browser and look at what displays. Open the file in notepad and work out the relationship between the two ways of displaying the character. Can you work out where the characters appear in the Unicode charts and look them up? Use the program excel to help you to write a web page to display the whole page table of Gujerati characters with the code points identified in decimal. Look at other code pages (e.g. the mathematical symbols at code points 2200 to 22FF) and see if they will display. ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download