Sorry, had to put this aside for awhile ... Actually, I like the way things behave without a filter at all (see other mail), but I just wanted to follow up ... and thank Johannes for his thoughtful comments. -- Ben -- > -----Original Message----- > From: Johannes Berg [mailto:johannes@xxxxxxxxxxxxxxxx] > Sent: Thursday, July 12, 2007 5:16 PM > To: Jiri Benc > Cc: benmcahill@xxxxxxxxx; flamingice@xxxxxxxxxxxx; > linux-wireless@xxxxxxxxxxxxxxx; Cahill, Ben M > Subject: Re: [PATCH 1/1] mac80211: Replace overly "sticky" > averagingfilters for rssi, signal, noise. > > On Wed, 2007-07-11 at 02:25 +0200, Jiri Benc wrote: > > > > + /* Quantize the averages (divide by 16) */ > > > + sta->last_rssi = sta->accum_rssi >> 4; > > > + sta->last_signal = sta->accum_signal >> 4; > > > + sta->last_noise = sta->accum_noise >> 4; > > > > First, do not obfuscate the code, please. If you want to > divide by 16, > > divide by 16. The compiler is perfectly capable of optimizing it. > > No, you're wrong, the compiler can only optimise that if it > knows for sure that the values can't ever be negative. And > quoting the patch further below: > > > + int accum_rssi; /* hi-precision running average (rssi * 16) */ > > + int accum_signal; /* hi-precision average > (signal-quality * 16) */ > > + int accum_noise; /* hi-precision running average (noise * 16) */ > > The compiler does some tricks to avoid the integer division > IIRC but it can't do a simple shift. But in principle you're > right, the code should say "/ 16" because either the > variables need to be made unsigned (only positive values are > put into them) or using a shift is wrong (if negative values > can happpen) Actually, "arithmetic" right shift works for either signed or unsigned. Arithmetic shift looks at the most-significant bit, and shifts more of that in from the left, preserving the sign. Our rssi and noise values are negative (dBm) values, and this integer shift formula worked fine. It's important that the variable is "int", rather than "unsigned", or else the compiler would use a "logical" right shift, which simply shifts in 0s from the left. > > With the algorithm as I see it, each update is done by > update(new_value): > avg = 15/16*avg + new_value > > which means that all old samples are still influencing the > current output. Exactly ... this is the characteristic of an "infinite impulse response" (IIR) filter. The output is fed back into the input. If we had infinite bits of precision in the output filter variable, the influence of a single input would constantly decay at the 15/16 rate, but would last forever. Since we don't have infinite precision, the effect of a single sample is limited. Usually, for a given desired behavior, it's easier to build an IIR filter than an FIR (finite impulse response) filter ... the FIR filter does *not* use any feedback from the output ... any history must be in the form of stored input values, which you suggest below. > > Doing two updates (update(a), update(b)) yields: > avg = 15/16 * (15/16*orig + a) + b = 225/256 * orig + 15/16 * a + b > > And after 16 updates the original values still has an > influence of about 3.5% on the output value: > update(a_0),...,update(a_15): > avg = (15/16)^16*orig + \sum_{i=0}^{15} (15/16)^i * a_i > = 0.3560*orig + 0.3798*a_0 + ... (sum of coefficients is ~10.30) > > Is this really what we want? Wouldn't it be better to have a > ringbuffer of the last 16 values and really do an average > over those? [which is what I understand as "moving average"] This is an FIR approach, which would work just fine, and would give results based on exactly 16 samples of history, distributed equally (rather than weighted towards more recent samples, which actually might be desirable), but would be more complicated to build and would use more storage. You might be exactly right about the definition of a "moving average". I might have mis-used the term. -- Ben -- > > johannes > - To unsubscribe from this list: send the line "unsubscribe linux-wireless" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html
