컴퓨터구성 Lecture Series #4 Chapter 3: Data Representation Spring, 2013 컴퓨터구성 : Spring, 2013: No. 4-1
Data Types Introduction This chapter presents data types used in computers for representing diverse numbers and characters Binary Information Data Information Numbers & other binary-coded info. to be used in computation Control Information Sequence of command signals needed for data manipulation such as programmed instructions Data Types Numbers used in arithmetic computations Alphabet letters in data processing Other discrete symbols for specific purposes Grey level data, etc. 컴퓨터구성 : Spring, 2013: No. 4-2
Data Types Number System The number system of base, or radix, r is a system that uses r distinct symbols for r digits Example 1: Decimal System (Radix r = 10) 10 distinct symbols: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 Quantity of 724.5: 7 x 10 2 + 2 x 10 1 + 4 x 10 0 + 5 x 10-1 Example 2: Binary System (Radix r = 2) 2 distinct symbols: 0, 1 Quantity of 101.1: 1 x 2 2 + 0 x 2 1 + 1 x 2 0 + 1 x 2-1 컴퓨터구성 : Spring, 2013: No. 4-3
Data Types Number System Octal System (Radix r = 8) 8 distinct symbols: 0, 1, 2, 3, 4, 5, 6, 7 Hexa-Decimal System (Radix r = 16) 16 distinct symbols: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F Quantity of 4F3 4 x 16 2 + F x 16 1 + 3 x 16 0 = (1267) 10 5 3 6 5 1 0 1 0 1 1 1 1 0 1 0 1 A F 5 Octal Binary Hexa Conversion between number systems is your job!! 컴퓨터구성 : Spring, 2013: No. 4-4
Data Types Examples: Octal & Hexa Octal Number Binary-coded Octal Decimal HexadecimalBinary-coded Number hexadecimal Decimal 0 1 2 3 4 5 6 7 10 11 12 24 62 143 370 000 001 010 011 100 101 110 111 001 000 001 001 001 010 010 100 110 010 001 100 011 011 111 000 0 1 2 3 4 5 6 7 8 9 10 20 50 99 248 Code for one octal digit 0 1 2 3 4 5 6 7 8 9 A B C D E F 14 F8 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 0001 0100 1111 1000 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 20 248 Code for one hexadecimal digit 컴퓨터구성 : Spring, 2013: No. 4-5
Data Types Decimal Representation BCD (Binary-Coded Decimal) Only 0-9 are represented with 4 bits To make conversion to decimal numbers easy after computation 16 distinct binary combinations are unassigned (not used) Wastes 6 combinations Decimal Number Binary-coded Decimal (BCD) 0 0000 1 0001 2 0010 3 0011 4 0100 5 0101 6 0110 7 0111 8 1000 9 1001 Code for one decimal digit 10 20 50 99 248 0001 0000 0010 0000 0101 0000 1001 1001 0010 0100 1000 컴퓨터구성 : Spring, 2013: No. 4-6
Data Types Many applications require handling of not only numbers but also alphabet letters and special characters ASCII Code 8 bits (including a parity bit) Differences b/w Lower case & Upper case alphabets are 32 BCD with leading 011 are ASCII Alphanumeric Representation Char. Binary code Char. Binary code A 100 0001 0 B 100 0010 1 C 100 0011 2 D 100 0100 3 E 100 0101 4 F 100 0110 5 G 100 0111 6 H 100 1000 7 I 100 1001 8 J 100 1010 9 K 100 1011 L 100 1100 M 100 1101 SPACE N 100 1110. O 100 1111 ( P 101 0000 + Q 101 0001 $ R 101 0010 * S 101 0011 ) T 101 0100 - U 101 0101 / V 101 0110, W 101 0111 = X 101 1000 Y 101 1001 Z 101 1010 011 0000 011 0001 011 0010 011 0011 011 0100 011 0101 011 0110 011 0111 011 1000 011 1001 010 0000 010 1110 010 1000 010 1011 010 0100 010 1010 010 1001 010 1101 010 1111 010 1100 011 1101 컴퓨터구성 : Spring, 2013: No. 4-7
Complements (r-1) s Complement Used for simplifying subtraction & logical manipulations (r-1) s Complement Given a number N with n digits, its (r-1) s complement is (r n -1) - N Decimal (r = 10) 9 s complement Example: N = 3450 r n -1 = 10 4-1 = 9999 9999-3450 = 6549 Binary (r = 2) 1 s complement Example: N = 1011001 r n -1 = 2 7-1 = 1111111 1111111-1011001 = 0100110 Change 0 1 & 1 0 컴퓨터구성 : Spring, 2013: No. 4-8
Complements r s Complement r s Complement Given a number N with n digits, its r s complement is (r n -N) (r n -N) = (r n - 1) - N + 1 = (r -1) s complement + 1 Decimal (r = 10) 10 s complement Example: N = 3450 r n = 10 4 = 10000 10000-3450 = 9999-3450 + 1 = 6549 + 1 = 6550 Binary (r = 2) 2 s complement Example: N = 1011000 r n = 2 7 = 10000000 10000000-1011000 = 1111111-1011000 + 1 = 0101000 Leave all lower order 0 s before the first 1 and the first 1 unchanged and complement the remaining upper binary numbers 컴퓨터구성 : Spring, 2013: No. 4-9
Complements Notes N O T E S No differences even when radix point is present Complement of a complement results in the original Three ways to subtract depending on how negative numbers are represented (will be shown shortly) 컴퓨터구성 : Spring, 2013: No. 4-10
Complements Subtraction of Unsigned Numbers What if numbers are represented as positive numbers? Subtraction of 2 n-digit Unsigned Numbers: M - N (N 0) Find r s complement of N & add to M M + (r n - N) = M - N + r n If M N ( M - N 0 ), sum will produce an end carry r n & discard this (M - N + r n - r n ) = M - N This is the answer If M N ( M - N 0 ), sum will not produce an end carry r n M + (r n -N) = { r n -(N-M)} = r s complement of (N - M) For answer, take r s complement and regard as negative 컴퓨터구성 : Spring, 2013: No. 4-11
Complements Subtraction of Unsigned Numbers Ex 1.1: 72532-13250 = 59282 Ex 1.2: 13250-72532 = - 59282 M = 72532 M = 13250 10 s complement of N = +86750 10 s complement of N = +27468 Sum = 159282 Sum = 40718 Discard 10 5 = -100000 10 s complement of Sum = 59282 Answer = 59282 Answer = - 59282 Ex 2.1: 1010100-1000011 = 0010001 Ex 2.2: 1000011-1010100 = - 0010001 X = 1010100 Y = 1000011 2 s complement of Y = +0111101 2 s complement of X = +0101100 Sum = 10010001 Sum = 1101111 Discard 2 8 = -10000000 2 s complement of Sum = 0010001 Answer = 0010001 Answer = - 0010001 컴퓨터구성 : Spring, 2013: No. 4-12
Fixed-Point Representation Introduction Negative Values Sign Bit at the leftmost bit position 0 for positive & 1 for negative Binary Point Fixed Point At extreme left or right of the stored number in a register We assume the latter the number is integer Floating Point Will be discussed in the next section Most of computer systems use floating-point for real numbers 컴퓨터구성 : Spring, 2013: No. 4-13
Fixed-Point Representation Integer Representation Positive Integer: Sign bit and magnitude: Negative Integer: 14 = 0 0001110 Signed-magnitude: -14 = 1 0001110 Used in ordinary arithmetic; but awkward in computers Signed-1 s complement: -14 = 1 1110001 Difficult since it has two zeros (+0 (0000) & -0 (1111)) Used only in old computers for numerical arithmetic Useful in logic operations (complementation) Signed-2 s complement: -14 = 1 1110010 Primarily used in most computers as well as in my lecture 컴퓨터구성 : Spring, 2013: No. 4-14
Data Representation Summary n- bit Numbers Unsigned Numbers = Unsigned Magnitude Signed Magnitude Signed 1 s complement Signed 2 s complement Max Min Zero 2 n -1 0 0 1111 0000 0000 + (2 n-1-1) -(2 n-1-1) + 0, - 0 0 111 1 111 0 000, 1 000 + (2 n-1-1) -(2 n-1-1) + 0, -0 0 111 1 000 0 000, 1 111 + (2 n-1-1) -2 n-1 0 0 111 1 000 0 Complement 컴퓨터구성 : Spring, 2013: No. 4-15
Fixed-Point Representation Arithmetic Addition Signed-Magnitude: Same Signs Add two magnitudes and put the sign bit Different Signs Subtract smaller magnitude from larger one Put the sign of data with larger magnitude Need comparison, addition, subtraction Q: Think about the rule for adding two numbers in signed- 1 s complement format Signed-2 s Complement: Rule Add two numbers including sign bits Discard carry out of sign bit, if any +6 +13 +19 00000110 00001101 00010011-6 +13 +7 11111010 00001101 00000111 Need addition, only Negative result is in 2 s complement form +6-13 -7 00000110 11110011 11111001-6 -13-19 11111010 11110011 11101101 컴퓨터구성 : Spring, 2013: No. 4-16
Fixed-Point Representation Arithmetic Subtraction Signed-Magnitude: Rule Change the sign of subtrahend Perform Signed-Magnitude Addition Signed-2 s Complement: Rule Take 2 s complement of subtrahend Add it to minuend Discard carry out of sign bit, if any Need addition, only Negative result is in 2 s complement form Q: Think about the rule for adding two numbers in signed- 1 s complement format 컴퓨터구성 : Spring, 2013: No. 4-17
Fixed-Point Representation Overflow When two numbers of n digits with the same sign are added & the sum occupies n+1 digits, we say that an overflow occurred Overflow Flip-Flop: A flip-flop to store the (n+1) th bit of the result When is overflow? Q: Think about the case two numbers in signed-1 s complement format Addition of 2 Unsigned Numbers End carry out of MSB Addition of 2 Signed-2 s Complement Numbers End carry out of sign bit does not imply the overflow End carry out of sign bit and the carry into sign bit are different Carries: 0 1 Carries: 1 0 +70 0 1000110-70 1 0111010 +80 0 1010000-80 1 0110000 +150 1 0010110-150 0 1101010 컴퓨터구성 : Spring, 2013: No. 4-18
Fixed-Point Representation Decimal Representation Disadvantages: Wasting storage space Numeric computations & their circuits are complicated 0 375 +9 760 0 135 (0000 0011 0111 0101) BCD (1001 0111 0110 0000) BCD (0000 0001 0011 0101) BCD Advantages: No need to convert between decimals & binaries Largely used in data processing where computations are rare For BCD adder see Fig. in your textbook 컴퓨터구성 : Spring, 2013: No. 4-19
Floating-Point Representation Composition: Mantissa (m) Signed fixed-point number Exponent (e) Position of binary point Interpretation m 2 e Normalization: MSB of the mantissa is nonzero Example (in Textbook): Fraction +001001.11 0 1001110 Exponent 0 00100 m x 2 e = +(.1001110) 2 x 2 +4 컴퓨터구성 : Spring, 2013: No. 4-20
Floating-Point Representation IEEE 754 Standard Example (in Real World): Sign bit Exponent (e) 8 bits in Excess-127 Mantissa (m) 23 bits Interpretation N = (-1) s 2 e-127 (1.m) 0 1 8 9 31 Exponent Mantissa 8 bits 23 bits Sign bit 64-bit Extention Sign bit Exponent (e) 11 bits coded into Excess-1023 Mantissa (m) 52 bits Interpretation N = (-1) s 2 e-1023 (1.m) 컴퓨터구성 : Spring, 2013: No. 4-21
Error Detection Codes Binary information transmitted thru communication medium is subject to external noise. Parity Bit: Error Detection Code An extra bit to make number of 1 s in a message either even or odd Even Parity: P(even) What if the message contains all zeros? Odd Parity : P(odd) So, this is generally used. Source x y z Destination x y z Error Indication Parity Generator Parity Checker 컴퓨터구성 : Spring, 2013: No. 4-22
Homework Exercise: 3-7, 3-8, 3-15, 3-16, 3-17, 3-19, 3-26 Hamming Code: Have you ever heard about the Hamming Code? I don t think so Find a book that describes the Hamming Code and make 1 or 2 page hand-written summary as a homework. Some of you will be chosen to present the idea during the class. 컴퓨터구성 : Spring, 2013: No. 4-23