
ECE 252B: Information on Previous Offerings
Behrooz Parhami: 2007/06/19  Email: parhami@ece.ucsb.edu  Problems: webadmin@ece.ucsb.edu Other contact info at: Bottom of this page  Go up to: B. Parhami's course syllabi or his home page
On June 19, 2007, Professor Parhami's UCSB ECE website moved to a new location. For an uptodate version of this page, visit it at the new address: http://www.ece.ucsb.edu/~parhami/ece_252b_old.htm Link to the most recent offering of ECE 252B: Computer ArithmeticPrevious offerings of ECE 252B
Return to:
Top of this page ECE 252B: Fall Quarter 2005 offeringThis area is reserved for important course announcements: The course was cancelled for the fall 2005 quarter; its next offering will be in Spring 2007.
Return to:
Top of this page ECE 252B: Winter Quarter 2005 offeringThis area is reserved for important course announcements: A new special issue of IEEE Trans. Computers has just appeared (March 2005), leading to an update in the References section. Some electronic resources have also been added to the References section. Course grades were assigned and reported on 2005/03/15.
Calendar: Course
lectures, homework assignments, and exams have been scheduled as follows. This
schedule will be strictly observed. Textbook chapters are specified for lectures
and exams. It is a good idea to look over the specified material
before
each lecture if possible.
Homework: General Requirements Solutions should be brought to class on the due date
and handed in before the lecture begins. Late
homework will not be accepted, so plan to start work on your assignments early. Use a cover page that includes your name, course and assignment number for your solutions. Staple
the sheets and write your name on top of every sheet in case sheets are
separated. Although
some cooperation is permitted, direct copying will have severe consequences. ECE 252B w2005, Course Grade Stats
* Course = 20%(HW total / 4) + 30%(Midterm) + 50%(Final or Paper) ECE 252B w2005, Homework #1: Number Systems and Addition (chap. 17, due Wed. Jan. 19) Do the following problems from the textbook or defined below: 2.1 [20 pts.], 3.11 [15 pts.], 5.A [15 pts.], 6.F [10 pts], 7.13 [20 pts.], 7.15 [20 pts.] Problem 5.A Binary adders as versatile building blocks  Show how to use a 4bit binary adder as: (a) A multiplyby3 circuit for a 4bit unsigned number. (b) Two independent 3input majority circuits implementing 2outof3 voting. Problem 6.F Implementing the carry operator  Show that the carry operator of Fig. 6.6 can be implemented by using g = (g˘ Ú g˛)(p˛ Ú g˛), thereby making all signals for p and g go through two levels of logic using a NOTNOR or NORNOR implementation. ECE 252B w2005, Homework #2: Multioperand Addition and Multiplication (chap. 812, due Wed. Feb. 2) Do the following problems from the textbook or defined below: 8.15 [25 pts.], 9.4c [20 pts], 9.15 [15 pts.], 10.5 [10 pts.], 11.E [15 pts.], 12.16 [15 pts.] Problem 11.E Unsigned/2’scomplement tree multiplier – Most processors allow both unsigned and signed numbers as operands in their integer arithmetic units. Discuss the design of a k ´ k tree multiplier that can act as an unsigned multiplier (for t = 0) or 2’scomplement multiplier (for t = 1), where t is a control signal. ECE 252B w2005, Homework #3: Division (chap. 1316, due Wed. Feb. 23) Do the following problems from the textbook or defined below: 13.7b [20 pts.], 13.D [20 pts.], 14.2d [20 pts], 15.13abc [20 pts.], 16.A [20 pts.] Problem 13.D Sequential division – Perform the unsigned binary division . 1100 1100 1100 / . 1001 11 by means of the restoring algorithm. Hint: Watch for overflow. Problem 16.A Sequential vs convergence division – Suppose multiplication and addition take 5 and 1 time units, respectively, and that all support and control functions (counting, conditionals, register transfers, etc.) take negligible time due to overlapped processing. Be brief and state all your assumptions clearly. (a) Express the time needed for simple binary restoring division as a function of the word width k. (b) Express the time needed for division by repeated multiplications (without an initial table lookup or other speedup methods) as a function of k. (c) Compare the results of parts a and b. Comment on the speed/cost tradeoffs for different word widths. ECE 252B w2005, Homework #4: FloatingPoint and Function Evaluation (chap. 1722, due Wed. Mar. 9) Do the following problems from the textbook or defined below: 17.11 [20 pts.], 18.F [20 pts.], 20.3 [20 pts.], 21.2a [20 pts.], 22.2ab [20 pts.] Problem 18.F Monotonicity in floatingpoint arithmetic – This problem is attributed to W. Kahan. Consider a computer that performs floatingpoint multiplication by truncating (rather than rounding) the exact 2pdigit product of pdigit normalized fractional significands to p digits; that is, it either does not develop the lower p digits of the exact product, or simply drops them. (a) Show that, for a radix r greater than 2, this causes the monotonicity of multiplication to be violated (i.e., there exist positive floatingpoint numbers a, b, and c such that a < b but a ´_{fp} c > b ´_{fp} c). Hint: when x ´_{fp} y < 1/r, postnormalization causes the least significant digit of the final product to be 0. (b) Show that multiplication remains monotonic in radix 2 (i.e., a Ł b implies a ´_{fp} c Ł b ´_{fp} c). ECE 252B w2005, Notes on homework solutions and other topics None. ECE 252B w2005, Possible Research Topics Given that no student has chosen the research path in lieu of the final exam, this section will not be updated for the current quarter. ECE 252B w2005, Midterm Exam Preparation
Textbook sections that are not required for the closedbook midterm exam: 3.5, 3.6, 4.4, 4.5, 4.6, 6.3, 7.2, 10.5 (some of these may be included in the final exam, which will be openbook) ECE 252B w2005, Final Exam Preparation
Return to:
Top of this page ECE 252B: Fall Quarter 2003 offering
Calendar: Course
lectures, homework assignments, and exams have been scheduled as follows. This
schedule will be strictly observed. Textbook chapters are specified for lectures
and exams. It is a good idea to look over the specified material
before
each lecture if possible.
Homework: General Requirements Solutions should be brought to class on the due date
and handed in before the lecture begins. Late
homework will not be accepted, so plan to start work on your assignments early. Use a cover page that includes your name, course and assignment number for your solutions. Staple
the sheets and write your name on top of every sheet in case sheets are
separated. Although
some cooperation is permitted, direct copying will have severe consequences. Course Grade Stats
* Course = 25%(HW total / 8) + 25%(Midterm) + 50%(Final or Paper) ECE 252B f2003, Homework #1: Number Representation (chapters 14, due Wed. Oct. 1) Do the following problems from the textbook: 1.3, 1.11, 2.13, 3.4a (part a only), 4.2 ECE 252B f2003, Homework #2: Basic & CarryLookahead Addition (chapters 56, due Wed. Oct. 8) Do the following problems from the textbook: 5.6def, 5.10, 6.5, 6.12, 6.16 ECE 252B f2003, Homework #3: Other Addition Topics (chapters 78, due Mon. Oct. 20) Do the following problems from the textbook or defined below: 7.6, 7.8, 7.C, 8.11, 8.B Problem 7.C (Carryskip versus carryselect adders): Compare the costs and delays of 16bit singlelevel carryskip and carryselect adders, each constructed from 4bit adder blocks and additional logic as needed. Which design would you consider more costeffective and why? State all your assumptions clearly. Problem 8.B (carrysave adder trees): a. Show the widths of the four CSAs required to reduce six 32bit unsigned binary numbers to two. b. Repeat part a, but assume that the six 32bit unsigned numbers are the partial products of a 32by6 multiplication (i.e., they are not aligned at the LSBs but shifted to the left by 0, 1, 2, 3, 4, and 5 bits). ECE 252B f2003, Homework #4: Basic & HighRadix Multiplication (chapters 910, due Mon. Oct. 27) Do the following problems from the textbook: 9.3, 9.9b, 9.16, 10.8a, 10.9 ECE 252B f2003, Homework #5: Other Multiplication Topics (chapters 1112, due Mon. Nov. 10) Do the following problems from the textbook: 11.10, 11.12, 12.1, 12.9*
* Correction to Problem 12.9: Change 2k
 2j + 1 to 2k
ECE 252B f2003, Homework #6: Basic & HighRadix Division (chapters 1314, due Mon. Nov. 17) Do the following problems from the textbook or defined below: 13.14, 13.A, 14.1cd, 14.5 Problem 13.A (sequential division): Perform the unsigned fractional binary division .0110 1101 / .1011 using the restoring and nonrestoring methods ECE 252B f2003, Homework #7: Other Division Topics (chapters 1516, due Mon. Nov. 24) Do the following problems from the textbook or defined below: 15.2, 15.B, 16.7, 16.13 Problem 15.B (radix8 division): Argue that the use of the quotient digit set [–6, 6] is preferable to the minimal digit set [–4, 4] in a radix8 divider that forms the multiple 3d by inputting the two values 2d and d into a fourinput carrysave adder tree that also receives the carrysave partial remainder as inputs. ECE 252B f2003, Homework #8: FloatingPoint Arithmetic (chapters 1720, due Mon. Dec. 1) Do the following problems from the textbook or defined below: 17.12, 17.C, 18.3, 19.15, 20.2 Problem 17.C (Logarithmic number systems): Consider an 8bit unsigned number system in which the base2 logarithm is represented with k = 3 whole and l = 5 fractional bits. a. What is the range of this number system? b. What is the maximum relative representation error for numbers within the above range? c. Represent the numbers x = 7 and y = 11 as accurately as possible in this number system. Additional Practice Problems (chapters 2124)
Notes on homework solutions and other topics A better solution to Problem 6.12 is based on the delay and cost recurrences D(k) = D(floor(k/2)) + 2 and C(k) = C(floor(k/2)) + k  1 for a BrentKung network of general width k (not necessarily a power of 2). In the solution handed out for Problem 11.12, the following corrections are needed for parts b and c. A couple of these are due to simple miscounting; one is due to the fact that in Wallace trees, HAs should not be used unless not doing so would increase the latency (number of levels). Part b, line 5  3 HAs; line 6  . . . 1 3 1 1 1 9bit adder; line 7  7 HAs + 9bit adder Part c, line 5  4 FAs + 3 HAs; line 7  21 FAs + 7 HAs ECE 252B f2003, Possible Research Topics In the following, IEEETC7/2000 refers to the latest computer arithmetic special issue of IEEE Trans. Computers published in July 2000 and ARITH2001 (2003) stands for the Proc. 15th (16th) IEEE Symp. Computer Arithmetic held in June 2001 (June 2003). 1. Design of parallelprefix adders, IEEETC7/2000 pp. 659680, ARITH2001 pp. 218225 + 277284. 2. Fast multiplication and powering, IEEETC7/2000 pp. 681701, ARITH2001 pp. 2339 + 7379, ARITH2003 pp. 204211. 3. Floatingpoint normalization and rounding, IEEETC7/2000 pp. 638658, ARITH2001 pp. 712 + 173194, ARITH2003 pp. 95103. 4. Logarithmic arithmetic units, IEEETC7/2000 pp. 702726, ARITH2001 pp. 229245, ARITH2003 pp. 253261; Also [Cole00]. 5. Function evaluation by table lookup, ARITH2001 pp. 101108 + 128135, ARITH2003 pp. 114121 6. Arithmetic for cryptography, IEEETC7/2000 pp. 740758, ARITH2001 pp. 5965, ARITH2003 pp. 174202. Midterm Exam Preparation Textbook sections that are not required for the closedbook midterm exam: 3.5, 3.6, 4.4, 4.5, 4.6, 6.3, 7.2, 10.5 (some of these may be included in the final exam, which will be openbook) Final Exam Preparation The final exam will include Chapters 119 and 2124, emphasizing the topics covered after the midterm. The following sections are excluded: 3.5 (pp. 4548), 3.6, 4.4, 4.5, 4.6, 7.2, 10.5, 15.4, 15.6, 19.4, 21.4, 21.6, 22.6. All other sections are included, even if they were not discussed in class. Return to:
Top of this page ECE 252B: Fall Quarter 2002 offering
Calendar: Course
lectures, homework assignments, and exams have been scheduled as follows. This
schedule will be strictly observed. Textbook chapters are specified for lectures
and exams. It is a good idea to look over the specified material
before
each lecture if possible.
Homework: General Requirements Solutions should be brought to class on the due date
and handed in before the lecture begins. Late
homework will not be accepted, so plan to start work on your assignments early. Use a cover page that includes your name, course and assignment number for your solutions. Staple
the sheets and write your name on top of every sheet in case sheets are
separated. Although
some cooperation is permitted, direct copying will have severe consequences. Course Grade Stats
* Course = 25%(HW total / 8) + 25%(Midterm) + 50%(Final or Paper) ECE 252B f2002, Homework #1: Number Representation (chapters 14, due Wed. Oct. 9) Do the following problems from the textbook: 1.4, 2.5, 2.7, 3.2, 4.3 ECE 252B f2002, Homework #2: Basic & CarryLookahead Addition (chapters 56, due Wed. Oct. 16) Do the following problems from the textbook or defined below: 5.5eh, 5.D, 6.3, 6.15, 6.H Problem
5.D
Full adder hardware realization Problem
6.H
Designing fast comparators ECE 252B f2002, Homework #3: Other Addition Topics (chapters 78, due Wed. Oct. 23) Do the following problems from the textbook or defined below: 7.7, 7.18, 8.9, 8.14, 8.A Problem 7.18 Correction In part c, fractional precision modes are 4 ´ (8bit) or 2 ´ (16bit). Problem 8.A Generalized parallel counters (a) Show an implementation of a (5, 5; 4)counter using (3; 2)counters. (b) One level of (5, 5; 4)counters can be used to reduce five operands to two. What is the maximum number of operands that can be reduced to two when two levels of (5, 5; 4)counters are used? (c) Generalize the result of part b to a counter that reduces x columns of n dots to a 2xbit result. ECE 252B f2002, Homework #4: Basic & HighRadix Multiplication (chapters 910, due Wed. Oct. 30) Do the following problems from the textbook or defined below: 9.11, 9.14eg, 9.D, 10.3, 10.A Problem 9.14 Correction The last three parts should be labeled e, f, and g. Problem 9.D Sequential 2’scomplement multiplication (a) Represent x = 3, y = –3, and z = 5 as 4bit, 2’scomplement numbers. (b) Compute x ´ z to get the 8bit product, using the sequential algorithm with right shifts. (c) Compute y ´ z to get the 8bit product, using the sequential algorithm with left shifts. Problem 10.A Radix4 Booth’s recoding Show that radix4 Booth’s recoding is equivalent to the following scheme: (1) Begin with a radix4 operand employing the standard digit set [0, 3]. (2) Rewrite each 2 (3) digit as –2 (–1), with a radix4 transfer of 1 to the next higher position. This results in an interim digit set [–2, 1]. (3) Add the transfers to the interim digits to obtain the recoded number with the digit set [–2, 2]. At the most significant end, ignore the outgoing transfer for a 2’scomplement operand. ECE 252B f2002, Homework #5: Other Multiplication Topics (chapters 1112, due Wed. Nov. 13) Do the following problems from the textbook or defined below: 11.1, 11.11a, 12.2, 12.12, 12.F Problem 12.F Building larger AMMs A 6 ´ 2 AMM computes an 8bit value p = a ´ x + b + y, where a and b (x and y) are 6bit (2bit) unsigned numbers. Using dot notation, show how three such AMMs can be used to build a 6 ´ 6 AMM having two 6bit multiplicative and two 6bit additive inputs and producing a 12bit result. ECE 252B f2002, Homework #6: Basic & HighRadix Division (chapters 1314, due Wed. Nov. 20) Do the following problems from the textbook or defined below: 13.5bc, 13.12bc, 13.C, 14.1ab, 14.10ab Problem 13.C Sequential nonrestoring division Apply the following modified form of nonrestoring division to the unsigned division .101/.110. In each iteration, the shifted partial remainder is compared to ±d; if it is ł d (< –d), q_{i} = 1 (^{}1) is chosen; otherwise, q_{i} is set to 0. What do you think of this algorithm? ECE 252B f2002, Homework #7: Other Division Topics (chapters 1516, due Mon. Nov. 27) Do the following problems from the textbook or defined below: 15.6, 15.11, 15.12, 16.3, 16.A Problem 16.A Sequential versus convergence division Suppose multiplication and addition take 5 and 1 time units, respectively, while all support and control functions (counting, conditionals, register transfers, etc.) take negligible time due to overlapped processing. Be brief and state all your assumptions clearly. (a) Express the time needed for simple binary restoring division as a function of the word width k. (b) Express the time needed for division by repeated multiplications (without an initial table lookup or other speedup methods) as a function of k. (c) Compare the results of parts a and b. Comment on the speed/cost tradeoffs for different word widths. ECE 252B f2002, Homework #8: FloatingPoint Arithmetic (chapters 1720, due Mon. Dec. 4) Do the following problems from the textbook or defined below: 17.10, 17.15, 18.6bc, 19.C, 20.2 Problem 19.C Backward error analysis Suppose we compute x^{4} by squaring x and again squaring the result. Each squaring operation is done via a floatingpoint multiplication. Show that the computed result is z = [(1 + r)x]^{4} and establish a bound on the magnitude of r. Notes on homework solutions and other topics Practice problems from Chapters 2122 (solutions will be handed out by 2002/12/9): 21.9a, 21.11, 22.1, 22.12 ECE 252B f2002, Possible Research Topics The following is from the previous offering of the course in fall 2001. It will be updated early in the fall quarter to reflect new topics and references. In the following, IEEETC7/2000 refers to the latest computer arithmetic special issue of IEEE Trans. Computers published in July 2000 and ARITH2001 stands for the Proc. 15th IEEE Symp. Computer Arithmetic held in June 2001. 1. Design of parallelprefix adders, IEEETC7/2000 pp. 659680, ARITH2001 pp. 218225 + 277284. 2. Fast multiplication and squaring, IEEETC7/2000 pp. 681701, ARITH2001 pp. 2339 + 7379. 3. Floatingpoint normalization and rounding, IEEETC7/2000 pp. 638658, ARITH2001 pp. 712 + 173194. 4. Logarithmic arithmetic units, IEEETC7/2000 pp. 702726, ARITH2001 pp. 229245. Also [Cole00]. 5. Function evaluation by table lookup, ARITH2001 pp. 101108 + 128135 6. Arithmetic for cryptography, IEEETC7/2000 pp. 740758, ARITH2001 pp. 5965. Midterm Exam Preparation Textbook sections that are not required for the closedbook midterm exam: 3.5 (pp. 4548), 3.6, 4.4, 4.5, 4.6, 6.3, 7.2 (some of these may be included in the final exam, which will be openbook) Final Exam Preparation The final exam will include Chapters 119 and 2122, emphasizing the topics covered after the midterm. The following sections are excluded: 3.5 (pp. 4548), 3.6, 4.4, 4.5, 4.6, 7.2, 15.4, 15.6, 19.4, 21.4, 21.6, 22.6. All other sections are included, even if they were not discussed in class. Return to:
Top of this page ECE 252B: Fall Quarter 2001 offering
Calendar: Course
lectures, homework assignments, and exams have been scheduled as follows. This
schedule will be strictly observed. Textbook chapters are specified for lectures
and exams. It is a good idea to look over the specified material
before
each lecture if possible.
Homework: General Requirements Solutions should be brought to class on the due date
and handed in before the lecture begins. Late
homework will not be accepted, so plan to start work on your assignments early. Use a cover page that includes your name, course and assignment number for your solutions. Staple
the sheets and write your name on top of every sheet in case sheets are
separated. Although
some cooperation is permitted, direct copying will have severe consequences. ECE 252B w2001, Homework #1: Number Representation (chapters 14, due Wed. Oct. 3) Do the following problems from the textbook: 1.1, 1.6, 2.3, 2.9, 3.7, 4.11 ECE 252B w2001, Homework #2: Basic & CarryLookahead Addition (chapters 56, due Wed. Oct. 10) Do the following problems from the textbook: 5.3, 5.6abc, 5.7, 6.13 Additional problem 6.C Consider a 16bit carrylookahead adder with 4bit blocks. Assume that block p and g signals are produced after 3 gate delays and that each block uses ripplecarry internally. The design uses a lookahead carry generator with 2 gate delays. Carry ripples through each stage in 2 gate delays and sum bits are computed in two gate delays once all the internal carries are known. State your assumptions whenever the information provided is not sufficient to answer the question. a. Compute the total addition time, in terms of gate delays, for this 16bit adder. b. We gradually increase the adder width to 17, 18, 19, . . . bits using 4 ripplecarry groups of equal or approximately equal widths, while keeping the block p and g delay constant. At what word width k would it be possible to increase the adder speed by using an additional level of lookahead? Bonus (optional) problem for extra credit: Problem 6.4 in the textbook. ECE 252B w2001, Homework #3: Other Addition Topics (chapters 78, due Wed. Oct. 17) Do the following problems from the textbook: 7.13, 7.18, 8.12, 8.13 Additional background and correction for Problem 7.18: Fractional precision is the opposite of multiple precision. It is used when several lowprecision numbers (such as those found in multimedia data) are packed into a single word and processed in parallel. Adding two such words, for example, has the effect of several independent shorter additions. For this reason, the term "subword parallelism" has also been used to describe this approach. Subword arithmetic is often performed with saturation (see Problem 7.F below). In part c of the problem, "(4 x 8)bit or (2 x 16)bit" should be "4 x (8bit) or 2 x (16bit)". Additional Problem 7.F In certain applications, when the result of an arithmetic operation exceeds the maximum allowed value, it would be inappropriate to generate the result modulo a power of 2. For example, in media processing, we do not want addition of 1 to a black pixel coded as FF in hexadecimal to turn it into a white pixel 00. Discuss how twooperand addition can be performed with saturation so that whenever the result exceeds 2^k – 1, the maximum value 2^k – 1 is produced at output. ECE 252B w2001, Homework #4: Basic & HighRadix Multiplication (chapters 910, due Wed. Oct. 24) Do the following problems from the textbook: 9.4d, 9.10, 9.14abc, 10.1, 10.15 ECE 252B w2001, Homework #5: Other Multiplication Topics (chapters 1112, due Wed. Nov. 5) Do the following problems from the textbook: 11.3, 11.9, 11.17, 12.5a, 12.18 ECE 252B w2001, Homework #6: Basic & HighRadix Division (chapters 1314, due Wed. Nov. 14) Do the following problems from the textbook: 13.2, 13.9, 13.12d, 14.4cd (see below ), 14.14 Correction to Problem 14.4: In all four parts, change the magnitude of the divisor d to .1010 ECE 252B w2001, Homework #7: Other Division Topics (chapters 1516, due Mon. Nov. 26) Do the following problems from the textbook: 15.3, 15.5, 16.6, 16.12 Additional Problem 15.B Argue that the use of the quotient digit set [–6, 6] is preferable to the minimal digit set [–4, 4] in a radix8 divider that forms the multiple 3d by inputting the two values 2d and d into a fourinput carrysave adder tree that also receives the carrysave partial remainder as inputs. ECE 252B w2001, Homework #8: FloatingPoint Arithmetic (chapters 1720, due Mon. Dec. 3) Do the following problems from the textbook: 17.4, 17.8, 18.5, 18.18, 19.5 Bonus problem for extra credit: 20.4 ECE 252B f2001, Possible Research Topics In the following, IEEETC7/2000 refers to the latest computer arithmetic special issue of IEEE Trans. Computers published in July 2000 and ARITH2001 stands for the Proc. 15th IEEE Symp. Computer Arithmetic held in June 2001. 1. Design of parallelprefix adders, IEEETC7/2000 pp. 659680, ARITH2001 pp. 218225 + 277284. 2. Fast multiplication and squaring, IEEETC7/2000 pp. 681701, ARITH2001 pp. 2339 + 7379. 3. Floatingpoint normalization and rounding, IEEETC7/2000 pp. 638658, ARITH2001 pp. 712 + 173194. 4. Logarithmic arithmetic units, IEEETC7/2000 pp. 702726, ARITH2001 pp. 229245. Also [Cole00]. 5. Function evaluation by table lookup, ARITH2001 pp. 101108 + 128135 6. Arithmetic for cryptography, IEEETC7/2000 pp. 740758, ARITH2001 pp. 5965. Final Exam Preparation The final exam will include Chapters 119 and 2122, emphasizing the topics covered after the midterm. The following sections are excluded: 4.4, 4.5, 4.6, 19.4, 22.6. All other sections are included, even if they were not discussed in class. Return to:
Top of this page ECE 252B: Winter Quarter 2001 offering
Calendar: Course
lectures, homework assignments, and exams have been scheduled as follows. This
schedule will be strictly observed. Textbook chapters are specified for lectures
and exams. It is a good idea to look over the covered chapter(s) before
each lecture if possible.
Homework: General Requirements Solutions should be brought to class on the due date
and handed in before the lecture begins. Late
homework will not be accepted, so plan to start work on your assignments early. Use a cover page that includes your name, course and assignment number for your solutions. Staple
the sheets and write your name on top of every sheet in case sheets are
separated. Although
some cooperation is permitted, direct copying will have severe consequences. ECE 252B w2001, Homework #1: Number Representation (chapters 14, due Mon. Jan. 22) Do the following five problems from the textbook: 1.2 (p. 15), 1.9 (p. 16), 2.10 (p. 32), 3.6 (p. 51), 4.5 (p. 70) Hint for Problem 1.9: Compute the weights associated with the first 16 positions of a number. Bonus problem 1.D on number representation (for extra credit): We want to build an abacus for use with the Roman numerals system. There are to be seven positions labeled, from left to right, M, D, C, L, X, V, and I. Each position is to have positive (black) and negative (red) beads to allow representations such as MCDXXIV. What are the minimum required numbers of the two types of beads in each position, given that all unsigned integers up to 1500 are to be representable? ECE 252B w2001, Homework #2: Basic & CarryLookahead Addition (chapters 56, due Mon. Jan. 29) Do the following five problems from the textbook: 5.5 parts j, l, m only (p. 88), 5.8 (p. 88), 5.9 (89), 6.1 (p. 104), 6.14 (p. 106) ECE 252B w2001, Homework #3: Other Addition Topics (chapters 78, due Mon. Feb. 5) Do the following four problems from the textbook and part a of problem 7.E given below: 7.4 (p. 121), 7.16 (p. 123), 8.6 (p. 138), 8.10 (p. 139) Problem 7.E on selftimed carryskip addition: (a) Apply the carryskip idea to the selftimed adder of Fig. 5.9, illustrating the result by drawing a block diagram similar to that in Fig. 7.1 for a 16bit carrycompletion adder made of four 4bit skip blocks. (b) [optional bonus part, for extra credit] Analyze the expected carry completion time in the adder of part a, when blocks of fixed width b are used to build a kbit selftimed adder, and discuss the practicality of this idea. Note (correction to the solution to Problem 3.6, part c): It was brought to my attention that the proposed solution does not work when the number has leading 0s. In this case, the leftmost borrow of 1 will not be absorbed, leaving a number with an invalid digit 1. There seems to be no way around this problem. A 1 digit must create a borrow which must be propagated over a sequence of 0 digits. If 0s are not transformed to positive values, the borrow cannot be absorbed. Because the length of the sequence of 0 digits is unbounded, no local transformation (carryfree process) can decide if the 0s are part of a sequence of leading 0s. If you feel that you made this point but did not receive proper credit, please see me. Note (correction to the solution of Problem 6.1): Besides the misspelled "performing" in part a, the term "pi_i" (or b_i) in the expression for d_i in part b should be complemented. ECE 252B w2001, Homework #4: Multiplication (chapters 911, due Mon. Feb. 12) Do the following six problems from the textbook: 9.1 (p. 153), 9.4b (p. 154), 9.14a (p. 155), 10.1 (p. 169), 10.3 (p. 169), 10.15 (p. 171) ECE 252B w2001, Homework #5: Multiplication & Division (chapters 1213, due Mon. Feb. 26) Do the following three problems from the textbook, plus Problem 12.A given below: 12.4 (p. 205), 13.10 (p. 225), 13.13 (p. 226) Problem 12.A on synthesis of multipliers: a. We want to synthesize a 12by4 parallel multiplier using singlebit and 4bit binary adders as the only building blocks. Using dot notation, specify an efficient design that minimizes the cost, assuming unit cost for 1bit adders and 6 units for 4bit adders. b. Repeat part a, this time using only (4, 4; 4)counters and 4bit adders. c. Repeat part a, this time using 4by4 multipliers and 4bit adders as the only building blocks. ECE 252B w2001, Homework #6: Other Division Topics (chapters 1416, due Mon. Mar. 5) Do the following three problems from the textbook, plus Problem 16.B given below: 14.4a,b (p. 242), 14.8 (p. 243), 15.4 (p. 257) Optional problem (for extra credit): 16.10 (p. 274) Problem 16.B on iterative reciprocation: a. Compute the reciprocal of d = (.1100 0000)_two using x^(i+1) = x^(i) (2  x^(i) d) and arithmetic with 12 bits after the radix point throughout. b. Repeat part a, using the expansion 1/d = 1/(1  y) = (1 + y)(1 + y^2)(1 + y^4)..., where y = 1  d, instead of the NewtonRaphson iteration. Each term 1 + y^(2^(i+1)) is computed by squaring y^(2^i) and adding 1. c. Compare the results of parts a and b and discuss. ECE 252B w2001, Homework #7: FloatingPoint Arithmetic (chapters 1719, due Mon. Mar. 12) [Note on HW#6: The statement of Problem 16.10 seems to be in error and I have been unable to ascertain what the correct version is. If you are able to find the correct version of the suggested convergence formula, then do the problem. Otherwise, you can do Problem 16.11 instead, which is quite similar and serves the same purpose as the one originally assigned.] Do the following four problems from the textbook: 17.7 (p. 294), 17.14 (p. 295), 18.9 (p. 309), 19.9 (p. 325) Optional problem (for extra credit): 19.10 (p. 326) Notes on MRRE for logarithmic representation Consider two consecutive logarithms L and L + ulp and a number x that falls between 2^L and 2^(L + ulp). Relative error for rounding down = (x  2^L)/x Relative error for rounding up = (2^(L + ulp)  x)/x The worstcase occurs when the relative error is the same for rounding down or up. Thus, the worstcase x satisfies: (x  2^L)/x = (2^(L + ulp)  x)/x From the above, we get x = (2^(L + ulp) + 2^L)/2. Plug this into either relative error equation to get: MRRE = (2^ulp  1)/(2^ulp + 1) Because 2^ulp is very close to 1, MRRE is approximately (2^ulp  1)/2 ECE 252B w2001, Possible Research Topics The ECE 252B research topics for winter 2001 are based on the latest computer arithmetic special issue of IEEE Trans. Computers published in July 2000. The special issue contains six pairs of papers in the following areas. Each pair can be chosen as a research subject area. The research report will be based on a detailed study of the chosen pair of papers, plus additional references that the student will identify in order to prepare a complete and informative paper. The six subject areas are: 1. Function evaluation = reciprocation & squarerooting, pp. 628637 + CORDIC, pp. 727739. 2. Rounding, pp. 638658. 3. Addition, pp. 659680. 4. Multiplication, pp. 681701. 5. Logarithmic processors, pp. 702726. 6. Cryptography, pp. 740758. Return to:
Top of this page ECE 252B: Winter Quarter 2000 offering
Calendar: Course
lectures, homework assignments, and exams have been scheduled as follows. This
schedule will be strictly observed. Textbook chapters are specified for lectures
and exams. It is a good idea to look over the covered chapter(s) before
each lecture if possible.
Return to: Top of this page  Go up to: B. Parhami's course syllabi or his home page

