Finding gaps in pulse train

[george seifert]

I have a pulse train that I'll receive via a DAQ card that looks like this

I need to find gaps in the pulses. I've attached a VI that generates simulated data and does the analysis. Basically I find the indicies of the peaks and then take the second derivative of those indicies. The gaps in the indicies give a spike in the second derivative. I can then use those spikes in the derivative to find the gaps.

I'm just wondering if there's a more elegant way to do this.

Thanks,

George

Fing gaps.zip

[Gary Rubin]

I'm just wondering if there's a more elegant way to do this.

Does your data always have that oscillatory pattern?

This seems to work on your sim data, but I don't know how representative that is of your real data.

[ShaunR]

I have a pulse train that I'll receive via a DAQ card that looks like this

I need to find gaps in the pulses. I've attached a VI that generates simulated data and does the analysis. Basically I find the indicies of the peaks and then take the second derivative of those indicies. The gaps in the indicies give a spike in the second derivative. I can then use those spikes in the derivative to find the gaps.

I'm just wondering if there's a more elegant way to do this.

Thanks,

George

Fing gaps.zip

For this signal, you can just look for zeros in your data which will be the start and end of gaps.

Edited August 18, 2009 by ShaunR

[george seifert]

Does your data always have that oscillatory pattern?

This seems to work on your sim data, but I don't know how representative that is of your real data.

Thanks I like your way better. Actually I've done something like that in the past and completely forgot about it.

I don't know for sure yet what the real data will look like. I'm sure it won't be this nice. But this is a good place to start.

George

For this signal, you can just look for zeros in your data which will be the start and end of gaps.

Well you can't get much simpler than that. I'll bet Gary's method is faster though. I know I didn't make that part of the criteria.

[ShaunR]

Thanks I like your way better. Actually I've done something like that in the past and completely forgot about it.

I don't know for sure yet what the real data will look like. I'm sure it won't be this nice. But this is a good place to start.

George

Well you can't get much simpler than that. I'll bet Gary's method is faster though. I know I didn't make that part of the criteria.

I bet it isn't

[Gary Rubin]

I bet it isn't

Well, you'd have to compare apples to apples. The input into the threshold peak detect looks the same as your output.

[ShaunR]

Well you can't get much simpler than that.

Ahh. You can. You don't need the for loop either

[Gary Rubin]

Ahh. You can. You don't need the for loop either

While we're being creative, here's another way to do it. Again, it works for this particular sim data. Not sure it's any more efficient than the diff method though. Curious to see your approach.

[george seifert]

Your comments got me to look closer at my simulated data. I knew my real data would be noisier, but it will also look more like a sine wave than the triangle wave I had. I bumped up the sample frequency and now it looks better. Sorry to say though that the contributed ideas won't work on the new data. I'm back to my original plan of finding peaks and differentiating. By finding the time between peaks in the differentiation I can get the gaps. OK anybody up for round 2?

George

Fing gaps 2.vi

[Gary Rubin]

Your comments got me to look closer at my simulated data. I knew my real data would be noisier, but it will also look more like a sine wave than the triangle wave I had. I bumped up the sample frequency and now it looks better. Sorry to say though that the contributed ideas won't work on the new data. I'm back to my original plan of finding peaks and differentiating. By finding the time between peaks in the differentiation I can get the gaps. OK anybody up for round 2?

George

Fing gaps 2.vi

The effectiveness of these all depend on your SNR.

How about a simple moving average (SMA) on the absolute value of the data and look for the result to be below some threshold? The size of the SMA window would depend on the noisiness of the data. That uses a for loop, unfortunately.

A slight variation would be to traverse the data array and check for the last N elements all below a threshold. Again, this uses a for loop.

Or a combination of my original idea and ShaunR's... Do the diff (or sum) with the array shift, compare to a thresh, then convert from boolean to 0,1.

[Mellroth]

...I'm back to my original plan of finding peaks and differentiating. By finding the time between peaks in the differentiation I can get the gaps...

Fing gaps 2.vi

When you find a gap, do you need the start location, stop location or the centre location (or do you need all of them)?

/J

[george seifert]

When you find a gap, do you need the start location, stop location or the centre location (or do you need all of them)?

/J

Ideally I need to find the start and stop of all the gaps. I need separate out and save the chunk of data between the gaps.

George

The effectiveness of these all depend on your SNR.

How about a simple moving average (SMA) on the absolute value of the data and look for the result to be below some threshold? The size of the SMA window would depend on the noisiness of the data. That uses a for loop, unfortunately.

A slight variation would be to traverse the data array and check for the last N elements all below a threshold. Again, this uses a for loop.

Or a combination of my original idea and ShaunR's... Do the diff (or sum) with the array shift, compare to a thresh, then convert from boolean to 0,1.

Using loops isn't necessarily a killer, but I do need to keep processing time to a minimum.

I think a SMA could work, but I think it'll be a little sloppy on finding the edges of the gaps (depending on how many samples I average).

Thanks for keeping the ideas coming. They may not work as is, but usually I get enough of a nudge in the right direction to figure it out.

George

[ShaunR]

While we're being creative, here's another way to do it. Again, it works for this particular sim data. Not sure it's any more efficient than the diff method though. Curious to see your approach.

Litteraly...you don't need the for loop.

Your comments got me to look closer at my simulated data. I knew my real data would be noisier, but it will also look more like a sine wave than the triangle wave I had. I bumped up the sample frequency and now it looks better. Sorry to say though that the contributed ideas won't work on the new data. I'm back to my original plan of finding peaks and differentiating. By finding the time between peaks in the differentiation I can get the gaps. OK anybody up for round 2?

George

Fing gaps 2.vi

Still works because its only detecting zeros which (in both your examples) only exist in the gaps.

Edited August 20, 2009 by ShaunR

[Gary Rubin]

Litteraly...you don't need the for loop.

I think that only does half the job. You'd still need to look for 2 consecutive 0's.

[ShaunR]

Ideally I need to find the start and stop of all the gaps. I need separate out and save the chunk of data between the gaps.

George

Using loops isn't necessarily a killer, but I do need to keep processing time to a minimum.

I think a SMA could work, but I think it'll be a little sloppy on finding the edges of the gaps (depending on how many samples I average).

Thanks for keeping the ideas coming. They may not work as is, but usually I get enough of a nudge in the right direction to figure it out.

George

Labview is highly optimised for "for" loops. They are very efficient. Far more so than most other array primitives/operators.

I think that only does half the job. You'd still need to look for 2 consecutive 0's.

Try it.

Edited August 20, 2009 by ShaunR

[Gary Rubin]

Labview is highly optimised for "for" loops. They are very efficient. Far more so than most other array primitives/operators.

No disagreement here. I still try to avoid using them if I can.

Try it.

Ideally I need to find the start and stop of all the gaps. I need separate out and save the chunk of data between the gaps.

The output of your example just provides a mask that indicated when the data is valid.

I don't think that's his desired output.

Edited August 20, 2009 by Gary Rubin

[ShaunR]

The output of your example just provides a mask that indicated when the data is valid.

I don't think that's his desired output.

Now your just being difficult...lol.

[Gary Rubin]

Now your just being difficult...lol.

Ah, I like that one!

Especially if you're using LV9 on a multicore system and can multithread the loop.

[ShaunR]

Ah, I like that one!

Especially if you're using LV9 on a multicore system and can multithread the loop.

Unfortunately you can't because it uses serialised data. I've actually found very few scenarios (so far) where I can use that feature. That maybe due to how I partition my code and the type of implementations.

[Gary Rubin]

Unfortunately you can't because it uses serialised data. I've actually found very few scenarios (so far) where I can use that feature. That maybe due to how I partition my code and the type of implementations.

Oh, right. I guess the shift register would get in the way... I haven't played with that feature yet (or LV2009, for that matter).

Actually, that got me thinking. I wonder what the performance difference is between your original looped approach from a couple days ago and the unlooped one. And does that change significantly if you multithread the looped one?

Edited August 20, 2009 by Gary Rubin

[ShaunR]

Oh, right. I guess the shift register would get in the way... I haven't played with that feature yet (or LV2009, for that matter).

Actually, that got me thinking. I wonder what the performance difference is between your original looped approach from a couple days ago and the unlooped one. And does that change significantly if you multithread the looped one?

Intriguing question. Well.

For loop original 10000 runs = 5080 ms.

No for loop 10000 runs = 2ms

For loop with 10000 run loop normal but code loop // (2cores)) 10000 runs = 2887 ms

For loop with 10000 run loop // (2cores) and code loop // (2cores)) 10000 runs = 2 ms

Edited August 20, 2009 by ShaunR

[Gary Rubin]

Intriguing question. Well. Rather than just saying "try it" I"did it".

For loop original 10000 runs = 5080 ms.

No for loop 10000 runs = 2ms

For loop with 10000 run loop normal but code loop // (2cores)) 10000 runs = 2887 ms

For loop with 10000 run loop // (2cores) and code loop // (2cores)) 10000 runs = 2 ms

Ok, I get the factor of ~2 speedup from the 5.08 seconds to the 2.887 seconds, but I'm pretty surprised at the last line. I think I would have have expected no difference, as both cores should already be fully committed by virtue of the code loop being parallelized.

And now you see why I avoid for loops whenever possible. The Boolean to 0,1 likely has an allocation associated with it, which is why you don't want to do that in a loop...

[ShaunR]

Ok, I get the factor of ~2 speedup from the 5.08 seconds to the 2.887 seconds, but I'm pretty surprised at the last line. I think I would have have expected no difference, as both cores should already be fully committed by virtue of the code loop being parallelized.

And now you see why I avoid for loops whenever possible. The Boolean to 0,1 likely has an allocation associated with it, which is why you don't want to do that in a loop...

Surprised me too . But maybe optimisations are coming into play.

Not sure what you mean by "whenever possible". If you need to "iterate" then I don't really see any other alternatives apart from "while" loops which don't have inherent capablity to dynamically terminate on the array length. Example perhaps?

[Gary Rubin]

Not sure what you mean by "whenever possible". If you need to "iterate" then I don't really see any other alternatives apart from "while" loops which don't have inherent capablity to dynamically terminate on the array length. Example perhaps?

I was referring mostly to the difference between your two test codes. One does an operation inside a loop, the other performs the same operation on a vector. Of course, most of the time you're using a loop, you have no choice in the matter because of the need to iterate.

That said, one example is a phase wrap on a vector. The logic is: if a>180, a = a-360. if a<-180, a=a+360. Because LV's Select does not allow the boolean input to be a vector, my first thought was to use a for loop. Instead, I was able to come up with a more efficient vectorized approach using modulos.

[ShaunR]

I was referring mostly to the difference between your two test codes. One does an operation inside a loop, the other performs the same operation on a vector. Of course, most of the time you're using a loop, you have no choice in the matter because of the need to iterate.

That said, one example is a phase wrap on a vector. The logic is: if a>180, a = a-360. if a<-180, a=a+360. Because LV's Select does not allow the boolean input to be a vector, my first thought was to use a for loop. Instead, I was able to come up with a more efficient vectorized approach using modulos.

Indeed.

For me it depends on whether I want (or need) to spend a day thinking about an elegent approach for a trivial part of the program or just want the results.

I'm not particularly a purist, so if its neat, easily understood but not the quickest piece of code on the planet, then thats fine.