Embedded Systems November 2000 Vol13_12

Issue link:

Contents of this Issue


Page 111 of 189

value appears in the data stream, it will be replaced by a value one larger. In the present case, incoming zeros get replaced by ones. This is ordinarily harmless. Recall that data values other than the median itself are only count- ed; so long as they stay on the correct side of the median, their actual values cannot affect the value returned by the calculation. Only if the true mean were ever zero would this usurpation affect the result, and in that case the median would be reported as 1, not zero. Ordinarily it is easy to avoid that ever happening, and even more com- monly, one would not care. However, in the rare situation where the small- est pos ible data value mu t also be a possible median, the program can be changed to suit. Either reverse the sorting order and use the largest pos- sible data value as the flag instead of the smallest, or use some other means (like setting a flag) to prevent gener- ating additional links once the new datum has been linked in. Worst-case analysis A microcontroller like the Motorola 68HC12 is a more likely controller than a PC for something like our robot project, so for a time estimate I counted cycles in a hand-coded ver- sion of this program for that proces- sor. For a full Nelement data buffer, there will be N steps down the chain, of which (N+ 1) / 2 will be odd and will include dereferencing the median pointer. There will be one pass through the link-out code, and one through link-in. Counting up the bus cycles gives 86 + N* 26, or at an 8MHz cycle rate (16MHz crystal) the filter takes 10.75 + N* 3.25ms: 46.5ms when N= 11. This is, in several respects, a good algorithm for hard real-time applica- tion. It has a fixed execution time (approximately so on any machine, and exactly so on the 'HC12) . By mak- ing u e of the sorted array left over from a previous step, that time becomes proportional to N, better than N log N which is the usual opti- mum when sorting. The code is easy to test thoroughly; it quickly exercises all of its branches when tested with any non-monotonic data sequence long enough to fill the buffer and start replacing old values. So next time you are hunting for a fire in a lightning storm, or have some other case of fat tails to handle, try this median filter. esp Phil Ek.strorn holds a British postgraduate diplorna in cornputer science, and a PhD in physics. He is currently chief physical scien- tist at Northwest Marine Technology, where he develops field instruments that often involve ernbedded computation. Contact hirn at ek.strorn@nrnt-inc. corn. 110 NOVEMBER 2000 Embedded Systems Programming

Articles in this issue

Archives of this issue

view archives of EETimes - Embedded Systems November 2000 Vol13_12