Part 1: Error Code Correction

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 sum the indices corresponding to the non-zero entries and subtract this sum from the invariant sum of the word entries in the illustrated code words. In addition to the sum, you will need to identify the location of the faulty bit. A convenient circuit that will let you identify the faulty bit index is a decoder shown here.

As can be seen on the figure, the decoder has three inputs (S2..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.

In order to sum the indices of the non-zero entries, you can use the multiplier circuit that you have constructed in your first lab. In that circuit, the multiplier was placed in the Q register and a right-to-left scan of the multiplier bits provided us the signal for adding the multiplicand onto a repeatedly shifted partial sum. While a right-to-left scan is still useful in this context, a shift of the accumulator is no longer needed (remember this is no longer a positional number system) and instead of adding the multiplicand, you need to add the index of the bit in the Q register. You can achieve this by incrementing the M register (starting from 1), which should correspond to the index position of the bit being scanned in the M register.

The algorithm is given as follows:

• Accumulator = 0, Counter = 1, Multiplier = Code
• Repeat 8 times
• If least significant bit of Multiplier is one Accumulator = Accumulator + Counter
• Shift Multiplier to the right, Counter = Counter + 1
• End

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 data:
• 10110001
• 11010010
• 00110101
• 00100001
• 00101100

Part 2: Logic Functions

As you have seen in your text, Gajski, Principles of Digital Design, Ch-3, multiple variant implementation of the same circuit exist. Besides, canonical, standard, and nonstandard forms, another dimension in constructing such circuits, is the type of complex gate discussed in section 3.9, such as AOI and OAI gates. Such complex gates frequently do not share axiomatic bases that define the operators of Boolean algebra. Neither is it straightforward to develop methods and approaches for the simplification of such complex gates.

While the inhibition ('@') and the implication ('#') operators (defined in Section 3.7) are in same sense primitive logic operators of two variables, they also share a number of characteristics of the aforementioned complex gates. We ask you to map a function given as a sum-of-minterms to a form that can be expressed as a combination of inhibition and implication gates (no other gates, not even inverters, even expressed as inhibition or implication gates can be used). After implementing the given function in this form you are asked to measure its delay.

In actual implementation of logic gates, there is a delay between the time at which the input is changed and the time at which the effect of the input change is observed at the output. Our aim is to measure the propagation delay of an inverter gate. The propagation delay of a gate is defined as the average time needed for input change to propagate to the output. The output of a gate can go from L to H, or H to L. The propagation delay for L to H is defined as t_plh and the propagation delay H to L is defined as t_phl . The average propagation delay can be defined as the average value of  t_plh and t_phl . Therefore,

 t_p = (t_plh + t_phl )/2

Signature: _________________________________

How to measure delay of a logic function:

1. Find an input combination such that inversion of one of the inputs will invert the output.
2. Apply a square wave to that input. The period of the square wave should be larger than twice the propagation delay of the boolean function for that particular input.
3. Observe both input and output wave form on the oscilloscope simultaneously in order to measure the propagation delay

You will use your ring oscillator as a square wave generator for the measurement of propagation delay. However, in order to get the period of oscillations long enough you need to modify the ring oscillator circuitry as in the following figure:

Implementation of a logic function with inhibition and implication operators.
The inhibition operator is denoted by '@' and defined as A@B = AB'
The implication operator is denoted by '#' and defined as A#B = A + B'

The function you are asked to implement is:

F = xyz + xy'z' + x'y'z

 F = [? @ { (? @ ?)  #  (? # ?) }] # [? # { (? @ ?) # (? # ?) }]

You may find the following identities of inhibition/implication gates useful in developing the desired function

• x + y = y # ( y # x ) = x # ( x # y)
• x + y' = x # y
• y + x' = y # x
• x' + y' = (x @ y) # y = (y @ x) # x
  .
• xy = y @ (y @ x) = x @ (x @ y)
• xy' = x @ y
• yx' = y @ x
• x'y' = (y # x) @ y = (x # y) @ x
  .
• [y @ (y @ x)]' = [(y # x) @ y]
• [x # y]' = y @ x
• x # y = y' # ( y' # x)
• x @ y = y' @ (y' @ x)

You are asked to do the following

1. Develop implication and inhibition gates out of your Lab Kit components, as just shown.
2. Use the inhibition and implication gates only, to implement the given sum-of-minterms form
3. For full credit implement this in the given form

F = [? @ { (? @ ?)  #  (? # ?) }] # [? # { (? @ ?) # (? # ?) }]
(If you can do this, you can skip part 2.)
4. Implement the circuit on a breadboard
5. Measure the propagation delays

Signature: _________________________________

You are also required to check whether the operators of inhibition and implication are 'commutative' and 'associative'. Starting from the previously  constructed implementation, implement the following functions and fill in the truth tables.

1. Apply all possible commutativity at the primary inputs
2. Convert the implementation into this form:

F = [? @ { ( (? @ ?)  #  ?) # ? }] # [? # { ( (? @ ?) #? ) # ? }]

In part 1, do Bullets (1-3) and turn in a  printout of your design. In part2, do Bullets (1-5). Get your TA's signature and turn-in a report outlining the simplification you have implemented and your results regarding commutativity and associativity of the underlying gates as in the last outlined part.