Can boxcar averaging cause rounding error?

[Nominal Animal]

A right shift is a division with floor rounding. In order to correctly round you need to add half the divider to the start value.

Code: [Select]

value = (value+8)>>4

Is this true for negative values?  :popcorn:

Good point.

It rounds halfway upwards, which is towards zero for negative values.

One needs to subtract half the divisor for negative values for rounding halfway away from zero; i.e.
    value = (value < 0) ? ((value - 8) >> 4) : ((value + 8) >> 4);

Note that this applies to all division operations, not just arithmetic shift right:
    value = (n < 0) ? (n - d/2) / d : (n + d/2) / d;

This even works for negative divisors d, noting that the addend (±d/2, which I typically call half) has the same sign as the divisor if n is positive, negated if n is negative.

For integer calculations, this works best when half itself is truncated towards zero (no rounding applied), so that looking at the results of all possible numerators, you'll have |d| zero results centered at n=0 (|d|-1 if |d| is even), and then |d| consecutive same results in both directions.  For example, for d=3, (n < 0) ? (n-1)/3 : (n+1)/3 yields results -3, -2, -2, -2, -1, -1, -1, 0, 0, 0, 1, 1, 1, 2, 2, 2, 3 for n=-8..+8.  For d=4, (n<0) ? (n-2)/4 : (n+2)/4 yields -2, -1, -1, -1, -1, 0, 0, 0, 1, 1, 1, 1, 2 for n=-6..+6.


For a sequence of values, you add the half to the sum, not to each term:
    sum = t1 + t2 + t3 + t4 + t5 + t6 + t7 + t8 + t9 + t10 + t11 + t12 + t13 + t14 + t15 + t16;
    avg = (sum < 0) ? (sum - 8)/16 : (sum + 8)/16;
Mathematically,
$$\left\lceil \frac{1}{N} \sum_{i=1}^N t_i \right\rfloor = \left\lfloor \frac{1}{N} \left( H + \sum_{i=1}^N t_i \right) \right \rfloor, \quad H = \pm \left\lfloor \frac{N}{2} \right\rfloor$$
where \$H\$ is negated if and only if the sum is negative.

If you do the division and rounding first, you lose precision, and introduce excess rounding error.  It is easiest to understand if you consider decimal numbers rounded to nearest integer.  \$\lceil 0.3 + 0.3 + 0.3 + 0.3 + 0.3 + 0.3 \rfloor = 2\$, but \$\lceil 0.3 \rfloor + \lceil 0.3 \rfloor + \lceil 0.3 \rfloor + \lceil 0.3 \rfloor + \lceil 0.3 \rfloor + \lceil 0.3 \rfloor  = 0\$.

[Andy Watson]

Unless there is a need for the averaged value I would skip the "dividing" and perform the limit checks against \$16 \times n\$

[Nominal Animal]

Unless there is a need for the averaged value I would skip the "dividing" and perform the limit checks against \$16 \times n\$

That way no rounding is needed either.

The only downside is that you need to compare against the sum, which is 4 bits larger than the individual terms.
If each term fits in 0..15 or -8..7, then 8-bit sum and limit values suffice.
If each term fits in 0..4095 or -2048..2047, then 16-bit sum and limit values suffice.
If each term fits in 0..1048575 or -524288..524287, then 24-bit sum and limit values suffice.
If each term fits in 0..268435455 or -134217728..134217727, then 32-bit sum and limit values suffice, and so on.

[Circlotron]

Unless there is a need for the averaged value I would skip the "dividing" and perform the limit checks against \$16 \times n\$

That would work in a way, but seeing the limit check is +/- 1 in both cases, the averaged /16 value gives me some low pass filtering, so any frequency jitter in the sampled pulses won't cause as much dithering about the threshold. I would effectively have a 16 count dead zone that drifts up or down.

I suppose I could achieve much the same outcome by using the undivided total and a bit of hysteresis on the limit, but the idea of averaging appealed to me. Some might say that subjectivity has no place in software, others might disagree. If two different approaches give the same end result with no downside either way, then I choose the one that gives the most satisfaction. 

[Circlotron]

A right shift is a division with floor rounding. In order to correctly round you need to add half the divider to the start value.

Code: [Select]

value = (value+8)>>4

Having thought about this overnight, the purpose of adding half the divisor becomes clear. It seems comparable to how an A/D converter assigns an analog value of say 3 to the digital span of 2.5 to 3.5 so it is centered on 3. It is offset by 1/2 LSB, same as the added 8 count is divided down to effectively 0.5 count in my case.

[jpanhalt]

In Assembly you should have a register that does what STATUS in PIC does.  That is, flags for carry, zero, and maybe other things, like DC (carry between nibbles).

Adding one half of the divisor to the sum before dividing is one way to ensure rounding.  Look at the following example:

1) In decimal, add 3.0+3.5+4.0+4.5 = 15.  The average is 3.75, so you round to 4 to avoid the decimal.

2) d.15 +2 = 17.  Divide by 4 = 4.25 --> 4 rounded .

3) d.15 = b'1111'.  Rotate right once --> b'0111' w/ carry =1.  Rotate again to divide by 4 -->b'0011' w/ carry =1.  Now add carry to the result = b'0100' = 4  .  Same answer.  Why? The bit in carry after 2 rotations is the 2^1 bit (i.e., 1/2 the divisor). 

Coding in Assembly is pretty easy either way.  I don't do C, but have been told using the STATUS register is not as clear cut.
 

[S. Petrukhin]

It rounds halfway upwards, which is towards zero for negative values.

It seems to me that you have forgotten the format of negative numbers. 
The operator ">>" (shr) for a negative number will shift the sign and the number will cease to be negative.

[Nominal Animal]

It rounds halfway upwards, which is towards zero for negative values.

It seems to me that you have forgotten the format of negative numbers. 
The operator ">>" (shr) for a negative number will shift the sign and the number will cease to be negative.

No; it is implementation defined in the C standard (C99-C23 6.5.7p5).   GCC, SDCC, Clang, ICC, and all other C compilers I've used implement (v >> n) as an arithmetic right shift for signed integer types of v, shifting in copies of the sign bit, iff the target architecture has an arithmetic right shift operation.  It does mean that with these compilers (and in e.g. Bash), (-1)>>1 == -1, which can be confusing.

I haven't seen any C compilers that shifted zero bits in when using >> for negative signed integer types, but the ones I've checked all do have separate arithmetic and binary right shift instructions (and exact-width binary integer types with signed integers using two's complement format).

[S. Petrukhin]

No; it is implementation defined in the C standard (C99-C23 6.5.7p5).   GCC, SDCC, Clang, ICC, and all other C compilers I've used implement (v >> n) as an arithmetic right shift for signed integer types of v, shifting in copies of the sign bit, iff the target architecture has an arithmetic right shift operation.  It does mean that with these compilers (and in e.g. Bash), (-1)>>1 == -1, which can be confusing.

I haven't seen any C compilers that shifted zero bits in when using >> for negative signed integer types, but the ones I've checked all do have separate arithmetic and binary right shift instructions (and exact-width binary integer types with signed integers using two's complement format).

Thank you!
I didn't know the subtleties of С.
There is no >> in Pascal (where I live), there is an explicit shr, which is an ordinary bit shift.

[SiliconWizard]

Bitwise manipulation of signed integers - unless you have a good rationale to do it, and know/can rely on well-defined behaviors of bitwise operators on them in the language you use - is IMHO a bad idea in most cases anyway.

[jpanhalt]

Bitwise manipulation of signed integers - unless you have a good rationale to do it, and know/can rely on well-defined behaviors of bitwise operators on them in the language you use - is IMHO a bad idea in most cases anyway.

Probably wise, but my routine in PIC Assembly for division (rotate and subtract, modified from a PICList link) involves negative numbers to avoid having to undo a subtraction.  I do not use the routine when the dividend or divisor are negative.  I haven't tested it in that situation but suspect it would fail.  "Most" is key.  In this thread, the TS has said the numbers are all positive.

[mikerj]

Bitwise manipulation of signed integers - unless you have a good rationale to do it, and know/can rely on well-defined behaviors of bitwise operators on them in the language you use - is IMHO a bad idea in most cases anyway.

Probably wise, but my routine in PIC Assembly for division (rotate and subtract, modified from a PICList link) involves negative numbers to avoid having to undo a subtraction.  I do not use the routine when the dividend or divisor are negative.  I haven't tested it in that situation but suspect it would fail.  "Most" is key.  In this thread, the TS has said the numbers are all positive.

To get an arithmetic right shift on the PIC, first rotate the MSB left one bit but don't write the result back to the variable, then perform the right shifts on your value:

Code: [Select]

RLF myval_msb,W ; put MS bit into carry
RRF myval_msb,F ; Shift MSB right, sign bit is shifted from carry into bit 7
RRF myval_lsb,F ; Shift LSB right
If you clear carry first you get a logical shift, which will not work as a division on negative values.

[jpanhalt]

Microchip has added arithmetic shifts to its 8-bit instruction set.  See: http://datasheet.elcodis.com/pdf/16/18/161877/pic16f1936-iss.pdf  (Apologies for not being a direct link. MCC seems to want to hide it behind marketing and sign-in requirements)

The code I mentioned for division is for positive integers and can me easily modified for any number of bytes.  I have not tried it beyond 32-bit by 32-bit division.  Usually, I us it for 32-bit by 16-bit or fewer division.