I didn't read all 11 pages of this thread, only the first couple. Here's a portable branch-free approach:

int n = <10-bit input>;
n = (n ^ 0x200) - 0x200;

This converts it to offset-binary, then subtracts the zero bias. It is completely portable (to satisfy purists here) and works regardless of how wide an int is (it'll of course work for int16_t, int32_t, or whatever). It should be just as efficient for AVR, since both instructions don't touch the lower byte.

Cool solution. Edit: Seems like GCC (also avr-gcc) optimize my solution and this solution to to same 3 assembler instructions AVR, or 2 instructions on an IA64.

Have to make such binary operations always clear by examples:

10-bit signed number is b000000ji hgfedcba

Zero or positive number has j=0, negative number has j=1.

Example for zero or positive number:
value >= 0 b0000000i hgfedcba
constant 0x200 b00000010 00000000
XOR result b0000001i hgfedcba
constant 0x200 b00000010 00000000
minus result b0000000i hgfedcba

Example for negative number:
value < 0 b0000001i hgfedcba
constant 0x200 b00000010 00000000
XOR result b0000000i hgfedcba
constant 0x200 b00000010 00000000
minus result b1111111i hgfedcba

Yea, seems to work great!

In the beginning was the Word, and the Word was with God, and the Word was God.

Posted by oloftangrot: Fri. Nov 7, 2014 - 11:50 AM

1

2

3

4

5

Total votes: 0

So here is an additional bonus weed end problem for you all. Find the optimal solution to compute the average of 10 consecutive samples of the 10 bit signed numbers and give the result as a 16 bit signed number.

By average I ment arithmetic mean. Of course input data should allow arbitrary values just as if the input is a bit noisy real time AD-converted signal. Would it be best to convert to the 16-bit signed format first before adding a new number or is it possible to have some other solution that also performs better? For myself I guess rehab is the best solution.

A simple moving average (SMA) and weighted moving average would need to store a window's worth of samples but an exponential moving average (EMA) requires only the previous sample. I imagine that's what skeeve is referring to by "decaying average".

Often a decaying average is enough. But if you do not want to have any historical data after a given number of sampls, the simple moving average is better suited:

#define FILTER_SIZE 64
/* Simple Moving Average filter:
inData is assumed to be in the range of [-512; 511] (= 10bit, sign extended);
the return value is scaled by the factor FILTER_SIZE=64 related to the input data */
int16_t filterSMA(int16_t inData)
{
static int16_t buffer[FILTER_SIZE];
static int16_t average;
static uint16_t bufferIndex;
static uint8_t startCounter;

/* add the latest value to the average */
average += inData;
/* remove oldest value from the average */
average -= buffer[bufferIndex];

/* store to buffer */
buffer[bufferIndex] = inData;
bufferIndex++;
if (bufferIndex>=FILTER_SIZE)
{
bufferIndex = 0;
}

if (startCounter<FILTER_SIZE)
{ /* special handling, if buffer is not completely filled (not settled) */
startCounter++;
return average*FILTER_SIZE/startCounter;
}
else
{
/* buffer is filled, filter is settled */
return average;
}
}

A decaying filter would look like this:

#define FILTER_STRENGTH 16
/* Decaying filter:
inData is assumed to be in the range of [-512; 511] (= 10bit, sign extended);
the return value is scaled by the factor FILTER_SIZE=64 related to the input data;
Watch out for remaining offsets! Watch out for overflows, if FILTER_STRENGTH is too big! */
int16_t filterDec(int16_t inData)
{

if (startCounter<1)
{ /* first value is the initialization for the average */
startCounter++;
average = inData*FILTER_SIZE;
}
temp = (int32_t)average*(FILTER_STRENGTH-1)+inData*FILTER_SIZE;
average = (int16_t)(temp/FILTER_STRENGTH);
return average;
}

The startCounter thing can be omitted, if you do not care, what happens during start-up.

Due to the integer division, the decaying filter will have some unwanted rounding effects.

If you have the memory, I propose the SMA filter, which actually needs only plus and minus.

In the beginning was the Word, and the Word was with God, and the Word was God.

So, let's take OP's case, with a "fixed" problem of AVR8 10-bit ADC result, to a 16-bit signed int. If the app is like mine, with continuous ADC sampling at, say, 200us each/10ksps, the sequence I proposed in #3 is less than a microsecond. How many cycles will your routine take? Hmmm--with CodeVision and Studio6.2 simulator, I get 2506 cycles. 300us at 8MHz. (Remember that I might want to do this in my app every 200us, and do a bunch of other stuff in my app as well...)

EDIT: Making the routine not inline cut the cycle count to a more-expected 150. 20us at 8MHz. [It could be a simulator artifact but a quick run-through indicated a possible situation with ... wait for it ... SIGN EXTENDING the shift count in the loop. LOL]

The very practical AVR8 solution from #3 is SBRC/ORI. 2 cycles if the operand(s) are in high registers.

Thus the objections to the political-correctness. But, I respect your beliefs. Just sayin'.

You can put lipstick on a pig, but it is still a pig.

I've never met a pig I didn't like, as long as you have some salt and pepper.

Compare the "politically correct" bitfield solution with the simple sequence originally proposed by us pagans:

https://www.avrfreaks.net/comment...

Same SBRC/ORI in both CodeVision and GCC.

You can put lipstick on a pig, but it is still a pig.

I've never met a pig I didn't like, as long as you have some salt and pepper.

- Log in or register to post comments

TopA re-read of the thread was "interesting". ;)

You can put lipstick on a pig, but it is still a pig.

I've never met a pig I didn't like, as long as you have some salt and pepper.

- Log in or register to post comments

TopI didn't read all 11 pages of this thread, only the first couple. Here's a portable branch-free approach:

This converts it to offset-binary, then subtracts the zero bias. It is completely portable (to satisfy purists here) and works regardless of how wide an int is (it'll of course work for int16_t, int32_t, or whatever). It should be just as efficient for AVR, since both instructions don't touch the lower byte.

- Log in or register to post comments

TopCool solution. Edit: Seems like GCC (also avr-gcc) optimize my solution and this solution to to same 3 assembler instructions AVR, or 2 instructions on an IA64.

- Log in or register to post comments

TopIndeed. Thank you @christop! This is now and forever in my toolbox.

A neat link to other 'bit twiddling' hacks, too...

"Experience is what enables you to recognise a mistake the second time you make it."

"Good judgement comes from experience. Experience comes from bad judgement."

"Wisdom is always wont to arrive late, and to be a little approximate on first possession."

"When you hear hoofbeats, think horses, not unicorns."

"Fast. Cheap. Good. Pick two."

"We see a lot of arses on handlebars around here." - [J Ekdahl]

- Log in or register to post comments

TopHave to make such binary operations always clear by examples:

10-bit signed number is b000000ji hgfedcba

Zero or positive number has j=0, negative number has j=1.

Example for zero or positive number:

value >= 0 b0000000i hgfedcba

constant 0x200 b00000010 00000000

XOR result b0000001i hgfedcba

constant 0x200 b00000010 00000000

minus result b0000000i hgfedcba

Example for negative number:

value < 0 b0000001i hgfedcba

constant 0x200 b00000010 00000000

XOR result b0000000i hgfedcba

constant 0x200 b00000010 00000000

minus result b1111111i hgfedcba

Yea, seems to work great!

In the beginning was the Word, and the Word was with God, and the Word was God.

- Log in or register to post comments

TopThis has been really interesting, folks.

Not being steeped in the mysteries of signed binary arithmetic, it has been a great learning event. Appreciate everyone's input.

Jim

Jim Wagner Oregon Research Electronics, Consulting Div. Tangent, OR, USA http://www.orelectronics.net

- Log in or register to post comments

TopSo here is an additional bonus weed end problem for you all. Find the optimal solution to compute the average of 10 consecutive samples of the 10 bit signed numbers and give the result as a 16 bit signed number.

- Log in or register to post comments

TopIt is not clear, which average you mean, for example

- block average,

- moving average,

- average, where the newer values count more than the older

=> FIR or IIR filter.

So, instead of solving the "weed end" problem , I would start with the week end problem first:

compute the moving average of 64 consecutive samples of 10 bit signed numbers and give the result as a 16 bit signed number.

Samples of 511 should lead to 32702,

samples of -512 should lead to 32768.

In the beginning was the Word, and the Word was with God, and the Word was God.

- Log in or register to post comments

TopBy average I ment arithmetic mean. Of course input data should allow arbitrary values just as if the input is a bit noisy real time AD-converted signal. Would it be best to convert to the 16-bit signed format first before adding a new number or is it possible to have some other solution that also performs better? For myself I guess rehab is the best solution.

- Log in or register to post comments

TopNeither problem is terribly difficult.

For the first, the hard part is deciding how to divide by ten.

Should one be fussy about rounding?

For the second, the main problem is storage.

One will have to store 64 samples.

That is 80 or 128 bytes.

If one has the resources, the problem is not hard.

For such things, I'm more likely to use a decaying average.

Iluvatar is the better part of Valar.

- Log in or register to post comments

TopA simple moving average (SMA) and weighted moving average would need to store a window's worth of samples but an exponential moving average (EMA) requires only the previous sample. I imagine that's what skeeve is referring to by "decaying average".

- Log in or register to post comments

TopCorrect.

Iluvatar is the better part of Valar.

- Log in or register to post comments

TopOften a decaying average is enough. But if you do not want to have any historical data after a given number of sampls, the simple moving average is better suited:

#define FILTER_SIZE 64

/* Simple Moving Average filter:

inData is assumed to be in the range of [-512; 511] (= 10bit, sign extended);

the return value is scaled by the factor FILTER_SIZE=64 related to the input data */

int16_t filterSMA(int16_t inData)

{

static int16_t buffer[FILTER_SIZE];

static int16_t average;

static uint16_t bufferIndex;

static uint8_t startCounter;

/* add the latest value to the average */

average += inData;

/* remove oldest value from the average */

average -= buffer[bufferIndex];

/* store to buffer */

buffer[bufferIndex] = inData;

bufferIndex++;

if (bufferIndex>=FILTER_SIZE)

{

bufferIndex = 0;

}

if (startCounter<FILTER_SIZE)

{ /* special handling, if buffer is not completely filled (not settled) */

startCounter++;

return average*FILTER_SIZE/startCounter;

}

else

{

/* buffer is filled, filter is settled */

return average;

}

}

A decaying filter would look like this:

#define FILTER_STRENGTH 16

/* Decaying filter:

inData is assumed to be in the range of [-512; 511] (= 10bit, sign extended);

the return value is scaled by the factor FILTER_SIZE=64 related to the input data;

Watch out for remaining offsets! Watch out for overflows, if FILTER_STRENGTH is too big! */

int16_t filterDec(int16_t inData)

{

static int16_t average;

static uint8_t startCounter;

int32_t temp;

if (startCounter<1)

{ /* first value is the initialization for the average */

startCounter++;

average = inData*FILTER_SIZE;

}

temp = (int32_t)average*(FILTER_STRENGTH-1)+inData*FILTER_SIZE;

average = (int16_t)(temp/FILTER_STRENGTH);

return average;

}

The startCounter thing can be omitted, if you do not care, what happens during start-up.

Due to the integer division, the decaying filter will have some unwanted rounding effects.

If you have the memory, I propose the SMA filter, which actually needs only plus and minus.

In the beginning was the Word, and the Word was with God, and the Word was God.

- Log in or register to post comments

TopI skimmed the thread and did not see the obvious way of sign extending in C -- sorry if I missed it.

static inline int8_t sign_extend8(uint8_t val, uint8_t bits)

{

uint8_t shift = 7 - bits;

return (int8_t)(val << shift) >> shift;

}

static inline int16_t sign_extend16(uint16_t val, uint8_t bits)

{

uint8_t shift = 15 - bits;

return (int16_t)(val << shift) >> shift;

}

However since your value is 10 bits and we're on an LE 8bit MCU the fastest option is:

uint8_t *arr = &val;

arr[1] = sign_extend8(arr[1], 2);

Which should take just the 2 cycles, one LSL and one ASR, assuming the value is already in registers.

On your other questions, no the bitwise ops (|, &, ^) do not care about signed vs unsigned.

- Log in or register to post comments

TopSome might prove to be a worthy of seeing other might not.

- Log in or register to post comments

TopLOL -- I thought we killed this pig.

So, let's take OP's case, with a "fixed" problem of AVR8 10-bit ADC result, to a 16-bit signed int. If the app is like mine, with continuous ADC sampling at, say, 200us each/10ksps, the sequence I proposed in #3 is less than a microsecond. How many cycles will your routine take? Hmmm--with CodeVision and Studio6.2 simulator, I get 2506 cycles. 300us at 8MHz. (Remember that I might want to do this in my app every 200us, and do a bunch of other stuff in my app as well...)

EDIT: Making the routine not inline cut the cycle count to a more-expected 150. 20us at 8MHz. [It could be a simulator artifact but a quick run-through indicated a possible situation with ... wait for it ... SIGN EXTENDING the shift count in the loop. LOL]

The very practical AVR8 solution from #3 is SBRC/ORI. 2 cycles if the operand(s) are in high registers.

Thus the objections to the political-correctness. But, I respect your beliefs. Just sayin'.

You can put lipstick on a pig, but it is still a pig.

I've never met a pig I didn't like, as long as you have some salt and pepper.

- Log in or register to post comments

TopAccording to the C99 standard, the result of the >> operator is implementation-defined for signed negative numbers.

This means, that we can not rely on the experience, that an arithmetic shift must be used (MSB is copied).

Also, reinterpretting the int16_t value as an array of two uint8_t values makes the code dependent on the endianess of the machine.

So, I would prefer the solution of comments #3 or #104.

In the beginning was the Word, and the Word was with God, and the Word was God.

- Log in or register to post comments

Topskotti wrote:That said, the algorithm is really ugly and a tad obscure.

I would change the presentation a little:

#104 would be good on a machine for which the absence of conditional code mattered.

Iluvatar is the better part of Valar.

- Log in or register to post comments

Top## Pages