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

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
kindygarden 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 (N1)*(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
> 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
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
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

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_OUTbfehrenbTakeThisOuTexecpc.com
1997\09\23@150720
by
Paul H. Dietz

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 longtailed 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: .....PICLISTKILLspam@spam@MITVMA.MIT.EDU at WDIINTERNET
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
kindygarden 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 (N1)*(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]

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 = ((SumPrevAvg)+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}> 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
> kindygarden 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 (N1)*(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@163428
by
Craig Niederberger

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
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ craignKILLspamuic.edu ~~~~~~~~~~~~~~~~~~~~~~~~~
Craig Niederberger MD FACS  Chief, Division of Andrology
University of Illinois at Chicago  Director Urologic Basic Research
Department of Urology M/C 958  3129962779 Fax: 3129961291
840 South Wood St, Chicago IL 60612  http://godot.urol.uic.edu
On Tue, 23 Sep 1997, Lawrence Lile wrote:
{Quote hidden}> 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
> kindygarden 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 (N1)*(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@163604
by
Octavio Nogueira
> 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  email: .....nogueiraKILLspam.....mandic.com.br
http://www.geocities.com/~oct_nogueira
"ProPic" Production PIC Programmer Windows under US$20
======================================================
1997\09\23@193849
by
Ross McKenzie

Octavio,
At 05:33 PM 9/23/97 0300, you wrote:
{Quote hidden}>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
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
sheepspeak .....
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

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

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

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
> Anybody got a good averaging algorithm?
There's some literature on this in the networking world. A nonworthless
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 N1
"average" samples:
((N1) * 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 * (N1) + 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 SIGCOMM87,
August 1987.
"Congestion Avoidance and Control," V. Jacobson, ACM SIGCOMM88,
August 1988.
BillW
1997\09\24@070833
by
Ruben Jonsson
{Quote hidden}> 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
>
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_OUTTakeThisOuTsbbs.se

1997\09\24@101227
by
trogers
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 VPR&D Time Tech Inc.
1997\09\24@102211
by
Lawrence Lile

> > Anybody got a good averaging algorithm?
<snip> derivation deleted
{Quote hidden}> 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
> 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...
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

> > 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 12 seconds,
display this as an initial value. Then begin averaging over longer
periods and more samples.
You might also try taking two readings of 810 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
> 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

On Tuesday, 23 Sep 1997, Lawrence Lile <lilelspam_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_1KILLspamKEYCORP.COM.AU
provided a quicknnifty 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 errorprone humans at unpredictable
rates) was a triviallyeasy IIR variant that minimizes the number of
datapoints to be stored (one) and uses only addition and bitshifts. In
pseudocode:
theSmoothedValue = 0;
while (NotDoneYet)
theSmoothedValue += ( getNextSample()  theSmoothedValue) >> 2 ;
or in english, "add to the running smoothed value onefourth the
(signed) difference between each new sample and the current
smoothed value."
This is sort of the software equivalent of the capacitordischarge
solution; intermittent large spikes decay quickly enough to have
little effect on the operation [of my application], while longterm
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 shiftcount
(divisor), and the low numerical value of your samples (015) 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 wordsperminute within a
couple of characters or so.)
Interesting topic; thanks to all who replied!
/steve holmes (lurker extraordinaire)
1997\09\25@044858
by
JeanLouis VERN

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 0xZZ1, the output changes
; immediately to 0xZZ1
; 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
> JeanLouis 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 0xZZ1, the output changes ; immediately to 0xZZ1 ; 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
JeanLouis VERN

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 0xZZ1, the output changes
; immediately to 0xZZ1
; 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
JeanLouis VERN
KILLspamjlvernKILLspamwriteme.com
1997\09\25@124443
by
Jean Mercier
>Anybody got a good averaging algorithm?
Try olympic 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

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
On 8 Jul 97 at 12:09, Jean Mercier wrote:
> >Anybody got a good averaging algorithm?
>
> Try olympic 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...