Pipelined carry-lookahead generation for a fast incrementer

Abstract

An incrementer pipelines the generation of carry lookahead signals. Count registers hold a current count of the incrementer. The current count is fed back as inputs to sum logic, which generates sum bits that are latched into the count registers as a next count. All-ones detect logic detects when all lesser-significance bits in the current count are ones. When all lesser bits are ones, the sum logic toggles the count bit to generate the sum bit for that bit position. Pre-carry logic generates pre-carry lookahead signals from the sum bits. The pre-carry lookahead signals are latched into pipelined carry registers. The pipelined carry registers drive pipelined carry lookahead signals to the all-ones detect logic. Thus carry lookahead signals are generated from a prior sum but used in a next clock cycle to generate then next sum.

1. A pipelined incrementer, comprising:
 count registers for storing a current count of the pipelined incrementer, the count registers receiving sum bits that are stored as the current count in response to a clock input;  
 pre-carry registers, receiving pre-carry signals that are stored as pipelined carry lookahead signals in response to the clock input;  
 pre-carry logic, receiving at least some of the sum bits, for generating the pre-carry signals as a function of a next count indicated by the sum bits, the next count being after the current count in a pre-determined sequence; and  
 sum logic, receiving the current count from the count registers, and receiving the pipelined carry lookahead signals from the pre-carry registers, for generating the sum bits that indicate the next count,  
 whereby carry signals are generated from the sum bits that indicate the next count, stored in the pre-carry register, and used by the sum logic in a following clock cycle.  
 
     
     
       2. The pipelined incrementer of  claim 1  wherein the sum logic further comprises for at least some bit-positions of the current count:
 toggle logic, receiving a count bit for a given bit-position of the current count from one of the current count registers, and receiving a local carry-in signal for the given bit-position, the toggle logic toggling the count bit to generate the sum bit for the bit-position in response to the local carry-in signal for the given bit-position; and  
 all-ones detect logic, receiving count bits for lesser bit-positions from some of the current count registers, and  wherein for some of the bit-positions of the current count receiving , the all- ones detect logic receives one or more of  the pipelined carry lookahead signals instead of some of  count bits for lesser-significant bit-positions of the current count, and wherein the all- ones detect logic is configured  for activating the local carry-in signal for the given bit position when all lesser-significant bit-positions than the given bit position are logical one,  
 whereby a count bit for a bit-position is toggled when all lesser-significant bit-positions of the current count are logical one as indicated by the count bits or the pipelined carry lookahead signals.  
 
     
     
       3. The pipelined incrementer of  claim 2  wherein the toggle logic is replicated for all bit-positions of the current count above a least-significant bit-position;
 wherein the all-ones detect logic is replicated for bit-positions of the current count above two least-significant bit-positions,  
 whereby toggle and all-ones detect logic is replicated for several bit-positions.  
 
     
     
       4. The pipelined incrementer of  claim 2  wherein the all-ones detect logic is not replicated for an upper bit-position of the current count that corresponds to a first pipelined carry lookahead signal that is generated from all bit-positions below the upper bit-position. 
     
     
       5. The pipelined incrementer of  claim 2  wherein the toggle logic for a bit-position comprises an exclusive-OR (XOR) gate or an exclusive-NOR (XNOR) gate. 
     
     
       6. The pipelined incrementer of  claim 2  wherein the all-ones detect logic for a bit-position comprises an AND gate or a NAND gate that receives a group of inputs selected from the count bits and the pipelined carry lookahead signals. 
     
     
       7. The pipelined incrementer of  claim 6  wherein the pre-carry logic comprises a first AND or NAND gate that receives as inputs a first group of lowest-significance bit-positions of the sum bits, and a second AND or NAND gate that receives as inputs a second group of next-lowest-significance bit-positions of the sum bits that are in more significant bit-positions than the first group. 
     
     
       8. The pipelined incrementer of  claim 7  wherein the sum bits comprise at least 7 bits and the count bits comprise at least 7 bits and the pipelined carry lookahead signals comprise at least 2 signals,
 whereby the pipelined incrementer is at least a 7-bit counter.  
 
     
     
       9. The pipelined incrementer of  claim 8  wherein the next count follows the current count in a binary-number sequence. 
     
     
       10. The pipelined incrementer of  claim 2  further comprising:
 reset logic, coupled to the count registers and to the pre-carry registers, for resetting the current count to an initial value in response to a reset signal.  
 
     
     
       11. The pipelined incrementer of  claim 10  wherein the reset logic comprises NOR gates between the sum bits and inputs to the count registers, the NOR gates receiving the reset signal,
 whereby reset is synchronous to the clock input.  
 
     
     
       12. A sequencer comprising:
 sequence register means, responsive to a clock, for storing sum bits input to the sequence register means as current state bits in response to the clock;  
 first carry register means, responsive to the clock, for storing a first pre-carry signal that is input to the first carry register means, and for outputting a first pipelined carry signal;  
 first pre-carry logic means, receiving a first group of the sum bits, for generating the first pre-carry signal;  
 second carry register means, responsive to the clock, for storing a second pre-carry signal that is input to the second carry register means, and for outputting a second pipelined carry signal;  
 second pre-carry logic means, receiving a second group of the sum bits, for generating the second pre-carry signal; and  
 combinatorial logic means, receiving the current state bits from the sequence register means and receiving the first and second pipelined carry signals, for generating the sum bits,  
 whereby pre-carry signals are generated from the sum bits and stored for use in a next cycle of the clock.  
 
     
     
       13. The sequencer of  claim 12  wherein the combinatorial logic means further comprises:
 toggle means for each sum bit, each toggle means receiving a current state bit and generating a sum bit for a different bit-position, the toggle means for inverting a logical state of the current state bit to generate the sum bit.  
 
     
     
       14. The sequencer of  claim 13  wherein the toggle means for a least-significant-bit (LSB) of the sum bits is an inverter that inverts the current state bit to generate the sum bit for a LSB bit-position;
 wherein the toggle means for bit-positions above the LSB bit-position each comprise an exclusive-OR (XOR) gate that has a second control input, the second control input being activated to cause the toggle means to invert the current state bit, but being de-activated to cause the toggle means to not invert the current state bit.  
 
     
     
       15. The sequencer of  claim 14  wherein the sum bits and the current state bits include a first group, a second group, and a third group of bit-positions;
 wherein the combinatorial logic means further comprises a first logic grouping that generates sum bits in the first group, a second logic grouping that generates sum bits in the second group, and a third logic grouping that generates sum bits in the third group;  
 wherein the first logic grouping of the combinatorial logic means does not receive the first and second pipelined carry signals but only receives current state bits from the first group;  
 wherein the second logic grouping of the combinatorial logic means does not receive the second pipelined carry signal but only receives current state bits from the second group and receives the first pipelined carry signal;  
 wherein the third logic grouping of the combinatorial logic means receives the first and second pipelined carry signals and receives current state bits from only the third group.  
 
     
     
       16. The sequencer of  claim 15  wherein a lowest bit-position in the second logic grouping has a toggle means that receives the current state bit for the bit-position and receives the first pipelined carry signal as the second control input;
 wherein other bit-positions in the second logic grouping have a toggle means with a second control input driven by a detect means for detecting when all lower bit-positions are in a pre-determined state that toggles the sum bit in the bit-position.  
 
     
     
       17. The sequencer of  claim 15  wherein each bit-position in the third logic grouping comprises:
 toggle means, receiving the current state bit for the bit-position, for toggling the current state bit to generate the sum bit in response to a second control input that is driven by a control signal for the bit-position; and  
 detect means, driving the control signal to the toggle means, for detecting when all when all lower bit-positions are in a pre-determined state that toggles the sum bit in the bit-position;  
 wherein a lowest bit-position in the third logic grouping has a detect means that receives the first and second pipelined carry signals;  
 wherein other bit-positions in the third logic grouping have a detect means that receives the first and second pipelined carry signals and at least one of the current state bits in the third group.  
 
     
     
       18. The sequencer of  claim 17  wherein the toggle means comprises an exclusive-OR (XOR) gate and wherein the detect means comprises an AND gate. 
     
     
       19. A pipelined-carry incrementer comprising:
 a first state register receiving a first sum bit and outputting a first state bit synchronized to a clock;  
 a second state register receiving a second sum bit and outputting a second state bit synchronized to the clock;  
 a third state register receiving a third sum bit and outputting a third state bit synchronized to the clock;  
 a fourth state register receiving a fourth sum bit and outputting a fourth state bit synchronized to the clock;  
 a fifth state register receiving a fifth sum bit and outputting a fifth state bit synchronized to the clock;  
 a sixth state register receiving a sixth sum bit and outputting a sixth state bit synchronized to the clock;  
 a seventh state register receiving a seventh sum bit and outputting a seventh state bit synchronized to the clock;  
 a first carry register receiving a first pre-carry and outputting a first pipelined carry synchronized to the clock;  
 a second carry register receiving a second pre-carry and outputting a second pipelined carry synchronized to the clock;  
 a first pre-carry gate, receiving the first, second, and third sum bits and outputting the first pre-carry;  
 a second pre-carry gate, receiving the fourth and fifth sum bits and outputting the second pre-carry;  
 second toggle logic that toggles the second state bit to generate the second sum bit when the first state bit is high;  
 third toggle logic that toggles the third state bit to generate the third sum bit when the first state bit and the second state bit are both high;  
 fourth toggle logic that toggles the fourth state bit to generate the fourth sum bit when the first pipelined carry is high;  
 fifth toggle logic that toggles the fifth state bit to generate the fifth sum bit when the first pipelined carry and the fourth state bit are both high;  
 sixth toggle logic that toggles the sixth state bit to generate the sixth sum bit when the first pipelined carry and the second pipelined carry are both high;  
 seventh toggle logic that toggles the seventh state bit to generate the seventh sum bit when the first pipelined carry and the second pipelined carry and the sixth state bit are all high.  
 
     
     
       20. The pipelined-carry incrementer of  claim 19  wherein the third, fifth, sixth, and seventh toggle logic comprise an AND gate that drives an input to an exclusive-OR (XOR) gate;
 wherein the second and fourth toggle logic comprise an XOR gate.  
 
     
     
       21. A pipelined sequencer, comprising:
   sequence state storage logic configured to store sequence state bits as a current sequence state of the pipelined sequencer in response to a clock input;        carry lookahead storage logic configured to store one or more pre - carry signals as pipelined carry lookahead signals in response to the clock input;        pre - carry logic configured to receive at least some of the sequence state bits and to generate the one or more pre - carry signals as a function of a next sequence state indicated by the sequence state bits; and        sequence state generation logic configured to generate the sequence state bits indicative of the next sequence state dependent upon the current sequence state and the pipelined carry lookahead signals.     
     
     
       22. The pipelined sequencer of  claim 21 , wherein to generate the sequence state bits indicative of the next sequence state, the sequence state generation logic is further configured to increment the current sequence state by an arithmetic value of  1 . 
     
     
       23. The pipelined sequencer of  claim 21 , wherein to generate the sequence state bits indicative of the next sequence state, the sequence state generation logic is further configured to increment the current sequence state by an arithmetic value other than  1 . 
     
     
       24. The pipelined sequencer of  claim 21 , wherein to generate the sequence state bits indicative of the next sequence state, the sequence state generation logic is further configured to decrement the current sequence state by an arithmetic value of  1 . 
     
     
       25. The pipelined sequencer of  claim 21 , wherein to generate the sequence state bits indicative of the next sequence state, the sequence state generation logic is further configured to decrement the current sequence state by an arithmetic value other than  1 . 
     
     
       26. The pipelined sequencer of  claim 21 , wherein the current sequence state and the next sequence state are encoded as binary numbers. 
     
     
       27. The pipelined sequencer of  claim 26 , wherein the next sequence state follows the current sequence state in a binary- number sequence.   
     
     
       28. The pipelined sequencer of  claim 21 , wherein the current sequence state and the next sequence state are encoded as values in a Gray code. 
     
     
       29. The pipelined sequencer of  claim 21 , further comprising reset logic configured to reset the sequence state storage logic and the carry lookahead storage logic to a reset value in response to a reset signal. 
     
     
       30. The pipelined sequencer of  claim 21 , wherein the sequence state generation logic includes all- ones detection logic configured to determine whether all less - significant bit positions than a given bit position of the current sequence state have a value of logical one.   
     
     
       31. The pipelined sequencer of  claim 30 , wherein for certain less- significant bit positions than the given bit position, the all - ones detection logic is configured to receive one or more pipelined carry lookahead signals corresponding to certain bit positions of the current sequence state instead of the values of the corresponding bits positions of the current sequence state.   
     
     
       32. A method, comprising:
   storing sequence state bits as a current sequence state of a pipelined sequencer in response to a clock input;        storing one or more pre - carry signals as pipelined carry lookahead signals in response to the clock input;        from at least some of the sequence state bits, generating the one or more pre - carry signals as a function of a next sequence state indicated by the sequence state bits; and        generating the sequence state bits indicative of the next sequence state dependent upon the current sequence state and the pipelined carry lookahead signals.     
     
     
       33. The method of  claim 32 , wherein generating sequence state bits indicative of the next sequence state includes incrementing the current sequence state by an arithmetic value of  1 . 
     
     
       34. The method of  claim 32 , wherein generating sequence state bits indicative of the next sequence state includes incrementing the current sequence state by an arithmetic value other than  1 . 
     
     
       35. The method of  claim 32 , wherein generating sequence state bits indicative of the next sequence state includes decrementing the current sequence state by an arithmetic value of  1 . 
     
     
       36. The method of  claim 32 , wherein generating sequence state bits indicative of the next sequence state includes decrementing the current sequence state by an arithmetic value other than  1 . 
     
     
       37. The method of  claim 32 , wherein the current sequence state and the next sequence state are encoded as binary numbers. 
     
     
       38. The method of  claim 37 , wherein the next sequence state follows the current sequence state in a binary- number sequence.   
     
     
       39. The method of  claim 32 , wherein the current sequence state and the next sequence state are encoded as values in a Gray code. 
     
     
       40. The method of  claim 32 , further comprising resetting the sequence state storage logic and the carry lookahead storage logic to a reset value in response to a reset signal. 
     
     
       41. The method of  claim 32 , wherein generating the sequence state bits indicative of the next sequence state includes determining whether all less- significant bit positions than a given bit position of the current sequence state have a value of logical one.   
     
     
       42. The method of  claim 41 , wherein for certain less- significant bit positions than the given bit position, determining whether the certain less - significant bit positions have a value of logic one is dependent upon one or more pipelined carry lookahead signals corresponding to certain bit positions of the current sequence state instead of the values of the corresponding bits positions of the current sequence state.   
     
     
       43. A pipelined incrementer, comprising:
   incrementer count storage logic configured to store incrementer count bits as a current incrementer count of the pipelined incrementer in response to a clock input;        carry lookahead storage logic configured to store one or more pre - carry signals as pipelined carry lookahead signals in response to the clock input;        pre - carry logic configured to receive at least some of the incrementer count bits and to generate the one or more pre - carry signals as a function of a next incrementer count indicated by the incrementer count bits; and        incrementer count generation logic configured to generate the incrementer count bits indicative of the next incrementer count dependent upon the current incrementer count and the pipelined carry lookahead signals.     
     
     
       44. The pipelined incrementer of  claim 43 , wherein to generate the incrementer count bits indicative of the next incrementer count, the incrementer count generation logic is further configured to increment the current incrementer count by an arithmetic value of  1 . 
     
     
       45. The pipelined incrementer of  claim 43 , wherein to generate the increment count bits indicative of the next incrementer count, the incrementer count generation logic is further configured to increment the current incrementer count by an arithmetic value other than  1 . 
     
     
       46. The pipelined incrementer of  claim 43 , wherein to generate the incrementer count bits indicative of the next incrementer count, the incrementer count generation logic is further configured to decrement the current incrementer count by an arithmetic value of  1 . 
     
     
       47. The pipelined incrementer of  claim 43 , wherein to generate the incrementer count bits indicative of the next incrementer count, the incrementer count generation logic is further configured to decrement the current incrementer count by an arithmetic value other than  1 . 
     
     
       48. The pipelined incrementer of  claim 43 , wherein the current incrementer count and the next incrementer count are encoded as binary numbers. 
     
     
       49. The pipelined incrementer of  claim 48 , wherein the next incrementer count follows the current incrementer count in a binary- number sequence.   
     
     
       50. The pipelined incrementer of  claim 43 , further comprising reset logic configured to reset the incrementer count storage logic and the carry lookahead storage logic to a reset value in response to a reset signal. 
     
     
       51. The pipelined incrementer of  claim 43 , wherein the incrementer count generation logic includes all- ones detection logic configured to determine whether all less - significant bit positions than a given bit position of the current incrementer count have a value of logical one.   
     
     
       52. The pipelined incrementer of  claim 51 , wherein for certain less- significant bit positions than the given bit position, the all - ones detection logic is configured to receive one or more pipelined carry lookahead signals corresponding to certain bit positions of the current incrementer count instead of the values of the corresponding bits positions of the current incrementer count.   
     
     
       53. A arithmetic logic unit including a pipelined sequencer, wherein the pipelined sequencer comprises:
   sequence state storage logic configured to store sequence state bits as a current sequence state of the pipelined sequencer in response to a clock input;        carry lookahead storage logic configured to store one or more pre - carry signals as pipelined carry lookahead signals in response to the clock input;        pre - carry logic configured to receive at least some of the sequence state bits and to generate the one or more pre - carry signals as a function of a next sequence state indicated by the sequence state bits; and        sequence state generation logic configured to generate the sequence state bits indicative of the next sequence state dependent upon the current sequence state and the pipelined carry lookahead signals.     
     
     
       54. The arithmetic logic unit of  claim 53 , wherein to generate the sequence state bits indicative of the next sequence state, the sequence state generation logic is further configured to increment the current sequence state by an arithmetic value of  1 . 
     
     
       55. The arithmetic logic unit of  claim 53 , wherein to generate the sequence state bits indicative of the next sequence state, the sequence state generation logic is further configured to increment the current sequence state by an arithmetic value other than  1 . 
     
     
       56. The arithmetic logic unit of  claim 53 , wherein to generate the sequence state bits indicative of the next sequence state, the sequence state generation logic is further configured to decrement the current sequence state by an arithmetic value of  1 . 
     
     
       57. The arithmetic logic unit of  claim 53 , wherein to generate the sequence state bits indicative of the next sequence state, the sequence state generation logic is further configured to decrement the current sequence state by an arithmetic value other than  1 . 
     
     
       58. The arithmetic logic unit of  claim 53 , wherein the current sequence state and the next sequence state are encoded as binary numbers. 
     
     
       59. The arithmetic logic unit of  claim 58 , wherein the next sequence state follows the current sequence state in a binary- number sequence.   
     
     
       60. The arithmetic logic unit of  claim 53 , wherein the current sequence state and the next sequence state are encoded as values in a Gray code. 
     
     
       61. The arithmetic logic unit of  claim 53 , further comprising reset logic configured to reset the sequence state storage logic and the carry lookahead storage logic to a reset value in response to a reset signal. 
     
     
       62. The arithmetic logic unit of  claim 53 , wherein the sequence state generation logic includes all- ones detection logic configured to determine whether all less - significant bit positions than a given bit position of the current sequence state have a value of logical one.   
     
     
       63. The arithmetic logic unit of  claim 62 , wherein for certain less- significant bit positions than the given bit position, the all - ones detection logic is configured to receive one or more pipelined carry lookahead signals corresponding to certain bit positions of the current sequence state instead of the values of the corresponding bits positions of the current sequence state.   
     
     
       64. A computer system including a pipelined sequencer, wherein the pipelined sequencer comprises:
   sequence state storage logic configured to store sequence state bits as a current sequence state of the pipelined sequencer in response to a clock input;        carry lookahead storage logic configured to store one or more pre - carry signals as pipelined carry lookahead signals in response to the clock input;        pre - carry logic configured to receive at least some of the sequence state bits and to generate the one or more pre - carry signals as a function of a next sequence state indicated by the sequence state bits; and        sequence state generation logic configured to generate the sequence state bits indicative of the next sequence state dependent upon the current sequence state and the pipelined carry lookahead signals.     
     
     
       65. The computer system of  claim 64 , wherein to generate the sequence state bits indicative of the next sequence state, the sequence state generation logic is further configured to increment the current sequence state by an arithmetic value of  1 . 
     
     
       66. The computer system of  claim 64 , wherein to generate the sequence state bits indicative of the next sequence state, the sequence state generation logic is further configured to increment the current sequence state by an arithmetic value other than  1 . 
     
     
       67. The computer system of  claim 64 , wherein to generate the sequence state bits indicative of the next sequence state, the sequence state generation logic is further configured to decrement the current sequence state by an arithmetic value of  1 . 
     
     
       68. The computer system of  claim 64 , wherein to generate the sequence state bits indicative of the next sequence state, the sequence state generation logic is further configured to decrement the current sequence state by an arithmetic value other than  1 . 
     
     
       69. The computer system of  claim 64 , wherein the current sequence state and the next sequence state are encoded as binary numbers. 
     
     
       70. The computer system of  claim 69 , wherein the next sequence state follows the current sequence state in a binary- number sequence.   
     
     
       71. The computer system of  claim 64 , wherein the current sequence state and the next sequence state are encoded as values in a Gray code. 
     
     
       72. The computer system of  claim 64 , further comprising reset logic configured to reset the sequence state storage logic and the carry lookahead storage logic to a reset value in response to a reset signal. 
     
     
       73. The computer system of  claim 64 , wherein the sequence state generation logic includes all- ones detection logic configured to determine whether all less - significant bit positions than a given bit position of the current sequence state have a value of logical one.   
     
     
       74. The computer system of  claim 73 , wherein for certain less- significant bit positions than the given bit position, the all - ones detection logic is configured to receive one or more pipelined carry lookahead signals corresponding to certain bit positions of the current sequence state instead of the values of the corresponding bits positions of the current sequence state.