Jerry Avins <jya@ieee.org> wrote:> I don't know what you mean by the sign bit "bleeding down" in > two's complement.I believe it is a different way of looking at the usual twos-complement sign extension. (The MC6809 is the only one I know that does sign extension with the SEX instruction.)> 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.Last I knew were the IBM series machines related to the 7090.> 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.There is also ones-complement, which CDC machines used, and, as I understand it, Unisys machines still do. Ones complement has a slightly more interesting wrap-around, where a carry out from the sign bit generates a carry-in to the ones digit. Fortran and C both allow for twos-complement, ones-complement, and sign-magnitude representation. (But not the offset form.) C requires a binary representation (or at least it has to look like that to the programmer.) Fortran allows any base greater than one. -- glen
IIR implementation on ARM
Started by ●March 9, 2011
Reply by ●March 29, 20112011-03-29
Reply by ●March 29, 20112011-03-29
On Mar 29, 1:58�pm, Walter Banks <wal...@bytecraft.com> wrote: ...> > Personally I am in favour of S and Q for signed and unsigned references > > Q8.24 and S7.24 for example. >this was precisely what i was referring to. the "Q" does not occupy a bit, but the "S" does. but i've seen the Q format used for signed also. it might be a bad usage of the terminology, such as it is. r b-j
Reply by ●March 30, 20112011-03-30
On Mar 29, 7:23�am, Brian Willoughby <Sound_Consulting-...@Sounds.wa.com> 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.if you want to avoid confusion, you should view this as it was (or should have been) first taught to you in college. (because of stupid HTML characters view, using Google, in "Fixed font"). so first: Unsigned N-bit two's complement integer: N-1 X_u = SUM{ x_n * 2^n } n=0 where x_n is of the set {0, 1} 0 <= X_u < 2^N then second: Signed N-bit two's complement integer: N-2 X_s = x_(N-1) * -2^(N-1) + SUM{ x_n * 2^n } n=0 where x_n is of the set {0, 1} -2^(N-1) <= X_s < 2^(N-1) now, if the bits, x_n, are the same in both cases, you can see that X_s = X_u + x_(N-1) * -2^N so, if you look at these N-bit numbers in as a circular ring (sorta like the DFT bins in our bloody argument of a month ago) where, just like an odometer, the zero value (0000) comes right after the value with all 1s (1111), this circular ring is exactly the same for signed and unsigned (which is why addition and subtraction is done exactly the same, sign bit and all). here, i'll try to draw it: for N=4: 0000 1111 0001 1110 0010 1101 0011 1100 0100 1011 0101 1010 0110 1001 0111 1000 for these 4-bit two's comp numbers, there is NO difference between what this circle is for signed or for unsigned numbers. adding 3 will move you clockwise 3 places and subtracting 2 will move you counter- clockwise 2 places. the *only* difference is interpretation and where you put the overflow boundary at. for unsigned numbers, the overflow boundary is between 1111 and 0000. for signed numbers, it's at the opposite side of the circle, between 0111 and 1000.> In other words, it doesn't have a nice symmetry (between the sign bit > versus all the other bits),dunno about "symmetry" but there *is* a very compact expression about what the sign bit does. the only thing different is the sign of the weighting value applied to that bit. for unsigned, the weight is 2^(N-1) and for signed it's -2^(N-1)> and so I prefer to treat the sign bit as separate.but it's the wrong way to look at it.> �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.and it's still is the wrong way to look at it, if you're doing two's complement. for signed-magnitude representation (like IEEE floating point), *then* you deal with the sign bit differently.> �Perhaps I think too much in terms of individual gates > implementing an arithmetic unit inside a processor.even so, for two's comp, you're dealing with the sign bit wrong. it is either weighted by the same weighting factor as for unsigned (but with a negative sign) *or* you can treat your signed value exactly like the unsigned, but with -2^N added when the sign bit is set (that's one extra role for the bit). that -2^N spins you around the circle to the very same position in the circle that you were before, so the bits are exactly the same and the addition and subtraction operators are exactly the same. it's just that the meaning is different by a 2^N term.> >> � 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.it's hardly standardized at all. that's the problem.> �Basically, usage in the field > seems to ignore the available standard too frequently.the "available standard" is *what*, exactly?> �But I think that > we have a reasonable, albeit flexible, standard if people would just > choose to use it."it" is *what*, exactly.> > > 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.well, Glen is either wrong (which he's not) or was talking about something a little different (which he was). when you cast your multiplication product of two Qm.n ("m" integer bits and "n" fractional bits) *back* into another Qm.n number, you must arithmetically shift the double-wide product to the right by n bits to scale it back correctly. this is the case regardless of whether your Qm.n is signed or unsigned. what you do with the bits that fall off the edge is a rounding or quantization issue. a whole 'nother topic.> 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,but you *don't* do that if you cast back to a 16-bit word. how is your 32-bit fractional number going to be viewed as a regular 16-bit fractional number again?> then you need to shift the result left by one bit, making it > Q.31 in the final result.and then you take your 16-bit value out of the high-order word, which is the same as shifting right by 16 bits (16 bits right after 1 bit left is 15 bits to the right). now, how are you gonna code that in C, *not* assembly?> �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.well, that's an assembly thing. i can do assembly too, but C doesn't do fractional, fixed-point math without an extension to the language. so, if you're coding your ARM in C, how are you gonna do it?> Many seasoned fixed-point programmers will maintain individual > variables, each with a different decimal place.you can do that, if you keep your ducks in a row.> �Then, the > multiplications must carefully count the position of the decimal place > in the result, according to where it is in each multiplicand.and, when you do your fixed-point multiplication with an integer machine, the bits to count are the ones on the *right* of the binary point. that's what you have to keep track of to keep your scaling correct. r b-j
Reply by ●March 30, 20112011-03-30
On Tuesday, March 29, 2011 3:10:42 PM UTC-4, glen herrmannsfeldt wrote:> Jerry Avins <j...@ieee.org> wrote: > > > I don't know what you mean by the sign bit "bleeding down" in > > two's complement. > > I believe it is a different way of looking at the usual > twos-complement sign extension. (The MC6809 is the only one I > know that does sign extension with the SEX instruction.) > > > 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 may still be signed-binary integer machines, but I > > know of none. Unsigned and two's complement are the other two. > > Last I knew were the IBM series machines related to the 7090. > > > Offset binary, two's complement, and unsigned all wrap around. > > The complete set of any one is known 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. > > There is also ones-complement, which CDC machines used, and, as > I understand it, Unisys machines still do. Ones complement has > a slightly more interesting wrap-around, where a carry out from > the sign bit generates a carry-in to the ones digit.I just forgot about one's complement. (Suppressed the trauma?)> Fortran and C both allow for twos-complement, ones-complement, > and sign-magnitude representation. (But not the offset form.)Forth, too.> C requires a binary representation (or at least it has to look > like that to the programmer.) Fortran allows any base greater > than one. > > -- glen
Reply by ●March 30, 20112011-03-30
On 2011/03/29 12:10, glen herrmannsfeldt wrote:> Jerry Avins<jya@ieee.org> wrote: > >> I don't know what you mean by the sign bit "bleeding down" in >> two's complement. > > I believe it is a different way of looking at the usual > twos-complement sign extension. (The MC6809 is the only one I > know that does sign extension with the SEX instruction.)What I was referring to can be explained as follows: When examining a positive number where there are fewer significant bits than the word size will hold, you can clearly see that there are leading zeroes until the first most significant bit. This corresponds intuitively to the pencil and paper world where we can see the (lack of) effect of leading zeroes on decimal numbers. When examining a negative two's complement number with fewer significant bits than the word size will hold, you instead see leading ones instead of leading zeroes. Those ones are not significant, and I referred to that situation as the sign bit "bleeding down" into the other bits. Pencil and paper decimal math has no corollary, because you don't write nines in front of negative numbers and treat them like leading zeroes. I am glossing over the differences between two's complement and the written decimal form that has an explicit symbol for the sign of a number. Brian Willoughby Sound Consulting
Reply by ●March 30, 20112011-03-30
On 2011/03/29 20:03, robert bristow-johnson wrote:> On Mar 29, 7:23 am, Brian Willoughby <Sound_Consulting-...@Sounds.wa.com> 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: >> >>> ... >> >> In other words, it doesn't have a nice symmetry (between the sign bit >> versus all the other bits), > > dunno about "symmetry" but there *is* a very compact expression about > what the sign bit does. the only thing different is the sign of the > weighting value applied to that bit. for unsigned, the weight is > 2^(N-1) and for signed it's -2^(N-1) > >> and so I prefer to treat the sign bit as separate. > > but it's the wrong way to look at it. > >> 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. > > and it's still is the wrong way to look at it, if you're doing two's > complement. for signed-magnitude representation (like IEEE floating > point), *then* you deal with the sign bit differently.I would suggest that your semantics are slightly off. Signed-magnitude deals with the sign bit completely separately, not just differently. As you explained, two's complement and related formats deal with the sign bit along with the other bits, but it's still just a little different. In other words, you make a good argument that the sign bit is not completely independent, but I don't think you can be convincing that the sign bit is not at least a little different in some situations, even if only when interpreting carry and overflow. Also, your SUMmations clearly treat the sign bit differently in the unsigned and signed cases. So, I'll agree that the sign bit is mostly the same as the other bits, but not without specific differences, and certainly not as completely independent as sign-magnitude.>>>> 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. > > it's hardly standardized at all. that's the problem. > >> Basically, usage in the field >> seems to ignore the available standard too frequently. > > the "available standard" is *what*, exactly?My reading of Wikipedia under "Q (number format)" shows it to be a perfectly serviceable standard, and certainly readily available. At least nothing that I read there is contradictory to what I've learned in the past or (more importantly) contrary to logic.>> But I think that >> we have a reasonable, albeit flexible, standard if people would just >> choose to use it. > > "it" is *what*, exactly.I will admit that I have surveyed perhaps too small of a subset of the industry, but between Texas Instruments' documents and Wikipedia I don't see why people have such a problem. There's a little leeway allowed in their descriptions, but they're the "it" I was referring to. (Yes, it would be better to have an ISO document that cannot be edited at any moment like Wikipedia, and is not as hard to find as Texas Instruments' documentation)>>> 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. > > well, Glen is either wrong (which he's not) or was talking about > something a little different (which he was).What Glen wrote was to reiterate the basic schoolkid teaching that multiplication of two numbers with decimal places requires you to add the digits of both multiplicands in order to determine the correct placement of the decimal point in the result. So, for 24 fractional bits on each input, the result ends up with 48 fractional bits. But the rules allows for multiplicands that do not match each other in their number of fractional bits, and thus the answer still isn't going to be 24 out for 24 in except for a few cases.> when you cast your multiplication product of two Qm.n ("m" integer > bits and "n" fractional bits) *back* into another Qm.n number, you > must arithmetically shift the double-wide product to the right by n > bits to scale it back correctly. this is the case regardless of > whether your Qm.n is signed or unsigned. > > what you do with the bits that fall off the edge is a rounding or > quantization issue. a whole 'nother topic. > >> 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, > > but you *don't* do that if you cast back to a 16-bit word. how is > your 32-bit fractional number going to be viewed as a regular 16-bit > fractional number again?It depends upon the implementation of your processor. DSP chips typically have something like a 40-bit accumulator which is constantly being used to read and write smaller depths like 32-bit, 16-bit, or 8-bit. In that case, if the only available 16-bit operation looks at the correct 16 bits, then you don't have to "do" anything to "cast" back to a 16-bit word. But I am getting off the topic of "ARM" by referring to DSP. I am not yet familiar with the DSP extensions to the ARM instruction set, so I have no idea what sort of casting may or may not be needed.>> then you need to shift the result left by one bit, making it >> Q.31 in the final result. > > and then you take your 16-bit value out of the high-order word, which > is the same as shifting right by 16 bits (16 bits right after 1 bit > left is 15 bits to the right). now, how are you gonna code that in C, > *not* assembly?Personally, I don't have a problem coding ARM in assembly, so I don't understand the point of your question.>> 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. > > well, that's an assembly thing. i can do assembly too, but C doesn't > do fractional, fixed-point math without an extension to the language. > so, if you're coding your ARM in C, how are you gonna do it?Ditto my comments about TI DSP being off-topic and ARM in assembly being trivial, so why C? I'm sure it's inappropriate for me to go into detail about the TMS320, but the OP opened this topic with discussions of assembly instructions, so I don't think we're limited to C language answers.>> Many seasoned fixed-point programmers will maintain individual >> variables, each with a different decimal place. > > you can do that, if you keep your ducks in a row.Fortunately, Apple's sample iOS code even shows an example of how to do this, with half way decent comments, too. I recall that they mix C language and assembly intrinsic macros.>> Then, the >> multiplications must carefully count the position of the decimal place >> in the result, according to where it is in each multiplicand. > > and, when you do your fixed-point multiplication with an integer > machine, the bits to count are the ones on the *right* of the binary > point. that's what you have to keep track of to keep your scaling > correct.Isn't that what I said? Q.15 x Q.15 := Q.30 Brian Willoughby Sound Consulting
Reply by ●March 30, 20112011-03-30
On 03/29/2011 11:03 PM, robert bristow-johnson wrote:> so, if you look at these N-bit numbers in as a circular ring (sorta > like the DFT bins in our bloody argument of a month ago) where, just > like an odometer, the zero value (0000) comes right after the value > with all 1s (1111), this circular ring is exactly the same for signed > and unsigned (which is why addition and subtraction is done exactly > the same, sign bit and all). here, i'll try to draw it: > > for N=4: > > 0000 > 1111 0001 > 1110 0010 > 1101 0011 > 1100 0100 > 1011 0101 > 1010 0110 > 1001 0111 > 1000 > > > for these 4-bit two's comp numbers, there is NO difference between > what this circle is for signed or for unsigned numbers. adding 3 will > move you clockwise 3 places and subtracting 2 will move you counter- > clockwise 2 places.This description is actually pretty close to the way ENIAC actually worked, except that it worked in base 10 (really!). Each base-ten digit was represented by a ring of ten tubes. One of those tubes held a logical high, and all the rest were low (or maybe the reverse, I forget). To add 5, they would just shift the ring clockwise. When it crossed from 9 to 0, it would clock the digit to the left. Here's a link to the book I read this in: http://www.amazon.com/ENIAC-Triumphs-Tragedies-Worlds-Computer/dp/0425176444/ref=sr_1_1?ie=UTF8&qid=1301510086&sr=8-1 -- Jim Thomas Principal Applications Engineer Bittware, Inc jthomas@bittware.com http://www.bittware.com (603) 226-0404 x536 Visualize whirled peas.
Reply by ●March 30, 20112011-03-30
On Wednesday, March 30, 2011 12:05:47 AM UTC-4, Brian Willoughby wrote:> On 2011/03/29 12:10, glen herrmannsfeldt wrote: > > Jerry Avins<j...@ieee.org> wrote: > > > >> I don't know what you mean by the sign bit "bleeding down" in > >> two's complement. > > > > I believe it is a different way of looking at the usual > > twos-complement sign extension. (The MC6809 is the only one I > > know that does sign extension with the SEX instruction.) > > What I was referring to can be explained as follows: When examining a > positive number where there are fewer significant bits than the word > size will hold, you can clearly see that there are leading zeroes until > the first most significant bit.I see leading sign bits.> This corresponds intuitively to the > pencil and paper world where we can see the (lack of) effect of leading > zeroes on decimal numbers. When examining a negative two's complement > number with fewer significant bits than the word size will hold, you > instead see leading ones instead of leading zeroes.I see leading sign bits.> Those ones are not > significant, and I referred to that situation as the sign bit "bleeding > down" into the other bits. Pencil and paper decimal math has no > corollary, because you don't write nines in front of negative numbers > and treat them like leading zeroes. I am glossing over the differences > between two's complement and the written decimal form that has an > explicit symbol for the sign of a number.That difference lies at the root of the matter. You can do ten's complement with pencil and paper, but as with binary, you need a beforehand choice of the number of digits. Try it. It might be enlightening. Jerry -- Engineering is the art of making what you want from things you can get.
Reply by ●March 30, 20112011-03-30
Jim Thomas <jthomas@bittware.com> wrote: (snip)>> for these 4-bit two's comp numbers, there is NO difference between >> what this circle is for signed or for unsigned numbers. adding 3 will >> move you clockwise 3 places and subtracting 2 will move you counter- >> clockwise 2 places.> This description is actually pretty close to the way ENIAC actually > worked, except that it worked in base 10 (really!).> Each base-ten digit was represented by a ring of ten tubes. One of > those tubes held a logical high, and all the rest were low (or maybe the > reverse, I forget). To add 5, they would just shift the ring clockwise. > When it crossed from 9 to 0, it would clock the digit to the left.(snip) Before EINIAC, mechanical calculators with decimal wheels were very popular. (Very much like a mechanical odometer.) The logic was then ported to vacuum tubes. It took some time for the idea of binary arithmetic, and the ability to use it, and convert to/from decimal, to sink in. -- glen
Reply by ●March 31, 20112011-03-31
On Mar 30, 10:06=A0pm, glen herrmannsfeldt <g...@ugcs.caltech.edu> wrote:> Jim Thomas <jtho...@bittware.com> wrote: > > (snip) > > >> for these 4-bit two's comp numbers, there is NO difference between > >> what this circle is for signed or for unsigned numbers. =A0adding 3 wi=ll> >> move you clockwise 3 places and subtracting 2 will move you counter- > >> clockwise 2 places. > > This description is actually pretty close to the way ENIAC actually > > worked, except that it worked in base 10 (really!). > > Each base-ten digit was represented by a ring of ten tubes. =A0One of > > those tubes held a logical high, and all the rest were low (or maybe th=e> > reverse, I forget). =A0To add 5, they would just shift the ring clockwi=se.> > =A0When it crossed from 9 to 0, it would clock the digit to the left. > > (snip) > > Before EINIAC, mechanical calculators with decimal wheels were > very popular.i think they were called "adding machines", no? i remember my parents using this adding machine and cranking out paper tape for all this stuff. i remember negative numbers were printed in red and the ink ribbon had to have two colors (red and black). memory lane. i also remember when i could hear the TV turn on and then 15750 Hz flyback. the TVs were both noisier and my hearing better in them's days. and, i'm sure Jerry, you can outdo me in remembering stuff that i have never seen.> =A0(Very much like a mechanical odometer.) =A0The logic > was then ported to vacuum tubes. =A0It took some time for the idea > of binary arithmetic, and the ability to use it, and convert > to/from decimal, to sink in.and that, to me, seemed like the only way to do things. i never thought that the BCD ADD instructions in the MC6800 were worth a spit. in 1974, i thought the only sensible system, even for a simple embedded system, was to convert decimal to binary upon input and back to decimal upon output. and i had always thought that the "text mode" monitors and printers were useless (just kick it into graphics mode and map the bits to the printer). it wasn't until the Apple Lisa and Mac that i really saw a commercial product line take the same philosophy. r b-j
