Searching \ for 'Averaging Algorithm' in subject line. ()
Make payments with PayPal - it's fast, free and secure! Help us get a faster server
FAQ page: www.piclist.com/techref/index.htm?key=averaging+algorithm
Search entire site for: 'Averaging Algorithm'.

Truncated match.
PICList Thread
'Averaging Algorithm'
1997\09\23@133303 by Lawrence Lile

flavicon
face
Anybody got a good averaging algorithm?

I've got a stream of numbers from 0 to 15 coming out of a PIC '620
comparator representing temperature of an appliance.  When I turn on
the flourescent lamp on my bench, the program picks up a spike, and
the relay in this thing fires momentarily, because it reads the
noise.  "NO PROBLEM" I sez, and sat down to write an averaging
algoritm.

This ought to be so easy.  The first "Algorithm" anybody learns in
kindy-garden Math 1 is how to average numbers.  I've been checking
out verious ways of averaging a stream of data, though, and don't
have one that satisfies on a PIC with Two byte arithmetic and no
floating point math.

Try this.  Make a spreadsheet with 300 or 400 random integers between
0 and 16.  Take the arithmetic average of all of 'em, probably
around 8.   Then try to simulate a PIC program processing each number
in succession that would get near the average, without floating point
math.  I tried a half dozen ways this morning.

One trick I worked out is that the average of N numbers, given the
NTH piece of data is being processed now, is (N-1)*(old average)/N
plus (Nth piece of data)/N.  If you pick 256 data points, given the
old average AVG and the new data point DATA,

NEWAVG = {(AVG*255)+DATA}/256

That oughta work!  Not so fast.  Using only integer values,no
floating point math,  the average climbs slowly toward zero and stays
there.  PICs can probably do floating point math, but there's gotta
be an easier way!


Best Regards,

Lawrence Lile

1997\09\23@135751 by Dave Reinagel

picon face
> Anybody got a good averaging algorithm?
>
> NEWAVG = {(AVG*255)+DATA}/256
>
A better way is to actually keep that sum of the last 256 reading
rather that multiplying the average by 255.  Thus you have

NEWACCUM = (ACCUM - ACCUM/256) + DATA;
AVG = NEWACCUM/256;

Keeping those extra 8 bits around all the time reduces that error
you noticed by your effect truncation of these least significant
8 bits.

Dave Reinagel

1997\09\23@141214 by dieser

flavicon
face
Lawrence Lile wrote:
>
> Anybody got a good averaging algorithm?
>

[snip]

>
> Best Regards,
>
> Lawrence Lile


Lawrence

       Try adding sixteen numbers and then shift right four bits
same effect as averaging the sixteen numbers or for more accurate
averaging add 256 numbers and then shift right by 8 (averaging 256
numbers) --- need to watch for overflowing the accumulator though.

regards Dave

1997\09\23@141223 by Joe Little

flavicon
face
    Anybody got a good averaging algorithm?

    I've got a stream of numbers from 0 to 15 coming out of a PIC '620
    comparator representing temperature of an appliance.


    Snip------------

    (newbee protection on)
    It seems like you could take readings pretty fast, and then save the
    measurement only when 'N' consecutive readings are the same.  This would
    ignore spikes, and still track changes.
    (newbee protection off)

1997\09\23@141427 by bfehrenb
picon face
On 23 Sep 97 at 12:32, Lawrence Lile wrote:


> I've got a stream of numbers from 0 to 15 coming out of a PIC '620
> comparator representing temperature of an appliance.  When I turn on
> the flourescent lamp on my bench, the program picks up a spike, and
> the relay in this thing fires momentarily, because it reads the
> noise.  "NO PROBLEM" I sez, and sat down to write an averaging
> algoritm.
>

Lawrence,
       Are you sure that an averaging algorithm is what you need?
The problem you describe suggests you need a spike filter.

I have had good luck in cases like this by using 'median' filtering.
This consists simply using the middle value of the N most recent
readings. To make things unambiguous, N should be odd.  I usually use
5.

You need to keep a stack of the five most recent readings.  Copy the
stack, sort it and use the middle value.  This tends to throw out
extreme readings which sounds like it might fit your application.

If you want some details, send me a note.
--
Bob Fehrenbach   Wauwatosa, WI  spam_OUTbfehrenbTakeThisOuTspamexecpc.com

1997\09\23@150720 by Paul H. Dietz

flavicon
face
    There is a much better way! It is called a median filter. Basically,
    this is just like a moving average (or more generically, an FIR)
    filter, except that you take the median of the data instead of the
    average. You do this by sorting the data in the window by value,
    and then outputing the value which ends up in the middle.

    Why is this better? Basically, you are trying to remove impulsive
    noise. Any linear filter will have an impulse response. (And averaging
    is just a very simple linear filter.) So from a deep theoretical
    standpoint, it is not possible to create a linear filter where
    the output does not respond in some way, however small. Consider the
    data set 3, 5, 2, 47 and 3. The average is 12. The median is 3.
    (pick the middle 2 3 ->3<- 5 47) We could replace the 47 with
    5,345,356 and the median would still have been 3. The average
    would be over a million. Yuck.

    It sounds like you have a classic median filter problem - a clean
    set of data with occassional noise. If you were trying to get
    rid of Gaussian noise, some sort of averaging would be the best
    choice. But for these long-tailed distributions, some form of
    nonlinear filter is more robust. And the best part is, it requires
    no math other than comparison. Thus, your problem is solved.

    Sort of. If you want to be really efficient, when median filtering
    a data stream people generally maintain a linked list of the
    data, removing expired data, and inserting the new data on the
    fly. That way you don't have to sort the whole list each time.
    Virtually any book on numerical algorithms should discuss this.

    Good luck!

    --- phd

    P.S. Disclaimer - my dissertation was on implementing median filters
    with analog components, so I tend to be a proponent...


______________________________ Reply Separator _________________________________
Subject: Averaging Algorithm
Author:  .....PICLISTKILLspamspam@spam@MITVMA.MIT.EDU at WDI-INTERNET
Date:    9/23/97 10:34 AM


Anybody got a good averaging algorithm?

I've got a stream of numbers from 0 to 15 coming out of a PIC '620
comparator representing temperature of an appliance.  When I turn on
the flourescent lamp on my bench, the program picks up a spike, and
the relay in this thing fires momentarily, because it reads the
noise.  "NO PROBLEM" I sez, and sat down to write an averaging
algoritm.

This ought to be so easy.  The first "Algorithm" anybody learns in
kindy-garden Math 1 is how to average numbers.  I've been checking
out verious ways of averaging a stream of data, though, and don't
have one that satisfies on a PIC with Two byte arithmetic and no
floating point math.

Try this.  Make a spreadsheet with 300 or 400 random integers between
0 and 16.  Take the arithmetic average of all of 'em, probably
around 8.   Then try to simulate a PIC program processing each number
in succession that would get near the average, without floating point
math.  I tried a half dozen ways this morning.

One trick I worked out is that the average of N numbers, given the
NTH piece of data is being processed now, is (N-1)*(old average)/N
plus (Nth piece of data)/N.  If you pick 256 data points, given the
old average AVG and the new data point DATA,

NEWAVG = {(AVG*255)+DATA}/256

That oughta work!  Not so fast.  Using only integer values,no
floating point math,  the average climbs slowly toward zero and stays
there.  PICs can probably do floating point math, but there's gotta
be an easier way!


Best Regards,

Lawrence Lile

1997\09\23@160412 by STEENKAMP [M.ING E&E]

flavicon
picon face
Hi,

I guess keeping the last N values and simply averaging them is out of the
question (uses too much RAM?).

Another approach would be to do the following:
Add the first N samples.  Lets make it 16.  Since your values are all 0
to 15, this sum will fit into a byte - lets call it Sum.
The average at this point is then Avg ~= Sum div 16.  When you receive
the next byte, you calculate your new average by
NewAvg = ((Sum-PrevAvg)+NewSample) div 16.  You simply keep in applying
this formula for each new sample.  The only storage spave you need is
for the Sum.
This is of course not a true average, but it performs a low pass function
on your data and will thus minimize the effect of noise spikes.

Hope this helps.
Niki


{Quote hidden}

1997\09\23@163428 by Craig Niederberger

flavicon
face
Hi Lawrence,

Keep in mind that for a constant window width, an average really isn't all
that different than a sum.  For example, take the series

           sum     average
2, 3, 4      9         3
3, 4, 5      12        4
4, 5, 6      15        5

If, say, you wanted to exclude windows with average > 4, and you knew the
window width was constant at 3, you could simply exclude windows with sum
> 12.  That would save you the computational cost of division.

Cheers,
Craig

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ craignspamKILLspamuic.edu ~~~~~~~~~~~~~~~~~~~~~~~~~
Craig Niederberger MD FACS          | Chief, Division of Andrology
University of Illinois at Chicago   | Director Urologic Basic Research
Department of Urology M/C 958       | 312-996-2779   Fax: 312-996-1291
840 South Wood St, Chicago IL 60612 | http://godot.urol.uic.edu

On Tue, 23 Sep 1997, Lawrence Lile wrote:

{Quote hidden}

1997\09\23@163604 by Octavio Nogueira

flavicon
face
> Anybody got a good averaging algorithm?
>
> I've got a stream of numbers from 0 to 15 coming out of a PIC '620
> comparator representing temperature of an appliance.  When I turn on
> the flourescent lamp on my bench, the program......

I have another question about this. One of my pic aplications is a cow
scale,
I do my best to keep it still but you can imagine how the cow listen to
me,
it don't keep still at all.
The filtering I'm doing is: VAL=(LASTVAL/7+NEWVAL)/8
I know thie is not the best way, is the median average better in this
case?

Regards,

Octavio

======================================================
Octavio Nogueira  - e-mail:   .....nogueiraKILLspamspam.....mandic.com.br
http://www.geocities.com/~oct_nogueira
"ProPic" Production PIC Programmer Windows under US$20
======================================================

1997\09\23@193849 by Ross McKenzie

flavicon
face
Octavio,

At 05:33 PM 9/23/97 -0300, you wrote:

{Quote hidden}

I had a friend in the '70s who designed a scale for sheep/goats. Whilst he
did not use a PIC, his approach may be of value to you.

His strain gauge sensor output was amplified and then put through an
adaptive filter before being digitised and displayed. His adaptive filter
was simply a low pass RC filter with the C being connected to ground via
4016 transmission gates. The first time on the scale, the filtering was very
short in time constant, allowing a quick attack. The time constant was
automatically adjusted by switching in progressively larger C values so that
the effects of dancing by the animal was filtered out quickly resulting in a
near perfect reading in a relatively short time. And no need to learn
sheep-speak .....

Perhaps you could use the PIC to switch filtering/averaging in your analogue
path in a similar way.

HTH,

Regards,

Ross McKenzie
Melbourne Australia

1997\09\23@225307 by Notes_Server_1

flavicon
face
Notes Server 1
09/24/97 10:54 AM


> Anybody got a good averaging algorithm?

    Lawrence, you've had a number of good responses
    (especially the suggestion to use a median filter,
    though this depends critically on your sample rate,
    spike width, etc.), but not much directly addressing
    your original question.

    First, keep in mind that because you have a continuous
    data stream you are actually interested in filtering
    rather than averaging.

    Casually, we often talk about 'rolling' or 'running'
    _averages_ when we really mean an IIR (infinite impulse
    response) filter.

    Take the simplest case:

         val = (val + sample) / 2

    This requires only the calculated (running) value, and
    the latest sample.  You can also see why this is called
    an INFINITE impulse response filter.  A very large
    sample can effect a large number (potentially infinite
    number) of subsequently calculated values.  The response
    of the filter to an impulse can extend indefinitely.

    Take the next simplest case:

         val = (val + old_sample + sample) / 3
         old_sample = sample

    Take the next simplest case:

         val = (val + oldest_sample + old_sample + sample ) / 4
         oldest_sample = old_sample
         old_sample = sample

    You get the picture...

    Now consider FIR (finite impulse response) filters.

    Take the simplest case:

         val = (old_sample + sample) / 2
         old_sample = sample

    You can see the difference.  The calculated value
    depends ONLY on the two latest samples.  A very large
    sample can effect only the current value and the next
    calculated value.  After that, the large sample (spike)
    no longer influences the calculated value.  The response
    of the filter to an impulse extends finitely.

    Take the next simplest case:

         val = (oldest_sample + old_sample + sample ) / 3
         oldest_sample = old_sample
         old_sample = sample

    Again, you get the picture...

    Now, in all the preceeding examples each sample is
    assigned the same 'weight'.  If you really want to
    get into filtering you need to assign different
    weights to the samples and from this derive different
    filter characteristics.

___Bob

1997\09\24@002434 by Bob Lunn

flavicon
face
Bob Lunn
09/24/97 02:24 PM


> Anybody got a good averaging algorithm?

    Lawrence, you've had a number of good responses
    (especially the suggestion to use a median filter,
    though this depends critically on your sample rate,
    spike width, etc.), but not much directly addressing
    your original question.

    First, keep in mind that because you have a continuous
    data stream you are actually interested in filtering
    rather than averaging.

    Casually, we often talk about 'rolling' or 'running'
    _averages_ when we really mean an IIR (infinite impulse
    response) filter.

    Take the simplest case:

         val = (val + sample) / 2

    This requires only the calculated (running) value, and
    the latest sample.  You can also see why this is called
    an INFINITE impulse response filter.  A very large
    sample can effect a large number (potentially infinite
    number) of subsequently calculated values.  The response
    of the filter to an impulse can extend indefinitely.

    Take the next simplest case:

         val = (val + old_sample + sample) / 3
         old_sample = sample

    Take the next simplest case:

         val = (val + oldest_sample + old_sample + sample ) / 4
         oldest_sample = old_sample
         old_sample = sample

    You get the picture...

    Now consider FIR (finite impulse response) filters.

    Take the simplest case:

         val = (old_sample + sample) / 2
         old_sample = sample

    You can see the difference.  The calculated value
    depends ONLY on the two latest samples.  A very large
    sample can effect only the current value and the next
    calculated value.  After that, the large sample (spike)
    no longer influences the calculated value.  The response
    of the filter to an impulse extends finitely.

    Take the next simplest case:

         val = (oldest_sample + old_sample + sample ) / 3
         oldest_sample = old_sample
         old_sample = sample

    Again, you get the picture...

    Now, in all the preceeding examples each sample is
    assigned the same 'weight'.  If you really want to
    get into filtering you need to assign different
    weights to the samples and from this derive different
    filter characteristics.

___Bob

1997\09\24@034529 by Mal Goris

flavicon
face
Octavio Nogueira writes:
> > Anybody got a good averaging algorithm?
> >
> > I've got a stream of numbers from 0 to 15 coming out of a PIC '620
> > comparator representing temperature of an appliance.  When I turn on
> > the flourescent lamp on my bench, the program......
>
> I have another question about this. One of my pic aplications is a cow
> scale,
> I do my best to keep it still but you can imagine how the cow listen to
> me,
> it don't keep still at all.
> The filtering I'm doing is: VAL=(LASTVAL/7+NEWVAL)/8
> I know thie is not the best way, is the median average better in this
> case?

To answer that question you need to know something about the
probability distribution of the data you are measuring. To do this,
you either guess what the distribution is (and you will be the best
one to do that) or you estimate it. To estimate the probability
distribution you record lots of measurements and then plot them as a
histogram. If you find that the distribution is evenly spaced around
the mean then averaging is good for you. If you find that the
distribution extends a long way on one side (more than the other side)
then the median may be your best estimator.

Mal
--
http://www.nfra.nl/~mgoris/

1997\09\24@040222 by William Chops Westfield

face picon face
   > Anybody got a good averaging algorithm?

There's some literature on this in the networking world.  A non-worthless
TCP implementation keeps track of an average "round trip time", as well
as an average variance, and a filter of sorts to prevent assorted erronous
results from being used in the caclulations.

The basic algorithm is similar to what's already been discussed.  First
you note that an alternate formula for an average:

       avg = samp1/N + samp2/N + samp3/N + ... sampN/N

You can rearrange this to:

       avg = sampN/N + (samp1/N + samp2/N...)

The second part of this is VERY CLOSE to what you'd get by using N-1
"average" samples:

       ((N-1) * avg)/N

Or      (1 - 1/N) * avg


So you have:

  new_avg = sampN/N + ( (1 - 1/N) * avg )

Of course, you can now pick N rather arbitarilly and keep
a "running average" by calculating:

       avg = avg * (1 - 1/N) + sampN/N

Now, this would normally be rather problematic to calculate without floating
point, and slow to do WITH floating point, so we observe that the smallest
fractional value we need to deal with is 1/N, pick N to be a nice power of
two, and use what is essentially FIXED POINT fractional numbers, but we'll
call keep an integer perspective by modifying the equation.
Multiply both sides by N:

       N*avg = avg * (N-1) + sampN

Or
       N*avg = N*avg - avg + sampN
       N*avg = N*avg + (sampN - avg)

If we store N*avg, we now have one division (shift) and a couple adds rather
than anything more complicated, and we keep log2(N) bits of fraction around.
Of course, you have to remember to also divide by N whenever you want to
access the actual average...

Typically, N=8 and you have (c code now!):

       sampN -= scaledavg>>3;
       scaledavg += sampN;

On an 8 bit microcontroller, it might make sense to use N = 256, so you
can do your division by simply selecting the high byte of scaledavg instead
of shifting.

Hope this makes sense...

References:

   "Round Trip Time Estimation," P. Karn & C. Partridge, ACM SIGCOMM-87,
        August 1987.


   "Congestion Avoidance and Control," V. Jacobson, ACM SIGCOMM-88,
       August 1988.

BillW

1997\09\24@070833 by Ruben Jonsson

flavicon
face
{Quote hidden}

Before shifting you could add half the value you are dividing with (8
in case of 16 numbers) to get it rounded. Without rounding, 15 ones
and 1 zero would result in an average of 0 instead of 1.
------------------------------------
Ruben Jonsson
AB Liros Elektronik
Box 9124
200 39 Malmo
Sweden
Tel +46 40 14 20 80
Mail: EraseMErubenspam_OUTspamTakeThisOuTsbbs.se
------------------------------------

1997\09\24@101227 by trogers

flavicon
face
Lawrence Lile wrote:

> Anybody got a good averaging algorithm?
>
> I've got a stream of numbers from 0 to 15 coming out of a PIC '620
> comparator representing temperature of an appliance.  When I turn on
> the flourescent lamp on my bench, the program picks up a spike, and
> the relay in this thing fires momentarily, because it reads the
> noise.  "NO PROBLEM" I sez, and sat down to write an averaging
> algoritm...

Hey Lawrence:

If you really have spikes (erroneously high data, due to real physical
processes) you can just take two or three samples and use the smallest. This is
fast and doesn't require much storage. The number of samples needed are a
function of the spike timing and your sampling window. This technique works for
a bunch of real world systems.

Tom Rogers  VP-R&D  Time Tech Inc.

1997\09\24@102211 by Lawrence Lile

flavicon
face
>     > Anybody got a good averaging algorithm?

<snip> derivation deleted

{Quote hidden}

Maybe I don't even have to divide by N.  My results go into an
algorithm that compares the measured temperature to a setpoint.
Setpoint could be any number, so I'll just pick a setpoint that is
already N times my temperature reading.



I'm going to simulate this on a spreadsheet again, and see how far
off it gets after several hundred or thousand cycles.  if it doesn't
"wind up" too bad, this might do the trick.



Best Regards,

Lawrence Lile

1997\09\24@102501 by Lawrence Lile

flavicon
face
> > Anybody got a good averaging algorithm?

>
> I have another question about this. One of my pic aplications is a
> cow scale, I do my best to keep it still but you can imagine how the
> cow listen to me, it don't keep still at all. The filtering I'm
> doing is: VAL=(LASTVAL/7+NEWVAL)/8 I know thie is not the best way,
> is the median average better in this case?

I'll bet that a sample size of 8 will give you nothing but noise.

METHOD 1:  Slaughter the cow, weigh it, and have a barbeque.;-)

METHOD 2: (easier on the cow)  Another post talks about an adaptive
filter.  Average over a small number of readings during 1-2 seconds,
display this as an initial value.  Then begin averaging over longer
periods and more samples.

You might also try taking two readings of 8-10 samples a couple of
seconds apart.  If the readings are the same within a small window
then the cow is momentarily still.  While it is still, shoot it
between the eyes and go back to method 1. ;-)




Best Regards,

Lawrence Lile

1997\09\24@102510 by Lawrence Lile

flavicon
face
>      Anybody got a good averaging algorithm?

>      Snip------------
>
>      (newbee protection on)
>      It seems like you could take readings pretty fast, and then
>      save the measurement only when 'N' consecutive readings are the
>      same.  This would ignore spikes, and still track changes.
>      (newbee protection off)

I seem to remember trying this once, and being amazed that I could
get ten spikes in a row.  Of course, I have a test I run that
specifically challenges things with hash and noise.  It consists of a
Rube Goldberg piece of plywood, on which is mounted two chattering
relays, a couple of universal motors, a spark igniter and a lamp
dimmer.  I figure you might see all these things in an average home.
Best Regards,

Lawrence Lile

1997\09\24@132616 by Stephen R. Holmes

picon face
On Tuesday, 23 Sep 1997, Lawrence Lile <lilelspamspam_OUTTOASTMASTER.COM> asked:

>Anybody got a good averaging algorithm?

to which there were many excellent replies suggesting that the problem
was perhaps not so much one of arithmetic averaging but of filtering
'spikes' from the input stream. In particular, @spam@Notes_Server_1KILLspamspamKEYCORP.COM.AU
provided a quick-n-nifty tutorial on IIR and FIR filters (thanks Bob!),
and Ross McKenzie <R.McKenzie@NOSP*M.SENCON.COM> described a hardware
implementation:

>His strain gauge sensor output was amplified and then put through an
>adaptive filter before being digitised and displayed. His adaptive filter
>was simply a low pass RC filter with the C being connected to ground via
>4016 transmission gates. The first time on the scale, the filtering was very
>short in time constant, allowing a quick attack.

A solution that worked well for me (in a project involving "decoding"
Morse code signals transmitted by error-prone humans at unpredictable
rates) was a trivially-easy IIR variant that minimizes the number of
data-points to be stored (one) and uses only addition and bit-shifts. In
pseudo-code:

 theSmoothedValue = 0;
 while (NotDoneYet)
   theSmoothedValue += ( getNextSample() - theSmoothedValue) >> 2 ;

or in english, "add to the running smoothed value one-fourth the
(signed) difference between each new sample and the current
smoothed value."

This is sort of the software equivalent of the capacitor-discharge
solution; intermittent large spikes decay quickly enough to have
little effect on the operation [of my application], while long-term
trends (steadily increasing or decreasing values) are tracked with
good accuracy and relatively little latency. The technique works best
for applications in which successive samples aren't really random at
all but tend to vary somewhat about a median (there's that word again)
value. Your sampling rate and the (wallclock) period over which an
"average" is accumulated may dictate changes to the shift-count
(divisor), and the low numerical value of your samples (0-15) may make
the technique ineffective without prescaling upwards. (In my Morse
code reader, the simple approach above allowed the software to "lock
on" to transmissions at rates from 5 to 50 words-per-minute within a
couple of characters or so.)

Interesting topic; thanks to all who replied!

/steve holmes   (lurker extraordinaire)

1997\09\25@044858 by Jean-Louis VERN

flavicon
face
At 12:32 23/09/1997 +0000, you wrote:
>Anybody got a good averaging algorithm?

; Offset multibytes variables
MSB     EQU     0
LSB16   EQU     1
LSB24   EQU     2
LSB32   EQU     3

CBLOCK 0x07
       SIGNAL                          ; signal (input and output)
       AVERAGE:2                       ; averaged value
ENDC

       ORG     0x1FF
       MOVLW   0

       ORG     0x000

; Just for testing ...
LOOP    MOVLW   0x80
       MOVWF   SIGNAL                  ; input
       CALL    AVERG
       MOVF    SIGNAL,W                ; output
; ......
       GOTO    LOOP


; AVERG
; First order lowpass filter
; Can be used to smooth a 8 bits signal (SIGNAL)
; Input  SIGNAL
; Output SIGNAL
; AVERAGE = AVERAGE - (AVERAGE/256) + SIGNAL
; SIGNAL  = AVERAGE/256
; At the beginning you can initialise AVERAGE with the first input value :
; AVERAGE(t0) = SIGNAL(t0) * 256

; The simplest way to averaging, but... integer arithmetic produce some
; output instabilities... for example :
; if input = constant = 0xZZ, AVERAGE converges to 0xZZ00 if previous output
; is < 0xZZ, or converges to 0xZZFF if previous output is > 0xZZ.
; If AVERAGE = 0xZZFF, and if the new input is 0xZZ+1, the output changes
; immediately to 0xZZ+1,
; If AVERAGE = 0xZZ00, and if the new input is 0xZZ-1, the output changes
; immediately to 0xZZ-1
; To avoid this problem you need a rounding (see later)...
if 0
AVERG   MOVF    AVERAGE+MSB,W           ; AVERAGE -= AVERAGE/256
       SUBWF   AVERAGE+LSB16,F
       BTFSS   STATUS,C
       DECF    AVERAGE+MSB,F

       MOVF    SIGNAL,W                ; AVERAGE += SIGNAL
       ADDWF   AVERAGE+LSB16,F
       BTFSC   STATUS,C
       INCF    AVERAGE+MSB,F

       MOVF    AVERAGE+MSB,W           ; SIGNAL = AVERAGE/256
       MOVWF   SIGNAL
       RETLW   0
else

; Average whith proper rounding...
; AVERAGE       SIGNAL(out)
; 0xFE80:0xFF00 0xFF
; 0xFD80:0xFE7F 0xFE
; 0x0180:0x027F 0x02
; 0x0080:0x017F 0x01
; 0x0000:0x007F 0x00
AVERG   MOVF    AVERAGE+MSB,W           ; W = AVERAGE/256
       XORWF   SIGNAL,W                ; (W = SIGNAL) ?
       BTFSS   STATUS,Z
       GOTO    AVERG1                  ; no
; (AVERAGE/256 = SIGNAL),
; if (AVERAGE <> 0) AND (SIGNAL <> 0xFF), (AVERAGE/256)+1
; allows a convergence always to 0xZZ00 if input is 0xZZ
       MOVF    AVERAGE+MSB,W
       IORWF   AVERAGE+LSB16,W         ; (AVERAGE = 0) ?
       BTFSC   STATUS,Z
; (AVERAGE = 0x0000), don't increment (AVERAGE/256)
       GOTO    AVERG1
       INCFSZ  SIGNAL,W                ; if SIGNAL = 0xFF, W = 0 and skip ...
       GOTO    AVERG2                  ; else continue whith (AVERAGE/256)+1

AVERG1  XORWF   SIGNAL,W                ; restore AVERAGE/256
AVERG2  SUBWF   AVERAGE+LSB16,F
       BTFSS   STATUS,C
       DECF    AVERAGE+MSB,F           ; AVERAGE -= (AVERAGE/256)

       MOVF    SIGNAL,W                ; AVERAGE += SIGNAL
       ADDWF   AVERAGE+LSB16,F
       BTFSC   STATUS,C
       INCF    AVERAGE+MSB,F
; rounding
       MOVF    AVERAGE+MSB,W           ; SIGNAL = (AVERAGE+128)/256
       BTFSC   AVERAGE+LSB16,7
       INCF    AVERAGE+MSB,W
       MOVWF   SIGNAL
       RETLW   0
endif

1997\09\25@094405 by Lawrence Lile

flavicon
face
> Jean-Louis Vern wrote
> >Anybody got a good averaging algorithm?
>
> ; Offset multibytes variables
> MSB     EQU     0
> LSB16   EQU     1
> LSB24   EQU     2
> LSB32   EQU     3

> ; The simplest way to averaging, but... integer arithmetic produce
> some ; output instabilities... for example : ; if input = constant =
> 0xZZ, AVERAGE converges to 0xZZ00 if previous output ; is < 0xZZ, or
> converges to 0xZZFF if previous output is > 0xZZ. ; If AVERAGE =
> 0xZZFF, and if the new input is 0xZZ+1, the output changes ;
> immediately to 0xZZ+1, ; If AVERAGE = 0xZZ00, and if the new input
> is 0xZZ-1, the output changes ; immediately to 0xZZ-1 ; To avoid
> this problem you need a rounding (see later)...
>  if 0


Thanks a lot, jean!  I am combing through this code to figure out how
on  it works.  Perhaps a more thorough  explanation would help.  I'm
having a rough time following it without comments.  Could you explain
it in English, or pseudocode?


Best Regards,

Lawrence Lile

1997\09\25@103849 by Jean-Louis VERN

flavicon
face
At 12:32 23/09/1997 +0000, you wrote:
>Anybody got a good averaging algorithm?

; Offset multibytes variables
MSB     EQU     0
LSB16   EQU     1
LSB24   EQU     2
LSB32   EQU     3

CBLOCK 0x07
       SIGNAL                          ; signal (input and output)
       AVERAGE:2                       ; averaged value
ENDC

       ORG     0x1FF
       MOVLW   0

       ORG     0x000

; Just for testing ...
LOOP    MOVLW   0x80
       MOVWF   SIGNAL                  ; input
       CALL    AVERG
       MOVF    SIGNAL,W                ; output
; ......
       GOTO    LOOP


; AVERG
; First order lowpass filter
; Can be used to smooth a 8 bits signal (SIGNAL)
; Input  SIGNAL
; Output SIGNAL
; AVERAGE = AVERAGE - (AVERAGE/256) + SIGNAL
; SIGNAL  = AVERAGE/256
; At the beginning you can initialise AVERAGE with the first input value :
; AVERAGE(t0) = SIGNAL(t0) * 256

; The simplest way to averaging, but... integer arithmetic produce some
; output instabilities... for example :
; if input = constant = 0xZZ, AVERAGE converges to 0xZZ00 if previous output
; is < 0xZZ, or converges to 0xZZFF if previous output is > 0xZZ.
; If AVERAGE = 0xZZFF, and if the new input is 0xZZ+1, the output changes
; immediately to 0xZZ+1,
; If AVERAGE = 0xZZ00, and if the new input is 0xZZ-1, the output changes
; immediately to 0xZZ-1
; To avoid this problem you need a rounding (see later)...
if 0
AVERG   MOVF    AVERAGE+MSB,W           ; AVERAGE -= AVERAGE/256
       SUBWF   AVERAGE+LSB16,F
       BTFSS   STATUS,C
       DECF    AVERAGE+MSB,F

       MOVF    SIGNAL,W                ; AVERAGE += SIGNAL
       ADDWF   AVERAGE+LSB16,F
       BTFSC   STATUS,C
       INCF    AVERAGE+MSB,F

       MOVF    AVERAGE+MSB,W           ; SIGNAL = AVERAGE/256
       MOVWF   SIGNAL
       RETLW   0
else

; Average whith proper rounding...
; AVERAGE       SIGNAL(out)
; 0xFE80:0xFF00 0xFF
; 0xFD80:0xFE7F 0xFE
; 0x0180:0x027F 0x02
; 0x0080:0x017F 0x01
; 0x0000:0x007F 0x00
AVERG   MOVF    AVERAGE+MSB,W           ; W = AVERAGE/256
       XORWF   SIGNAL,W                ; (W = SIGNAL) ?
       BTFSS   STATUS,Z
       GOTO    AVERG1                  ; no
; (AVERAGE/256 = SIGNAL),
; if (AVERAGE <> 0) AND (SIGNAL <> 0xFF), (AVERAGE/256)+1
; allows a convergence always to 0xZZ00 if input is 0xZZ
       MOVF    AVERAGE+MSB,W
       IORWF   AVERAGE+LSB16,W         ; (AVERAGE = 0) ?
       BTFSC   STATUS,Z
; (AVERAGE = 0x0000), don't increment (AVERAGE/256)
       GOTO    AVERG1
       INCFSZ  SIGNAL,W                ; if SIGNAL = 0xFF, W = 0 and skip ...
       GOTO    AVERG2                  ; else continue whith (AVERAGE/256)+1

AVERG1  XORWF   SIGNAL,W                ; restore AVERAGE/256
AVERG2  SUBWF   AVERAGE+LSB16,F
       BTFSS   STATUS,C
       DECF    AVERAGE+MSB,F           ; AVERAGE -= (AVERAGE/256)

       MOVF    SIGNAL,W                ; AVERAGE += SIGNAL
       ADDWF   AVERAGE+LSB16,F
       BTFSC   STATUS,C
       INCF    AVERAGE+MSB,F
; rounding
       MOVF    AVERAGE+MSB,W           ; SIGNAL = (AVERAGE+128)/256
       BTFSC   AVERAGE+LSB16,7
       INCF    AVERAGE+MSB,W
       MOVWF   SIGNAL
       RETLW   0
endif

       Jean-Louis VERN
       KILLspamjlvernKILLspamspamwriteme.com

1997\09\25@124443 by Jean Mercier

flavicon
face
>Anybody got a good averaging algorithm?

Try olym-pic filtering:

From ten samples, discard the highest and the lowest, average the
others.

Well i could not resist :)

Jean

1997\09\25@174632 by Lawrence Lile

flavicon
face
Paul Dietz Wrote:

>      There is a much better way! It is called a median filter.
>      Basically, this is just like a moving average (or more
>      generically, an FIR) filter, except that you take the median of
>      the data instead of the average. You do this by sorting the
>      data in the window by value, and then outputing the value which
>      ends up in the middle.
>

Alas!  I have spent a couple days messing around with median filters.
The first one I wrote pushed large values off the end of the sort
stack, into lala land.  It would never climb up.  The next one pushed
them off the bottom of the sort stack.  Would never climb down.
Finally I got one that read in 32 analog values, sorted them, and
took the median as the setpoint.  Code works. BUT the  Relay fires
whenever I hit the lamp on my bench.  Noise immunity is still out of
reach after a lot of hard work.  Oh well, I know how to sort now.   I
fear the noise immunity is harder to buy than this.

I see three avenues:

1. Go postal.

2. Try a longer time delay between measurements, until I get around
the noise.

3. give up on median filters as being too complex, and going back to
averaging.

Another day, another $0.50 US.

Best Regards,

Lawrence Lile

1997\09\26@025613 by mikesmith_ozNOSP*M

flavicon
face
On  8 Jul 97 at 12:09, Jean Mercier wrote:

> >Anybody got a good averaging algorithm?
>
> Try olym-pic filtering:
>
> >From ten samples, discard the highest and the lowest, average the
> others.
>
> Well i could not resist :)

It almost sounds reasonable - for 'one shot' averaging rather than
FIR this is probably a good one.
MikeS
<mikesmith_ozNOSP*M.relaymail.net>
(remove the you know what before replying)

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