Low-complexity parallel evaluation of powers exploiting bit-level redundancy

In this work, we investigate the problem of computing any requested set of power terms in parallel using summations trees. This problem occurs in applications like polynomial approximation, Farrow filters (polynomial evaluation part) etc. In the proposed technique, the partial product of each power term is initially computed independently. A redundancy check is then made in each and among all partial products matrices at bit level. The redundancy here relates to the fact that same three partial products may be present in more than one columns, and, hence, can be mapped to the same full adder. The proposed algorithm is tested for different sets of powers and wordlengths to exploit the sharing potential.