12
$\begingroup$

I want to know how I can determine whether a series of data is periodic or not.

I want to use Fourier transform/series. My data looks either aperiodic

[111100001111000110010101010000101]

or periodic

[11001100110011001100]

and I need to decide which it is automatically. What types of analyses or calculations can I perform to determine if a signal is periodic or not?

$\endgroup$
14
$\begingroup$

I would do a normalized autocorrelation to determine periodicity. If it is periodic with period $P$ you should see peaks at every $P$ samples in the result. A normalized result of "1" implies perfect periodicity, "0" implies no periodicity at all at that period, and values in between imply imperfect periodicity. Subtract the data sequence's mean from the data sequence before doing the autocorrelation because it will bias the results.

The peaks will tend to diminish the farther away from the center they get simply because of having fewer overlapping samples. You can mitigate that effect by multiplying the results by the inverse of the percentage of overlapping samples.

$$ U(n) = A(n) * \frac{N}{\lvert N-n\rvert} $$ where $U(n)$ is the un-biased autocorrelation, $A(n)$ is the normalized autocorrelation, $n$ is the offset, and $N$ is the number of samples in the data sequence that you are checking for periodicity.

EDIT: This is an example of how to tell if the sequences are periodic. The following is Matlab code.

s1 = [1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 1 1 0 0 1 0 1 0 1 0 1 0 0 0 0 1 0 1];
s1n = s1 - mean(s1);
plot(xcorr(s1n, 'unbiased'))

The "unbiased" parameter to the xcorr function tells it to do the scaling described in my equation above. The auto-correlation is not normalized, though, which is why the peak at the center is around 0.25 instead of 1. That doesn't matter, though, as long as we keep in mind that the center peak is perfect correlation. We see that there are no other corresponding peaks except at the outermost edges. Those do not matter because there there is only one sample overlapping, so that is not meaningful.

Non-periodic

s2 = [1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0];
s2n = s2 - mean(s2);
plot(xcorr(s2n, 'unbiased'))

Here we see that the sequence is periodic because there are multiple unbiased autocorrelation peaks with the same magnitude as the center peak.

Periodic

$\endgroup$
  • 3
    $\begingroup$ +1: You might also want to mean-correct the data before forming $A(n)$, otherwise any DC-offset might get in the way of finding the periodic peaks. $\endgroup$ – Peter K. Apr 24 '13 at 13:51
  • 1
    $\begingroup$ @PeterK Good point. $\endgroup$ – Jim Clay Apr 24 '13 at 14:13
  • $\begingroup$ Hey Jim, thanks..I am little bit confused how to start programming this, because where ever I search about autocorrelation I find complex formulas, I dont really get the idea where to start from and how to detect peak with period P in the code. With me I have a list of values V[]={110011001100..} now how to put them in autocorrelation formulas and determine wether its periodic or not...Can you please give me a little easy start...Thanks a lot $\endgroup$ – safzam Apr 26 '13 at 10:00
  • $\begingroup$ @safzam If you are using Matlab or Python (numpy) they have autocorrelation functions already. If you need something in C/C++/Java/whatever, then try here- dsprelated.com/showmessage/59527/1.php $\endgroup$ – Jim Clay Apr 26 '13 at 18:16
  • $\begingroup$ For example I used following two signals s1 ans s2: s1 = [1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1] s2 = [1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1] r1 = numpy.correlate(s1, s1, mode='full') r2 = numpy.correlate(s2, s2, mode='full') I used these four lines in a python code. I got r1 = [1 2 1 2 4 2 3 6 3 4 8 4 3 6 3 2 4 2 1 2 1] and r2 = [1 0 1 1 2 0 3 2 3 2 6 2 3 2 3 0 2 1 1 0 1] both r1 and r2 gives a same rainbow curve like shape.. How can i determine in the code that one signal is peroidc or nearly periodic or not periodic at all, thanks $\endgroup$ – safzam Apr 29 '13 at 15:48
4
$\begingroup$

Jim's answer sent me to think about how to test this statistically. This led me to the Durbin-Watson autocorrelation test.

The generalization of it is to form:

$$ DW(\tau) = \frac{\displaystyle \sum_{n=\tau}^{N-1} \left [ U(n) - U(n-\tau) \right ]^2 }{\displaystyle\sum_{n=0}^{N-1} U(n)^2} $$

and my attempt at implementing this in scilab is:

// http://en.wikipedia.org/wiki/Durbin%E2%80%93Watson_statistic
s1 = [1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 1 1 0 0 1 0 1 0 1 0 1 0 0 0 0 1 0 1];
s1n = s1 - mean(s1);
xs1 = xcorr(s1n,"unbiased");
N1 = length(xs1);

s2 = [1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0];
s2n = s2 - mean(s2);
xs2 = xcorr(s2n,"unbiased");
N2 = length(xs2);

dwstat1 = [];
dwstat2 = [];

for lag = 1:15,

    dxs1 = xs1((lag+1):N1) - xs1(1:(N1-lag));
    dxs2 = xs2((lag+1):N2) - xs2(1:(N2-lag));


    dwstat1 = [dwstat1 sum(dxs1.^2) / sum(xs1.^2)];
    dwstat2 = [dwstat2 sum(dxs2.^2) / sum(xs2.^2)];

end;

The upshot is that if $DW(\tau)$ is close to zero or close to 4 for a given value of $\tau$, then there is a periodicity (autocorrelation) there.

If I plot the result for our two example sequences:

enter image description here

Then it's clear that the second sequence exhibits correlation at lags of 4, 8, etc. and anti-correlation at lags of 2, 6, etc.

What I'm still not sure about is how to say $DW(\tau)$ is "close to" 0 or 4. I'll dig a little further and see what I come up with.

$\endgroup$
  • $\begingroup$ thank you for this info. Infact I am making a program in python where I get a lot of lists of 0s and 1s. I want to separate periodic, random, burst type of series. I am trying the above logic in python but "xcorr" function is not in python, then I used numpy.correlate(lst, lst, mode='full') function. Also the lists contains round 70,000 list of 0s and 1s.. I just want to determine if this list is periodic or not... if there is a little un periodicity I can avoid it. any further hint plz. thanks in advance. $\endgroup$ – safzam May 15 '13 at 13:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.