Lab Assignment #3, July 22, 2002

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

Introduction: This lab consists of implementation of an error correction circuit for a specific code on LogicWorks.

Error Correction Code

It is reputed that the ancient Mayan civilization used a base-8 number system and that they furthermore had developed a computer that represented base-8 numbers! In order to represent a base-8 number they had developed a (rather inefficient; it used 8 bits instead of the minimum 3!) code as follows:
 
0 10000010
1 01000100
2 01000011
3 00101000
4 00100101
5 00011001
6 00010110
7 00001111

In order to understand this exercise, consider the following rule: for every bit with the value 1, subtract the index of the bit. (Consider the rightmost position to be at index 1 and the leftmost at index 8.)

You are asked to develop an error-correcting code, by understanding the Hamming distance of the aforementioned code and generating the appropriate logic circuitry for correcting all errors that can be corrected according to the Hamming code distance analysis. In order to do this, you will need probably to perform the appropriate addition and subtraction operations. In addition to this, you will need to identify the location of the faulty bit. A convenient circuit that will let you identify the faulty bit index is the decoder shown here.

As can be seen on the figure, the decoder has four inputs (S3..0). Depending on the value of the inputs, one of the outputs of the decoder becomes a 1, all of the others are zero. Since an XOR gate with one input connected to 1 acts like an inverter gate, depending on the value of the inputs to the decoder, the corrupted bit will be flipped (inverted); thus the erroneous word with one bit error will be corrected. You have to determine which 4 bits to use as S(3..0). (The actual decoder given to you will not have an enable pin).

In order to sum and subtract the appropriate indices, you can use a circuit similar to the divider circuit that you have constructed in your previous lab. In that circuit, the dividend was placed in the A and Q registers and a right-to-left shift of the dividend was performed, with the sign of the result of a subtraction providing a signal that was used to determine whether or not to load the result of the subtraction into the A register.

While a right-to-left shift is still useful in this context, a shift of the accumulator is no longer needed ( this is no longer a positional number system) and instead of subtracting the divisor, you need to subtract the index of the left (most significant) bit currently stored in the Q register (use an 8SHIFT_REG for Q). You can achieve this by using a Counter-8 device for the M register and decrementing it (starting from 8), which should correspond to the index position of the bit being scanned in the Q register.

The algorithm is given as follows: The algorithm consists of the following steps in the given order:

You need to get the new control for this circuit. It will have a similar interface to the control for the restoring division:

You are supplied with the control unit. The control unit has three input signals, CLK, Begin, CurrentBit, 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. CurrentBit: This is how you tell the control unit what bit of the code word is being examined currently.
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 computation is completed
  3. LoadA: Loads data into accumulator A
  4. LoadQ: Loads the data into the Q register
  5. Count: This signal can be used to tell the M register when to load and decrement.
  6. ShiftQ: Tells the Q register when to shift.
  7. Source: Determines which set of inputs will be loaded into register A (0 if initial inputs, 1 if result of addition/subtraction)
  8. A/S: Indicates whether the operation is addition or subtraction (0 = add, 1 = subtract).
  9. LoadM: Loads the data into the M register
Another component that you will probably find useful is an absolute value evaluator. This component can be obtained when the most significant bit (the sign bit) of the second operand is connected to the add/sub input of an adder/subtracter, with the first operand being 0.

Use the Lab3 library on the class website. This is similar to the library used in the last lab, but the adder/subtracter has been modified, a new control unit has been added, and a decoder has been added.

You are asked to the following:

    1) Identify the error correction needed and define a strategy for implementing it in line with the above comments
    2) Modify the datapath according to the given hints.
    3) Simulate your circuit with the following three sets of data: