CENG 103 Intro to CENG Lecture Notes SB - 1

CENG 103 Introduction to Computer Engineering Part ı – Introduction and Information Representation Prof. Dr. Semih Bilgen Istanbul Okan University  Contents Introduction to computer engineering Information representation – number systems Boole...

CENG 103 Introduction to Computer Engineering Part ı – Introduction and Information Representation Prof. Dr. Semih Bilgen Istanbul Okan University  Contents Introduction to computer engineering Information representation – number systems Boolean Algebra and Digital logic structures Computer architecture Little Computer 3 (LC-3) Software and programming Control and data structures Input/Output (I/O) Ethics and Computer Engineering  Introduction to Computer Engineering Human mental performance (paper&pencil): Average 1 Arithmetic OP (AOP)/sec Human perception performance: Less than 16 images/sec 1946 IBM 602 performance: 200 AOP/sec Machine 12-Digit Program 6-Digit 4-Digit Model Cycles Storage Functions Steps Counters Counters per Minute Units 1 200 12 6 3 3 +, -, *, / 2 200 12 6 3 3 +, -, *, / 50 150 6 4 3 1 +, -, *, / 51 150 6 4 3 1 +, -, *  Colossus computer vacuum tube supercomputer 1943: 500,000 AOP/sec Wikipedia: Colossus was a set of computers developed by British codebreakers in the years 1943–1945 to help in the secret communication systems used during WW2. Colossus used thermionic valves (vacuum tubes) to perform Boolean and counting operations. Colossus is thus regarded as the world's first programmable, electronic, digital computer, although it was programmed by switches and plugs (SB: «hard wired») and not by a stored program (SB: «software»). Thermionic valves (vacuum tubes)  Development of CPU performance – very briefly: The first microprocessor, the Intel 4004 in 1971, contained 2300 transistors and operated at 106 KHz, 92,600 AOP/Sec. (0,92 MIPS) By 1992, those numbers had jumped to 3.1 million transistors at a frequency of 66 MHz on the Intel Pentium microprocessor, an increase in both parameters of a factor of about 1000. Pentium 1994 performance was 188 MIPS at 100 MHz Today’s microprocessors contain more than ten billion transistors and can operate at more than 4 GHz, another increase in both parameters of about a factor of 1000. Intel® Core™ i9-13900K (2022): 14.2 billion transistors, 4.3 GHz; Integer Math: 211,545 MIPS (more than two hundred thousand million AOP/sec)  What is a computer? A very large systematically interconnected collection of very simple parts (e.g. 14 billion transistors, etc.) In this course we shall become familiar with those parts and step-by-step, understand how they are interconnected to reach today’s intelligent systems: oInformation representation oTransistors  Gates  information processing  Integrated circuits (chips)  devices  computer oProgramming oData and control structures oOperating systems  Information representation All digital equipment operate on binary representation of information A bit (binary digit) can have only two values: 0/1, and is the smallest unit of information: Information means the choice between possible options. Unless there are at least two options, there can be no choice, hence no information. With multiple bits, choices among larger sets of options are possible. E.g. 2 bits  4 options (00, 01, 10, 11), 3 bits  8 options, etc. The number of choices (combinations) that can be represented by n bits is 2n The number of bits needed to represent N choices (alternatives) is log2N  Examples At least how many bits are necessary for binary representation of the 29 letters of the Turkish alphabet? Log229 ~ 4.86 so 4 bits are not sufficient, 5 bits are needed. (24 = 16, 25 = 32) A 6-bit team code is used to represent all teams participating in a volleyball tournament. What is the maximum number of teams that can participate in this tournament?  26 = 64, so up to 64 teams can participate.  Redundant coding Assume that we need to encode the alphabet {A, B, C, D} in binary form. The following codes, and countless others, are possible: A B C D Note 00 01 10 11 Min size code 000 011 110 101 Even no of 1’s 100 010 001 111 Odd no of 1’s 0000 0011 1100 1111 Min size x 2 00000000 00001111 11110000 11111111 Min size x 4 The extra bits may be used for ensuring correct communication – many complex algorithms are available for that purpose.  Representing numeric information Positional notation: Positions named as p: 0, 1, 2, etc. from right to left, each bit value multiplied by 2p to obtain number value, i.e. Converting binary to decimal representation. e.g. 100112 represents 1 x 20 + 1 x 21 + 0 x 22 + 0 x 23 + 1 x 24 = 1910 This is UNSIGNED integer representation. To convert decimal to binary, simply keep dividing by 2 and writing the remainders starting from position 0, going towards the left, until the quotient is 0. e.g. Find the binary representation of 3710. 37 / 2 : q=18, r=1 18 / 2 : q=9, r=0 9 / 2 : q=4, r=1 4 / 2 : q=2, r=0 2 / 2 : q=1, r=0 1 / 1 : q=0, r=1 so, 3710 = 1001012  Binary numeric formats Binary: only 0’s and 1’s Octal: 3-bit combinations represented by digits {0, 1, 2, 3, 4, 5, 6, 7} e.g. 0111011110002 = 35708 10011102 = 1168 (Grouping starts from the least significant bit.) Hexadecimal: 4-bit combinations represented by HEX digits {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F} e.g. 0111011110002 = 778H 11011111010110002 = DF58H 110000110010112 = 30CBH  Representing signed integers Sign-Magnitude notation: Highermost order (leftmost) bit represents sign, the rest represents magnitude. e.g. +1210 = 011002, -1210 = 111002 One’s Complement notation: Leftmost bit represents sign, and the other bits are all flipped (0 1) for negative numbers e.g. +1210 = 011002, -1210 = 100112 Neither of these notations are suitable for computational circuits, so a more convenient notation is used for representing negative numbers:  2’s Complement notation Start with the representation of the positive number Flip all bits Add 1 e.g. To represent -1910: Start with 0100112 which represents +19 Flip all bits: 101100 Add 1: 1011012 represents -1910 in 2’sC notation. Why is this preferred?  2’s complement arithmetic - 19 101101 + 19 010011 00 (1) 000000 Arithmetic with 2’s complement numbers is straightforward – no special operation is necessary. Given any binary number, to find the decimal equivalent: If the leftmost bit is 0, the number is positive, simply multiply bit values with positional weights ( x 2p at position p) and add. If the leftmost bit is 1, the number is negative; flip all bits, convert to decimal, then add 1 to find the magnitude. e.g. 101101  010010  18 + 1  19, so 1011012 = -1910  e.g. 5 bit integer representations Unsigned Sign-Mag 1’s Comp 2’s Comp Bit Unsigned Sign-Mag 1’s Comp 2’s Comp Bit pattern pattern 0 +0 +0 0 00000 16 -0 -15 -16 10000 1 +1 +1 +1 00001 17 -1 -14 -15 10001 2 +2 +2 +2 00010 18 -2 -13 -14 10010 3 +3 +3 +3 00011 19 -3 -12 -13 10011 4 +4 +4 +4 00100 20 -4 -11 -12 10100 5 +5 +5 +5 00101 21 -5 -10 -11 10101 6 +6 +6 +6 00110 22 -6 -9 -10 10110 7 +7 +7 +7 00111 23 -7 -8 -9 10111 8 +8 +8 +8 01000 24 -8 -7 -8 11000 9 +9 +9 +9 01001 25 -9 -6 -7 11001 10 +10 +10 +10 01010 26 -10 -5 -6 11010 11 +11 +11 +11 01011 27 -11 -4 -5 11011 12 +12 +12 +12 01100 28 -12 -3 -4 11100 13 +13 +13 +13 01101 29 -13 -2 -3 11101 14 +14 +14 +14 01110 30 -14 -1 -2 11110 15 +15 +15 +15 01111 31 -15 -0 -1 11111  Examples (1) An 8-bit computer word contains 10011001. What is the decimal equivalent if this is interpreted as: Unsigned integer? 128 + 16 + 8 + 1 = 153 Sign-magnitude integer? - (16 + 8 + 1) = -25 1’s complement integer? - (64 + 32 + 4 + 2) = -102 d) 2’s complement integer? - (64 + 32 + 4 + 2 + 1) = -103  Examples (2) Show the representation of the integer -6510 in an 8-bit Word as a: a) Sign-magnitude integer: 11000001 b) 1’s complement integer: 10111110 c) 2’s complement integer: 10111111  Fractional numbers e.g. 10.10112 = 1 x 21 + 0 x 20 + 1 x ½ + 0 x ¼ + 1 x 1/8 + 1 x 1/16 = 2 + 0.5 + 0.125 + 0.0625 = 2.687510  Floating point number representation A floating point number is represented as: v = s × 2e × (1+m) Where v is the number, s is the sign, m is the mantissa, and s = +1 (positive numbers) when the sign bit is 0 s = −1 (negative numbers) when the sign bit is 1 e = Exponent − 127 (in other words the exponent is stored with 127 added to it, also called "biased with 127") m = Fraction in binary form (0 ≤ m < 1), the fractional part includes an implicit 1 on the left of the binary point. e.g. 0.15625 can be represented as a 32bit floating point number as follows: s = +1 e = -3 (from 124 – 127) (because 2-3 = 0.125 < 0.15625 < 0.25 = 2-2 , we must multiply the fractional part by 2-3 ) m = 0.25 (note: m=0.25 means multiply by 1.25) So, v = +1 x 2-3 x 1.25 = +1 x 0.125 x 1.25 = 0.15625  Decimal to 32-bit floating point conversion Consider a real number, e.g. 12.375 Convert and normalize the integer part into binary (1210 = 11002) Convert the fraction part (0.37510 = 0 x ½ + 1 x ¼ + 1 x 1/8 = 0.0112) Add the two results (1100.0112) Adjust them to produce a proper final conversion:   32-bit floating point example (continued): Since 32 bit floating point number standard (IEEE 754 binary32) requires real values to be represented in (1.b1b2…b23)2 x 2e format, 1100.011 is shifted to the right to become (1.100011)2 x 23 = 12.37510 The exponent is 3, so it must be stored as (3 + 127)10 = (130)10 = 100000102 The fraction is 100011 (the «1.» is not stored) So, (12.375)10 = (0 10000010 10001100000000000000000)2 = (41460000)H  e.g. What is the decimal value represented by the floating point number: 0011 1110 0110 1101 0000 0000 0000 0000 Sign bit is 0, so number is positive. e = 011111002 = 12410, so exponent of the number is 124-127 = -3 Mantissa is 1101101 (leaving out the less significant 0’s), So, the number is: 1.1101101 x 2-3 = (1 + ½ + ¼ + 1/16 + 1/32 + 1/128) x 2-3 =(1 +.5 +.25 + 0.0625 + 0.03125 + 0.0078125) / 8 = 0.23110  Representation of alpha-numeric information ASCII («American Standard Code for Information Interchange»): 7-bit code to represent lower case and upper case letters of the English alphabet, as well as all decimal digits, punctuation marks and control characters. Extended (8-bit) ASCII code that includes Greek letters as well as other symbols together with all 7-bit ASCII symbols. So the same 8-bit data may be interpreted in many different ways: 7-bit ASCII, 8-bit ASCII, unsigned, sign magnitude, 1’sC, 2’s C, … 7-bit ASCII Table  Any 32-bit (4 Byte) data item may mean (i.e. be interpreted/used as): Alphanumeric: 4 character ASCII code (7-bit ASCII or Extended 8-bit ASCII) Another alphanumeric code (e.g. Unicode, EBCDIC, etc) Numeric: IEEE 754 binary 32 floating point number Unsigned binary number Sign-magnitude integer 1’sC integer 2’sC integer