University of California at BerkeleyCollege of EngineeringDepartment of Electrical Engineering and Computer ScienceEECS150, Spring 2010Homework Assignment 12: Adders and Other Design BlocksDue April 23rd, 2pmHomework submissions must be made via the course SVN repository. Email submissions will notbe accepted! Please format your homework as plain text, or PDF, or another semi-universal format.Please do not submit Word files.Before starting the problems below, please read sections 5.1-5.2 of DDCA.1. Consider the bit-serial multiplier given in lecture 24, slide 5.To better understand this circuit, trace (write down the contents of registers at every cycle) themultiplication of 4’d5 by 4’b9 through a 4-bit bit-serial multiplier.Now propose how this multiplier can be extended to handle signed 2’s complement multiplication.2. The following are all important characteristics of any design block:• Latency: how many cycles does a single division take?• Throughput: how many divisions per cycle (a fraction) can your circuit handle? Notice thatpipelining can be used to improve throughput at the cost of latency.• Issue rate: How often can the circuit begin a new operation? In other words, every howmany cycles can the divider take a new set of inputs?In this problem, we will study the pop-count operator. This operator takes one 2’s complementN-bit input, and produces a 2’s complement output equal to the number of ones (high bits) in theinput. In other words, this operator counts high bits in the input. Such an operation is useful innetwork interfaces to interpret data that may contain bit flips (Wikipedia 8b/10b encoding for oneexample). In answering the following questions, you may use gates, registers, MUXes, and N-bitadders.(a) Design a 16-bit combinational pop count operator. What are the latency, throughput andissue rate of this design?1(b) Design a 16-bit bit-serial pop count operator. What are the latency, throughput and issuerate of this design?(c) In 2-3 sentences, discuss how the two designs can be combined to trade-off cost and perfor-mance.3. The partial design of a particular 8-bit carry lookahead adder is shown below. Many details areomitted for simplicity. Not shown are the carry-in and carry-out signals, c0and c8, the internalcarry signals, and the output signals, s0– s7.a0b0a1b1a2b2a3b3a4b4a5b5a6b6a7b7p0g0p1g1p2g2p3g3p4g4p5g5p6g6p7g7PAGAPBGBPCGCWrite boolean expressions for the following signals as they would be computed in an adder witha circuit as shown above.(a) p0=g0=(b) PA=GA=(c) PC=GC=(d) c4=(e) c8=2(f) s4=4. (a) The circuit shown below is used to multiply the 6-bit number X by a 6-bit constant value, C.It is made up of instances of a full-adder cell. The full-adder takes as input 3 1-bit signalsand outputs a 1-bit sum and a 1-bit carry.What is the value of C?FASumCarryFull-adderFAFAFAFAFAFAFAFAFAFAFAFA0x0x1x2x3x4x5p0p1p2p3p4p5p6p7p8p90(b) Using nothing but instances of the full-adder cell from part a), draw a circuit for adding four3-bit numbers, w2w1w0, x2x1x0, y2y1y0, and z2z1z0. First minimize the total delay thenthe total number of full-adder cells. Label all inputs and outputs.5. Consider the design of a carry-select adder using circuit elements where the delay through the2-to-1 multiplexor (any input to output) is exactly 1/2 the delay through a full-adder cell (anyinput to any output): τmux=12· τF A.(a) For a 128-bit adder with all select groups the same size (s), what group size and what numberof groups (g), will lead to an adder with minimal delay?s =g =(b) In general, for an n-bit adder of this type (carry-select with all groups the same size), whatis the optimal value for s and g as a function of n?s =g =Briefly justify your answer.36. You have a LOT of work to do. Please make sure you are able to finish your project.7. Extra for experts:Bit-serial operators are interesting for a number of reasons, particularly their economy of hard-ware resources. Applications that impose a modest baseline throughput requirement (such asaudio processing), and thus do not benefit from high-throughput arithmetic, can make excellentuse of this style of design.Alyssa P. Hacker is wondering how to build a 16-bit bit-serial divider. Being a mighty CS150student, propose one design for such a circuit, and compute the following for your design (if theanswer is input-dependent, give the best and worst cases):(a) Latency(b) Throughput(c) Issue
View Full Document
Unlocking...