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

Publishing Venue

Motorola

Related People

Barry Herold: AUTHOR [+3]

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 [3]. 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 [3]. 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                                                                ...