INFERRING THE PERIODICITY OF DISCRETE SIGNALS

• US 20130307524A1
• Filed: 05/02/2013
• Published: 11/21/2013
• Est. Priority Date: 05/02/2012
• Status: Abandoned Application

• Current Assignee: Ramot at Tel Aviv University Limited (Tel Aviv University)
• Original Assignee: Ramot at Tel Aviv University Limited (Tel Aviv University)
• Inventors: Shavitt, Yuval, Weinsberg, Udi, Argon, Oded
• Application Number:
  US13/875,486
• Publication Number:
  US 20130307524A1
• Time in Patent Office: Days
• US Class Current: 324/76.39
• CPC Class Codes: G01R 23/02 Arrangements for measuring frequency, e.g. pulse repetition rate; Arrangements for measuring period of current or voltage
• CPC Class Codes: G06F 17/18 for evaluating statistical data , e.g. average values, frequency distributions, probability functions, regression analysis forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04
• CPC Class Codes: G06F 2218/14 by matching peak patterns

Abstract

A method for testing a signal comprises obtaining a signal, determining whether the signal has at least one period, measuring that period and providing the measurement as output. A power spectral density estimation can be used for signals having a single period, and an autocorrelation function with slicing can be used in an iterative procedure for finding multiple periods within signals.

Claims

1. A method for testing a signal comprising:

obtaining the signal;

determining whether the signal has at least one period;

measuring the period; and

outputting the period.

2. The method of claim 1 comprising using power spectral density if only one period is detected, to measure the period, and if multiple periods are detected then obtaining an autocorrelation of the signal, slicing the autocorrelation into slices, for each slice finding peaks and lags, and wherein the measuring the signal comprises setting a current period as a longest one of the lags.

3. The method of claim 2, comprising iteratively coarsening the slices to find further ones of the multiple periods in the signal.

4. The method of claim 2, further comprising stopping the iterative coarsening when all determined periods are contained within a single slice.

5. The method of claim 1, wherein when the determining whether the signal has at least one period comprises determining that the signal has only one period, using a power spectral density to determine the frequency of the only one period.

6. The method of claim 1, wherein the outputting the period comprises outputting a list of all periods found in the obtained signal, and providing a confidence value for each period in the list.

7. The method of claim 6, comprising calculating the confidence value by dividing a number of lags found by a number of lags expected for the current period.

8. The method of claim 1, comprising finding successively longer periods in the obtained signal by iteratively relaxing a time-domain autocorrelation function.

9. The method of claim 8, wherein the finding successively longer periods at least partly comprises finding peak levels in the autocorrelation function, peak levels of different amplitude being assigned to different periods and peak levels of a same amplitude being assigned to a same period.

10. The method of claim 1, wherein the obtaining a signal further comprises shaping the signal to capture a periodic change therein.

11. The method of claim 10, wherein the capturing comprises one member of the group comprising:

a) apply a start value and repeatedly negate the value upon changes in the signal;

b) for a signal having a range, dissecting the range into two range parts and assigning each range part a value from {“

1”

, “

−

1”

}; and

c) obtaining a number of packets per predetermined time period.

12. The method of claim 1, wherein the output at least one period is used to obtain at least one member of the group consisting of:

an availability of end-hosts on a network, a usage of inter-network links on a network for balancing load and cost of transit, optimal peak hour traffic shaping, alternation of allocated IP addresses, malicious host identification, network forensic analysis, and tracking infected hosts over time using their IP addresses.

13. Apparatus for testing a signal comprising:

an input for obtaining the signal;

a period detector for determining whether the signal has at least one period;

a period measurement unit associated with the period detector configured to measure the period; and

an output for outputting the measured period.

14. The apparatus of claim 13 configured to obtain an autocorrelation of the signal, and to slice the autocorrelation into slices, wherein the period detector is configured to determine whether the signal has at least one period by finding for each slice finding peaks and lags, and wherein the period measurement unit is configured to set a period as a longest one of the lags.

15. The apparatus of claim 14, configured to iteratively coarsen the slices to find further periods in the signal.

16. The apparatus of claim 14, configured to stop the iterative coarsening when all determined periods are contained within a single slice.

17. The apparatus of claim 13, wherein period detector detects only one period, the period measurement unit is configured to use a power spectral density to determine the frequency of the only one period.

18. The apparatus of claim 13, wherein the output is configured to provide a list of all periods found in the obtained signal.

19. The apparatus of claim 18, wherein the output unit is further configured to provide a confidence value for each period in the list.

20. The apparatus of claim 19, wherein the measurement unit is configured to calculate the confidence value by dividing a number of lags found by a number of lags expected for the current period.

21. The apparatus of claim 13, configured to find successively longer periods in the obtained signal by iteratively relaxing a time-domain autocorrelation function.

22. The apparatus of claim 21, wherein the finding successively longer periods at least partly comprises finding peak levels in the autocorrelation function, peak levels of different amplitude being assigned to different periods and peak levels of a same amplitude being assigned to a same period.

23. The apparatus of claim 13, wherein the input is configured to shape the signal to capture a periodic change therein.

24. The apparatus of claim 23, wherein the capturing comprises one member of the group comprising:

a) applying a start value and repeatedly negate the value upon changes in the signal;

b) for a signal having a range, dissecting the range into two range parts and assigning each range part a value from {“

1”

, “

−

1”

}; and

c) obtaining a number of packets per predetermined time period.

25. The apparatus of claim 13, further comprising using the output to obtain at least one member of the group consisting of:

an availability of end-hosts on a network, a usage of inter-network links on a network for balancing load and cost of transit, optimal peak hour traffic shaping, alternation of allocated IP addresses, malicious host identification, network forensic analysis, and tracking infected hosts over time using their IP addresses.