EEM16/CSM51A Logic Design of Digital Systems Winter 2022

NOTE:

1. This final exam is to be done individually using Logisim Evolution v3.7.2.

2. Submission Procedure: You need to submit your solution online via Gradescope. Please read the section titled “What to submit?” at the end of this document.

3. Late Submission: There is no late submission.

4. Logisim:

○ You must use the version of Logisim made available for download on Piazza. As you edit in Logisim, save frequently and also make backup copies of your design file.

○ We will grade using the top-level circuit (it is labeled DUT in most cases), but you are free to create additional sub-circuits which you use in DUT.

○ I highly recommend using Logisim’s tunnels which make your circuit cleaner and allow for

easier debugging; they allow you to move a value from one part of the circuit to another without having to drag a wire all the way across. You can create tunnels for all the inputs

and their complements. Instead of hooking up the inputs directly to the gates, you can hook

up using tunnels instead.

○ Do not rename or move any input or output pins, or add any additional pins. Doing so will in all likelihood cause the Autograder to fail and result in points to be deducted (see below).

○ Testing is as critical as design, and in particular, make sure to test for edge cases. For manual testing, you can use the hand tool and click on the input pins to change their values,

which will propagate to the rest of the circuit. You can reset the simulation back to the start with Ctrl-R to test again after you make changes. You can also use the Test Vector feature to automatically test your circuit.

○ The Test Vector and Command-line Verification features in Logisim Evolution allow you to test your circuits. You can read more about them in the Logisim Evolution User's Guide. You are also free to exchange test cases (i.e. expected input-output pairs) or collaboratively create them with other students in the class, but are not allowed to share testbench (i.e. circuits designed to test) as that is viewed as part of the work.

○ You must use designs relying only on gates and within specified component limits that are permitted for each problem. Failure to do so will result in a zero score.

○ Save frequently and commit frequently! Try to save your code in Logisim every 5 minutes or so, and commit every time you produce a new feature, even if it is small.

○ As you work on your Logisim design, make use of additional subcircuits, tunnels, piobes, etc. to make your design modular so that the design is easier to understand and debug.

5. Please comply with all the instructions as failure to do so can cause Autograder to not be able to test your design. If we have to manually grade because your failure to comply with instructions (e.g, file names, pin naming, etc.) required us to fix, we will deduct 20% of the maximum points from each question where the problem occurs. Note that this does not apply to design bugs - there is no manual grading.

6. Grading: Please read the section titled “Grading” towards the end of this document.

7. You will need to submit a report as well, using the template at

https://docs.google.com/document/d/1g2TwlxFcqt9d9W-zreTWJjueQkD67KuKbYCc8MVcV18

(make a copy, edit, save as PDF, and then upload on Gradescope)

8. Version History:

○ 1.0: initial release

Task: Cube Root Computer

The goal in this task is to design a synchronous positive-clock-edge triggered sequential system that takes in a 2’s complement number [23: 0] as input and returns as a 2’s complement number [8: 0] the real-valued cube-root of [23: 0] rounded towards zero.

E.g. an input of 419430310  =   0011111111111111111111112 will result in an answer of

16110  =  0101000012 , and an input of − 419430310  =   1100000000000000000000012 will result in an answer of −  16110  =  1010111112  .

You can think of your system as a server computer that is responding to requests from an external client as in the figure below (note that the figure omits the clock and reset signals).

The client interacts with the cube-root server via a four-phase request-acknowledge handshake which     involves a signal called that goes from client to server, and a signal called that goes back from the server to the client. Normally and are both 0 . To initiate a new transaction with the server,   the client will put the necessary inputs for the server on and set =  1, The server, upon seeing =  1will know that there is a new task, and start computing using the values on . When done, it  will put the results on and also set =  1 . The client upon seeing =  1 will know that the     server is done, and read , and then set =  0 to tell server that it is finished reading and the server acknowledges by setting =  0 . Clearly, client must keep stable while =  1 and   the server must keep stable while =  1 . The figure below details this handshake (in the figure one an consider ( )  to represent the computation of the real-value cube root).

Four-Phase Handshake (Return-to-Zero Handshake)

The following pseudo code describes the handshake from the perspective of your system:

Initial State:

Step 1:

Step 2:

Step 3:

Step 4:

Step 5:

Step 6:

REQ and ACK are both 0 after

While True:

Wait for REQ==1

DOUT = RealCubeRoot(DIN)

Set ACK=1

Wait for REQ==0

Set ACK=0

reset

// wait for new DIN

// this may take variable # of  clock cycles

// tell client that DOUT is ready

// wait for client to acknowledge reading DOUT

// tell client that we are ready for next input

Your design should follow the following specification. You would likely find it useful to consider splitting the task into a controller FSM and a datapath.

Clock: Inputs: Outputs:

, , [23: 0]

, [8: 0]

Starter Logisim File: final.circ

Main Circuit: DUT

Allowed Logisim Modules

●    From Gates library: only NOT, and NAND.

●    From Memory:  only D Flip-Flops and Register from Memory

●    From  Arithmetic:  at  most  2  Multipiers,  at  most 4 Adders, at  most 2 Subtractors, at  most 2 Comparators. No other components from Arithmetic.

●    From Plexers: at most four Multiplexers. No other components from Plexers.

●    From wiring: any except Transistor, Pull Resistor, POR, Transmission Gate, Power, and Ground.

○    Note that while you can use Pin in any subcircuits that you define, you must not add any Pin to DUT as that will cause failure with the Autograder.

●    From Input/Output: Any.

●    None from any other library.

Restrictions

●    At most 1000 components total (your design will have a lot fewer; this is just a conservative limit and designed to prevent students who seek to game things by using excessive combinational logic). Logisim components such as pins, tunnels, wires, probes, splitters, LEDs, buttons, etc. that are used for wiring and I/O are excluded. The intent of the problem is that you should not attempt to build complex datapath blocks using simple gates. Please do not attempt to bypass this spirit of the problem.

●    Since the system is required to be synchronous, you should not use any asynchronous inputs in any sequential elements that you use - e.g. do not use the asynchronous set or reset signals on flip-flops.

Cost of Logisim Components

● -bitwidth NOT: 2  ×

● -bitwidth NAND with inputs: 2  × ×

●    D Flip-Flop: 18

● -bitwidth Register: 20  ×

● -bitwidth Adder, Subtractor, Comparator: 28  ×

● -bitwidth Multiplier: 28  × 2

● -bitwidth 2 -to-1 Multiplexer: 6   × ×  2 +   2 +   ( >  1 ? 2   × × 2 :  0)

○    For a -bitwidth 2-to-1  Multiplexer, the cost expression simplifies to 12 +  2 .

Desired Behavior:

1.   The active edge of is the rising edge unless otherwise specified.

2. is meant to be used as a synchronous reset signal. Whenever the external world wants to reset the system, it will assert =  1 for at least one rising edge of and then make

=  0 to start normal operation. Note that reset may occur multiple times as the system runs, and even in the middle of a handshake.

3.   The external world does not care about the values of output signals on clock edges before the first clock edge after the start at which your system sees =  1 .

4.   If =  1 at a clock edge, then the client must see =  0 at the next clock edge and likewise your system is assured to see =  0 at that clock edge (i.e. the next clock edge).

5.   Your system should produce and in accordance with the functionality described earlier.

Desiderata:

●    Correct functionality

○    If your design fails our tests, your score will depend on the report only.

○    Please test carefully, particularly for edge cases.

●    Low ×

○ is  measured  by adding  up all the component costs  (you can get this from the Autograder when you upload)

○    We will measure in terms of average # of clock cycles from becoming 1 to becoming 1 while with correct )

■    You can obtain it during your testing. Think about the worst case.

○    Note that a simple algorithm that searches for solutions in a brute force manner will result in  a of a little bit over 200. But smarter algorithms can reduce the to around

10 but at the cost of a more complex design.

●    Good architecture and clean design, testing strategy, quality of explanation, etc.

What to Submit:

●    Your design in final.circ (using the starter version of this file)

●    For  every  control  FSM  in  your  system,  you  must  provide  a  .gv  file  gv  (state  graph  using https://edotor.net or https://sketchviz.com), naming them as final_ 1.gv, final_2.gv, and so on. T

●    A report final.pdf using the template (see URL under instructions). The report will include (see template for details):

○    For every control FSM, the state transition diagram, the state transition table, assignment of states to bitvectors

○    An overall block diagram showing how the various control FSMs interact with each other and with the datapath, as well as a  high-level via of the various components  in the datapath.

○    A block diagram of your datapath and how it interacts with the various control FSMs

○    Description of testing strategy.

○    Analysis of × product

○    Note  that  when  grading  the  report,  we  will  consider  not  only  correctness  but  also efficiency (e.g., how many states did you used), clarity, and lack of unnecessary verbiage.

Grading

You will get a score of zero if any gates other than those allowed for a problem are used. You may use (and in fact encouraged to) use subcircuits in Logisim to create nice hierarchical designs. Problem scores will be split as follows:

Functionality: × :

50% (this comes from Autograder)

20% (this comes from Autograder)