Thread: [Algorithms] Truncate then average? Or average then truncate?
Brought to you by:
vexxed72
From: Robin G. <rob...@gm...> - 2010-05-28 07:24:13
|
Got a bit of a brain block, and I'd welcome someone with a clearer picture of what's the correct thing to do. I have a hardware controller that I'm writing firmware for, specifically debouncing button presses. That's gone fairly well by using a word for each sample of the keystate. An interrupt timer fires and I sample the button states, one bit per key, dumping the current state into a ring buffer of N words. At key scanning time I AND all the words in the buffer together and if any of the bits in each "column" are set I register it as a keypress. So I get instant reaction to a keydown and an N-iteration delay before the columns clear so I can register a keyup. This deals with noisy bounces on key depressions and releases just fine. I am now attempting to "debounce" an analog input. The issue is that the ADC reads the input and returns a 10-bit value, the bottom two bits of which are subject to noise, but that's fine as I only need a value in the range 0..127. So my current effort is to read the ADC value several times, sum them, divide by the number of samples and then lose the bottom 3 bits. This works great for most values in the range, except for the smallest values - 0, 1, 2, ... As you move the controller through the range down to the smallest values, they exhibit the noise and become like an unordered list. Other values where a lot of bits flip, like the boundary between 63 and 64, also allow the noise to propagate up to affect the value. Technically, there should be no reason for even the smallest numbers to show the noise - only the bottom two bits exhibit noise and we're removing three bits of the final value. What order should I be doing this and why? Why am I amplifying the noise to the point where it's a problem? - Robin Green. |
From: James R. <ja...@fu...> - 2010-05-28 08:13:38
|
Are you reading the ADC three times a frame and averaging, or are you reading once per frame and then averaging over the last few frames? Is there a deadspace for the source input that you should be taking into consideration too? (Most analogue inputs have some form of dead space towards zero you should ignore, if possible.) Robin Green wrote: > Got a bit of a brain block, and I'd welcome someone with a clearer > picture of what's the correct thing to do. > > I have a hardware controller that I'm writing firmware for, > specifically debouncing button presses. That's gone fairly well by > using a word for each sample of the keystate. An interrupt timer fires > and I sample the button states, one bit per key, dumping the current > state into a ring buffer of N words. At key scanning time I AND all > the words in the buffer together and if any of the bits in each > "column" are set I register it as a keypress. So I get instant > reaction to a keydown and an N-iteration delay before the columns > clear so I can register a keyup. This deals with noisy bounces on key > depressions and releases just fine. > > I am now attempting to "debounce" an analog input. The issue is that > the ADC reads the input and returns a 10-bit value, the bottom two > bits of which are subject to noise, but that's fine as I only need a > value in the range 0..127. So my current effort is to read the ADC > value several times, sum them, divide by the number of samples and > then lose the bottom 3 bits. This works great for most values in the > range, except for the smallest values - 0, 1, 2, ... As you move the > controller through the range down to the smallest values, they exhibit > the noise and become like an unordered list. Other values where a lot > of bits flip, like the boundary between 63 and 64, also allow the > noise to propagate up to affect the value. Technically, there should > be no reason for even the smallest numbers to show the noise - only > the bottom two bits exhibit noise and we're removing three bits of the > final value. > > What order should I be doing this and why? Why am I amplifying the > noise to the point where it's a problem? > > - Robin Green. > > ------------------------------------------------------------------------------ > > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list > > |
From: Jeremiah Z. <Jer...@vo...> - 2010-05-28 16:20:02
|
Broken divider? I don't see how the noise bits can bleed into the other bits after dividing unless it's rounding up. Have you tried taking a power of two samples and shifting instead of dividing? -----Original Message----- From: Robin Green [mailto:rob...@gm...] Sent: Friday, May 28, 2010 2:24 AM To: Game Development Algorithms Subject: [Algorithms] Truncate then average? Or average then truncate? Got a bit of a brain block, and I'd welcome someone with a clearer picture of what's the correct thing to do. I have a hardware controller that I'm writing firmware for, specifically debouncing button presses. That's gone fairly well by using a word for each sample of the keystate. An interrupt timer fires and I sample the button states, one bit per key, dumping the current state into a ring buffer of N words. At key scanning time I AND all the words in the buffer together and if any of the bits in each "column" are set I register it as a keypress. So I get instant reaction to a keydown and an N-iteration delay before the columns clear so I can register a keyup. This deals with noisy bounces on key depressions and releases just fine. I am now attempting to "debounce" an analog input. The issue is that the ADC reads the input and returns a 10-bit value, the bottom two bits of which are subject to noise, but that's fine as I only need a value in the range 0..127. So my current effort is to read the ADC value several times, sum them, divide by the number of samples and then lose the bottom 3 bits. This works great for most values in the range, except for the smallest values - 0, 1, 2, ... As you move the controller through the range down to the smallest values, they exhibit the noise and become like an unordered list. Other values where a lot of bits flip, like the boundary between 63 and 64, also allow the noise to propagate up to affect the value. Technically, there should be no reason for even the smallest numbers to show the noise - only the bottom two bits exhibit noise and we're removing three bits of the final value. What order should I be doing this and why? Why am I amplifying the noise to the point where it's a problem? - Robin Green. ------------------------------------------------------------------------------ _______________________________________________ GDAlgorithms-list mailing list GDA...@li... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list This message, including any attachments, may contain privileged and/or confidential information. Any distribution or use of this email by anyone other than the intended recipient(s) is strictly prohibited. If you are not the intended recipient, please notify the sender immediately and delete all copies. Thank you. |
From: Robin G. <rob...@gm...> - 2010-05-28 17:02:12
|
OK, imagine this. We have a noisy two lowest bits, so we're removing the bottom three bits of the value and averaging four samples. If the value is around 180 we get: 10110101b + 10110100b + 10110110b + 10110101b --------------- 1011010100b >> 2 --------------- = 1011010b But if the value is close to a power of two, e.g. 64, we get unstable values: 1000000b + 0111111b + 1000001b + 0111111b ------------ 11111111b >> 2 ------------ = 0111111b The noise in the LSBs ends up bits flipping bits high up in the number in a way that truncating doesn't solve. Mr Bunnell is right, I should probably look more into numerical filtering rather than bit tricks. Duh. - Robin Green. On Fri, May 28, 2010 at 9:06 AM, Jeremiah Zanin <Jer...@vo...> wrote: > Broken divider? I don't see how the noise bits can bleed into the other bits after dividing unless it's rounding up. Have you tried taking a power of two samples and shifting instead of dividing? > |
From: Michael B. <mi...@fa...> - 2010-05-28 16:25:43
|
You probably need to filter the ADC results. I suggest a gaussian filter approximated using a moving average. Search for "Gaussian and Other Low Lag Filters" and you'll find tables of coefficients for different order filters. You won't need a ring buffer for a 1st order filter, but you will have to use the interrupt timer to get evenly spaced samples. -michael ----- Original Message ----- From: "Robin Green" <rob...@gm...> To: "Game Development Algorithms" <gda...@li...> Sent: Friday, May 28, 2010 12:24 AM Subject: [Algorithms] Truncate then average? Or average then truncate? > Got a bit of a brain block, and I'd welcome someone with a clearer > picture of what's the correct thing to do. > > I have a hardware controller that I'm writing firmware for, > specifically debouncing button presses. That's gone fairly well by > using a word for each sample of the keystate. An interrupt timer fires > and I sample the button states, one bit per key, dumping the current > state into a ring buffer of N words. At key scanning time I AND all > the words in the buffer together and if any of the bits in each > "column" are set I register it as a keypress. So I get instant > reaction to a keydown and an N-iteration delay before the columns > clear so I can register a keyup. This deals with noisy bounces on key > depressions and releases just fine. > > I am now attempting to "debounce" an analog input. The issue is that > the ADC reads the input and returns a 10-bit value, the bottom two > bits of which are subject to noise, but that's fine as I only need a > value in the range 0..127. So my current effort is to read the ADC > value several times, sum them, divide by the number of samples and > then lose the bottom 3 bits. This works great for most values in the > range, except for the smallest values - 0, 1, 2, ... As you move the > controller through the range down to the smallest values, they exhibit > the noise and become like an unordered list. Other values where a lot > of bits flip, like the boundary between 63 and 64, also allow the > noise to propagate up to affect the value. Technically, there should > be no reason for even the smallest numbers to show the noise - only > the bottom two bits exhibit noise and we're removing three bits of the > final value. > > What order should I be doing this and why? Why am I amplifying the > noise to the point where it's a problem? > > - Robin Green. > > ------------------------------------------------------------------------------ > > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list > > |
From: Tom F. <tom...@ee...> - 2010-05-28 22:19:06
|
Not sure I understand what answer you want out of the last example. The value is 63.5 +/- 0.5. You can either get back 63 or 64, but no matter how you filter it, that value will still oscillate slightly at some ADC setting. If you literally want no change if there's only a noise variance, just do a threshold trick - do the filtering the way you're doing it, and then if the filtered result is within some epsilon of the previously-returned value, keep returning that previous value. Otherwise, send the new value. It's a standard trick for things like analogue joysticks. It works OKish, but has bizarre stair-step response to slow movement (whereas a properly-filtered answer will also move slowly). TomF. > -----Original Message----- > From: Robin Green [mailto:rob...@gm...] > Sent: Friday, May 28, 2010 10:02 AM > To: Game Development Algorithms > Subject: Re: [Algorithms] Truncate then average? Or average then > truncate? > > OK, imagine this. We have a noisy two lowest bits, so we're removing > the bottom three bits of the value and averaging four samples. If the > value is around 180 we get: > > 10110101b > + 10110100b > + 10110110b > + 10110101b > --------------- > 1011010100b >> 2 > --------------- > = 1011010b > > But if the value is close to a power of two, e.g. 64, we get unstable > values: > > 1000000b > + 0111111b > + 1000001b > + 0111111b > ------------ > 11111111b >> 2 > ------------ > = 0111111b > > The noise in the LSBs ends up bits flipping bits high up in the number > in a way that truncating doesn't solve. Mr Bunnell is right, I should > probably look more into numerical filtering rather than bit tricks. > Duh. > > - Robin Green. > > > On Fri, May 28, 2010 at 9:06 AM, Jeremiah Zanin > <Jer...@vo...> wrote: > > Broken divider? I don't see how the noise bits can bleed into the > other bits after dividing unless it's rounding up. Have you tried > taking a power of two samples and shifting instead of dividing? > > > > ----------------------------------------------------------------------- > ------- > > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms- > list > No virus found in this incoming message. > Checked by AVG - www.avg.com > Version: 8.5.437 / Virus Database: 271.1.1/2861 - Release Date: > 05/28/10 06:25:00 |
From: Jon W. <jw...@gm...> - 2010-06-08 04:13:02
|
I don't get the AND thing -- you can't get instant key response that way, because you need to wait for all the words to have the bit set before it registers as a "key down." Is there more state there than the description? When it comes to the ADC, there are a few things I would think about, FWIW: 1) Put a capacitor and resistor on the analog input before the ADC. I don't care what they say; it's cheap, and very helpful! 2) You definitely want to sum first, and then divide. In fact, if you want a value from 0 .. 127, and have 10 bit numbers (0 .. 1023) coming in, I would sample four times at evenly spread intervals into a ring buffer, and calculate the output values as the sum of the last four samples, shifted right five bits. (your range will be 0 .. 4092, which divided by 32 ends up as 0 .. 127) 3) You probably also want to implement some dead space at both ends in the hardware. This means, if the summed range is 0 .. 4092, you might actually want to treat 0 .. 100 as 0, and 3093 .. 4092 as 127, and spread the rest of the interval between the two values, assuming you have efficient multiplication or division. If this is for a thumb stick (game controller style) you also want a dead space in the center, although that could potentially be applied in the software driver rather than firmware. Sincerely, jw -- Americans might object: there is no way we would sacrifice our living standards for the benefit of people in the rest of the world. Nevertheless, whether we get there willingly or not, we shall soon have lower consumption rates, because our present rates are unsustainable. On Fri, May 28, 2010 at 3:18 PM, Tom Forsyth <tom...@ee...>wrote: > Not sure I understand what answer you want out of the last example. The > value is 63.5 +/- 0.5. You can either get back 63 or 64, but no matter how > you filter it, that value will still oscillate slightly at some ADC > setting. > > If you literally want no change if there's only a noise variance, just do a > threshold trick - do the filtering the way you're doing it, and then if the > filtered result is within some epsilon of the previously-returned value, > keep returning that previous value. Otherwise, send the new value. It's a > standard trick for things like analogue joysticks. It works OKish, but has > bizarre stair-step response to slow movement (whereas a properly-filtered > answer will also move slowly). > > TomF. > > > > -----Original Message----- > > From: Robin Green [mailto:rob...@gm...] > > Sent: Friday, May 28, 2010 10:02 AM > > To: Game Development Algorithms > > Subject: Re: [Algorithms] Truncate then average? Or average then > > truncate? > > > > OK, imagine this. We have a noisy two lowest bits, so we're removing > > the bottom three bits of the value and averaging four samples. If the > > value is around 180 we get: > > > > 10110101b > > + 10110100b > > + 10110110b > > + 10110101b > > --------------- > > 1011010100b >> 2 > > --------------- > > = 1011010b > > > > But if the value is close to a power of two, e.g. 64, we get unstable > > values: > > > > 1000000b > > + 0111111b > > + 1000001b > > + 0111111b > > ------------ > > 11111111b >> 2 > > ------------ > > = 0111111b > > > > The noise in the LSBs ends up bits flipping bits high up in the number > > in a way that truncating doesn't solve. Mr Bunnell is right, I should > > probably look more into numerical filtering rather than bit tricks. > > Duh. > > > > - Robin Green. > > > > > > On Fri, May 28, 2010 at 9:06 AM, Jeremiah Zanin > > <Jer...@vo...> wrote: > > > Broken divider? I don't see how the noise bits can bleed into the > > other bits after dividing unless it's rounding up. Have you tried > > taking a power of two samples and shifting instead of dividing? > > > > > > > ----------------------------------------------------------------------- > > ------- > > > > _______________________________________________ > > GDAlgorithms-list mailing list > > GDA...@li... > > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > > Archives: > > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms- > > list > > No virus found in this incoming message. > > Checked by AVG - www.avg.com > > Version: 8.5.437 / Virus Database: 271.1.1/2861 - Release Date: > > 05/28/10 06:25:00 > > > > ------------------------------------------------------------------------------ > > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list > |
From: Robin G. <rob...@gm...> - 2010-06-08 05:38:52
|
On Mon, Jun 7, 2010 at 9:12 PM, Jon Watte <jw...@gm...> wrote: > I don't get the AND thing -- you can't get instant key response that way, > because you need to wait for all the words to have the bit set before it > registers as a "key down." Is there more state there than the description? The idea comes from Jack Ganssle's article on Software Debouncers: http://www.ganssle.com/debouncing-pt2.htm > When it comes to the ADC, there are a few things I would think about, FWIW: > 1) Put a capacitor and resistor on the analog input before the ADC. I don't > care what they say; it's cheap, and very helpful! An R/C Network on the input, isn't that just another form of hysteresis? And one that's subject to the astonishing inaccuracies of electrolytic caps? > 2) You definitely want to sum first, and then divide. In fact, if you want a > value from 0 .. 127, and have 10 bit numbers (0 .. 1023) coming in, I would > sample four times at evenly spread intervals into a ring buffer, and > calculate the output values as the sum of the last four samples, shifted > right five bits. (your range will be 0 .. 4092, which divided by 32 ends up > as 0 .. 127) This was exactly the form that caused the problem around values with a lot of bits set. You're trying to discard the random bottom bits, but you include their influence by summing before removing them by truncation. The solution I ended up using records the previous ADC value in it's full 10-bit value. A new ADC value has to exceed this old sample by more than the Hysteresis amount before I allow it through to truncation. The insight was to keep the comparison values at full resolution, discard values below the H threshold and truncate the samples only just before they are used. Values are now rock solid. The problem was that the premature truncation was discarding important information. > 3) You probably also want to implement some dead space at both ends in the > hardware. This means, if the summed range is 0 .. 4092, you might actually > want to treat 0 .. 100 as 0, and 3093 .. 4092 as 127, and spread the rest of > the interval between the two values, assuming you have efficient > multiplication or division. If this is for a thumb stick (game controller > style) you also want a dead space in the center, although that could > potentially be applied in the software driver rather than firmware. Linear POTs seem to have dead space at either end built in, but the dead center is a good idea - but should it be circular or square? - Robin Green. |
From: <pad...@ob...> - 2010-06-08 13:43:29
|
Adding an RC (effective low pass filter) is a trick that works because of the TTL (or CMOS) thresholds. Bounce can be seen as high frequency contamination. Hysteresis is not a phenonemon that concerns us, nor is it a significant property of RC which can be considered linear for all but the most pathological components. However, of course the lowpass adds a small delay to all operations, since the rise time is finite. Since bounce can be considered above a couple of hundred Hz, the slugging time of the switch will be at worst a few milliseconds. (Nothing that ever bothered us on old consoles) With regard to the LSB innaccuracy: I'm sorry that I didn't fully understand the OP question, but the first thing that popped in to my mind was that this is a dither problem. Dither only works when you add a _known_ noise source (predictable in spectral terms) to swamp the (unknown) LSB errors. Andy On 08 June 2010 at 07:38 Robin Green <rob...@gm...> wrote: > On Mon, Jun 7, 2010 at 9:12 PM, Jon Watte <jw...@gm...> wrote: > > I don't get the AND thing -- you can't get instant key response that way, > > because you need to wait for all the words to have the bit set before it > > registers as a "key down." Is there more state there than the description? > > The idea comes from Jack Ganssle's article on Software Debouncers: > > http://www.ganssle.com/debouncing-pt2.htm > > > > When it comes to the ADC, there are a few things I would think about, FWIW: > > 1) Put a capacitor and resistor on the analog input before the ADC. I don't > > care what they say; it's cheap, and very helpful! > > An R/C Network on the input, isn't that just another form of > hysteresis? And one that's subject to the astonishing inaccuracies of > electrolytic caps? > > > > 2) You definitely want to sum first, and then divide. In fact, if you want a > > value from 0 .. 127, and have 10 bit numbers (0 .. 1023) coming in, I would > > sample four times at evenly spread intervals into a ring buffer, and > > calculate the output values as the sum of the last four samples, shifted > > right five bits. (your range will be 0 .. 4092, which divided by 32 ends up > > as 0 .. 127) > > This was exactly the form that caused the problem around values with a > lot of bits set. You're trying to discard the random bottom bits, but > you include their influence by summing before removing them by > truncation. > > The solution I ended up using records the previous ADC value in it's > full 10-bit value. A new ADC value has to exceed this old sample by > more than the Hysteresis amount before I allow it through to > truncation. The insight was to keep the comparison values at full > resolution, discard values below the H threshold and truncate the > samples only just before they are used. Values are now rock solid. > > The problem was that the premature truncation was discarding important > information. > > > 3) You probably also want to implement some dead space at both ends in the > > hardware. This means, if the summed range is 0 .. 4092, you might actually > > want to treat 0 .. 100 as 0, and 3093 .. 4092 as 127, and spread the rest of > > the interval between the two values, assuming you have efficient > > multiplication or division. If this is for a thumb stick (game controller > > style) you also want a dead space in the center, although that could > > potentially be applied in the software driver rather than firmware. > > Linear POTs seem to have dead space at either end built in, but the > dead center is a good idea - but should it be circular or square? > > - Robin Green. > > ------------------------------------------------------------------------------ > ThinkGeek and WIRED's GeekDad team up for the Ultimate > GeekDad Father's Day Giveaway. ONE MASSIVE PRIZE to the > lucky parental unit. See the prize list and enter to win: > http://p.sf.net/sfu/thinkgeek-promo > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list |
From: Jon W. <jw...@gm...> - 2010-06-08 18:09:47
|
> > > 2) You definitely want to sum first, and then divide. In fact, if you > want a > > value from 0 .. 127, and have 10 bit numbers (0 .. 1023) coming in, I > would > > sample four times at evenly spread intervals into a ring buffer, and > > calculate the output values as the sum of the last four samples, shifted > > right five bits. (your range will be 0 .. 4092, which divided by 32 ends > up > > as 0 .. 127) > > This was exactly the form that caused the problem around values with a > lot of bits set. You're trying to discard the random bottom bits, but > you include their influence by summing before removing them by > truncation. > > Signal theory says you can't possibly be more noisy after summing and truncating than you were before. There is no way for the low 2 bits of input to "leak" into higher values on the output. There *is* a way for the outcome to toggle between, say, 63 and 64, at your sample rate, if there is a signal component present at (or close to) your Nyquist frequency. There's basically nothing you can do against that. And it will "flip the bits" for all the bits -- but, seen as a value, that's not really a problem. Basically, what I hear you saying is that, when you go from 10 bits input to 7 bits data using oversampling and summing, you will still get noise in the lowest bit of the 7-bit data, which means that you have at least 4 noisy bits in the input, not just two. The way to fix that is to make the input less noisy. There are many things that can make the input noisy. The input to the ADC is one -- that's where you want a good filter if possible (the RC was one suggestion which is cheap, there are better :-). Perhaps your ADC already has an adjustable anti-aliasing filter, in which case you can just lower the cut-off of that. The reference voltage for the ADC is another source of noise. If you can't get that steady, you're in trouble. Again, some RC goodness on that input might help. Another option is to apply real DSP. Summing values just implements a simple FIR filter with very shallow slope. You can get better response by designing a four-pole IIR filter and feeding it the inputs (assuming you can get integer quantization to stay stable -- else do it as two bi-quad filters). Set the cut-off at something significantly lower than your sampling rate. For example, if you sample at 4 kHz (4 samples per tick for USB 1 ms tick rate, say), then you can set the cut-off frequency (-3 dB point) to 200 Hz and nobody will feel any lag. But, really -- 7 bits is such low dynamic range (~43 dB), it should be easily addressable using cheap components. Sincerely, jw |