Abstract:
Bit and byte synchronization for sampling and decoding a data string is provided a single data field u. The data string x has pre-pended to it a short string of is (ones), followed by u to yield a string y= . . .  1111 , u, x. The string is pre-coded by convolution with 1/(1⊕D 2 ). PRML-sampling of y starts at an initial phase, and vectors are obtained from that string by sampling at pre-selected phases following the initial sampling point. The vectors of y are compared with vectors corresponding to PRML samples of an initial set of bits in u obtained at predetermined phases. The pair of y, u vectors exhibiting the minimum Euclidian distance yields a sampling correction value by which the initial sampling phase is corrected and a new initial sampling point preceding x is determined. Here, bit and byte synchronization have been achieved and sampling of x proceeds at the corrected phase, from the new initial sampling point.

Description:
BACKGROUND OF THE INVENTION  
       [0001]     The invention relates to data coding, and particularly to data coding for achieving bit and byte synchronization using a single data field.  
         [0002]     Bit synchronization refers to the synchronization of a clock for receiving or reading incoming data with the data being received or read. Normally, bit synchronization is achieved when a field of, say, 1s (ones), is written as the data is stored (or transmitted) in a partial-response, maximum-likelihood sequence (“PRML”) channel, and it is sampled using an acquisition loop. In a PRML channel, byte synchronization refers to a field with a data pattern in the data that marks the first bit of a symbol. For byte synchronization, this field is followed by a pattern that, when recognized, determines the start of data. Thus, data can be sampled and the information retrieved in the usual form.  
         [0003]     As pointed out in U.S. Pat. No. 6,089,749, the conventional byte synchronization approach has the disadvantage of a long synchronization pattern, with a significant possibility of synchronization failure. The &#39;749 patent proposes a byte synchronization scheme using a byte synchronization pattern between 16 and 18 bits in length.  
         [0004]     Our purpose is to unify both the bit synchronization and byte synchronization fields into a single field and achieve bit and byte synchronization simultaneously using the single field (“bit-byte synchronization”). The idea is that the new field is short, allowing for significant savings in magnetic disk real estate. Alternatively, the new field can be used in a hybrid way. In order to combat events like thermal asperity (TA) that wipes out a whole synchronization field, a dual synchronization architecture has been proposed: the bit-byte synchronization field is repeated twice, so if the first bit-byte synchronization field is wiped out, then the system relies on the second one to achieve synchronization. One of the problems associated with TA is loss of both bit and byte synchronization. For that reason, it would be useful to have a synchronization field that recovers bit and byte synchronization simultaneously. Such a capability is disclosed in the following specification.  
       SUMMARY OF THE INVENTION  
       [0005]     This invention combines bit and byte synchronization into a single data field u. A data string x has pre-pended to it a short string of 1s (ones), followed by u to yield a string y= . . . 1111, u, x. The string y is normally precoded by convolving it with 1/(1⊕D 2 ), where the symbol ⊕ denotes modulo 2 addition and the operator D denotes a delay of one, D 2  a delay of 2, etc. Thus, for a string x 0 ,x 1 ,x 2 ,x 3  . . . then (1⊕D 2 )(x 0 ,x 1 ,x 2 ,x 3  . . . ) denotes the string: 
        x 0 ,x 1 ,x 0 ⊕x 2 ,x 1 ⊕x 3 ,x 2 ⊕x 4  . . . 
 
 The operation 1/(1⊕D 2 ) denotes the inverse of 1⊕D 2 . PRML-sampling of y starts at an initial phase, and vectors are obtained from that string by sampling at pre-selected phases following the initial sampling point. The vectors of y are compared with vectors corresponding to PRML samples of an initial set of bits in u obtained at predetermined phases. The pair of y, u vectors exhibiting the minimum Euclidian distance yields a sampling correction value by which the initial sampling phase is corrected and a new initial sampling point preceding x is determined. Here, bit and byte synchronization have been achieved and sampling of x proceeds at the corrected phase, from the new initial sampling point. 
       
 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0007]      FIG. 1A  is a partially schematic diagram of a magnetic disk with tracks and sectors in which data is stored.  FIG. 1B  is a diagram showing a prior art format of data stored on the disk with separate fields for bit and byte synchronization patterns.  
         [0008]      FIG. 2  is a diagram showing data stored on the disk with a single field for a bit-byte synchronization pattern.  
         [0009]      FIG. 3  is a block diagram of a data transmission system in which the method of the invention is executed.  
         [0010]      FIG. 4  is a flow diagram illustrating a first embodiment of the method of the invention.  
         [0011]      FIG. 5  is a flow diagram illustrating a second embodiment of the method of the invention.  
         [0012]      FIG. 6  is a flow diagram illustrating a third embodiment of the method of the invention.  
     
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS  
       [0013]     Refer to  FIGS. 1A and 1B  in which a storage disk  100  has data stored on at least one surface  110  in a plurality of tracks (one of which is indicated by  112 ), each of which is divided into a plurality of sectors (one of which is indicated by  114 ). Previously, data sectors stored as shown in  FIG. 1A  had the format illustrated in  FIG. 1B . In  FIG. 1B , a data sector  120  has a data section  121  with data and a header section  122  with separate fields  123  and  124 . The field  123  holds a bit synchronization pattern and the data field  124  holds a byte synchronization pattern. The invention is represented by the data string format of  FIG. 2  where a data sector  130  has a data section  131  with data and a header section  132  with a single field  133  holding a single synchronization pattern for bit-byte synchronization.  
         [0014]     In the discussion that follows, a 20-bit bit-byte synchronization pattern is set forth to illustrate certain principles. However, it will be clear to those skilled in the art that the ideas and algorithms to be presented can be adapted to a bit-byte synchronization pattern of any size.  
         [0015]     The bit-byte synchronization pattern is preceded by a sufficient number of is such that sampling starts before the pattern is encountered. The exemplary 20-bit bit-byte synchronization pattern is: 
 
 u =(10110111111011011111)  (1) 
 
         [0016]     The string . . . 1111, u, x is transmitted, where x is the data. Sampling of the string starts at any moment prior to u. The idea is that once u is read, both byte synchronization and very close bit-synchronization have been achieved.  
         [0017]     The method of bit-byte synchronization proceeds as follows. Consider the string y=. . . 1111, u, x, with u and x as described above. The first step is to precode y by convolving it with 1/(1⊕D 2 ), where ⊕ denotes modulo-2 addition. This precoded string is then sampled at an initial unknown point f using PRML. In a noiseless environment, when the first 16 bits of u, are sampled, i.e., (1011011111101101), at phases 0, 0.125, 0.25, 0.375, 0.5, 0.625, 0.75 and 0.875 respectively using PRML, the following 8 vectors are obtained (notice that precoding makes the samples of u 0  below coincide in absolute value with the first 16 bits of u):  
                 u   _     0     =       ⁢     (     1   ,   0   ,     -   1     ,   1   ,   0   ,     -   1     ,   1   ,   1   ,     -   1     ,     -   1     ,   1   ,   0   ,     -   1     ,   1   ,   0   ,     -   1       )                     u   _     1     =       ⁢     (     1.11   ,     -   0.29     ,     -   0.82     ,   1.12   ,     -   0.29     ,     -   0.84     ,   1.19   ,   0.78   ,                       ⁢       -   1.18     ,     -   0.76     ,   1.1   ,     -   0.29     ,     -   0.82     ,   1.12   ,     -   0.29     ,     -   0.84       )                   u   _     2     =       ⁢     (     1.13   ,     -   0.57     ,     -   0.57     ,   1.15   ,     -   0.56     ,     -   0.61     ,   1.32   ,   0.54   ,                       ⁢       -   1.31     ,     -   0.51     ,   1.13   ,     -   0.57     ,     -   0.58     ,   1.15   ,     -   0.56     ,     -   0.62       )                   u   _     3     =       ⁢     (     1.09   ,     -   0.81     ,     -   0.3     ,   1.1   ,     -   0.8     ,     -   0.36     ,   1.41   ,   0.27   ,                       ⁢       -   1.4     ,     -   0.21     ,   1.1   ,     -   0.81     ,     -   0.3     ,   1.12   ,     -   0.79     ,     -   0.37       )                   u   _     4     =       ⁢     (     0.98   ,     -   0.99     ,   0   ,   0.99   ,     -   0.98     ,     -   0.08     ,   1.44   ,   0   ,                       ⁢       -   1.44     ,   0.08   ,   0.98   ,     -   1     ,   0   ,   1   ,     -   0.97     ,     -   0.09       )                   u   _     5     =       ⁢     (     0.8   ,     -   1.11     ,   0.3   ,   0.8   ,     -   1.1     ,   0.21   ,   1.4   ,     -   0.27     ,                       ⁢       -   1.41     ,   0.36   ,   0.8   ,     -   1.12     ,   0.3   ,   0.81   ,     -   1.08     ,   0.2     )                   u   _     6     =       ⁢     (     0.56   ,     -   1.15     ,   0.59   ,   0.57   ,     -   1.13     ,   0.51   ,   1.31   ,     -   0.54     ,                       ⁢       -   1.32     ,   0.61   ,   0.56   ,     -   1.15     ,   0.58   ,   0.57   ,     -   1.13     ,   0.5     )                   u   _     7     =       ⁢     (     0.3   ,     -   1.12     ,   0.82   ,   0.29   ,     -   1.1     ,   0.76   ,   1.18   ,     -   0.78     ,                       ⁢       -   1.19     ,   0.84   ,   0.29   ,     -   1.12     ,   0.82   ,   0.29   ,     -   1.1     ,   0.76     )             
 
         [0018]     Consider m=min{d(u i , u j ), 0≦i≦j≦ 7 }, where d(u i , u j ) denotes the Euclidean distance between u i  and u j . The 16-bit vector (1011011111101101) was chosen in such a way that it maximizes m. Of course other choices are possible, but this vector is the one that gives the best results with the algorithms for bit-byte synchronization to be described next. However, this is only a preferred embodiment and several others are obvious to those skilled in the art.  
         [0019]      FIG. 3  illustrates a data transmission system in which the invention may be practiced. In this regard, a data transmission system is one that communicates encoded data between two entities. The data transmission system may be, for example, a broadcast or guided wire telecommunication system. Preferably, the system is a component of a disk drive in which data is prepared for storage, stored on one or more magnetic disks, retrieved from disk storage, and processed for use. The system includes a PRML encoder  300  that receives and encodes a stream of data to produce a data stream x. The data stream is formatted by a formatter  302  into a string y, where y=1111, u, x. The string y is pre-coded by a pre-coder  304 , which produces a pre-coded string (1/(1⊕D D 2 ))·y. The pre-coded string passes through a noisy channel  306  (such as by being written to and read from one or more data storage disks) whence it is received by a sampler  308 , which produces PRML samples of the now noisy pre-coded string, with sampling starting at some arbitrary point and producing a string of samples at points f, f+1, f+2, . . . before the start of u. A synchronizer  310  receives the samples and uses pre-determined samples u j  of u to determine bit/byte synchronization. When synchronization is found, the synchronizer adjusts the sampling points and indicates that synchronization is achieved to the sampler  308  and a PRML detector  320 . The sampler adjusts and resets sampling, and the PRML detector applies PRML decoding to the adjusted sampled data to produce an estimate of the data stream x. The data stream x may then be decoded.  
         [0020]     The synchronizer operates by implementing one of the following algorithms.  
         [0021]     Algorithm 2.1 Assume the string . . . 1111, u, x, where u is defined in (1) and x is random data. This string is precoded by convolution with 1/(1⊕D 2 ) and PRML sampling of the precoded string starts at points f, f+1, f+2, . . . before the start of u, where the initial sampling point f is random and unknown. The sampled signal will be possibly subject to noise. Denote this sampled and possibly noisy signal by v 0 , v 1 , v 2 , . . . . Then, the algorithm proceeds as follows: 
    Set i←0.     BACK:     For each 0≦j≦7, let v i , =(v i , v i+1 , . . . , v i+15 ) and d i,j =d(v i , u j ;).     If d i,j ≦2 then go to NEXT, else     Set i←i+1 and go to BACK.     NEXT:     Let m i =min{d i,j , 0≦j≦ 7 }, and mi+=min{d+lj,  0 &lt;j&lt; 7 }.     If m i &gt;m i+1 , then set if i←1 and go to BA CK.     Let j o  be such that m i =d i,jo .     Reset the phase as f←f−(j 0 /8).     Start sampling the data at sampling points f+i+20, f+i+21, f+i+22 . . . to obtain a sampled sequence w=w 0 , w 1 , w 2 , . . . . 
 
 Apply maximum likelihood decoding to w to obtain an estimate of x. 
   
 
         [0033]     An example of Algorithm 2.1 is as follows.  
       Example 2.1  
       [0034]     Assume the string 
        . . . 1111, u, x=( . . . 11111011011111101101111111011 . . . ) 
 
 where u is defined in (1). Precoding this string yields 
    1/(1⊕D 2 )( . . . 1111,u,x)=( . . . 11001001001100100100110011100 . . . ) 
 
 Next, assume that sampling starts at point 0.35 (which is unknown) and the following samples are obtained: 
    −0.05 −0.2 −1.34 −0.29 1.1 −0.77 −0.35 1.11 −0.76 −0.42 1.39 0.33 −1.39 −0.28 1.1 −0.77 −0.36 1.12 −0.76 −0.43 1.39 0.33 −1.39 −0.3 1.3 0.63 −0.34 −1.23 −0.6 . . . 
 
 By adding white gaussian noise with a variance of 0.06 to the samples above, for instance, the following samples may be obtained: 
    −0.09 −0.12 −1.37 −0.22 1.12 −0.75 −0.38 1.07 −0.74 −0.46 1.31 0.35 −1.3 −0.29 1.02 −0.86 −0.38 1.21 −0.69 −0.47 1.37 0.27 −1.37 −0.31 1.25 0.7 −0.25 −1.33 −0.57 . . . =v 0 v 1  . . . v 28          
 
         [0039]     By applying at each step the algorithm, notice that for each 0≦j≦7 and v i =(v i , v i+1 , . . . v i+l5 ), d i,j =d(v i , u j ) gives:  
                                                                                                     i   d i,0     d i,1     d i,2     d i,3     d i,4     d i,5     d i,6     d i,7                                  0   9.44   12.78   16.57   20.83   25.18   29.27   33.1   36.33       1   17.13   13.03   9.56   6.95   5.4   4.91   5.61   7.36       2   47.94   47.08   44.55   41.28   36.97   31.81   26.23   21.01       3   16.24   21.67   26.96   32.24   36.85   40.5   43.16   44.81       4   4.86   2.03   0.4   0.1   1.15   3.5   7.11   11.62                  
 
         [0040]     It can be seen that the minimum is achieved at d 4,3 . Therefore, the phase will be corrected in ⅜=0.375. Since the original (unknown) sampling point was 0.35, this sampling point is reset as 0.35−0.375=−0.025. Since i=4, sampling starts at points 
        f+i+20,f+i+21,f+i+22 . . . =23.975 ,24.975 , 25.975.        
 
         [0042]     Notice that for perfect bit-byte synchronization, it would be necessary to sample at points 24, 25, 26.  
         [0043]     The bit-byte synchronization method described in Algorithm 2.1 provides useful results. However, even in a noiseless situation, an error of 0.06 (or 6%) is common. Although such an error is not catastrophic, the noise can easily make synchronization even more difficult. One way to make the sampling more precise is by increasing the number of comparison vectors u i . In the preferred embodiment described above these vectors are obtained by sampling at skips of 0.125. Smaller sample intervals may be taken. Of course doing so would increase the complexity of the system.  
         [0044]      FIG. 4  illustrates a method  400  according to Algorithm 2.1. The method is represented by a flow diagram with the understanding that it would be embodied either as a processor program comprising a series or sequence of commands executed by the synchronizer  310  of  FIG. 3 . Preferably, the method  400  operates on a string . . . 1111, u, x, and is preceded by pre- coding the string as discussed above, which produces the pre-coded data string y. The method begins in step  410  by sampling the string to obtain the sample vectors v 0 , v 1 , v 2 , . . . at the sampling points f, f+1, f+2, . . . before the start of u. An iteration counter i is initialized in step  412 . Then, in step  414  the Euclidian distance d i,j  is taken between a current sample vector v i  and each of eight sample vectors of u. According to the test in step  416 , if the Euclidian distance d i,j  is greater than 2, the method increments i by one and loops back through  414 ; otherwise, the method goes to step  420 . In step  420 , a first minimum Euclidian distance m i  is the minimum d i,j  calculated with v i , and a second minimum Euclidian distance m i+1  is the minimum d i+1,j  calculated with v i+1 . The minimum m i  is searched for in decision  421  by comparing the current m i  with m i+1  and, if necessary, incrementing i and looping through steps  420 ,  421  and  422  until the minimum m i  is found. The minimum value of m i  is used in step  423  to calculate a value (j 0 /8) with which to adjust the sampling points. With the adjustment, a sampled sequence w is obtained in step  424  from which an estimate of the data string x is derived by maximum likelihood decoding.  
         [0045]     Another alternative is to perform an interpolation process. One way to do this is to take, instead of the smallest sampled value, a number of smallest ones (for example, the three smallest ones) and interpolate between them. This process will be described in the next algorithm.  
         [0046]     Algorithm 2.2 Assume the string . . . 1111, u, x, where u was defined in (1) and x is random data. This string is precoded by convolution with 1/(1⊕D 2 ). Then, PRML sampling of the precoded string starts at points f, f+1, f+2 . . . before the start of u, where the initial sampling point f is random and unknown. The sampled signal will possibly be subject to noise. Denote this sampled and possibly noisy signal by v 0 , v i , v 2 , . . . . Then, proceed as follows: 
    Set     i←0.     BACK: For each 0≦j≦7, let v i , =(v i , v i+1 , . . . , v i+15 ) and d i,j =d(v i , u j ).     If d i,j ≦2 then go to NEXT, else,     Set i←i+1 and go to BACK.     NEXT: Consider the vector of distances of length 16:  
               d   _     =       ⁢     (       d       i   +   1     ,   0       ,     d       i   +   1     ,   1       ,   …   ⁢           ,     d       i   +   1     ,   7       ,     d     i   ,   0       ,     d     i   ,   1       ,   …   ⁢           ,           ⁢     d     i   ,   7         )                 =       ⁢     (       d   0     ,     d   1     ,   …   ⁢           ,     d   15       )               
   
 
         [0053]     Now, consider l, 0≦l≦13 such that d 1 , d 1+1 , d 1+2 , are the smallest values in d (without loss of generality, it may be assumed that these three values are consecutive, although this assumption is not necessary to the operation of the algorithm). Consider the vector of length 16:  
               a   _     =     (     0   ,   0.125   ,   0.25   ,   …   ⁢           ,   0.875   ,   1   ,   1.125   ,   …   ⁢           ,   1.875     )                 =     (       a   0     ,     a   1     ,   …   ⁢           ,     a   15       )               
     Let     
       r   =             ⅆ     l   +       1     ⁢         ⅆ     l   +       2     ⁢     a   l         +       ⅆ   l     ⁢       ⅆ     1   +   2       ⁢     a     l   +   1           +       ⅆ   l     ⁢       ⅆ     l   +   1       ⁢     a     l   +   2                 ⅆ     l   +   1       ⁢       ⅆ     l   +   2       ⁢     +       ⅆ   l     ⁢       ⅆ     l   +   2       ⁢     +       ⅆ   l     ⁢     ⅆ     l   +   1                           
    Make f←f−(r−1).     Start sampling the data at sampling points f+i+20, f+i+21, f+i+22 . . . to obtain a sampled sequence w=w 0 , w 1 , w 2 , . . . 
 
 Apply maximum likelihood decoding to w to obtain an estimate of x. 
   
 
       Example 2.2  
       [0056]     As an example of Algorithm 2.2, similarly to Example 2.1, assume a string: 
        . . . 1111, u, x=( . . . 11111011011111101101111101010 . . . ), 
 
 where u was defined in (1). Precoding this string, we obtain  
           1     1   ⊕     D   2         ⁢     (       …   ⁢           ⁢   1111     ,   ,     u   _     ,     x   _       )       =     (     …   ⁢           ⁢   11001001001100100100110001000   ⁢           ⁢   …     ⁢           )         
 
 Next, assuming that sampling of the precoded string starts at the unknown initial point 1.97, the following samples are obtained: 
    −0.97 −0.05 0.96 0.06 −1.03 0.96 0.06−1.03 0.94 1.04 −0.95 −1.05 0.96 0.06 −1.03 0.96 0.06 −1.03 0.94 1.04 −0.95 −1.03 −0.04 0.98 0.06 −1.01 −0.04 0.98 0.04 . . . 
 
 By adding white gaussian noise with a variance of 0.06 to the samples above, for instance, the following samples may be obtained: 
    −0.96 −1.01 0.98 0.2 −0.96 1.02 −0.04 −0.92 0.86 0.94 −0.87 −1.1 0.92 0.04 −1.09 0.87 0.01 −1.09 0.99 0.96 −0.96 −0.99 0.02 0.94 0.12 −1.03 −0.12 1.01 0.08 . . . =v 0  v 1  . . .     . . .        
 
         [0061]     By applying at each step the algorithm, notice that for each 0≦j≦7 and v i =(v i , v i+1 , . . . , v i+15 ), di,j=d(v i , u j ) gives:  
                                                                                                     i   d i,0     d i,1     d i,2     d i,3     d i,4     d i,5     d i,6     d i,7                                  0   40.44   36.57   31.75   26.82   21.76   16.8   12.31   8.86       1   32.23   36.81   40.22   42.97   44.37   44.33   43.01   40.85       2   0.14   1.13   3.36   6.79   11.11   16.11   21.61   27.17       3   29.98   24.76   19.22   14   9.24   5.21   2.19   0.5                  
 
 Notice that, according to Algorithm 2.2, d i,j ≦2 is achieved at i=2, so  
               d   _     =       ⁢     (       d       i   +   1     ,   0       ,     d       i   +   1     ,   1       ,   …   ⁢           ,     d       i   +   1     ,   7       ,     d     i   ,   0       ,     d     i   ,   j       ,   …   ⁢           ,           ⁢     d     i   ,   7         )                 =       ⁢     (     29.98   ,   24.76   ,   19.22   ,   14   ,   9.24   ,   5.21   ,   2.19   ,   0.5   ,                       ⁢     0.14   ,   1.13   ,   3.36   ,   6.79   ,   11.11   ,   16.11   ,   21.61   ,   27.17     )             
 
 Manifestly,  1 =7, thus, (a l , a l+, a   l+2 )=(0.875, 1, 1.125) and (d l , d l+1 , d l+2 )=(0.5, 0.14,1.13). This gives,  
       r   =             ⅆ     l   +   1       ⁢       ⅆ     l   +   2       ⁢     a   l         +       ⅆ   l     ⁢       ⅆ     1   +   2       ⁢     a     l   +   1           +       ⅆ   l     ⁢       ⅆ     l   +   1       ⁢     a     l   +   2                 ⅆ     l   +   1       ⁢       ⅆ     l   +   2       ⁢     +       ⅆ   l     ⁢       ⅆ     l   +   2       ⁢     +       ⅆ   l     ⁢     ⅆ     l   +   1                       =   0.99         
 
 Since the initial (unknown) sampling point was 1.97 and i=2, according to Algorithm 2.2,f is reset to f←f−(r−1)=1.97−(0.99 −1)=1.98 and sampling starts at points 
        f+i+20, f+i+21, f+i+22 . . . =23.98, 24.98, 25.98, . . . . 
 
 Again, notice that for perfect bit-byte synchronization, one would need to sample at points 24, 25, 26, . . . 
       
 
         [0063]      FIG. 5  illustrates a method  530  according to Algorithm 2.2. The method is represented by a flow diagram with the understanding that it would be embodied either as a processor program comprising a series or sequence of commands executed by the synchronizer  310  of  FIG. 2 . Preferably, the method  530  operates on a string . . .1111, u, x, and is preceded by pre-coding the string as discussed above, which produces the pre-coded data string y. The method begins in step  410  by sampling the string to obtain the sample vectors v 0 , v 1 , v 2 , . . . at the sampling points f, f+1, f+2, . . . before the start of u. An iteration counter i is initialized in step  412 . Then, in step  414  the Euclidian distance dij is taken between a current sample vector v i  and each of eight sample vectors of u. According to the test in step  416 , if the Euclidian distance d i,j  is greater than 2, the method increments i by one and loops back through  414 ; otherwise, the method goes to step  531 . In step  531 , a vector d of sixteen Euclidian distances is calculated with v i  and u j  and the three smallest values of d are selected in step  532 . The sixteen unit vector a is accessed in step  533  and the elements of a at the same vector locations as the three smallest values of d are combined with the three smallest values of d in step  534  to obtain a value r representing interpolation among the three smallest values of d. The value of r is used to adjust the initial sampling point f in step  535 . With the adjustment, a sampled sequence w is obtained in step  536  from which an estimate of the data string x is derived by maximum likelihood decoding.  
         [0064]     The next algorithm introduces a modification that makes it slightly more efficient than Algorithm 2.2.  
         [0065]     Algorithm 2.3 Assume the string . . . 1111, u, x, where u was defined in (1) and x is random data. This string is precoded by convolution with 1/(1⊕D 2 ) and PRML sampling of the precoded string starts at points f, f+1, f+2, . . . before the start of u, where the initial sampling point f is random and unknown. The sampled signal will be possibly subject to noise. Denote this sampled and possibly noisy signal by v 0 , v 1 , v 2 , . . . Then, proceed as follows: 
    Set     i←0     BACK: For each 0≦j≦7, let v i =(v i , v i+1 , . . . , v i+15 ) and d i,j =d(v i , u j ).     If d i,j ≦2, then go to NEXT, else,     Set if i←i+1 and go to BACK.     NEXT: Consider the vector of distances of length 16 
               d   _     =       ⁢     (       d       i   +   1     ,   0       ,     d       i   +   1     ,   1       ,   …   ⁢           ,     d       i   +   1     ,   7       ,     d     i   ,   0       ,     d     i   ,   1       ,   …   ⁢           ,           ⁢     d     i   ,   7         )                     ⁢     (       d   0     ,     d   1     ,   …   ⁢           ,     d   15       )               
 
 Consider 1, 0≦l≦13 such that d l+1  is the smallest value in d and, without loss of generality, d l , d l+1 , and d l+2  are the three smallest values in d. Consider the vector of length 16:  
               a   _     =     (     0   ,   0.125   ,   0.25   ,   …   ⁢           ,   0.875   ,   1   ,   1.125   ,   …   ⁢           ,   1.875     )                 =     (       a   0     ,     a   1     ,   …   ⁢           ,     a   15       )               
 
 If d l+2 ≦2d l  or d l ≦2d l+2 , let  
       r   =           ⅆ     l   +   1       ⁢       ⅆ     l   +   2       ⁢     a   l         +       ⅆ   l     ⁢       ⅆ     l   +   2       ⁢     a     l   +   1           +       ⅆ   l     ⁢       ⅆ     l   +   1       ⁢     a     l   +   2                 ⅆ     l   +   1       ⁢       ⅆ     l   +   2       ⁢     +       ⅆ   l     ⁢       ⅆ     l   +   2       ⁢     +       ⅆ   l     ⁢     ⅆ     l   +   1                           
       Otherwise   ,   let       
             ⅆ     l   +   1       ⁢     a   l       +       ⅆ   l     ⁢     a     l   +   1               ⅆ   l     ⁢     a     l   +   1             
 
 Make f←f−(r−1). 
 
 Start sampling the data at sampling points f+i+20, f+i+21, f+i+22 . . . to obtain a sampled sequence w=w 0 , w 1 , w 2 , . . . Apply maximum likelihood decoding to w to obtain an estimate of x. 
   
 
       Example 2.3  
       [0072]     This example describes the same situation as Example 2.2, where 1=7, (a l , a l+1 , a l+2 )=(0.875, 1, 1.125) and (d l , d l+1 , d l+2 )=(0.5, 0.14,1.13). Notice that d l+2 =1.3&gt;2(0.5)=2d l . Thus, according to Algorithm 2.3:  
       r   =             ⅆ     l   +   1       ⁢     a   l       +       ⅆ   l     ⁢     a     l   +   1               ⅆ   l     ⁢     a     l   +   1           =   0.97         
 
 Since the initial (unknown) sampling point was 1.97 and i=2, according to Algorithm 2.3, f is reset according to f←f−(r−1)=1.97−(0.97−1)=2 and sampling starts at points 
        f+i+20, f+i+21, f+i+22 . . . =24,25,26, . . . . 
 
 Thus, perfect bit-byte synchronization occurs in this case. 
       
 
         [0074]      FIG. 6  illustrates a method  650  according to Algorithm 2.3. The method is represented by a flow diagram with the understanding that it would be embodied either as a processor program comprising a series or sequence of commands executed by the synchronizer of  FIG. 152 . Preferably, the method  650  operates on a string . . . 1111, u, x, and is preceded by pre-coding the string as discussed above, which produces the pre-coded data string y. The method begins in step  410  by sampling the string to obtain the sample vectors v 0 , v 1 , v 2 , . . . at the sampling points f, f+1, f+2, . . . before the start of u. An iteration counter i is initialized in step  412 . Then, in step  414  the Euclidian distance d i,j  is taken between a current sample vector v i  and each of eight sample vectors of u. According to the test in step  416 , if the Euclidian distance d i,j  is greater than 2, the method increments i by one and loops back through  414 ; otherwise, the method goes to step  531 . In step  531 , a vector d of sixteen Euclidian distances is calculated with v i  and u j  and the three smallest values of d are selected in step  532 . The sixteen unit vector a is accessed in step  533  and the elements of a at the same vector locations as the three smallest values of d are obtained. In decision  651 , the first and third of the three smallest values of d are compared. If the variance between the two values exceeds a threshold, r is calculated in step  534  by interpolation among the three smallest values of d as in  FIG. 3C . Otherwise, r is calculated in step  652  by interpolation between only the two smallest values of d. The value of r is used to adjust the initial sampling point f in step  653 . With the adjustment, a sampled sequence w is obtained in step  654  from which an estimate of the data string x is derived by maximum likelihood decoding.  
         [0075]     Representative simulation results obtained using Algorithms 2.1, 2.2 and 2.3 are tabulated below. In all cases, white Gaussian noise with a variance of 0.06 was added. A number of tests were run for each algorithm and for each case to measure how far away the results were from perfect bit-synchronization (byte synchronization was correct in all cases). For instance, in Example 2.1 this number is 0.025, in Example 2.2 it is 0.02 and in Example 2.3 it is is 0. The average of all these numbers, the standard deviation, the worst case and the percentage of cases above 0.05 are shown in the following table.  
                                                                                                 Average                       Variance   Number   bit           Percentage       Algor-   of   of   Synch   Standard   Worst   above       ithm   AWGN   Tests   Error   Deviation   Case   0.05                                2.1   0.06   437018   0.03   0.02   0.1     15%       2.2   0.06   100190   0.015   0.01   0.06   0.006%       2.3   0.06   255355   0.01   0.008   0.06   0.001%