Average value of 1000 sample

[Karamel]

Hi,

I am working on msp430 microcontroller's adc unit. I am taking 12 bit, 1000 samples and how can I calculate their average value? If I try to add 1000 samples, variable will be overflow.    I didn't find any idea to solve this problem. How can I do this?

[jbb]

Hi

I think you mean the sum value.  If you use a 32 bit integer you should be OK.

e.g.

#include "stdint.h"

function()
{
   int32_t bigsum = 0;
   for (....)
   {
      bigsum += getAdc()
   }
}

FYI, unless you need exactly 1000 samples, working with 1024 might allow for easier maths in future steps (e.g. dividing by 1024 is the same as shifting right by 10).

[Karamel]

Hi

I think you mean the sum value.  If you use a 32 bit integer you should be OK.

e.g.

#include "stdint.h"

function()
{
   int32_t bigsum = 0;
   for (....)
   {
      bigsum += getAdc()
   }
}

FYI, unless you need exactly 1000 samples, working with 1024 might allow for easier maths in future steps (e.g. dividing by 1024 is the same as shifting right by 10).

I have written mistakely, not absolute, "average of 1000 samples. Each value is 12 bit"

[frozenfrogz]

You could calculate a rolling average, or - if you have all 1000 samples written to a buffer - collapse the buffer down pair-wise.
https://en.wikipedia.org/wiki/Moving_average

[Bruce Abbott]

If I try to add 1000 samples, variable will be overflow...

I have written mistakely, not absolute, "average of 1000 samples. Each value is 12 bit"

Not making sense. Show us your code.

[Rerouter]

I think he misunderstood your approach,

If its a static averaging, e.g. you want to measure 1000 samples, and then average them:
Using a 32 bit variable, you add all your samples up, then divide by the number of samples to get your result,
a cleaner approach to this is likely to sum each value in to a total value as your sampling them so you dont need to allocate room for 1000 samples,
e.g. Total = Total + Sample

If its a moving average, then there are a few ways you can implement it, as shown on that wikipedia entry linked above, and it will come down to how you want it to behave, e.g. do you want the result of the division rounded to the nearest digit, or just the integer your on, do you want newer values to have more precedence over older values, do you have room to store 1000 12 bit numbers if you want to do a ring buffer style approach so you know it is always the exact average with no small error introduced by rounding or lack of precision.

equally some of the approached are "computationally expensive" but it comes down to your requirements,

[sokoloff]

Hi,

I am working on msp430 microcontroller's adc unit. I am taking 12 bit, 1000 samples and how can I calculate their average value? If I try to add 1000 samples, variable will be overflow.    I didn't find any idea to solve this problem. How can I do this?

If you have int32 or uint32 available on your platform, use that.

Because you're asking the question, I'll assume that you only have 16-bit numbers available.

Try something like this (which does an average of 1024 samples):

It holds the accumulator (the running sum) in 2 16-bit integers, one the high half and one the low half.

Code: [Select]

#include <stdio.h>
#include <stdlib.h>

typedef short          int16;
typedef unsigned short uint16;

typedef int            int32;
typedef unsigned int   uint32;


void test()
{
  // These variables are what you have on a 16 bit platform
  uint16 high, low;

  // These variables are what you have on a 32 bit platform
  // I'm using them here just to prove that the 16 bit math works
  // In your application, you would only use the uint16s
  uint32 sum, test;

  high = 0, low = 0;
  sum = 0;
  int i;
  for (i = 0; i < 1024; i++) {
    // Use rand() if you don't have arc4random on your platform
    int16 new_measurement = arc4random() % (1 << 12);
    uint16 old_low;

    /*if ((i % 64) == 0)
      printf("Meas: %d\n", new_measurement);*/
   
    sum = sum + new_measurement;

    old_low = low;
    low = low + new_measurement;
    if (old_low > low)
      high++;
   
  }
  test = (((uint32) high) << 16) + (uint32) low;
  printf("After %d additions,  sum = %8d (0x%04x)\n", i, sum, sum);
  printf("After %d additions, test = %8d (0x%04x)\n", i, test, test);
  printf("After %d additions,  low = %8d (0x%04x)\n", i, low, low);
  printf("After %d additions, high = %8d (0x%04x)\n", i, high, high);

  // avg1 is computed using the 32 bit accumulator (testing)
  uint16 avg1 = sum / i;

  // avg2 is computed using the 2 16 bit accumulators (real code)
  // Shift right by 10 (divide by 1024)
  // Take 6 bits from the low
  // Take 10 bits from the high
  uint16 avg2 = low >> 10 | ((high & 0x05ff) << 6);

  printf("After %d additions, avg1 = %8d (0x%04x)\n", i, avg1, avg1);
  printf("After %d additions, avg2 = %8d (0x%04x)\n", i, avg2, avg2);
 
}

int main()
{
 
  printf("Sanity check the type sizes.\n");

  printf("sizeof(int16) = %ld\n", sizeof(int16));
  printf("sizeof(uint16) = %ld\n", sizeof(uint16));
  printf("sizeof(int32) = %ld\n", sizeof(int32));
  printf("sizeof(uint32) = %ld\n", sizeof(uint32));
  printf("sizeof(long) = %ld\n", sizeof(long));

  if (sizeof(int16) != 2)
    printf("Halting because sizeof(int16) is not 2.\n");
  if (sizeof(uint16) != 2)
    printf("Halting because sizeof(uint16) is not 2.\n");
  if (sizeof(int32) != 4)
    printf("Halting because sizeof(int32) is not 4.\n");
  if (sizeof(uint32) != 4)
    printf("Halting because sizeof(uint32) is not 4.\n");

  test();
  return 0;
}


[edpalmer42]

I seem to be missing something here.

To average 1000 samples you sum the samples and divide the sum by 1000.  But the OP is having problems with overflow.  Fine.  Take each sample and divide it by 1000.  Add the result to the sum.  Do that 1000 times and you've done the identical math in a more convenient manner and since your numbers are 1000 times smaller, you avoid the overflow.

What am I missing?

Ed

[sokoloff]

I seem to be missing something here.

To average 1000 samples you sum the samples and divide the sum by 1000.  But the OP is having problems with overflow.  Fine.  Take each sample and divide it by 1000.  Add the result to the sum.  Do that 1000 times and you've done the identical math in a more convenient manner and since your numbers are 1000 times smaller, you avoid the overflow.

What am I missing?

That you lose a fair amount of precision in taking a 12 bit measurement and doing integer division by 1000. Even doing right shift 10 bits throws away some information that can introduce a bias into the averaging process.

Without adding an offset, the bias is enormous.
With adding an offset before dividing/shifting, the bias is less, but still meaningful. Presumably, OP is averaging to get a better or more representative measurement.

Code below:

Code: [Select]

#include <stdio.h>
#include <stdlib.h>

typedef short          int16;
typedef unsigned short uint16;

typedef int            int32;
typedef unsigned int   uint32;


void test()
{
  // These variables are what you have on a 16 bit platform
  uint16 high, low;

  // This is the divide first method
  uint16 div_first1;

  // This is the divide first method with less bias
  uint16 div_first2;

  // This is the right shift first method
  uint16 shift_first1;
 
  // This is the right shift first method with less bias
  uint16 shift_first2;
 
  // These variables are what you have on a 32 bit platform
  // I'm using them here just to prove that the 16 bit math works
  // In your application, you would only use the uint16s
  uint32 sum, test;

  high = 0, low = 0;
  div_first1 = 0;
  shift_first1 = 0;
  div_first2 = 0;
  shift_first2 = 0;
  sum = 0;
  int i;
  for (i = 0; i < 1024; i++) {
    // Use rand() if you don't have arc4random on your platform
    int16 new_measurement = arc4random() % (1 << 12);
    uint16 old_low;

    /*if ((i % 64) == 0)
      printf("Meas: %d\n", new_measurement);*/
   
    sum = sum + new_measurement;

    old_low = low;
    low = low + new_measurement;
    if (old_low > low)
      high++;

    if (i < 1000) {
      div_first1 += new_measurement / 1000;
      div_first2 += (new_measurement + 500) / 1000;
    }
    shift_first1 += new_measurement >> 10;
    shift_first2 += (new_measurement + 512) >> 10;
  }
  test = (((uint32) high) << 16) + (uint32) low;
  printf("After %d additions,  sum = %8d (0x%04x)\n", i, sum, sum);
  printf("After %d additions, test = %8d (0x%04x)\n", i, test, test);
  printf("After %d additions,  low = %8d (0x%04x)\n", i, low, low);
  printf("After %d additions, high = %8d (0x%04x)\n", i, high, high);

  // avg1 is computed using the 32 bit accumulator (testing)
  uint16 avg1 = sum / i;

  // avg2 is computed using the 2 16 bit accumulators (real code)
  // Shift right by 10 (divide by 1024)
  // Take 6 bits from the low
  // Take 10 bits from the high
  uint16 avg2 = low >> 10 | ((high & 0x05ff) << 6);

  printf("After %d additions, avg1 = %8d (0x%04x)\n", i, avg1, avg1);
  printf("After %d additions, avg2 = %8d (0x%04x)\n", i, avg2, avg2);

  printf("Biased results:\n");
  printf("After %d operations, div_avg1 = %8d (0x%04x)\n", 1000, div_first1, div_first1);
  printf("After %d operations, shift_avg1 = %8d (0x%04x)\n", i, shift_first1, shift_first1);

  printf("Less Biased results:\n");
  printf("After %d operations, div_avg2 = %8d (0x%04x)\n", 1000, div_first2, div_first2);
  printf("After %d operations, shift_avg2 = %8d (0x%04x)\n", i, shift_first2, shift_first2);

}

int main()
{
 
  printf("Sanity check the type sizes.\n");

  printf("sizeof(int16) = %ld\n", sizeof(int16));
  printf("sizeof(uint16) = %ld\n", sizeof(uint16));
  printf("sizeof(int32) = %ld\n", sizeof(int32));
  printf("sizeof(uint32) = %ld\n", sizeof(uint32));
  printf("sizeof(long) = %ld\n", sizeof(long));

  if (sizeof(int16) != 2)
    printf("Halting because sizeof(int16) is not 2.\n");
  if (sizeof(uint16) != 2)
    printf("Halting because sizeof(uint16) is not 2.\n");
  if (sizeof(int32) != 4)
    printf("Halting because sizeof(int32) is not 4.\n");
  if (sizeof(uint32) != 4)
    printf("Halting because sizeof(uint32) is not 4.\n");

  test();
  return 0;
}


[sokoloff]

I seem to be missing something here.

To average 1000 samples you sum the samples and divide the sum by 1000.  But the OP is having problems with overflow.  Fine.  Take each sample and divide it by 1000.  Add the result to the sum.  Do that 1000 times and you've done the identical math in a more convenient manner and since your numbers are 1000 times smaller, you avoid the overflow.

Or, if you want to think about it by example rather than in code, apply that algorithm to a steady series of "499" measurements.

Each measurement is integer divided by 1000, so even if you add the 500 offset, it is rounded down to 0, so the average of 1000 measurements, each a steady 499, is 0 by that algorithm.

Even if you say "OK, don't divide by 1000, only divide by 250 and it still won't overflow". Same problem; you still introduce quantization in the output. A stream of 499s becomes 500. A stream of 450s becomes 500. A stream of 124s becomes 0, but 125s becomes 250, etc.

Whether this matters in the application of course depends on the application.

[edpalmer42]

I seem to be missing something here.

To average 1000 samples you sum the samples and divide the sum by 1000.  But the OP is having problems with overflow.  Fine.  Take each sample and divide it by 1000.  Add the result to the sum.  Do that 1000 times and you've done the identical math in a more convenient manner and since your numbers are 1000 times smaller, you avoid the overflow.

Or, if you want to think about it by example rather than in code, apply that algorithm to a steady series of "499" measurements.

Each measurement is integer divided by 1000, so even if you add the 500 offset, it is rounded down to 0, so the average of 1000 measurements, each a steady 499, is 0 by that algorithm.

Even if you say "OK, don't divide by 1000, only divide by 250 and it still won't overflow". Same problem; you still introduce quantization in the output. A stream of 499s becomes 500. A stream of 450s becomes 500. A stream of 124s becomes 0, but 125s becomes 250, etc.

Whether this matters in the application of course depends on the application.

Of course - integer math vs. floating point.  Ok, got it.  Thanks.

Ed

[hamster_nz]

Unless I am mistaken...

average = sum(samples) / 1000;

In integer math is the same as...

average  = (sum(samples/100) + sum(samples%100)/100)/10;

So the process would be:
- separate out the hundreds and sum them up
- sum up the remainders
- then add  "sum(remainder)/100" to the total of hundreds,
- finally divide by 10 to get your average

The first two steps can be performed on each sample as it arrives....

[amspire]

You can speed this up by averaging over 1024 samples rather then 1000 samples. divide by 1024 is simply done by shifting the sum by 10 bits to the right.

There are also ways to do a running average if you are interested in that. One way is to do

sum = reading + (sum - sum/1024)
average = sum/1024

You will get an average out that is still very similar to an average of 1024 readings, but the average is updated every reading rather then just once every 1024 readings. You will notice that with the running average, you do not even need a counter or loop. It only involves additions, subtractions and bit shifting.

[rs20]

Unless I am mistaken...

average = sum(samples) / 1000;

In integer math is the same as...

average  = (sum(samples/100) + sum(samples%100)/100)/10;

sum(samples%100) could be as large as 1000 * 99 = 99000, which doesn't fit in 16 bits.

Anyway, any half-decent compiler should support 32-bit integers, so we should be sure the OP doesn't have access to 32-bit integers before suggesting these horrendously unreadable workarounds.

[Mechatrommer]

You can speed this up by averaging over 1024 samples rather then 1000 samples. divide by 1024 is simply done by shifting the sum by 10 bits to the right.

There are also ways to do a running average if you are interested in that. One way is to do

sum = reading + (sum - sum/1024)
average = sum/1024

You will get an average out that is still very similar to an average of 1024 readings, but the average is updated every reading rather then just once every 1024 readings. You will notice that with the running average, you do not even need a counter or loop. It only involves additions, subtractions and bit shifting.

Code: [Select]

sum = reading + (sum - average)
average = sum >> 10
less one bit shift...

anyway, it seems the OP is still figuring out the difference between 16 bits with 32 bit integers... 1000 x 2 ^ 12 = 4,096,000 far smaller than signed 32 bit value can take (2,147,483,648). the problem is the declaration... explicitly use int32 instead of "compiler infinite wisdom int" and you are done with whatever you already had..

[sleemanj]

Yeah, bad idea, see rs20 below.


(In the absence of 32bit integers) I would just pop off the stack and sum as many samples as can be before overflow, average them, push that result onto the stack, repeat until the stack length is 1.
If you have all the samples pre-collected, then it would be better to do some "knapsack packing", so you can fit as many samples into an average result as possible.

In pseudo code something like this...

Code: [Select]

BatchTotal=0
BatchCount=0
WHILE count(Samples)
{
  Sample=PopSmallest(Samples)
  IF AddingWouldNotOverflow(BatchTotal, Sample)
  {
     BatchTotal += Sample
     BatchCount++
  }
  else
  {
    PushSample(BatchTotal/BatchCount)
    BatchTotal = Sample
    BatchCount = 1
  }
}
Result = BatchCount ? BatchTotal/BatchCount : 0


[Mechatrommer]

what on earth compiler that doesnt support 32 bits? unless the OP is back to the future from atari world.

[rs20]

(In the absence of 32bit integers) I would just pop off the stack and sum as many samples as can be before overflow, average them, push that result onto the stack, repeat until the stack length is 1.

If you have all the samples pre-collected, then it would be better to do some "knapsack packing", so you can fit as many samples into an average result as possible.

In pseudo code something like this...

Code: [Select]

BatchTotal=0
BatchCount=0
WHILE count(Samples)
{
  Sample=PopSmallest(Samples)
  IF AddingWouldNotOverflow(BatchTotal, Sample)
  {
     BatchTotal += Sample
     BatchCount++
  }
  else
  {
    PushSample(BatchTotal/BatchCount)
    BatchTotal = Sample
    BatchCount = 1
  }
}
Result = BatchCount ? BatchTotal/BatchCount : 0


Oh god no, averaging is not an associative operation* so the answer your algorithm gives depends on the order that samples arrive. In particular, it basically just discards the result of the previous batch, since all the hundreds of samples that might have contributed to that batch end up as a single value, with no more weight than any subsequent individual sample.

I mean, if we work with 8-bit variables for simplicity, your algorithm will take the samples [1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 101] and output 51.00 as the average. Considering that the real average is 1.39, that's not a minor error. And all this inaccuracy comes at the cost of just presupposing that the OP has a priority queue handy.

* (Unless you maintain weights for each batch, which you're not doing here, and if you did, you'd have to use 32-bit numbers to maintain that so...)

[sleemanj]

Oh god no, averaging is not an associative operation*

True and well demonstrated, maths never my strong suit.  TIL.

[tggzzz]

Almost everybody replying to this thread will benefit from reading, learning, and inwardly digesting
How Computers Handle Numbers
This could be called "Computer Arithmetic Uncovered". It will describe how computers store and process integers and floating point numbers, and also the exceptions that might arise and what they mean. The intent is to explain how modern computers handle numbers, and how to get reliable answers for a reasonable amount of effort.

See http://help.uis.cam.ac.uk/help-support/training/downloads/course-files/programming-student-files/arithmetic

[JPortici]

At the risk of sounding like a broken record, the OP should check the manual for the compiler he's using, and find the section that describes supported data types.
since the MCU he's using is 16 bit i assume that, as with XC16 for PIC24/dsPIC, the "int" type will be 16 bits and long type 32 bits.

I find this to be "logical" as i always think as it as a variable with the same width as the data bus and long to be twice as long.

What i usually do for projects that can be either on 16 or 32 bit processors i use "int" where the only thing i care about is that the variable is processed with minimal effort (if 16 bit is enough.. and my data bus size is 16 bits why waste instuctions and load/store time to handle 32 bit variables?) and use exact size types (int16_t, int32_t, ...) which are defined in the stdint.h include file, where i need to be sure of which size the varaible should be.

Reading the material posted by tgzzz will help you understand more on the issue.
Also, if you increase your buffer to a power of two, in this case 1024, your MCU will be happy and process the average in no-time (a logical shift is much faster than an hardware or software divider.. as fast as a single instruction if your mcu has a barrel shifter)

tl;dr: use long.
better tl;dr: always include <stdint.h> and use int32_t / uint32_t/etc