1. [5 marks]
Prove that not(x) y + not(xy) = not(xy) algebraically (not using a
truth table).
(Our algebraic identities handout is appendix A to this exam.
For the web page version, see the algebraic identities handout in
postscript or PDF.)
2. [5 marks]
Find a minimal sum-of-products form for the function ab(b XOR c) + d,
using any method.
3. [10 marks]
Draw a sequential circuit which maintains a three-bit value in three
flip-flops (of any kind), with two inputs: "add one" and "subtract
one"'.
The "add one" operation is like a normal counter -- every time it cycles
to 1 and back to 0, the output of the counter increases by one, if you
interpret the three output bits as a three-bit base two number.
"Subtract one" performs the opposite function;
e.g. a 6 will change to 5 (and
then if the user presses "add one" next, it will go back to 6).
These two lines will never be 1 simultaneously, and each time they are 1 they
will stay at 1 "long enough" for any purposes.
You can use any desired components such as any kind of flip-flops, etc; and higher-level combinational circuit components such as decoders, full adders, etc.
4. [15 marks]
Design a sequential circuit with three boolean inputs and a clock input.
The three boolean inputs represent choices in a game.
On each clock cycle, the three boolean inputs get stored in three flip-flops,
one each.
Furthermore, the current three inputs are compared to the previous three
inputs (which are now coming out of the three flip-flops), in their
corresponding positions;
i.e. x0 is compared to Q0,
x1 is compared to Q1,
etc.
There are two output lines which represent a binary number from 0 to 3. The output value indicates how many of the three boolean inputs match their previous values.
For example, if the three bits this cycle are 010, and the three bits last cycle were 000, the output would be the number 2, since the outer digits match and the middle digit does not match.
5. [10 marks]
Suppose that we designed a gate technology which involved three different
voltage ranges on each wire rather than two; thus instead of a wire's voltage
level representing either 0 or 1, it could represent 0, 1, or 2.
(There are a great many disadvantages of such a scheme, which is why we don't
do it; but let's consider the possibility for this exam question.)
This would, of course, necessitate a complete redesign of all of our logic gates, and furthermore, they would have to be based on this three-value system instead of being based on boolean logic; so we won't draw any circuit diagrams in this system right now.
Instead, consider the fact that this would allow us to do base three arithmetic where our half-adders and full-adders now do base two arithmetic.
In the binary system, here is a truth table for the "carry-out" and "sum" outputs for a half-adder (with no "carry-in" input):
| x | y | c | s | |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | |
| 0 | 1 | 0 | 1 | |
| 1 | 0 | 0 | 1 | |
| 1 | 1 | 1 | 0 |
a) Draw the analogue of this table for a half-adder in this proposed trinary (base three) system. That is, your half-adder will take two three-valued inputs, and will produce a carry-out and a sum which are also (potentially) three-valued.
b) These half-adders could be combined to make a full adder (with carry-in) in much the same way as we combine half-adders to make full adders in binary (not exactly the same, but close). Similarly, we could then connect up a row of full adders with each full adder's carry-out connected to the next full adder's carry-in, and in this way we could produce a multi-digit addition, just as we combine our full adders to produce multi-bit addition now.
Identify one aspect of computer arithmetic which we would not be able to implement in basically the same way as we do it in binary, and justify why not in a sentence or two.
6. [10 marks]
Write a program in the PDP-11 assembly language to count the number of bytes
in memory addresses 10008 to 17778 inclusive (i.e. just
short of 20008) which are equal to their immediately-preceding byte.
For example, if byte locations 1234 and 1235 both contain the number 71,
that's a match which counts. If byte location 1236 also contains 71,
that's a second match. But if byte location 1236 contains the number 55,
and byte location 1237 contains the number 71, that 71 in 1237 does not
count as a match.
7. [10 marks]
Here is a subroutine in the PDP-11 assembly language which performs
multiplication by repeated addition, assuming that the second parameter is
non-negative. It is similar to an assignment four
question, although that assignment didn't ask for a full subroutine.
MULT: MOV R1, -(R6) ; save registers
MOV R2, -(R6)
MOV 10(R6), R1 ; first operand
MOV 6(R6), R2 ; second operand, guaranteed non-negative
CLR R0 ; R0 will be the return value
LOOP: TST R2
BEQ DONE
ADD R1, R0
DEC R2
BR LOOP
DONE: MOV (R6)+, R2 ; restore registers
MOV (R6)+, R1
RTS R7
Notes: BR is an unconditional branch; BEQ is branch if equal (i.e. if Z is 1).
In C or Java, this would look something like this:
int mult(int x, int y) // precondition: y >= 0
{
int retval = 0;
while (y > 0) {
retval += x;
y--;
}
return retval;
}
Alternatively, we could write this recursively, quite naturally:
int mult(int x, int y) // precondition: y >= 0
{
if (y == 0)
return 0;
return mult(x, y - 1) + x;
}
Write the recursive version in the PDP-11 assembly language.
8. [5 marks] Using our simple one-bus CPU architecture (see appendix B to this exam), write microcode which performs the PDP-11 instruction "CMP R0, R1", setting the condition codes.
Note that there is no "Subtract" ALU function. You will use the "Complement B" control line which if set, flips all the bits in the "B" operand coming from the bus. Combined with Set Carry-In, this can be used to perform subtraction.
Start your microroutine with step 3, after the standard fetch sequence.
9. [5 marks] Here is microcode to put the sum of the contents of registers R1, R2, R3, and R4 into Z. This is from my solutions to assignment four, except we're not worrying about the condition codes here. It is based on the one-bus architecture described in appendix B to this exam.
10. R1out, Yin
11. R2out, Add, Zin
12. Zout, Yin
13. R3out, Add, Zin
14. Zout, Yin
15. R4out, Add, Zin
Similarly, write microcode to put the sum of registers R1, R2, R3, and R4 into R5 using the two-bus architecture below. You should be able to use fewer steps.
10. [10 marks]
A divided highway has groups of lanes called the
"inner" and "outer" lanes.
Cars can switch from one set of lanes to the other only at specified
interchanges.
To improve traffic flow, sensors in the roadway determine the average speed of
cars in that group of lanes, and "pixel boards" which look like the
following picture advise motorists of the speed situation:
Each lattice point in the pixel board is a lightbulb, which can be on or off, and thus can be controlled by digital logic circuits.
This pixel board will show one of the following four messages:
OUTER AND INNER LANES MOVING WELL INNER LANES SLOW; OUTER LANES MOVING WELL OUTER LANES SLOW; INNER LANES MOVING WELL OUTER AND INNER LANES MOVING SLOWLY
Design the circuitry to compute which message to show, and to send the bits comprising the appropriate message to the pixel board.
Use high-level components. For example, the bits comprising the above messages should be stored in a ROM, and you don't have to specify what all the bits are, just how that ROM is used and what it is connected to.
Your inputs consist of two numeric speed values in km/h, one for the inner lanes, one for the outer lanes. Traffic is deemed to be "moving well" if the speed exceeds 70 km/h, and "moving slowly" (or "slow") if the speed is 70 km/h or less. Also use high-level combinational circuitry components; for example, a comparator which outputs whether or not its input is greater than 70.
End of exam. Total marks: 85.