Truncated match.
PICList
Thread
'Almost memoryless average?'
1999\04\26@153345
by
Matt Bennett

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
1999\04\26@155911
by
Richard Martin
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.
1999\04\26@160308
by
Lawrence Lile

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}
1999\04\26@165845
by
Matt Bennett

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
1999\04\26@173811
by
wagnerl

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
1999\04\26@210915
by
Scott Dattalo

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 11bits 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 6cycle 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
>
1999\04\27@002907
by
Scott Newell
>However, it's a slug compared to Dmitry's 6cycle 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
I like itbrute force has an elegance all its own.
newell
1999\04\27@110012
by
Lawrence Lile
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.
1999\04\27@112700
by
Marco DI LEO

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 divideby8 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/
1999\04\27@151915
by
John Payson

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 11bit 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 incrementifcarry,
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.
1999\04\28@042002
by
Dr. Imre Bartfai

Hi,
I guess you *can* do the right shifting 3 times before addition, if you
save the shiftedout 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
>
>
1999\04\28@143213
by
Ray Gardiner
>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
1999\04\29@021110
by
Dr. Imre Bartfai

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
>
>
More... (looser matching)
 Last day of these posts
 In 1999
, 2000 only
 Today
 New search...