Silicon Programming--Winter 06-07--Assignment 1--due Jan. 19at beginning of class.

Each problem is worth the same number of points. Please write neatly or type. Be sure all parts of your assignment are stapled or securely clipped together. This homework is to be YOUR INDIVIDUAL WORK. You may ask questions of our grader or of me. You are encouraged to discuss general concepts with your classmates, but the answers you turn in should be yours alone.

1. a. show that NOR is a complete set for 2-input boolean functions.

b. Is NAND associative? (Hint: use a truth table to prove or disprove your answer).

2. Use a K-map to simplify:

f(A,B,C,D) = A'B'C'D' + A'B'CD + ABC'D' + ABC'D + ABCD + ABCD' + AB'C'D' + AB'C'D.

3. Design a comparator for two-bit unsigned binary numbers a =a1a0, and b=b1b0, with output 1 if a >= b and 0 else. Use AND-OR-NOT logic and simplify using a K-map if possible.

4. Design an 8-bit incrementer using AND-OR-NOT gates. Assuming the time through a gate is 2 ns (nanoseconds) and the time through a wire is negligible, calculate the time through a critical path in your design. (Note: an incrementer adds 1 to its input; an incrementer is simpler than an adder).

5. Using AND-OR-NOT logic, design a 1-bit "full subtractor", where inputs are A,B, and BORROWIN, and outputs are DIFFERENCE and BORROWOUT. (Assume inputs are positive).

6. Design a fsm to recognize the pattern 1111 in a string of input bits. Overlapping patterns should also be found, e.g., 0111110 contains 2 instances of 1111. Design your machine so that it uses a minimal number of states. Show how the machine could be implemented using appropriate flip-flops and combinational logic.

7. Using AND-OR-NOT logic, compare the number of gates and the delay for a 4-bit adder to add inputs A = A3A2A1A0 and B = B3B2B1B0 to produce S = S4S3S2S1S0

a. if it is designed as a "carry-ripple" adder (using 4 full adders connected in series)

b. if it is designed to minimize the time to compute the sum (by using extra hardware to compute the carries immediately).

Assume each AND or OR gate requires 2 units of delay; assume NOT requires one unit of delay.

8-10. Building a computer. While today's microprocessors continue to deliver more and more computing capability with decreasing area and power requirements, an increasing number of embedded systems applications require flexible programming with very limited resources. Examples include applications in environmental control, automobiles, health care, avionics, and space exploration. Thus the ability to design a powerful yet very simple processor is still important. To see how one might go about this, your task is to finish the "design" of a simple computer with the following architecture (ref. Hill & Peterson, Digital Systems, 1978). The machine will be a 1-register ("accumulator") machine (AC). Operands for single-operand instructions will be in the accumulator (not, shift, …), Operands for 2-operand instructions will be in the accumulator and memory (add, load, …). There will also be a separate "carry" flip-flop (CF) to hold the carry-out of an adder, a shifted bit, or possibly a condition. Additional registers will be 2 index registers called IA and IB, as well as the memory data register (MD), the memory address register (MA), the instruction register (IR), and the PC (PC). CF is 1 bit, MA, IA and IB are 13 bits, and all other registers are 18 bits.There are two 18-bit input buses to the ALU, ABUS and BBUS, and one 19-bit output bus, OBUS. Below is a schematic of the computer's data unit.

ABUS (18) BBUS(18)

ALU output

OBUS (19)

The memory is word-addressable. Each word will be 18 bits long. Instruction format:

Address modes will be direct, indirect, indexed by IA, or indexed by IB.

I/O will be to and from the accumulator (this is a very primitive machine).

Opcodes: Use an "expanding opcode" format: op codes 000-110 denote operations which may access memory; op code 111 signifies that the other 15 bits do NOT contain a memory address. Op code 111 operations can include, e.g., shifts, I/O, checking accumulator or carry bit, …

This computer must be capable of performing "general purpose" computing: it must be able to do integer arithmetic (integer 2's complement add, subtract, multiply, and divide, where the result of a divide is a quotient and a remainder); logical operations (and, or, not); jumps (conditional and unconditional), so that loops and choice functions may be implemented; simple subroutine call and return, and interrupts.

1. what should the instruction set be (specify op codes 0-6 and important op code 7 instruc.)?

2. What should be inside the ALU?

3. What signals must be generated in the control unit? what will each signal affect?

4. How will subroutines be handled?

5. How will interrupts be handled?

6. For your machine, write programs to: a. compute the sum of n numbers; b. bubblesort n numbers; c. call a swap subroutine (SWAP(X,Y) exchanges contents of mem locations X and Y).