IEEE TRANSACTIONS ON MAGNETICS, VOL. 33, NO. 5, SEPTEMBER 1997
`
`2149
`
`Design of a Rate 6/7 Maximum Transition Run Code
`
`Barrett Brickner and Jaekyun Moon
`Department of Electrical Engineering, University of Minnesota, Minneapolis, MN 55455
`
`transition run (MTR) codes provide
`Abstract-Maximum
`significant minimum distance gains when used with sequence
`detectors operating at high linear densities. A method for
`reducing the RLL k constraint associated with MTR block codes
`is presented. A block decodable, rate 4/5 MTR code with k=4
`illustrates the technique. This reduction of k is combined with
`sliding-block decoding to develop a 97.8% efficient rate 6/7
`MTR code with k=8.
`
`inserting ones at the boundary. The key is to use codewords with a
`pair of ones at the boundary when the adjacent codeword has a zero
`next to the pair of ones. Because these words are not allowed by the
`block encoder, they can be decoded unambiguously.
`To illustrate, this method is applied to the rate 4/5MTR(2;8)
`block code described by the mapping in Table I. If the encoder state
`z is defined as the trailing bit of the previous codeword, then the
`following conditional mappings can be employed:
`
`I. INTRODUCTION
`
`ODULATION codes are used to eliminate troublesome
`
`and
`
`M patterns or to introduce certain desirable characteristics in the
`
`recorded sequences [l]. An important case of the former is
`suppression of minimum distance error events, which dominate the
`performance of sequence detectors. At low densities, the minimum
`distance error is a single bit error, which does not allow for an
`improvement via the elimination of input patterns. However, as
`linear densities in the magnetic recording channel approach 2.5 bits
`per PWso, the event changes. Assuming the NRZ input symbols
`(write current levels) are {-l,+l}, the error pattern ek = k(2, -2,2)
`dominates. Examination of the input patterns reveals that at least
`one pattern in each error generating pair contains three or more
`transitions. Therefore, a code that eliminates these error prone
`patterns by limiting the maximum number of consecutive transitions
`to two can improve the performance of near-optimal detectors.
`The class of codes known as maximum transition run (MTR)
`codes limits the number of consecutive transitions to j=2, and yields
`a coding gain [2][3]. The usual RLL k constraint is retained for
`timing recovery, leading to an encapsulation of the code parameters
`as MTR(j;k), where j is the maximum number of consecutive
`transitions. Prior to write precompensation, transitions allowed by
`the MTR code have a constant phase relative to the write clock. This
`is in contrast to the ternary 3PM code in which a pair of closely
`spaced transitions are used as a third symbol by shifting the pair half
`of the bit window to place the zero crossing at the same position in
`the bit window as the peak of an isolated pulse [4]. The codes
`developed in this paper are all MTR(2;k) types. Although the MTR
`code provides a concise set of constraints to yield the desired coding
`gain, similar distance gains may be obtained by other constraints
`such as those developed for E 2PRML [5].
`
`The vector x = (xlx 2...x,)
`represents the m-bit data word, and
`y = ( y , y , ...y,) is the n-bit codeword. Equations (1) and (2)
`implement the substitution rule
`
`.... 0,000.. - .... 0,110..
`
`(3)
`where the comma indicates the boundary between two codewords.
`The results is a rate 4/5MTR(2;6) code that requires a two state
`encoder and block decoder. By looking forward to the next data
`word, the encoder can determine if the following codeword will
`begin with a zero. In that case, the substitution
`
`.. 000,o .... - .. 011,o ....
`
`(4)
`is applied to further reduce k. As shown in Fig. 1, the encoder is a
`two-state encoder that uses the present data word x and the next
`data word w to produce block decodable 4/5MTR(2;4) codewords.
`
`...
`window 4
`1-encoder
`Fig. 1. Block diagram for the 415 MTR(2;4) encoder/decoder.
`
`...
`
`ture time ---t
`
`U
`
`The encoder block is described by the Boolean logic functions
`
`II. RATE 415 CODE DESIGN FOR REDUCED k CONSTRAINT
`
`One design methodology for MTR block codes is to maximize the
`code rate and then minimize the RLL k constraint. In doing so,
`however, it is possible to arrive at codes with reasonable rates but
`large values for k. To reduce k, a simple method for designing a
`two-state encoder for use with block decoding is proposed. With a
`block code, long periods of nontransitions generally occur when a
`codeword that ends with a string of zeros is concatenated with one
`that beings with a string of zeros. These long runs can be broken by
`
`Manuscript received January 31, 1997.
`This work was supported in part by Seagate Technology.
`
`and the corresponding decoder by
`
`-- - -
`x 4 = YIY2Y4X3 + Y4Y5
`Y3Y4X3 + Y]Y2 .
`XI = Y3 YsX4
`
`+
`
`0018-9464/97$10.00 0 1997 IEEE
`
`Authorized licensed use limited to: Kilpatrick Townsend & Stockton LLP. Downloaded on September 01,2020 at 23:37:08 UTC from IEEE Xplore. Restrictions apply.
`
`LSI Corp. Exhibit 1023
`Page 1
`
`

`

`2750
`
`Table I. Data to codeword maminn for a rate 4/5MTR(2;8) code.
`
`0100~00100 1000*01000
`0000-10000
`010l~00101 1001*0l001
`0001++00001
`0010~000l0 0110*00110
`1010*01010
`1011*10010
`0011-10001
`0lll*lOllO
`
`1100*01100
`1101*01101
`lllO*lOlOO
`llll*lOlOl
`
`Multiplication in the logic equations is equivalent to a Boolean
`AND, “+” denotes the OR operation, and an overbar indicates
`inversion. Logic equations given in this paper are minimized with
`respect to their complexity rather than timing requirements. As a
`result, some output variables are functions of other outputs as in (4)
`where x1 depends on x4. Evaluation of the functions from top to
`bottom in the given ordering is sufficient to guarantee that the
`necessary variables are valid at any given point. Again, note that
`although the encoder has two states (determined by the last codebit),
`the decoder can be realized as a block decoder because the
`substituted codewords are uniquely mapped to data words.
`ILI. RATE 617 CODE DESIGN
`
`A rate 617 code is possible in block form, if the inputloutput
`block sizes are quadrupled to 24/28; however, the large block sizes
`would result in an undesirably large logic circuit. Instead, a 617
`state-dependent code requiring a sliding block decoder with a
`modest window size is developed. The procedure described here is
`specific to MTR code design and is not appropriate for general code
`design. By focusing solely on the MTR parameters, this method can
`exploit codeword properties intrinsic to the MTR constraints.
`
`A. Codeword Selection
`To begin, the set of n=7 bit codewords that would be valid for an
`MTR j=2 block code are determined. (At this point, the RLL k
`constraint is ignored). For n=7, there are 57 valid words, including
`the all-zeros word; these are referred to as the basic set. For m=6,
`2m = 64 codewords are required. To satisfy this requirement, an
`extended set is formed by combining “1 10” with the set of length
`n=4 MTR block codewords. In hexadecimal form, the extended set
`is {60, 61, 62,64, 65,66,68, 69, 6A}. These additional words bring
`the codeword count to 66,2 more than are required. The extended
`set will not violate the MTR constraint if the preceding codeword
`ends in a zero. However, a method for preventing a violation when
`a one precedes an extended codeword is required; otherwise, three
`consecutive ones could occur. By converting the trailing three bits
`of the preceding word to “01 1 ,” the presence of a substitution is
`indicated. For the problem at hand, two substitutions are needed.
`These substitutions are referred to as Type I and Type 11 and are
`described by
`
`.... 001,110 .... - .... 011,001 ....
`.... 101,110 .... - .... 011,010 ....
`
`and
`
`(8)
`respectively. These substitutions allow the decoder to determine the
`type by looking forward three bits into the next codeword.
`
`B. Bounding and reduction of the k constraint.
`From the basic and extended sets of codewords, a rate 6/7
`MTR(2;-) code could be constructed. Because there are two extra
`codewords, the all zeros codeword is discarded, which bounds the
`maximum run of zeros to k=12 (generated by the concatenation of
`1000000,0000001). Reduction of the k constraint is accomplished
`
`by employing the method of section II. For the 6/7 code, a single
`rule is required. This Type III substitution is described by
`
`.... 000,000 .... - .... 011,000 .... .
`
`(9)
`Because the “01 1” pattern is followed by three consecutive zeros,
`it cannot be confused with ihe Type I and I1 substitutions. The
`resulting worst case zero-runs occur with the pattern pairs
`‘‘1000000,001 ....” and “ .... 100,0000001.” Thus, the Type III
`substitution reduces k to give a rate 617 MTR(2;8) code.
`
`C. Codeword mapping
`In a ROM based lookup table, any mapping of data words to
`codewords would be acceptable; however, the complexity of the
`corresponding Boolean logic equations will depend on the chosen
`mapping. The approach here is to generate a reasonable mapping;
`to find an optimal solution would require definition of the criterion
`for optimality, which could be area, speed, or some other metric. A
`divide-and-conquer approach in which the codeword set is
`partitioned into disjoint subsets containing a number of elements
`equal to a power of two makes the problem more tractable. Eight
`sets of eight codewords were used in the mapping chosen for this
`paper. These partitions are illustrated in Fig. 2 where a dot
`represents a valid codeword with a hexadecimal value equal to the
`sum of the row and column labels. The partitions are labeled
`alphabetically in the order in which they will be used. Partitions A,
`B, C, E, F and G were chosen so that the three most significant bits
`in the codeword map to the three most significant bits in the data
`word. Within these partitions, the codewords are ordered by the four
`least significant bits as { 8,1,2,9,4,5,6,A} so that the bits in seven of
`the codewords can be mapped directly to the data word. Similarly,
`the codewords in partitions D and H were ordered in an ad hoc
`manner that by inspection would yield a reasonable mapping. The
`basic code mapping (without substitutions) is provided in Table 11.
`
`Fig. 2. Partitioning of the n=7 codeword set assuming no substitutions.
`
`-
`
`100OOOHlOOlooo 100000*1101000
`010000*0101ooo
`0oooo0*0001000
`1 m 1 loo001 * 110ooo1
`loo001
`01ooo1*01ooo01
`000001 ”00ooo01
`loool0*lml0
`100010*11ooo10
`ol00l0-0loool0
`oo0010*OoooolO
`1ooo11*1001001
`100011“1101001
`010011-0101001
`000011”0001001
`lOOl~*1000100 100100-1100100
`010100-0100100
`000100*oo00100
`100101*1000l01
`100101-1100101
`010101*0100101
`000101-0000101
`01 0 1 10-01 001 10 1 001 10- 1000 1 10
`1001 10- 1 1001 10
`0001 1 0t*0000110
`100111*1101010
`010111*0101010
`100111-1001010
`ooo111“0001010
`01 1ooo*0110001
`lOlooo*l0l lo00 111ooo-o001100
`001000-0011000
`011001*0010000
`101001-101o001
`111001“ooo1101
`001001*0010001
`011010-0100ooo
`101010-1010010
`111010*0101100
`001010-0010010
`00101 1~0011001 011011-011oooo
`101011-1011001
`11101 1-0101101
`001 100“0010100
`011 1OO”lOOOOOO
`l01100-1010100
`11 1 lOO“lOOl100
`001101*0010l01
`011101*1010000
`101101-1010101
`111101*1001101
`001 110-0010110
`01 11 1 0 * 1 1 m
`101 110*1010110
`111 110*0110100
`001111-0011010
`011111-0110010
`101111*1011010
`111111-0110101
`
`Table U. Data to codeword map for a rate 6/7 code without substitutions.
`
`(7)
`
`Authorized licensed use limited to: Kilpatrick Townsend & Stockton LLP. Downloaded on September 01,2020 at 23:37:08 UTC from IEEE Xplore. Restrictions apply.
`
`LSI Corp. Exhibit 1023
`Page 2
`
`

`

`Based on the mapping in Table 11, the encoder can be
`implemented as a finite state machine using the present and future
`data word as input. The corresponding decoder uses a 13-bit wide
`window that encompasses the present codeword and the three
`adjacent bits from both the preceding and next codewords.
`Representative block diagrams for these two components are shown
`in Fig. 3. On the encoder side, x and w are the present and future
`data words, respectively. The state variables z and s are delayed
`versions of the trailing bit from the codeword and the auxiliary
`variable U. The present codeword at the decoder is denoted y with
`z and v being the past and present codewords, respectively.
`The encoder block implements the set of Boolean logic equations
`described by
`
`k =w1w2w3w4ws+w1w2w3
`-
`- -
`m = w, w2 w3 w4ws w6 + w, w2 w3
`
`I 1 n\
`
`2151
`
`Fig. 3, Block diagram for the 6,7 MTR(2;8) encoder/decoder,
`M1X code. This does not imply that a code with less complexity or
`a smaller RLL k constraint c&d not be constructed, Although-not
`shown here, a 96% efficient rate 5/6MTR(2;6) code was also
`constructed using the method presented in this section.
`Simulations were performed to quantify the performance gain of
`tbeMcodeoverarate16/17RU-(0,,6/6)ccde[q.SNRin~~4is
`lOlog,,(l/a~ )
`where the amplitude of the Lorentzian isolated pulse has been
`normalized to 1 and 0: is the variance of the additive white Gaussian
`noise. At a user bit density of 2.5 bitsPWS0, the MTR coded
`E ’PRML and FDTS/DF r=2 detectors show 1dB improvement over
`the same systems using an RLL code.
`
`.
`
`1 E-01
`
`1 E-02
`
`1 E-03
`
`1 E-04
`
`1 E-05
`
`-I
`16/17 PRML
`-F
`16/17EPRML
`8
`
`16/17E2PRML +
`
`6RE2PRML
`-0-
`16/17 tau=2
`
`. *
`
`1 E-06
`17
`
`19
`
`23
`21
`SNR (dB)
`Fig. 4. Performance with a Lorentzian pulse at 2.5 user bits/PWSO.
`IV. CONCLUSION
`
`6i7 tau=2
`I
`
`25
`
`27
`
`(1 1)
`
`A state-dependent encoding method for reducing the RLL k
`constraint in systems employing block decoding was presented. This
`technique was used to aid in the development of a rate 6/7 MTR(2;8)
`code. With an efficiency of 97.8%, this code is close to the
`maximum theoretical code rate but can be implemented with
`reasonable complexity.
`
`REFERENCES
`
`D. Eficiency and Pe@ormance
`the rate Of ‘Odes
`the MTRj=2 constraint is
`
`limited to the capacity C=0.8791, the RLL k=8 constraint reduces
`-
`-
`
`the capacity to C=0.8760. Thus, the efficiency of the rate 617 code
`described here is Eff = rute/cupucity=98.6%. By comparison, the
`rate 4/5MTR(2;4) code is 95.5% efficient. A rate of 7/8 is permitted
`under fie MTR constraint; however, such a code would have to be
`constraint‘
`the
`99.5% efficient even before
`Therefore, a rate 6/7 code is likely to be the highest rate, practical
`
`[I] P. H. Siege1 and J. K. Wolf, “Modulation coding for information storage,”
`IEEE Commun. Mag., vol. 29, no. 12, pp. 68-86, Dec. 1991.
`. _
`r21 J. Moon and B. Bricher. “Maximum transition run codes for data storaEe
`systems,” IEEE Trans. hagn., vol. 32, no. 5, pp. 3992-3994, Sept. 1996.
`[3] J, Moon and B, Brickner, “Method and apparatus for implementing
`Patent pending No. (5O/oI4,954, filed
`maximum transition
`codes,”
` AD^ 5.1996.
`[4] 0. V. Jacoby, “Ternary 3PM magnetic recording code and system,” IEEE
`Trans. Mugn., vol. 17, no. 6, pp. 3326-3328, Nov. 1981.
`[51 R. Karabed and p. H. Siegel, “Coding for higher order Partial response
`channels,” SPIE vol. 2605, pp. 115-126, Oct. 1995.
`[6] K. p. Tsang, “Method and apparatus for implementing
`length limited
`cod@ in
`response
`U.S. pafent5,537,112, July 16,1996.
`
`1
`
`7
`
`
`
`Authorized licensed use limited to: Kilpatrick Townsend & Stockton LLP. Downloaded on September 01,2020 at 23:37:08 UTC from IEEE Xplore. Restrictions apply.
`
`LSI Corp. Exhibit 1023
`Page 3
`
`