Data coding for data storage systems

The present invention generally relates to data coding for data storage systems and particularly relates to data encoding and decoding methods and apparatus for data storage systems.

There is an increasing demand at least in the field of magnetic recording and optical recording systems for inner codes that constrain channel input sequences so that they have certain desired properties for timing recovery, gain control, and, in some applications, for limiting path memory requirements of Viterbi detectors. For example, conventional peak detection systems typically employ run length limited (RLL) (d,k) constrained codes. These codes are normally found in optical recording systems and in relatively low linear-density magnetic recording systems. At moderate linear densities, the introduction of Partial Response Maximum Likelihood (PRML) detection to hard disk drive data storage devices involved the use of a different class of constrained codes known as (G,I) codes. As demonstrated by J. Moon and B. Brickner, “Maximum transition run codes for data storage systems,” IEEE Trans. Magn., vol. 32, pp. 3992-3994, September 1996 and R. D. Cideciyan, E. Eleftheriou, B. Marcus, and D. Modha “Maximum Transition Run Codes for Generalized Partial-Response Channels” IEEE J. Select. Areas Commun ., 19(4), pp. 619-634, April 2001, maximum transition run (MTR) (j,k) codes have been introduced to provide run length limited properties and to enhance the detector performance. A 16/17 code combining an 8 bit unconstrained code with a nine bit (G,I) constrained byte is described in both J. Sonntag, “Apparatus and method for increasing density of run length limited block codes without increasing error propagation,” U.S. Pat. No. 5,604,497 and Coker, above. A 1/(1+D 2 ) precoder is also employed in Sonntag, above, and J. Coker, D. Flynn, R. Galbraith, T. Truax, “Method and apparatus for implementing a set rate code for data channels with alternate 9-bit code words and 8-bit code words,” U.S. Pat. No. 5,784,010. High rate codes produced by interspersing MTR code words with uncoded source symbols are described in A. Wijngaarden, E. Soljanin, “A combinatorial technique for constructing high-rate MTR-RLL codes,” IEEE J. Select. Areas Commun ., 19(4), pp. 582-588, April 2001. A 1(1+D) precoder is employed in A. Wijngaarden, above. All of the aforementioned codes are designed on the basis of a precoder being present at the output of the constrained code encoder. At the receiver side, the precoder operation is undone by an inverse precoder circuit. However, the inverse precoder causes error propagation that adversely affects the performance. For example, the inverse precoder can cause an increase in sector error rate of the outer Reed-Solomon (RS) code. In applications such as magnetic recording, the code rate is subject to a stringent requirement.

In accordance with the present invention, there is now provided a modulation encoder having a finite state machine for converting input bits into output bits in which the number of alternating output bits is limited to j+1 where j is a predefined maximum number of transitions in the output bits, and in which the number of like output bits is limited to k+1 where k is a predefined maximum number of non-transitions in the output bits.

Viewing the present invention from a different aspect, there is now provided, a modulation encoder having a finite state machine for converting input bits into output bits in which the number of like output bits is at least d+1 and at most k+1 where d is a predefined minimum number of non-transitions in the output bits and k is a predefined maximum number of non-transitions in the output bits.

In a preferred embodiment of the present invention, there is provided encoding apparatus for converting an input bit stream into an output bit stream, the apparatus comprising: partitioning logic for partitioning the input bit stream into a first group of bits and a second group of bits; at least one modulation encoder of one of the forms herein before described connected to the partitioning logic for converting the first group of bits into coded output bits; and, combining logic connected to the or each modulation encoder and the partitioning logic for combining the coded output bits and the second group of bits to generate the output bit stream. The encoding apparatus may comprise a plurality of modulation encoders as herein before described each for converting a different subgroup of the first group of bits into coded output bits, wherein the different subgroups of the first group of bits are interleaved with different subgroups of the second group of bits. The apparatus may additionally or alternatively comprise a parity generator connected to the or each modulation encoder and the partitioning logic for generating a parity code in dependence on the second group of bits and the coded output bits. The combining logic preferably comprises a parallel to serial convertor connected to the or each modulation encoder and the partitioning logic.

Viewing the present invention from another aspect, there is now provided a modulation decoder having a sliding block decoder logic for recovering output bits from input bits in which the number of alternating input bits is limited to j+1 where j is a predefined maximum number of transitions in the input bits, and in which the number of like input bits is limited to k+1 where k is a predefined maximum number of non-transitions in the input bits.

Viewing the present invention from yet another aspect, there is now provided a modulation decoder having sliding block decoder logic for recovering output bits from input bits in which the number of like input bits is at least d+1 and at most k+1 where d is a predefined minimum number of non-transitions in the input bits and k is a predefined maximum number of non-transitions in the input bits.

In another preferred embodiment of the present invention, there is provided decoding apparatus for decoding an input bit stream into an output bit stream, the apparatus comprising: partitioning logic for partitioning the input stream into a first group of bits and a second group of bits; at least one modulation decoder of one of the forms herein before described connected to the partitioning logic for decoding the first group of bits into decoded output bits; and, combining logic connected to the or each modulation decoder and the partitioning logic for combining the second group of bits and the decoded output bits. Such apparatus may comprise a plurality of modulation decoders as herein before described each for converting a different subgroup of the first group of bits into decoded output bits, wherein the different subgroups of the first group of bits are interleaved with different subgroups of the second group of bits. The partitioning logic of the decoding apparatus may comprise a serial to parallel convertor connected to the or each modulation decoder.

It will be appreciated that the present invention extends to a signal processing device comprising encoding apparatus and decoding apparatus as herein before described. Similarly, it will be appreciated that the present invention extends to a data storage device comprising a data storage channel, together with encoding apparatus and encoding apparatus as herein before described.

Viewing the present invention from yet another aspect, there is provided a bit encoding method comprising, via a finite state machine, converting input bits into output bits in which the number of alternating output bits is limited to j+1 where j is a predefined maximum number of transitions in the output bits, and in which the number of like output bits is limited to k+1 where k is a predefined maximum number of non-transitions in the output bits.

In accordance with the present invention, there is also provided a bit encoding method comprising, via a finite state machine, converting input bits into output bits in which the number of like output bits is at least d+1 and at most k+1 where d is a predefined minimum number of non-transitions in the output bits and k is a predefined maximum number of non-transitions in the output bits.

In yet another preferred embodiment of the present invention, there is provided a data encoding method for converting an input bit stream into an output bit stream, the method comprising: partitioning the input bit stream into a first group of bits and a second group of bits; converting the first group of bits into coded output bits according to one of the bit encoding methods herein before described; and, combining the coded output bits and the second group of bits to generate the output bit stream.

Viewing the present invention from a further aspect, there is now provided a bit decoding method comprising, via sliding block decoder logic, recovering output bits from input bits in which the number of alternating input bits is limited to j+1 where j is a predefined maximum number of transitions in the input bits, and in which the number of like input bits is limited to k+1 where k is a predefined maximum number of non-transitions in the input bits.

In accordance with the present invention, there is further provided a bit decoding method comprising, via sliding block decoder logic, recovering output bits from input bits in which the number of like input bits is at least d+1 and at most k+1 where d is a predefined minimum number of non-transitions in the input bits and k is a predefined maximum number of non-transitions in the input bits.

In a further preferred embodiment of the present invention, there is now provided a data decoding method for decoding an input bit stream into an output bit stream, the method comprising: partitioning logic for partitioning the input bit stream into a first group of bits and a second group of bits; decoding the first group of bits into decoded output bits via one of the bit decoding methods herein before described; and, combining the second group of bits and the decoded output bits.

In a preferred embodiment of the present invention to be described in detail shortly, byte-oriented (m-bit bytes) precoderless constrained codes are provided. In a particularly preferred embodiment of the present invention, these codes are conveniently combined with multiparity block codes to provide a further enhancement of system performance. In an especially preferred embodiment of the present invention, a very high rate precoderless inner code is provided by concatenating unconstrained bits with constrained n-bit bytes. The constrained n-bit bytes are obtained by encoding unconstrained m-bit bytes (n>m). In applications using outer RS codes, the m-bit bytes can be matched to the symbol size of the RS code to minimize error propagation. Preferred embodiments of the present invention include: apparatus and methods for providing rate 96/102 codes with two 8/9 (G,I) constrained bytes and four parity bits; apparatus and methods for providing rate 96/100 codes with two 8/9 MTR (j=1,2,3)) constrained bytes and 2 parity bits; apparatus and methods for providing rate 96/102 codes with three 8/9 MTR (j=1,2,3)) constrained bytes and 3 parity bits; and, apparatus and methods for providing rate 96/102 codes with two 8/9 MTR (j=2,3)) constrained bytes and 4 parity bits.

Preferred embodiments of the present invention are illustrated in the Figures appended hereto which:

FIG. 1 is a block diagram of data storage system;

FIG. 2 is a block diagram of a conventional data storage system;

FIG. 3 is a block diagram of a data storage system embodying the present invention;

FIG. 4 is a block diagram, in the form of a finite-state machine, of an encoder for a rate-8/9 MTR (j=1,2,3) code;

FIG. 5 is a block diagram of a rate-96/100 MTR (j=1,2,3)/unconstrained dual-parity encoder;

FIG. 6 is a block diagram of a rate-96/100 MTR (j=1,2,3)/unconstrained dual-parity decoder;

FIG. 7 is a block diagram of a rate-96/102 MTR (j=1,2,3)/unconstrained triple-parity encoder;

FIG. 8 is a block diagram of a rate-96/102 MTR (j=1,2,3)/unconstrained triple-parity decoder;

FIG. 9 is a block diagram of a rate-96/102 MTR (j=2,3)/unconstrained quadruple-parity encoder;

FIG. 10 is a block diagram of a rate-96/102 MTR (j=2,3)/unconstrained quadruple-parity decoder;

FIG. 11 is a block diagram of a rate-96/102 (G=4, I=6)/unconstrained quadruple-parity encoder; and,

FIG. 12 is a block diagram of a rate-96/102 (G=4, I=6)/unconstrained quadruple-parity decoder.

Referring first to FIG. 1, a data storage system comprises an encoder subsystem 1 for encoding write data to be written onto a storage medium 4 of a recording channel 3 and a decoder subsystem 2 for decoding signal detected from the recording channel 3 to produce read data. The storage medium 4 may be in the form of a magnetic disk, optical disk, or the like. The encoder subsystem 1 and decoder subsystem 2 may be integrated into a single application specific integrated circuit.

With reference to FIG. 2, in a conventional data storage system, the encoder subsystem 1 comprises a Reed Solomon (RS) encoder 11 , a modulation encoder 12 , and a precoder 13 . Similarly, the decoder subsystem 2 comprises a detector 14 , an inverse precoder 15 , a channel decoder 16 , and an RS decoder 17 . In operation, the RS encoder 11 converts an incoming user bit stream into a sequence of symbols such as 8 bit bytes. The channel encoder 12 is based on a logic state machine. In use, the modulation encoder 12 converts incoming bits into output encoded bits according to a transition-based translation. The precoder 13 converts the transitions in the output of the modulation encoder 12 into levels suitable for recording in the recording channel 3 . In the decoder subsystem 2 , the detector 14 recovers the levels from the recording channel 3 . The inverse precoder 15 converts the levels back into logic transitions. The logic transitions are then decoded by the modulation decoder 16 to provide the symbols. The symbols are converted into an output user bit stream by the RS decoder 17 .

As indicated in [2], the following three classes of modulation codes are conventionally employed in optical and magnetic recording:

1) (d,k) codes in association with 1/(1⊕D) precoders;

2) (G,I) codes in association with 1/(1⊕D 2 ) precoders; and,

3) MTR (j,k) codes in association with 1/(1⊕D) precoders.

In conventional coding systems, these codes, when combined with an appropriate precoder, impose constraints on binary channel input sequences. Specifically, after precoding, the d-constraint limits the minimum length of like binary symbols at the channel input to d+1. Similarly, after preceding, the k-constraint limits the maximum length of like binary symbols at the channel input to k+1. Likewise, after preceding, the G-constraint limits the maximum length of like and alternating binary symbols at the channel input to G+2. In addition, after precoding, the I-constraint limits the maximum length of like binary symbols in the odd and even interleave of channel input sequences to I+1. In a similar fashion, after preceding, the j-constraint limits the maximum length of alternating binary symbols at the channel input to j+1.

Referring now to FIG. 3, in a preferred embodiment of the present invention, the encoder subsystem 1 comprises a modulation encoder 18 having a finite state machine adapted to convert the incoming RS encoded symbols into output levels according to a level based translation. The need for a precoder is thus eliminated. Similarly, in the decoder subsystem 2 , the need for an inverse precoder is eliminated by a channel decoder 19 comprising sliding block decoder logic adapted to convert outputs into the symbols via a level based translation.

The codes described herein in the interests of exemplifying the present invention avoid the use of any preceding operation. Therefore, there is no need to use a precoder in the encoder subsystem 1 . Similarly, there is no need to use an inverse precoder in the decoder subsystem 2 . The absence of an inverse precoder in particular is desirable in the interests of reducing error propagation, thereby leading to, for example, improved soft error rates at the input of the RS decoder 17 .

Particularly preferred embodiments of the invention include: encoders and decoders for a rate-96/100 MTR (j=1,2,3)/uncoded dual-parity code; encoders and decoders for a rate-96/102 MTR (j=1,2,3)/uncoded triple-parity code; and, encoders and decoders for a rate-96/102 MTR (j=2,3)/uncoded quadruple-parity code. Each of these codes are based on rate-8/9 precoderless MTR mother codes. Preferred embodiments of the present invention based on a rate-8/9 MTR (j=1,2,3) mother code and a rate-8/9 MTR (j=2,3) mother code are described and corresponding code tables are provided. In addition, examples of an encoder and a decoder of a precoderless rate-96/102 (G=4, I=6)/uncoded quadruple-parity code are described.

The rate-8/9 MTR (j=1,2,3) code is specified in Table 1 appended hereto. This code imposes the following time-varying constraints on maximum length of transition runs:

1) j=1 at the end of the second bit

2) j=2 at the end of the third bit

3) j=3 at the end of the fourth bit

4) j=2 at the end of the fifth bit

5) j=3 at the end of the sixth bit

6) j=2 at the end of the seventh bit

7) j=3 at the end of the eighth bit

8) j=2 at the end of the ninth bit

This code also satisfies the k=12 constraint and the t c =7 twins constraint referred to in [2].

The rate-8/9 MTR (j=2,3) code is specified in Table 2 appended hereto. This code imposes the following slightly weaker time-varying constraints on maximum length of transition runs:

1) j=2 at the end of the third bit

2) j=3 at the end of the fourth bit

3) j=2 at the end of the fifth bit

4) j=3 at the end of the sixth bit

5) j=2 at the end of the seventh bit

6) j=3 at the end of the eighth bit

7) j=2 at the end of the ninth bit

This code also satisfies the k=9 constraint and the t u =6 twins constraint referred to in [2].

Referring to FIG. 4, depicted therein is a representation of an example of a finite state machine of a modulation encoder 18 embodying the present invention for the rate-8/9 MTR (j=1,2,3) code. State A corresponds to the case in which the last bit of the preceding code word is “0”. In other words, all the 9-bit code words that arrive in state A end with a “0”. In fact, the last bit of all code words in lists A 1 , A 2 and B is “0”, where in general the set notation X implies that all the code words in X can be obtained by bit inversion of all the code words in X. Similarly, state B corresponds to the case in which the last bit of the preceding code word is “1”. In other words, all the 9-bit code words that arrive in state B end with a “1”. In fact, the last bit of all code words in the lists A 1 , A 2 and B is “1”. The code word lists A 1 , A 2 are selected such that the time-varying j-constraint, the k=12 constraint, and the t c =7 path memory constraint for j-constrained Viterbi detectors [2] are satisfied.

Examples of a rate-96/100 MTR (j=1,2,3)/unconstrained dual parity encoder and a counterpart decoder will now be described with reference to FIGS. 5 and 6.

In the following, x k , 1≦k≦m, denotes the k-th bit in the array x[1:m] where x 1 is the least recent bit and x m is the most recent bit.

Referring to FIG. 5, the rate-96/100 encoder comprises a parallel to serial (P/S) convertor 10 . A parity inserter 20 is connected for input to the P/S convertor 10 . A first rate-8/9 MTR 2-state encoder 30 and a second rate-8/9 MTR 2-state encoder 40 are also connected for input to the P/S convertor 10 . The input of the encoder, a[1:96], consists of 12 bytes. Each of the rate-8/9 MTR encoders 30 and 40 maps eight bits into nine bits according to Tables 1a, 1b, 1c and 1d appended hereto. As indicated in Table 1, this mapping depends on the value of the previous bit p. For example, p=a 8 and p=a 56 are the previous bits for MTR encoders 30 and 40 , respectively. The output after rate-8/9 MTR block encoding is denoted by b[1:100] and consists of two 9-bit MTR code words satisfying a j=1,2,3 constraint interspersed with 10 unconstrained bytes. The parity inserter 20 generates parity bits b 99 and b 100 based on the following parity equations at the channel input. ⊕ 49 i = 0  b 1 + 2  i = 0 , and     ⊕ 49 i = 0  b 2 + 2  i = 0.

Note that in this coding scheme there is no precoding and inverse preceding. Thus, the output of the P/S convertor 10 can be fed directly to a write precompensation circuit.

Referring now to FIG. 6, the rate-96/100 decoder comprises a serial to parallel (S/P) convertor 50 . A first rate-8/9 MTR block decoder 60 and a second rate-8/9 MTR block decoder 70 are connected to receive outputs from the S/P convertor 50 . The output from the S/P convertor 50 is denoted by c[1:100]. Note that the two parity bits c[99:100] are dropped. Each of the rate-8/9 MTR block decoders 60 and 70 performs the inverse mapping in accordance with Table 1. Note that a 9-bit legal code word can never occur simultaneously in two different rows of Table 1. Decoding is therefore unambiguous.

Examples of a rate-96/102 MTR (j=1,2,3)/Unconstrained Triple-Parity Encoder and a counterpart decoder will now be described with reference to FIGS. 7 and 8.

Referring to FIG. 7, the rate-96/102 triple-parity encoder comprises a P/S convertor 80 . A parity inserter 90 is connected for input to the P/S convertor 80 . A first rate-8/9 MTR 2-state encoder 100 , a second rate-8/9 MTR 2-state encoder 110 , and a third rate-8/9 MTR 2-state encoder 120 are also connected for input to the P/S convertor 80 . Again, each of the rate-8/9 MTR encoders 100 , 110 , and 120 maps eight bits into nine bits according to Tables 1a, 1b, 1c and 1d. As indicated in Table 1, this mapping depends on the value of the previous bit p. For example, p=a 8 , p=a 40 and p=a 72 are the previous bits for the MTR encoders 100 , 110 , and 120 , respectively. The parity inserter 90 generates parity bits b 100 b 101 and b 102 based on the following parity equations at the channel input. ⊕ 33 i = 0  b 1 + 3  i = 0 , ( 1 ) ⊕ 33 i = 0  b 2 + 3  i = 0 , ( 2 ) ⊕ 33 i = 0  b 3 + 3  i = 0. ( 3 )

For a polynomial code with generator polynomial g(x)=1+g 1 x+g 2 x 2 +x 3 , the parity bits b 100 b 101 and b 102 can be determined according to the equation. b 100  x 2 + b 101  x 1 + b 102 = ( ⊕ 99 i = 1  b i  x 102 - i )     mod     g  ( x )

Based on this formulation the parity bits generated according to the equations (1)-(3) can also be obtained using the generator polynomial 1+x 3 . In principle, the generator polynomial is selected such that the polynomial code detects all error events from a specified list. In general, the parity bits can be selected according to any linear code specified by a parity check matrix. Note that in this coding scheme there is no preceding and inverse preceding. The output of the P/S convertor 80 can be fed directly to a write precompensation circuit.

Referring to FIG. 8, the rate-96/102 decoder comprises an S/P convertor 130 . A first rate-8/9 MTR block decoder 140 , a second rate-8/9 MTR block decoder 150 , and a third rate-8/9 MTR block decoder 160 are connected to receive outputs from the S/P convertor 130 . The output from the S/P convertor 130 is denoted by c[1:102]. Note that the three parity bits c[99:100] are dropped. Each of the rate-8/9 MTR block decoders 140 , 150 , and 160 performs the inverse mapping in accordance with Table 1. Note that a 9-bit legal code word can never occur simultaneously in two different rows of Table 1. Thus, decoding is unambiguous.

Examples of a Rate-96/102 MTR (j=2,3)/Unconstrained Quadruple-Parity encoder and corresponding decoder will now be described with reference to FIGS. 9 and 10 respectively.

Referring to FIG. 9, the rate-96/102 quadruple-parity encoder comprises a P/S convertor 170 . A parity inserter 180 is connected for input to the P/S convertor 170 . A first rate-8/9 MTR 2-state encoder 190 and a second rate-8/9 MTR 2-state encoder 200 are also connected for input to the P/S convertor 170 . Each of the rate-8/9 MTR encoders 190 and 200 maps eight bits into nine bits according to Tables 2a, 2b, 2c and 2d. As indicated in Table 2, this mapping depends on the value of the previous bit p. For example, p=a 8 and p=a 56 are the previous bits for the MTR encoders 190 and 200 , respectively. The parity inserter computes parity bits b 99 , b 100 , b 101 and b 102 according to the following equation b 99  x 3 + b 100  x 2 + b 101  x 1 + b 102 = ( ⊕ 98 i = 1  b i  x 102 - i )     mod     g  ( x )     where     g  ( x ) = 1 + g 1  x + g 2  x 2 + g 3  x 3 + x 4 .

In principle, the generator polynomial is selected such that the polynomial code detects all error events from a specified list. In general, the parity bits can be selected according to any linear code specified by a parity check matrix. Note that in this coding scheme there is no precoding and inverse precoding. The output of the P/S convertor 170 can be fed directly to the write precompensation circuit.

With reference to FIG. 10, the rate-96/102 decoder comprises an S/P convertor 210 . A first rate-8/9 MTR block decoder 220 and a second rate-8/9 MTR block decoder 230 are connected to receive outputs from the S/P convertor 210 . The output from the S/P convertor 210 is denoted by c[1:102]. Note that the four parity bits c[99:102] are dropped. Each of the rate-8/9 MTR block decoders 220 and 230 performs the inverse mapping in accordance with Table 2.

Note that a 9-bit legal code word can never occur simultaneously in two different rows of Table 2. Thus, decoding is unambiguous.

Examples of a Rate-96/102 (G=4, I=6)/Unconstrained Quadruple-Parity encoder and corresponding decoder will now be described with reference to FIGS. 11 and 12 respectively.

Referring to FIG. 11, the rate-96/102 quadruple-parity encoder comprises a P/S convertor 240 . A parity inserter 250 is connected for input to the P/S convertor 240 . A first rate-8/9 (G,I) block encoder 260 and a second rate-8/9 (G,I) block encoder 270 are also connected for input to the P/S convertor 240 . Each of the rate-8/9 block or stateless encoders 260 and 270 maps eight bits into nine bits according to Tables 3a, 3b, 3c and 3d. The parity inserter 250 computes parity bits b 99 , b 100 , b 101 and b 102 according to the following equation b 99  x 3 + b 100  x 2 + b 101  x 1 + b 102 = ( ⊕ 98 i = 1  b i  x 102 - i )     mod     g  ( x )

where g(x)=1+g 1 x+g 2 x 2 +g 3 x 3 +x 4 . In principle, the generator polynomial is selected such that the polynomial code detects all error events from a specified list. In general, the parity bits can be selected according to any linear code specified by a parity check matrix. Note that in this coding scheme there is no preceding and inverse preceding. The output of the P/S convertor 240 can be fed directly to a write precompensation circuit.

With reference to FIG. 12, the corresponding rate-96/102 decoder comprises an S/P convertor 280 . A first rate-8/9 (G,I) block decoder 290 and a second rate-8/9 (G,I) block decoder 300 are connected to receive outputs from the S/P convertor 280 . The output from the S/P convertor 280 is denoted by c[1:102]. Note that the four parity bits c[99:102] are dropped. Each of the rate-8/9 block decoders 290 and 300 performs the inverse mapping in accordance with Table 3.

While the invention has been described with respect to certain preferred embodiments and exemplifications, it is not intended to limit the scope of the claims thereby, but solely by the claims appended hereto.