Patent ID: 7917569

Claim:
A device for implementing a sum-of-products expression comprising: a first set of 2-input Shift-and-Add (2SAD) circuits comprising respective taps for receiving a first set of coefficients for generating a first set of partially optimized expression terms by removing repeated odd fundamental coefficients and applying recursion therein to generate a reduced area sum-of-products implementation; a second set of 1-input Shift-and-Add (1SAD) circuits comprising respective taps for receiving a second set of coefficients obtained as a subset of the first set of coefficients for generating a second set of partially optimized expression terms by applying vertical optimization therein; a third set of 2SAD circuits comprising respective taps for receiving a combination of a third set of the coefficients, comprising respective taps for receiving a first subset of the first set of partially optimized expression terms and comprising respective taps for receiving a first subset of the second set of partially optimized expression terms as inputs, for generating a third set of partially optimized expression terms by applying horizontal optimization; a fourth set of 2SAD circuits comprising respective taps for receiving a combination of a fourth set of the coefficients, comprising respective taps for receiving a second subset of the first set of partially optimized expression terms, comprising respective taps for receiving a second subset of the second set of partially optimized expression terms, and comprising respective taps for receiving a first subset of the third set of partially optimized expression terms as inputs, for generating a fourth set of partially optimized expression terms by applying decomposition and factorization therein; and a fifth set of 2SAD circuits comprising respective taps for receiving the fourth set of partially optimized expression terms for providing an output.