Third order polynomial evaluation in FPGA

I am looking to implement a third order polynomial in an FPGA. What kind of constraints should I impose on the coefficients and widths of the input variable, and how should I go about showing the error of the implementation?

I'm very new to this kind of formal DSP. So far I'm exploring both a Horner's rule and a parallel implementation. All of my inputs are ~12 bits of width. If I scale the inputs and then keep everything unsigned, how would I quantize this error?

Sorry if this is vague. I hope someone has some ideas/notes that can point me in the right direction.

Thanks!

On Sat, 01 Nov 2014 21:40:16 -0700, Travis Ayres wrote:

> I am looking to implement a third order polynomial in an FPGA. What kind
> of constraints should I impose on the coefficients and widths of the
> input variable, and how should I go about showing the error of the
> implementation?

What the hell do you mean by "implement a third order polynomial"?  Do 
you mean you want to implement a function y = f(x), where

y = a_3 * x^3 + a_2 * x^2 + a_1 * x + a_0   ?

> I'm very new to this kind of formal DSP. So far I'm exploring both a
> Horner's rule and a parallel implementation. All of my inputs are ~12
> bits of width. If I scale the inputs and then keep everything unsigned,
> how would I quantize this error?

What error?  What makes you think there will be error?  Error in what 
sense?

Answer, and you may not need to ask your current question.

> Sorry if this is vague. I hope someone has some ideas/notes that can
> point me in the right direction.

Well, clarify your question with a description of what it is that you 
want to actually _do_, and what your concerns are, and maybe someone will 
be able to help you.

Perhaps if you tell us what you're _really_ doing (i.e., making an 
automatic rice cooker, improved GPS locator, designing a nuke that can be 
cobbled together by 3rd-world tribesmen to enhance their self-esteem, 
etc.)

-- 
www.wescottdesign.com

On Saturday, November 1, 2014 9:50:17 PM UTC-7, Tim Wescott wrote:
> On Sat, 01 Nov 2014 21:40:16 -0700, Travis Ayres wrote:
> 
> > I am looking to implement a third order polynomial in an FPGA. What kind
> > of constraints should I impose on the coefficients and widths of the
> > input variable, and how should I go about showing the error of the
> > implementation?
> 
> What the hell do you mean by "implement a third order polynomial"?  Do 
> you mean you want to implement a function y = f(x), where
> 
> y = a_3 * x^3 + a_2 * x^2 + a_1 * x + a_0   ?

Yes; a third order polynomial.   

> 
> > I'm very new to this kind of formal DSP. So far I'm exploring both a
> > Horner's rule and a parallel implementation. All of my inputs are ~12
> > bits of width. If I scale the inputs and then keep everything unsigned,
> > how would I quantize this error?
> 
> What error?  What makes you think there will be error?  Error in what 
> sense?

Error in the conversion between floating and fixed point; error introduced by rounding modes, scaling and truncation. 


> 
> Answer, and you may not need to ask your current question.
> 
> > Sorry if this is vague. I hope someone has some ideas/notes that can
> > point me in the right direction.
> 
> Well, clarify your question with a description of what it is that you 
> want to actually _do_, and what your concerns are, and maybe someone will 
> be able to help you.
> 
> Perhaps if you tell us what you're _really_ doing (i.e., making an 
> automatic rice cooker, improved GPS locator, designing a nuke that can be 
> cobbled together by 3rd-world tribesmen to enhance their self-esteem, 
> etc.)

I thought the tacit agreement on the internet was that everyone was trying to do the last one? 

> 
> -- 
> www.wescottdesign.com

On Sat, 01 Nov 2014 23:15:47 -0700, Travis Ayres wrote:

> On Saturday, November 1, 2014 9:50:17 PM UTC-7, Tim Wescott wrote:
>> On Sat, 01 Nov 2014 21:40:16 -0700, Travis Ayres wrote:
>> 
>> > I am looking to implement a third order polynomial in an FPGA. What
>> > kind of constraints should I impose on the coefficients and widths of
>> > the input variable, and how should I go about showing the error of
>> > the implementation?
>> 
>> What the hell do you mean by "implement a third order polynomial"?  Do
>> you mean you want to implement a function y = f(x), where
>> 
>> y = a_3 * x^3 + a_2 * x^2 + a_1 * x + a_0   ?
> 
> Yes; a third order polynomial.
> 
> 
>> > I'm very new to this kind of formal DSP. So far I'm exploring both a
>> > Horner's rule and a parallel implementation. All of my inputs are ~12
>> > bits of width. If I scale the inputs and then keep everything
>> > unsigned, how would I quantize this error?
>> 
>> What error?  What makes you think there will be error?  Error in what
>> sense?
> 
> Error in the conversion between floating and fixed point; error
> introduced by rounding modes, scaling and truncation.
> 
This is why you need to tell us what you're _really_ doing.  You aren't 
framing your real problem well enough, and you aren't giving us enough 
information to answer you.  Error is obviously a concern, but you aren't 
speaking in engineering units, so it's impossible to make any sensible 
reply.

What is your input?  Fixed point?  Floating, since you mention it?

What does your output need to be?

Do you have any constraints on intermediate data representation?

What is your error budget?

I could go on and on and on, and probably not cover all the bases -- or 
you could outline what you're _really_ trying to do, and all of a sudden 
about half a dozen really bright people will know what you need, and will 
start helping you.

-- 
www.wescottdesign.com

On 11/2/2014 1:15 AM, Travis Ayres wrote:
> On Saturday, November 1, 2014 9:50:17 PM UTC-7, Tim Wescott wrote:
>> On Sat, 01 Nov 2014 21:40:16 -0700, Travis Ayres wrote:
>>
>>> I am looking to implement a third order polynomial in an FPGA. What kind
>>> of constraints should I impose on the coefficients and widths of the
>>> input variable, and how should I go about showing the error of the
>>> implementation?
>>
>> What the hell do you mean by "implement a third order polynomial"?  Do
>> you mean you want to implement a function y = f(x), where
>>
>> y = a_3 * x^3 + a_2 * x^2 + a_1 * x + a_0   ?
>
> Yes; a third order polynomial.
>
>>
>>> I'm very new to this kind of formal DSP. So far I'm exploring both a
>>> Horner's rule and a parallel implementation. All of my inputs are ~12
>>> bits of width. If I scale the inputs and then keep everything unsigned,
>>> how would I quantize this error?
>>
>> What error?  What makes you think there will be error?  Error in what
>> sense?
>
> Error in the conversion between floating and fixed point; error introduced by rounding modes, scaling and truncation.

Where does floating point come in?  If you are converting a 12 bit 
number to floating point, why would there be error introduced?

Not sure what you mean by scaling the 12 bit inputs.  Why do you need to 
scale them?

The cube of a 12 bit unsigned number is just a 36 bit number.  If you 
preserve all 36 bits there will be no error.  What is the resolution of 
your coefficients?  Add those bits to the 36 bits to find the total 
number of bits needed to represent the result.  Then decide how many of 
those bits you want to keep and how many you want to discard.

-- 

Rick

Tim Wescott <tim@seemywebsite.com> wrote:
> On Sat, 01 Nov 2014 23:15:47 -0700, Travis Ayres wrote:
 
(snip)

>>> > I'm very new to this kind of formal DSP. So far I'm exploring both a
>>> > Horner's rule and a parallel implementation. All of my inputs are ~12
>>> > bits of width. If I scale the inputs and then keep everything
>>> > unsigned, how would I quantize this error?
 
(snip)
>> Error in the conversion between floating and fixed point; error
>> introduced by rounding modes, scaling and truncation.
 
> This is why you need to tell us what you're _really_ doing.  You aren't 
> framing your real problem well enough, and you aren't giving us enough 
> information to answer you.  Error is obviously a concern, but you aren't 
> speaking in engineering units, so it's impossible to make any sensible 
> reply.

I suppose, but there isn't quite as much choice as that.

The usual FPGA block multiplier does 18 bit signed twos complement
multiplication, generating a 36 bit product. You probably want to
use those.  You won't be using all 36 bits, but having them allows
you to put the binary point where you want it. 

If the inputs are signed, you should keep them signed.  Where is
the binary point in the input?  How many bits of precision do you 
need, and how many would you like to have (if more than you need.)

> What is your input?  Fixed point?  Floating, since you mention it?

Fixed point is a lot easier (takes up less FPGA space) and is usually
a good choice for DSP problems.
 
> What does your output need to be?
 
> Do you have any constraints on intermediate data representation?
 
> What is your error budget?
 
> I could go on and on and on, and probably not cover all the bases -- or 
> you could outline what you're _really_ trying to do, and all of a sudden 
> about half a dozen really bright people will know what you need, and will 
> start helping you.

-- glen

Hi Travis,

(answering also a specific question that I got by email, as it could be of
general interest. It relates to example code I've got here
http://www.dsprelated.com/showarticle/594.php
in particular Figure 8: Horner scheme evaluation)

a fixed point implementation of Horner's scheme seems a good approach.
That's at least what I use.

"Fixed point math" is one key concept. You'll find lots of info on the web,
but IMHO it's best explored learning-by-doing. 
In fixed point math, the idea is that I multiply floats by shifting the
(binary) decimal point, that is, multiplying by powers of two. 

Horner is a series of multiplications (and additions). 
In a multiplication, I shift the first argument by "a" bits and the second
by "b" bits. 
The product is shifted by "a+b" bits. To go back to the original "a"-bit
shifted format for the next Horner round, I have to shift back by "b"
bits.

The "shift-back-by-b-bits" is the ">>> 13" in Fig. 8 
Note, ">>>" in Verilog means _arithmetic_ shift, which preserves the sign
bit.
Now this discards the lower 13 bits completely, equivalent to a floor(...)
rounding operation. 
The result is more accurate if I use midpoint rounding, that is, "floor(...
+ 0.5)". And 0.5 in fixed point is 1 << 12.

Therefore the complete Horner scheme goes 
acc <= c3;
acc <= (acc * xLSB + $signed(1 << 12)) >>> 13) + c2;
acc <= (acc * xLSB + $signed(1 << 12)) >>> 13) + c1;
result <= (acc * xLSB + $signed(1 << 12)) >>> 13) + c0;

BTW, when writing fixed point code, I have to think carefully about
saturation: An internal overflow can turn the output signal into random
noise.
For Horner, this isn't trivial as it won't be obvious, whether the final
result is overflow or underflow, or has gone intermediately out-of-range
and returned. 
The problem can be avoided by checking every possible input value for a
given set of coefficients.
	 

_____________________________		
Posted through www.DSPRelated.com

On Sun, 02 Nov 2014 03:48:42 -0600, mnentwig wrote:

> Hi Travis,
> 
> (answering also a specific question that I got by email, as it could be
> of general interest. It relates to example code I've got here
> http://www.dsprelated.com/showarticle/594.php in particular Figure 8:
> Horner scheme evaluation)
> 
> a fixed point implementation of Horner's scheme seems a good approach.
> That's at least what I use.
> 
> "Fixed point math" is one key concept. You'll find lots of info on the
> web,
> but IMHO it's best explored learning-by-doing.


> In fixed point math, the idea is that I multiply floats by shifting the
> (binary) decimal point, that is, multiplying by powers of two.

I'm not happy with this definition.  I would say that fixed-point math is 
NOT in any way floating point.  Instead, fixed-point math is a 
generalization of integer math, where you can express numbers with 
fractional parts.

This article may help: http://en.wikipedia.org/wiki/Q_%28number_format%
29.  I'm pretty sure that the Q notation is fairly popular.

<< snip >>

> BTW, when writing fixed point code, I have to think carefully about
> saturation: An internal overflow can turn the output signal into random
> noise.

And my, that can be embarrassing -- when it doesn't result in 
dismemberment, incineration and/or death.

> For Horner, this isn't trivial as it won't be obvious, whether the final
> result is overflow or underflow, or has gone intermediately out-of-range
> and returned.
> The problem can be avoided by checking every possible input value for a
> given set of coefficients.

I'm not sure if this is what you meant, but I would do one of two things: 
either arrange my number format so that overflow never happens, or check 
for overflow and saturate (or error out) at each stage.

Arranging for no overflow ever is safer.  Just calculate the maximum and 
minimum value that each intermediate value can take for any given input 
and your given coefficients, then make sure that the number fits.  While 
you're at it, you can make sure that if you do truncation or rounding 
that the error caused by that is not too severe.

-- 
www.wescottdesign.com

On 11/2/2014 4:49 PM, Tim Wescott wrote:
> On Sun, 02 Nov 2014 03:48:42 -0600, mnentwig wrote:
>
>> Hi Travis,
>>
>> (answering also a specific question that I got by email, as it could be
>> of general interest. It relates to example code I've got here
>> http://www.dsprelated.com/showarticle/594.php in particular Figure 8:
>> Horner scheme evaluation)
>>
>> a fixed point implementation of Horner's scheme seems a good approach.
>> That's at least what I use.
>>
>> "Fixed point math" is one key concept. You'll find lots of info on the
>> web,
>> but IMHO it's best explored learning-by-doing.
>
>
>> In fixed point math, the idea is that I multiply floats by shifting the
>> (binary) decimal point, that is, multiplying by powers of two.
>
> I'm not happy with this definition.  I would say that fixed-point math is
> NOT in any way floating point.  Instead, fixed-point math is a
> generalization of integer math, where you can express numbers with
> fractional parts.
>
> This article may help: http://en.wikipedia.org/wiki/Q_%28number_format%
> 29.  I'm pretty sure that the Q notation is fairly popular.
>
> << snip >>
>
>> BTW, when writing fixed point code, I have to think carefully about
>> saturation: An internal overflow can turn the output signal into random
>> noise.
>
> And my, that can be embarrassing -- when it doesn't result in
> dismemberment, incineration and/or death.
>
>> For Horner, this isn't trivial as it won't be obvious, whether the final
>> result is overflow or underflow, or has gone intermediately out-of-range
>> and returned.
>> The problem can be avoided by checking every possible input value for a
>> given set of coefficients.
>
> I'm not sure if this is what you meant, but I would do one of two things:
> either arrange my number format so that overflow never happens, or check
> for overflow and saturate (or error out) at each stage.
>
> Arranging for no overflow ever is safer.  Just calculate the maximum and
> minimum value that each intermediate value can take for any given input
> and your given coefficients, then make sure that the number fits.  While
> you're at it, you can make sure that if you do truncation or rounding
> that the error caused by that is not too severe.

All of this is about doing as much as possible while using as little as 
possible.  If multiplying four numbers in an FPGA you can preserve 
exactly whichever portions of the results, intermediate or final, as you 
choose, or not preserve what you choose.  There is no point in 
optimizing unless the benefit is worth the effort.  Usually optimization 
is just not optimal in some other sense, so don't do it unless you need 
to.

In this case it is simple enough to just code up the full calculations 
and pick the portion of the result with the significant bits.  We 
haven't heard from the OP lately, so we may not find out where the 
significant bits lie.

-- 

Rick

Hi,

>> or check for overflow and saturate (or error out) at each stage.

I see no obvious way to saturate in a Horner scheme, as later operations
use the saturated value as input. The sign of a saturated intermediate
result is not necessarily the sign of the output. 

If anybody knows a clever solution, please post it.

An exact calculation without rounding seems generally impractical, if I
look at the required bit width. 

	 

_____________________________		
Posted through www.DSPRelated.com