PROVISIONAL
`APPLICATION ·
`NUMBER
`
`SERIAL NUMBER
`60/014,954
`F·ROV IS, I 01\JAL
`
`FILING DATE CLASS
`04/05/96
`
`SUBCLASS
`
`GROUP ART UNIT
`
`EXAM1NeR
`
`~ JAEKY~~ MOON, MINNEAPOLIS, MN; BARRETT J. BRICKNER, MINNEAPm.rs, MN.
`
`i
`·~
`
`**CONTINUING DATA********'************
`VERIFIED
`
`**FOREIGN/PCT APF'LICATIOMS************
`VERIFIED
`
`Foreign priority claimed
`35 USC 119 condttlon• mel
`
`AS
`FILED
`
`STATE OR SHEETS TOTAL
`COUNTRY DRWGS. CLAIMS
`
`FlJREI~~ FILING LICENSE GRANTED 02/11/?7
`(cid:143)
`· D yes
`no
`.(cid:143)
`y<,fi O no
`Examlne(s lnlUal• --+
`V•~fiecl 8nd Acknowledged
`.JOHI\J F THUENTE
`;·ATTEPGON AND KEOUGH
`:. ;; 0 (: F(r,h:r:, TOliJER
`!'•ic\f/CUIC:TTE: AVl:],II_IE :30UTH
`.,_,,/-~'
`MT~NEAPOL[S MN 55402-1314
`
`***** SMALL ENTITY****•
`
`INOEP.
`CLAIMS
`
`An·c .oNEY'S
`FIL;'.\iO Fe.E
`DOCKET No:
`RECEIVED
`:1i:i.OO .. O I 17f:7n0:1.-·Ub
`
`MI\J
`
`9
`
`METHOD AND APPARATUS FOR IMPLEMENTING MAXIMUM TRANSITION RUN CODES
`
`U.S, DEPT. OF COMMJ PAT. & TM-PT0-436L {Rev.1
`
`Fom, PT0-1625
`/) ,,
`(Rev. 5/95
`. ,<~"'
`✓
`
`(FACE)
`
`UMN_0000020
`
`UMN EXHIBIT 2021
`LSI Corp. et al. v. Regents of Univ. of Minn.
`IPR2017-01068
`
`
`Page 1 of 41
`
`

`

`____ 12. - - - - - - - - -
`____ 13. - - - - - - - - - - - - - -
`
`__ g_ ----------,---
`____ 10.
`- - - - - ' - - ' 11. ================== -----
`____ 14. ___ _____:_ ___ - -
`____ 1 s. -----'-__ .:.__ __
`____ 15. - - - - - (cid:173)
`~ - - -1 7 . - - - - - -
`_ ___ 1 s. - - - - - - - - , - - - - -~ - - - - -
`____ 19. - - - - - -
`____ 2 o. - - -~ - -
`____ 21. - - - - - - -
`____ 22. - - - - - -
`__ :____23 _ - - - - - - -
`~ - - - 24. - - - - - -~ - -
`- - -~ 25.
`- - - - - -
`____ 27. _____ __:,_
`- - - - ' - - 26. __ __ _:__ __ ~_ - - - - -
`- - - - 28 . -----=-----
`____ 30. ___ _:,__ __
`- - - - 29 . - - - - - -
`
`- - - - -
`
`- -~ - 31 .
`- - - - 32 . - - - - - - -~ - - - - - -
`
`(FRONT)
`
`UMN_0000021
`
`
`Page 2 of 41
`
`

`

`IDNO.
`
`DATE
`
`POSITION
`
`CLASSIFIER
`EXAMINER
`TYPIST
`VERIFIER
`CORPS CORR.
`SPEC.HAND
`FILE MAINT
`DRAFTING
`
`(LEFT INSIDE)
`
`J ..
`
`UM N _ 0000022
`
`
`Page 3 of 41
`
`

`

`BAR CODE LABEL
`
`11111111~1111111111111111111111111111111111111111
`
`U.S. PATENT APPLICATION
`
`SERIAL NUMBER
`
`60/014,954
`PROVISIONAL
`
`RUNG DATE
`
`CLASS
`
`GROUP ART UNIT
`
`04/05/96
`
`JAEKYUN MOON, MINNEAPOLIS, MN; BARRETT J, BRICKNER, MINNEAPOLIS, MN,
`
`**CONTINUING DATA*W******W**~****•****
`VERIFIED
`
`**FOREIGN/PCT APPLICATIONS************
`VERIFIED
`
`FOREIGN t!LING LICENSE GRANTED 02/11/97
`TOTAL
`INDEPENDENT
`CLAIMS
`ClAIMS
`
`SHEETS
`DRAWING
`
`STATS OR
`COUNTAY
`
`MN
`
`9
`
`JOHN F THUENTE
`PATTERSON AND KEOUGH
`1200 RAND TOWER
`527 MARQUETTE AVENUE SOUTH
`MINNEAPOLIS MN 55402-1314
`
`***** SMALL ENTITY*****
`
`RUNG FEE
`RECl:IVEO
`
`ATTORNEY DOCKET NO.
`
`$100. 00
`
`178?.0l-US-O
`
`METHOD AND APPARATUS FOR IMPLEMENTING MAXIMUM TRANSITION RUN CODES
`
`This ls to certify that annexed hereto is a true copy from the records of the United States
`Patent and Trademark Office of the application which is identified above.
`By oillharity of lho
`COMMISSIONER OF PATENTS AND TRADEMARKS
`
`Dall
`
`Certifying Ollie.or
`
`UMN_0000023
`
`
`Page 4 of 41
`
`

`

`PATENT APPLICATION SERXArhio014954
`
`U.S. DEPARTMENT OF COMl'.ERCE
`PATENT AND TRADEMARK OFFICE
`FEE RECORD SHEET
`
`PT0-1556
`(S/87)
`
`UMN_0000024
`
`
`Page 5 of 41
`
`

`

`Patterson & Keough, P.A.
`Attorney Docket No.: 1787.01-US-01
`
`METHOD AND APPARATUS FOR IMPLEMENTING
`MAXIMUM TRANSITION RUN CODES
`
`Field of the Invention
`The present invention relates in general to digital storage systems. More
`specifically, this invention deals with an improved coding method and apparatus
`for use in data recovery channels utilizing sequence detection methods.
`
`5
`
`1 0
`
`1 5
`
`Background of the Invention
`Magnetic recording systems represent an increasing fraction of the total
`volume of magnetic storage devices. Accordingly, there is an ever increasing
`demand for greater densities in these devices. A wide variety of detection and
`equalization methods have been proposed to address this need. Large code storage
`at optimal capacity is one of the ways to meet this demand.
`The use of Runlength limited (RLL) codes in magnetic recording is well
`lmown. These codes impose a (d,k) constraint on the recorded data sequence. In
`reference to the non-return-to-zero (NRZ) sequence, d + 1 is the minim um number
`of consecutive like symbols and k+l is the maximum number of consecutive like
`symbols. 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. With the NRZ recording format, where the binary "1"
`represents a positive level in the magnetization waveform the binary "O" a negative
`level in the same waveform, (d+1) is-the minimum number of consecutive like
`symbols and (k+ 1) is the maximum number of com;e..utive like symbols in the
`binary sequence. With the Non-Return-to-Zero-Inversion (NRZI) recording format,
`3 0 where a magnetic transition is represented by "l" and no transition by "O", d and k
`are the minimum and maximum numbers of consecutive "O"s between any two
`
`2 0
`
`2 5
`
`UMN_0000025
`
`
`Page 6 of 41
`
`

`

`2
`
`5
`
`1 0
`
`''l''s, respectively. See P.H. Siegel, "Recording codes for digital magnetic storage,"
`IEEE Transactions on Magnetics, vol. MAG-21, no. 5, pp. 1344 - 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 M. Cohn, G.V. Jacoby, and A.
`Bates III, "Data encoding method and system employing two-thirds code rates with
`full word lookahead," U.S. Patent 4,337,458, 1982. Also popular is the (0,4/ 4) code,
`where d=O and k=4 both for the data sequence and for the sequence that results if
`every other symbol is considered. See J.S. Eggenberger and A. M. Patel, "Method and
`apparatus for implementing optimal PRML codes," U.S. Patent 4,707,681, 1987. In
`optical data storage, a special"type of RLL con~traint is applied to guarantee the
`minimum size of the written mark on the medium. See R. Karabed and P.H.
`Siegel, "Even mark modulation for optical recording," International Conference on
`15 Communications, June 1989. While (d,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 cha1u,el 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,G/I) codes clre designed
`specifically for interleaved systems such as class IV partial response (PR4) systems,
`and are not suitable for other detectors such as extended class IV partial response
`(EPR4) systems and fixed-delay tree search (FDTS) systems.
`
`2 0
`
`25
`
`Summary of the Invention
`The present invention relates to a coding techniqt1e to improve data
`storage devices such as magnetic computer disk drives and professional and
`consumer tape recorders. The present coding scheme, as referred to herein, as the
`maximum transition-run (MTR) code eliminates certain error-prone binary data
`patterns from an allowable set of input data patterns that are to be recorded in the
`
`UMN_0000026
`
`
`Page 7 of 41
`
`

`

`3
`
`5
`
`1 5
`
`storage medium. As a consequence, the final bit error rate, the most important
`performance measure of any digital recorder, is improved significantly when the
`original data bits are reproduced. This improvement in the bit error rate can also be
`traded for an increase in storage density if the error rate performance of the recorder
`is already satisfactory. See B. J. Bl'ickner and J. Moon, "Coding for increased distance
`with a d=O FDTS/DF detector," Seagate Internal Report, May 1995; also presented at
`the Annual Meeting of the National Storage Industry Consortiwn, Monterey, CA,
`June 1995, which paper is incorporated herein by reference. J. Moon and B. J.
`Brickner, "Maximum transition run codes for data storage systems," a Supplemental
`1 0 Disclosure submitted herewith and duly incorporated herein by reference.
`More specifically, the MTR code imposes a limit on the maximum
`number of consecutive transitions that can occur in the written magnetization
`pattern in magnetic recording. Findings under the present invention indicate that
`the performance improvement is most significant when the maximum number of
`consecutive transitions is limited to two. The MTR code with a constraint length of
`2 will allow "dibit" transitions in the magnetization pattern, but will not permit
`"tribit'' or longer runs of consecutive transitions. Unless indicated otherwise, the
`disclosure of the MTR code relating to the present invention will be focused on the
`constraint length of two. When the MTR coding scheme is combined with a certain
`class of sequence detectors, to recover written data in high density recording, the bit(cid:173)
`error-rate (BER) performance is improved significantly over existing code/ detector
`combinations such as (0,G/1) coded/partial response maximum likelihood (PRML)
`and (1,7) RLL code/peak detector combinations. Computer implemented
`simulations show large performance advantages of the MTR code combined with
`high order PRML systems and fixed d_elay tree search with decision feedback
`(FDTS/DF} systems the existing code/detector combinations. According to the NRZI
`format, the present code constraint is equivalent to limiting the maximum
`runlength of ones (l's). To facilitate timing recovery, the usual maximum
`runlength constraint i:; also imposed on the zeros (O's).
`
`2 0
`
`2 5
`
`UMN_0000027
`
`
`Page 8 of 41
`
`

`

`4
`
`Brief Description of the Drawings
`Fig. 1 shows pairs of write patterns causing most errors h1 sequence detection at high
`user densities.
`Fig. 2 is a state diagram for the MTR code with 7c =6.
`Fig. 3 is a table showing capacities for the MTR code with different k constraints.
`Fig. 4 is a table showmg code parameters for various MTR block codes.
`Fig. 5 shows a mappmg of datawords to codewords for the rate 4/5 lv'ITR code with
`k=8.
`Fig. 6a shows an encoder logic implementation for the rate 4/5 MTR code.
`Fig. 6b shows a decoder logic implementation for the rate 4/5 MTR code.
`Fig. 7 shows a decimal representation of valid codewords for the 8/10 MTR block
`code with k=6.
`
`Fig. Sa illustrates a modified FDTS detection for 1:=2.
`
`Fig. 8b illustrates a modified FDTS detection for -.=3.
`Fig. 9 shows a decimal representation of codewords corresponding to different
`values of C for the 8/12 DC-free MTR code.
`Fig. 10 lists code parameters for various DC-free MTR block codes.
`
`Detailed Description of the MTR Codes
`Investigation of high density error patterns in FDTS/DF detection reveals
`that errors arise mostly due to the detector's inability to distinguish the minimum
`distance transition patterns, both pairs of which are shown in Fig. 1. These two pairs
`correspond to an NRZ mput error pattern of ek = ± (2 - 2 2), assuming input data take
`on +l's and -l's. The present approach is to remove data patterns allowing this type
`of error pattern through codmg. The potential improvement in the FDTS detection
`performance using this approach can be estimated by computmg the increase in the
`minimum distance between two divergmg lookahead tree paths after removh1g the
`paths that allow the ±[2 - 2 2) error events. A simple minimum distance analysis for
`
`5
`
`1 0
`
`1 5
`
`20
`
`2 5
`
`UMN_0000028
`
`
`Page 9 of 41
`
`

`

`5
`
`5
`
`1 0
`
`1 5
`
`2 0
`
`2 5
`
`PRML systems reveals that this is also a critical error pattern in high order PRML
`systems such as E2PR4ML. Note that the (1,k ) RLL code eliminates all four
`transition patterns shown in Fig. 1, but the rate penalty is typically too large to see
`
`any coding gain unless the user density is very high. The idea of MTR coding is to
`eliminate all sequences with three or more consecutive transitions, but allow the
`dibit pattern in the recorded sequence. Thus, with MTR coding, the two dominant
`error events will still be prevented as with (1,k ) coding, but the required code rate is
`much better than that of the typical (1,/c ) RLL code.
`
`Fig. 2 shows the sta_te diagram of the MTR code based on the NRZI
`recording convention, where 1 and O represent the presence and absence,
`respectively, of a magnetic transition. Also included is the usual k -constraint for
`timing recovery. The capacity of the code can be obtained by finding the largest
`eigenvalue of the adjacency matrix for the given state diagram. The capacities for
`different k constraints are given in Fig. 3.
`While state-dependent encoders and sliding block decoders can be
`designed for the MTR constraint, we observe that simple fixed-length block codes
`can be realized with good rates and reasonable le values. A computer search is
`utilized to find the 2m n -bit codewords required to implement a rate min block
`code. First, all binary words that contain the NRZI string of "111" or more thank
`consecutive NRZI "O"s are removed from the list of 2111 n -bit binary words. Then, in
`order to meet the MTR constraint at the codeword boundaries, words that start or
`end with a "11" string are removed. Also, the k constraint is satisfied at the
`boundary by removing the words with k1+1 leading O's or kz+l trailing O's where
`k1+k2=k. Fig. 4 shows code parameters for representative block codes obtained
`through computer search for various combinations of n and k. The efficiency was
`found by dividing the code rate min by the capacity computed for the given value
`of k and the MTR constraint.
`As an example of a MTR block code, the rate 4/5, MTR=2;k=8 block code is
`given in Fig. 5. The pairing of user data blocks and codewords were chosen so that
`
`UMN_0000029
`
`
`Page 10 of 41
`
`

`

`6
`
`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 optimal
`in terms of minimizing the logic implementation. Note that the k=8 constraint
`comes into effect when the codewords 10000 00001 occur in sequence. If the user
`data and codeword pairs are represented by
`
`X3X2x1xo H y4y3y2y1,
`then the equations for the encoder are:
`
`yo= xox1+xox2.\:3+xox2x3
`
`Y1 =xux1x2+X7XjX3+XiY2X3
`yz= Xz
`y F Y1x3+ xox2x3
`
`y4= XoX-1X-2X3+XoX1+X1X2X3
`The corresponding decoder is
`xo= Yo+yz Y4
`x1= Yo+yo y4+y2 Y1
`X2= Y2
`X3= y3+y1 V2 y4+y1 y2 Y4
`
`Two-level NAND logic implementations of the above equations are
`shown in Fig. 6a and Fig. 6b, respectively. These logic rules are representative of
`those that could be developed for any of the MTR codes using inclustry standard
`design packages. Fig. 7 shows a qecimal representation of 282 valid codewords to
`implement an 8/10 MTR block code. Extra codewords can be used as alternates.
`
`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 the trellis diagram. For the FDTS/DF
`detector, the code-violating lookahead paths must be prevented from being chose as
`
`5
`
`1 0
`
`1 5
`
`2 0
`
`25
`
`UMN_0000030
`
`
`Page 11 of 41
`
`

`

`7
`
`the most-likely path, a technique similar to the one used in the (1,7) coded FDTS/DF
`
`channel. To illustrate the idea, consider Fig. 8 that shows a ,::;;;3 lookahead tree
`
`utilized in FDTS/DF detection. The shaded paths in the tree correspond to the input
`
`data patterns with three consecutive transitions, and, thus, should be considered
`
`5
`
`illegal. For the -r=2 tree shown in Fig. Sb, 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. J. Brickner and J. Moon, "A high dimensional signal space implementation of
`FDTS/DF," presented at Intermag '96, Seattle, Washington, April 1996. For a more
`detailed desoiption of FDTS/DF detection, see J. Moon and L. R. Carley, "Apparatus
`and method for fixed delay tree search," U.S. Patent 5,136,593, 1992.
`
`With this modification in FDTS/DF detection, the squared minimum
`Euclidean distance between any two diverging paths, denoted by /J min, is given by
`1 + fr2+ f 22+ ... +f 12 for,: greater than or equal to 1, where fk represents the equalized
`dibit response (at the output of the forward equalizer). For example, the effective
`
`SNR gain of the t==2 FDTS/DF over the DFE, assuming the same MTR code, is given
`
`by 10 log 10(1+h2+f22) 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 ±(2 - 2 2), the
`minimum distance for the E2PR4 response (120 - 2 - 11 is 6✓2. With MTR coding,
`the worst case error pattern becomes a single bit error pattern of ±{2}, and the
`corresponding channel output distance is :;imply the square root of the energy in the
`
`1 0
`
`1 5
`
`2 0
`
`equalized dibit response, or 2✓ 10. 'This increase in the minimum distance is
`
`2 5
`
`equivalent to an SNR gain of 4.47 dB. If the code rate penalty is small, the overall
`
`coding gain would be significant.
`
`UMN_0000031
`
`
`Page 12 of 41
`
`

`

`8
`
`5
`
`1 5
`
`DC-Free MTR Codes
`Other useful constraints can be imposed on the MTR code at the expense
`of lowering the code rate. There exist storage systems where the recorded square
`waveform can not 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 l's over O's in the bina1y sequence up to that time, assuming the NRZ
`recording format is used (a negative RDS means there has been more O's than l's).
`1 0 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 "0101" or "1010" as well as any words that contain
`mote than (k+ 1) consecutive like symbols. Then, to satisfy the MTR constraint at
`the codeword boundaries, remove all words that start with "01" or "10" and remove
`all words that end with "101" or "010". The same effect can be achieved by
`removing all words that end with 01 or 10 as well as the words that start with "101"
`or "010". The k constraint can be salisfied al boundaries by eliminaling all words
`that either start with k1 consecutive like symbols or end with k2 consecutive like
`symbols, where k1 and k2 are preselected numbers such that k1 +k2=k+ 1. The
`remaining codewords in the list now satisfy the MTR constraint as well as the k
`Investigation of the remaining codewords reveals that for every
`constraint.
`codeword, there exists another codeword which is a bit-by-bit complement of the
`first codeword. Let us now define charge C to be the number of l's in the codeword
`minus the number of O's in the same codeword. If a codeword has a charge C, its bit-
`2 5 wise complement will have a charge-~. This property is used to design a DC-free
`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
`
`2 0
`
`UMN_0000032
`
`
`Page 13 of 41
`
`

`

`9
`
`mapping is 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. Fig. 9 shows a decimal
`representation of codewords corresponding to different values of C for the 8/12 DC(cid:173)
`free MTR code. the k-constraint in this case is equal to 8. Fig. 10 lists the code
`parameters for various DC-free MTR block codes obtained using the method
`described above.
`
`5
`
`UMN_0000033
`
`
`Page 14 of 41
`
`

`

`1 0
`
`What is claimed is:
`
`2
`3
`4
`
`5
`
`6
`
`7
`8
`
`9
`1 0
`11
`
`A storage system implemented device for encoding m -bit binary dataword
`1.
`into 11 -bit bi11ary codewords, where m and n are positive mtegers and 11
`is greater
`
`than m , the device comprising:
`
`receiver means for receiving the datawords;
`
`encoder means for producing sequences of the codewords;
`recorder means for recording said sequences of the codewords on
`
`the storage system; and
`said encoder means having a communication with said receiver
`
`and said recorder.
`
`The device according to claim 1 wherein, said encoder means produces
`2.
`said sequences of the codewords such that no more than j consecutive transitions
`2
`and no more than k consecutive transitions are generated in the recorded square
`3
`4 waveform where j and k are integers at least greater than 2.
`
`3.
`
`The device according to claim 1 wherein, said sequences of codewords
`
`relate to a limitation on j consecutive ones and k consecutive zeros when the
`recording is based on a Kon-Return-to-Zero-Inversion (NRZI) format.
`
`The device accordini:; to clann 1 wherein, said sequences of codewords
`4.
`relate to a limitation of no more than j consecutive transitions from one to zero and
`
`from zero to one and no more than (k+ 1) consecutive zeros and (k+ 1) consecutive
`ones when the recording is based on a non-return-to-zero (NRZ) format.
`
`2
`3
`
`2
`
`3
`4
`
`UMN_0000034
`
`
`Page 15 of 41
`
`

`

`11
`
`. 1
`2
`
`3
`
`4
`5
`
`6
`7
`8
`
`9
`1 0
`1 1
`1 2
`1 3
`1 4
`1 5
`
`2
`
`3
`
`2
`
`1
`2
`3
`4
`
`5
`
`The device according to claim 1 wherein the encoder means produces a
`5.
`codeword in response to the datawords, said codeword relating sequentially to
`individual datawords, in said datawords and further includes the device
`
`implemented steps of:
`setting a word-by-word mapping of 2m m -bit datawords to 2m n -
`
`bit codewords; and
`preselecting valid codewords including the steps of:
`removing binary words which comprise more than j
`
`consecutive ones or more than k consecutive zeros from a list of 2" n -bit
`
`possible binary words to form a list;
`
`removing words having one of a start and end with two
`
`consecutive ones from said list;
`removing words having one of a start with k1 consecutive zeros
`and end with k2 consecutive zeros; and
`selecting said valid codewords residing in said list.
`
`The device according to claim 5 wherein, said step of removing words
`6.
`having one of a start with k1 and end with k2 consecutive zeros further includes
`selecting k1 and k2 integers related in a manner to yield k1+k2=k.
`
`The device according to claim 1 wherein the sequences of codewords
`7.
`complies with a DC-free constraint.
`
`8.
`
`The device according to claim S wherein, said step of preselecting valid
`
`codewords further includes the steps of:
`removing all binary words that contain one of 0101 and 1010 and
`
`any words containing more than (k+l) consecutive like symbols from a
`
`list of 211 n -bit binary words;
`
`UMN_0000035
`
`
`Page 16 of 41
`
`

`

`1 2
`
`6
`
`.7
`8
`
`9
`
`1 0
`1 1
`
`removing all words that start with one of 01 and 10 including
`those that end with one of 1010 and 010;
`removing all words that start with one of k1 consecutive like
`symbols and end with k2 consecutive like symbols; and
`removing one of all codewords with negative charges and all
`
`codewords with positive charges.
`
`The device according to claim 8 wherein, said step of removing all binary
`9.
`2 words is replaced by a step of removing all words which end with one of 01 or 10
`and words which start with one of 101 and 010.
`3
`
`A storage system implemented device for encoding m -bit binary
`10.
`datawords into n -bit binary codewords, where m and n are positive integers and n
`
`is greater than m , the device comprising:
`receiving means for receiving data words;
`decoder means for decoding the n -bit codewords into m -bit
`datawords;
`encoder means for producing sequences of the codewords;
`recorder means for recording said sequences of the codewords on
`
`the storage system;
`said decoder means, said encoder means and said recorder
`means being in communication with said receiver means.
`
`A device implemented method for encoding m -bit binary data words into
`11.
`n -bit codewords, where m and n are positive integers and n is greater than 111
`to
`thereby store data in a storage system, comprising the device implemented steps of:
`receiving the datawords;
`producing sequences of codewords; and
`recording said sequences or codewords on to the storage system.
`
`2
`
`3
`4
`
`5
`6
`7
`
`8
`
`9
`1 0
`1 1
`
`2
`3
`4
`5
`6
`
`UMN_0000036
`
`
`Page 17 of 41
`
`

`

`1 3
`
`The device implemented method of claim·u wherein, said steps of
`12.
`producing sequences of codewords includes generating no more than j consecutive
`2
`transitions and no more than k consecutive non-transitions in a recorded square
`3
`4 waveform where j and k are integers greater than 2.
`
`The device implemented method of claim 11 wherein, the sequences of
`13.
`codewords have no more than j consecutive one and no more than k consecutive
`zeros when used in conjunction. with an NRZI recording format.
`
`I
`
`2
`
`3
`
`The device implemented method of claim 11 wherein, one of a fixed tree
`14.
`search detector and a signal space formulation is used to prime lookahead paths
`2
`3 which violate MTR code constraints in a decision tree.
`
`UMN_0000037
`
`
`Page 18 of 41
`
`

`

`03--28-1996 16:36
`
`612' '":4583
`
`u of 11 Elec Er
`
`P. l2
`
`bO 014954
`
`Fig. l
`
`Fig.2
`
`UMN_0000038
`
`
`Page 19 of 41
`
`

`

`03-2e-1sss 1s,3s
`
`U oi H Ell'O Er
`
`P.13
`
`bO 014954
`
`c.r-~-•
`MTR4:k-
`Mlllol:MO
`Mlll""WI
`Mnl>olJ("'l
`M'TIO•l:1-7.
`M1ll"3.f.l:-S
`M!ll-2;~
`
`_2,;.,
`
`MTIW:1-J
`
`CHldh,
`0.1711
`tl.!711
`0.!'174
`0,1710
`01"1
`o.m"
`o.1,1p
`04!ll
`0.,9,t7
`
`Fig.3
`
`UMN_0000039
`
`
`Page 20 of 41
`
`

`

`03-28-1996 16:36
`
`6121>~54583
`
`u of H Elee Er,"
`
`?. 14
`
`.. • . reu •UhhllY l!rd1ah1A h11\11ra4
`•
`a.!l!IQO
`•
`0.!QOO
`o, ,oo~
`'
`0.000
`'
`0.6000
`'
`•
`0.(QOO
`0,,000
`0.11000
`'
`o.un
`. ,, . D,UU
`o.,,n
`I
`D.Uf7
`o.,,~.,
`e
`'
`'
`• I
`O,H6'
`o.,u1
`7 A ' o.nn
`7 • ' 0,11U
`7 • ' o.uu
`1 7 ' 0,'1U3
`1 e • o.,1n
`, • ~ •. ,111
`7 10 • D.'1&J
`0 • • 0,,,00,
`• ' • 0,1500
`• • • 0,T5DO
`• 1 ' 0,,,-00
`• • • 0,1500
`I 10 • 0,7'00
`' • ' o.u:n
`l , 11,,,,,.
`' 1 , b.1'1111
`' ' ' 11.,.,,,
`' I , a.111e
`I IO , O,i'JU
`t ' 0.?1'78
`10 ' , 0, 'JQCO
`10 ' • 0,11000
`" ' • 0,.000
`" • ' D,1000
`l ' IJ,1000
`I • o. 711]
`11 • ' 0.7)73
`11 • ' 0,0182
`7 • 0,111:1
`11
`' • 0,0111il
`a
`' I
`n
`Cl ,1112
`I o,nu
`u • ' 0. 7500
`11 111
`12 ' t 0,7!00
`' ' D,'7100
`ll 1 ' o.,,oa
`" P 10 O,llll
`" , .. o,n,.a
`lD U:,
`,.
`0.(1)3),
`'10 o.nn
`1,
`' 10 O.HH
`I 10 o.Hta
`ll 0 lD 0,'1'U
`1' 9 10 o,n:u
`ll 10 ll D,.IIU:1
`• l1 o.,u,
`• l1 o.,.~,
`1(
`,.
`' 1l 0.,.,1
`1<
`,.u o.,n1
`u
`11 •a 0,7'57
`u
`iU 0,18!17
`1, •a o,n,u
`14 lO 11 0,?DS'J
`" l "
`" , " 0,10110
`
`I
`I
`
`5
`
`I
`
`I
`
`I 0,'15DD
`
`I
`
`I
`
`10
`
`I 7 0.,000
`
`10
`111 10
`11
`
`I 0,!!000
`
`I 10 0,11)1
`
`J>
`
`1)
`
`U
`1S
`
`0,1000
`1,
`0,IIDDD
`0 "
`1, ? i l o,enDo
`I 12. IL.11(100
`1!
`
`1, . " n.e12s
`
`.LO 11 Cl,iOOP
`1!1
`)I ' i i 0.'751:10
`u Ill D,ll.2~
`7 ll o,un
`H
`u 111 D,OU5
`" I ll 0.11H
`U 111 13
`0,.1.!Ul:5
`
`'·""
`
`O,llO
`0,!UI
`0.100
`o.,u1
`o.uu
`o.,n1
`a.nu
`o-,,u;
`o.nn
`0.100
`o,,u,
`0,,,11
`0,?SU
`0.15U
`11,!l!l.,
`0,1111
`0.1n,
`O,IUCI
`0.11,4
`0,e1u
`o.nu
`D,UH
`o.nu
`0,IUD
`0.1:sn
`O.Cll2
`D,UUJ
`D,U&0
`O,?UJ
`o,sou
`o.o,o
`D.007
`o,u,,
`o.nu
`,.m•
`0,1856
`Cl,U!it
`o.,:iu
`O,J1U
`1;1,nn
`o.un
`O,UOJ
`a.u,:a
`o,u,7-,
`0,'421
`o.u,o
`o.,Ho
`0,UH
`11.UU
`O.l!BI
`0. ,.,.,,~
`o.uo
`o.m,
`O.HlJ
`o.uu
`,.,m
`o.un
`11,nu
`Q,UU
`O,IIIC'J
`o.nu
`o.no
`O, U),
`i), '1£0
`0.'3.S'1
`o.tou
`o.nu
`o.o,n
`0,0!15
`Cl,8'17
`0,IH~
`0,13)!
`C.t::IU
`ri.,u1
`0.)1:JJ
`o,a,u,,
`o.uc,
`,.m,
`Q,,cn
`o.,uo
`C,UD5
`0.11)75
`o.u,o
`Q.n,3
`
`1
`8
`ll
`l!
`II
`
`11
`
`21
`
`1'
`e,
`
`IT
`100
`11,
`1)1
`
`10
`Ill
`177
`
`"'
`20,
`a.,
`31!
`Ill
`IH
`
`,,
`"
`"
`.,
`,.
`"
`..
`"
`u
`.,
`,1
`,2
`>)
`..
`"
`••
`"
`,,.
`.. ,
`.. ,
`'"
`'"
`n,
`...
`'"
`S80
`,u
`"'
`'1l
`'"
`
`1001
`1.0,,
`lll,
`:U,U
`Un
`U.'11
`1,713
`1110
`u5,
`:ai,
`20')4
`l12~
`
`'"'
`
`!U4
`JUJ
`HtO
`1,05
`Ulil
`lH:.I
`UH
`5'701
`n,f
`s:,n
`UO?
`7010
`t:'111
`a,u
`lOiOJ
`lUU
`uo,D
`1UOJ
`UtU
`
`•--- lletd1WC1"41 .......
`
`bO 01,\954
`
`U112
`l!!OJ-'I
`l.119!16
`:a.o,2;i
`lll88
`22:,n
`UUli
`21.Ut
`an,
`J,,10
`JUdO
`•O'l'~O
`4l30:I
`on,
`Heu
`,au
`,u,o11
`0279
`,,,u
`
`11
`I 17 0.110'5
`ll I ll Cl.110,S
`'1 lo U
`0,11!-'ll
`
`l.:I 10 11, 0,8112
`
`i:5 10l1 11,HOO
`
`)1 10 23 C,Ul.SI
`
`O.UH
`
`f "
`
`~e 1C H
`
`0,0'11
`
`°""' uu,au u,n.2u
`
`l1 . " a.un
`...t.. 1otCLciilacty
`uioo.,"·nl• ___ ,.
`-
`A • ~
`•••ULb.l.a HCJUiUd,
`,, '13 o.,«41
`ain
`D.llH
`o.uu
`81!)2
`1nu
`17
`'11 O.llll
`0,90'1
`u,u
`'
`o e:u,
`11
`0.$01
`•
`l7 ,u o.,u~
`7 "
`0,Jill(ll
`113111.
`'
`I 1, o,e:aJs
`•
`O,tJIII
`l7
`1U'4,
`D,'3'17
`17 10 ~' 0,02:!5
`100111
`11 ,u o. 1'18
`"
`0, 1115
`1')U
`11 '" 0,n,1
`18 •u O,Ull
`ll,tDU
`lUBI
`"
`" I< , " 0,!Hl
`o.uoo
`-J2"'16!!
`a.nu
`l:1'7611
`"
`lO e 1s 0,!IH
`H'He
`0,S.Hl
`c.u,,
`u
`t lS 0,1)>)
`la'rU
`ll lO U. 0,6));)
`a.9UJ
`lJ . " o.•01
`l2HG
`u
`4 I! 0,1U5
`C,,.25
`321'8
`1, 5 1' c.,us
`o.uo.:
`U"a
`a G 11 O,inS
`(l.!10115
`.hH~
`" 1 II c,u:n
`0.S'U4
`&l'15
`u p" a,u21
`C,,j\£1)
`(i,5~ 5
`O.HU
`<!lli
`17S2!'il
`,,
`B LOH O,i01
`0,950
`IIOC2d
`6S!ill
`~'
`"
`6Stu
`D,UU
`0 ll 0.600"
`013::1
`" ' " O.DOOD
`..
`D.SJJ,
`i,!lu
`'45B
`..
`"
`20 611 O,IIODO·
`HHn
`0,9215
`l!!H
`" " '1! 0,B000
`uHo
`0 9lCl
`'-''lG
`,o ,n 0,1500
`..
`u 1 ul
`u10,~
`0.,10)
`..
`" • i, 0,115110
`c..un
`1'242'
`BlOU
`:u lO 1, o.uoo
`"
`0,HH
`u,0,2
`1)]072
`" l U
`o,,oH
`0,7UP
`lH,48
`O!1J6
`n
`! 11 0,80,,
`O,UH
`JHJU
`1l~O?.I
`o.,n,
`"'
`ll I 1' 0,80!H
`u10,2
`21D'HO
`"' " 71, 0,10!5
`o.u.,o
`ll10'2
`~)HOJI
`a.uu
`.1sl.,oa
`HI
`1HO't~
`o.,u2,
`128
`uui:~ti
`lllO'J:11
`121
`~6=1u
`il,0:1,0
`I:> SHiO
`" • 17 0,7131
`l>I
`"' " ' ,. 0,$]8jl
`O.H2,
`lJ07H
`Ul.07l
`o.:an
`,, ? 18 O,UB2
`201'4
`llO(ijJ
`,.em
`" I 11
`la&
`0.!42'
`21'ilU.4
`"' " . ,, 0.1:an
`)U.121
`lSI
`UHU
`Cl.ll'Hl
`U:!1U
`,, ' ,. 0.111,2
`23 . " 0,78:U
`" I 18 0.11112
`,si
`H.al.h
`0,9-3410
`,u
`UU4,
`u.:u,
`o,,lU
`,.,
`.2~214'
`.. ' " Cl,lliUil
`l5C
`D.JlH
`06J'JO
`H:ll44
`o,,Hl
`2'2ll,1
`3i14!iU
`o.nu
`., . " IL~.2U
`!.:11120
`":1'1)2
`,a~a0
`'"
`IJ,!l'17
`a . " ~,7'17
`• 5211)18.
`2J. 7 U D,UH
`,Hlll
`0,!IUO,
`792.!IH
`n a 11 O,IHl
`"'
`n,,u
`~:u1u
`(l,&d:U
`o.u:.,
`Ul007
`!>:141U
`o.,4o(i
`U 10 lJ o.nu
`"'
`H)4U
`5.lUBI
`O.H>I
`ll>
`70'1'8
`lU)(I
`m
`l 19 o. m,
`10u,en
`II
`•• ,121
`!l4lll
`21 . ,. 0,!1000
`" I 20 0,l)ll
`512
`0.UOO
`1:tll!III&
`)OlU'1'
`'" " 1 lO c,nH
`tl,IISO
`10:USI
`100'16
`2, ' ,. o.m,
`H 8 lO O,IJ)J
`3ll
`0,J!r:l.l
`l5l1Hl
`1t1Ul!S7fi
`1024
`O,tOi Hlll2l
`1CIU57'
`uu
`,,
`:U 10 jlD a.nu
`Q,UIU
`10U57fi
`H7J081
`o,u,1
`lDU
`l.H0.2i,
`.l.018571
`o.n:u·
`1024
`' " D.&000
`)UUU
`J.0415711:
`" ' 11 0.H00
`.2,uou
`lDU
`O.U'1'1
`3051'1:.~a-
`" 'u D.uoo
`,, I 21 o.uo.o
`c.uu
`:ua,u~
`.OH
`26'.JiHH
`" iU o.uoo,
`o.nu
`L0%4
`2n!,tU
`lOt'1J2
`1.0H
`)o,,l~:l
`O.M'7l
`HGD3RA
`0.,su
`UH
`::u,"
`HIHilH
`20H~!i2
`" • ll o.,on
`o.,u.,
`" • 21 o.,o,,
`O,UO
`lo,11~J
`2'2521!11
`)na1n
`HU
`20,,u::i
`,, I ZZ a,e,o
`" I 2l e-,acu
`2018
`1201n U:UJD4
`1;1,5'7U
`i6 ' " o.u,l
`Jo,,
`1041
`0,JUD
`4811<11
`U,CJO•
`,uuo,
`O,IIH
`" . " o.uo
`·5.:l&DU1
`mo
`21
`I 22 O.HU
`lO,-lU
`C,Pll4l
`4HOO-l
`ill 10 2J o.u~,g
`101&
`0,905
`!~7)01'
`tHUO&
`I ,i o.n,,
`o.u.0,
`•o;a.us,
`20n
`11
`aOJ'71!~
`.. c,,
`j1D4f
`01115& HU]of,
`O.POI
`" ' " o.t110
`" . ,, Cl.1057
`O.U6.,
`77'1JlilJ
`411Ui0'
`" I II o,e,u
`Cl,975.!
`11113'0
`831UO&
`.. . " o.ni,
`1' ' " 11.nu
`a.nu
`fU.'f.!JO!l
`8'J88'M
`" ' " Cl,Ua
`100!801 BJ6U0t
`D.97011
`o .~7b0-
`nsu0e
`l007C0,1
`,.
`O,BIIIO
`7).UH:1 UH)~4
`O.H,,
`1:1004'51
`UIIIUOG
`•• , " 0,121'
`,. • 2t o.un.
`o.&.UJ
`8Hel!IOD
`1.f.2U311i
`Cl,51,D'J H1U9!l
`tllH!iO!I
`,. 'H o.en1
`~.,111:i
`li,!04,0
`lfil712.U
`o.nu
`lt'71U72 U:7'7?:111
`
`l
`I
`
`1'
`
`II
`11
`II
`ll
`ll
`ll
`ll
`!)
`l2
`
`,i,
`
`Ill
`
`OU
`4Cl'6
`tOtli
`40!6
`IOU
`tOU
`ea~
`IUJ
`u.n
`!1'1
`111S)
`aua
`
`Fig. 4
`
`L----------------