COMPUTING MEAN AND VARIANCE RECURSIVELY

 

 

BACKGROUND

---

 

Just several days ago, when I was reading someone’s c language code for motor encoder ADC data smoothing, I saw these lines below.

#define RATE_BUF_SIZE 6
typedef struct{
	int32_t raw_value;  
	int32_t last_raw_value;
	int32_t ecd_value; 
	int32_t diff;													
	int32_t temp_count;              
	uint8_t buf_count;							
	int32_t ecd_bias;											
	int32_t ecd_raw_rate;						
	int32_t rate_buf[RATE_BUF_SIZE];
	int32_t round_cnt;					
	int32_t filter_rate;										
	float ecd_angle;
}Encoder;
void EncoderProcess(volatile Encoder *v, CanRxMsg * msg)
{
	int i=0;
	int32_t temp_sum = 0;    
	v->last_raw_value = v->raw_value;
	v->raw_value = (msg->Data[0]<<8)|msg->Data[1];
	v->diff = v->raw_value - v->last_raw_value;
	if(v->diff < -7500)  
	{
		v->round_cnt++;
		v->ecd_raw_rate = v->diff + 8192;
	}
	else if(v->diff>7500)
	{
		v->round_cnt--;
		v->ecd_raw_rate = v->diff- 8192;
	}		
	else
	{
		v->ecd_raw_rate = v->diff;
	}
	v->ecd_value = v->raw_value + v->round_cnt * 8192;
	v->ecd_angle = (float)(v->raw_value - v->ecd_bias)*360/8192 + v->round_cnt * 360;
	v->rate_buf[v->buf_count++] = v->ecd_raw_rate;
	if(v->buf_count == RATE_BUF_SIZE)
	{
		v->buf_count = 0;
	}
	for(i = 0;i < RATE_BUF_SIZE; i++)
	{
		temp_sum += v->rate_buf[i];
	}
	v->filter_rate = (int32_t)(temp_sum/RATE_BUF_SIZE);					
}

It’s easy to understand that the author is trying to smooth the data using a moving average filter, which is identified by the last five lines. Let’s rewrite them alone below.

for(i = 0;i < RATE_BUF_SIZE; i++)
{
	temp_sum += v->rate_buf[i];
}
v->filter_rate = (int32_t)(temp_sum/RATE_BUF_SIZE);

Moving average filter is a not a stupid method for data smoothing, but the implementation above is stupid. Each invocation just pushes a new element in and pops an element out, let’s say the sequence length is n, then there will be n-1 elements remain the same, but the implementation trys to re-calculate the sum of them, that’s what I’m saying stupid about. As a matter of fact, the time complexity of this method can be cut down from O(n) to O(1). As a trade off, we just need to add some additional variables. A more efficient implementation is showed below. The added variables is noted out.

#define RATE_BUF_SIZE 6
typedef struct{
	int32_t raw_value;  
	int32_t last_raw_value;
	int32_t ecd_value; 
	int32_t diff;													  
	int32_t ecd_bias;											
	int32_t ecd_raw_rate;						
	int32_t rate_buf[RATE_BUF_SIZE];
	uint8_t buf_ptr;		 // pointer to current index	
	int32_t sum;             // sum of buffered data
	int32_t delta_sum;       // delta sum  of buffered data
	int32_t round_cnt;					
	int32_t filter_rate;										
	float ecd_angle;
}Encoder;
void EncoderProcess(volatile Encoder *v, CanRxMsg * msg)
{
	v->last_raw_value = v->raw_value;
	v->raw_value = (msg->Data[0]<<8)|msg->Data[1];
	v->diff = v->raw_value - v->last_raw_value;
	if(v->diff < -7500)  
	{
		v->round_cnt++;
		v->ecd_raw_rate = v->diff + 8192;
	}
	else if(v->diff>7500)
	{
		v->round_cnt--;
		v->ecd_raw_rate = v->diff- 8192;
	}		
	else
	{
		v->ecd_raw_rate = v->diff;
	}
	v->ecd_value = v->raw_value + v->round_cnt * 8192;
	v->ecd_angle = (float)(v->raw_value - v->ecd_bias)*360/8192 + v->round_cnt * 360;
	v->delta_sum =  v→ecd_raw_rate – v→rate_buf[v→buf_ptr]; // compute the delta value
	v->sum +=  v->delta_sum; // add to sum
	v->rate_buf[v->buf_ptr++] = v→ecd_raw_rate; // spin the ring buffer
	if(v-> buf_ptr == RATE_BUF_SIZE)
	{
		v->buf_count = 0;
	}
	v->filter_rate = (int32_t)(v->sum/RATE_BUF_SIZE);					
}

 

THE RECURSIVE FORM OF MEAN AND VARIANCE

---

 

As a further exploring of the given case above, let’s find the recursive form of mean and variance of a sequence with length n.

At time k-1:

(1)

(2)

(3)

At time k:

(4)

(5)

(6)

Let’s first look at equation (2) and equation (5).

(7)

(8)

Now we have equation (9), which is the recursive form of mean.

(9)

Then we look at equation (3) and equation (6).

(10)

(11)

(12)

For the fourth term of equation (12), by replacing with the right part of equation (9), we have equation (13) and (14).

(13)

(14)

Combining equation (12) with equation (14), we have equation (15).

(15)

Now we have the recursive form of variance as equation (16).

(16)