`
`PATENT
`NUMBER
`
`l.',t j...rri.i l-X:i: ;!: i:: ::: i! :i
`::::,:::;'i'i_,,
`.i. lj, .j. i..i:.riiii
`
`i: ii: :.i::i;i:1i:.1: :::i-::,r,i jr,t ;i::,i::i.: !!::i:
`:.:. i:::' :::.: i.... .i i...: i.i 'l
`.i. i...i iii iii i..i ,
`
`i::, i.:i .,. :.:i :l
`
`i.., ,..i. j
`
`,.i: ,.,.r j
`
`..., :.,.;
`
`z Ec6(
`
`t
`
`JO u
`
`J-
`
`9.
`
`UTILITY
`SERIAL
`NUMBER
`
`SERIALNUMBER
`::.i i:t:i .,. .tt . :i : ! ., ,r i i::
`
`gz6i
`
`l
`
`,#sisdrffi
`
`i.: :!: :i: :l: :i: :i:
`
`d#$Hee
`
`ri: :ir :::: i ! i:::, ::::' ': i:::;i: -J :l::, i 'r "l
`:,,:t- t.i ! i. t i.' i I
`
`5-K
`
`Foreign priority claimed E yes
`35 USC 119 conditions mot E yes
`V€rfiod and
`
`5F
`
`PARTS OF APPLICATION
`FILED SEPARATELY
`
`NOTICE OF ALLOWANCE MAILED
`
`33<
`
`Assistant Examiner
`
`U.S. DEPI OF
`
`PAT. &TM-PTO.436L
`
`').u
`
`Label
`Area
`
`)rm PTO-4364
`lev. 8/92)
`
`q/
`;(-t'lt
`
`JEFFRTYA. GAFFIN
`$UPERVISCIRY P,qTEST EXAMINER
`
`,tn"#N
`
`ISSUE
`BATCH
`
`NUMBER &,x
`
`WARNING: The information disclosed herein may be restricted. Unauthorized digclosurg may be
`by the United States Code Tltle 35, Sections 122, 181 and 368. Possession outside
`Patent & Trademark Otlice is restricted to authorized employees and contractors only.
`
`(FACE)
`
`LSI Corp. Exhibit 1006
`Page 1
`
`
`
`0si730?16
`
`PA
`
`trffiiltM*Nn0
`
`APPROVED FOR LICENSE
`
`Drte
`Entbred
`or
`Gounted
`
`CONTENTS
`
`Date
`Received
`or
`Mailed
`
`7-g*f {
`
`13.
`
`14.
`
`15.
`
`16.
`
`17.
`
`18.
`
`19.
`
`20.
`
`22.
`
`27.
`
`29.
`
`30.
`
`31.
`
`32.
`
`PTS enff$T JAr'l 1 t: 1s$$
`
`r{
`
`LSI Corp. Exhibit 1006
`Page 2
`
`
`
`PATENT APPLICATION SERIAL NO.
`
`0s/rua?16
`
`U.S. DEPARTMENT OF COMMERCE
`PATENT AT\ID TRADEMARK OFFICE
`FEE RECORD STMET
`
`3;i'1 [L 1il.1it,'?$ *973,]1.!.*
`i. :iiiL
`3?,t.L]i.r Lrf;
`
`PTO-1556
`(st87)
`
`LSI Corp. Exhibit 1006
`Page 3
`
`
`
`? ;,
`
`t !,. Ji ..r.s ._\.. . ,-.r
`
`0s/730716
`
`"
`
`ffi#
`
`Patterson & Keougtr, P.A.
`Attorney Docket No.: 1008.10-US-02
`
`CERTFICATE OF EXPRESS N{AIL
`Eryress lvtail labcl No. FM541656055US
`Dahof Depooit
`Octoberl5- 1996
`
`I hereby certify that tris paper is beinc deposibd with th€
`Unitcd- Stat€s ?oetal Seri'iie'E:<presc' Maiil Poet Office to
`Addreesse" scwia r,rrder 37 C.Ftr. S 1.10 on ttn date indicated
`abgve and ie addreesed to ttre Assistant Cocrrrissim€r br
`Fatents, WashingtdL D.C, 20231.
`
`SPECIFICATION
`
`I4IDfiMUM TRANSTTTON RUN CODES
`
`RETAIED APPTICATIONS
`This application is a formal application of the Provisional Application
`filed on April 5, L996, and assigned Serial No. 60/014854.
`
`LSI Corp. Exhibit 1006
`Page 4
`
`
`
`8
`frttf a@a'nq ;l-*i't.'"t
`Na. bo/0LL(,q,9(, fr(el
`
`3.4 (, - I0i
`tJs/7it0716
`+<."- k'-zA( oF US' fovr\iw*( alth"^*;'*t
`,ts-qA.
`
`f\
`
`The present invention relates in general to digital storage systems. More
`specificalll, the invention pertains to an improved coding technique involving
`data recovery channels utilizing sequence detection methods.
`
`10
`
`15
`
`20
`
`25
`
`BACKGROUND OF THE INVENTION
`Channel codes, sometimes called modulation codes, are maPPings of data
`bits into the symbols that are either transmitted in a communication system or
`recorded onto a medium in a storage device. The purpose of these codes is to
`prevent certain characteristics in the stream of symbols that make their recovery
`difficult, Runlength limited (RLL) codes are commonly used in magnetic recording.
`These cod.es impose a (d,k) constraint on the recorded data sequence. With the Non-
`Return-to-Zerc (NRZ) recording format, where the binary "1" represents a positive
`level ir, the magnetization waveform and the binary "0" negative level in the same
`waveform , d+1, is the minimum number of consecutive like symbols and k+1 is the
`maximum number of consecutive like symbols in the binary sequence. With the
`Non-Return-to-Zero-Inversion (NRZI) recording format, where a magnetic
`transition is represented by L and no transition by 0, d and k are the minimum and
`maximum rrumber of consecutive 0's between any two L's, respectively as described
`in P.H. Siegel, "Recording codes for digital magnetic storage," IEEE Transactions on
`Magnetics, vol. MAG-21, no. 5, pp. 1.3a4 - 1349, Sept. 1985. The d constraint is used
`to increase the minimum physical spacing between transitions. The k constraint
`guarantees that a change in the readback waveform will occur at regular intervals
`for the purpose of synchronizing a phase locked loop to the data. A (1',7) code is a
`common example of an RLL code; see U.S. Patent 4,337,458. Also popular is the
`(0,4/4) code, where d=0 and k=4 both for the data sequence and for the sequence that
`results if every other symbol is considered; see U.S. Patent 4,707,68L Additional
`constraints, such as a limitation orr the total number of NRZI l.'s in a codeword for
`the purpose of improving timing and gain control can be applied to these codes; see
`
`LSI Corp. Exhibit 1006
`Page 5
`
`
`
`U.S. Patent 5,196,849. A DC-free constraint as described in U.S. Patent 4,499,454 can
`be used to reduce the low frequency spectral content of the readback signal. Codes
`for data storage typically assume a binary symbol set such as the polarity of the write
`signal or the presence and absence of a transition, but it is possible to conceive
`systems that use more than two distinct symbols. For example, the ternary 3PM
`code uses three distinct symbols and places a lower bound on the distance between
`symbols in the same way that the RLL d constraint is applied to the binary case. See
`G.V. Jacoby, "Ternary 3PM magnetic recording code and system," IEEE Transnctions
`on Magnetics, vol. MAG-17, no. 6, pp.3326-3328, November 1981. In optical data
`storage, a special type of RLL constraint is applied to guarantee the minimum size of
`the written mark on the medium as described in R. Karabed and P. H. Siegel, "Even
`mark modulation for optical recbrding," International Conference on
`Communications, June 1989. While RLL (1,k ) coding has many useful properties,
`the required code rate, given by the number of data bits per channel bit, is typically
`low, forcing the channel to operate at a considerably higher speed than the actual
`data rate. On the other hand, (0,4/4) or more generally (0,G/I )coding offers a much
`higher rate, but does not provide any coding gain. Also, (O,GI ) codes are designed
`specifically for interleaved systems such as class IV partial response (PR4) systems,
`and are not optimal for other detectors such as fixed-delay tree search (FDTS)
`
`10
`
`15
`
`20
`
`systems.
`
`25
`
`Sequence detectors are data recovery devices that examine multiple
`received samples to recover the input data sequence. Methods such as Viterbi
`detection, FDTS/DF, and PRML are all sequence detectors. In magnetic data storage
`devices, the response of the channel to an input symbol typically extends over
`several sample periods. Sequence detectors can outperform sample-by-sample
`decision rules such as peak detection by using information about the data to be
`detected contained in adjacent samples. Errors in sequence detectors arise mostiy
`from difficulty in distinguishing minimum distance patterns. For a sequence
`detector that uses M samples to make a decision, all possible noiseless sample
`
`3
`
`LSI Corp. Exhibit 1006
`Page 6
`
`
`
`sequences can be plotted as points in an M-dimensional space, where each sample
`corresponds to a coordinate in this space. The minimum distance patterns are those
`patterns corresponding to different decisions that have the minimum Euclidean
`distance from one another. The Euclidean distance is the geometric distance
`between two points and refers to the square root of the sum of the squares of the
`differences between the coordinates of two points. The performance of sequence
`detectors such as E2PRML can be improved by coding to remove the patterns that
`cause minimum distance error events, thereby increasing the minimum distance.
`This increase in the minimum distance as a result of coding is termed coding gain.
`See R. Karabed and P. H. Siegel, "Coding for higher order partial response channels,"
`Proceedings of the International Society for Optical Engineering, vol 2605, pp. 115-
`126,1995.
`
`SUMMARY OF THE INVENTION
`The present invention relates to a channel coding technique to improve
`data storage devices such as magnetic computer disk drives and professional and
`consumer tape recorders. The coding scheme, which is referred to herein as the
`maximum transition-run (MTR) coding, eliminates certain error-prone binary data
`patterns from the allowable set of input data patterns that are to be recorded in the
`storage medium. As a consequence, the final bit error rate is improved significantly
`when the original data bits are reproduced. This improvement in the bit error rate
`can be traded for an increase in storage density if the error rate performance is
`already satisfactory. See B. Brickner and J. Moon, "Coding for increased distance
`with a d=0 FDTS/DF detector, " Seagate lnternal Report, May 1995; also presented at
`the Annual Meeting of the National Storage Industry Consortium, Monterey, CA,
`June 1995, and J. Moon and B. Brickner, "Maximum transition run codes for data
`storage systems," presented at Intermag '96 , Seattle, Washington, April 1996,
`More specifically, the MTR code imposes a iimit on the maximum
`number of consecutive transitions that can occur in the written magnetization
`
`10
`
`15
`
`20
`
`25
`
`4
`
`LSI Corp. Exhibit 1006
`Page 7
`
`
`
`pattern in magnetic recording. Analysis indicates that the performance
`improvement is most significant for the bit densities anticipated for products in the
`near future when the maximum nurnber of consecutive transitions is limited to
`two. The MTR code with a constraint length of j=2 will allow "dibit" transitions in
`the magnetization pattern, but will not permit "tribil" or longer runs of consecutive
`transitions. Unless indicated otherwise, our discussion of the MTR code relating to
`the present invention will be focused on the constraint of j =2 hereafter' when the
`MTR coding scheme is combined with a certain class of sequence detectors to
`recover written data in high density.recording, the bit-error-rate (BER) performance
`is improved significantly over existing code/detector combinations such as (0,G/ )
`code/partial response maximum likelihood (PRML) and (1,7) RLL code/peak
`detector combinations. Computer implemented simulations show a large
`performance advantage with the MTR code combined with high order PRML
`systems and fixed delay tree search with decision feedback (FDTS/DF) systems over
`the existing code/detector combinations. With the NMI format, the MTR code
`constraint is equivalent to limiting the maximum runlength of L's. To facilitate
`timing recovery, the usual maximum runlength constraint is also imposed on 0's.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`Figure L shows pairs of write patterns causing most errors in sequence
`detection at high user densities.
`Figure 2 is the state diagram for the MTR code with i=2.
`Figure 3 is the state diagram for an MTR (2;6) code.
`Figure4givesthecapacitiesfortheMTR/=2codeswithdifferentRLLk
`constraints.
`Figure 5 is a table showing the code parameters for MTR i =2btock codes
`with different RLL k constraints and different block sizes.
`Figure 6 shows a mapping of datawords to codewords for the rate 4/5 MTR
`
`(2;8) code.
`
`L0
`
`15
`
`20
`
`25
`
`5
`
`LSI Corp. Exhibit 1006
`Page 8
`
`
`
`Figure 7 is the E2PR4-VA trellis modified for use with an MTR j =2 code.
`Figure 8 illustrates a FDTS t=3 detector modified for use with an MTR i =!
`
`Figure 9 illustrates a FDTS t=2 detector modified for use with an MTR i =2
`
`code.
`
`5 code.
`
`Figure L0 lists a decimal representation of the valid codewords
`corresponding to different values of C for theS/I2 DC-free MTR/ =2 code.
`Figure LL lists code parameters for DC-free MTR j =2 blockcodes with
`different RLL k constraints and different block sizes.
`
`10
`
`15
`
`DESCRIPTION OF THE PREFERRED EMBODIMENT
`The present invention pertains to an improved coding technique to
`enhance the minimum distance properties of sequence detectors. The invention is
`advantageously used in storage and similar systems operating at high data densities.
`Prior art experience indicates that the primary source of errors in optimal
`and near-optimal sequence detectors operating at high data densities is the detector's
`inability in the presence of noise to distinguish the minimum distance patterns.
`Figure L is an exemplary depiction of pairs of write patterns which cause most errors
`in sequence detection. These four pairs correspond to an NRZ input error (or
`20 difference) pattern of eo- t 12 - 2 2|, assuming input data take on +1's and -1"'s.
`The present state of the art approach to attenuate these errors is to remove
`data patterns allowing this type of error pattern through coding. The potential
`improvement in the FDTS detection performance using this approach can be
`estimated by computing the increase in the minimum distance between two
`25 diverging look ahead tree paths after removing the paths that allow the +{2 - 2 2l
`error events. A simple minimum distance analysis for PRML systems reveals that
`this is also a critical error pattern in high order PRML systems such as E2PR4ML.
`Low order PRML systems are not dominated by these errors because thev force the
`
`LSI Corp. Exhibit 1006
`Page 9
`
`
`
`cha4nel to respond like a low density system where the minimum distance error
`event is different.
`To obtain a coding gain (improvement in minimum distance due to
`coding), the minimum distance pairs shown in Figure L must be eliminated. In
`accordance with the present invention, this can be accomplished using the existing
`RLL (1,k ) code, which does not allow consecutive transitions. The minimum
`requirement for producing a coding gain in this situation is to remove one pattern
`from each pair of minimum distance sequences. RLL (1,k ) codes eliminate both
`patterns associated with all the minimum distance pairs and thereby result in fewer
`patterns available to the encoder. Consequently this imposes the need to map input
`data to a small set of patterns resulting in a lower code rate (the ratio of the number
`of input bits to output bits). Further, this increases the speed and bandwidth at
`which the detector must operate to produce data bits at a particular speed. An
`increase in noise bandwidth translates to increased noise in the system, which
`works against the coding gain. The idea of MTR coding is to eliminate all sequences
`with three or more consecutive transitions, but allow the dibit pattern to survive in
`the recorded sequence. Thus, with MTR coding, the dominant error events will be
`prevented as with (1",k ) coding, but the required code rate is much better than that of
`the typical (1,k ) RLL code.
`Referring now to Figure 2, the MTR / =2 code based on the NRZI
`recording convention, where L and 0 represent the presence and absence,
`respectively, of a magnetic transition is shown. Specifically, Figure 2 depicts a state
`diagram defining all possible channel input sequences. For example, a sequence can
`be found by starting at any state and moving along the arrows. In the alternate, a
`sequence can also be found by taking each arrow label as the channel input. The
`capacity of the code can be obtained by finding the largest eigenvalue of the
`adjacency matrix A, which describes the transitions between states for the given state
`diagram and computing:
`CapacitY = logrl,*""(A).
`
`(1)
`
`10
`
`15
`
`20
`
`25
`
`,7
`
`LSI Corp. Exhibit 1006
`Page 10
`
`
`
`To more compactly describe the code constraints, the MTR parameters are written as
`fi;k) where 7 is the MTR constraint and k is the usual RLL constraint. For practical
`codes, the RLL k-constraint must be included for timing recovery. This constraint
`can be incorporated into the state diagram as in the case of the MTR(7;k)=(2;6) code
`shown in Figure 3. The capacities for MTR(2;k) codes for different k constraints are
`given in Figure 4. The capacity is the upper bound on the code rate for the given set
`of parameters. Most codes will have a rate less than capacity because typically the
`code complexity will become very large as the code rate approaches capacity. For
`example, a code with a rate of 7 /B is possible for k> 8i however, it is likely to be
`extremely complex. Lower rates such as 4/5,5 /6 and 6 /7 wiIL require less
`complexity, while still improving on the 2/3 rate of RLL(1'7) codes'
`While state-dependent encoders and sliding block decoders can be
`designed for the MTR constraint, simple fixed-length block codes can be realized
`with good rates and reasonable k values. A computer search is utilized to find the
`Zm n-bit codewords required to implement a rcte m/n block code. First, all binary
`words that contain the NRZI string of "11L" or more than k consecutive NRZI 0's
`are removed from the list of 2n n-bit binary words. Then, in order to meet the MTR
`constraint at the codeword boundaries, words that start or end with a "11"' sttins are
`removed. Also, the k constraint is satisfied at the boundary by removing the words
`with k1+L leading 0's or k2+1 trailing 0's where k:+kr=ft. Figure 5 shows code
`parameters for representative block codes obtained through computer search for
`various combinations of n and k. The efficiency is defined as the ratio of the code
`rate, mfn, to the capacity computed for the given value of k and the MTR
`constraint. Thus, the efficiency is a measure of how close the rate is to the uPPer
`bound.
`
`As an example of a MTR block code, the rate 4/5, MTR(2;8) block code is
`given in Figure 6. The pairing of user data blocks and codewords were chosen so
`that the second bit in the codeword corresponds to the second bit in the user data.
`Many other pairings are possible; the one chosen is reasonable, but not necessarily
`
`10
`
`15
`
`20
`
`25
`
`LSI Corp. Exhibit 1006
`Page 11
`
`
`
`optimal in terms of minimizing the logic implementation. Note that the k=B
`constraint comes into effect when the codewords 10000 00001 occur in sequence. If
`the user data and codeword pairs are represented by
`Y =[XoXtXrXs] +lY- lYoYtY2YsY4l.
`5 then the equations for the encoder are:
`M=To*7,
`Yo =T tV rT uT o + XrT, + XrX,
`Y1=XeT ,.7 , + XsT 2
`Yz= Xt
`
`(2)
`
`(3)
`
`10
`
`Ys= XzT tM
`Yq=T oT ,xu + xrM +T ,xu.
`
`The corresponding decoder is
`
`15
`
`Xo=T zY ox, +Y oyrT , + y,
`xf Yz
`Xz= YoX: + YsXs + Yj
`Xs= YoY3 + Ya.
`
`(4)
`
`These logic rules are representative of those that could be developed for any of the
`MTR codes using industry standard design packages"
`Block codes with short block lengths tend to have low efficiencies because
`many potential codewords are eliminated by the boundary conditions. State-
`dependent encoders can use more codewords and achieve higher efficiencies
`because the state carries information about the previously used codeword(s). A
`shortcoming of codes that use a state-dependent encoder is that, in general, they
`require a sliding-block decoder that examines the codeword arrd other codewords
`adjacent to it. This mechanism can cause detection errors in adiacent codewords to
`
`LSI Corp. Exhibit 1006
`Page 12
`
`
`
`affect the decoding of other codewords, an effect known as error propagation. It is
`possible to conceive state-depended encoders that use block decoders, thereby
`eliminating error propagation in the decoder. To this end, a two-state encoder can
`be formed in which the two states correspond to the last bit of the previous
`codeword. Knowledge of the most recent bit allows codewords to be added for both
`cases. In this manner, the mapping from dataword to codeword is dependent on the
`previously used codeword, but if the mapping from codeword to dataword is
`unique, a block decoder can be used.
`An application of this technique is the reduction of the k constraint for a
`particular block code. The block code boundary condition eliminates all codewords
`that begin with "I'J"", but if the last bit is known to be a 0, these codewords are valid.
`For small block sizes, the k constraint usually comes into effect when codewords
`beginning arrd ending with 0 are joined. By replacing the codewords with a long
`run of NRZI 0's with a codeword beginning with "L1," when the previous bit is a 0,
`the k constraint can be reduced. To illustrate this, consider the rate a/5 MTR(2;8)
`code. The RLL k=8 condition exists only when the codewords 10000 and 00001 are
`put together. Similarly,k=7 occurs when 10000 and 00010 or 01000 and 0000L are
`combined. A11 three cases can be eliminated if, following a codeword with Yn=S, ths
`codewords 00001 and 00010 are replaced by codewords where Yo=L. This is not
`
`possible for a block code because all the available codewords are used; however,
`codewords beginning with 1"1,0 are valid if the preceding bit is a 0. In the case of
`codewords with length n=5, three such words exist; they are 11000, 11001, and 1L010.
`To reduce the required k constraint to 6, the following conditional mappings are
`used:
`
`10
`
`15
`
`20
`
`-'--r* r
`
`2s { lt'c
`
`K
`
`and
`
`Yl (X = 0010) =
`
`[110002=0
`{
`[00010, Z = |
`
`L0
`
`(s)
`
`(6)
`
`LSI Corp. Exhibit 1006
`Page 13
`
`
`
`where Z is the value of Ia in the previous codeword. All other pairings are
`unchanged from Table I. In effect, the conditional mappings creates a state
`dependent encoder with two states. Unlike most state dependent encoders, there is
`only one possible data word for each codeword; therefore, a block decoder can be
`5 used. Boolean equations for the resulting encoder is given by
`
`10
`
`Yo=X tY tY sY n +XzY s + X oY, +XrXu
`Yr =T tXzT tZ +V rT ,XuZ + XoX ,T s + XoT ,
`Yz= Xt
`Y, =T ,xrV uz + xoV ,x, +T oxrx,
`Y+= XsT z.
`
`The corresponding block decoder is
`
`15
`
`Xo= Y zYaXa +Y ,Y sXz + Y oYt
`xF Yz
`Xz= YoYrV n + YsV 1Y4 + YsY2 + Y3
`Xs= YoY3 + Y4.
`
`(7)
`
`(8)
`
`20
`
`MODIFIED DETECTION AND DISTANCE GAIN
`To realize the coding gain at the detector output, the detector has to be
`modified. In the case of PRML systems, this amounts to removing those states that
`correspond to the illegal data patterns from a trellis. A Viterbi trellis corresponding
`to an E2PR4 system modified for use with MTR(2;k) coding is shown in Figure 7.
`25 For uncoded or RLL(0,k) systems, all 16 states would be present along with two state
`transitions corresponding to the two binary inputs. The state labels are Yo = (op,, o1n-1,
`
`a1"-2 ,a1n3 ) where ag att€ the NRZ write current symbols taking on values from {-1,,+1}.
`The states labeled 5 and L0, corresponding to (-1,+1,-1,+1) and (+I,-1.,+t,-L),
`
`11
`
`LSI Corp. Exhibit 1006
`Page 14
`
`
`
`resPectively, have been removed because they represent three consecutive
`transitions in the NRZ data. Similar modifications can be performed on higher
`order PRML detectors. For the FDTS/DF detector, the code-violating look ahead
`paths must be prevented from being chosen as the most-likely path, a technique
`similar to the one used in the RLL(1,7) coded FDTS/DF channel. To illustrate the
`
`idea, consider Figure 8 that shows a tr=3look ahead tree utilized in FDTS/DF
`detection. The shaded paths in the tree correspond to the input data patterns with
`three consecutive transitions, and ale considered illegal. For the t=2 tree shown in
`Figure 9, the past decision must be used to determine an illegal path, which is either
`the third path or the sixth path, as indicated by the marked paths. The complexity in
`the signal space formulation of the FDTS/DF detector is also reduced greatly with
`the MTR code. See, for example, B. Brickner and ]. Moon, 'A high dimensional
`signal space implementation of FDTS/DF," presented at Intermag '96, Seattle,
`Washington, April 1996. For a rnore detailed description of FDTS/DF detection, see
`U.S. Patent 5,136,593.
`With this modification in FDTS/DF detection, the squared minimurn
`
`Euclidean distance between any two diverging paths, denoted by F*6, is typically
`given by aQ+f ,2+fzz+ ...+f ,2) for t greater than or equal to 2, where f= (L, f t, f z, ...,
`f u) represents the / sample equalized dibit response (at the output of the forward
`equalizer) normalized so the first sample is 1". The effective SNR gain of the t=2
`FDTS/DF over the DFE, assuming the MTR j =2 code, is given by 1"01og10$/t + f f +
`f zz)dB.
`
`The distance gain with MTR coding is also significant for high order
`PRML systems such as E2PR4. When the critical NRZ error pattern is t{2 - 2 21, the
`minimum distance for the E2PR4 response {1 2 0 - 2 - 1l is 6lT . With MTR coding,
`the worst case error pattern becomes a single bit error pattern of +{2}, and the
`corresponding channel output distance is simply the square root of the energy in the
`
`10
`
`15
`
`20
`
`25
`
`12
`
`LSI Corp. Exhibit 1006
`Page 15
`
`
`
`equalized dibit response, or l0lT . This increase in the minimum distance is
`equivalent to an SNR gain of 2.218 dB. If the code rate penalty is small, the overall
`coding gain is significant.
`
`DC-FREE MTR CODES
`Other useful constraintE can be imposed on the MTR code at the expense
`of lowering the code rate. There exist storage systems where the recorded square
`waveform cannot have a DC component. In such applications, a DC-free constraint
`is necessary on the written data. The MTR code can be designed to have a DC-free
`property. A DC-free constraint is satisfied by bounding the running digital sum
`(RDS) of the binary sequence. The RDS at a given time is defined to be the excess
`number of 1's over 0's in the binary sequence up to that time, assuming the NRZ
`recording format is used (a negative RDS means there has been more 0's than L's).
`The following method can be used to design DC-free MTR codes. Assume
`an NRZ recording format. Starting from a list of 2n n -bit binary words, first remove
`all binary words that contain either "010L" or "L010" as well as any words that
`contain more than k+1" consecutive like symbols. Then, to satisfy the MTR i =2
`constraint at the codeword boundaries, remove all words that start with "01" or "I0"
`and remove all words that end with "1"01" or "0I0". The same effect can be achieved
`by removing all words that end with 0L or L0 as well as the words that start with
`"'1,0L" or "0\0". The k constraint can be satisfied at boundaries by eliminating all
`words that either start with k1 consecutive like symbols or end with k2 consecutive
`like symbols, where k1 and k2 are preselected nurnbers such that k1 +k2-k+I. The
`remaining codewords in the list now satisfy the MTR constraint as well as the k
`constraint. Investigation of the remaining codewords reveals that for every
`codeword, there exists another codeword which is a bit-by-bit complement of the
`first codeword. Now define charge C to be the number of L's in the codeword
`minus the number of 0's in the same codeword, If a codeword has a charge C, its bit-
`wise cornplement will have a charge -C. This property is used to design a DC-free
`
`10
`
`15
`
`20
`
`25
`
`13
`
`LSI Corp. Exhibit 1006
`Page 16
`
`
`
`code. The final list of the valid DC-free MTR codewords is obtained by further
`removing either all the words with negative charges or all the words with positive
`charges. The final list now contains codewords with either zero-charge or charges
`with the same polarity. When a dataword is mapped to a zero-charge codeword, the
`mapping is one-to-one as usual. But when a dataword is mapped to non-zero-
`charge codeword, either the codeword itself or its bit-wise complement is released by
`the encoder output, depending of the RDS value at the end of the last codeword. By
`choosing the codeword with a polarity which is opposite to the polarity of the
`present RDS value, the RDS is always kept bounded. Figure 10 shows a decimal
`representation of codewords corresponding to different values of C for the 8/12 DC-
`free MTR code. The k -constraint in this case is equal to 8. Figure 11 lists the code
`parameters for various DC-free MTR block codes obtained using the method
`described above.
`While the preferred embodiments of the invention have been shown and
`15 described, it will be obvious to those skilled in the art that changes, variations and
`modifications may be made therein without departing from the invention in its
`broader aspects and, therefore, the aim in the appended claims is to cover such
`changes and modifications as fall within the scope and spirit of the invention.
`
`10
`
`1,4
`
`LSI Corp. Exhibit 1006
`Page 17
`
`
`
`What is claimed is:
`
`greater
`
`pparatus for encoding m-bit binary datawords into n$itbtnary codewords,
`waveform, where m and n are preselected positive integers such that
`m , camPrlsmg:
`ver means for receiving the dataword;
`means coupled to the receiver means, for producing sequences
`
`a i
`
`s
`
`of fixed length
`
`said sequ
`the recorded waveform
`
`and
`
`ting no more than i consecutive transitions in
`that 7 is an integer equal to or greater than 2;
`
`said sequences generating
`without a transition in the recorded
`
`than k consecutive sample periods
`
`A,oal7r.
`'Zin
`
`3n
`A=
`
`2. Apparatus as in claim L wherein the i consecutive transition limit is defined
`by the relationship 2Sj <1.0.
`4
`,{
`Apparatus as in claim 2 wherein the consecutive transition limit is defined by
`the relationship i=2.
`
`Apparatus as in claim 2 wherein the binary sequences produced by combining
`codewords have no more than i consecutive L's and no more than k consecutive
`0's when used with a NRZI recording format.
`Alu
`
`Apparatus as in claim 2 wherein binary sequences produced by combining
`codewords have no more than one of i consecutive transitions from 0 to 1 and from
`L to 0 and no more than one of /c +L consecutive 0's and k +L consecutive L's when
`used in conjunction with a NRZ recording format.
`
`15
`
`5 6 7 8 9
`
`10
`
`11
`
`1 2
`
`1 2
`
`1 2 J
`
`1 2 aJ 4
`
`LSI Corp. Exhibit 1006
`Page 18
`
`
`
`tl
`I1, F.
`Apparatus as in claim 2 wherein the encoder means produces a codeword in
`2 response to each dataword sequentially, based on a predetermined word-by-word
`3 mapping of 2m m-bit datawords to 2m n -bit codewords, wherein the codewords are
`4 preselected using a selection method comprising the steps of:
`5
`emoving binary words that contain more than one of i consecutive
`6
`1's and more than k consecutive 0's from a list of 2n possible n-bit binary
`7
`words;
`8
`removing one of binary words that begin and end with two
`9
`consecutive L's;
`10
`removing one of binary words that begin with k1+ L consecutive
`11
`0's and end with k2+1' consecutive 0's where k1 + kz=k; and
`12
`choosing 2m codewords remaining in the list, which contains at least
`13
`2mvalid codewords.
`4Jt
`1 rf.
`Apparatus as in claim 2 wherein the encoder means produces a codeword, in
`2 response to each dataword sequentially, based on a predetermined word-by-word
`3 mapping of 2m m-bit datawords to one of N n-bit codeword sets, wherein N may be
`4 written as N = 2i and.l is a positive integer and further that a selection of one of
`5 said N n-bit codeword sets is determined by a state of the encoder wherein said state
`6 is a predetermined function of a previous state and the encoder input and each set
`7 contains 2m codewords wherein, a particular codeword may appear more than once
`8 in a given set and further a particular codeword may also appear in more than one
`9 set.
`I
`4
`Apparatus as in clai#wherein the encoder means produces a codeword in
`{
`response to each dataword sequentially, based on a predetermined word-by-word
`mapping of 2m m-bit datawords to one of two n-bit codeword sets, where each
`particular codeword set contains 2m different codewords, some of which may also be
`
`1 2 J 4
`
`16
`
`LSI Corp. Exhibit 1006
`Page 19
`
`
`
`5 used in the other set and the set mapped to the encoder is chosen based on the last
`6 bigpry symbol of the previous codeword.
`/ttl,
`1, f.
`Apparatus as in claimg{rherein, a first set (A) is chosen when a last binary
`2 symbol of a previous codewofi (Z) is a 0 and a second set (B) is chosen when Z is a 1,
`3 and valid codewords for sets A and B are by the steps of:
`4
`removing binary words that contain more than one of i consecutive
`5
`1.'s and more than k consecutive 0's from each of two lists of 2rz possible
`6
`codewords for sets A and B, respectively;
`7
`removing words that end with two consecutive L's from both lists;
`8
`removing words from the list for set B that begin with two consecutive
`9
`10
`11
`12
`13
`14
`15
`1'6
`
`L',s;
`
`selecting k1 + k2 = la;
`removing words from the list for set A that begin with one of k1 + L 0's
`and end withk2 + l. 0's;
`removing words from the list for set B that end with consecutive 0/s
`and k2 + 1; and
`
`selecting the 2m codewords used in each of set A and set B from the
`respective lists, each of which contains at least 2m codewords.
`
`6
`1 Jd Apparatus as in claim 2 wherein the sequences of codewords also satisfy a DC-
`2 free constraint.
`b
`4
`1 2{. Apparatus as in claim,Jdwherein the encoder means produces a codeword in
`2 response to each dataword sequentially, based on a predetermined word-by-word
`3 mapping of 2m m-bit dataword s to 2m n-bit codewords, where the codewords are
`4 preselected using a selection method comprising the steps of:
`5
`removing binary words that contain either "0L0L" or "10L0" from a list
`6
`of 2n possible n-bit binary words;
`
`t7
`
`LSI Corp. Exhibit 1006
`Page 20
`
`
`
`removing word