UNIVERSITY OF MASSACHUSETTS Dept of Electrical Computer Engineering Digital Computer Arithmetic CE666 Koren Part 1 1 ECE 666 Part 1 Introduction Israel Koren Spring 2008 Copyright 2008 Koren Prerequisites and textbook Prerequisites courses in Digital Design Computer Organization Architecture Recommended book Computer Arithmetic Algorithms I Koren 2nd Edition A K Peters Natick MA 2002 Textbook web page http www ecs umass edu ece koren arith Recommended Reading B Parhami Computer Arithmetic Algorithms and Hardware Design Oxford University Press 2000 M Ercegovac and T Lang Digital Arithmetic Morgan Kaufman 2003 CE666 Koren Part 1 2 Copyright 2008 Koren Administrative Details Instructor Prof Israel Koren Office KEB 309E Tel 545 2643 Email koren ecs umass edu Office Hours TuTh 2 30 3 30 Course web page http www ecs umass edu ece koren ece66 6 Grading CE666 Koren Part 1 3 Homework No credit Two Mid term exams 25 each Final Exam or Project 50 Copyright 2008 Koren Course Outline Introduction Number systems and basic arithmetic operations Unconventional fixed point number systems Sequential algorithms for multiplication and division Floating point arithmetic Algorithms for fast addition High speed multiplication Fast division and division through multiplication Efficient algorithms for evaluation of elementary functions Logarithmic number systems Residue number system error correction and detection in arithmetic operations CE666 Koren Part 1 4 Copyright 2008 Koren The Binary Number System In conventional digital computers integers represented as binary numbers of fixed length n An ordered sequence of binary digits Each digit x bit is 0 or 1 i The above sequence represents the integer value X Upper case letters represent numerical values or sequences of digits Lower case letters usually indexed represent individual digits CE666 Koren Part 1 5 Copyright 2008 Koren Radix of a Number System The weight of the digit x is the i th power of 2 i 2 is the radix of the binary number system Binary numbers are radix 2 numbers allowed digits are 0 1 Decimal numbers are radix 10 numbers allowed digits are 0 1 2 9 Radix indicated in subscript as a decimal number Example 101 decimal value 101 10 101 decimal value 5 CE666 Koren Part 1 6 2 Copyright 2008 Koren Range of Representations Operands and results are stored in registers of fixed length n finite number of distinct values that can be represented within an arithmetic unit Xmin Xmax smallest and largest representable values Xmin Xmax range of the representable numbers A result larger then Xmax or smaller than Xmin incorrectly represented The arithmetic unit should indicate that the generated result is in error an overflow indication CE666 Koren Part 1 7 Copyright 2008 Koren Example Overflow in Binary System Unsigned integers with 5 binary digits bits Xmax 31 10 represented by 11111 2 Xmin 0 10 represented by 00000 2 Increasing Xmax by 1 32 10 100000 2 5 bit representation only the last five digits retained yielding 00000 2 0 10 In general A number X not in the range Xmin Xmax 0 31 is represented by X mod 32 If X Y exceeds Xmax the result is S X Y mod 32 Example X 10001 Y 10010 1 00011 17 18 3 35 mod 32 Result has to be stored in5a 5 bit register the most significant bit with weight 2 32 is discarded CE666 Koren Part 1 8 Copyright 2008 Koren Machine Representations of Numbers Binary system one example of a number system that can be used to represent numerical values in an arithmetic unit A number system is defined by the set of values that each digit can assume and by an interpretation rule that defines the mapping between the sequences of digits and their numerical values Types of number systems conventional e g binary decimal unconventional e g signed digit number system CE666 Koren Part 1 9 Copyright 2008 Koren Conventional Number Systems Properties of conventional number systems Nonredundant Every number has a unique representation thus No two sequences have the same numerical value Weighted A sequence of weights wn 1 wn 2 w1 w0 determines the value of the n tuple xn 1 xn 2 x1 x0 by wi weight assigned to xi digit in ith position Positional The weight wi depends only on the position i of digit xi wi r i CE666 Koren Part 1 10 Copyright 2008 Koren Fixed Radix Systems r the radix of the number system Conventional number systems are also called fixed radix systems With no redundancy 0 xi r 1 xi r introduces redundancy into the fixedradix number system If xi r is allowed two machine representations for the same value xi 1 xi and xi 1 1 xi r CE666 Koren Part 1 11 Copyright 2008 Koren Representation of Mixed Numbers A sequence of n digits in a register not necessarily representing an integer Can represent a mixed number with a fractional part and an integral part The n digits are partitioned into two k in the integral part and m in the fractional part k m n The value of an n tuple with a radix point between the k most significant digits and the m least significant digits is CE666 Koren Part 1 12 Copyright 2008 Koren Fixed Point Representations Radix point not stored in register understood to be in a fixed position between the k most significant digits and the m least significant digits These are called fixed point representations Programmer not restricted to the predetermined position of the radix point Operands can be scaled same scaling for all operands Add and subtract operations are correct aX aY a X Y a scaling factor Corrections required for multiplication and division aX aY a 2X Y aX aY X Y Commonly used positions for the radix point rightmost side of the number pure integers m 0 leftmost side of the number pure fractions k 0 CE666 Koren Part 1 13 Copyright 2008 Koren ULP Unit in Last Position Given the length n of the operands the m weight r of the least significant digit indicates the position of the radix point Unit in the last position ulp the weight of the least significant digit ulp r m This notation simplifies the discussion No need to distinguish between the different partitions of numbers into fractional and integral parts Radix conversion see textbook p 4 6 CE666 Koren Part 1 14 Copyright 2008 Koren Representation of Negative Numbers Fixed point numbers in a radix r system Two ways of representing negative numbers Sign and magnitude representation or signed magnitude representation Complement representation with two alternatives Radix complement two s complement in the binary system Diminished radix complement one s complement in the