An Efficient Method for Evaluating Complex Polynomials

Abstract : We propose an effi cient hardware-oriented method for evaluating complex polynomials. The method is based on solving iteratively a system of linear equations. The solutions are obtained digit-by-digit on simple and highly regular hardware. The operations performed are defined over the reals. We describe a complex-to-real transform, a complex polynomial evaluation algorithm, the convergence conditions, and a corresponding design and implementation. The la- tency and the area are estimated for the radix-2 case. The main features of the method are: the latency of about m cycles for an m-bit precision; the cycle time independent of the precision; a design consisting of identical modules; and digit-serial connections between the modules. The number of modules, each roughly corresponding to serial-parallel multiplier without a carry-propagate adder, is 2(n + 1) for evaluating an n-th degree complex polynomial. The method can also be used to compute all successive integer powers of the complex argument with the same latency and a similar implementation cost. The design allows straightforward tradeoffs between latency and cost: a factor k decrease in cost leads to a factor k increase in latency. A similar tradeoff between precision, latency and cost exists. The proposed method is attractive for programmable plat- forms because of its regular and repetitive structure of simple hardware operators.
Document type :
Journal articles
Complete list of metadatas

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00446889
Contributor : Jean-Michel Muller <>
Submitted on : Wednesday, January 13, 2010 - 3:56:00 PM
Last modification on : Wednesday, November 20, 2019 - 7:35:15 AM
Long-term archiving on : Thursday, June 17, 2010 - 10:43:44 PM

File

ErcegovacMuller2010.pdf
Publisher files allowed on an open archive

Identifiers

Collections

Citation

Milos Ercegovac, Jean-Michel Muller. An Efficient Method for Evaluating Complex Polynomials. Journal of Signal Processing Systems, Springer, 2010, 58 (1), pp.17-27. ⟨10.1007/s11265-008-0265-8⟩. ⟨ensl-00446889⟩

Share

Metrics

Record views

273

Files downloads

232