Parity prediction for arithmetic increment function

Abstract

The present invention provides a method and apparatus to check the arithmetic increment function through prediction of the change in the bit-level parity of the result by means of a series of identical cells connected in a linear array. The array predicts the change in parity produced by the arithmetic increment function which allows the increment function to be checked in an efficient manner. The advantages of the present invention are that the parity check design saves hardware cost over prior schemes that require duplication of incrementers and comparison of the results and schemes that require generation of parity after incrementing, and that the iterative, identical cell implementation of the parity predictor is well-suited for current VLSI and future digital logic circuits as they progress towards molecular, self-assembling components.

1. A circuit for generating a parity check for an increment function on an operand, said circuit comprising:
 a plurality of cells arranged in a row, each cell capable of receiving from an operand input at least one pair of bits from the operand and connected sequentially to one another by way of a disable connection and a parity inversion connection; and 
 a logic circuit in each cell that sends a disable signal over the disable connection to disable the logic circuit in each subsequent cell in the plurality of cells when there is no carry predicted from an increment to be performed on the at least one pair of bits from the operand and sends a parity inversion signal over the parity inversion connection when the at least one pair of bits from the operand indicates that incrementing the at least one pair of bits from operand would change the parity of the operand. 
 
     
     
       2. The circuit according to  claim 1 , wherein said disable connection further includes a disable input capable of providing a disable input signal to a cell and a disable output capable of providing a disable output signal to a subsequent cell in the plurality of cells. 
     
     
       3. The circuit according to  claim 1 , wherein no carry is predicted from an increment to be performed on a pair of bits selected from a set of bit patterns including “01 and 10”. 
     
     
       4. The circuit according to  claim 1 , wherein incrementing the at least one pair of bits from the operand changes the parity when an odd number of bits are altered. 
     
     
       5. The circuit according to  claim 4 , wherein incrementing a bit pattern derived from a set of bit patterns including “00 and 10” results in altering the odd number of bits. 
     
     
       6. The circuit according to  claim 5 , wherein the logic circuit in each cell does not receive a disable signal when a carry is predicted from the one or more preceding cells in the plurality of cells. 
     
     
       7. The circuit according to  claim 1 , wherein the parity inversion signal carried over the parity inversion connection indicates that the parity of the operand will change when it is incremented. 
     
     
       8. An apparatus for generating a parity check for an increment function, said apparatus comprising:
 means for receiving an operand in a plurality of cells before incrementing the operand by an increment function; 
 means for determining from one cell in the plurality of cells at least one pair of bits from the operand with at least one bit having a logical value zero that prevents a carry from occuring in one or more of the subsequent cells; 
 means responsive to the determination for disabling from the plurality of cells those cells subsequent to the one cell; and 
 means for indicating an inversion of the parity when an increment to the one cell having the at least one pair of bits from the operand changes a parity of the operand. 
 
     
     
       9. The apparatus according to  claim 8 , wherein the parity of the operand is inverted when the increment to the at least one pair of bits from the operand would result in changing an odd number of bits. 
     
     
       10. The apparatus according to  claim 9 , wherein incrementing a bit pattern derived from a set of bit patterns including “00 and 10” results in altering an odd number of bits. 
     
     
       11. A method for generating a parity check for an increment function on an operand, said method comprising the steps of:
 receiving an operand in a plurality of cells before incrementing the operand by the increment function; 
 determining from one cell in the plurality of cells at least one pair of bits from the operand with at least one bit of logical value zero that prevents a carry from occuring in one or more of the subsequent cells; 
 responding to the determination by disabling from the plurality of cells those cells subsequent to the one cell; and 
 indicating an inversion of the parity when an increment to the one cell having the at least one pair of bits from the operand changes a parity of the operand. 
 
     
     
       12. The method according to  claim 11 , wherein the parity of the operand is inverted when the increment to the at least one pair of bits from the operand would result in changing an odd number of bits. 
     
     
       13. The method according to  claim 12 , wherein incrementing a bit pattern derived from a set of bit patterns including “00 and 10” results in altering an odd number of bits.