### Homework assignment 7

This is a five-part assignment. The parts are to be submitted using submit under the name hw7. Solutions are due at November 4 at 11:59pm.

This is not a partnership assignment. Hand in your own work.

### Problem 7.1

Implement a 4-2 multiplexor (four inputs, two selector inputs, and one output) using nothing more than 2-1 multiplexors. Here's what we mean by a 4-2 multiplexor:

 ``` s1 s0 Q 0 0 A 0 1 B 1 0 C 1 1 D ```

Submit your solution, a file named mux4_2.circ.

### Problem 7.2

Using the same method that you will have for an adder in lab, implement a 4-bit subtractor. First, construct a truth table for a bit slice. It has three inputs: A, B, and BRin (borrow in). It produces two outputs: R and BRout. The way it works is just like when you learned to subtract. A minus the Borrow minus B produces one bit of the result and a Borrow (which may be zero) from the next higher position. Do the following example by hand first.

```A:   1 1 0 1    (13)
B:  -0 0 1 1     (3)
--------
C:   1 0 1 0    (10)
```

Submit your solution, a file named subtractor.circ.

### Problem 7.3

You are to implement a 4-bit 4-input circuit that sorts its inputs in a single clock cycle (hence the name "parallel" or "combinational" sort).

Shown below is a schematic of the `ParallelSort` module. Your job is to translate this schematic into Logisim. We have already done some of the work for you; you may create new wires as needed, but you may not add inputs or outputs.

The schematic uses two other circuits, Exchange4 and Register. Registers are provided in one of the Logisim libraries; choose Project->Load Library->Memory to access them. You are to design Exchange4 yourself. It takes two 4-bit inputs A and B. Its two outputs are max(A,B) and min(A,B). We suggest that you use your subtractor from exercise 7.2 to implement Exchange4.

If you have a few extra minutes:

• Attempt to simplify the circuit by reducing the number of `Exchange4` instances. Is it possible? Why or why not?

• Can you come up with a design for a sequential sorter which uses fewer `Exchange4` instances by sharing them over time?

Submit your solution, a file named sorter.circ.

### Problem 7.4

Modify your 4-bit counter from lab so that it is a configurable up/down counter. Do this by introducing an additional flipflop that holds the "state", i.e., a bit that determines whether it counts up or down and an input to set this state bit. Do not change the structure that you have built with FAs and D FFs. Instead, use the state bit to select one of two increment values with a mux.

Submit your solution, a file named counter.circ.

### Problem 7.5

In lab you saw a shift register (online in the file ~cs61cl/code/shiftreg.circ). A one-dimensional pong game of sorts can be designed in the same way. It should have a set of five D FFs like in the shift register, but in this case when the 1 hits the right end it reverse and heads back to the left. When it hits the left end it reverses again. Like the up/down counter, you will want to introduce a bit of state that is the direction. Use muxes to steer the bits in the correct direction.

Submit a file named pong.circ.