Abstract:
Accurate correction of a local clock that avoids excessive drift in the local clock while avoiding an accumulation of quantization errors. A local clock according to the present techniques generates a local time by accumulating a sequence of rate coefficients selected from a plurality of rate coefficients using a series of progressively longer replacement periods.

Description:
BACKGROUND 
   A wide variety of electronic systems may include a local clock. Examples of devices that may include a local clock are numerous and include computer systems, servers, storage devices, test instruments, industrial control devices, environmental control devices, and appliances. 
   A local clock may include a counter and an oscillator that generates an oscillator signal that causes the counter to increment its count. For example, an oscillator signal having a frequency of one megahertz may cause a counter to increment its count every microsecond, i.e. to count microseconds. Higher frequency oscillators may be used to provide higher time resolutions. 
   A local time may be associated with a counter by incrementing the counter with a value other than one. For example an oscillator having a frequency of 250 kHz may be used to increment a counter by four every four microseconds in order to maintain a time count in microseconds. A value by which a counter is incremented depends on the rate of its oscillator compared to a time increment to be counted. 
   The frequency of an oscillator in a local clock may change over time. For example, the frequency of an oscillator may change in response to changes in temperature or other environmental factors. Changes to the frequency of an oscillator may cause a local clock to run faster at some times and slower at other times, thereby decreasing its accuracy. 
   One prior technique for improving the accuracy of a local clock is to periodically apply a correction. For example, a correction may be added to or subtracted from a local clock to bring it into agreement with a reference time. Unfortunately, applying a correction to a local clock leaves the local clock free to later drift out of agreement with the reference time. Corrections may be frequently applied to a local clock but at the risk of accumulating excessive quantization errors. For example, a local clock that holds an n bit value has a possible quantization error of 1/n during each addition or subtraction of a correction. 
   SUMMARY OF THE INVENTION 
   Accurate correction of a local clock is disclosed that avoids excessive drift in the local clock while avoiding an accumulation of quantization errors. A local clock according to the present techniques generates a local time by accumulating a sequence of rate coefficients selected from a plurality of rate coefficients using a series of progressively longer replacement periods. 
   Other features and advantages of the present invention will be apparent from the detailed description that follows. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The present invention is described with respect to particular exemplary embodiments thereof and reference is accordingly made to the drawings in which: 
       FIG. 1  shows a local clock according to the present teachings; 
       FIG. 2  shows one embodiment of a rate correction circuit according to the present teachings. 
   

   DETAILED DESCRIPTION 
     FIG. 1  shows a local clock  10  according to the present teachings. The local clock  10  includes a counter  12  that generates a time count  18  in response to an oscillator signal  16  from an oscillator  14 . The oscillator signal  16  causes the counter  12  to increment, e.g. on rising edges of the oscillator signal  16 . The local clock  10  includes a rate correction circuit  20  and an accumulator  22  that generate a local time  110  by accumulating a set of rate coefficients  100  in response to the time count  18 . The rate correction circuit  20  selects a sequence of rate coefficients  100  using a series of progressively longer replacement periods. 
   The rate coefficients  100  may be referred to as A 0 , A 1 , . . . A M . The rate correction circuit  20  selects a coefficient  40  from among the rate coefficients A 0 , A 1 , . . . A M  for accumulation by the accumulator  22  for each step in the time count  18 . 
   Table 1 shows the index i of the rate coefficient A i  that is selected by the rate correction circuit  20  this embodiment in the time count  18  in one embodiment. In this embodiment, the rate coefficient A 1  replaces every 4th use of the rate coefficient A 0 . The rate coefficient A 2  replaces every 4th use of the rate coefficient A 1 , and so on. 
   
     
       
             
             
             
           
             
             
             
           
         
             
                 
               TABLE 1 
             
             
                 
                 
             
             
                 
               Time 
               Rate 
             
             
                 
               Count 
               coefficient 
             
             
                 
               (hex) 
               Index i 
             
             
                 
                 
             
           
           
             
                 
             
           
        
         
             
                 
                1 
               0 
             
             
                 
                2 
               0 
             
             
                 
                3 
               0 
             
             
                 
                4 
               1 
             
             
                 
                5 
               0 
             
             
                 
                6 
               0 
             
             
                 
                7 
               0 
             
             
                 
                8 
               1 
             
             
                 
                9 
               0 
             
             
                 
               A 
               0 
             
             
                 
               B 
               0 
             
             
                 
               C 
               1 
             
             
                 
               D 
               0 
             
             
                 
               E 
               0 
             
             
                 
               F 
               0 
             
             
                 
               10 
               2 
             
             
                 
               11 
               0 
             
             
                 
               12 
               0 
             
             
                 
               13 
               0 
             
             
                 
               14 
               1 
             
             
                 
               15 
               0 
             
             
                 
               16 
               0 
             
             
                 
               17 
               0 
             
             
                 
               18 
               1 
             
             
                 
               19 
             
             
                 
                 
             
           
        
       
     
   
   The allocation of the rate coefficients A 0 , A 1 , . . . A M  to the steps in the count  18  provide a set of replacement periods. The replacement periods may be referred to as N 0 , N 1  . . . N M . The replacement periods N 0 , N 1  . . . N M  in one embodiment are multiples of each other such that N j =k*N j+1 , for all j where the multiplication factor k is a power of two. In the case of k=4, the local time  110  accumulates as A 0, 2 *A 0 , 3*A 0 , (A 1 +3*A 0 ), (A 1 +4*A 0 ), (A 1 +5*A 0 ), (A 1 +6*A 0 ) (2*A 1 +6*A 0 ), . . . (3*A 1 +12*A 0 ), (A 2 +3*A 1 +12*A 0 ), (A 2 +13*A 0 ) and so on. Each rate coefficient A 0 , A 1 , . . . A M  has a range of zero to (2^k−1). The rate coefficients A 0 , A 1 , . . . A M  and the replacement periods N 0 , N 1 . . . N   M  yield an instantaneous quantization error in the local time  110  that does not exceed k/2 times the rate coefficient LSB. Each time the quantization error of the local time  110  approaches k/2 times the rate coefficient LSB, another longer-period rate coefficient is invoked. 
   In one embodiment, the counter  12  is a binary counter of length log 2(k*M) bits. 
     FIG. 2  shows one embodiment of the rate correction circuit  20 . The rate correction circuit  20  includes a set of AND gates  60 - 62  and a set of OR gates  63 - 65  that implement a multiplexor and some enable logic  50  for the multiplexor. The enable logic  50  enables uses the AND gates  60 - 62  to enable the rate coefficients A 0 , A 1 , . . . A M  via a set of enable signals  70 - 72  (Enable 0  through Enable M ). The enable logic  50  enables only one of the rate coefficients A 0 , A 1 , . . . A M  at each step of the time count  18 . The OR gates  63 - 65  provide the enabled rate coefficient  40  to the accumulator  22 . 
   The enable signals  70 - 72  are determined by combining bits of the time count  18 . The enable signal  70 , Enable 0 , for the 0th rate coefficient is ˜(˜x 0  &amp; ˜x 1  &amp; ˜x 2  &amp; . . . &amp; ˜x k−2  &amp; x k−1 ). The enable signal Enable i  for the ith positive rate coefficient is (˜x 0  &amp; ˜x 1  &amp; ˜x 2  &amp; &amp; ˜x p−2  &amp; x p−1 ) &amp; ˜(˜x p  &amp; ˜x p+1  &amp; ˜x p+2  &amp; . . . &amp; ˜x p+k−2  &amp; x p+k−1 ), where p=i*k. In this equation, the x&#39;s are the bit values of all of the stages of the counter  12 . In an embodiment in which k=4 and M=3, the counter  12  is 12-stage binary counter that derives the enable signals  70 - 72  for the four rate coefficients A 0 , A 1 , A 2 , and A 3 . The enable signals  70 - 72  for this embodiment are as follows.
         Enable 0 =˜(˜x 0  &amp; ˜x 1  &amp; ˜x 2  &amp; x 3 )   Enable 1 =(˜x 0  &amp; ˜x 1  &amp; ˜x 2  &amp; x 3 ) &amp; ˜(˜x 4  &amp; ˜x 5  &amp; ˜x 6  &amp; x 7 )   Enable 2 =(˜x 0  &amp; ˜x 1  &amp; ˜x 2  &amp; ˜x 3  &amp; ˜x 4  &amp; ˜x 5  &amp; ˜x 6  &amp; ˜x 7 ) &amp; ˜(˜x 8  &amp; ˜x 9  &amp; ˜x 10  &amp; x 11 )   Enable 3 =(˜x 0  &amp; ˜x 1  &amp; ˜x 2  &amp; ˜x 3  &amp; ˜x 4  &amp; ˜x 5  &amp; ˜x 6  &amp; ˜x 7  &amp; ˜x 8  &amp; ˜x 9  &amp; ˜x 10  &amp; x 11 )       

   The rate correction circuit selects higher index rate coefficients with progressively less frequency. In the example embodiment set forth above, the A 0  rate coefficient is used 15 times for every 16 steps of the counter  12 . The A 1  rate coefficient is used 15 times for every 256 (16*16) steps of the counter  12 . The A 2  rate coefficient is used 15 times for every 4096 (16*16*16) steps of the counter  12 . The A 3  rate coefficient is used once every 4096 steps of the counter  12 . In an embodiment with an integer number of counter stages and k stages between each rate coefficient and a total of M+1 rate coefficients, the number of times each rate coefficient is applied is n i =(k−1)*2^(k*M)/2^(k*(i+1)) for i&lt;M and n m =1. 
   For the example above, the number of times each rate coefficient is selected is as follows.
         n 0 =3840   n 1 =240   n 2 =15   n 3 =1       

   The local clock  10  improves quantization accuracy over the prior art technique of one correction per correction interval by a factor of k to the M power. The instantaneous accuracy of the local clock  10  is also high because the rate coefficients A 0 , A 1 , . . . A M  are applied relatively frequently. 
   Additional rate coefficients may be used to decrease the value of k and therefore the maximum quantization error, but with an increase in hardware. If the replacement periods N 0 , N 1  . . . N M  are not uniform multiples of each other, then the quantization error is corrected more frequently by some rate coefficients and less frequently by other rate coefficients. 
   The rate coefficients A 0 , A 1 , . . . A M  are selected to yield a final count F. The final count F may be derived from a time offset for correcting the local time  110 , e.g. during IEEE 1588 time synchronization. The most frequently used rate coefficient is selected first and then the others are selected in sequence. The rate coefficients A 0 , A 1 , . . . A M  are determined as follows.
         A 0 =floor(F/n 0 )   A 1 =floor((F−A 0 *n 0 )/n 1 )   A 2 =floor((F−A 0 *n 0 −A 1 *n 1 )/n 2 )   A i =floor((F−A 0 *n 1  . . . −A i−1 *n i−1 )/n i )       

   For the example above, with a final count F equal to 16,793, then the rate coefficients A 0 , A 1 , . . . A M  are as follows.
         A 0 =4   A 1 =5   A 2 =15   A 3 =8       

   Alternative counting schemes may be used in the local clock  10 , but at the expense of more complicated rate coefficient selection logic. Counting schemes in which the frequency of rate coefficient use does not decrease geometrically with rate coefficient number will make suboptimal use of the rate coefficients by allowing more error. 
   The foregoing detailed description of the present invention is provided for the purposes of illustration and is not intended to be exhaustive or to limit the invention to the accurate embodiment disclosed. Accordingly, the scope of the present invention is defined by the appended claims.