Velocity Reviews > VHDL > round,fix and floor algortihms

# round,fix and floor algortihms

Dave
Guest
Posts: n/a

 01-03-2008
On Jan 3, 11:55*am, (E-Mail Removed) wrote:
> On Jan 3, 10:58*am, Dave <(E-Mail Removed)> wrote:
>
>
>
>
>
> > On Jan 3, 10:37*am, Andy <(E-Mail Removed)> wrote:

>
> > > On Jan 3, 9:29 am, (E-Mail Removed) wrote:

>
> > > > On Jan 3, 9:57 am, Andy <(E-Mail Removed)> wrote:

>
> > > > > On Jan 3, 7:16 am, "Symon" <(E-Mail Removed)> wrote:

>
> > > > > > <(E-Mail Removed)> wrote in message

>
> > > > > >news:(E-Mail Removed)...>Iwoul dliketoknowwhich round,fix and floor algorithm would be best
> > > > > > > to be implemented on an FPGA. I am working on a DSP project. I want to
> > > > > > > write funtions in VHDL which can be called and would return the round,
> > > > > > > fix and floor value of integers.

>
> > > > > > I'm missing something. How do you 'round' or 'floor' an integer? They
> > > > > > already are, aren't they?
> > > > > > Cheers, Syms.

>
> > > > > For integers, I think it should be approached as round(), ceil() or
> > > > > floor() of a ratio of two integers, since rational numbers (including
> > > > > rational approximations of non-rational numbers) are the primary
> > > > > issue, not integers. Unsigned integer division uses floor anyway. I've
> > > > > implemented unsigned ceil(n/d) before as (n + d - 1) / d, used for
> > > > > constants only (no synthesized hardware created). I haven't tried it,
> > > > > but I suppose something like (n + d / 2) / d would work for unsigned
> > > > > round()? It makes my head hurt to think about signed versions of
> > > > > these...

>
> > > > > In hardware, bit operations are probably more efficient (i.e. perform
> > > > > a fixed point division, and add one if the fraction msb is set for
> > > > > round(), or if any fraction bits are set for ceil(), then truncate the
> > > > > fraction. Anyone looked at the fixed point package to see how they do
> > > > > it?

>
> > > > > Andy

>
> > > > I want to implement Round Half Up algorithm in FPGA's. The inputs are
> > > > in the form unsigned_logic_vector having a bit width "bw1". Output is
> > > > return unsigned_logic_vector of width "bw2". I would like to know how
> > > > to implement this. I am not sure, but i guess I have to add a '10'
> > > > after the decimal point. But I dont understand one thing. How would I
> > > > know where the decimal point is in a string of '1' and '0' in the
> > > > input.

>
> > > Using std_logic_vector, signed or unsigned types, you just have to
> > > keep track of the binary point yourself.

>
> > > That's the beauty of the fixed point package and sfixed or ufixed
> > > types: bit 0 is always lsb of integer, bit -1 is msb of fraction.
> > > Positive bit indexes are the integer, and negative ones are the
> > > fraction.

>
> > > Andy- Hide quoted text -

>
> > > - Show quoted text -

>
> > It's always helped me to comment my code where I use a fixed-point
> > numbers, showing where the binary point is *I describe the number as
> > "Qx.y", where x is the umber of integral bits (including sign), and y
> > is the number of fractional bits. Something like:

>
> > signal x : signed(15 downto 0); -- Q1.15
> > signal y : signed(15 downto 0); -- Q1.15
> > signal z : signed(31 downto 0); -- Q2.30
> > signal a : signed(16 downto 0); -- Q2.15

>
> > ...

>
> > z <= x * y; -- Q1.15 * Q1.15 = Q2.30
> > a <= x + y; -- Q1.15 + Q1.15 = Q2.15 (to avoid overflow)

>
> > Dave- Hide quoted text -

>
> > - Show quoted text -

>
> I am still under confusion. I understand binary point. What I dont
> understand is if I get an input whose bit width is different than the
> bit width of ouptut, how will I know where the bianry point of the
> inout is. I am trying to write a function for floor, ceiling and round
> in VHDL. All these functions would have variable input and output bit
> widths. How will I know where the binary point of the output is?
>
> Thanks- Hide quoted text -
>
> - Show quoted text -

It sounds like what you're actually trying to implement is a truncate/
sign extend function. Try looking at the resize() function in
numeric_std. If the input width is less than the output width, you
probably want to sign extend. If the input width is larger than the
output width, then you may want to chop off some of the LSB's, or
possibly chop off some MSB's (designer's choice). Be careful, because
I think the resize function actually may chop off MSB's - I can't
remember. The exact position of the binary point is something that the
caller of the function will have to keep track of, keeping in mind the
behavior of the function. You shouildn't have to worry about it while
writing the function. With fixed point, the binary point position
exists only in the designer's mind (or comments).

What you're describing has nothing to do with rounding. There is,
however, a truncation method called "round-to-even", which is much
like truncation (chopping off LSB's), but twiddles with the LSB of the
result to try to get rid of any DC bias resulting from the truncation,
which otherwise would always be rounding in the same direction. Google
for it in comp.dsp or the internet to get a better explanation of it -
it's been a while for me.

Hope this helps.

Dave

Andy
Guest
Posts: n/a

 01-03-2008
On Jan 3, 10:55 am, (E-Mail Removed) wrote:
> On Jan 3, 10:58 am, Dave <(E-Mail Removed)> wrote:
>
>
>
> > On Jan 3, 10:37 am, Andy <(E-Mail Removed)> wrote:

>
> > > On Jan 3, 9:29 am, (E-Mail Removed) wrote:

>
> > > > On Jan 3, 9:57 am, Andy <(E-Mail Removed)> wrote:

>
> > > > > On Jan 3, 7:16 am, "Symon" <(E-Mail Removed)> wrote:

>
> > > > > > <(E-Mail Removed)> wrote in message

>
> > > > > >news:(E-Mail Removed)...>Iwoul dliketoknowwhich round,fix and floor algorithm would be best
> > > > > > > to be implemented on an FPGA. I am working on a DSP project. I want to
> > > > > > > write funtions in VHDL which can be called and would return the round,
> > > > > > > fix and floor value of integers.

>
> > > > > > I'm missing something. How do you 'round' or 'floor' an integer? They
> > > > > > already are, aren't they?
> > > > > > Cheers, Syms.

>
> > > > > For integers, I think it should be approached as round(), ceil() or
> > > > > floor() of a ratio of two integers, since rational numbers (including
> > > > > rational approximations of non-rational numbers) are the primary
> > > > > issue, not integers. Unsigned integer division uses floor anyway. I've
> > > > > implemented unsigned ceil(n/d) before as (n + d - 1) / d, used for
> > > > > constants only (no synthesized hardware created). I haven't tried it,
> > > > > but I suppose something like (n + d / 2) / d would work for unsigned
> > > > > round()? It makes my head hurt to think about signed versions of
> > > > > these...

>
> > > > > In hardware, bit operations are probably more efficient (i.e. perform
> > > > > a fixed point division, and add one if the fraction msb is set for
> > > > > round(), or if any fraction bits are set for ceil(), then truncate the
> > > > > fraction. Anyone looked at the fixed point package to see how they do
> > > > > it?

>
> > > > > Andy

>
> > > > I want to implement Round Half Up algorithm in FPGA's. The inputs are
> > > > in the form unsigned_logic_vector having a bit width "bw1". Output is
> > > > return unsigned_logic_vector of width "bw2". I would like to know how
> > > > to implement this. I am not sure, but i guess I have to add a '10'
> > > > after the decimal point. But I dont understand one thing. How would I
> > > > know where the decimal point is in a string of '1' and '0' in the
> > > > input.

>
> > > Using std_logic_vector, signed or unsigned types, you just have to
> > > keep track of the binary point yourself.

>
> > > That's the beauty of the fixed point package and sfixed or ufixed
> > > types: bit 0 is always lsb of integer, bit -1 is msb of fraction.
> > > Positive bit indexes are the integer, and negative ones are the
> > > fraction.

>
> > > Andy- Hide quoted text -

>
> > > - Show quoted text -

>
> > It's always helped me to comment my code where I use a fixed-point
> > numbers, showing where the binary point is I describe the number as
> > "Qx.y", where x is the umber of integral bits (including sign), and y
> > is the number of fractional bits. Something like:

>
> > signal x : signed(15 downto 0); -- Q1.15
> > signal y : signed(15 downto 0); -- Q1.15
> > signal z : signed(31 downto 0); -- Q2.30
> > signal a : signed(16 downto 0); -- Q2.15

>
> > ...

>
> > z <= x * y; -- Q1.15 * Q1.15 = Q2.30
> > a <= x + y; -- Q1.15 + Q1.15 = Q2.15 (to avoid overflow)

>
> > Dave- Hide quoted text -

>
> > - Show quoted text -

>
> I am still under confusion. I understand binary point. What I dont
> understand is if I get an input whose bit width is different than the
> bit width of ouptut, how will I know where the bianry point of the
> inout is. I am trying to write a function for floor, ceiling and round
> in VHDL. All these functions would have variable input and output bit
> widths. How will I know where the binary point of the output is?
>
> Thanks

You won't, unless you are given an argument to your function that
tells you where the binary point(s) are, or you use sfixed or ufixed
from the fixed point packages as your argument and return data types.

Don't reinvent the wheel; these packages were designed for exactly
that.

Andy

Dave
Guest
Posts: n/a

 01-03-2008
On Jan 3, 1:29*pm, Andy <(E-Mail Removed)> wrote:
> On Jan 3, 10:55 am, (E-Mail Removed) wrote:
>
>
>
>
>
> > On Jan 3, 10:58 am, Dave <(E-Mail Removed)> wrote:

>
> > > On Jan 3, 10:37 am, Andy <(E-Mail Removed)> wrote:

>
> > > > On Jan 3, 9:29 am, (E-Mail Removed) wrote:

>
> > > > > On Jan 3, 9:57 am, Andy <(E-Mail Removed)> wrote:

>
> > > > > > On Jan 3, 7:16 am, "Symon" <(E-Mail Removed)> wrote:

>
> > > > > > > <(E-Mail Removed)> wrote in message

>
> > > > > > >news:(E-Mail Removed)...>Iwoul dliketoknowwhichround,fix and floor algorithm would be best
> > > > > > > > to be implemented on an FPGA. I am working on a DSP project. I want to
> > > > > > > > write funtions in VHDL which can be called and would return the round,
> > > > > > > > fix and floor value of integers.

>
> > > > > > > I'm missing something. How do you 'round' or 'floor' an integer? They
> > > > > > > already are, aren't they?
> > > > > > > Cheers, Syms.

>
> > > > > > For integers, I think it should be approached as round(), ceil() or
> > > > > > floor() of a ratio of two integers, since rational numbers (including
> > > > > > rational approximations of non-rational numbers) are the primary
> > > > > > issue, not integers. Unsigned integer division uses floor anyway.. I've
> > > > > > implemented unsigned ceil(n/d) before as (n + d - 1) / d, used for
> > > > > > constants only (no synthesized hardware created). I haven't tried it,
> > > > > > but I suppose something like (n + d / 2) / d would work for unsigned
> > > > > > round()? It makes my head hurt to think about signed versions of
> > > > > > these...

>
> > > > > > In hardware, bit operations are probably more efficient (i.e. perform
> > > > > > a fixed point division, and add one if the fraction msb is set for
> > > > > > round(), or if any fraction bits are set for ceil(), then truncate the
> > > > > > fraction. Anyone looked at the fixed point package to see how they do
> > > > > > it?

>
> > > > > > Andy

>
> > > > > I want to implement Round Half Up algorithm in FPGA's. The inputs are
> > > > > in the form unsigned_logic_vector having a bit width "bw1". Output is
> > > > > return unsigned_logic_vector of width "bw2". I would like to know how
> > > > > to implement this. I am not sure, but i guess I have to add a '10'
> > > > > after the decimal point. But I dont understand one thing. How would I
> > > > > know where the decimal point is in a string of '1' and '0' in the
> > > > > input.

>
> > > > Using std_logic_vector, signed or unsigned types, you just have to
> > > > keep track of the binary point yourself.

>
> > > > That's the beauty of the fixed point package and sfixed or ufixed
> > > > types: bit 0 is always lsb of integer, bit -1 is msb of fraction.
> > > > Positive bit indexes are the integer, and negative ones are the
> > > > fraction.

>
> > > > Andy- Hide quoted text -

>
> > > > - Show quoted text -

>
> > > It's always helped me to comment my code where I use a fixed-point
> > > numbers, showing where the binary point is *I describe the number as
> > > "Qx.y", where x is the umber of integral bits (including sign), and y
> > > is the number of fractional bits. Something like:

>
> > > signal x : signed(15 downto 0); -- Q1.15
> > > signal y : signed(15 downto 0); -- Q1.15
> > > signal z : signed(31 downto 0); -- Q2.30
> > > signal a : signed(16 downto 0); -- Q2.15

>
> > > ...

>
> > > z <= x * y; -- Q1.15 * Q1.15 = Q2.30
> > > a <= x + y; -- Q1.15 + Q1.15 = Q2.15 (to avoid overflow)

>
> > > Dave- Hide quoted text -

>
> > > - Show quoted text -

>
> > I am still under confusion. I understand binary point. What I dont
> > understand is if I get an input whose bit width is different than the
> > bit width of ouptut, how will I know where the bianry point of the
> > inout is. I am trying to write a function for floor, ceiling and round
> > in VHDL. All these functions would have variable input and output bit
> > widths. How will I know where the binary point of the output is?

>
> > Thanks

>
> You won't, unless you are given an argument to your function that
> tells you where the binary point(s) are, or you use sfixed or ufixed
> from the fixed point packages as your argument and return data types.
>
> Don't reinvent the wheel; these packages were designed for exactly
> that.
>
> Andy- Hide quoted text -
>
> - Show quoted text -

Do all tools support these new packages? Which ones do? i have ISE
Webpack 9.2, and I don't think it does yet. They are definitely very
cool.

FPGA.unknown@gmail.com
Guest
Posts: n/a

 01-03-2008
On Jan 3, 1:43*pm, Dave <(E-Mail Removed)> wrote:
> On Jan 3, 1:29*pm, Andy <(E-Mail Removed)> wrote:
>
>
>
>
>
> > On Jan 3, 10:55 am, (E-Mail Removed) wrote:

>
> > > On Jan 3, 10:58 am, Dave <(E-Mail Removed)> wrote:

>
> > > > On Jan 3, 10:37 am, Andy <(E-Mail Removed)> wrote:

>
> > > > > On Jan 3, 9:29 am, (E-Mail Removed) wrote:

>
> > > > > > On Jan 3, 9:57 am, Andy <(E-Mail Removed)> wrote:

>
> > > > > > > On Jan 3, 7:16 am, "Symon" <(E-Mail Removed)> wrote:

>
> > > > > > > > <(E-Mail Removed)> wrote in message

>
> > > > > > > >news:(E-Mail Removed)...>Iwoul dliketoknowwhichround,fixand floor algorithm would be best
> > > > > > > > > to be implemented on an FPGA. I am working on a DSP project. I want to
> > > > > > > > > write funtions in VHDL which can be called and would return the round,
> > > > > > > > > fix and floor value of integers.

>
> > > > > > > > I'm missing something. How do you 'round' or 'floor' an integer? They
> > > > > > > > already are, aren't they?
> > > > > > > > Cheers, Syms.

>
> > > > > > > For integers, I think it should be approached as round(), ceil() or
> > > > > > > floor() of a ratio of two integers, since rational numbers (including
> > > > > > > rational approximations of non-rational numbers) are the primary
> > > > > > > issue, not integers. Unsigned integer division uses floor anyway. I've
> > > > > > > implemented unsigned ceil(n/d) before as (n + d - 1) / d, used for
> > > > > > > constants only (no synthesized hardware created). I haven't tried it,
> > > > > > > but I suppose something like (n + d / 2) / d would work for unsigned
> > > > > > > round()? It makes my head hurt to think about signed versions of
> > > > > > > these...

>
> > > > > > > In hardware, bit operations are probably more efficient (i.e. perform
> > > > > > > a fixed point division, and add one if the fraction msb is set for
> > > > > > > round(), or if any fraction bits are set for ceil(), then truncate the
> > > > > > > fraction. Anyone looked at the fixed point package to see how they do
> > > > > > > it?

>
> > > > > > > Andy

>
> > > > > > I want to implement Round Half Up algorithm in FPGA's. The inputs are
> > > > > > in the form unsigned_logic_vector having a bit width "bw1". Output is
> > > > > > return unsigned_logic_vector of width "bw2". I would like to know how
> > > > > > to implement this. I am not sure, but i guess I have to add a '10'
> > > > > > after the decimal point. But I dont understand one thing. How would I
> > > > > > know where the decimal point is in a string of '1' and '0' in the
> > > > > > input.

>
> > > > > Using std_logic_vector, signed or unsigned types, you just have to
> > > > > keep track of the binary point yourself.

>
> > > > > That's the beauty of the fixed point package and sfixed or ufixed
> > > > > types: bit 0 is always lsb of integer, bit -1 is msb of fraction.
> > > > > Positive bit indexes are the integer, and negative ones are the
> > > > > fraction.

>
> > > > > Andy- Hide quoted text -

>
> > > > > - Show quoted text -

>
> > > > It's always helped me to comment my code where I use a fixed-point
> > > > numbers, showing where the binary point is *I describe the number as
> > > > "Qx.y", where x is the umber of integral bits (including sign), and y
> > > > is the number of fractional bits. Something like:

>
> > > > signal x : signed(15 downto 0); -- Q1.15
> > > > signal y : signed(15 downto 0); -- Q1.15
> > > > signal z : signed(31 downto 0); -- Q2.30
> > > > signal a : signed(16 downto 0); -- Q2.15

>
> > > > ...

>
> > > > z <= x * y; -- Q1.15 * Q1.15 = Q2.30
> > > > a <= x + y; -- Q1.15 + Q1.15 = Q2.15 (to avoid overflow)

>
> > > > Dave- Hide quoted text -

>
> > > > - Show quoted text -

>
> > > I am still under confusion. I understand binary point. What I dont
> > > understand is if I get an input whose bit width is different than the
> > > bit width of ouptut, how will I know where the bianry point of the
> > > inout is. I am trying to write a function for floor, ceiling and round
> > > in VHDL. All these functions would have variable input and output bit
> > > widths. How will I know where the binary point of the output is?

>
> > > Thanks

>
> > You won't, unless you are given an argument to your function that
> > tells you where the binary point(s) are, or you use sfixed or ufixed
> > from the fixed point packages as your argument and return data types.

>
> > Don't reinvent the wheel; these packages were designed for exactly
> > that.

>
> > Andy- Hide quoted text -

>
> > - Show quoted text -

>
> Do all tools support these new packages? Which ones do? i have ISE
> Webpack 9.2, and I don't think it does yet. They are definitely very
> cool.- Hide quoted text -
>
> - Show quoted text -

Thank you all for your help.