Parity prediction circuit for adder/counter

A parity prediction circuit for predicting parity in an adder, counter or similar device. The parity prediction is obtained with a parity prediction network connected from most significant bit to least significant bit. The parity prediction network is used in place of a parity generator or in combination with a parity generator for error checking purposes. In a special application, the parity prediction is employed for a ripple-carry type counter where the predicted parity bit is produced by a single network of NAND gates connected in series from high-order to low-order counter bits. The predicted parity is available no later than the completion of the carry-out propagation.

BACKGROUND OF THE INVENTION 
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. 
SUMMARY OF THE INVENTION 
The present invention is a parity prediction circuit in conjunction with 
adders, counters and other similar devices for predicting the parity of 
the outputs from the devices. The parity prediction circuit includes a 
network for transmitting one or more parity prediction transmission bits 
from the most significant (high-order) bit to the least significant 
(low-order) bit of the adder or other device. The transmitted parity 
prediction information is logically combined with the carry-in and the 
parity bits of each of the input numbers to the adder or other device to 
form the predicted parity of the device output. 
In a particular example, for a binary adder of n+1 bits, the parity 
prediction network includes n stages where the i.sup.th stage transmits 
the parity prediction information as the two bits x.sub.i and y.sub.i. The 
x.sub.i and y.sub.i parity prediction bits are transmitted to the 
i+1.sup.th stage. 
The transmitted parity prediction bits x.sub.i and y.sub.i are defined in 
terms of the transmitted information from the next high-order previous 
i-1.sup.th stage and the bit propagate, P.sub.i, and bit generate, 
G.sub.i, where P.sub.i and G.sub.i are formed from the i.sup.th bits of 
the binary input numbers a.sub.0, a.sub.1, . . . , a.sub.i, . . . , 
a.sub.n, and b.sub.0, b.sub.1, . . . , b.sub.i, . . . , b.sub.n. The 
x.sub.i and y.sub.i bits are given as follows: 
x.sub.i =[P.sub.i ][x.sub.i-1 ] 
y.sub.i =[y.sub.i-1 ].sym.[(G.sub.i)(x.sub.i-1)] 
where: 
x.sub.i-1 =first transmitted bit from i-1.sup.th stage 
y.sub.i-1 =second transmitted bit from i-1.sup.th stage 
P.sub.i =a.sub.i .sym.b.sub.i =EXCLUSIVE-OR of a.sub.i and b.sub.i 
G.sub.i =(a.sub.i)(b.sub.i)=AND of a.sub.i and b.sub.i 
.sym.=EXCLUSIVE-OR symbol 
.sym.=EXCLUSIVE-NOR symbol 
In a particular embodiment of the adder in which the binary input number 
a.sub.0, a.sub.1, . . . , a.sub.n is 0 for all (n+1) bits, the two number 
binary adder reduces to a binary counter. In such a binary counter where 
all values of a.sub.i (for "i" equal to 0, 1, . . . , n) equal to 0, the 
G.sub.i term also becomes equal to 0 and the P.sub.i term reduces to 
b.sub.i. With these simplifications, each stage of the parity prediction 
network becomes a simple NAND gate or other simple logical structure. Such 
a network of NAND gates is substantially more simple than the network of 
EXCLUSIVE-OR and EXCLUSIVE-NOR gates which can be employed to generate 
parity in a conventional manner. Also, the parity prediction from the NAND 
gate network of the present invention is available not later than a 
carry-out from the high-order stage of the counter. 
In another embodiment of the invention, EXCLUSIVE-NOR gates used in forming 
the parity prediction stages for a full binary adder are bundled in pairs. 
With this bundling, the gate delay of the parity prediction network is 
substantially reduced. 
In accordance with the above summary, the present invention achieves the 
objective of providing improved parity prediction circuits in conjunction 
with binary adders, counters and similar devices. 
Additional objects and features of the present invention will appear from 
the following description in which the preferred embodiments of the 
invention have been set forth in detail in conjunction with the drawings.

DETAILED DESCRIPTION 
In FIG. 1, a full adder 10 is shown schematically. The full adder 10 adds a 
first binary number a.sub.0, a.sub.1, . . . , a.sub.i, . . . , a.sub.n and 
a second binary number b.sub.0, b.sub.1, . . . , b.sub.i, . . . , b.sub.n 
to form the full sum s.sub.0, s.sub.1, . . . , s.sub.i, . . . , s.sub.n. 
The full adder 10 includes the stages FA.sub.0, FA.sub.1, FA.sub.2, . . . 
, FA.sub.i, . . . , FA.sub.n. 
In FIG. 1, each of the stages FA.sub.1 (for "i" equal to 0, 1, . . . , n) 
receives a carry-in C.sub.i and produces a carry-out C.sub.i-1. The 
carry-in, C.sub.n, for the stage FA.sub.n is a carry-in signal, C.sub.IN. 
The carry-out from the high-order stage FA.sub.0 is the carry-out signal 
C.sub.OUT. 
In FIG. 1, the parity of the binary number a.sub.0, a.sub.1, . . . , 
a.sub.n is given by the parity bit p.sub.a. Similarly, the parity of the 
binary number b.sub.0, b.sub.1, . . . , b.sub.n is given by the parity bit 
p.sub.b. The parity bits p.sub.a and p.sub.b can be formed in any manner. 
For example, conventional ripple-type parity generation employs a string 
of EXCLUSIVE-OR gates similar to or like that shown for network 14 in 
connection with the sum output from the adder. Also, conventional 
tree-type parity generation circuits are well-known and may be employed. 
In a conventional manner, the parity generation network 14 includes the 
EXCLUSIVE-NOR gate 14.sub.0 and the EXCLUSIVE-OR gates 14.sub.1, 14.sub.2, 
. . . , 14.sub.i, . . . , 14.sub.n. The gate 14.sub.n is trivial in that 
it receives the s.sub.n input and a constant logical "0" input. Because 
the parity bit, p.sub.s, generated by network 14 is derived directly from 
the sum output s.sub.0, s.sub.1, . . . , s.sub.n, the generated parity bit 
p.sub.s cannot detect any error in the addition by the full adder 10. 
In accordance with the present invention in FIG. 1, a parity prediction 
network 12 is provided. The parity prediction network 12 includes the 
parity prediction stages PP.sub.0, PP.sub.1, PP.sub.2, . . . , PP.sub.i, . 
. . , PP.sub.n and the parity prediction PP.sub.OUT output stage 13. The 
stage PP.sub.i is typical of each of the stages for i equal to 1, 2, . . . 
, n. In the embodiment shown, the stage PP.sub.0 is trivial and only 
generates constant logical 1's. If the value of the carry-out C.sub.OUT is 
to be considered together with the sum in forming the predicted parity, 
then the stage PP.sub.0 is not trivial and is like each of the other 
stages PP.sub.i. In such case, the PP.sub.0 stage has inputs, x.sub.-1 and 
y.sub.-1, both equal to a constant 1 and has outputs, x.sub.0 and y.sub.0, 
determined in the same manner as the other x.sub.i and y.sub.i outputs for 
values of "i" greater than 0. 
The PP.sub.i parity prediction stage receives the two transmitted parity 
information bits x.sub.i-1 and y.sub.i-1 as inputs from the previous 
i-1.sup.th stage and receives the bit propagate P.sub.i and the bit 
generate G.sub.i bits as inputs from the full adder FA.sub.i stage. In 
response to these inputs the PP.sub.i parity prediction stage transmits 
the two parity prediction information bits x.sub.i and y.sub.i to the next 
i+1.sup.th stage. In the case of the PP.sub.1 stage, x.sub.0 and y.sub.0 
are each logical 1's. In the case of the low-order PP.sub.n stage, the 
x.sub.n and y.sub.n low-order transmission bits connect as inputs to the 
PP.sub.OUT circuit 13. 
In FIG. 1, the parity prediction PP.sub.OUT circuit, in addition to the 
transmission bits x.sub.n and y.sub.n, receives the C.sub.IN, the p.sub.a 
and p.sub.b bits as inputs. The PP.sub.OUT output stage 13 logically 
combines those inputs to generate the predicted parity bit p.sub.p. 
It is apparent from the FIG. 1 circuit that the parity prediction network 
14 forms the predicted parity bit independently of the parity generation 
bit p.sub.s. Accordingly, a conventional comparator 16 for comparing the 
p.sub.s and p.sub.p bits produces an error-detection signal (ERROR DET) 
whenever those bits are different. 
It should also be noted that in FIG. 1, the parity prediction network 12 
transmits the two parity prediction bits from stage to stage from the 
high-order PP.sub.1 stage to the low-order PP.sub.n stage, that is, for 
all stages of PP.sub.i for values of "i" from 1 to "n". 
In FIG. 1, the bit propagate signals, such as P.sub.i for the i.sup.th 
stage, and the bit generate signals, such as G.sub.i for the i.sup.th 
stage, are generated in a conventional manner from the corresponding 
i.sup.th stage FA.sub.i of the full adder. More specifically, the P.sub.i 
and G.sub.i signals are given as follows: 
EQU P.sub.i =a.sub.i .sym.b.sub.i 
EQU G.sub.i =(a.sub.i)(b.sub.i) 
EQU i=1, 2, . . . , n 
In FIG. 2, further details of the PP.sub.i stage of the parity prediction 
network 12 is shown as typical of the "n" stages PP.sub.1, PP.sub.2, . . . 
, PP.sub.n. The stage PP.sub.i includes the NAND gate 20 which logically 
combines the x.sub.i-1 and the P.sub.i signals to provide the x.sub.i 
signal. The stage PP.sub.i includes the NAND gate 21 which logically 
combines the x.sub.i-1 and the G.sub.i signals to provide an input to the 
EXCLUSIVE-NOR gate 22. Gate 22 receives as its other input the y.sub.i-1 
signal. Gate 22 produces the y.sub.i signal as an output. Accordingly, the 
PP.sub.i stage of FIG. 2 generates the parity prediction transmission bits 
x.sub.i and y.sub.i for all values of "i" from 1 to "n" as follows: 
EQU x.sub.i =[P.sub.i ][x.sub.i-1 ] 
EQU y.sub.i =[y.sub.i-1 ].sym.[(G.sub.i) (x.sub.i-1)] 
where: 
EQU x.sub.0 =1 
EQU y.sub.0 =1 
In FIG. 3, further details of the PP.sub.OUT stage 13 of the parity 
prediction network 12 of FIG. 1 are shown. The PP.sub.OUT stage includes 
the NAND gate 23 which logically combines the C.sub.IN bit and the x.sub.n 
bit to form an input to the EXCLUSIVE-NOR gate 24. The other input to the 
gate 24 is the y.sub.n bit. The output from the gate 24 is an input to the 
EXCLUSIVE-NOR gate 26. The other input to the gate 26 is from the 
EXCLUSIVE-NOR gate 25. Gate 25 produces its output as a logical 
combination of the parity input bits p.sub.a and p.sub.b. The output from 
the EXCLUSIVE-NOR gate 26 is the predicted parity bit p.sub.p. Any two of 
the gates 24, 25 or 26 may be changed to EXCLUSIVE-OR gates without 
changing the intended logical function. 
In connection with the generation of the predicted parity bit p.sub.p, it 
should be noted that the prediction network 12 does not utilize any of the 
carry signals C.sub.i internal to the full adder 10. For this reason, the 
predicted parity p.sub.p output is available at least as soon as the 
carryout, C.sub.OUT from the high-order stage FA.sub.0. The high-speed 
nature of the parity prediction network 12 coupled with its independence 
from the generated parity p.sub.s, renders the predicted parity p.sub.p 
ideal for comparison with generated parity p.sub.s for detecting errors in 
the addition performed by the full adder 10. 
In FIG. 4, a 4-bit counter with a parity prediction circuit is provided as 
a special case of the FIG. 1 circuit where "n" is equal to 3. In FIG. 4, 
the counter stages CS.sub.0, CS.sub.1, CS.sub.2 and CS.sub.3 correspond to 
the full adder stages FA.sub.0, FA.sub.1, . . . , FA.sub.n in FIG. 1 where 
"n" is equal to 3. In the FIG. 1 circuitry, it is assumed that all values 
of a.sub.i for "i" equal to 0, 1, . . . , n are equal to 0. With this 
assumption, the full adder stages of FIG. 1 can be reduced to counter 
stages of the type shown in FIG. 4. 
In FIG. 1 with all the values of a.sub.i equal to 0, the bit propagate 
P.sub.i and bit generate G.sub.i values also are reduced. The values of 
G.sub.i for all values of "i" equal to 0, 1, 2, . . . , n are 0. All 
values of P.sub.i or "i" equal to 0, 1, 2, . . . , n become equal 
respectively to b.sub.i. 
Under these conditions, each parity prediction stage 12.sub.i of the FIG. 2 
type is reduced to the NAND gate 20. The parity prediction network 
therefore becomes a string of 2-input NAND gates 20'.sub.0, 20'.sub.1, 
20'.sub.2 and 20'.sub.3 as shown in FIG. 4. The NAND gate 20'.sub.0 is 
employed (with the x.sub.-1 input equal to 1) only when the counter 
carry-out C.sub.OUT is to be considered in forming the predicted parity. 
When the predicted parity does not consider C.sub.OUT (that it, predicts 
parity for only b'.sub.0, b'.sub.1, b'.sub.2 and b'.sub.3) then gate 
20'.sub.0 can be eliminated. Alternatively, if gate 20'.sub.0 is retained, 
its input x.sub.-1 is equal to 0 so that x.sub.0 is always equal to 1. The 
x.sub.-1 input, therefore, is a control for selecting or excluding the 
carry-out C.sub.OUT from the parity prediction. 
In FIG. 4, the PP.sub.OUT circuit 13' includes an AND-OR-INVERT gate 17 
forming the predicted parity p.sub.p. The gate 17 receives the low-order 
transmission bit x.sub.3 (x.sub.n with "n" equal to 3) from the low-order 
stage consisting of NAND gate 20'.sub.3. The x.sub.3 bit connects to gate 
17 directly on one side and through INVERTER gate 18 on the other side. 
Similarly, the parity p.sub.b connects directly on one side to gate 17 and 
through inverter 19 on the other side. The circuit 13' effectively forms 
the EXCLUSIVE-OR of the x.sub.3 and p.sub.b signals. With this embodiment, 
p.sub.p is always the predicted parity for the binary number b.sub.0, 
b.sub.1, b.sub.2 and b.sub.3 as stepped by a +1 increment by the stepping 
signal C.sub.IN. In the case where C.sub.IN is a selectable 1 or 0, the 
p.sub.p value is valid after the C.sub.IN signal steps b.sub.0, b.sub.1, 
b.sub.2 and b.sub.3 by +1 to form the new binary number b'.sub.0, 
b'.sub.1, b'.sub.2 and b'.sub.3. Note that circuit 13' does not require 
any connection to the C.sub.IN stepping input. In the case where C.sub.IN 
is always a constant 1, then the counter output is always the new binary 
number having the predicted parity p.sub.p. 
In FIG. 4, the circuit 13" is an alternate embodiment for circuit 13'. 
Circuit 13" receives the C.sub.IN stepping signal and logically combines 
it with the low-order transmission bit x.sub.3 and the parity p.sub.b to 
form the predicted parity p.sub.p. For circuit 13", p.sub.p is always 
valid for b'.sub.0, b'.sub.1, b'.sub.2 and b'.sub.3. 
In FIG. 4, the parity prediction network 12' is even more simple than the 
parity generation network 14'. The simplicity of the parity prediction 
network comprising NAND gates is more simple than the parity generation 
network comprising a string of EXCLUSIVE-OR and EXCLUSIVE-NOR gates since 
NAND gates are simpler to construct in integrated semiconductor technology 
than EXCLUSIVE-OR and EXCLUSIVE-NOR gates. Normally, the delay time of a 
2-input EXCLUSIVE-NOR gate is twice the delay time of a 2-input NAND gate. 
Accordingly, the formation of the predicted parity bit p.sub.p is 
substantially faster for the counter of FIG. 4 then the generation of the 
generated parity bit p.sub.b'. 
In FIG. 5, an alternate prediction network 12" for use in connection with a 
16-bit example of the full adder of FIG. 1 is shown. In FIG. 5, the bit 
propagate signals P.sub.i and the bit generate signals G.sub.i for "i" 
equal to 1, 2, . . . , 15 are the same as defined in connection with FIG. 
1. Similarly, the NAND gates 20.sub.1, 20.sub.2, . . . , 20.sub.15 are 
analogous to the NAND gate 20 in FIG. 2. In FIG. 5, the NAND gates 
21.sub.1, 21.sub.2, . . . , 21.sub.15 are analogous to the NAND gate 21 of 
FIG. 2. The gates 21.sub.1, 21.sub.2, . . . , 21.sub.15 form the parity 
prediction transmission bits x.sub.1, x.sub.2, . . . , x.sub.15, 
respectively. In FIG. 5, no direct analogy is present for the 
EXCLUSIVE-NOR gate 22 of FIG. 2. Rather, pairs of NAND gates 21 provide 
inputs to the bundled EXCLUSIVE-NOR gates 30. For example, the outputs 
from NAND gates 21.sub.2 and 21.sub.3 connect as inputs to the 
EXCLUSIVE-NOR gate 30.sub.2,3. The output from the gate 30.sub.2,3 
provides an input to the EXCLUSIVE-NOR gate 31.sub.2,3. The output from 
the gate 31.sub.2,3 provides one input to the EXCLUSIVE-NOR gate 
31.sub.4,5 along with the output from the EXCLUSIVE-NOR gate 30.sub.4,5. 
In FIG. 5, the EXCLUSIVE-NOR gate 31.sub.2,3 takes the place of two or the 
gates of the gate 22 type in FIG. 2. Gate 31.sub.2,3 receives the y.sub.1 
input and produces the y.sub.3 output. Similarly, the gate 31.sub.4,5 
receives the y.sub.3 input and produces the y.sub.5 output. The 
even-valued y.sub.2 and y.sub.4 signals are not explicitly formed although 
their values, of course, are included within the odd-valued y.sub.3 and 
y.sub.5. More generally, the EXCLUSIVE-NOR gates 31.sub.2,3 ; 31.sub.4,5 ; 
31.sub.6,7 ; . . . , 31.sub.14,15 produce the odd-valued signals y.sub.3, 
y.sub.5, y.sub.7, . . . , y.sub.15, respectively. Although the even-valued 
signals y.sub.2, y.sub.4, y.sub.6, . . . , y.sub.14 are not explicitly 
generated they are included within the values y.sub.3, y.sub.5, y.sub.7, . 
. . , y.sub.15, respectively. 
In FIG. 5, the parity prediction network 12" forms the transmission bits 
x.sub.i for all values of "i" from 1 to "n" where x.sub.i is given as 
follows: 
EQU x.sub.i =[P.sub.i ][x.sub.i-1 ] 
where P.sub.i is the bit propagate given by 
EQU P.sub.i =a.sub.i .sym.b.sub.i 
Where the carry-out C.sub.OUT is not to be considered as is the case in 
FIG. 5, the value of x.sub.i-1 for "i" equal to 1 is 1, that is, x.sub.0 
is equal to 1 so that x.sub.1 is given as follows: 
EQU x.sub.i =[P.sub.i ][x.sub.0 ]=P.sub.i 
Where the carry-out C.sub.OUT is to be considered, x.sub.i is also defined 
for "i" equal to 0 as follows: 
EQU x.sub.0 =[P.sub.0 ][x.sub.-1 ]=P.sub.0 
In FIG. 5, the parity prediction network 12" forms the transmission bits 
y.sub.i for values of "i" equal to 3, 5, . . . , 13, 15 where y.sub.i is 
given as follows: 
EQU y.sub.i =[y.sub.i-2 
].sym.[(G.sub.i-1)(x.sub.i-2)].sym.[(G.sub.i)(x.sub.i-1)] 
where G.sub.i is the bit generate given by, 
EQU G.sub.i =(a.sub.i)(b.sub.i) 
Where the carry-out is not to be considered as in the case of FIG. 5, the 
value of y.sub.i-2 for "i" equal to 3 is G.sub.i so that y.sub.3 is given 
as follows: 
EQU y.sub.3 =[y.sub.1 ].sym.[(G.sub.2)(x.sub.1)].sym.[(G.sub.3)(x.sub.2)] 
where, 
EQU y.sub.1 =G.sub.1 
EQU x.sub.i =P.sub.i 
Where the carry-out C.sub.OUT is to be considered, y.sub.i is also defined 
for "i" equal to 1 as follows: 
EQU y.sub.1 =[y.sub.-1 ].sym.[(G.sub.0)(x.sub.-1)].sym.(G.sub.1)(x.sub.0)] 
where x.sub.-1 is equal to the constant 1 and x.sub.0 is equal to P.sub.0. 
In the latter case where the carry-out C.sub.OUT is to be considered, FIG. 
5 is modified to include a NAND gate 21.sub.0 (not shown) to form a signal 
[(x.sub.-1)(G.sub.0)] as an input to replace the 1 input to gate 
30.sub.0,1. Also, a NAND gate 20.sub.0 (not shown) is included to form a 
signal [(x.sub.-1)(P.sub.0)] as the x.sub.0 input to gate 20.sub.1. 
In FIG. 5, the use of only the odd-valued transmission signals y.sub.1, 
y.sub.3, y.sub.5, . . . , y.sub.15 results from bundling the outputs from 
the gates 21. With this manner of bundling the outputs, the number of 
delay times created in forming the predicted parity p.sub.p bit is 
substantially reduced. 
In FIG. 5, the numbers within the gate symbols designate the accumulated 
delay times where 2-input NAND gates are designated as one unit of delay 
and the EXCLUSIVE-NOR gates are designated as two units of delay. As 
indicated in FIG. 5, the output from the last EXCLUSIVE-NOR gate has 23 
accumulated units of delay. If the parity prediction were extended to 
include the carry-out C.sub.OUT, then 24 units of delay would be required. 
While the invention has been particularly shown and described with 
reference to the preferred embodiments thereof, it will be understood by 
those skilled in the art that those changes in form and details may be 
made therein without departing from the spirit and the scope of the 
invention.