Post by thread:Almost memoryless average?

I'm trying to figure out how to compute an average of 8 discrete measurements to reduce noise (on a 16C71). The measurements appear to have a gaussian type of distribution, centered around some DC value, with perhaps a 2 bit sigma (noise amplitude). I want that DC value. Average = (X1+X2+X3+X4+X5+X6+X7+X8)/8 But the summation of X1 ... X8 would be possibly greater than eight bits. Here's my situation: I recieve 50 bytes of data, (X1.1 .. X1.50) in the first burst, and store them (in the PICs limited memory). I then recieve another 50 bytes (X2.1 .. X2.50). Eventually I will recieve 8 bursts (up to X8.1 .. X8.50). I want to average X1.1, X2.1, ... X8.1, and so on. Is there any way to do this without losing precision? There is time between XA.N and XA.N+1 to do some calculations. This can be done with just 2 samples (X1.1+X2.1)/2 (utilizing the carry generated with the add, and keeping the result in 8 bits) I'm wondering if there is any way to extrapolate this method into a greater number of samples. Doing the division (right shift) before the add won't help- since that would serve to eliminate immediately the small variations I'm trying to compensate for. This message is not really as clear as I would like it to be, but I don't see any way to explain it better without a white board in front of me. I hope I've gotten the point across adequately. Matt Bennett -- Matt Bennett spam_OUTmjbTakeThisOuTarlut.utexas.edu

If you are willing to assume that over the emsemble of samples the probability of (some order of ) low order bits being 1 or 0 is just 0.5:. i.e b0 = 1 with prob. 0.5, b1=1..etc.... bn=......., then just throw them away "up front" and add the "average" value of that backin at the end. In some definition thats what some flavor of 'random' means; i.e. sample value = average + 'uniformly numerically distributed' random variable (of size = 0.5 of 'lopped ' bitfield). This distrubution isn't gaussian, approximates it with 'box' with center (average) in the right place. This "is not really as clear as I would like it to be," but you should see it. I don't think there is another 'cheap trick' which doesn't require some 'extra' temp storage.

Forget averaging. You'll constantly run into problems with 8 bit math, problems with what I might call windup, errors due to truncation of floating point part of your result (since you can't do floating point math in any practical way) etc. etc. etc. I've got an explanation on my web page (and it's been talked to death here) about median filtering. Median filtering involves no math, just sorting. You'll get a better picture of a noisy value with a median filter than an average, especially when the noise is not gaussian (which may not apply to you..) Try these numbers: 5 7 8 8 8 8 9 9 Average is 7.75, which the PIC truncates to 7, median is 8. Do a lot of crazy math to adjust the 8 bit math, or just sort 8 values. Which is easier? Which is more accurate? Median filters work, generally like this: Clear out a section of RAM to zero. Take N readings, and as you take them sort them into the array of RAM so the array appears in sorted order. Pick the n/2'th value as your median. Clear the RAM again and start over. I often use up to 16 readings, although as few as 5 might give useful data. You can get a working routine from my page and pick it apart. Best Regards Lawrence Lile >> AutoCad Blocks for electronics >>PIC stuff incl median filters >> PEN PLOTTER to PC board conversion >> Amateurish pictures of me and my bicycles HTTP://home1.gte.net/llile/ {Original Message removed}

At 03:20 PM 4/26/99 , William Henning wrote: >Simplest solution: > >Use 100 bytes, two bytes per sample; accumulate to a 16 bit value then shift right three times to divide by eight at the end. Easy to code if you have 50 regs available. I think this is about the only way (for the speed I'm looking for). I *was* planning on using the 16C71, but my memory has been clouded by using the 16F84, which has ~twice the ram of the 16C71. *doh* I guess that means I'm using the 16C715, with 2K of program and 128 bytes of RAM. The median method Lawrence Lile suggests won't reduce gaussian noise with any predictablility that I can see, and it would use far too much ram. There is an equation, which I cannot remember, that specifies the dB gain for averaging. The gain goes up sharply for the first few iterations, but it quickly levels out. I don't know how to compute the S/N (necessary in this situation) for the median method. I guess in this situation, like life, TANSTAAFL. Matt -- Matt Bennett .....mjbKILLspam@spam@arlut.utexas.edu

Matt Bennett wrote: {Quote hidden}> > I'm trying to figure out how to compute an average of 8 discrete > measurements to reduce noise (on a 16C71). The measurements appear to > have a gaussian type of distribution, centered around some DC value, with > perhaps a 2 bit sigma (noise amplitude). I want that DC value. > > Average = (X1+X2+X3+X4+X5+X6+X7+X8)/8 But the summation of X1 ... X8 would > be possibly greater than eight bits. > > Here's my situation: I recieve 50 bytes of data, (X1.1 .. X1.50) in the > first burst, and store them (in the PICs limited memory). I then recieve > another 50 bytes (X2.1 .. X2.50). Eventually I will recieve 8 bursts (up > to X8.1 .. X8.50). I want to average X1.1, X2.1, ... X8.1, and so on. Is > there any way to do this without losing precision? There is time between > XA.N and XA.N+1 to do some calculations. > > This can be done with just 2 samples (X1.1+X2.1)/2 (utilizing the carry > generated with the add, and keeping the result in 8 bits) I'm wondering if > there is any way to extrapolate this method into a greater number of > samples. If You just can't save 8 apples in your pockets for later selection of which one is the average size, the best is just slice one apple at time in 8 pieces of same size and save one piece of each apple. After you do it with the 8 apples, you would have a whole apple, composed by different slices sizes, but it would correspond exactly to the average apple size and weight. Of course, digital information requires enough bits for precision, in your case of only one byte per apple times 8 apples, it means a resolution of 256/8 = 32. The said lack of resolution dividing 15 / 4 = 3.75, so digital loses the .75 and it results in 3 is true but with a bit of imagination it is fixed to 4: When shifting right 15 (0000 1111) turns to 7 (0000 0111), forget this first carry bit, shifting again to end the division by 4, it results in (0000 0011) with the last bit carried out, that means at least a half bit, so reintegrate it in the calculation as a rounding to one, the 3 turns to be 4 (0000 0100). Another example, dividing 77 / 4 = 19.25, so shifting 77 [4Dh] (0100 1101) right once it goes to (0010 0110) forget this carry bit, shifting right again, results in (0001 0011) without a carry bit, it results in 13h, or 19. The carry bit from the last division, or shift right, would means a half bit, that means the decimal 0.5, it could be "added" as value 01h to the actual result, as a rounding up number, so results 7.5 to 7.999 would be 8, while 7.0 up to 7.499999 would be to 7.0 The apples slices example only works if you know exactly how many apples you would sample, so you would cut the apples by this same quantity of slices. The sort technique already suggested needs memory space (pockets) to store all the apples and then choose the average. There is no magic, just divide each sample value by 8 and add with the stored correspondent n.1, n.2 and so on. Precision error examples: 59 59 59 59 60 60 60 60 add values 7 7 7 7 8 8 8 8 = 60, error of 0.83% (round up). 59 59 59 59 59 59 59 59 add values 7 7 7 7 7 7 7 7 = 56, error of 5% 60 60 60 60 60 60 60 60 add values 8 8 8 8 8 8 8 8 = 64, error of 6.66% There is no magic, it is a storage limitation problem... go for a bigger internal RAM chip... :) Wagner

On Mon, 26 Apr 1999, Matt Bennett wrote: > I'm trying to figure out how to compute an average of 8 discrete > measurements to reduce noise (on a 16C71). The measurements appear to > have a gaussian type of distribution, centered around some DC value, with > perhaps a 2 bit sigma (noise amplitude). I want that DC value. > > Average = (X1+X2+X3+X4+X5+X6+X7+X8)/8 But the summation of X1 ... X8 would > be possibly greater than eight bits. > > Here's my situation: I recieve 50 bytes of data, (X1.1 .. X1.50) in the > first burst, and store them (in the PICs limited memory). I then recieve > another 50 bytes (X2.1 .. X2.50). Eventually I will recieve 8 bursts (up > to X8.1 .. X8.50). I want to average X1.1, X2.1, ... X8.1, and so on. Is > there any way to do this without losing precision? There is time between > XA.N and XA.N+1 to do some calculations. How do you squeeze 50 bytes into a c71 that has only 36 registers? Perhaps you mean the c74? Well in any case, you may wish to consider arranging your data vertically and adding 3 more bits of resolution. As an example, suppose you have 8 data samples that require 11 bits each, you really only need 88 bits to store the information. However, if you use the pic's registers 'horizontally' - or the way you normally view them - then you would require 2 bytes per sample or 16*8=128 bits to store the information. Of course, 40 of those bits are wasted... Now in your case, if you wish to extend the data's dynamic range by three more bits you'll need (50 samples) * (11bits/sample) = 550 bits. The first 48 samples can be grouped together in sets of 8 each and would require 528 bits or 66 bytes. The last 2 samples would be grouped together and would require an additional 11 bytes if they were vertical. However, it would make sense to keep these horizontal and use only 4 bytes. So in all you'd require about 72 bytes and have about 11-bits dynamic range. Or if you didn't mind 77 bytes, you could accomodate 54 samples. Here's an example of a vertical adder. http://www.interstice.com/~sdattalo/technical/software/pic/vertical_adder.asm However, it's a slug compared to Dmitry's 6-cycle solution that does the same thing. I'm fairly certain that's as fast as it can be done. Check out for the reason why: www.interstice.com/~sdattalo/va_optimizer.c http://www.interstice.com/~sdattalo/va_optimizer2.c {Quote hidden}> > This can be done with just 2 samples (X1.1+X2.1)/2 (utilizing the carry > generated with the add, and keeping the result in 8 bits) I'm wondering if > there is any way to extrapolate this method into a greater number of > samples. > > Doing the division (right shift) before the add won't help- since that > would serve to eliminate immediately the small variations I'm trying to > compensate for. > > This message is not really as clear as I would like it to be, but I don't > see any way to explain it better without a white board in front of me. I > hope I've gotten the point across adequately. > > Matt Bennett > > -- > Matt Bennett > mjbKILLspamarlut.utexas.edu >

Egads! You are right - it has dissappeared! I'll fix it sometime today. Sorry! -----Original Message----- From: .....ulcsaKILLspam.....eskimo.com <EraseMEulcsaspam_OUTTakeThisOuTeskimo.com> To: lilelspam_OUTtoastmaster.com <@spam@lilelKILLspamtoastmaster.com> Date: Monday, April 26, 1999 5:04 PM Subject: Re: Almost memoryless average? Hi. Could you be a bit more specific about *where* on your web page this can be found? I was just there, but couldn't spot it. Thanks... Brian Aase > I've got an explanation on my web page (and it's been talked to death here) > about median filtering. Median filtering involves no math, just sorting. > You'll get a better picture of a noisy value with a median filter than an > average, especially when the noise is not gaussian (which may not apply to > you..) > You can get a working routine from my page and pick it apart.

Matt Bennet wrote: > Average = (X1+X2+X3+X4+X5+X6+X7+X8)/8 But the summation of X1 ... X8 > would be possibly greater than eight bits. > > This can be done with just 2 samples (X1.1+X2.1)/2 (utilizing the > carry generated with the add, and keeping the result in 8 bits) > I'm wondering if there is any way to extrapolate this method into > a greater number of samples. > > Doing the division (right shift) before the add won't help- since > that would serve to eliminate immediately the small variations I'm > trying to compensate for. You can write the above formula as Av=X1/8+X2/8+X3/8+X4/8+X5/8+X6/8+X7/8+X8/8 This should be equal to Av=(((X1+X2)/2+(X3+X4)/2)/2+((X5+X6)/2+(X7+X8)/2)/2)/2 So you can extend your method of averaging two values repeating the operation "grouping" the intermediate results. I'll try to PIC this (not tested at all): movf X2 addwf X1, F rrf X1, F ; X1=(X1+X2)/2 movf X4 addwf X3, F rrf X3, F ; X3=(X3+X4)/2 movf X6 addwf X5, F rrf X5, F ; X5=(X5+X6)/2 movf X8 addwf X7, F rrf X7, F ; X7=(X7+X8)/2 movf X3 addwf X1, F rrf X1, F ; X1=((X1+X2)/2+(X3+X4)/2)/2 movf X7 addwf X5, F rrf X5, F ; X5=((X5+X6)/2+(X7+X8)/2)/2 movf X5 addwf X1, F rrf X1, F ; X1=(((X1+X2)/2+(X3+X4)/2)/2+ ; ((X5+X6)/2+(X7+X8)/2)/2)/2 Since you always add two 8bit values at time having a 9bit result (file register + carry bit) that is divided by two using right shifts you never lose significance in the addition. You pay this with 7 shift operation instead of the 3 you would need for a divide-by-8 operation. > This message is not really as clear as I would like it to be, but I > don't see any way to explain it better without a white board in > front of me. I hope I've gotten the point across adequately. I hope my reply is at least as clear as your message :-). Ciao Marco ------ Marco DI LEO KILLspamm.dileoKILLspambigfoot.com http://members.tripod.com/~mdileo/

|Well in any case, you may wish to consider arranging your data vertically |and adding 3 more bits of resolution |Now in your case, if you wish to extend the data's dynamic range by three |more bits you'll need (50 samples) * (11bits/sample) = 550 bits. The first |48 samples can be grouped together in sets of 8 each and would require 528 |bits or 66 bytes. The last 2 samples would be grouped together and would |require an additional 11 bytes if they were vertical. However, it would |make sense to keep these horizontal and use only 4 bytes. I think a slightly easier approach would be to keep the bottom 8 bits of each 11-bit total in "horizontal" format and just put the top 3 bits in vertical format, at least for the first 48 of them. The two oddballs you could store horizontally, optionally packing them both into a byte. This would yield a total of 48 bytes for storing LSB's and 18 bytes for storing 48 sets of MSB's, plus one for the oddballs; total 67. Note that your "vertical" math now only needs to be an increment-if-carry, rather than an add. Another method, somewhat alluded to above, would be to store MSB's horizontally, but packed two per byte. This would need a total of 75 bytes; more than the above, but less than 100.

Hi, I guess you *can* do the right shifting 3 times before addition, if you save the shifted-out values also (it is the modulus by division with 8). They can be also cumulated such way as the originals and at the end shift right 3 times also right and the result is to be added to the sum of the previous data. It requires only one more RAM cell. I hope this helps. Imre P.S: Here also an example Original DIV by 8 Remainder 123 15 3 45 5 5 66 8 2 23 2 7 12 1 4 36 4 4 82 10 2 1 0 1 ---------------------------------- 388 45 28 SUM 48.5 45 3.5 AVG On Mon, 26 Apr 1999, Matt Bennett wrote: {Quote hidden}> I'm trying to figure out how to compute an average of 8 discrete > measurements to reduce noise (on a 16C71). The measurements appear to > have a gaussian type of distribution, centered around some DC value, with > perhaps a 2 bit sigma (noise amplitude). I want that DC value. > > Average = (X1+X2+X3+X4+X5+X6+X7+X8)/8 But the summation of X1 ... X8 would > be possibly greater than eight bits. > > Here's my situation: I recieve 50 bytes of data, (X1.1 .. X1.50) in the > first burst, and store them (in the PICs limited memory). I then recieve > another 50 bytes (X2.1 .. X2.50). Eventually I will recieve 8 bursts (up > to X8.1 .. X8.50). I want to average X1.1, X2.1, ... X8.1, and so on. Is > there any way to do this without losing precision? There is time between > XA.N and XA.N+1 to do some calculations. > > This can be done with just 2 samples (X1.1+X2.1)/2 (utilizing the carry > generated with the add, and keeping the result in 8 bits) I'm wondering if > there is any way to extrapolate this method into a greater number of > samples. > > Doing the division (right shift) before the add won't help- since that > would serve to eliminate immediately the small variations I'm trying to > compensate for. > > This message is not really as clear as I would like it to be, but I don't > see any way to explain it better without a white board in front of me. I > hope I've gotten the point across adequately. > > Matt Bennett > > -- > Matt Bennett > RemoveMEmjbTakeThisOuTarlut.utexas.edu > >

>On Mon, 26 Apr 1999, Matt Bennett wrote: > >> I'm trying to figure out how to compute an average of 8 discrete >> measurements to reduce noise (on a 16C71). The measurements appear to >> have a gaussian type of distribution, centered around some DC value, with >> perhaps a 2 bit sigma (noise amplitude). I want that DC value. >> <snip> >> Matt Bennett >> Hi Matt, Here is a different approach. Whay about averaging the first derivative, since the noise is only 2 bits or so. Then all you need is to average the difference between samples. Also if a lot of the 50 samples are always close together you could just keep some value and then store the differences from that value. Ray Gardiner spamBeGonerayspamBeGonehdc.com.au

Hi, it is a nice approach. However, one must keep in mind doing *signed* arithmetics, which is not inherently supported by PIC... Imre On Thu, 29 Apr 1999, Ray Gardiner wrote: {Quote hidden}> >On Mon, 26 Apr 1999, Matt Bennett wrote: > > > >> I'm trying to figure out how to compute an average of 8 discrete > >> measurements to reduce noise (on a 16C71). The measurements appear to > >> have a gaussian type of distribution, centered around some DC value, with > >> perhaps a 2 bit sigma (noise amplitude). I want that DC value. > >> > <snip> > >> Matt Bennett > >> > > Hi Matt, > > Here is a different approach. > > Whay about averaging the first derivative, since the noise is only > 2 bits or so. Then all you need is to average the difference between > samples. > > Also if a lot of the 50 samples are always close together you could > just keep some value and then store the differences from that value. > > > Ray Gardiner TakeThisOuTrayEraseMEspam_OUThdc.com.au > >