Patent ID: 7152089

Claim:
A circuit that performs a prefix computation, comprising: an N-bit prefix network comprised of prefix cells arranged into L+l logic levels, wherein N is greater than 8 and an integral power of two, and wherein L=log 2 N; wherein the N-bit prefix network computes N outputs {Y N , . . . , Y 1 } from N inputs {X N , . . . , X 1 } using an associative two-input operator ∘◯, such that Y 1 =X 1 , Y 2 =X 2 ∘X 1 , Y 3 =X 3 ∘X 2 ∘X 1 , . . . , Y N =X N ∘X N−1 ∘ . . . ∘X 2 ∘X 1 , wherein each prefix cell has a fanout of at most 2 f +1; and wherein there are at most 2 t horizontal wiring tracks between each logic level; wherein l+f+t=L−1; and wherein l>0,f>0, and t>0.