## Computer Science 237 |

**Lecture 21: Error Correcting Memory, Computation Circuits****Date: October 30, 2006**

* *

- Announcements
- Computer Science registration open house - Wednesday at 6 PM
- Lab 6 back soon
- Lab 7 due now

- Wrapup of Error Correcting Memory
- Lab 8 Out
- form groups of 2 or work individually
- meet in TCL 312b at 1:15 sharp to get started - stay as long as you'd like or leave after the intro
- your circuits must be complete and graded by Tuesday, November 7
- no late submissions because of the exam coming right after this lab is done

- Computation Circuits
- Suppose we want to build a circuit for multiplication, but not a combinational circuit like we built for addition
- Can we compute it like this function?
int mult_by_adding(int x, int y) { int product = 0; while (x > 0) { product += y; x--; } return product; }

- To develop this into a circuit, we use registers to represent variables and wires to represent loops
- Hex keypads to input values (we'll use single hex digits, but it's easy enough to expand)
- Three registers: x, y, product
- To start, copy values from hex keypads into x and y, clear 0
- add an "initialize" switch to do this

- After initialization, we need to loop. On each step:
- add y to product, store result in product
- subtract 1 from x, store result in x

- note that x register can be set by the hex keypad or by the result of a decrement - need to treat inputs as a bus and make sure it has exactly one (and the correct) driver when its CLK input goes high
- continue looping until x becomes 0, then no more adding
- The loop needs to happen in stages and remain synchronized
- for each time we subtract 1 from x, we want to add y to product
- there will be adders to do all of this, but adders are
*always*adding whatever values are presented on their inputs - we don't want to have the result go back around and get added again and again - we will use a clock input (actually a switch in the circuit, but realistically it will be a clock) and come up with substages/phases where we do parts of the computation
- how to build such a clock?
- convert a single clock input into 4 "time shifted" clocks at a lower frequency
- we'll use the lower 2 bits of a counter - other possibilities as well

- Phases in this computation:
- Phase 0: let adders add
- Phase 1: copy results of adders into temp registers
- Phase 2: put temp register outputs onto x/product register inputs
- Phase 3: copy values into x/product registers

- Need to stop when x gets down to 0, even though the clock may/will continue
- LOTS of room for optimization - do we need all those registers? phases?
- Think about: can we build a faster circuit to implement the
"shifty multiplication" example from earlier in the semester?
int multiply(int x, int y) { int product = 0; while (x) { if (x&1) product+=y; x >>= 1; y <<= 1; } return product; }

* *

- RepeatedAddition