US Patent 7155473 High-speed parallel-prefix modulo 2n-1 adders

A parallel-prefix modulo 2n−1 adder that is as fast as the fastest parallel prefix 2n integer adders, does not require an extra level of logic to generate the carry values, and has a very regular structure to which pipeline registers can easily be added. All nodes of the adder have a fanout ≦2. In the prefix structure of the adder, each carry value term output by the parallel prefix structure is determined by the all of the bits in the operands input to the adder. In one embodiment, there are log2 n stages in the prefix structure. Each stage has n logical operators, and all of the logical operators in the prefix structure are of the same kind. Pipeline registers may be inserted before and/or after a stage in the prefix structure.