The present invention relates to parity prediction circuits and particularly to parity prediction circuits for use in adders, counters and other similar data processing circuits. Parity predition and parity generation have long been employed in data processing circuits for the detection of errors.
Parity generation is a term which describes the generation of a parity bit, p.sub.a, from a binary number having the n+1 bits a.sub.0, a.sub.1, . . . , a.sub.n. Where ".sym." is an EXCLUSIVE-OR symbol and ".sym." is an EXCLUSIVE-NOR symbol, the generated parity bit, p.sub.a, is defined as follows: EQU p.sub.a =a.sub.0 .sym.a.sub.1 . . . .sym.a.sub.n-1 .sym.a.sub.n
A binary adder functions to add a first binary number a.sub.0, a.sub.1, . . . , a.sub.n and a second binary number b.sub.0, b.sub.1, . . . , b.sub.n to form the sum s.sub.0, s.sub.1, . . . , s.sub.n. Parity generation from the sum forms the parity bit, p.sub.s, given as follows: EQU p.sub.s =s.sub.0 .sym.s.sub.1 . . . .sym.s.sub.n-1 .sym.s.sub.n
It is well-known that the parity bit, p.sub.s, generated from the sum, that is, generated from the adder output only, does not indicate whether or not the summation was performed correctly by the adder.
Parity prediction is a term which describes the technique of forming a parity bit, p.sub.p, based upon the inputs to an adder or other device rather than based solely upon the output of the device. If the predicted parity bit, p.sub.p, is independently derived from the inputs, the predicted parity bit, p.sub.p, can be compared with the generated parity bit, p.sub.s, for error-detecting purposes. For example, in a binary adder, the comparison of the predicted parity bit, p.sub.p, with the generated parity bit, p.sub.s, can be used to detect errors in the addition performed by the adder. If the predicted and generated parity bits are the same, no error is detected. If the predicted and generated parity bits differ, then an error is detected.
For the purpose of error detecting, the parity prediction bit should be as independent as possible from any parity generation bit generated directly from the device output without, however, introducing too much circuit complexity. To the extent that the parity prediction bit is not independent from the parity generation bit, the predicted parity and the generated parity may both be wrong so that no error detection can occur.
Predicted parity is useful also as a replacement for generated parity particularly when the predicted parity is simpler, faster operating, or otherwise superior.
While a number of parity prediction circuits and techniques have been known, there is a need for improved parity prediction circuits. Particularly, there is a need for parity prediction circuits which are suitable for use in connection with large scale integration such as metal oxide silicon (MOS) technology.
In accordance with the above background, it is an object of the present invention to provide an improved parity prediction circuit for adders and counters.
USPTO Backgrounds
USPTO Backgrounds