Method and Apparatus for Division Error Detection

This invention relates to computer systems and the detection of errors which occur in the performance of arithmetic operations, especially for detecting division errors.

One of the functions of most computers systems is to perform arithmetic operations. Occasionally, an error occurs during an arithmetic operation, often due to malfunction of hardware within the computer system. It is beneficial to detect such an error immediately when it occurs. Traditionally, the detection of such arithmetic errors is performed by providing a duplicate piece of hardware to perform a computation which verifies the main calculation. This can be expensive and potentially very slow.

For instance, in order to detect an addition error the obvious implementation shown in FIG. 1 is to provide an extra full adder 100 to produce the same sum as the original calculation. One would then use an exclusive "NOR" 110 for the width of the result in order to produce a value which indicates whether all of the bits in the first result and the second result were identical. Next, all the bits of the resulting indicator are "AND"ed 120 to generate a single bit result which indicates the success of the operation.

The prime objections to this method are the expense of the full adder 100 and the high propagation delay in performing the full add. Typically, a full adder propagates several outputs including a generate, a propagate, and a compliment of the given result. Once this addition is done there is still the need and expense of performing the exclusive "NOR" and the final "AND" on that result in order to get the single bit answer desired.

It is an object of the present invention to provide a fast and novel method of error detection for arithmetic operations. More particularly, it is an object of this invention to provide such an apparatus and method for detecting errors in a division operation.

It is another object of the present invention to provide a method of error detection which does not require the hardware expense of providing a full adder in the computer system.

This invention is directed to providing a time and cost efficient method of performing error detection on the result of an arithmetic operation; especially a division operation. It does so through the use of a Carry-Save Adder (CSA). A CSA is known in the art to be faster and less costly than the use of a full adder. A preferred embodiment of the present invention employs a CSA which accepts three inputs to produce the partial sum and carry bits of the three inputs. For purposes of this invention the inputs consist of the two integers which form the sum of the result being checked and the ones compliment of the result being checked.

The method takes advantage of the relationship between the operands of an arithmetic operation and the ones complement of the operation's result. Given two operands, P and Q, which when added yield a result R and given another input N, which is the ones compliment of R, then the sum of P plus Q plus N equals 2 to the power of L minus 1, where L is the width of the result being checked. This relation is easily proven:

Note that the value on right side of the equal sign equates to all ones for the bits of a number represented in binary. Using this relationship P, Q and N are input to the CSA for the addition case to produce a result which is expected to yield all ones along the combination of the sum and carry bit output. Other combinations of inputs are employed to verify other arithmetic operations.

FIG. 1 depicts a mechanism employed in the prior art to perform arithmetic error checking.

FIG. 2 depicts a preferred embodiment of the CSA mechanism of the present invention.

FIG. 3 shows the logic diagram of the individual inputs and outputs of the CSA employed in a preferred embodiment of the present invention.

FIG. 4 shows the logic diagram of the output of a CSA employed in a preferred embodiment of the present invention shown in FIG. 3.

FIG. 5 is a flow chart which depicts the method employed in a preferred embodiment of the present invention.

FIG. 6 shows the logic diagram of the individual inputs and outputs of the optimized CSA/XOR mechanism employed in a preferred embodiment of the present invention.

FIG. 7 shows the logic diagram of the output of a combined CSA/XOR mechanism employed in a preferred embodiment of the present invention.

FIG. 8 shows the logic diagram of the individual inputs and outputs of a combined CSA/XOR mechanism employed in a preferred embodiment of the present invention.

As described above, the subject invention puts a multiple input Carry Save Adder (CSA) to advantageous use to perform error checking on an arithmetic result by employing the following relationship. The method relies upon (P+Q)=R and (P+Q+N)=(2**L)-1, where N is the one's complement of R and L is the width of R. The sum (P+Q+N) should yield a result of all ones among the bits of the sum and carry bits of a CSA.

In a preferred embodiment shown in FIG. 2 which uses a three input CSA 200 to produce a partial sum, S, and a carry, C, of inputs P, Q and N, an exclusive "OR" 210 of S and C must be all true if R is correct. This method verifies the arithmetic operation in a less expensive and more rapid manner than the use of a full adder as employed in the previous art.

Given that each element of the CSA may be indexed with an index I, the CSA in the preferred embodiment has inputs P[I], Q[I] and N[I] and outputs C[I] and S[I]. In such an environment the sum (S+(C * 2))=(P+Q+N). The following table shows more clearly how the elements of the Carry Save Adder are related:

As the sum is generated from right to left each bit of the sum equals S[I] XOR C[I-1], provided there is not a carry generated to its right. Thus, if there are no carries the relation is true if all the exclusive "OR"s of S[I] and C[I-1] are true. Also, the right most column which generates a carry must produce a zero sum because there are only 2 inputs. The exclusive "OR" of that column also produce a one result.

If S is all ones and a carry exists, the relation is false because the exclusive "OR"s are not all ones thus indicating an error in result R. In this way it can be seen that the exclusive "OR" function of S and C is sufficient to produce the equal relation of (P+Q)=R.

The first step for checking such an addition in this three input embodiment shown in FIG. 2 is to use the CSA 200 to produce the partial results S and C for inputs P, Q and N. Next use L exclusive "OR" gates 210 to produce X where X[I]=(S[I] XOR C[I-1]). Next perform a logical "AND" 220 on all the bits of X to generate the result. A one result indicates no error has occurred.

FIG. 3 shows how the CSA results are generated at a bit level. Inputs P[I], Q[I], and N[I] are input to an XOR gate 300 to yield bit S[I]. Each of the three possible unique two input combinations of inputs P[I], Q[I], and N[I] are input to an AND gate 310, 320, 330. The output of each AND gate is input to an OR gate 340 to yield bit C[I]. Bits S[I] and C[I-1] are then input to a XOR gate 350 to yield bit X[I].

FIG. 4 shows how the individual bit level outputs of each CSA 400 are fed to a XOR gate 350 to yield each bit of X. The individual bits of X are then input to an AND gate 410 to yield the final result.

The method of an embodiment of the present invention is shown by the flow chart of FIG. 5. First perform the arithmetic operation 500 to determine the result, R. Also determine the inputs, P, Q, and potentially Y which are appropriate to check result R. For instance, for the addition case P and Q would be the two operands of the addition. For division, P and Q would be determined by shifting the operands with zero fill and adding in Y as the remainder as described hereinafter.

Set L equal to the number of valid bits in either input P or Q 510, whichever value is larger. Set I equal to 0 at step 520. Next determine the one's compliment, N, of result R 524 filling any used bits with a value of one.

Set S[I] at step 530 to P[I] XOR Q[I] XOR N[I]. Determine C[I] at step 540 using (Q[I] AND P[I]) OR (Q[I] AND N[I]) OR (P[I] AND N[I]). Increment I 550 then compare I to L, the number of valid bits in the inputs which need to be processed 560. If I is less than L, return to step 530 and continue.

If I is not less than L, reset I to zero at step 570. Set X[I]=S[0] XOR 0 at 580 since C[-1] may not be valid reference. Increment I at 590. Set X[I]=S[I] XOR C[I-1] 600. Compare I to L 610 and if I is less than L return to step 590. If not, determine if all the bits of X equal 1 at step 630. If not, handle the error 640. If X=1 the operation was successful.

While the above embodiment employed a three input CSA using P, Q, and N, it will be obvious to those skilled in the art that an additional input to the CSA could be used advantageously to check multiple operand results.

Another implementation of the above of error checking mechanism would be to employ it to check the multiplication of operands. This embodiment employs the 3 input CSA described above. It checks the operation where (P * Q) yields R and where N is the ones compliment of R.

First, P is input into two of the inputs of the CSA and N is entered into the third input. The value of P in each of the inputs is shifted to achieve a value equivalent to multiplying P by the value of Q. For example, if Q equals 5 then one P input is shifted two bits to the left effecting a multiplication by 4. The other P input is unshifted effecting a multiplication by 1. The sum of the two P inputs should equal the result R which was P times Q. The table below should help make this example more clear:

Note that the undefined values for the two inputs are zero filled. Note also that the undefined values for the N input are one filled. This is merely consistent with the respective definition of these values.

Employing the previously described embodiment, the CSA produces the partial results S[I] and C[I] of the three inputs. Next, the exclusive "OR" of S[I] and C[I-1] yields X[I]. Finally, the bits of X are logically "AND"ed to generate a result. A zero result indicates an error.

Another useful implementation of the above method of error checking is for a division operation. Given a dividend, Q, divided by a divisor, P, a result, R, is generated. However, there may be situations where P does not divide evenly into Q and a remainder, Y, will also result. One means of employing the above described error checking method requires at least 4 inputs on the CSA. Result, R, would be put into 2 of the inputs and shifted appropriately as in the multiplication case described above. A third input would be used to input the remainder, Y, and finally the 4th input would have N as its input. In such a situation, all of the above described operations for producing S and C and operating on that result are the same.

This invention may still be employed to check a division operation when a CSA with only 3 inputs is available. In one implementation the result, R, is entered into 2 of the inputs. One of the R inputs is shifted sufficiently to the left to permit the remainder, Y, to be entered into the right most bits of that input. For example, the maximum remainder for a division by 3 is 2 which requires 2 bits for its binary representation. In this situation, one R input is shifted left 2 bits permitting the entry of the Y result in the right most 2 bits of that input. Note that this produces (R*4)+Y. Since the goal in this example is for the two R inputs to yield (3*R)+Y, the second R input is negated. This yields (R*4)+Y+(-R)=(R*3)+Y as desired. The following table may be helpful in understanding this example:

The ones compliment, N, of the divident, Q, is entered in the third input. The three inputs are added to yield S and C. Note that this is a true add where the negative value of the second input causes a subtraction. The results of S and C are handled from this point on as described previously. A zero result on the final "AND" of X indicates an error.

There is another embodiment which is employed in a preferred embodiment of the present invention to perform division error checking. Enter the result, R, into each of the first 2 inputs. Shift one input left sufficiently to shift in not less than the maximum possible remainder value minus 1. Shift the other inputs as described above to yield within one of the proper final result. For instance, in table 4 shown below an example for a divide by 3 is shown.

The remainder, Y, is input by extending inputs 1 and 2 by Y and input N by 1's. The following truth table shows the amount added to column 0, which is the column where N[0] is located, for this example.

The operations on the three inputs are the same as described in the first embodiment above to yield S and C which are then used to yield X.

Given all the above situations in which a CSA is employed to check the result of an arithmetic operation there is yet another improvement that may be employed to check the result. Specifically, this improvement is to combine the CSA function and the exclusive "OR" function into a single function, F, through the use of standard minimization techniques. The exact equations will depend on which of the given above described embodiments is employed.

FIG. 6 is a logic diagram of how this is accomplished at the bit level for the set of inputs used in the embodiment of FIG. 3. As in FIG. 3, the three possible unique two input combinations of inputs P[I-1], Q[I-1], and N[I-1 are input to an AND gate 410, 420, 430. The output of each AND gate is input to an OR gate 440 to yield bit C[I-1]. The improvement is to avoid the step of creating S[I] explicitly by employing a 4 input XOR gate 450. Inputs P[I], Q[I], and N[I] are fed directly to XOR gate 450 with C[I-1] as the fourth input to yield X[I]. This eliminates XOR gate 300 and the XOR gate 350 shown in FIG. 3.

FIG. 7 depicts how the individual bit level outputs of the combined CSA/XOR mechanism 500 yield each bit of X. As in FIG. 4 the individual bits of X are then input to an AND gate 410 to yield the final result.

Standard minimization techniques may yield further improvements depending on the operation being checked. For the embodiment where division by three is checked and the input is shifted sufficient to shift in not less than the maximum possible remainder minus 1 the following set of equations are true.

Substituting for S and C yields:

Following the standard minimization yields:

Where RN=not R and N=not Q.

Referring to Table 4 for the above if i=1 then R[i-2]=Y[1] E1 ? ##STR1##

Using this method X is computed by performing on a computer the series of logical operation steps described by equation 1 above. FIG. 8 depicts the logic diagram at the bit level for this optimized version of the CSA/XOR functions.

On a typical processor this has about the same execution time as the steps for the CSA function described above without requiring the hardware expense of a CSA. Note also that the step of the final XOR on S[i] and C[i-1] to produce X has been eliminated thus yielding X in an even more efficient manner. Similar minimization techniques may be applied to other such embodiments.

While the above set of embodiments have focused upon the use of a three input Carry Save Adder to accomplish error checking, it will be obvious to one skilled in the art that the availability of additional inputs would broaden the applicability of such error checking to permit a more diverse set of checking to occur. Specifically, the availability of additional inputs would broaden the number of cases where this method could be used to check the results of a given divisor which may not be possible in the three input CSA case.

A system and method has also been revealed to utilize minimization of the logical operations involved to determine the series of logical operations which may be employed to accomplish such error checking without the use of a CSA. Those skilled in the art will recognize that this may yield a system which is more efficient than employing a hardware CSA.