Shop OBEX P1 Docs P2 Docs Learn Events
How much memory for averages? - Page 2 — Parallax Forums

How much memory for averages?

2

Comments

  • realolman1realolman1 Posts: 55
    edited 2017-01-26 12:35
    Good Lord, again... I may not be good, but I'm slow... Peter Jakacki ... all that "averaging" went right over my head... hahahaha

    Heater, absolutely I learned a few things today.
  • Heater.Heater. Posts: 21,230
    edited 2017-01-26 14:03
    Sorry could not resist it. I had to do a quick test of a boxcar average (aka, "true" average") vs the exponential average. For a box car length of 16 vs an exponential "alpha" factor of 1/16 they come out almost identical when subjected to an input signal with noise.

    averages.png

    The code to do the exponential filter is much smaller and quicker. Here is how it looks in JS:
    let exponentialAverage = 0;
    const alpha = 1 / 8;
    
    let boxCarAverage = 0;
    let boxCarBuffer = new Array(16).fill(0);
    const boxCarLength = 16;
    
    let sample = 0;
    let n = 0;
    
    // Simulate an input signal with noise.
    function getSample() {
        return (1 - 1/4 + Math.sin(n/32) / 2 + Math.random() / 16);
    }
    
    while (1) {
        // Read a sample.
        sample = getSample();
    
        // Calculate exponential average.
        exponentialAverage = (sample * alpha) + (exponentialAverage * (1 - alpha));
    
        // Calculate "true" boxcar average
        boxCarBuffer[n % boxCarLength] = sample;
        let boxCarSum = 0;
        for (let i = 0; i < boxCarLength; i += 1) {
            boxCarSum = boxCarSum + boxCarBuffer[i];
        }
        boxCarAverage = boxCarSum / boxCarLength;
    
        console.log(n, sample, exponentialAverage, boxCarAverage);
        n += 1;
    }
    
    640 x 480 - 42K
  • Heater. wrote: »
    Sorry could not resist it. I had to do a quick test of a boxcar average (aka, "true" average") vs the exponential average. For a box car length of 16 vs an exponential "alpha" factor of 1/16 they come out almost identical when subjected to an input signal with noise.

    http://forums.parallax.com/discussion/download/119495/averages.png


    If we had pure sine waves to work with then we wouldn't need a filter, right? :)
    Mix some nasties into that sine wave and see what happens, but I would have thought a buffer length of 16 was way too small for a finite sample.
  • Heater.Heater. Posts: 21,230
    edited 2017-01-26 14:30
    OK. How about a nice square wave input. Boxcar length of 64. exponetial alpha of 1/64.

    averages.png

    Arguably with these convenient binary sizes and factors the box car is getting to a sensible average value quicker on start up. But the exponential is maintaining a closer to actual average value. (Hmm...the exponential is more a "real" average in this case). Still, the startup in both cases could be improved by initialising the averages with the first sample value.
    640 x 480 - 30K
  • I've used a boxcar or a simple average to reduce effects of pickup from the power lines in low level signals.
    For example, average of 32 samples in 1/60 second. The question is, what is the source of noise, and is the signal itself steady over long intervals? If steady, then a long average whether IIR or FIR will do just fine. But if the signal is changing then there is more to consider. Temperature measurements are usually pretty steady, so long filter time as suggested in post #1 will be fine to smooth out the short term fluctuations from a sigma-delta ADC. However, the Prop sigma-delta ADC will also have long term drift, which is a kind of noise that is harder to filter.

    A Kalman or complimentary filter is good for smart tracking of changing signals, but does not help at all with long term drift, which pretty much has to be taken care of in the hardware or with clever ($!) compensation schemes.
  • Heater.Heater. Posts: 21,230
    Oh boy, all the way through IIR filters and FIR filters to Kalman.

    All our OP wanted was an "average".

    Tracy, I know nothing of Kalman but I got the idea it was all about integrating or "fusing" measurements from multiple sensors to arrive at a more accurate result.

    @evanh,
    ...IIR filters are not an average. Averaging is a FIR filter. The moment you introduce an internal decay you've lost any average.
    Perhaps. Given that we are talking of an infinite stream of samples it all depends on how you define "average". After all we cannot have an "N" of infinity. As my examples above show.

  • Tracy AllenTracy Allen Posts: 6,656
    edited 2017-01-27 07:01
    The simple answer to realolman1's question in post number 1 was already "Yes", in answer to, <the input value, the running total, the number of values added together, and the end result... the averaged values....--snip-- So it shouldn't take any special amount of memory should it?> ... Yes, end of story. Then...

    divergent. Here is a link to another of the many threads in the past that have dealt with the topic of data smoothing or averaging or filtering.
    http://forums.parallax.com/discussion/118111/digital-filter-potpourri
    BR's first post there offers a collection of filter methods, including a couple of single-sensor Kalman methods. Kalman filters can adapt quickly to changing conditions due to inclusion of any source of information that suggests the direction or magnitude of change. That can come from a single data stream, for example, if it is highly improbable that four readings of temperature in a row will be successively increasing, the filter can effectively lower its time constant to respond to what is probably a real temperature trend. The math gets advanced quickly when fusion of more sensors and sources of uncertainty are involved. For that, look to the quadcopter guys.

  • evanhevanh Posts: 15,126
    Heater. wrote: »
    ...IIR filters are not an average. Averaging is a FIR filter. The moment you introduce an internal decay you've lost any average.
    Perhaps. Given that we are talking of an infinite stream of samples it all depends on how you define "average". After all we cannot have an "N" of infinity. As my examples above show.
    Obviously it's not being applied to 100% of the whole waveform in one go. The averaging length is defined by the filter strength - window size. This ties in with the "running" part of a running average.
  • ErNaErNa Posts: 1,738
    edited 2017-01-27 08:42
    We indeed are overengineering the answer to realolman's question. As temperatur itself is averaged movement of molecules, the response time for temperature sensor is quite long, in the seconds. Within a second you can measure an analog signal of "normal" quality to an extrem resolution. If a single measuremt takes 1 ms, 1000 samples can be done in 1 s and so the noise will go down by a factor of 30 (sqrt 1000) So the domination factor is precision of the sensor and ADC. Resolution can go to infinite. But those results are only numbers.

    Why do we average?
    We want to have a more stable value to be not confused by jumping digits. When measuring the temperature we always look to the past, because the current temperature of an object results from earlier heat flow. So it is not of importance, how I average. That is different from denoising a voice signal where the first goal is not do disturb the characteric of the vocal tract.

    Measuring temperature means: I want to know the current past. When I measure a sample now and average 10 values, I need 10 data points. The next sample shifts all the values, the first measured is eliminated. Adding all and divide by 10 means: all the temperature sample in the near past contribute equally to the current value. What is not adequate, because to feel todays temperature I'm not interested if it was cold yesterday. So it is a good idea to determine the current temperature by amphasizing close in time values and deminishing older samples. That exactly is what an R/C low pass filter does and the digital equivalent is the Infinite Response Filter, what just means, take a part of the past and average it to the present. Or, in other words: as improvements came from free trade, guided trade will not improve a system. When I order parts from China, I get them by post from a import tax free stock in germany (up to 180€), when I order my propeller components I have to go to customs, fill out forms, pay tax, and refund it later! Takes me about 2 hours!
  • Heater.Heater. Posts: 21,230
    Tracy,

    Ha! Your simple answer is the opposite of mine. That is "No" as in "No it does not need any special variables, above and beyond the ones listed in the question.

    Sadly most of the links in the linked digital-filter-potpourri no longer work.

    I have to look into this Kalman thing. Never occurred to me it was useful in filtering a single signal. But from what you say it's kind of fusing two signal there, the actual signal and also some extra information about that signal.

    Whenever I looked at Kalman I did not understand anything. Do you know an idiots guide to Kalman?

  • Heater.Heater. Posts: 21,230
    evanh,
    Obviously it's not being applied to 100% of the whole waveform in one go.
    Quite so. To my mind "average" as we learned in school is defined as the sum of a number of values divided by the number of values. Meanwhile a signal is conceptually an infinite stream of values. Ergo you cannot have an average for a signal.

    You can however have an average of a part of a signal, an average over the last second or day or week. At which point it gets a different name "running average" or whatever. My little point was that you are then defining an average for yourself and the results you get will depend how you define it. There is no "true"average as claimed above.
  • Heater.Heater. Posts: 21,230
    ErNa,
    Measuring temperature means: I want to know the current past
    I love that "current past". Such a wonderful contradiction. it's past but it's now. Made my brain stutter.

    As my good old friend once said "For me the past...is not over yet".

    I din't get the part about ordering goods from China.
  • evanhevanh Posts: 15,126
    edited 2017-01-27 14:12
    Heater. wrote: »
    You can however have an average of a part of a signal ...

    Lol! One can be as arbitrary as one likes about what constitutes the working range. Why is this an argument?!

    Addendum: In maths it's just called a dataset. There is no signal. A dataset is whatever you want it to be.
  • ErNaErNa Posts: 1,738
    Heater. wrote: »
    ErNa,
    I din't get the part about ordering goods from China.
    It's about trade contracts. If you throw cocain over a fence or a wall, you don't have to pay taxes, not VAT and not customs. If I order from Mouser, they do all the bureaucracy for me. If I order something from Parallax, the parcel normally ends up in customs and I have to head over and pay both import taxes (normally: nothing, but I have to prove) and VAT 19%. But if I order from china and it comes from a duty free zone in Germany, they send it by normal letter and as long as a limit is not reached, there is nothing to care about. I can imagine, now that things are changing (towers normally don't cross boarders, so some may miss this experience), trade with China will be even more simplified. ;-(

  • Heater.Heater. Posts: 21,230
    Yes, but I can't make the connection between trade restrictions and memory required for averages.
  • ErNaErNa Posts: 1,738
    In average it takes about 10 neurons to memorize that abolishing trade restrictions increases overall efficiency. ;-)But I should stop ;-)
  • Heater.Heater. Posts: 21,230
    edited 2017-01-27 15:55
    A package of 50 Euros of goods from China arrived for me last week. Customs are still sitting on it. Paying the duty is one thing but all this dicking around with web forms, phone calls, and now a real paper form in the post drives one nuts. Between my wasted time and the salaries of the customs guys this has cost the local economy more than the package is worth. Certainly a lot more than they will collect!

    Today the said they would be returning the goods on Monday.

    All of which makes me above averagely furious.
  • kwinnkwinn Posts: 8,697
    Heater. wrote: »
    A package of 50 Euros of goods from China arrived for me last week. Customs are still sitting on it. Paying the duty is one thing but all this dicking around with web forms, phone calls, and now a real paper form in the post drives one nuts. Between my wasted time and the salaries of the customs guys this has cost the local economy more than the package is worth. Certainly a lot more than they will collect!

    Today the said they would be returning the goods on Monday.

    All of which makes me above averagely furious.

    This is the kind of thing that calls for having a wearable hidden camera so that one could go down there and have a polite conversation to find out what the problem is. Then if it turns out to be the typical bureaucratic idiocy it can be posted on youtube and sent to your local representative.
  • heater wrote:
    Whenever I looked at Kalman I did not understand anything. Do you know an idiots guide to Kalman?
    Someone recently posted this video series:



    I found it quite easy to understand -- up to a point.

    -Phil
  • Heater.Heater. Posts: 21,230
    Whoa, there will be 55 vids in that Kalman series. He's only up to number 42.
  • My simple running average, the mul compiles to a left shift + original value and the div to a right shift.

    unsigned int temp = ADC10MEM;
    battery.volt=(temp+battery.volt*3)/4; // averaging 3/4 old + 1/4 new
  • Heater.Heater. Posts: 21,230
    The first 6 of those Kalman vids were simple enough. I don't get a good feel as to why those simple calculations work well yet.

    If I understand it correctly the idea is to assign less weight weight to measurements that look a bit "dodgy" when mixing them into your new estimate of the "true" value. Conversely measurements that fit well with your idea of truth get more weight.

    As opposed to a simple exponential filter or moving average that accepts all measurements as equally valid.

    It's bit like doing those physics experiments where you take a bunch of measurements, plot them on a graph, eyeball it and throw away all the ones that look like "outliers", then draw a straight line through the rest to get your result!

    Anyway, time to start coding up that simple example he gives and see how it compares to the averages we have presented here already.



  • Hi
    looking over your shoulder- I never understood it either!
    Dave
  • Heater.Heater. Posts: 21,230
    Ha! Look over my shoulder and you most likely come away with the wrong answer. :)

    Coding up that Kalman example will have to wait a bit. I have some soldering to do here...
  • ErNaErNa Posts: 1,738
    We had lengthy discussions about fourier transforms and how the are connected to the vector calculus. All this comes from a simple equation: A = B
    The first assumption is: things can be equivalent. If we do not agree about this, discussion is not needed and no result will be.

    If we agree that there is a case were A = B, the next step is: A - B = 0 must be agreed on.

    Now you have a bunch of measurements of a temperature. Every single measurement gives a perfect result. The first value: 31° So the temperature is 31°. The next value: 32° OK, now the temperatur is 32°. What will be the next value?

  • ceptimusceptimus Posts: 135
    edited 2017-01-27 20:11
    I normally use the exponential average method, but with a 'quick response threshold' added. This gives (to a certain degree) the best of both worlds: when the input changes suddenly, the averaged output also reacts quickly, but while the input remains within the threshold then the filtering removes the noise.

    Basic idea:

    newAverage := 0.9 x oldAverage + 0.1 x latestReading

    if abs(newAverage - latestReading) > threshold then newAverage := latestReading

    An actual implementation normally doesn't use floating point values so the figure actually retained is, say, 100 times the average and all the calculations are integer based.
    The threshold is best set manually to be just over twice the amount of 'noise' seen when the input is steady. You can write code to make the threshold auto-tune, but it's more complex and can be fooled by real world noise that only happens occasionally - for example say you have a weighing scale and the normal 'noise' is only an ounce or so, but you want the filtering to remain active even when someone walks past the scale causing 'noise' vibrations of, say, five ounces.
  • Heater.Heater. Posts: 21,230
    ceptimus,

    Interesting idea that quick response threshold. Basically what you are doing is resetting your averaging if you detect a step change in the input. Thus saving it having to spend time floating up-down to the new level. This may well be appropriate for for weighing scales. Dump a heavy weight on the scales and it detects something big has happened and immediately jumps to the new weight. Then resumes averaging that.

    It may not be such a good idea in other cases where signals are expected to vary smoothly. A noise spike may exceed the threshold and immediately bump the average to totally the wrong value.
  • Heater.Heater. Posts: 21,230
    So, if you have a few measurements of some constant value plus a bit of noise you can sort of guess where the next measurement should be. Imagine you were plotting them by hand, after a while you can draw a straight line through the measurements you have. Extending that line into the future you can estimate where you expect the next measurement to be, you would expect it to be on or close to your line.

    Of course the next measurement probably is not on your line due to the noise. But now you can say, if the measurement is far from my prediction I will pay less attention to it and move my line only a little towards it. If the new measurement is close to my prediction I will pay more attention to it and move my line more towards it.

    Basically we are using the knowledge that the actual value should be constant, there for measurements that are far up or down from our estimate are to be trusted less.

    If I understand correctly this is what Kalman is doing when it uses the "kalman gain" to control how much effect every new measurement has. Any one like to say if I'm on the right track here?

    I have a feeling it gets even better than that. Say your signal is rising at constant rate. Now that line you would plot through the points is not horizontal but inclined. Well that's no problem, you can still extend that line into the future, make your estimate of where the next measurement should be and continue as above.

    I get this feeling that kalman handles that situation as well.

    I think this is some kind of magic, kalman is not just using a single signal to form an average, it's using the signal plus it's idea of the rate of change of the signal.






  • ErNaErNa Posts: 1,738
    we are always in a hurry and so we project a future before analyzing the current past. That I wanted to show with my latest post: if you measure a temperature twice and you get different values, the temperature has changed. You have no information about any true value. The measured values are facts. And the moment the temperature rises, you can predict that the next measurement will be higher by the same difference. And you have no chance to make a better prediction! But if now you measure an unexpected value, you know that your prediction, and the model you applied: linear behavior, is wrong. Only now you can start about thinking of noise. But noise is a term, that comes from your experience, the established past. That again means: measuring a temperature implicitely contains so much established knowledge, you are not aware of, that your judgement is not independent, only linked to the data just aquired. To me any kind of filter uses knowledge, implicite or explicite and Kalman tries to extract this knowledge from the currently aquired data and so to dynamically adjust the filter characteristics.
  • heater wrote:
    The first 6 of those Kalman vids were simple enough. ...
    Yeah, after that is when I started to zone out, too.

    -Phil
Sign In or Register to comment.