Abstract:
The invention relates to a data modulation method applicable to make data streams tend to have desired properties, useful for clock recovery, making signals more distinguishable, or enforcing run-length conditions. A stream of input data and a corresponding stream of output data are grouped into elements of a finite field. Input elements of said input data are modified by a transform generating output elements of the output data, such that a current output element is a linear combination of a current input element and at least one previous output element. A multiplier applied to at least one previous output element is a non-zero and non-unity element of the finite field. A set of initial conditions inherent to the transform, is selected such that the output elements resulting from the transform tend to have the desired property.

Description:
BACKGROUND OF THE INVENTION  
       [0001]     1. Field of Invention  
         [0002]     The present invention relates to modulation of data transfer signals, for instance in reading from, and writing to a magnetic medium, such as a hard disk drive. The invention more specifically relates to modulation intended to make the signal properties meet specific criteria, for instance enforcing run-length limited conditions, making signals more distinguishable (increasing “distance”), and providing clock recovery information.  
         [0003]     2. Relevant Background  
         [0004]      FIG. 1  is a schematic representation of a data transfer chain  8 , such as used in a hard disk drive. A sequence of user data to be written on a hard-disk is input to an Error Correcting Coding (ECC) circuit  10 . An encoder  12 , implementing the desired modulation, receives k-bit blocks of output b from the ECC  10  and produces (k+r)-bit blocks c. The (k+r)-bit blocks c are referred to as codewords. The encoder  12  outputs the codeword c to a 1/(1+D 2 ) filter or precoder  14 . The term “D” designates a one bit delay and “+” designates the bitwise exclusive OR operator. Thus, the i-th bit x i  in a codeword output c by precoder  14  is expressed as 
   x   i   =c   i   +x   i-2 .  
         [0005]     Such an operation needs two initial conditions x −1  and x 0  to be set for x, for instance (0, 0).  
         [0006]     Codeword x passes in a channel  16  through one or more channel filters  18 . The channel, which is where the data is written to the hard-disk and read back from the hard-disk, is typically corrupted by additive noise n, such that the received sequence r is defined by r=z+n, where z is the output of filters  18 .  
         [0007]     Based on the received sequence r, a Viterbi detector  20 , for example, generates a detected sequence xˆ, which is a reproduction of the input x to the channel filters  18 . Next, bits xˆ are filtered by a filter  22  which performs the function (1+D 2 ) that is an inverse of the function performed by precoder  14 , and generates g. The output g of the filter  22  is decoded by a decoder  24  to produce a decoded sequence d, which is a reproduction of the ECC output sequence b. An ECC decoder  26  receives the output sequence d and reestablishes the user input to ECC coder  10 .  
         [0008]     As mentioned above, the codewords used in the system have k+r bits, whereas the corresponding user data blocks have a lower number of bits k, whereby there is an efficiency loss. The efficiency of the encoder is called “rate” and it is defined as k/(k+r).  
         [0009]     Known modulation techniques implemented by the encoder  12  strive to increase the rate and impose desired properties on the codeword. Often this makes each bit of a codeword depend on every bit of the incoming data block. Such techniques have the drawback of increasing “error propagation”—often one corrupted bit in a codeword would cause the loss of most of the bits in the resulting data block.  
         [0010]     US published application 20040059980, incorporated herein by reference, discloses a modulation method for use in encoder  12 , which has short error propagation while imposing desirable properties on the codewords.  
         [0011]     The modulation has the following generic transform:  
       1       f   0     +       f   1     ⁢   D     +       f   2     ⁢     D   2       +       f   3     ⁢     D   3       +   …   +       f   r     ⁢     D   r             
 
         [0012]     where D is a one-bit delay and f=(f 0 , f 1 , f 2  . . . f r ) is a set of constant binary values, with f 0 =f r =1, characterizing the modulation scheme. In other words, given an i-th bit b i  of a user data block, the i-th bit a i  of the resulting codeword a is defined as: 
 
 a   i   =b   i   +f   1   a   i-1   +f   2   a   i-2   + . . . +f   r   a   i-r , 
 
         [0013]     where i varies from 1 to k.  
         [0014]     This operation requires r initial conditions, one for each of bits a 1-r  to a 0 . Since each initial condition is one bit, there are 2 r  possible choices for a set of initial conditions.  
         [0015]     In a first part of the modulation scheme, an intermediate codeword a is calculated as above from b with a set of initial conditions set to zero. Thus:  
           a     1   -   r       =   0     ,     
     ⁢       a     2   -   r       =   0     ,     
     ⁢   ⋯       
           a   0     =   0     ,     
     ⁢       a   1     =     b   1       ,     
     ⁢       a   2     =       b   2     +       f   1     ⁢     a   1           ,     
     ⁢       a   3     =       b   3     +       f   1     ⁢     a   2       +       f   2     ⁢     a   1           ,     
     ⁢   ⋯       
           a   r     =       b   r     +       f   1     ⁢     a     r   -   1         +       f   2     ⁢     a     r   -   2         +   …   +       f     r   -   1       ⁢     a   1           ,     
     ⁢       a     r   +   1       =       b     r   +   1       +       f   1     ⁢     a   r       +       f   2     ⁢     a     r   -   1         +   …   +       f   r     ⁢     a   1               
     ⋯     
           a   k     =       b   k     +       f   1     ⁢     a     k   -   1         +       f   2     ⁢     a     k   -   2         +   …   +       f   r     ⁢     a     k   -   r             ,       
 
         [0016]     In a second part of the modulation scheme, a set of initial conditions is selected for each codeword c to be generated, depending on a predefined map relating the initial conditions to a predefined set of values for the intermediate codeword a. For instance, if a is all 1s, all 01s or all 10s, use “initial conditions No. 1”, otherwise use “initial conditions No. 2”.  
         [0017]     Once the set of initial conditions is selected, rather than recalculating the final codeword c by applying the above transform with the selected initial condition set, the effect t (t 1-r , t 2-r , . . . t 0 , t 1 , t 2 , . . . t k ) of the initial condition set is simply added to the intermediate codeword a, i.e. c=a+t. The effect t is calculated by inserting the selected initial condition set in the above transform, and applying the transform to all variables b set to zero.  
         [0018]     Of course, the zero initial conditions may also be selected, in which case the intermediate codeword a becomes the final codeword c.  
         [0019]     An interesting property of this modulation technique is that these initial conditions may thus be changed from one codeword to the next without requiring the decoder to be reconfigured. This allows real-time setting of the initial conditions for each codeword so that each codeword may be made to have desired properties.  
         [0020]     As an example with r=1 and f 1 =1, there is one initial condition having two possible values: 0 or 1. For a same data block, switching the initial condition between 0 and 1 switches the resulting codeword to its complement. Therefore, it is certain that one choice of the initial condition will yield a majority of 1s in the resulting codeword. If this is a desired property, the map is such that if the 0 initial condition yields more 0s than 1s in the codeword, the 1 initial condition is selected, otherwise the 0 initial condition is selected. Producing a large number of is is often a desired property, because each 1 causes a transition in the signal when it passes through the precoder  14 , which transition helps in recovering clock information at the other end of the channel.  
         [0021]     Since each bit c i  of a codeword c is calculated from r previous bits, corruption of one bit will corrupt r further bits, i.e. the error propagation length is r+1. Therefore, in practical applications, r will be chosen small, often equal to 1 or 2. Choosing r small also increases the rate of the encoder, equal to k/(k+r).  
         [0022]     The above disclosed modulation technique provides satisfactory results for enhancing signal properties obeying linear laws, which is the case in the specifications for hard-disks with “longitudinal recording”, i.e. having magnetic polarization that changes along the tracks of the disk.  
         [0023]     Currently, some hard-disks tend to be of the “perpendicular recording” type, i.e. having magnetic polarization changes perpendicular to the disk. The signal specifications for such disks require the “charge” to tend to zero, and this preferably over small sequences of consecutive bits. The charge is defined as the sum of 1s and 0s written on the disk, where each 1 is summed as +1 and each 0 is summed as −1. In other words, the data recorded on the disk should tend to have as many 1s as 0s.  
         [0024]     The zero charge requirement becomes an additional parameter to be taken into account in the modulation scheme. The known modulation schemes do not offer enough flexibility to address this problem.  
         [0025]     What is needed, therefore, is a signal modulation scheme with enhanced flexibility, that can in particular make the charge tend to zero while satisfying other requirements in the properties of the signal.  
       SUMMARY OF THE INVENTION  
       [0026]     According to the invention, this need is satisfied by a data modulation method comprising the steps of: grouping a stream of input data and a corresponding stream of output data into elements of a finite field; applying to input elements of the input data a transform generating output elements of the output data, such that a current output element is a linear combination of a current input element and at least one previous output element, wherein a multiplier applied to at least one previous output element is a non-zero and non-unity element of the finite field; and selecting a set of initial conditions inherent to the transform, such that the output elements resulting from the transform tend to have a desired property.  
         [0027]     According to an embodiment of the invention, the method comprises the further the steps of: calculating intermediate elements by applying the transform to the input elements with a set of initial conditions of value zero; calculating the effect of the selected set of initial conditions by applying said transform to input elements having value zero and the selected set of initial conditions; and adding the effect to the intermediate elements to obtain the output elements.  
         [0028]     According to an embodiment of the invention, the step of selecting the initial conditions comprises the steps of: defining distinct sets of initial conditions, each set having a single non-zero element at a distinct position; and selecting each non-zero element of the sets of initial conditions such that the output elements tend to have a respective property.  
         [0029]     The invention also provides for a decoder or inverse data modulation method comprising the steps of: grouping a stream of input data and a corresponding stream of output data into elements of a finite field; and applying to the input elements of the input data a transform generating output elements of the output data, such that a current output element is a linear combination of a current input element and at least one previous input element, wherein a multiplier applied to a previous output element is a non-zero and non-unity element of the finite field. 
     
    
     BRIEF DESCRIPTION OF THE DRAWING  
       [0030]     The invention is illustrated in the accompanying drawing, wherein:  
         [0031]      FIG. 1  illustrates a signal processing chain in which the present invention may be implemented.  
         [0032]      FIG. 2  schematically shows a disk drive system in which the signal processing chain of  FIG. 1  may be included. 
     
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS  
       [0033]     In an embodiment of the invention, each user data block B=(b 1 , b 2 , . . . b k ) fed to the encoder  12  of the processing chain of  FIG. 1  is subdivided into p=k/m m-tuples B 1 , B 2 , . . . B p . Each m-tuple B i  is considered as an element of a finite field GF(2 m ). The modulation transform is expressed as:  
       1       α   0     +       α   1     ⁢     D   m       +       α   2     ⁢     D   m   2       +       α   3     ⁢     D   m   3       +   …   +       α   r     ⁢     D   m   r             
 
         [0034]     where D m  is a one m-tuple delay and (α 0 , α 1 , α 2 , . . . α r , are constant elements of GF(2 m ), at least one of which is non-zero and non-unity. In other words, given an i-th m-tuple B i  of a user data block B, the i-th m-tuple A i  of the resulting codeword A is defined as: 
 
 A   i =α 0   B   i +α 1   A   i-1 +α 2   A   i-2 + . . . +α r   A   i-r , 
 
         [0035]     where i varies from 1 to p. Of course, all arithmetic is performed over finite field GF(2 m ).  
         [0036]     Addition in a finite field is a bitwise exclusive OR operation. Multiplication is more complex: the two operands are multiplied under their polynomial representation, and the resulting polynomial, modulo the “generator polynomial” of the finite field, is the final result. Such multiplication introduces pseudo-random properties in the results, which contributes to enhanced flexibility of the modulation scheme according to embodiments of the invention.  
         [0037]     The above transform requires r initial conditions in finite field GF(2 m ) for A 1-r  to A 0 . Since each initial condition is an element of finite field GF(2 m ), there are 2 mr  possible choices for a set of initial conditions.  
         [0038]     In a generic use of the modulation scheme according to embodiments of the invention, a set of constants α=(α 0 , α 1 , α 2 , . . . α r ) is predefined. The corresponding decoder also uses this same set of constants. In operation, a set of initial conditions is found for each codeword being generated in order to make that codeword best match a set of required properties. The choice of the initial conditions does not affect the operation of the decoder, which is one of the interesting features of this type of modulation scheme.  
         [0039]     The error propagation length of this modulation scheme is rm+1 bits, since one corrupted bit will affect r m-tuples.  
         [0040]     In a preferred embodiment, the modulation scheme is used in two parts.  
         [0041]     In a first part, an intermediate codeword A is calculated with the above transform from B with initial conditions set to zero. Thus:  
           A     1   -   r       =   0     ,     
     ⁢       A     2   -   r       =   0     ,     
     ⁢   ⋯       
           A   0     =   0     ,     
     ⁢       A   1     =       α   0     ⁢     B   1         ,     
     ⁢       A   2     =         α   0     ⁢     B   2       +       α   1     ⁢     A   1           ,     
     ⁢       A   3     =         α   0     ⁢     B   3       +       α   1     ⁢     A   2       +       α   2     ⁢     A   1           ,     
     ⁢   ⋯       
           A   r     =         α   0     ⁢     B   r       +       α   1     ⁢     A     r   -   1         +       α   2     ⁢     A     r   -   2         +   …   +       α     r   -   1       ⁢     A   1           ,     
     ⁢       A     r   +   1       =         α   0     ⁢     B     r   +   1         +       α   1     ⁢     A   r       +       α   2     ⁢     A     r   -   1         +   …   +       α   r     ⁢     A   1               
     …     
         A   p     =         α   0     ⁢     B   p       +       α   1     ⁢     A     p   -   1         +       α   2     ⁢     A     p   -   2         +   …   +       α   r     ⁢       A     p   -   r       .             
 
         [0042]     In a second part of the modulation scheme, a map M is defined that relates specific initial condition sets to specific criteria satisfied by the intermediate codeword A. Once the set of initial conditions is selected, rather than recalculating the final codeword C by applying the above transform with the selected initial condition set, the effect T (T 1-r , T 2-r , . . . T 0 , T 1 , T 2 , . . . T p ) of the initial condition set is simply added to the intermediate codeword A, i.e. C=A+T. This is possible, because the transform is linear. The effect T is calculated by inserting the selected initial condition set in the above transform, and applying the transform with input B set to zero.  
         [0043]     The modulation scheme may be noted ENC(α, M)(X), where α represents the set of constants (α 0 , α 1 , α 2 , . . . α r ) used in the transform, X is the set of p m-tuples to which the transform is applied, and M designates the map that defines initial conditions used in calculating the current codeword. The result of ENC(α, M)(X) is a set of k+rm bits, or r+p m-tuples or elements of GF(2 m ).  
         [0044]     In one embodiment of the invention, instead of exploring all possible initial conditions, only r+1 predefined initial condition sets are used. Map M is thus characterized by r+1 submaps M 0 , M 1 , . . . Mr, each associated to a respective one of the r+1 predefined initial condition sets. M 0  is associated to initial conditions set to zero, and each of maps Mi, i&gt;0, is associated to an initial condition set where all elements are zero, except the i-th, which is equal to unity, i.e. (0, 0, . . . 0, 1, 0, . . . 0), where 1 is at the i-th position.  
         [0045]     Thus, the transform, applied to a user data block B will be expressed as:  
                 ENC   ⁡     (       α   _     ,   M     )       ⁢     (     B   _     )       =       ⁢         ENC   ⁡     (       α   _     ,   M0     )       ⁢     (     B   _     )       +                     ⁢         β   1     ⁢     ENC   ⁡     (       α   _     ,   M1     )       ⁢     (     0   _     )       +                     ⁢         β   2     ⁢     ENC   ⁡     (       α   _     ,   M2     )       ⁢     (     0   _     )       +                     ⁢   ⋯                   ⁢       β   r     ⁢     ENC   ⁡     (       α   _     ,   Mr     )       ⁢     (     0   _     )                 
 
         [0046]     ENC(α, MO)(B) designates the intermediate codeword A, and all of the other terms represent the effect T of the initial conditions, wherein β=(β 1 , β 2 , . . . β r ) designates a set of scaling factors in GF(2 m ) that will generally change for each codeword A. In fact, map M is such that β=M(X), whatever the value of X. The scaling factors β could form part of their respective submaps, but the above notation allows to better visualize which parameters are adjustable and causes submaps M 0 , M 1 , . . . Mr to be constant.  
         [0047]     The inverse transform, i.e. the decoding operation performed by decoder  24 , can be designated DEC(α)(Y). As previously mentioned, the map M does not intervene in the decoding operation. The decoder is such that: 
 
 B   i =α 0   −1 ( C   i +α 1   C   i-1   +α   2   C   i-2   + . . . α   r   C   i-r ), 
 
         [0048]     where B i  is an m-tuple output by the decoder and C i  is an m-tuple currently input to the decoder.  
         [0049]     The modulation scheme will be better understood through various examples illustrated below.  
       EXAMPLE 1  
       [0050]     1. p=14  
         [0051]     2. r=1  
         [0052]     3. m=4  
         [0053]     4. (α 0 , α 1 )=(1,μ), where μ is a non-zero and non-unity element of GF(2 4 )  
         [0054]     5. Map M 1  specifies the use of the unity over GF(2 4 ) as initial condition  
         [0055]     6. β 1  is chosen such that it does not belong to S={0, A 1 μ −1 , A 2 μ −2 , . . . A 14 μ −14 } (reason explained later). This is always possible, since β 1  has 16 possible distinct values, whereas S only has 15 elements.  
         [0056]     In this example, intermediate codeword A=ENC(α, M 0 )(B) is expressed as:  
           A   0     =   0     ,     
     ⁢       A   1     =     B   1       ,     
     ⁢       A   2     =       B   2     +     μ   ⁢           ⁢     B   1           ,     
     ⁢       A   3     =       B   3     +     μ   ⁢           ⁢     B   2       +       μ   2     ⁢     B   1           ,     
     ⁢   ⋯       
         A   14     =       B   14     +     μ   ⁢           ⁢     B   13       +     …   ⁢           ⁢     μ   13     ⁢     B   1             
 
         [0057]     The additive effect T of the initial conditions is β 1 ENC(α, M 1 )(0)=β 1 (1, μ, μ 2 , μ 3 , . . . μ 14 ). β 1  is chosen such that T+A has all 4-tuples non-zero, i.e. β 1 ≠0, μβ 1 ≠A 1 , μ 2 β 1 ≠A 2 , . . . μ 14 β 1 ≠A 14 . Hence the choice defined above in item  6 .  
         [0058]     With this choice, each 4-tuple of the final codeword C contains at least one bit at 1, which ensures that there is at least one transition in the signal every 4 bits at the output of precoder  14 . This property promotes clock recovery.  
         [0059]     The search for the desired value of PI requires at most 14 trials out of the 15 non-zero possible values. Each trial requires a comparison with each of the 14 last values of set S. If the 14 th  trial is unsuccessfuil, it is certain that the value searched for is the 15 th  non-zero value.  
         [0060]     The decoder in this example is such that: 
 
 B   i   =C   i   +μC   i-1 , 
 
         [0061]     where B i  is an m-tuple output by the decoder and C i  is an m-tuple currently input to the decoder.  
       EXAMPLE 2  
       [0062]     1. p=6  
         [0063]     2. r=1  
         [0064]     3. m=2  
         [0065]     4. (α 00 , α 1 )=(1, μ), where μ is a non-zero and non-unity element of GF(2 2 )  
         [0066]     5. Map M 1  specifies the use of unity as initial condition. Let Q=ENC(α, M 1 )(0)=(1, μ, μ 2 , . . . μ 6 )  
         [0067]     6. β 1  is chosen such that C=A+T=A+β 1 Q has the least charge. The charge of C is defined as 2[(−1) c     -1   +(−1) c     0   +(−1) c + . . . (−1) c     12   ], where c -1 , c 0 , c 1 , . . . c 12  are the successive bits of codeword C. (This amounts to adding +1 for each bit at 1 and −1 for each bit at 0, and multiplying the final result by 2.)  
         [0068]     The search for the required value of β 1  is particularly simple in this example, since there are only four values to try.  
         [0069]     This exemplary modulation does not require a precoder  14  (nor the inverse precoder  22 ), since the codewords are short (12 bits) and the modulation inherently inserts transitions. Indeed, transitions are necessary to make the charge tend to zero.  
         [0070]     In using this example in a simulation on random input data, the variance of the charge is about 1.74 over a significant number of consecutive codewords. This result is satisfactory for dealing with perpendicular recording hard-disks.  
         [0071]     The decoder in this example is also such that: 
 
 B   i   =C   i   +μC   i-1 , 
 
         [0072]     where B i  is an m-tuple output by the decoder and C i  is an m-tuple currently input to the decoder The efficiency of the modulation in reducing charge may be increased by increasing m and k, whereby there will be more values to try for β 1 .  
         [0073]     If several values of β 1  happen to reduce the charge, then preferably the one causing most transitions in codeword C is selected, whereby clock-recovery is also promoted. Alternatively, if a precoder  14  is present, the value causing C to have most 1s is selected instead.  
         [0074]     If multiple properties are to be satisfied by the codewords, r may be chosen equal to the number of properties, whereby there will be as many factors β to search for as desired properties. Factors β will not be independent and it may be necessary to optimize them through several iterations, i.e. if an optimal first factor is found for a first property, a subsequently found optimal second factor for a second property may affect the optimality of the first factor, whereby the first factor is searched for again, which may in turn affect the optimality of the second factor. This may continue until a compromise is found for both factors.  
         [0075]      FIG. 2  illustrates in simplified form a disk drive system  100  in which the present invention may be embodied. Disk drive system  100  includes a system processor  113  that processes requests and commands from a host computer  101  that direct the drive system to perform specific behavior involving disk drive assembly  107 . Examples include reading and writing data to disk drive assembly  107  through a read/write subsystem  105 , providing state information such as defect tables, error status and the like. Disk controller unit  103  includes data processing capacity as well as memory in the form of ROM or RAM  112  and buffer memory  104  to generate responses to received commands and requests. The generated responses return data, state information and/or error codes depending on the particular operation being performed.  
         [0076]     Disk drive assembly  107 , e.g., an HDD system, implements physical mass storage typically on a plurality of magnetic disks and read/write head electronics for transferring data with the disks. Disk drive assembly  107  typically includes read channel hardware for preprocessing and amplifying data read from the magnetic media as well as a spin motor for spinning the disks and voice coil motor (VCM) for positioning the read/write head electronics at specific locations with respect to the disk surface(s).  
         [0077]     A servo control  108  generates drive signals that control the VCM and/or spin motors. These drive signals are in the form of precision voltage or current signals that drive the motors directly.  
         [0078]     Host  101  typically comprises a data processing device such as a personal computer, server, workstation or the like that requires access to bulk data storage capabilities of disk drive assembly  107 . Host  101  sends write commands and data via controller  103  to write data onto the disks as well as read commands to retrieve previously written data from disks within disk drive assembly  107 . On both read and write operations the data transmitted from the host  101  to the disk controller  103  includes an indication of a specific location or set of locations on the disk drive assembly that contains the data that is to be accessed.  
         [0079]     The data that is exchanged through disk controller  103  is typically buffered in buffer memory  104  that is accessible via memory controller  109  and subsequently transmitted to disk assembly  107  or host  101 . Buffer memory  104  is used to overcome differences between the speed at which host  101  operates as compared to the speed at which disk assembly  107  operates. In place of or in addition to buffer memory  104 , a cache memory may be implemented by appropriate changes (e.g., tag management, hit/miss detection and the like) to memory controller  109 .  
         [0080]     The present invention may be implemented in hardware within the read/write subsystem  105 , in software executed within the system processor  113 , or in a combined hardware and software mode in processor  113  and subsystem  105 .  
         [0081]     Although the invention has been described and illustrated with a certain degree of particularity, it is understood that the present disclosure has been made only by way of example, and that numerous changes in the combination and arrangement of parts can be resorted to by those skilled in the art without departing from the spirit and scope of the invention, as hereinafter claimed.