# Computer Science 237 Computer Organization

### Williams College Fall 2006

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

#### Agenda

• 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:
1. add y to product, store result in product
2. 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 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;
}
```