 ## Modulo means

Friday, November 21st, 2008 by Nigel Jones

Normally on this blog I’m either giving my opinions on embedded matters, or offering tips on how to do things better. Well today I’m turning the tables, as I’d like your help. Yesterday I ran into a rather perplexing problem, which I’d be interested to see if any of my readers can solve.

In a product I am working on, there is a phase comparator generating difference readings in the range 0 – 0xF. The phase comparator is somewhat noisy and so I want to obtain a moving average of the phase differences. Now typically to perform a moving average filter, one sums the elements in a buffer and divides by the number of elements to obtain the arithmetic mean. Indeed we can do this here, provided that we don’t flip back and fore across the zero line. If we do cross the zero line then the method breaks down. For example, if successive phase differences are 0, F, 0, F, 0, F …. 0, F, then the simple arithmetic mean of these numbers will be 8 instead of some value between F and 0.

You may think that the answer is to switch to signed arithmetic and operate over the range -8 … +7. However, a little thought will show that you have now merely shifted the problem as to what happens when the system is close to -8 such that the values alternate between -8, 7, -8, 7 … -8, 7.

Thus, can you come up with a robust, efficient solution to compute the mean of an array of modulo numbers?

The problem is solvable as one of the Engineers that I’m working with hit upon not one, but two possible solutions (nice work Kyle). However, I’d be interested in other possible approaches.

I’ll publish Kyle’s method(s) next week.

Home

### 3 Responses to “Modulo means”

1. victorh says:

To be honest, I completely missed your point. I can’t even understand what your problem is. I got loss in:Indeed we can do this here, provided that we don’t flip back and fore across the zero line.“here” where?In the past, I have enjoyed your posts. I even applied on my projects some of the knowledge you put in them. So I believe this post also includes some clever insight which, unfortunately, I missed to understand.Maybe you could rephrase it? Thanks 🙂

2. Bruno Santiago says:

Victorh:The point is he is measuring phase. If the phase difference is greater than 359 degrees, it is 0 again.Nigel:Why not average the inputs of the phase comparator?If it´s not possible, you can think you´re working with polar cordinates and measuring only the angle. Choose an arbritary radius and then convert to cartesian cordinates. Then average x and y. Then convert back to polar coordinates and take angle.Thus, it´s probably not efficient at all.

3. Bruno Santiago says:

If you want to average a small power of two samples it can be efficient.This way, you can average two by two and it´s a lot easier.Imagine you have sample A and sample B.If | A – B | <= 8 (or 180 degrees), then it´s plain ( A + B ) / 2If | A – B | > 8 and A + B >= 16 (or 360 degrees), then it's ( A + B – 16 ) / 2If | A – B | > 8 and A + B < 16, then it's 16 + [ ( A + B – 16 ) / 2 ]