help with algorithm

[electroRF]

Hi,

I'd like to detect if N Events occurred in a Time Window T, and if so, act on it.

For example, each event is a certain interrupt, and I'd like to know whether N=4 interrupts occurred in a Time Window of T=100ms, and if yes, notify the user.

How would you implement such algorithm?

Note that it could be that 4 events would occur @ t = 80ms, 90ms, 150ms, 179ms, and therefore it means that 4 events occurred in 100ms, which means the user should be notified.

As this will be implemented on embedded chip and not PC, it should be as efficient as possible, Cycles concerning (e.g., setting a Timer to constantly work would be inefficient, as it'd interrupt frequently and therefore "steal" cycles from the system even when no events occur).

These events don't occur frequently.

Thank you

 

[NorthGuy]

You will have to keep times of occurences of the last N events - in a circular buffer perhaps. Then, after inserting new event, compare the time of the last event with the time of the first in the buffer - if it's less than 100, you've got your warning.

 

[Cicero]

You will have to keep times of occurences of the last N events - in a circular buffer perhaps. Then, after inserting new event, compare the time of the last event with the time of the first in the buffer - if it's less than 100, you've got your warning.

Thats exactly what I'd do.

You need to run a timer, but prescale it down to the ms range or at least the slowest you can that gives you enough resolution. Then just let it free run, so no servicing apart from an interrupt on overflow, you need to keep track for events that happen over a timer overflow or more. It wont eat resources because its free running. Obviously if its a 32bit timer it'll be better because it'll take ages to overflow but since we dont know your platform we can't help here. For example, a 32bit ms timer will take 49days to overflow, and a 16bit ms timer just over a minute.

Then when you get your event interrupt just grab the timer value and the overflow counter value as well into a circular event buffer as Northguy suggested. Check the time difference between the first and last and you're golden.

 

[electroRF]

Guys,
Thank you very much!

One question please.

When the Timer reaches its max value, it starts automatically from the beginning.

I'd need to prevent it from causing me a trouble.

I thought of the following.

Every time an interrupt (event) occurs, I'd set another Timer to expire after 100ms.

If another Interrupt (event) occurs before the Timer expired, I'd stop the Timer and restart it to Expire after 100ms.

Now, there could be 2 options:

1. N = 4 Events occurred before the Timer Expired, therefore, I'd notify the user.

2. 1 <= N < 4 Events occurred when the Timer Expired, and therefore, I'd clean the Circular Buffer.

What is your opinion on it?

Is there a better way to take into account the fact that the Timer runs from the start when it reaches its end?

 

[Cicero]

Guys,
Thank you very much!

One question please.

When the Timer reaches its max value, it starts automatically from the beginning.

I'd need to prevent it from causing me a trouble.

I thought of the following.

Every time an interrupt (event) occurs, I'd set another Timer to expire after 100ms.

If another Interrupt (event) occurs before the Timer expired, I'd stop the Timer and restart it to Expire after 100ms.

Now, there could be 2 options:

1. N = 4 Events occurred before the Timer Expired, therefore, I'd notify the user.

2. 1 <= N < 4 Events occurred when the Timer Expired, and therefore, I'd clean the Circular Buffer.

What is your opinion on it?

Is there a better way to take into account the fact that the Timer runs from the start when it reaches its end?

Rather do this.

With your free flowing timer, when it overflows and it enters that interrupt, process your circular buffer then as well. If you've got events within 100ms of the overflow leave them for the next time. If you dont, clear your buffer and reset your overflow counter as well.

 

[NorthGuy]

If you re-start 100ms timer when you get an event, you don't need to store the times of the event, only the number. Although your requirement from the original post was not to start timers. Doesn't your system have some sort of time base that you can use to get current time when an event happens?

 

[Pommie]

If you restart the timer on each event you will never reach event two, or did I miss something. Just store event times in a circular buffer and check when a new event happens. If you use a 32 bit variable for counting mS then it won't wrap around until around 2064.

Mike.

 

[electroRF]

Hi friends,
Thank you very much.

Rather do this.

With your free flowing timer, when it overflows and it enters that interrupt, process your circular buffer then as well. If you've got events within 100ms of the overflow leave them for the next time. If you dont, clear your buffer and reset your overflow counter as well.

What do you mean please by Overflow Counter?

If you re-start 100ms timer when you get an event, you don't need to store the times of the event, only the number. Although your requirement from the original post was not to start timers. Doesn't your system have some sort of time base that you can use to get current time when an event happens?

Hi NorthGuy,
I have 2 questions please regarding your post:
1. How could storing the numbers help you identify whether 4 Events occurred in 100ms Interval?
2. If I won't use a timer, I'm fearing of the following:
Event #1 time = 50ms
Event #2 time = 60ms
Event #3 time = 70ms
Event #4 time = 80ms + Wrap-Around of the timer

Event #4 occurred long time after Event #1-#3, but if I won't use the Timer Technique, I'd think that Event #4 occurred 10ms after Event #3.


Mike
Thank you Mike.
I'm using 32KHz Timer, I'll check how often it wraps around.

 

[Pommie]

I'd setup a timer to generate a 1mS interrupts and simply increment a 32 bit counter. Store the count when an event occurs. If the latest event minus the one 4 events before is less than 100 then it happened.

If using a pic then timer2 can easily be setup to generate 1mS interrupts.

Mike.

 

[electroRF]

Hi Mike,

I assume that the 32-bit 32KHz Timer which I use, wraps around after 2^(32) * 1 / 32K = 36.4 hours, which is not that much.

I'd rather not generate an interrupt every 1ms, because these events rarely happen, so it'd be a too large overhead.

 

[Cicero]

What do you mean please by Overflow Counter?

Basically you set up a timer to free run. If its a 16bit timer, it'll overflow when the value reaches 0xFFFF and wraps back to 0x0000. So you must set up an interrupt for when that overflow happens.

You need to keep track of the overflows for your timer, so you can check events that occur at before and after an overflow.
Maybe this eg will help. Obviously you need to initialise it all, this is just as an example.

struct event
{
  u8 eventType;     /*what your event is */
  u32 overflowCount; /* overflow counter, copy from */
  u16 timeVal;      /* direct timer value copied */
};

u32 overflowCounter;
struct event events[4]; /* circular array of your events */
u8 eventNum;            /* for the circular buffer */

/* Interrupt for overflow of free running timer  - shouldn't happen often */
void interrupt_FreeRunningTimer () {
  overflowCounter++;
}

void interrupt_Event (void) {
  events[eventNum].eventType = funcGetEventType();  /* whatever your event is, save it */
  events[eventNum].timeVal = functGetTimerVal();    /* pulls the timer value direct */
  events[eventNum].overflowCount = overflowCounter; /* get overflow counter */
  if (++eventNum >= 4) {
    eventNum=0;
  }
  /* process them to check for alarm */
  processEvents ();
}

void processEvents (void) {
  u32 timeFirstEvent, timeLatestEvent;
  u8 eventNumFirst, eventNumLatest;

  /* Only care about our latest event, and the first one */
  if (eventNum=0) {
    eventNumLatest=3;
    eventNumFirst=0;
  } else {
    eventNumLatest=eventNum-1;
    eventNumFirst=eventNum;
  }
  timeFirstEvent = overflowCount*65535 + events[eventNumFirst].timeVal;
  timeLatestEvent = overflowCount*65535 + events[eventNumLatest].timeVal;
  /* Presuming its a 1ms timer */
  if ( (timeLatestEvent - timeFirstEvent) > 100) {
    functThrowAlarm();
  }
}

 

[NorthGuy]

unsigned int buffer[4]; // assumes 32-bit ints
int counter;
 
int process_event(unsigned int event_time) {
  buffer[counter&3] = event_time;
  return (event_time - buffer[++counter&3]) < HUNDRED_MS;
}

There's a small (next to none) probability that it might trigger falsely because of timer overflows. If that's the problem, run something like this every few hours:

void housekeeping(unsigned int current_time) {
  for (int i = 0; i < 4; i++) {
    if ((buffer[i]-current_time)&0x80000000) buffer[i] -= 0x7f000000;
  }
}

 

[Pommie]

I'd rather not generate an interrupt every 1ms, because these events rarely happen, so it'd be a too large overhead.

An interrupt that just increments a variable will probably only take 20 cycles. If you use a pic at 1MHz then a 1mS interrupt will use 2% of the available time. With a 8MHz clock that reduces to ¼%. Not much of an overhead at all and it'll simplify your code.

Mike.

 

[Cicero]

An interrupt that just increments a variable will probably only take 20 cycles. If you use a pic at 1MHz then a 1mS interrupt will use 2% of the available time. With a 8MHz clock that reduces to ¼%. Not much of an overhead at all and it'll simplify your code.

Mike.

Although I posted a way of doing it without having a regular occurring interrupt as requested, I'd probably use a 1ms interrupt as well, depending on how complex your application is. I'd use it as a 1ms OS ticker for example, and it would be a useful time source for many other areas of your code as well. Just a thought OP, possibly think of the bigger picture, application dependant.

 

[electroRF]

NorthGuy, Cicero, Mike
Thank you very much dear friends!

Your help has been great to me!

 

[electroRF]

Hi dear friends.

I'd love getting your input on an additional related algorithm.

The user would like to be notified also when density of the Events is above 50% (with at least 6 events).

The Event can happen every time a certain Module is activated - if the event (interrupt) happens, it'd happen ~1ms after the module was activated.

Therefore, When the Module is activated 10 times, and the Event occurred 6 times, the user would like to be notified: E.G.

Module Activation: .......................................... 1--2--3--4---5--6---7--8---9--10--11-12-13-14-15
Event Occurred (Y) / Not Occurred (N): .............. N, N, N, Y , N , Y , N , Y , N , Y , N , Y , Y, N, N

At the above Example, the user should be notified when the Event occurred at the 13th Activation, since if you start gathering statistics from #4 to #13, you'll see 6 Events occurred out of 10 Module Activations = i.e. 60% density with at least 6 Events.

The Inputs I have are:
- When a Module is activated
- When an Event (interrupt) happens (which, if happens, it'd happens ~1ms after the Module was activated)

How would you handle the counting?

My main dilemma is, when to Reset the Events-Counter and Module-Activation Counter?

I know that I should start counting only when the 1st Event occurs.

I'd love hearing your ideas

Thank you.

 

[NorthGuy]

Same thing. Maintain a circular buffer with 10 elements. At every activaton, add a new element (which will override the last) and mark it as N. At every event mark the last element as Y, count the number of Ys in the buffer and if it is more than 5 then ring the bell.

 

[electroRF]

Thank you NorthGuy

Perhaps you mean 11 Elements?

E.g.

Y N N N N N Y Y Y Y Y
(x1 Y, x5 N, x5 Y)

 

[NorthGuy]

No. You only need 10 elements. If you're interested in last 10 activations, then it is irrelevant what happened in the 11-th activation.

 

[NorthGuy]

Duplicate