Searching \ for 'Sort 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=sort+algorithm
Search entire site for: 'Sort algorithm ?'.

Truncated match.
PICList Thread
'Sort algorithm ?'
1998\10\30@060920 by Stefan Sczekalla-Waldschmidt

flavicon
face
Hi,

While I expect "bubble-sort" as not very efficient I decide quick-sort
as overshoot for sorting less than 10 Values.

My expectation is worst case 57*(test and swap) for the buble-sort-way
with 8 Values.

Does anybody have a idea for a small fast sort algorithm ?

Ideas - suggestions ?

kind regards

       Stefan Sczekalla-Waldschmidt
       spam_OUTsswTakeThisOuTspamoikossw.de

1998\10\30@124649 by Scott Dattalo

face
flavicon
face
Stefan Sczekalla-Waldschmidt wrote:
>
> Hi,
>
> While I expect "bubble-sort" as not very efficient I decide quick-sort
> as overshoot for sorting less than 10 Values.
>
> My expectation is worst case 57*(test and swap) for the buble-sort-way
> with 8 Values.
>
> Does anybody have a idea for a small fast sort algorithm ?
>

How are you receiving the unsorted data? I've found that it's more
efficient to make a single pass through the sorting algorithm for each
piece of data that is received (as opposed to a pair of loops that are
required for the bubble sort algorithm). If you're receiving a block of
data that can't be delayed, then this obviously won't work for you.

One trick that I've found useful is to sort the pointers to the data
instead of the data itself. For example if you have 16 or fewer items
then the 'pointers' can be nibbles. It's much quicker to swap nibbles
than to swap two 16-bit values. Another benefit of this approach (again
assuming that each data value is processed as it's received) is that a
circular array can be used to store the data. The new value simply
overwrites the old. In addition, if you need the average of the sorted
array, then you can maintain a running sum that is reduced by the oldest
value and increase by the newest value each time a new sample is placed
into the array. (I probably should post the code instead of
beating-around-the-bush.)

Scott

1998\10\30@142718 by Bob Blick

face
flavicon
face
On Fri, 30 Oct 1998, Scott Dattalo wrote:
> (I probably should post the code instead of
> beating-around-the-bush.)

Yes, please!

Thanks,
Bob


'Sort algorithm ?'
1998\11\03@053341 by Stefan Sczekalla-Waldschmidt
flavicon
face
Hello Scott,

>
> How are you receiving the unsorted data? I've found that it's more
> efficient to make a single pass through the sorting algorithm for each
> piece of data that is received (as opposed to a pair of loops that are
> required for the bubble sort algorithm). If you're receiving a block of
> data that can't be delayed, then this obviously won't work for you.
>

I4ll get a single value ( Source : TMR0 ) right after a High2Low
transition on a Portbit. Minimum time for claculating will be abt. 1ms
which is plenty of time.

The data will be stored in a circular buffer. My first thought was to
copy the data to a shadow buffer. doing all processing to the shadow.

You4d give an interesting Idea to me, just to copy the pointer to the
data rather the data itself. This will give the benefit that I can
remove the pointer if the data is "processed". My approch for sorting
was to look for the smallest data, then store it to a 3rd buffer, 1st
location, find second smallest data, storing to the 2nd location,
looking for the third smallest date storing to 3rd location and so on ..

than doing a average over the Values in the middle of the set.

suggestions ?

{Quote hidden}

Kind regards

       Stefan Sczekalla-Waldschmidt
       .....sswKILLspamspam@spam@oikossw.de

1998\11\03@114630 by Scott Dattalo

face
flavicon
face
Stefan Sczekalla-Waldschmidt wrote:
>
> Hello Scott,
>
> >
> > How are you receiving the unsorted data? I've found that it's more
> > efficient to make a single pass through the sorting algorithm for each
> > piece of data that is received (as opposed to a pair of loops that are
> > required for the bubble sort algorithm). If you're receiving a block of
> > data that can't be delayed, then this obviously won't work for you.
> >
>
> I4ll get a single value ( Source : TMR0 ) right after a High2Low
> transition on a Portbit. Minimum time for claculating will be abt. 1ms
> which is plenty of time.

As I suspected, you receive the data one-chunk-at-a-time. This makes the
single pass sorting algorithm doable for you, although 1ms is quite
enough time to bubble sort an array. (But wouldn't be nice to have idle
time for the just-in-case scenario?)


{Quote hidden}

Stefan,

Your application is nearly identical to mine. (Though I'm not sure of
the size of your data items nor the number of them [but if you were
willing to implement three buffers, then you probably didn't have that
much data]). Essentially you want to create a median filter that
averages too. In other words, you wish to collect a series of N samples,
sort them, throw away the extremes, and then compute the average with
what's remaing. Is that correct?

If so then you may want to visit the "median filter" I threw out onto a
web page because of Bob Blick's prodding. The routine you'll find there
should do exactly what you want. It's written as a macro (because in my
application I needed several median filters). This is good because it's
extremely flexible in terms of size and thresholding, but bad because
the flexibility makes it confusing to follow. Hopefully there are enough
comments for it to make sense.

BTW. The web page consists of a cut-n-paste untested version. The
original version (for which the median filter was written) was tested.

http://www.interstice.com/~sdattalo/technical/software/pic/medfilt.html

Scott

1998\11\04@104945 by Stefan Sczekalla-Waldschmidt

flavicon
face
Hello Scott,


> Stefan,
>
> Your application is nearly identical to mine. (Though I'm not sure of
> the size of your data items nor the number of them [but if you were
> willing to implement three buffers, then you probably didn't have that
> much data]). Essentially you want to create a median filter that
> averages too. In other words, you wish to collect a series of N samples,
> sort them, throw away the extremes, and then compute the average with
> what's remaing. Is that correct?

Simply YES :-) -

>
> If so then you may want to visit the "median filter" I threw out onto a
> web page because of Bob Blick's prodding.

I will visit your Web-Page.

While I still have to look at your Web-Page, discussing with two friends
in the amateur-radio-club yesterday evening gave also some new Ideas to
me.

While the dataset I4ll look at is rather small we came up with the Idea
to first
filter the data for extremes, using a kind of modifiable window below
and over the expected center data. the size and position of the window
is modified by monitoring how often per time the window borders are
missed. The values passing this "filter" will
be stored in the well known circular buffer. because of having this data
filtered in fornt of storing, there should be no need for sorting - just
average the data.

What do you think about this idea - beside I dont know if this way would
have been useful for you.

Kind regards

       Stefan Sczekalla-Waldschmidt
       sswspamKILLspamoikossw.de

1998\11\04@114142 by Scott Dattalo

face
flavicon
face
On Wed, 4 Nov 1998, Stefan Sczekalla-Waldschmidt wrote:

> Hello Scott,
>
>
> While I still have to look at your Web-Page, discussing with two friends
> in the amateur-radio-club yesterday evening gave also some new Ideas to
> me.
>
> While the dataset I4ll look at is rather small we came up with the Idea
> to first
> filter the data for extremes, using a kind of modifiable window below
> and over the expected center data. the size and position of the window
> is modified by monitoring how often per time the window borders are
> missed. The values passing this "filter" will
> be stored in the well known circular buffer. because of having this data
> filtered in fornt of storing, there should be no need for sorting - just
> average the data.
>
> What do you think about this idea - beside I dont know if this way would
> have been useful for you.

If you know the range before hand, then this would make more sense.
However, a median filter isn't necessarily filtering just out-of-range
data. As Lawrence and others have said before, it's intended to instead
filter that occasional noise spike that is not representative of the data
(or at least representative of that portion of data for which you're
interested).

Or to say it differently, the median filter works by truncating the
extremes of the last N samples. So for example, suppose you have 'normal
ranging' data and then you get a 'spike'. The median filter would remove
this spike. But suppose that the 'spike' is really a step function - the
new trend in the data. Well eventually, the last N samples will all be at
the same level as the 'spike' and the median filter will pass this new
value. So the point I'm trying to make, is that the thresholding is in the
indices of the sorted data and not in the values of the data.

If you want to protect against invalid, out-or-range data, then threshold
the values as they're obtained. If you want to remove the occasional (and
possible expected, but undesirable) spike, then use a median filter. In
either case, you may wish to add a subsequent linear filter (e.g. FIR/IIR
type which could be as simple as finding their average). However, placing
a median threshold around the current average (as you discuss above) may
prevent the algorithm from tracking a step function.

Does this make sense?


Scott

1998\11\05@061403 by Stefan Sczekalla-Waldschmidt

flavicon
face
Hi Scott,

Scott Dattalo wrote:
>
>
> If you know the range before hand, then this would make more sense.
> However, a median filter isn't necessarily filtering just out-of-range
> data. As Lawrence and others have said before, it's intended to instead
> filter that occasional noise spike that is not representative of the data
> (or at least representative of that portion of data for which you're
> interested).
>
> Or to say it differently, the median filter works by truncating the
> extremes of the last N samples. So for example, suppose you have 'normal
> ranging' data and then you get a 'spike'. The median filter would remove
> this spike. But suppose that the 'spike' is really a step function - the
> new trend in the data. Well eventually, the last N samples will all be at
> the same level as the 'spike' and the median filter will pass this new
> value.

While I understood the paragraph above, the sentence below confuses me a
little,
because (* see below )

> So the point I'm trying to make, is that the thresholding is in the
> indices of the sorted data and not in the values of the data.

> If you want to protect against invalid, out-or-range data, then threshold
> the values as they're obtained. > If you want to remove the occasional (and
> possible expected, but undesirable) spike, then use a median filter. In
> either case, you may wish to add a subsequent linear filter (e.g. FIR/IIR
> type which could be as simple as finding their average).

> However, placing a median threshold around the current average (as you discuss
above) > may prevent the algorithm from tracking a step function.

You are right, but I4m not sure if the discussion of my idea pointed
out, that the thresholds for filtering where meant as of a dynamic
adapting kind ? ( please excuse my ugly english ).

(*) I thought with the adapting threshold, the behaviour should have
been mostly the same like the sorting way which will react faster
because the dynamic threshold needs additional attention.

   Possibly the dynamic adapting thresholds Way will be somewhat more
flexible for
   detecting error-states.

> Does this make sense?

Yes does, so wich way to chose depends on the desired behaviour.

I think in my Case - Motor-speed-control ( Model railroad ) a
step-function will be a indicator for a kind of failure.

Best regards

       Stefan Sczekalla-Waldschmidt
       .....sswKILLspamspam.....oikossw.de

PS: many thanks for making the medfilter.asm available.

1998\11\05@132458 by Scott Dattalo

face
flavicon
face
Stefan Sczekalla-Waldschmidt wrote:
>

 <SNIP>

{Quote hidden}

ss above) > may prevent the algorithm from tracking a step function.
>
> You are right, but I4m not sure if the discussion of my idea pointed
> out, that the thresholds for filtering where meant as of a dynamic
> adapting kind ? ( please excuse my ugly english ).
>
> (*) I thought with the adapting threshold, the behaviour should have
> been mostly the same like the sorting way which will react faster
> because the dynamic threshold needs additional attention.

<snip>

> I think in my Case - Motor-speed-control ( Model railroad ) a
> step-function will be a indicator for a kind of failure.



Hmmm. If a 'step function' can be an indication of a failure, could this
be an indication that sampling rate is too fast? I'm not trying to imply
that this is problem or anything, I'm just merely suggesting that you
perhaps may be able to lower your sampling rate (and keep the same
filter; yet have more time for other things...)

BTW, perhaps Morgan may care to elaborate, but from what I can tell it
appears his (otherwise efficient) 'median' filter may be susceptible to
a large step too. In particular, a large step that tends to oscillate
around a median point (a median point much higher than the current
median point in the filter). I may be just mis-reading the comments [:)]
but it seems like that even though the filter contains N elements, it's
possible for samples N-older than the current sample can be held in
sample array. Am I mis-understanding the code, Morgan?

On another non-pic microcontroller, I found that the indirect addressing
required for index-sorting to be too inefficient. So instead, I
implemented the median + averaging filter like so:

#define MAX_SAMPLES 8
static int samples[MAX_SAMPLES] = {0,0,0,0,0,0,0,0};
static int index = 0;
static int sum = 0;

int filter(int new_sample)
{
 int smallest, biggest,i;

 /* update the total by adding in the newest sample and removing the
oldest */

 sum = sum - samples[index] + new_sample;

 /* Overwrite the oldest sample with the newest (circular array) */
 samples[index] = new_sample;

 index = (index + 1) & (MAX_SAMPLES-1);


 smallest = biggest = samples[0];

 /* find the extremes: */

 for(i=1; i<MAX_SAMPLES; i++)
   {
      if(smallest>samples[i])
        smallest = samples[i];

      if(biggest<samples[i])
        biggest = samples[i];

   }

 /* remove the extremes from the sum */
 /* note, division really isn't necessary... */
 return(sum - biggest - samples);

}

The actual code was in assembly (of course). And this is from memory...

> PS: many thanks for making the medfilter.asm available.

Your welcome.

Scott

1998\11\05@193631 by Morgan Olsson

picon face
>BTW, perhaps Morgan may care to elaborate, but from what I can tell it
>appears his (otherwise efficient) 'median' filter may be susceptible to
>a large step too.

No, the eight middle values in filter array (sorted by value) are averaged,
creating the output value.

The four highest and the four lowest in filter array is not used for the
calculation of current output.

BUT:
When the signal change to values like the extreme highest/lowest, theese
will be shifted in.

The very largest step we can get for every filter process is when we have
loaded it full of minimum value, then feeding it with only maximum values;
then the output will ramp from min to max in linear steps of 1/8 of (max-min)

In this case there will be a delay of four feeds before ramping, as the
four extremes of high and low are not used for output.

Thus the value of output is not disturbed by spikes of up to four feeds!

>In particular, a large step that tends to oscillate
>around a median point (a median point much higher than the current
>median point in the filter).

I am not sure what you mean.
If we have an continuous oscillating waveform signal the output will be the
average of the half of numbers of samples being closest to median.
(theoretically, we will of course as always have aliasing effects etc)

>I may be just mis-reading the comments [:)]

They are probably hard to read even for a swede...
The routine is a compilation af a bunch of paper notes, and as it works i
have not bothered to clean the comments.
I will think about making them in english when i revise the routine.
I plan to make it a macro with compile-time dimensioning parameters
Some time...  ;)

>but it seems like that even though the filter contains N elements, it's
>possible for samples N-older than the current sample can be held in
>sample array.

Yes, it is intentional.

>Am I mis-understanding the code, Morgan?
Probably not, though it is not easy to read my home-made macros and swedish
explanations... alhough i read it like i think.
(Don't take me to a shrink now...)  ;)

The filter is not trashing values by time, that would be a waste IMHO
Instead it trashes the one of the earlier samples being furthest away from
the current median on the opposite side of the new feed injection.

Gee...  I mean:

If injected > median, trash lowest
If injected < median, trash highest

(As you may suspect, this filter was constructed from drwaing it as a
process, then flow-chart, then coded.)

Say you have a very noisy signal;
In my application i can also have a decent signal for a while, then a burst
of much noise.

So i *want* the filter to throw away the extremes, regardless of their age.

Say i am measuring temperature sensor which reads 32.1 to 32.5 ¡C
After 16 feeds the filter will contain a sorted series of values between
32.1 and 32.5 ¡C. (and outputs the average of the 8 middle array values)

Then there is a burst of noise which give sample values of everything
between -20 to +150¡C:
1)  Only values between 32.1 and 32.5 will be injected between the old
samples, causing very little disturbance.  (at injection below array middle
the values above are shifted up, trashing the highest, and vice versa fo
rinjection above middle.)

2) Values above 32.5 will be injected to top, all values shifts down
trashing the lowest.

3) Values below 32.1 will be injected to bottom, all values shifts up
trashing the highest.

At noise bursts 2) and 3) will be fighting, trashing each others out-of
order values.

As neither the four highest nor the four lowest positions are used for
calculating output value it vill take a lot of noise before filter is
disturbed.

So, for short periods noise will have extremely little effect on output.
The only thing that happens when 2) and 3) concurs is that values from the
top/bottom four positions are shifted in/out of the middle eight positions
from where the output is calculated as average.  As the most diverse values
are at the end oft the array, they will be the first to get trashed from a
opposite or more normal feed value, and the latest to be shifted in when/if
a even more extreem feed is given.

So: the filter stops noise very good.

AND, and this is important too: (for my application anyway)
When a real change in signal occours, the filter settles pretty fast:
Say we first have a 16 feeds of the value 100
Then wee feed it with values 132
1) four feeds until ramping begins (output still =100)
2) eight feeds while ramping   (eight steps; changing +4 at a time)
3) No residual change   (output keep at =132)

Another good thing is that it can pretty time-effectively crunch feeds from
A/D converter every A/D-ready-interrupt, needing buffering only the last
sample.
The code is not very big either.

Tip:
This is not very easy to understand from just words.
The best way is to draw it on paper, more like a process than a flow-chart.
This is probably the fourth filter variant i
tested and it is by far the best for my application.

If anybody creates variants of this filter, maybe as macro, register
controlled array size etc  :)  I appreciate to recieve copies.

Opinions, suggestions, problems found, etc  welcome
/Morgan

       Morgan Olsson                   ph  +46(0)414 70741
       MORGANS REGLERTEKNIK            fax +46(0)414 70331
       H€LLEKS           (in A-Z letters: "HALLEKAS")
       SE-277 35 KIVIK, SWEDEN               EraseMEmrtspam_OUTspamTakeThisOuTiname.com
___________________________________________________________

1998\11\06@210703 by Scott Dattalo

face
flavicon
face
Morgan Olsson wrote:

> Gee...  I mean:
>
> If injected > median, trash lowest
> If injected < median, trash highest

Ahh! That's the key point I was missing. I was assuming that the
'trashing' would occur on the opposite ends.

The only kind of signal that could cause this type of filter to 'fail'
would be one oscillating with an amplitude larger than the current
extremes. In which case, you can safely make the argument that the
filter is not 'failing', but actually filtering out the noise.

But OTOH, in some applications you might have to ensure that this
doesn't happen. For example, I could envision a situation where an
incoming signal is very steady and the filter is filled with this
quiescent value. Then the signal slowly changes its value while at the
same time some 'noise source' is introduced. The DC/median component
which we wish to capture is changing. However, because of the
oscillations due to the noise, the filter's median value remains
unchanged. (Each oscillation pushes the previous extreme off of the
sample stack.)

In your case (temperature monitoring), this scenario wouldn't occur. So
the filter (or I should say the MOMA - the Morgan Olson Median
Algorithm) would work beautifully. In my case, the samples were all over
the place (lots of high frequency noise). It really boils down to: Know
your signals and know your noises!

Scott

1998\11\06@220350 by Dmitry Kiryashov

flavicon
face
Hello Scott.

> But OTOH, in some applications you might have to ensure that this
> doesn't happen. For example, I could envision a situation where an
> incoming signal is very steady and the filter is filled with this
> quiescent value. Then the signal slowly changes its value while at the
> same time some 'noise source' is introduced. The DC/median component
> which we wish to capture is changing. However, because of the
> oscillations due to the noise, the filter's median value remains
> unchanged. (Each oscillation pushes the previous extreme off of the
> sample stack.)

Is it possible to look at example of such a sequency of data ?
Also interesting to know what possible range of imcoming data.

WBR Dmitry.

1998\11\07@142814 by Morgan Olsson

picon face
At 09:57 1998-11-06 -0800, you wrote:
>Morgan Olsson wrote:
>
>> Gee...  I mean:
>>
>> If injected > median, trash lowest
>> If injected < median, trash highest
>
>Ahh! That's the key point I was missing. I was assuming that the
>'trashing' would occur on the opposite ends.
>
>The only kind of signal that could cause this type of filter to 'fail'
>would be one oscillating with an amplitude larger than the current
>extremes. In which case, you can safely make the argument that the
>filter is not 'failing', but actually filtering out the noise.

Yes, in my application which has to supress "bursts" of noise, this
behaviour is very desireable.

>But OTOH, in some applications you might have to ensure that this
>doesn't happen. For example, I could envision a situation where an
>incoming signal is very steady and the filter is filled with this
>quiescent value. Then the signal slowly changes its value while at the
>same time some 'noise source' is introduced. The DC/median component
>which we wish to capture is changing. However, because of the
>oscillations due to the noise, the filter's median value remains
>unchanged. (Each oscillation pushes the previous extreme off of the
>sample stack.)

Yes, that may be a problem.

But total locking is *very* unlikely to happen in practical life:
The filter will only be locked if the injected number of feeds with values
higher than the current array maximum values are exactly the same as the
the number of feeds with values lower than the current array minimum.

Example:
The noise amplitude > sampled array range; then if the real average change
we will have more samples injected in one end than in the other.
The exception is if the noise has extremely sharp rise *and* fall times,
and even duty cycle, like a square-wave.  In practical life, however,
inifinite rise/fall doesnt exist, and also the aliasing, sample-hold error,
etc will help moving the filter by adding imprecision (!)

As most noise is very spread the feeds will occasionally inject in the
array, making it change slowly.

So, in real life the filter vill handle every situation, in the way that
the more noise that is present, the more hesistant the filter will appear;
slower output change.  In most applications that is very good.

However we can construct a error:
If we add noise in the form of an unsymmetric square-wave, with an
amplitude so high that it will lead to injections of new feeds in ends of
the sample array,  it can make more injections in top of filter, than in
bottom, even if the real average is changing in the opposite direction!

If anybody have idea of how to avoid that, please post it! :)

I«ve been thinking of using a plain average-of-the-last-n-samples filter,
and compare to "my" filter, and if very diferent, feed "my" filter with
additional "fake samples" of that average vaule.

Another idea i«ve had is to add software generated symmetric and spread
"noise" (i.e sawtooth ramp values, but spread in time to more noise-like)
to the samples before feeding the filter with it.

The amplitude of that noise should be controlled not to disturb the real
signal, of course.  Means of control could be to control it from the
difference of plain rolling average-of-the-last-n-samples average, and
current filter output.

Ideas, comments, solutions, etc, please

For the sampling, as always, make sure that the sampling frequency are
distant from any regular noise frequency, like switched mode power
supplies, motor drives, etc!

I use also to have irregular sampling timing:
Sample A
Sample A
Sample B
Sample A
Sample C
Sample A
etc...

Where A is the one i need best response from, C and B is less important.

>In your case (temperature monitoring), this scenario wouldn't occur. So
>the filter (or I should say the MOMA - the Morgan Olsson Median
>Algorithm) would work beautifully.

Thanks for the naming, i will update the code labels  :)

>In my case, the samples were all over
>the place (lots of high frequency noise). It really boils down to: Know
>your signals and know your noises!

Exactly.
Always thoose investigations... ;)

/Morgan

>Scott

       Morgan Olsson                   ph  +46(0)414 70741
       MORGANS REGLERTEKNIK            fax +46(0)414 70331
       H€LLEKS           (in A-Z letters: "HALLEKAS")
       SE-277 35 KIVIK, SWEDEN               mrtspamspam_OUTiname.com
___________________________________________________________

1998\11\07@180423 by Morgan Olsson

picon face
Just a short note:
The averaged output generated by the posted code is formed from eight added
positions, then just shifted right 3 steps to divide by 8.

This truncates, giving a rounding error of a half lsb average.

Remedy is of course to initialise the 3-byte adder T4:T3:T2 to 000004
instead of clearing it as now is done in routine Sum16.

/Morgan
       Morgan Olsson                   ph  +46(0)414 70741
       MORGANS REGLERTEKNIK            fax +46(0)414 70331
       H€LLEKS           (in A-Z letters: "HALLEKAS")
       SE-277 35 KIVIK, SWEDEN               @spam@mrtKILLspamspaminame.com
___________________________________________________________

1998\11\09@042418 by Stefan Sczekalla-Waldschmidt

flavicon
face
Hello Morgan,
>
I used the weekend to do a test of the MOAF but I think i made an
mistake when
remake the IFRXXXGO Macro. Can you eventually post these Macros ?

I seems always to inject values to > viktfilter+15,
trashing allways the most upper value.

As a first test, I tested the behaviour with an input of 1 increasing up
to D'15' where
I expected to get all low-bytes of the filter filled.

I try to show the contents of the array:

1:
        |           |           |           |

0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1
0  0  0  0  0  0  0  0  0  0  0  0  0  0  2  1
0  0  0  0  0  0  0  0  0  0  0  0  0  3  2  1
0  0  0  0  0  0  0  0  0  0  0  0  4  3  2  1

(...)
8:
0  0  0  0  0  0  0  0  8  7  6  5  4  3  2  1
9:
0  0  0  0  0  0  0  0  9  8  7  6  5  4  3  2

2: (!)
0  0  0  0  0  0  0  0  2  9  8  7  6  5  4  3

I also noticed a value in tyngd_utH while I expected only changes in
tyngd_utL
so there could have happen something while cutting and pasting or I4ve a
register
still to clrf.

I will check the code once more, and stepping through it, cant be hard
to find but
it was rather late ...

Best regards

       Stefan

PS:


I also borrowed a swedish->german->swedish dictionary from my parents in
law...

1998\11\09@072916 by Morgan Olsson

picon face
At 10:26 1998-11-09 +0100, you wrote:
>Hello Morgan,
>>
>I used the weekend to do a test of the MOAF

       :)

Both swedish anf PICmenmonic language exercise

> but I think i made an mistake when
>remake the IFRXXXGO Macro. Can you eventually post these Macros ?

Ok, I've given the house away, but kept the key...
- Who will give me the highest price?

Just kidding ;)

Here follow some relevant code-pullouts, from three macro libraries:

This is my whole MACROseries for 8-bit compare, in swenglish:
; =====================================================================
;J€MF…R register med literal och om villkor uppfyllts sŒ GOTO

;om reg equal, goto
IFREGO  MACRO   reg, literal, where
       movf    reg,W
       sublw   literal
       ifzs
       goto    where
       ENDM

;om reg hšgre, goto
IFRHGO  MACRO   reg, literal, where
       movf    reg,W
       sublw   literal
       ifcc
       goto    where
       ENDM

;om reg lŠgre, goto
IFRLGO  MACRO   reg, literal, where
       movf    reg,W
       sublw   literal
       ifzs            ;Om lika
       goto $+3        ;hoppa till instr efter makrot
       ifcs
       goto    where
       ENDM

;om reg1 hšgre Šn reg2, goto
IFR1HGO MACRO   reg1, reg2, where
       movf    reg1,W
       subwf   reg2,W
       ifcc
       goto    where
       ENDM

;om reg1 hšgre Šn reg2, goto
IFR1LGO MACRO   reg2, reg1, where
       movf    reg1,W
       subwf   reg2,W
       ifcc
       goto    where
       ENDM
; =====================================================================
;J€MF…R unsigned 1-byte register
; SŠtter flaggor efter operationen A-B pŒ subwf vis
; LŠmnar variablerna helt oršrda
CMPU1   MACRO   RA,RB
       movf    RA,W
       subwf   RB,W
       ENDM

;jŠmfšr med konstant
CMCU1   MACRO RA, const
       movf    RA,W
       sublw   const
       ENDM
; =====================================================================
;ATT anv efter compare-rutin som sŠtter flaggor efter
;       operationen A-B pŒ subwf vis

;If equal                               Z=1 om A = B
ifeq    MACRO
       btfsc STATUS,2  ;ifzs
       ENDM

;If different                   Z=0 om A <> B
ifdi    MACRO
       btfss STATUS,2  ;ifzc
       ENDM

;If higher or equal             C=1 om A >= B
ifhe    MACRO
       btfsc STATUS,0  ;ifcs
       ENDM

;If lower                               C=0 om A < B
iflo    MACRO
       btfss STATUS,0  ;ifcc
       ENDM

;If higher                              C=0 & Z=0  om A > B
IFHI    MACRO
       btfss STATUS,0  ;ifcc   ;om A < B
       goto $+3                ;sŒ hoppa šver fšrsta instr efter MACROt
       btfss STATUS,2  ;ifzc   ;Om inte lika heller, sŒ...
       ENDM

;If lower or equal              C=0 om A < B  Z=1 om A = B
IFLE    MACRO
       btfss STATUS,0  ;ifcc   ;om A < B
       goto $+2                ;sŒ hoppa till fšrsta instr efter MACROt
       btfsc STATUS,2  ;ifzs   ;Om lika
       ENDM


;**************************************************************
;I belive the above might need some of theese bittest/check:
;**************************************************************



;Set bit in register
s       macro   reg,bit
       bsf             reg,bit
       ENDM

;Clear bit in register
c       macro   reg,bit
       bcf             reg,bit
       ENDM

;Set Carry
sc      macro
       bsf     STATUS,0
       ENDM

;Clear Carry
cc      macro
       bcf     STATUS,0
       ENDM

;Set Half carry
shc     macro
       bsf     STATUS,1
       ENDM

;Clear Half carry
chc     macro
       bcf     STATUS,1
       ENDM

;Set Zero flag
sz      macro
       bsf     STATUS,2
       ENDM

;Clear Zero flag
cz      macro
       bcf     STATUS,2
       ENDM
; ======================================================
; - Bittest "IF (/not) bit is set do next instruction" -

; IF bit in register is Set
ifs     macro   reg,bit
       btfsc   reg,bit
       ENDM

; IF bit in register is Clear
ifc     macro   reg,bit
       btfss   reg,bit
       ENDM

; IF Carry Set
ifcs    macro
       btfsc   STATUS,0
       ENDM

; IF Carry Clear
ifcc    macro
       btfss   STATUS,0
       ENDM

; IF Half carry Set
ifhcs   macro
       btfsc   STATUS,1
       ENDM

; IF Half carry Clear
ifhcc   macro
       btfss   STATUS,1
       ENDM

; IF Zero flag Set
ifzs    macro
       btfsc   STATUS,2
       ENDM

; IF Zero flag Clear
ifzc    macro
       btfss   STATUS,2
       ENDM

;"Borrowflag" fšr subwf (= invers av carry)
ifbs    macro   ;"If borrow set"
       btfss STATUS,0
       ENDM
ifbc    macro
       btfsc STATUS,0
       ENDM

;**************************************************************
; Theese are also needed
;**************************************************************

;STore Literal -> W & dest
;SŠtter ingen flagga.
STL     MACRO   literal,dest
       movlw   literal
       movwf   dest
       ENDM

;KOPIERA REGISTER
;sourcereg -> W and destinationreg
;Z satt efter W,=source
FWF     MACRO   source,dest
       movf    source,W
       movwf   dest
       ENDM


;**************************************************************
;And here is part of code i once used for test of MOMA with MPLAB
;Maybe reusable?
;**************************************************************

start:
       

preload:
       STL 0x40,tyngd_refL
       STL 0x80,tyngd_refH
       STL viktfilter, FSR     ;Peka pŒ lŠgsta vŠrdet i listan, lŒgbyte
n
preloadloop:

       FWF tyngd_refL,INDF
       incf FSR,F
       FWF tyngd_refH,INDF
       incf FSR,F

       incf tyngd_refL,F

       FWF tyngd_refL,INDF
       incf FSR,F
       FWF tyngd_refH,INDF
       incf FSR,F

       incf tyngd_refL,F

       FWF tyngd_refL,INDF
       incf FSR,F
       FWF tyngd_refH,INDF
       incf FSR,F

       incf tyngd_refL,F

       FWF tyngd_refL,INDF
       incf FSR,F
       FWF tyngd_refH,INDF
       incf FSR,F

       incf tyngd_refL,F

       incf tyngd_refH,F
       incf tyngd_refH,F
       incf tyngd_refH,F
       incf tyngd_refH,F

       IFRLGO FSR,viktfilter+32,preloadloop

stop    goto stop


Enjoy! :)
/Morgan

       Morgan Olsson                   ph  +46(0)414 70741
       MORGANS REGLERTEKNIK            fax +46(0)414 70331
       H€LLEKS           (in A-Z letters: "HALLEKAS")
       SE-277 35 KIVIK, SWEDEN               KILLspammrtKILLspamspaminame.com
___________________________________________________________

1998\11\09@081719 by Stefan Sczekalla-Waldschmidt

flavicon
face
Morgan Olsson wrote:
>
> At 10:26 1998-11-09 +0100, you wrote:
> >Hello Morgan,
> >>
> >I used the weekend to do a test of the MOAF
>
>         :)
>
> Both swedish anf PICmenmonic language exercise

well ... the exercise faciliates decoding the Macros :)

with the preload routine another question shows up: I dont need to
initialize the
viktfilter[0..31] array ?

It looks like Myke Predow should add to his Page with useful code
snippets a Page for
useful Makros like yours or Scott4s !

Possibly I had the IFRHGO wrong, will check this today evening.

Kind regards

       Stefan Sczekalla-Waldschmidt
       RemoveMEsswTakeThisOuTspamoikossw.de

1998\11\09@110438 by Morgan Olsson

picon face
>> Both swedish anf PICmenmonic language exercise
>
>well ... the exercise faciliates decoding the Macros :)

Leave that to MPASM...  ;)

>with the preload routine another question shows up: I dont need to
>initialize the
>viktfilter[0..31] array ?

At startup i have a routine that clears the whole RAM.

So, after having fed the filter with any value 16 times it is fully
initialized.

Another approach: Whatever is in the filter it will be "initialized" by
feeding it with 16 equal feeds.

Or at least when you have fed it with 16 feeds of higher value than the
lowest or lower value than the highest in array.

A quick-start way is to fill the filter with 16 copies of the first
recieved value, either by calling it 16 times the first feed (code saving?)
or separate copy ruotine.

>It looks like Myke Predow should add to his Page with useful code
>snippets a Page for
>useful Makros like yours or Scott4s !
Thanks

Yes!
A routine library site!
       Morgan Olsson                   ph  +46(0)414 70741
       MORGANS REGLERTEKNIK            fax +46(0)414 70331
       H€LLEKS           (in A-Z letters: "HALLEKAS")
       SE-277 35 KIVIK, SWEDEN               spamBeGonemrtspamBeGonespaminame.com
___________________________________________________________

1998\11\09@152152 by Scott Dattalo

face
flavicon
face
Dmitry Kiryashov wrote:
>
> Hello Scott.
>
> > But OTOH, in some applications you might have to ensure that this
> > doesn't happen. For example, I could envision a situation where an
> > incoming signal is very steady and the filter is filled with this
> > quiescent value. Then the signal slowly changes its value while at the
> > same time some 'noise source' is introduced. The DC/median component
> > which we wish to capture is changing. However, because of the
> > oscillations due to the noise, the filter's median value remains
> > unchanged. (Each oscillation pushes the previous extreme off of the
> > sample stack.)
>
> Is it possible to look at example of such a sequency of data ?
> Also interesting to know what possible range of imcoming data.

Often times the source of the signal provides the noise too. For
example, in the DTMF decoder application, I found that the algorithm
would produce a fairly tightly banded signal for the 'ideal case'.
However, if there is a voice present during the DTMF signal, the decoder
would produce a signal that flutuated. Yet the median/average value (or
more precisely the average of the median values) over several samples
was fairly close to the unperturbed case. In general, anytime there is a
sporadic high frequency component present in your signal it's possible
that MOMA (Morgan's filter) will simply not respond to it. (Which, as I
said before, may be a good thing - depending on the application.)



Scott

1998\11\09@181826 by Dmitry Kiryashov

flavicon
face
Hello Scott.

> Often times the source of the signal provides the noise too. For
> example, in the DTMF decoder application, I found that the algorithm
> would produce a fairly tightly banded signal for the 'ideal case'.
> However, if there is a voice present during the DTMF signal, the decoder
> would produce a signal that flutuated. Yet the median/average value (or
> more precisely the average of the median values) over several samples
> was fairly close to the unperturbed case. In general, anytime there is a
> sporadic high frequency component present in your signal it's possible
> that MOMA (Morgan's filter) will simply not respond to it. (Which, as I
> said before, may be a good thing - depending on the application.)

To detect DTMF in addition to filtering the main frequencies it is
requeried
to know that high harmonics of mains are absent (to exclude false voice
recog-
nition as DTMF). The simple idea was visit me. Maybe we should add
another one
simple wideband filter (for instance starting from 3nd harmonic minimal
freq
and ending at 5rd harmonic of maximal freq). If this additional filter
don't
detect anything that all is ok. Probably I couldn't offer the
programming
details of such suggestion but idea looks reasonable. (Probably it'll be
some-
thing related to autocorrelation signal with itself)

WBR Dmitry.

1998\11\09@185654 by Scott Dattalo

face
flavicon
face
Dmitry Kiryashov wrote:
{Quote hidden}

This is the approach that Analog Devices takes in their DSP-based DTMF
decoder. (Actually they decode the 'fundamentals' and the '2nd
Harmonics'.) However, this approach isn't entirely succesful (from what
I've read in other literature). But even if you do implement this
filtering strategy, you're still going to be plagued by the 'broad band'
nature of some conversations. In other words, normal conversation can
overlap the DTMF frequencies.  (The 'autocorrelation' trick helps,
though.)

Scott

1998\11\20@064516 by Morgan Olsson

picon face
>BTW, perhaps Morgan may care to elaborate, but from what I can tell it
>appears his (otherwise efficient) 'median' filter may be susceptible to
>a large step too.

No, the eight middle values in filter array (sorted by value) are averaged,
creating the output value.

The four highest and the four lowest in filter array is not used for the
calculation of current output.

BUT:
When the signal change to values like the extreme highest/lowest, theese
will be shifted in.

The very largest step we can get for every filter process is when we have
loaded it full of minimum value, then feeding it with only maximum values;
then the output will ramp from min to max in linear steps of 1/8 of (max-min)

In this case there will be a delay of four feeds before ramping, as the
four extremes of high and low are not used for output.

Thus the value of output is not disturbed by spikes of up to four feeds!

>In particular, a large step that tends to oscillate
>around a median point (a median point much higher than the current
>median point in the filter).

I am not sure what you mean.
If we have an continuous oscillating waveform signal the output will be the
average of the half of numbers of samples being closest to median.
(theoretically, we will of course as always have aliasing effects etc)

>I may be just mis-reading the comments [:)]

They are probably hard to read even for a swede...
The routine is a compilation af a bunch of paper notes, and as it works i
have not bothered to clean the comments.
I will think about making them in english when i revise the routine.
I plan to make it a macro with compile-time dimensioning parameters
Some time...  ;)

>but it seems like that even though the filter contains N elements, it's
>possible for samples N-older than the current sample can be held in
>sample array.

Yes, it is intentional.

>Am I mis-understanding the code, Morgan?
Probably not, though it is not easy to read my home-made macros and swedish
explanations... alhough i read it like i think.
(Don't take me to a shrink now...)  ;)

The filter is not trashing values by time, that would be a waste IMHO
Instead it trashes the one of the earlier samples being furthest away from
the current median on the opposite side of the new feed injection.

Gee...  I mean:

If injected > median, trash lowest
If injected < median, trash highest

(As you may suspect, this filter was constructed from drwaing it as a
process, then flow-chart, then coded.)

Say you have a very noisy signal;
In my application i can also have a decent signal for a while, then a burst
of much noise.

So i *want* the filter to throw away the extremes, regardless of their age.

Say i am measuring temperature sensor which reads 32.1 to 32.5 ¡C
After 16 feeds the filter will contain a sorted series of values between
32.1 and 32.5 ¡C. (and outputs the average of the 8 middle array values)

Then there is a burst of noise which give sample values of everything
between -20 to +150¡C:
1)  Only values between 32.1 and 32.5 will be injected between the old
samples, causing very little disturbance.  (at injection below array middle
the values above are shifted up, trashing the highest, and vice versa fo
rinjection above middle.)

2) Values above 32.5 will be injected to top, all values shifts down
trashing the lowest.

3) Values below 32.1 will be injected to bottom, all values shifts up
trashing the highest.

At noise bursts 2) and 3) will be fighting, trashing each others out-of
order values.

As neither the four highest nor the four lowest positions are used for
calculating output value it vill take a lot of noise before filter is
disturbed.

So, for short periods noise will have extremely little effect on output.
The only thing that happens when 2) and 3) concurs is that values from the
top/bottom four positions are shifted in/out of the middle eight positions
from where the output is calculated as average.  As the most diverse values
are at the end oft the array, they will be the first to get trashed from a
opposite or more normal feed value, and the latest to be shifted in when/if
a even more extreem feed is given.

So: the filter stops noise very good.

AND, and this is important too: (for my application anyway)
When a real change in signal occours, the filter settles pretty fast:
Say we first have a 16 feeds of the value 100
Then wee feed it with values 132
1) four feeds until ramping begins (output still =100)
2) eight feeds while ramping   (eight steps; changing +4 at a time)
3) No residual change   (output keep at =132)

Another good thing is that it can pretty time-effectively crunch feeds from
A/D converter every A/D-ready-interrupt, needing buffering only the last
sample.
The code is not very big either.

Tip:
This is not very easy to understand from just words.
The best way is to draw it on paper, more like a process than a flow-chart.
This is probably the fourth filter variant i
tested and it is by far the best for my application.

If anybody creates variants of this filter, maybe as macro, register
controlled array size etc  :)  I appreciate to recieve copies.

Opinions, suggestions, problems found, etc  welcome
/Morgan

       Morgan Olsson                   ph  +46(0)414 70741
       MORGANS REGLERTEKNIK            fax +46(0)414 70331
       H€LLEKS           (in A-Z letters: "HALLEKAS")
       SE-277 35 KIVIK, SWEDEN               TakeThisOuTmrtEraseMEspamspam_OUTiname.com
___________________________________________________________

1998\11\20@072541 by Scott Dattalo

face
flavicon
face
Stefan Sczekalla-Waldschmidt wrote:
>

 <SNIP>

{Quote hidden}

ss above) > may prevent the algorithm from tracking a step function.
>
> You are right, but I4m not sure if the discussion of my idea pointed
> out, that the thresholds for filtering where meant as of a dynamic
> adapting kind ? ( please excuse my ugly english ).
>
> (*) I thought with the adapting threshold, the behaviour should have
> been mostly the same like the sorting way which will react faster
> because the dynamic threshold needs additional attention.

<snip>

> I think in my Case - Motor-speed-control ( Model railroad ) a
> step-function will be a indicator for a kind of failure.



Hmmm. If a 'step function' can be an indication of a failure, could this
be an indication that sampling rate is too fast? I'm not trying to imply
that this is problem or anything, I'm just merely suggesting that you
perhaps may be able to lower your sampling rate (and keep the same
filter; yet have more time for other things...)

BTW, perhaps Morgan may care to elaborate, but from what I can tell it
appears his (otherwise efficient) 'median' filter may be susceptible to
a large step too. In particular, a large step that tends to oscillate
around a median point (a median point much higher than the current
median point in the filter). I may be just mis-reading the comments [:)]
but it seems like that even though the filter contains N elements, it's
possible for samples N-older than the current sample can be held in
sample array. Am I mis-understanding the code, Morgan?

On another non-pic microcontroller, I found that the indirect addressing
required for index-sorting to be too inefficient. So instead, I
implemented the median + averaging filter like so:

#define MAX_SAMPLES 8
static int samples[MAX_SAMPLES] = {0,0,0,0,0,0,0,0};
static int index = 0;
static int sum = 0;

int filter(int new_sample)
{
 int smallest, biggest,i;

 /* update the total by adding in the newest sample and removing the
oldest */

 sum = sum - samples[index] + new_sample;

 /* Overwrite the oldest sample with the newest (circular array) */
 samples[index] = new_sample;

 index = (index + 1) & (MAX_SAMPLES-1);


 smallest = biggest = samples[0];

 /* find the extremes: */

 for(i=1; i<MAX_SAMPLES; i++)
   {
      if(smallest>samples[i])
        smallest = samples[i];

      if(biggest<samples[i])
        biggest = samples[i];

   }

 /* remove the extremes from the sum */
 /* note, division really isn't necessary... */
 return(sum - biggest - samples);

}

The actual code was in assembly (of course). And this is from memory...

> PS: many thanks for making the medfilter.asm available.

Your welcome.

Scott

1998\11\23@143028 by John Payson

flavicon
face
|The very largest step we can get for every filter process is when we have
|loaded it full of minimum value, then feeding it with only maximum values;
|then the output will ramp from min to max in linear steps of 1/8 of (max-min)

I know that when performing "normal" filtering methods, it's
useful to use a weighted average of the recent data rather than
counting all recent things equally.  Would such an approach be
useful here also perhaps?  [and if so, would it be worth the
trouble of implementing it]?

For example, if you were to give the middle 9 values in the weights

 1 8 28 56 70 56 28 8 1   [all /256]

then a step input would translate into a nice curve rather than a
ramp.  Depending upon what the signal was being used for, it would
seem this might be a significant improvement.  Of course, if the
input is other than a step function, the behavior could be a bit
harder to characterize.

1998\11\23@163810 by Scott Dattalo

face
flavicon
face
John Payson wrote:
{Quote hidden}

Richard Hamming's (as in THE Hamming window) book "Numerical Methods for
Scientist and Engineers" describes a (relatively) simple technique to
find the frequency response of such filtering methods. (Though, he
doesn't discuss Median Filters which are inherently non-linear.) It's
basically a fourier transform, but his presentation is very easy to
follow (IMO). I used it to compare the frequency response of Simpson's
1/3 rule versus Simpson's 3/8 rule (which is conducive to pic division)
versus the rectangular rule for numeric integration. If anyone cares for
the resulting matlab program let me know.

Scott

1998\11\24@063134 by Stefan Sczekalla-Waldschmidt

flavicon
face
hi,

here is another way for a median filter.

It works by tagging the 4 highest and the 4 lowest values of a circular
buffer, then
just adding up all values and subtracting the extrema.

benefit:        easy mangement of the circular buffer. No sorting required.
               low memory needs.

If interested I can post the basic-source of my test version. Didn4t had
the time
to convert to mpasm. :-(

There is also a way the filter could be speeded up, but this speed up is
not predictable because it depends on the input-values and the tags.
This means, the speed-up
could be noticed statistically because the speed-up works not with every
input-value.

BTW     does somebody know how many iterations are needed for a given array
size
       with bubble-sort vs. quick-sort etc. ?


Kind regards

       Stefan Sczekalla-Waldschmidt
       RemoveMEsswspamTakeThisOuToikossw.de


'Sort algorithm ?'
1998\12\16@070354 by Stefan Sczekalla-Waldschmidt
flavicon
face
part 0 816 bytes content-type:application/x-unknown-content-type-ASM_auto_file;My efforts leads to results ! attached you will find a averaging
Median-Filter.

It works by tagging the 4 most high and 4 most low values of a given set
(16 Values)
the remaining Values get averaged.

It4s current implementation is 8Bit wide and the buffer holds 16 Values.
the 8 Values in the middle are averaged.

execution time @ 4 Mhz aprox. 2.3 ms

Comment`s refers to a BASIC version I posted approx 2 weeks ago.

All comments, and sugestions are welcome. If someone have Ideas for a
speed-up - let me know.

Kind regards

       Stefan Sczekalla-Waldschmidt
       sswEraseMEspam.....oikossw.de
Content-Type: application/x-unknown-content-type-ASM_auto_file;
name="median2.asm"
Content-Disposition: inline;
filename="median2.asm"

Attachment converted: wonderland:median2.asm (????/----) (000219F8)

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