For whatever it's worth, here's our version of ptolemy.math.Quantizer. We
ran into these bugs some time ago, fixed them, but at the same time changed
the rules about truncation towards the nearest ***LESS OR EQUAL***
fixed-point value that has the given precision since that is what happens in
most fixed-point DSP implementations when you, for example, truncate a
32-bit result to 16 bits by ignoring the 16 LSBs. That is why we didn't
contribute these changes back but kept them local.
They were used to test some 16/32-bit bit-exact vocoder algorithms.
Zoltan Kemenczy
Research in Motion Limited (www.rim.net)
305 Phillip St, Waterloo, Ontario Canada N2L 3W8
----------------------------------------------------------------------
/* A collection of methods for creating fixed point values.
Copyright (c) 1998-2001 The Regents of the University of California
and Research in Motion Limited.All rights reserved.
Permission is hereby granted, without written agreement and without
license or royalty fees, to use, copy, modify, and distribute this
software and its documentation for any purpose, provided that the above
copyright notice and the following two paragraphs appear in all copies
of this software.
IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA OR RESEARCH IN MOTION
LIMITED BE LIABLE TO ANY PARTY
FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES
ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF
THE UNIVERSITY OF CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF
SUCH DAMAGE.
THE UNIVERSITY OF CALIFORNIA AND RESEARCH IN MOTION LIMITED
SPECIFICALLY DISCLAIMS ANY WARRANTIES,
INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE
PROVIDED HEREUNDER IS ON AN "AS IS" BASIS, AND THE UNIVERSITY OF
CALIFORNIA AND RESEARCH IN MOTION
LIMITED HAVE NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES,
ENHANCEMENTS, OR MODIFICATIONS.
PT_COPYRIGHT_VERSION_2
COPYRIGHTENDKEY
@ProposedRating Yellow ([EMAIL PROTECTED])
@AcceptedRating Red ([EMAIL PROTECTED])
*/
package ptolemy.math;
import java.math.BigDecimal;
import java.math.BigInteger;
//////////////////////////////////////////////////////////////////////////
//// Quantizer
/**
This class provides a set of static methods for creating instances
of the FixPoint class from doubles, integers, or fixed point numbers.
The various round() methods return a fixed point value that is nearest
to the specified number, but has the specified precision.
The various truncate() methods return a fixed point value that is
nearest to the specified number, but no greater in magnitude.
All of these methods may introduce quantization errors and/or overflow.
@author Bart Kienhuis
@contributor Edward A. Lee
@version $Id: Quantizer.java,v 1.20 2001/10/16 04:36:13 cxh Exp $
@see FixPoint
@see Precision
*/
public class Quantizer {
// The only constructor is private so that this class cannot
// be instantiated.
private Quantizer() {}
///////////////////////////////////////////////////////////////////
//// public methods ////
/** Return the fixed point number that is nearest to the specified
* value, but has the given precision, possibly introducing
* quantization or overflow errors.
* An overflow error occurs if the specified number does not fit
* within the range possible with the specified precision. In that
* case, the returned value is either the maximum or minimum value
* possible with the given precision, depending on the sign of the
* specified number. In this case, a flag is set in the returned
* value to indicate that an overflow error occurred.
*
* @param value The value to represent.
* @param precision The precision of the representation.
* @return A fixed-point representation of the value.
*/
public static FixPoint round(double value, Precision precision) {
BigDecimal newValue = new BigDecimal( value );
return round( newValue, precision);
}
/** Return the fixed point number that is nearest to the specified
* value, but has the given precision, possibly introducing
* quantization or overflow errors.
* An overflow error occurs if the specified number does not fit
* within the range possible with the specified precision. In that
* case, the returned value is either the maximum or minimum value
* possible with the given precision, depending on the sign of the
* specified number. In this case, a flag is set in the returned
* value to indicate that an overflow error occurred.
*
* @param value The value to represent.
* @param precision The precision of the representation.
* @return A fixed-point representation of the value.
*/
public static FixPoint round(BigDecimal value, Precision precision) {
BigInteger tmpValue;
BigInteger fxvalue;
boolean overflow = false;
BigDecimal x = value;
BigDecimal maxValue = precision.findMaximum();
BigDecimal minValue = precision.findMinimum();
// check if 'x' falls within the range of this FixPoint
// possible with the given precision
if ( x.compareTo(maxValue) > 0 ) {
overflow = true;
x = maxValue;
}
if ( x.compareTo(minValue) < 0 ) {
overflow = true;
x = minValue;
}
// determine the scale factor by calculating
// 2^fractionBitLength By multiply the given value 'x' with
// this scale factor. An value is obtained of the fraction
// part is dropped. The integer remaining after the scaling
// will be represented by the BigInteger.
int number = precision.getFractionBitLength();
// This division divides two number in a precision of 40
// decimal behind the point. This is equivalent with a
// fractional precision of 128 bits. ( ln(1-^40)/ln(2) > 128)
BigDecimal resolution = _one.divide( _getTwoRaisedTo(number+1),
40, BigDecimal.ROUND_HALF_EVEN);
BigDecimal multiplier;
if ( x.signum() >= 0 ) {
multiplier = x.add(resolution );
} else {
multiplier = x.subtract(resolution);
}
BigDecimal kl = _getTwoRaisedTo(number).multiply( multiplier );
// By going from BigDecimal to BigInteger, remove the fraction
// part. This part introduces a quantization error.
fxvalue = kl.toBigInteger();
// Create a new FixPoint
FixPoint fxp = new FixPoint( precision, fxvalue );
// and set the overflow flag, if overflow occurred
if ( overflow ) {
fxp.setError( FixPoint.OVERFLOW );
}
return fxp;
}
/** Return the fixed point number that is nearest to the specified
* value, but has the given precision, possibly introducing
* quantization or overflow errors.
* An overflow error occurs if the specified number does not fit
* within the range possible with the specified precision. In that
* case, the returned value depends on the specified mode.
* If the mode is SATURATE, then the return value is either
* the maximum or minimum value possible with the given
* precision, depending on the sign of the
* specified number. If the mode is OVERFLOW_TO_ZERO,
* then the return value is zero.
* In either case, a flag is set in the returned
* value to indicate that an overflow error occurred.
*
* @param value The value to represent.
* @param newPrecision The precision of the representation.
* @param mode The overflow mode.
* @return A new fixed-point representation of the value.
*/
public static FixPoint round(
FixPoint value,
Precision newPrecision,
int mode) {
FixPoint newValue = null;
BigDecimal x = value.bigDecimalValue();
BigDecimal maxValue = newPrecision.findMaximum();
BigDecimal minValue = newPrecision.findMinimum();
// check if 'x' falls within the range of this FixPoint
// possible with the given precision
if ( x.compareTo(maxValue) < 0 &&
x.compareTo(minValue) > 0 ) {
// In range, thus leads at most to a quantization error
newValue = Quantizer.round(x, newPrecision);
} else {
FixPoint result;
//Not in range. Can lead to an overflow problem.
switch(mode) {
case SATURATE:
if ( x.signum() >= 0) {
result = Quantizer.round( maxValue, newPrecision );
} else {
result = Quantizer.round( minValue, newPrecision );
}
result.setError(FixPoint.OVERFLOW);
//return result;
break;
case OVERFLOW_TO_ZERO:
result = new FixPoint(newPrecision, BigInteger.ZERO);
result.setError(FixPoint.OVERFLOW);
//return result;
break;
default:
throw new IllegalArgumentException("Illegal Mode of " +
"overflow handling");
}
newValue = result;
}
return newValue;
}
/** Return the nearest less than or equal fixed point number
* that has the given precision, possibly introducing
* quantization or overflow errors.
* An overflow error occurs if the specified number does not fit
* within the range possible with the specified precision. In that
* case, the returned value is either the maximum or minimum value
* possible with the given precision, depending on the sign of the
* specified number. In this case, a flag is set in the returned
* value to indicate that an overflow error occurred.
*
* @param value The value to represent.
* @param precision The precision of the representation.
* @return A fixed-point representation of the value.
*/
public static FixPoint truncate(double value, Precision precision) {
BigDecimal newValue = new BigDecimal( value );
return truncate( newValue, precision);
}
/** Return the nearest less than or equal fixed point number
* that has the given precision, possibly introducing
* quantization or overflow errors.
* An overflow error occurs if the specified number does not fit
* within the range possible with the specified precision. In that
* case, the returned value is either the maximum or minimum value
* possible with the given precision, depending on the sign of the
* specified number. In this case, a flag is set in the returned
* value to indicate that an overflow error occurred.
*
* @param value The value to represent.
* @param precision The precision of the representation.
* @return A fixed-point representation of the value.
*/
public static FixPoint truncate(BigDecimal value, Precision precision) {
BigInteger tmpValue;
BigInteger fxvalue;
boolean overflow = false;
BigDecimal x = value;
BigDecimal maxValue = precision.findMaximum();
BigDecimal minValue = precision.findMinimum();
// check if 'x' falls within the range of this FixPoint with
// given precision
if ( x.compareTo(maxValue) > 0 ) {
overflow = true;
x = maxValue;
}
if ( x.compareTo(minValue) < 0 ) {
overflow = true;
x = minValue;
}
int number = precision.getFractionBitLength();
BigDecimal tmp = x.subtract(minValue);
tmp = _getTwoRaisedTo(number).multiply(tmp);
// Truncate by going from BigDecimal to BigInteger
fxvalue = tmp.toBigInteger();
fxvalue = fxvalue.add(_getTwoRaisedTo(number).multiply(minValue)
.toBigInteger());
// Create a new FixPoint
FixPoint fxp = new FixPoint( precision, fxvalue );
if ( overflow ) {
fxp.setError( FixPoint.OVERFLOW );
}
return fxp;
}
/** Return the nearest less than or equal fixed point number
* that has the given precision, possibly introducing
* quantization or overflow errors.
* An overflow error occurs if the specified number does not fit
* within the range possible with the specified precision. In that
* case, the returned value depends on the specified mode.
* If the mode is SATURATE, then the return value is either
* the maximum or minimum value possible with the given
* precision, depending on the sign of the
* specified number. If the mode is OVERFLOW_TO_ZERO,
* then the return value is zero.
* In either case, a flag is set in the returned
* value to indicate that an overflow error occurred.
*
* @param value The value to represent.
* @param newPrecision The precision of the representation.
* @param mode The overflow mode.
* @return A new fixed-point representation of the value.
*/
public static FixPoint truncate(
FixPoint value,
Precision newPrecision,
int mode) {
FixPoint newValue = null;
BigDecimal x = value.bigDecimalValue();
BigDecimal maxValue = newPrecision.findMaximum();
BigDecimal minValue = newPrecision.findMinimum();
FixPoint result;
if ( x.compareTo(maxValue) > 0 ) {
switch (mode) {
case SATURATE:
result = Quantizer.truncate( maxValue, newPrecision );
break;
case OVERFLOW_TO_ZERO:
result = new FixPoint(newPrecision, BigInteger.ZERO);
break;
default:
throw new IllegalArgumentException("Illegal Mode of " +
"overflow handling");
}
result.setError(FixPoint.OVERFLOW);
} else if ( x.compareTo(minValue) < 0 ) {
switch (mode) {
case SATURATE:
result = Quantizer.truncate( minValue, newPrecision );
break;
case OVERFLOW_TO_ZERO:
result = new FixPoint(newPrecision, BigInteger.ZERO);
break;
default:
throw new IllegalArgumentException("Illegal Mode of " +
"overflow handling");
}
result.setError(FixPoint.OVERFLOW);
} else {
result = Quantizer.truncate(x, newPrecision);
}
return result;
}
///////////////////////////////////////////////////////////////////
//// public variables ////
/** Indicate that overflow should saturate. */
public static final int SATURATE = 0;
/** Indicate that overflow should result in a zero value. */
public static final int OVERFLOW_TO_ZERO = 1;
///////////////////////////////////////////////////////////////////
//// private methods ////
/** Get the BigDecimal which is the 2^exponent. If the value is
* already calculated, return this cached value, else calculate
* the value.
*
* @param number the exponent.
* @return the BigDecimal representing 2^exponent.
*/
private static BigDecimal _getTwoRaisedTo(int number) {
if ( number < 32 && number >= 0 ) {
return _twoRaisedTo[number];
} else {
BigInteger two = _two.toBigInteger();
return new BigDecimal( two.pow( number ) );
}
}
///////////////////////////////////////////////////////////////////
//// private variables ////
/** Static reference to the BigDecimal representation of one. */
private static BigDecimal _one = new BigDecimal("1");
/** Calculate the table containing 2^x, with 0 < x < 64. Purpose
* is to speed up calculations involving calculating 2^x. The table is
* calculated using BigDecimal, since this make the transformation from
* string of bits to a double easier.
*/
private static BigDecimal[] _twoRaisedTo = new BigDecimal[32];
/** Static reference to the BigDecimal representation of two. */
private static BigDecimal _two = new BigDecimal("2");
//////////////////////
// static initializer
//////////////////////
static {
BigDecimal p2 = _one;
for (int i = 0; i < 32; i++) {
_twoRaisedTo[i] = p2;
p2 = p2.multiply( _two );
}
}
}
-----Original Message-----
From: Stephen Andrew Neuendorffer [mailto:[EMAIL PROTECTED]]
Sent: April 1, 2002 3:02 PM
To: [EMAIL PROTECTED]; [EMAIL PROTECTED]
Cc: [EMAIL PROTECTED]; bart Kienhuis
Subject: Re: [Ptolemy] Re: Quantizer bug
I've fixed this... truncation of negative numbers now rounds towards zero,
as I believe it should.
Jeff: Here is a more correct truncate method from ptolemy.math.Quantizer.
It looks like there are other problems with the fixpoint package,
however. I bit of quick poking seems to suggest that
truncate(fixpoint) and round(fixpoint) both truncate the value. There are
probably other bugs as well.
Particularly disturbing is that there were tests for the truncate method
that were obviously wrong (and not even returning one of the closest
fixed-point values...)
There are quite a few test suites for IEEE754/854... perhaps we could grab
one and leverage it? I don't know if it would have caught this error or
not, but... Unfortunately, the FixPoint code is a bit orphaned at the
moment...
public static FixPoint truncate(BigDecimal value, Precision precision)
{
BigInteger tmpValue;
BigInteger fxvalue;
boolean overflow = false;
BigDecimal x = value;
BigDecimal maxValue = precision.findMaximum();
BigDecimal minValue = precision.findMinimum();
// check if 'x' falls within the range of this FixPoint with
// given precision
if ( x.compareTo(maxValue) > 0 ) {
overflow = true;
x = maxValue;
}
if ( x.compareTo(minValue) < 0 ) {
overflow = true;
x = minValue;
}
// determine the scale factor by calculating 2^fractionBitLength
// By multiply the given value 'x' with this scale factor, we get
// a value of which we drop the fraction part. The integer
remaining
// will be represented by the BigInteger.
int number = precision.getFractionBitLength();
BigDecimal multiplier;
BigDecimal epsilon;
BigDecimal tmp;
// calculate epsilon
// This division divides two number in a precision of 40
// decimal behind the point. This is equivalent with a
// fractional precision of 128 bits. ( ln(1-^40)/ln(2) > 128)
epsilon = _one.divide(_getTwoRaisedTo(number + 11),
40, BigDecimal.ROUND_HALF_EVEN);
// Since there is slack in floating point numbers, add or
// subtract epsilon as appropriate to get the 'intuitively
// correct' fixed point value. Note that this epsilon is MUCH
smaller
// than the one performed with round.
if ( x.signum() >= 0 ) {
multiplier = x.add( epsilon );
} else {
multiplier = x.subtract(epsilon);
}
// determine the scale factor.
BigDecimal kl = _getTwoRaisedTo(number).multiply( multiplier );
// By going from BigDecimal to BigInteger, remove the fraction
// part introducing a quantization error.
fxvalue = kl.toBigInteger();
// Create a new FixPoint
FixPoint fxp = new FixPoint( precision, fxvalue );
if ( overflow ) {
fxp.setError( FixPoint.OVERFLOW );
}
return fxp;
}
At 08:37 AM 4/1/2002 -0800, Christopher Hylands wrote:
>The following appeared in comp.soft-sys.ptolemy.
>It look like Quantizer.java has not changed since Ptolemy II 1.0
>Can someone take a look and see what they think?
>
>If you responde, please cc [EMAIL PROTECTED]
>
>-Christopher
>
>------- Forwarded Message
>
>
>From: jpat <[EMAIL PROTECTED]>
>Subject: Quantizer bug
>Date: Sat, 30 Mar 2002 21:41:30 GMT
>
>ptolemy.math.Quantizer.java (PTII) gives incorrect results for negative
>numbers when using the truncate method. This is easily seen on the
FixedPoint
>demo at the ptolemy web site.
>(http://ptolemy.eecs.berkeley.edu/ptolemyII/ptII1.0/ptII1.0/ptolemy/domains
/
>sdf/demo/FixPoint/FixPoint.htm). Set the DoubleToFix actor's quantization
>parameter to truncate and notice that the "first quantized" error diverges
>for negative numbers. It is even easier to see if you increase the
precision.
>
>Looking at the code, I suspect the problem is in the calculation of epsilon
>in the truncate(BigDecimal value...) method. I don't understand why epsilon
is
>being added to the number before scaling but this is one place the code is
>different for positve vs. negative numbers. Note that in the positive
case,
>5 gets added to the exponent (variable is called "number") while in the
>negative case 11 gets added.
>
>Can anyone figure this code out and post the correct method? This is
hanging
>me up badly as I have built my entire system in PTII but need to model the
>quantization noise accurately.
>
>Thanks,
>Jeff
>- ---------
>
>Jeff Patterson
>Senior Design Engineer
>Synthesis Center of Technology
>Agilent Technologies
>[EMAIL PROTECTED]
>
>
>------- End of Forwarded Message
>
>_______________________________________________
>Ptolemy maillist - [EMAIL PROTECTED]
>http://www.gigascale.org/ptolemy/listinfo/ptolemy
----------------------------------------------------------------------------
Posted to the ptolemy-hackers mailing list. Please send administrative
mail for this list to: [EMAIL PROTECTED]
----------------------------------------------------------------------------
Posted to the ptolemy-hackers mailing list. Please send administrative
mail for this list to: [EMAIL PROTECTED]
