Lab Assignment #2, Due July 15, 2002

         Due 1:00PM, to be emailed to sgossin@cs.ucsd.edu

Introduction: In this lab you are asked to complete an assignment composed of two parts. In part 1, you will build a divider using the restoring algorithm described in the lab lecture. In part two, you will be given a number of logic function pairs. You have to show whether the function pairs are equivalent or not by implementing these functions, XORing the two outputs of the functions, and if they are not equivalent, pinpointing the input combinations for which the two differ.

Part 1: Restoring Division (of positive integers)

In this part of the experiment, you will build a circuit that divides a positive 15-bit integer dividend by a positive 8-bit integer divisor by using LogicWorks. The datapath of the design is given in the following figure. You may refer to this restoring division algorithm description here!
 
 

You are supplied with the control unit. The control unit has four input signals, CLK, Begin, S, and A7 and has several output signals. The input control signals are:

  1. CLK: The clock signal that will be used for the entire circuit.
  2. Begin: When this signal is set to 1 and then 0, the circuit is reset.
  3. S: This is the sign of the result of the subtraction.
  4. A7: This is the most significant bit of the value in the A register (used for shifting).
The output control signals are:
  1. CLR: Used to clear the values in the registers at the beginning of computation
  2. End: Indicates that the division is completed
  3. LoadA: Loads data into accumulator A
  4. LoadQM: Loads the data into the Quotient register, Q, and the divisor register, M.
  5. ShiftA: Shifts register A to the left. The most significant bit of the Q register must be shifted into the least significant bit of the Accumulator (register A).
  6. ShiftQ: Shifts the Q registers to the left. This is performed one more time that the ShiftA.
  7. Source: Determines which set of inputs will be loaded into register A (0 if initial inputs, 1 if result of addition/subtraction)
  8. Q: The value of the next quotient bit (as determined by the previous subtraction)
  9. A/S: Indicates whether the operation is addition or subtraction (0 = add, 1 = subtract).
  10. SO: The previous value of the most significant bit of the A register (A7). This value is shifted through the control unit ad appears in this pin.
The algorithm consists of the following steps in the given order: The control unit will supply you with the necessary control signals, once you assert the begin signal. What you need to do is to hook up the control signals to the datapath. The control signals provided by the Control unit are:
 
 
Cycle CLR End LoadA LoadQM ShiftA ShiftQ Source Q A/S SO
0 1 0 0 0 0 0 0 0 1 0
1 0 0 1 1 0 0 0 0 1 0
2,5,8,11,14,17,20 0 0 0 0 0 0 1 1/0 1 1/0
3,6,9,12,15,18,21 0 0 1/0 0 0 0 1 1/0 1 1/0
4,7,10,13,16,19,22 0 0 0 0 1 1 1 1/0 1 1/0
23 0 0 0 0 0 0 1 1/0 1 1/0
24 0 0 1/0 0 0 0 1 1/0 1 1/0
25 0 0 0 0 0 1 1 1/0 1 1/0
26 0 1 0 0 0 0 0 0 1 0

For this part, we will add new components to the CSE140L library. These are the Control unit, a shift register with parallel load and synchronous reset for register A, Q, and M, a 9-bit Adder/Subtracter, and 8 2x1 multiplexers.

The control unit takes 4 inputs. CLK is the clock signal used in your circuit, S is the sign of the result of the 9-bit subtraction (the most significant bit), A7 is the most significant bit of the A register, and Begin is the signal that will begin the division process (Note that begin must be set to 1 and then 0 for the process to begin).

For registers A, Q, and M use the 8SHIFTREG register. For this register CLR sets the output to all 0's. CLK is the clock signal for the circuit, SH will cause the register to shift on the next clock signal, LD will cause the register to load the inputs (D0..7) into the outputs (Q0..7) on the next clock signal, and SI represents the bit that will be shifted into Q0 if SH is also set.

The 9ADDER_SUB device will perform A+B or A-B depending on the value of the A/S pin (0 for Add, 1 for subtract).

The 8MUX2_1 device will either output A or B to the Q pins depending on the value of the S0 pin (S0 = 0 will select A, S0 =1 will select B).

Initially, you must load the 15 bit dividend into registers A and Q. The most significant bit of the dividend should be in the most significant bit of register A, and the least significant bit of the dividend should be placed in the second least significant bit of register Q. The divisor must be loaded in register M.

A detailed step-by-step example of this algorithm can be found here.

Part 2: Logic Functions

In this part, you are given four pairs of logic functions. You need to decide whether these function pairs are equivalent or not. In case when the functions are not equivalent, you need input combinations which produce different outputs. First implement both of the functions and connect the outputs of the two functions as inputs to an XOR gate. Next, test all possible 4-tuples and see if the value of the XOR gate is ever 1. These are the inputs for which the two functions differ. Identify all such inputs.

1. BD + AD', AB + A'BD + AB'D'
2. C'D+BD, A'C'D + ABC' + ABD + B'C'D
3. A'B + AD', AB + BD' + AD'
4. AC' + A'B + A'C, A'B'C + A'CD' + A'BD + BC'D' + AC'

Requirements:
For part 1, you need to return the circuit design in LogicWorks. In the report text file provide a short overview of your implementation of the restoring division algorithm and the work separation amongst the team members, if any. For part 2, identify the complete set of input combination(s) that you found out to show the inequality of function pairs. Also return the schematic of your implementation of the logic functions in logic gate representation when the counter is connected. You can also return a formal proof of whether the function pairs are equal or not.
Remember to email your *.cct files and the report ASCII (text) to sgossin@cs.ucsd.edu