Post by thread:Sort algorithm ?

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

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}> 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 Kind regards Stefan Sczekalla-Waldschmidt .....sswKILLspam@spam@oikossw.de

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

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 sswKILLspamoikossw.de

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

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 .....sswKILLspam.....oikossw.de PS: many thanks for making the medfilter.asm available.

Stefan Sczekalla-Waldschmidt wrote: > <SNIP> {Quote hidden}> 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 discu 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

>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€LLEKS (in A-Z letters: "HALLEKAS") SE-277 35 KIVIK, SWEDEN EraseMEmrtspam_OUTTakeThisOuTiname.com ___________________________________________________________

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

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€LLEKS (in A-Z letters: "HALLEKAS") SE-277 35 KIVIK, SWEDEN mrtspam_OUTiname.com ___________________________________________________________

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

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€LLEKS (in A-Z letters: "HALLEKAS") SE-277 35 KIVIK, SWEDEN KILLspammrtKILLspaminame.com ___________________________________________________________

>> 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€LLEKS (in A-Z letters: "HALLEKAS") SE-277 35 KIVIK, SWEDEN spamBeGonemrtspamBeGoneiname.com ___________________________________________________________

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

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.

Dmitry Kiryashov wrote: {Quote hidden}> > 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. 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

>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€LLEKS (in A-Z letters: "HALLEKAS") SE-277 35 KIVIK, SWEDEN TakeThisOuTmrtEraseMEspam_OUTiname.com ___________________________________________________________

John Payson wrote: {Quote hidden}> > |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. 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