IIR implementation on ARM

On 2011/03/25 07:25, luminous wrote:
> I'm interested in a biquad implementation on the 5E version of the ARM
> architecture.
>
> I have drawn a picture of how I imagine that a biquad implementation can be
> done with the SMLAWy instruction, you can find it here:
> http://dl.dropbox.com/u/10432980/biqARM.pdf
>
> A shift of 16 bits is inherent in the accumulator and not drawn as a
> separate block.
>
> I have indicated the scaling resulting in different parts of the diagram
> with a QI.F notation where I is the number of integer bits and F the number
> of fractional bits.
>
> The shift of 2 bits to the left is done to avoid that the integer part
> grows indefinitely due to the multiplications in the feedback path.
>
> I would be very glad for any comments on this, is there a smarter or more
> traditional way to do it so that the shifter isn't needed?
>
> /Viktor

I glanced over your picture quickly, and I notice that you specify Q0.32 
for y().  This implies that you have positive-only numbers, otherwise 
there's no place for the sign bit to go.  Normal signals tend to be 
bipolar, right?  Thus, you'd need to specify Q0.31, or Q.31 for short.

Now that I think about it, it seems that all of your fixed point 
notations are neglecting the sign bit (unless you have 17-bit and 33-bit 
registers).

Brian Willoughby
Sound Consulting

On Mar 27, 9:12�am, Brian Willoughby
<Sound_Consulting-...@Sounds.wa.com> wrote:
>
...
> I glanced over your picture quickly, and I notice that you specify Q0.32
> for y(). &#4294967295;This implies that you have positive-only numbers, otherwise
> there's no place for the sign bit to go. &#4294967295;Normal signals tend to be
> bipolar, right? &#4294967295;Thus, you'd need to specify Q0.31, or Q.31 for short.

i think the correct notation would be Q1.31 .  i have also seen the
notation S.31 .  if there were more bits to the left of the binary
point (say 3 more bits for a range of -8.0 to +7.99999), then it would
be Q4.28 or S3.28 .

i wish this notation would get standardized.

r b-j

On 2011/03/27 19:58, robert bristow-johnson wrote:
> On Mar 27, 9:12 am, Brian Willoughby
> <Sound_Consulting-...@Sounds.wa.com>  wrote:
>>
> ...
>> I glanced over your picture quickly, and I notice that you specify Q0.32
>> for y().  This implies that you have positive-only numbers, otherwise
>> there's no place for the sign bit to go.  Normal signals tend to be
>> bipolar, right?  Thus, you'd need to specify Q0.31, or Q.31 for short.
>
> i think the correct notation would be Q1.31 .  i have also seen the
> notation S.31 .  if there were more bits to the left of the binary
> point (say 3 more bits for a range of -8.0 to +7.99999), then it would
> be Q4.28 or S3.28 .
>
> i wish this notation would get standardized.

Agreed.

Texas Instruments seems to at least do a good job of explaining what 
they mean, but they leave the sign bit out of the visible numbers.  Thus 
the whole and fractional parts always add up to 15 or 31 or one bit less 
than the word length.

Apple doesn't define it at all, to my knowledge.  So, when they discuss 
8.24 as the canonical format for iOS (iPhone, iPad, iPod), they don't 
explain that you can't represent +255.0 in that notation.  New 
programmers often get confused as to why they cannot exceed +127.x or 
-128.0 in this format.  Apple should clarify that they're using Q7.24, 
if Texas Instruments' standard is accepted, or at least mention that 
8.24 loses a bit to the sign.

Thankfully, Wikipedia seems to conclusively state that the Q number 
format always sets aside the most significant bit for the sign bit, so 
that ordinary integer arithmetic logic can operate on fixed point 
numbers.  There's always the shadow of doubt when referencing Wikipedia 
for anything, but this twos-complement standard seems both completely 
logical and unavoidable, so I have no reason to doubt that it would be 
part of any sane Q number format specification.

Curiously: Where have you seen anyone Q1.31 for a number with 0 whole 
bits?  Apple is the only example I am aware of, but they use "8.24" and 
not literally "Q8.24" (I believe they'd be wrong if they used the 
latter, since the Q number format is somewhat standardized).

Brian Willoughby
Sound Consulting

On Mar 28, 3:20�am, Brian Willoughby
<Sound_Consulting-...@Sounds.wa.com> wrote:
> On 2011/03/27 19:58, robert bristow-johnson wrote:
>
...
>
> Curiously: Where have you seen anyone Q1.31 for a number with 0 whole
> bits?

i think that's all i ever see.

the sign bit is also an integer bit.

> &#4294967295;Apple is the only example I am aware of, but they use "8.24" and
> not literally "Q8.24" (I believe they'd be wrong if they used the
> latter, since the Q number format is somewhat standardized).

it *is*?  (standardized?)  i thought that was what i was complaining
about (that it *isn't* standardized).  what did you mean by "Agreed"?

really, the key number to worry about is the number to the *right* of
the "." .  so that Apple 8.24 format means that the number represented
by that *integer* (all fixed-point numbers ultimately live their lives
as integers - it's only in the mind of the programmer that they are
not integers) is 2^(-24) times the integer representation.  it makes
no difference for addition and subtraction, but when you multiply,
then you must realize that your result is 2^24 times too big and, to
bring the product back down to the correct scaling, you must shift
right by 24 bits.  some hardware does this for you, but i don't think
the ARM in an iPod does and i don't think that the C programming
language does it for you (until you use the x >>= 24; operation).

r b-j

robert bristow-johnson <rbj@audioimagination.com> wrote:
(snip)

>> Curiously: Where have you seen anyone Q1.31 for a number 
>> with 0 whole bits?
 
> i think that's all i ever see.
 
> the sign bit is also an integer bit.
 
(snip)
> really, the key number to worry about is the number to the *right* of
> the "." .  so that Apple 8.24 format means that the number represented
> by that *integer* (all fixed-point numbers ultimately live their lives
> as integers - it's only in the mind of the programmer that they are
> not integers) is 2^(-24) times the integer representation.  

IBM, in its descriptions of fixed point arithmetic does not describe
them as integers.  

> it makes
> no difference for addition and subtraction, but when you multiply,
> then you must realize that your result is 2^24 times too big and, to
> bring the product back down to the correct scaling, you must shift
> right by 24 bits.  

Well, more specifically, add the number of bits to the right of
the binary point, and that is the number to the right of the
binary point in the product.  That is the rule I learned in 3rd
grade (decimal, but the same rule).  Many high-level programming
languages don't provide support for fixed-point non-integer data.
Most processors support an N bit multiply with 2N bit product.
Many also a divide with 2N bit dividend (needed for dividing
scaled data).

> some hardware does this for you, but i don't think
> the ARM in an iPod does and i don't think that the C programming
> language does it for you (until you use the x >>= 24; operation).

PL/I, one of the few languages that supports scaled fixed point
arithmetic, describes them not counting the sign, with
FIXED BINARY(31,0) being the normal 32 bit integer.  The scale
factor (digits after the radix point) can be positive or negative.
The first number (31 above) is the total digits not counting the sign.

-- glen

On 03/27/2011 10:58 PM, robert bristow-johnson wrote:
> On Mar 27, 9:12 am, Brian Willoughby
> <Sound_Consulting-...@Sounds.wa.com>  wrote:
>>
> ...
>> I glanced over your picture quickly, and I notice that you specify Q0.32
>> for y().  This implies that you have positive-only numbers, otherwise
>> there's no place for the sign bit to go.  Normal signals tend to be
>> bipolar, right?  Thus, you'd need to specify Q0.31, or Q.31 for short.
>
> i think the correct notation would be Q1.31 .  i have also seen the
> notation S.31 .  if there were more bits to the left of the binary
> point (say 3 more bits for a range of -8.0 to +7.99999), then it would
> be Q4.28 or S3.28 .
>
> i wish this notation would get standardized.

I should also pipe up and say I've seen it as A(0, 31). Again as
I've stated in the past, I original saw this used by Don Heckathorn,
a physicist at MIT Lincoln Labs with whom I worked for a short while
back around 1998. A(x,y) is for signed, U(x,y) for unsigned - don't
know what "A" stands for!
-- 
Randy Yates                             Digital Signal Labs
919-577-9882                            http://www.digitalsignallabs.com
yates@digitalsignallabs.com

On 2011/03/28 07:46, robert bristow-johnson wrote:
> On Mar 28, 3:20 am, Brian Willoughby
> <Sound_Consulting-...@Sounds.wa.com>  wrote:
>> On 2011/03/27 19:58, robert bristow-johnson wrote:
>>
> ...
>>
>> Curiously: Where have you seen anyone Q1.31 for a number with 0 whole
>> bits?
>
> i think that's all i ever see.
>
> the sign bit is also an integer bit.

In fixed point, 'integer' is confusing (IMO) ... at least for C 
programmers.  The 'whole' part doesn't necessarily include the sign bit.

All (binary) numbers can be expressed as a sum of weighted powers, b2^n, 
where b is the value (0, 1) of the bit, and n is some power of the radix 
(2).

The sign bit, in contrast, I've seen notated as (-1)^b, where b is the 
value (0, 1) of the bit.

In other words, it doesn't have a nice symmetry (between the sign bit 
versus all the other bits), and so I prefer to treat the sign bit as 
separate.  It is rather interesting how the sign bit is duplicated in 
twos-complement, all the way from the top of the word to the most 
significant bit of the value in question.  So, in some respects, the 
sign bit does bleed into a number which had fewer significant bits than 
the word can hold.  But I'm still compelled to treat the sign bit 
separately.  Perhaps I think too much in terms of individual gates 
implementing an arithmetic unit inside a processor.


>>   Apple is the only example I am aware of, but they use "8.24" and
>> not literally "Q8.24" (I believe they'd be wrong if they used the
>> latter, since the Q number format is somewhat standardized).
>
> it *is*?  (standardized?)  i thought that was what i was complaining
> about (that it *isn't* standardized).  what did you mean by "Agreed"?

"Agreed" that it would be nice if it got officially and thoroughly 
standardized by everyone involved in the industry, as opposed to 
"somewhat standardized" as I observed.  Basically, usage in the field 
seems to ignore the available standard too frequently.  But I think that 
we have a reasonable, albeit flexible, standard if people would just 
choose to use it.

Some might say Q7.24, some might abbreviate that to Q.24 (with the 
assumption that a 32-bit word with sign bit is a given).  To me, that's 
enough of a standard, either one you choose.  But throwing in 8.24 as a 
synonym starts to allow too much confusion, especially in a field with 
many new members.


> really, the key number to worry about is the number to the *right* of
> the "." .  so that Apple 8.24 format means that the number represented
> by that *integer* (all fixed-point numbers ultimately live their lives
> as integers - it's only in the mind of the programmer that they are
> not integers) is 2^(-24) times the integer representation.  it makes
> no difference for addition and subtraction, but when you multiply,
> then you must realize that your result is 2^24 times too big and, to
> bring the product back down to the correct scaling, you must shift
> right by 24 bits.  some hardware does this for you, but i don't think
> the ARM in an iPod does and i don't think that the C programming
> language does it for you (until you use the x>>= 24; operation).

Glen beat me to the punch by pointing out that you don't shift by 24 
when working with 8.24 format.

If you multiply two Q.15 numbers, you get a Q.30 number.  If you want to 
maintain the decimal point in the same position relative to the left of 
the word, then you need to shift the result left by one bit, making it 
Q.31 in the final result.  The TMS320 has a FRAC mode bit in its status 
register which will accomplish this left shift in the same cycle as the 
multiplication, but it's turned off by default for the sake of the C 
programmers.

Many seasoned fixed-point programmers will maintain individual 
variables, each with a different decimal place.  Then, the 
multiplications must carefully count the position of the decimal place 
in the result, according to where it is in each multiplicand.

Brian Willoughby
Sound Consulting

I don't know what you mean by the sign bit "bleeding down" in two's complement. There are four binary number schemes that I've seen in common use. Offset binary is rare now, and never had much currency except in analog<->digital converters. Signed binary survives in floating-point representations. There mat still be signed-binary integer machines, but I know of none. Unsigned and two's complement are the other two. 

Offset binary, two's complement, and unsigned all wrap around. The complete set of any one is know by some as a number circle. The three number circles are in fact identical. They differ only in their wrap-around points. Those bits that are propagated by an arithmetic right shift aren't bleeding over. They're part of the number.

Jerry
-- 
Engineering is the art of making what you want from things you can get.

Brian Willoughby wrote:

> On 2011/03/28 07:46, robert bristow-johnson wrote:
> > On Mar 28, 3:20 am, Brian Willoughby
> > <Sound_Consulting-...@Sounds.wa.com>  wrote:
> >> On 2011/03/27 19:58, robert bristow-johnson wrote:
> >>
> > ...
> >>
> >> Curiously: Where have you seen anyone Q1.31 for a number with 0 whole
> >> bits?
> >
> > i think that's all i ever see.
> >
> > the sign bit is also an integer bit.
>
> In fixed point, 'integer' is confusing (IMO) ... at least for C
> programmers.  The 'whole' part doesn't necessarily include the sign bit.
>
> All (binary) numbers can be expressed as a sum of weighted powers, b2^n,
> where b is the value (0, 1) of the bit, and n is some power of the radix
> (2).
>
> The sign bit, in contrast, I've seen notated as (-1)^b, where b is the
> value (0, 1) of the bit.
>
> In other words, it doesn't have a nice symmetry (between the sign bit
> versus all the other bits), and so I prefer to treat the sign bit as
> separate.  It is rather interesting how the sign bit is duplicated in
> twos-complement, all the way from the top of the word to the most
> significant bit of the value in question.  So, in some respects, the
> sign bit does bleed into a number which had fewer significant bits than
> the word can hold.  But I'm still compelled to treat the sign bit
> separately.  Perhaps I think too much in terms of individual gates
> implementing an arithmetic unit inside a processor.
>
> >>   Apple is the only example I am aware of, but they use "8.24" and
> >> not literally "Q8.24" (I believe they'd be wrong if they used the
> >> latter, since the Q number format is somewhat standardized).
> >
> > it *is*?  (standardized?)  i thought that was what i was complaining
> > about (that it *isn't* standardized).  what did you mean by "Agreed"?
>
> "Agreed" that it would be nice if it got officially and thoroughly
> standardized by everyone involved in the industry, as opposed to
> "somewhat standardized" as I observed.  Basically, usage in the field
> seems to ignore the available standard too frequently.  But I think that
> we have a reasonable, albeit flexible, standard if people would just
> choose to use it.
>
> Some might say Q7.24, some might abbreviate that to Q.24 (with the
> assumption that a 32-bit word with sign bit is a given).  To me, that's
> enough of a standard, either one you choose.  But throwing in 8.24 as a
> synonym starts to allow too much confusion, especially in a field with
> many new members.
>
> > really, the key number to worry about is the number to the *right* of
> > the "." .  so that Apple 8.24 format means that the number represented
> > by that *integer* (all fixed-point numbers ultimately live their lives
> > as integers - it's only in the mind of the programmer that they are
> > not integers) is 2^(-24) times the integer representation.  it makes
> > no difference for addition and subtraction, but when you multiply,
> > then you must realize that your result is 2^24 times too big and, to
> > bring the product back down to the correct scaling, you must shift
> > right by 24 bits.  some hardware does this for you, but i don't think
> > the ARM in an iPod does and i don't think that the C programming
> > language does it for you (until you use the x>>= 24; operation).
>
> Glen beat me to the punch by pointing out that you don't shift by 24
> when working with 8.24 format.
>
> If you multiply two Q.15 numbers, you get a Q.30 number.  If you want to
> maintain the decimal point in the same position relative to the left of
> the word, then you need to shift the result left by one bit, making it
> Q.31 in the final result.  The TMS320 has a FRAC mode bit in its status
> register which will accomplish this left shift in the same cycle as the
> multiplication, but it's turned off by default for the sake of the C
> programmers.
>
> Many seasoned fixed-point programmers will maintain individual
> variables, each with a different decimal place.  Then, the
> multiplications must carefully count the position of the decimal place
> in the result, according to where it is in each multiplicand.

> In fixed point, 'integer' is confusing (IMO) ... at least for C
> programmers.  The 'whole' part doesn't necessarily include
> the sign bit

For C programmers a document worth looking at is
IEC/ISO 18037 Programming languages - C - Extensions to support embedded processors

In this document signed accum and fract types use s in notation for a sign bit and nothing for unsigned fixed point types.

Personally I am in favour of S and Q for singed and unsigned references

Q8.24 and S7.24 for example.

Regards,


w..
--
Walter Banks
Byte Craft Limited
http://www.bytecraft.com

Brian Willoughby <Sound_Consulting-RM-@sounds.wa.com> wrote:

(snip)
> In fixed point, 'integer' is confusing (IMO) ... at least for C 
> programmers.  The 'whole' part doesn't necessarily include the sign bit.
 
> All (binary) numbers can be expressed as a sum of weighted powers, b2^n, 
> where b is the value (0, 1) of the bit, and n is some power of the radix 
> (2).
 
> The sign bit, in contrast, I've seen notated as (-1)^b, where b is the 
> value (0, 1) of the bit.
 
> In other words, it doesn't have a nice symmetry (between the sign bit 
> versus all the other bits), and so I prefer to treat the sign bit as 
> separate.  

For twos-complement the sign bit can be given the -(2**(N-1)) weight,
such that it does (almost) follow the symmetry.  That doesn't quite
work for ones-complement, and not at all for sign-magnitude.

> It is rather interesting how the sign bit is duplicated in 
> twos-complement, all the way from the top of the word to the most 
> significant bit of the value in question.  So, in some respects, the 
> sign bit does bleed into a number which had fewer significant bits than 
> the word can hold.  But I'm still compelled to treat the sign bit 
> separately.  Perhaps I think too much in terms of individual gates 
> implementing an arithmetic unit inside a processor.

-- glen