HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

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 metadata

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00446889
Contributor : Jean-Michel Muller Connect in order to contact the contributor
Submitted on : Wednesday, January 13, 2010 - 3:56:00 PM
Last modification on : Friday, February 4, 2022 - 3:19:18 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

86

Files downloads

194