Name1:___________________________     Name2:___________________________  

Name3:___________________________

Lab Assignment #3, Due February 12, 1999

         Due 5:00PM, to be placed under the door of AP&M'4840  

Introduction: This lab consist of two parts: (i) Implementation of an error correction circuit for a specific code on LogicWorks, (ii) Measurement of delay of an inverter gate, and delay of a multi-level implementation of a logic function with implication and inhibition gates.

Part 1: Error Correction Code

It is reputed that the ancient Thracian civilization used a base-7 number system and that they furthermore had developed a computer that represented base-7 numbers! In order to represent a base-7 number they had developed a (rather inefficient; it used 8 bits instead of the minimum 3!) code as follows:
 

In order to understand this exercise, think about the following points. How many 1s and 0s does each 8-bit code have?  Consider also the following rule: if there are two ones in a row, add the index of the left one (do this for each pair of 1's), and if there are two zeroes in a row, subtract the index of the left zero (do this again for every pair of 0's). Assume the index of the rightmost bit to be 1, and the index of the leftmost bit to be 8. What is the total result? In generating the result you need to use a left "virtual" bit of 1 and a right "virtual" bit of 0; the actual word to be considered looks like 1xxxxxxxx0, where xxxxxxxx is the code word and the "virtual" bits from left and right help you form the pairs for the first and the last bits. Now that you know these two properties of the code, how many bits need to be simultaneously flipped in order to produce another legal word? The following table reviews the aforementioned rules.

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 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.
You have to determine which bit from the result is to be used as an enable signal of this decoder and which 3 bits as S(2..0). Also be careful with the correspondence between Q(7..0) and the bits in your final result, i.e. the position of the "Corrected bit" from the above schematic in the result word.

In order to sum and subtract the appropriate indices, you can use the multiplier circuit that you have constructed in your previous lab. In that circuit, the multiplier was placed in the Multiplier register and a right-to-left scan of the multiplier bits provided us the signal for adding or subtracting 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/subtracting the multiplicand, you need to add or subtract the index of the left bit (of a pair of two ones or zeroes, respectively) in the Multiplier register. You can achieve this by incrementing the Multiplicand register (starting from 1), which should correspond to the index position of the bit being scanned in the M register. Be careful with the shift in (SI) signal of the Multiplier - you need to connect it to +5V in order to follow the convention of left "virtual" bit equal to 1.

The algorithm is given as follows:

• Accumulator = 0, Counter = 1, Multiplier = Code
• Repeat 9 times
• • If the least significant bit of Multiplier is 1 and Q=1, then Accumulator = Accumulator + Counter
  • If the least significant bit of Multiplier is 0 and Q=0, then Accumulator = Accumulator - Counter
  • Shift Multiplier to the right (the least significant bit of the multiplier goes to Q), Counter = Counter + 1
• End

You need to get the new control for this circuit. It will have the same interface as the control for Booth's multiplication. All you have to do is to modify the datapath of your circuit such that it will implement the above algorithm. For this part, we will add a "counter" and new control (Control_C) to the CSE140L library. The counter will have a low active load input, which will set the counter output to 1, and a high active increment input which will increment the counter every clock cycle.

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:
4. • 10110011
   • 11001101
   • 00110100
   • 00010101
   • 01100011

Part 2: Logic Functions

The object of this part of the exercise is twofold. You are asked to develop experience with measuring delays through a logic circuit and also to get some understanding for the possible implementation of a circuit . We will use the circuit that you develop for the latter as a measurement tool for the former objective also.

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

Further information about propagation delays can be found in  Gajski, Principles of Digital Design, Ch-3. Since the delay of an inverter gate is usually less then 10ns, we cannot directly measure the delay of an inverter gate. Therefore, we will build a circuit called a ring oscillator (odd number of inverters connected like a ring) and measure the period of oscillation in order to determine the average propagation delay of an inverter gate.
   

The figure shows a ring oscillator. In order for  the ring oscillator to oscillate you must have an odd number of inverters connected in a ring fashion. You can choose the output of any inverter to observe the waveform and measure the period of oscillations.  Use at least three inverters. If you choose to use three inverters, the period of oscillations will be 6 times the propagation delay of an individual inverter gate. When you measure the propagation delay of an inverter gate, get the TA's signature and let them verify your measurement. You will need to use this setup to measure the delay of the logic function implementation.
 t_{plh =}               t_phl  =               t_p =

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

As an example: Suppose the logic function is F = ABC. For the input combination B = 1, C = 1, inversion of the input A will invert the output. Therefore, connect a square wave to the input A, and observe both waveforms simultaneously. The waveforms should look like the waveform given in the following figure.

   
Then measure the propagation delay of the circuit for the particular input you choose. Measure both L to H and H to L delays and find the average 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:  
where the resistor is 330 ohms and the capacitor is 0.01 microF.
 

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 the full adder summation function:

• Sum = xyz + xy'z' + x'y'z + x'yz'

The implementation should have the following form:

•  Sum = [? @ { (? @ ?)  #  (? # ?) }] # [? # { (? @ ?) # (? # ?) }]

Where '?' represents any of the literals x,y, and z, but not their complements.

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)

Implementation of implication and inhibition gates:

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
4. 
   Sum = [? @ { (? @ ?)  #  (? # ?) }] # [? # { (? @ ?) # (? # ?) }]
   (If you can do this, you can skip part 2.)
5. Implement the circuit on a breadboard
6. Measure the propagation delays

Implement the circuit and fill in the following truth table. Use the switches on the breadboard as the inputs so that they can be changed easily. Choose one of the input combinations satisfying the condition given in "How to measure delay of a logic function" and measure the propagation delays.  

t_{plh =}               t_phl  =               t_p =

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:
3. 
   Sum = [? @ { ( (? @ ?)  #  ?) # ? }] # [? # { ( (? @ ?) #? ) # ? }]

 Requirements:

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.