Browse Prior Art Database

# Method for Polynomial Transformation for Recursive Implementation

IP.com Disclosure Number: IPCOM000033541D
Original Publication Date: 2004-Dec-15
Included in the Prior Art Database: 2004-Dec-15
Document File: 5 page(s) / 509K

Motorola

## Related People

Barry Herold: AUTHOR [+2]

## Abstract

This paper presents a method to transform a regular polynomial into a recursive form. For an nth degree polynomial, 2n -1 multiplications and n additions are required. The transformation removes the multiplications and achieves the same with just n additions, hence reducing hardware complexity, power consumption and area requirements. Most methods to reduce computational complexity of a polynomial generation make use of Horner’s rule or Estrin’s Algorithm . However, these methods still require the use of multipliers.

This text was extracted from a Microsoft Word document.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 28% of the total text.

Method for Polynomial Transformation for Recursive Implementation

Barry Herold, Mohamed Imtiaz Ahmed & King Lee

1.                    Abstract

This paper presents a method to transform a regular polynomial into a recursive form. For an nth degree polynomial, 2n -1 multiplications and n additions are required. The transformation removes the multiplications and achieves the same with just n additions, hence reducing hardware complexity, power consumption and area requirements. Most methods to reduce computational complexity of a polynomial generation make use of Horner’s rule or Estrin’s Algorithm . However, these methods still require the use of multipliers.

2.                    Detailed Description

General Case

Consider a 4th order polynomial represented as

whereand  are the coefficients. For simplicity we consider that x increases in steps of 1. Hence by substituting x by x+1 in the above equation, we obtain the next value of f(x+1).

At first glance, we notice that f(x+1) contains f(x) and a remainder polynomial which we can refer to as g(x), i.e.

where

Similarly the next sample f(x+2) can be evaluated and simplified to be

It can be noted that the value of the function f at any given instant can always be determined by the past values of itself and past values of the remainder polynomial.

g(x+1) consists of a g(x) and a remainder polynomial which we designate as h(x).

where,

Similarly, the next sample g(x+2) is evaluated to be as

where,

,

Again,, where i(x) is the remainder polynomial defined as follows

The next sample of h(x+2) is defined as

where,

and

i(x+1) is a function of i(x) and a remainder constant we shall call j, i.e.

where                                                                ... 