Searching \ for 'Almost memoryless average?' in subject line. () Help us get a faster server
FAQ page: techref.massmind.org/techref/mems.htm?key=memory
Search entire site for: 'Almost memoryless average?'.

Truncated match.
'Almost memoryless average?'
1999\04\26@153345 by  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
mjb arlut.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
>>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
mjb arlut.utexas.edu  Matt Bennett wrote:
{Quote hidden}

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.

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}  >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

I like it--brute force has an elegance all its own.

newell  Egads! You are right - it has dissappeared!   I'll fix it sometime today.
Sorry!

-----Original Message-----
From: ulcsa eskimo.com <ulcsa eskimo.com>
To: lilel toastmaster.com <lilel toastmaster.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
rrf     X1, F   ; X1=(X1+X2)/2
movf    X4
rrf     X3, F   ; X3=(X3+X4)/2
movf    X6
rrf     X5, F   ; X5=(X5+X6)/2
movf    X8
rrf     X7, F   ; X7=(X7+X8)/2

movf    X3
rrf     X1, F   ; X1=((X1+X2)/2+(X3+X4)/2)/2
movf    X7
rrf     X5, F   ; X5=((X5+X6)/2+(X7+X8)/2)/2

movf    X5
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
m.dileo bigfoot.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,

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}  >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 ray hdc.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}

More... (looser matching)
- Last day of these posts
- In 1999 , 2000 only
- Today
- New search...