I
`
`&Seagate
`Annual Report
`
`Barrett Brickner and J aekyun Moon
`
`September 26, 1995
`
`University of Minnesota
`CENTER FOR MICROMAGNETICS AND INFORMATION TECHNOLOGIES
`
`UMN EXHIBIT 2025
`LSI Corp. et al. v. Regents of Univ. of Minn.
`IPR2017-01068
`
`
`Page 1 of 19
`
`

`

`Seagate Annual Report
`
`2
`
`1 Introduction
`Various detection schemes for a linear channel corrupted with additive white Gaussian noise
`(A WGN) were studied. Except where noted, the simulations and analysis were performed using
`an actual magnetoresistive (MR) head response. The focus of the research was on the use of
`fixed-delay tree search with decision feedback (FDTS/DF) with (O,k) run length limited (RLL)
`codes. The performance of FDTS/DF is compared to a partial response maximum likelihood
`(PRML) detector and the optimum detector, maximum likelihood sequence detection (MLSD).
`Alternate formulations of the FDTS detector, based on a signal space representation, are
`presented. Finally, a new coding technique, which can be used either to reduce detector
`complexity or improve margin, is discussed.
`
`2 Channel Model
`The channel model used for all .the work presented is linear with additive white gaussian
`no_ise. A block diagram for the channel/detector is shown in Figure 1. The write current samples
`are a,..., hn is the sampled, filtered step response, nk are the AWGN samples, en is the forward
`.equalizer, and bn is the feedback filter. For a PRML detector, then bn block is not included. The
`value 7 is the delay of the detector and the depth of a FDTS structure.
`
`ak
`- - - ' l l)lo(cid:141)
`
`I 1-D
`
`n
`
`X k .---------.
`- - detector
`
`a k-i-
`
`Figure 1. Channel model and detector block diagram
`
`The sampled transition response is shown in Figure 2. The magnitude spectrum of the reponse,
`prior to processing by the anti-aliasing low pass filter, is shown in Figure 3. The equalizers were
`optimized at each SNR point before measuring the bit error rate (BER). ·The optimization
`criterion was minimum mean square enor (MMSE). The effects of equalizer length were not
`considered. A sufficiently large number of taps ( 41 for the forward equalizer and 21 for the
`feedback filter) was used so that the filter lengths would not degrade the detector performance.
`
`3 Detector Distance Properties
`The performance of a detection scheme is dominated by the pair of symbols that are
`closest to each other in Euclidean distance. For an error to occur, the amount of noise that must
`be added is half of this distance. Because the noise amplitude is assumed to be Gaussian
`distributed, a _small increase in distance can greatly reduce the probability of an error.
`
`B. Brickner, J. Moon
`
`University of Minnesota
`
`September 26, 1995
`
`
`Page 2 of 19
`
`

`

`I
`
`Seagate Annual Report
`
`0.9
`
`0.8
`
`0.7
`
`0.6
`
`0.5
`
`0.4
`
`0.3
`
`0.2
`
`0.1
`
`0
`
`l
`
`/
`
`t
`\..
`
`-0.1
`-30
`
`-20
`
`-1 0
`
`0
`Scmplo Number
`
`10
`
`20
`
`30
`
`10•
`
`'
`
`10- J
`0
`
`3
`
`-
`
`I
`'\.
`\I
`
`I
`I
`
`I
`
`I
`
`I
`
`'
`
`I
`
`I
`
`\ ,~
`
`!
`
`\ /"'-
`
`I
`
`\
`
`I
`
`I
`
`I A j -
`
`' f
`
`4
`
`5
`
`' i
`
`,
`
`8,
`
`10
`
`F"re~u• ncy n-armaliza:d to 1/ (2t>FW50)
`
`Figure 2. Sampled, filtered transition response
`
`Figure 3. Spectrum of an unfiltered transition
`
`3.1 Maximum Likelihood Sequence Detection
`Maximum Likelihood Sequence Detection (MLSD) yields the optimum detector
`performance for a linear channel with AWGN. Although implementing an unconstrained MLSD
`in a commercial disk drive is not economically feasible, it is useful as an absolute performance
`. bound against which other detection schemes may be compared. The distance between the two
`closest sequences is denoted by dmiw The performance of the MLSD detector is approximately
`
`P MLSo(e) " K ·Q [ ~:']
`
`(1)
`
`where Q(-) is the complementary distribution function for a Gaussian distribution, a is the square
`root of the noise power at the output of the forward equalizer, and K as a constant independent
`of d"';,,-
`
`The minimum distance can be bounded with_ the following [1]
`
`MIN t [ t b/k-J] 2 ':$; d~0
`
`k=O
`
`J=O
`
`{ }L
`~o
`
`:::; MIN f [ t b1ek-J] 2
`
`{ }L
`~o
`
`k=O
`
`J=O
`
`(2)
`
`where {bn; n=l, ... ,J} are the feedback filter coefficients and ba=I. The term b0=1 is a result of
`training the equalizers for a DFE; i.e., for ideal operation, the samples at the input to a DFE are
`±ha, The error sequence of length L+l, {ek} is taken to be all possible error sequences where
`ea= ±2, and all other ek are O or ±2. This assumes that the desired data sequence is taken from
`ak = ±1 so that the differences are in {±2,0}. These upper and lower bounds represent non(cid:173)
`increasing and non-decreasing functions, respectively, of the error length L. These bounds wi11
`converge as L (cid:157)
`co. The bounds, as a function of L, for the case where the user density is
`Du = 2.5 are shown in Figure 4.
`
`B. Brickner, J. Moon
`
`University of Minnesota
`
`September 26, 1995
`
`
`Page 3 of 19
`
`

`

`Seagate Annual Report
`
`3.2 ~I
`
`\
`\
`
`µppet B4'd
`
`I
`
`3.0
`
`2.8
`
`C ·e 2.s
`,,
`
`2.4
`
`2.2
`
`2.0
`0
`
`c..--V
`
`/
`
`-
`
`I
`
`1
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`L--l--i.---
`/Lovier Bb\Xld
`
`I
`
`9
`
`10 11 12 1.3
`
`L
`Figure 4. Bounding of dmin for D u = 2.5
`
`4
`
`V v
`
`/ V
`
`i.-V
`
`/
`
`7
`6
`5
`Tree Oeplh
`
`8
`
`9
`
`10
`
`11
`
`12
`
`0.0
`
`-0.5
`
`!
`i-1.0
`.,,
`
`~ - 1.5
`
`I 0
`
`-2.0
`
`~
`
`-2.5
`0
`
`1
`
`---
`/
`I
`I
`
`2
`
`3
`
`4
`
`Figure 5. FDTS/DF Minimum Distance (/3,.,n)
`
`As shown, the upper bound rapidly converges to dm;11 while the lower bound approaches
`more slowly. The rapid convergence of the upper bound is explained by noting that for L ~ 2,
`the minimum distance error sequence determined by the upper bound was e = ±( -2, + 2,-2). Thus,
`when L = 2, the upper bound will be evaluated for this minimum distance event. Assuming that
`an event with a smaller distance does not exist beyond the range of L that was examined, there
`will be no decrease in the upper bound, because the minimum error event will already have been
`accounted for. It has been shown that at high densities, the minimum distance error sequence is
`of the form em;11 = ±(-2,+2,-2), a result which agrees with Figure 4 (2].
`
`3.2 Fixed Delay Tree Search
`A measure of performance similar to dm;11 exists for FDTS/DF. In the case of the tree
`search, the quantity of interest is the distance between the pair of conflicting symbols with the
`smallest Euclidean distance. This value, termed fimin is determined by [3]
`
`(3)
`
`Notice that this is the same as the lower bound in (2). Thus, the minimum distance in FDTS/DF
`is a non-decreasing function of the depth r. Note that because fim,,, is the lower bound for d
`the performance ofFDTS/DF must converge to the MLSD bound. This distance (in dB) from dmin
`is shown as a function of Tin Figure 5. The only question remaining is how large the tree depth
`should be. This criterion is still dominated by the need to balance complexity against
`performance, but the distance properties provide some assistance in choosing a depth. For
`.
`.
`example, there is less incentive to increase the complexity from depth r= 1 to r-2, but increasing
`from r-2 to ;=3 results in a noticeable improvement for this particular channel.
`
`;
`111
`
`11
`
`,
`
`B. Brickner, J. Moon
`
`University of Minnesota
`
`September"26, 1995
`
`
`Page 4 of 19
`
`

`

`r
`
`Seagate Annual Report
`
`5
`
`4 Coding to Improve Signal Margin
`The bit error rate (BER) performance of optimal and suboptimal sequence estimators in
`an additive white Gaussian noise (A WGN) channel is dominated by the Euclidean distance
`between the two closest, conflicting sequences. For MLSD, it h·as been shown that at high data
`densities, the error rate performance is dominated by the error sequence e = ±(-2,+2,-2), where
`e is the difference between two valid sequences. An examination of the error sequences that
`correspond to /3,,,;n for FDTS/DF show that the most likely error sequence consists of three or
`more consecutive non-zero values in the error sequence. The Euclidean distance between the
`various conflicting sequences in the tree search indicates that eliminating error sequences
`containing ±( ... ,-2,+f,·2, ... ) will yield a significant improvement in distance.
`
`4.1 Coding Objective
`two pairs of
`the
`Figure 6 shows
`conflicting patterns that can cause the error
`sequence e = ±(-2,+2,-2). The sequences shown
`are non-return-to-zero (NRZ) sequences, which
`correspond to the write current waveform in a
`magnetic recording system. One or both of the
`conflicting patterns can be eliminated by requiring
`that the valid sequences contain no more than two
`consecutive transitions. A transition corresponds
`to a change in the level of the NRZ sequence.
`
`0, 0, 0, -2,+2,-2, 0, 0, 0
`
`--------n-......-..-_____,_____
`
`Figure 6. Sequence~ that cause e=±(-2,+2,-2).
`
`4.2 Maximum Transition Run Coding
`In order to increase the minimum sequence distance, a new class of codes, designated
`maximum transition run (MTR) codes, is introduce. These codes limit the number of consecutive
`transitions that can occur in a recorded sequence. As noted before, eliminating three or more
`consecutive transitions results in a significant increase in minimum distance. Therefore, the use
`of MTR=2;k codes is proposed for use in magnetic recording. The k constraint is the same as the
`k constraint used in RLL coding. The RLL d constraint for the MTR codes is d=O. If the written
`data is considered as an NRZI (non-return-to-zero inversion) sequence, where a 1 corresponds
`.to a change in the level of the corresponding NRZ sequence, and a O signifies no change, the
`MTR=2 constraint means that no more than two consecutive 1 'scan occur. For the remainder of
`this report, data and code words are assumed to be an NRZI representation.
`The properties of a MTR=2 code are discussed in the context of code design. The
`characteristics of several codes that could be readily applied to data storage are examined. The
`discussion will focus on block codes, in which there is a one-to-one mapping between an m-bit
`block of user bits and an n-bit codeword. More complex and efficient codes can be developed
`by using a state machine as the encoder. While the design techniques for these codes is beyond
`the scope of this paper, they can be applied to develop codes which incorporate the MTR
`constraint.
`
`B. Brickner, J. Moon
`
`University of Minnesota
`
`September 26, 1995
`
`
`Page 5 of 19
`
`

`

`r
`I
`
`Seagate Annual Report
`
`6
`
`0
`
`0
`
`4.3 Code Capacities
`A state diagram for a code that suppresses
`three or more consecutive transitions is shown in
`Figure 7. A sequence that meets the MTR=2
`constraint can be obtained by moving along the
`arrows connecting states and reading off the label
`above the arrow. This state diagram may be
`described algebraically with an adjacency matrix
`f
`A
`h
`1
`·
`b
`th
`, w ere e ement aiJ is
`e num er o arrows
`originating at state i and ending at state j. For the
`state machine in Figure 7, the adjacency :a~ix[i' ~ ~ ]
`
`Figure 7. State diagram for codes that suppress three
`consecutive transitions.
`
`The capacity (or upper bound on the code rate) is given by [4]
`
`1 0 0
`
`(4)
`
`(5)
`
`where fl.max is the largest eigenvalue of A. For the adjacency matrix given by (4), the capacity is
`C = 0.8791. The capacities for various codes is given in Table I.
`
`Table I. Capacities of MTR=2;k codes
`
`I
`
`I
`
`I
`
`Code Constraint
`
`MTR=2;k:::o:,
`
`MTR= 2;k=l0
`
`MTR=2;k=9
`
`MTR=2;k=8
`
`MTR=2;k=7
`
`MTR=2;k=6
`
`MTR=2;k=5
`
`MTR=2;k=4
`
`MTR=2;k=3
`
`Capacity
`
`0.8791
`
`0.8782
`
`0.8774
`
`0.8760
`
`0.8732
`
`0.8680
`
`0.8579
`
`0.8376
`
`0.7947
`
`B. Brickner, J. Moon
`
`University of Minnesota
`
`September 26, 1995
`
`
`Page 6 of 19
`
`

`

`I Seagate Annual Report
`
`7
`
`The capacity of the code limits the achievable code rate. A large code rate is important
`for two reasons. First, for a given rate of user bits, coding with a low code rate will require a
`larger channel bandwidth. Second, a low code rate translates to a larger symbol density on the
`storage medium, which results in increased intersymbol interference (ISI). The sample rate for
`a channel operating at a user data rate of 100 Mbit/sec is shown in Table II for several RLL and
`MTR codes. Note that all the MTR codes except the rate 12/14 code can be implemented as a
`block code.
`Table II. Sampling rates required to obtain 100 Mbit/sec
`
`I
`
`Code
`
`RLL (0,4/4)
`
`MTR=2;k=7
`
`MTR=2;k=7
`
`MTR=2;k=8
`
`MTR=2;k=6
`
`MTR=2;k=6
`
`MTR=2;k=8
`
`RLL (1,7)
`
`I
`
`Code Rate
`
`I
`
`Sample Rate
`
`I
`
`8/9
`
`12/14
`
`16/19
`
`10/12
`
`9/11
`
`8/10
`
`4/5
`
`2/3
`
`113 MS/s
`
`117 MS/s
`
`119 MS/s
`
`120 MS/s
`
`122 MS/s
`
`125 MS/s
`
`125 MS/s
`
`150 MS/s
`
`4.4 Block Code Design
`Given the MTR constraint and an RLL k constraint, a computer search can be used to find
`the 2n m-bit codewords required to implement a block code. In order to meet the k constraint at
`the boundaries, codewords with k1+ 1 leading O's or k2+ I trailing O's, where k1+k2=k, are removed
`from the search. When k is even, k1=k2=k/2; when k is odd, k1- l =k2 or kr 1 =k1• Valid block codes
`with an MTR=2 constraint are shown for various combinations of n and kin Table III. Efficiency
`is defined as the ratio of code rate to capacity.
`
`B. Brickner, J . Moon
`
`University of Minnesota
`
`September 26, 1995
`
`
`Page 7 of 19
`
`

`

`I Seagate Annual Report .
`
`Table m. Block codes with maximum transition run constraint: MTR=2;k
`
`8
`
`..
`- - cod.ewords - -
`rate efficiency available required
`n k
`---
`2 o.sooo
`2 0.5000
`4 ' 3 0.7S00
`
`4
`4
`
`4
`5
`
`' 4
`
`3 0.6000
`5
`4
`s s 3 0.6000
`s 6
`3 0.6000
`s 7
`3 0.6000
`5
`8
`4 0.8000
`4 0.6667
`6 s 4 0. 6667
`4 0.6667
`6
`6
`7
`0.6667
`6
`4
`6
`8
`4 0.6667
`0.6667
`6
`9
`4
`6 10 4 0. 6667
`5 0. 714 3
`7
`4
`7
`5
`5 0.7143
`7
`6
`5 0. 7143
`7
`7
`5 0.7143
`8
`7
`5 0. 7143
`7
`5 0. 7143
`9
`7 10 5 0.7143
`0 .7500
`4
`8
`6
`5
`6 0.7S00
`8
`8
`6 0.7500
`6
`8
`6 0.7S00
`7
`8
`8
`6 0.7S00
`6 0.7S00
`9
`8
`8 10 6 0.7500
`9
`6 0.6667
`4
`9
`5
`7 0. 7778
`6
`7 0. 7778
`9
`9
`7
`7 0. 7778
`8
`9
`7 0.7778
`9
`9
`7 0. 7778
`9 10 7 0.7778
`10
`7 0.7000
`4
`l~ s 7
`0 . 7000
`10
`6
`8 0.8000
`10 7
`8 0.8000
`10 8
`8 0.8000
`10 9
`8 0.8000
`10 10 8 0.8000
`11 4
`8 0.7273
`8 0. 7273
`11 5
`9 0. 8182
`ll. 6
`11 7
`9 0.8182
`11 8
`9 0. 8182
`9 0.8182
`l l 9
`ll 1 0
`9 0.8182
`12
`9 0.7S00
`4
`12 s 9 0.7S00
`12 6
`9 0.7500
`12 7
`9 0.7500
`12 8 10 0.8333
`12 9 10 0.8333
`12 10 10 0.8333
`
`O.S969
`0.5828
`0.8640
`0. 7163
`0. 6994
`0. 6912
`0.6871
`0. 9133
`0.7959
`0. 7771
`0.7'80
`0. 7634
`0. 7611
`0.7598
`0.7591
`0.8527
`0.8326
`0.8229
`0.8180
`0.81S4
`0. 8141
`0.8133
`0 . 8954
`0.8742
`0. 864 0
`0.8S89
`0.8562
`0.8548
`0.8540
`0.7959
`0 . 9066
`0.8960
`0.8907
`0.8879
`0.8864
`0.8856
`0.83S7
`0.8159
`0.9216
`0.9161
`0. 9133
`0. 9117
`0.9109
`0. 8682
`0. 8477
`0. 942'
`0. 9370
`0.9340
`0.9325
`0.9316
`0.8954
`0,8742
`0. 864 0
`0.8S89
`0.9513
`0.9497
`0. 9489
`
`- - codewords - -
`rat:e efticiency available r e quired
`
`n k m
`- - -
`13 4 10 0.7692
`13 5 10 0. 7692
`13 6 10 0 .7692
`7 10 0.7692
`13
`13 8 10 0. 7692
`13 9 10 0.7692
`13 10 11 0. 8462
`14 4 l l 0. 7 857
`14 5 l l 0.7857
`14 6 11 0.7857
`14 7 11 0.7857
`14 8 11 0.7857
`14 9 l l 0.7857
`l4 10 ll 0.78S7
`15 4 l l 0.7333
`15 5 12 0.8000
`15 6 12 0.8000
`15 7 12 0.8000
`15 8 12 0 .8000
`15 9 12 0.8000
`15 10 12 0.8000
`16
`4 12 0.7500
`16 5 13 0 .8125
`16 6 13 0.8125
`16 7 13 0.8125
`16 8 l3 0.8125
`16 9 13 0.812S
`16 10 13 0 . 8125
`17 4 13 0.7647
`17 5 13 0. 764 7
`17 6 14 0.8235
`17 7 14 0.823S
`17 8 14 0.8235
`17 9 14 0.8235
`17 10 l4 0 .8235
`18 4 14 0. 7778
`0 . 7778
`18 5 14
`6 15 0.8333
`1 8
`18 7 15 0.8333
`18 8 15 0.8333
`18 9 15 0 .8333
`18 10 15 0.8333
`19 4 15 0.7895
`19 5 15 0 .7895
`19 6 15 0.7895
`19 7 l6 0 . 8421
`19 8 16 0.8421
`19 9 16 0. 94'21
`19 10 16 0. 8421
`20 4 16 0.8000
`20 5 16 0.8000
`20 6 16 0.8000
`20 7 16 0.8000
`20 8 17 0 . 8500
`20 9 17 0.8500
`20 10 17 0.8500
`
`0. 9183
`0.8966
`0.8862
`0.8809
`0.8781
`0.8767
`0. 9635
`0 . 9380
`0. 9159
`0.9052
`0.8998
`0.8970
`0.8955
`0.8947
`0.8755
`0.9325
`0. 9216
`0.9161
`0.9133
`0.9117
`0 . 9109
`0.8954
`0 . 9471
`0.9360
`0.9305
`0. 927S
`0.9260
`0. 9252
`0.9129
`0.8914
`0. 9487
`0. 9431
`0.9401
`0.9386
`0.9377
`0.9285
`0.9066
`0.9600
`0.9543
`0.9513
`0. 94 97
`0.9489
`0.9425
`0.9202
`0.9095
`0.9644
`0. 9613
`0.9597
`0.9589
`0 .9551
`0.9325
`0 .9216
`0. 9161
`0.9703
`0.9687
`0.9679
`
`1188
`1471
`1712
`1841
`19S6
`2017
`2074
`2122
`2667
`3124
`3372
`3590
`3705
`3814
`3792
`4834
`5702
`6176
`6588
`6807
`7010
`6778
`8760
`10408
`11313
`12090
`12505
`12886
`12112
`15877
`18996
`20723
`22188
`22972
`23686
`21646
`28776
`34670
`37960
`40720
`42202
`43536
`38684
`52153
`63278
`69534
`74732
`77529
`80024
`69132
`94523
`115492
`127369
`137152
`142429
`147092
`
`1024
`1024
`1024
`1024
`1024
`1024
`2048
`2048
`2048
`2048
`2048
`2048
`2048
`2048
`2048
`4096
`4096
`4096
`4096
`4096
`4096
`4096
`8192
`8192
`8192
`8192
`8192
`8192
`8192
`8192
`16384
`16384
`16384
`16384
`16384
`16384
`16384
`32768
`32768
`32768
`32768
`32768
`32768
`32768
`32768
`6S536
`65S36
`65536
`65536
`65536
`65536
`65S36
`65536
`131072
`131072
`l31072
`
`6
`7
`8
`12
`13
`14
`1S
`lo
`20
`23
`26
`21
`28
`29
`30
`36
`41
`46
`49
`52
`53
`S4
`66
`75
`84
`89
`94
`97
`100
`116
`137
`1S4
`163
`172
`177
`182
`208
`247
`282
`299
`316
`325
`334
`372
`448
`514
`S49
`580
`597
`614
`664
`812
`938
`100S
`106'
`1097
`1128
`
`4
`4
`8
`8
`8
`8
`8
`16
`l6
`1'
`16
`16
`16
`16
`16
`32
`32
`32
`32
`32
`32
`32
`64
`64
`64
`64
`64
`64
`64
`64
`128
`128
`128
`128
`128
`128
`128
`128
`256
`2S6
`256
`256
`256
`256
`256
`512
`512
`512
`512
`512
`512
`512
`512
`512
`1024
`1024
`1024
`
`As an example of a MTR block code, the rate 4/5, MTR=2;k=8 block code is given in
`Table IV. 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 optimal in terms of minimizing the logic
`implementation. Note that the k=8 constraint comes into effect when the codewords 10000 09001
`occur in sequence. The user data and codeword pairs are represented by
`X3XzX1Xo .. Y,v'y'v'1Yo
`
`B. Brickner, J. Moon
`
`University of Minnesota
`
`September 26, 1995
`
`
`Page 8 of 19
`
`

`

`I Seagate Annual Report
`
`The equations for the encoder are
`
`'
`
`-
`Yo = X<f1 + X<f2X3 + X<fzX3
`-
`Yi = Xo,X1Xz + X1XzX3 + X1X2X3
`Y2 = Xz
`-
`· Y3 = X1X3 + XoXzX3
`----
`Y4 = XoX1XzX3 + XoX1 + X1XzX3
`
`The corresponding decoder is
`
`Xo = Yo + Y1Y4
`XI = Y1 + YoY4 + Yv'4
`Xz = Y2
`-
`-
`X3 = Y3 + Y1Yi)'4 + Y1Y2Y4
`
`9
`
`(6)
`
`(7)
`
`Two-level NAND logic implementations of (6) and (7) are shown in Figure 8 and
`Figure 9, respectively. These logic rules are representative of those that could be developed for
`any of the MTR block codes.
`Table IV. A rate 4/5, MTR=2;k=8 block code: user data - codeword
`
`0000 - 10000
`_ 0001 - 00001
`0010- 00010
`0011 - 10001
`
`0100- 00100
`0101 - 00101
`0110- 00110
`0111 - 10110
`
`1000 - 01000
`1001 - 01001
`1010-01010
`1011 - 10010
`
`1100 - 01100
`1101 - 01101
`1110 - 10100
`1111 - 10101
`
`B. Brickner, J . Moon
`
`University of Minnesota
`
`September 26, 1995
`
`
`Page 9 of 19
`
`

`

`Seagate Annual Report
`
`1 O
`
`x3 x2 xl xO
`
`. Figure 8. Logic Implementation of a rate 4/5 MTR=2;/c=i8 encoder.
`
`y4 y3 y2 yl yO
`
`yl
`
`y3
`
`y4
`
`xO
`
`xl
`
`x3
`
`Figure 9. Logic Implementation of a rate 4/5 MTR=2;k=8 decoder.
`
`B. Brickner, J. Moon
`
`University of Minnesota
`
`September 26, 1995
`
`
`Page 10 of 19
`
`

`

`Seagate Annual Report
`
`11
`
`y'
`
`4.5 Detector Design
`In order to obtain the full benefits of the MTR=2 coding, the detector structure must be
`modified so that illegal paths are removed from consideration. For example, in the r=3 FDTS,
`the paths
`
`are automatically eliminated. These are shown shaded in Figure 10. Additionally, paths which
`violate the constraint can be elirp.inated by considering the previously decided symbol. In the case
`of a r=2 FDTS, the path corresponding to the previous decision, ak.3 is eliminated; i.e.,
`(ak, ak-1' ak_2, (2~_3) = ±(+1, -1, +1, - 1)
`
`The two possibilities are shown in Figure 11. Although the examples given here and the
`simulation results presented later are based on FDTS/DF, the MTR coding techniques will also
`yield improved performance when used with other sequence estimators such as maximum ·
`likelihood sequence detection and reduced state sequence estimation.
`
`Figure 10. FDTS r-3 showing paths eliminated by
`MTR=2;k codes.
`
`F igure 11. FDTS r-2 showing paths eliminated by
`MTR=2;k b~sed on ak.J•
`
`5 Signal Space Detection
`A signal space representation of the detection process involves mapping a received data
`vector into an M-dimensional space. This received vector consists of the current sample and 7
`previous samples; thus, M = T + 1. The detection problem is a matter of determining which of
`the possible noiseless points is closest to the received data. For a pair of points, this can be
`interpreted as determining on which side of the orthogonal bisector of the segment between the
`two points, the input sample lies. When several points are involved, the boundary is composed
`of several linear segments. In the· next section, the design of these boundaries is considered.
`
`8. Brickner, J . Moon
`
`University of Minnesota
`
`September 26, 1995
`
`
`Page 11 of 19
`
`

`

`'
`
`Seagate Annual Report
`
`5.1 Implementation of Boundaries
`A linear signal space boundary can be
`implemented using an FIR filter, an offset term,
`and a binary slicer (or single-bit quantizer).
`Consider Figure 12, where two point, f and g are
`shown separated by a linear boundary. A point in
`the shaded region is closest to point f; conversely,
`a point in the unshaded region is closest to g.
`The boundary between two points is
`defined by the locus of point equidistantly spaced
`from the two points being separated. Equivalently,
`the square of the distance may he used, which
`gives
`
`This can be simplified to
`
`12
`
`:::;(cid:173)
`~ Of -- -- --+------'
`I<
`
`_,
`
`(g0,g1)
`
`_,
`- 2L - -~- - - - ' -- -~ - - - J
`-2
`0
`x(k)
`
`Figure 12. A linear boundary separating two points in
`two-dimensional space
`
`T
`
`(8)
`
`(9)
`
`The line ( or hyperplane in high dimensions) can be realized by using an FIR filter augmented
`with an adder to provide an offset term. The result is
`t L W;x1c-; + c = 0
`
`(10)
`
`i• O
`
`where W is the FIR weight vector defined by
`
`and the offset term is
`
`C = t (J;2 - g/)
`
`i:O
`
`(11)
`
`(12)
`
`For the remainder of this section, the term FIR filter will signify a standard FIR filter augmented
`with an offset term. The sign of the output determines which side of the boundary x is on. Thus,
`a simple slicer converts the FIR output to a binary partitioning of the signal space. A block
`diagram for implementing a linear boundary is shown in Figure 13.
`
`8. Brickner, J. Moon
`
`University of Minnesota
`
`September 26, 1995
`
`
`Page 12 of 19
`
`

`

`Seagate Annual Report
`
`13
`
`Figure 13. Implementation of a linear boundary using
`an FIR filter
`
`Figure 14. Two-dimensional
`representation for D.=2.5
`
`x(lo.)
`
`signal
`
`space
`
`In general, performing detection for d = 0 coding requires more than one FIR filter. When
`multiple hyperplanes are used to define the boundary, a simple logic circuit using the FIR/slicer
`values as inputs can be used to make the decision. As an example, the 2-dimensional case
`corresponding to D,, = 2.5 is shown in Figure 14, where the shaded region corresponds to
`ak-1 = +l.
`Although it may not be obvious, a feedback loop internai to the detector is required to
`maintain the desired minimum distance. The purpose of this loop is to cancel ISI terms inside the
`FIR filters due to previously determined symbols. For example, without an internal feedback loop,
`the noiseless points in a 3-dimensional space would take the form
`x = (xk, xk-1, xk-2) = (akbo +ak_1b1 +ak_2b2, ak_1bo +ak_zb2 +ak_3b3, ak_zbo +ak-i2 +ak_4b3)
`
`Because a detector operating in 3 dimensions has a delay of r-=2, the symbols ak.3 and ak.4 have
`already been determined, so their inclusion does not provide any additional information. In fact,
`if these are not removed, each doubles the number of symbols in space, because the detector must
`consider all of the case where each is ±1 separately. Examination of these added points has
`indicated that the overall effect is a reduction in the minimum distance. The feedback operation
`in signal space can be viewed as a translation of the decision boundary so that it is in the correct
`position for a set of data symbols consistent with the past decisions. After applying feedback, the
`coordinates in 3-dimensional space become
`x = (xk, xk-1' xk-2) = (akbo+ak-1b1 +ak-2b2, ak-1bo+ak-2b1, ak_zb~)
`
`5.2 Simplifications
`Signal space detection will have the same distance properties as FDTS/DF, provided a
`hyperplane (boundary) exists for each pair of conflicting points. Conflicting points are simply two
`points in the M-dimensional space, one of which corresponds to the symbol ak•T=+ 1 and the other
`to ak•r=-1. Thus, a total of 22
`' boundaries are required; e.g. an implementation of r-=3 would
`require 64 boundaries. Clearly, this is more complex than a direct implementation of FDTS,
`which would require only 2t+1=16 multiplies for the branch metric calculations. Fortunately,
`symmetry allows a substantial reduction in the number of multipliers for the SSD (signal space
`detector).
`If 64 FIR filters are implemented in 4-dimensional space, a total of 256 multiplies and
`
`B. Brickner, J. Moon
`
`University of Minnesota
`
`September 26, 1995
`
`
`Page 13 of 19
`
`

`

`Seagate Annual Report
`
`14
`
`64 additions are required, not including the internal feedback. Because the coordinate in the
`( rt-1 t dimension is determined by ak-rbo, the corresponding multiplier is Wr = 4. A total of 64
`multipliers may be removed by dividing through by this term. Further, the symmetry of the FIR
`portion (not including the offset) will be identical, and the only difference will be that the
`negative of the offset for one is added to the second. This was illustrated in Figure 14, where two
`of the lines have the same slope, but different intercepts (offsets). These simplifications are
`mentioned, not to propose the use of a full set of hyperplanes, but rather to indicate that there
`are many ways to reduce the complexity of these FIR filters.
`The two dimensional case presented earlier indicates an important simplification; one of
`the boundary lines was unnecessary and could be removed with affecting performance. The same
`will be true in higher dimensions so that a set of boundaries may removed without degrading the
`detector. Because the detector performance is dominated by pairs separated by /3m;m the boundaries
`between points with distances much greater thanf3min can be translated and rotated to some degree
`without significantly affecting the error rate. A set of hyperplanes may be placed in such a way
`as to separate these pairs so that several pairs share the same boundary. Methods for adaptively
`placing a small number of hyperplanes to achieve optimal performance under that constraint are
`being explored. The signal space implementation has an added savings because the path metric
`update required for FDTS is eliminated.
`As an example of the structure that was discussed, consider the 2-dimensional case,
`corresponding to FDTS/DF with r=l, pictured in Figure 15. This corresponds to the signal space
`in Figure 14. If W,.(j) corresponds to the jlh term of thejth boundary (or FIR filter), then the filter
`·
`weights are
`
`The offset terms are given by
`
`c'U) = cU)
`W1U) '
`
`j = 1,2
`
`(13)
`
`(14)
`
`Where the W,(j) and c(j) terms are given by equations (11) and (12). W'(l) sets the slope of the
`two parallel lines, while W'(3) specifies the line that is closest to the x1c., axis.
`
`5.3 Relationship to FDTS/DF
`The signal space detector was developed in an attempt to simplify the FDTS algorithm;
`therefore, it is instructive to examine parallels in the two methods. In each case, an input
`sequence of fixed length is compared to all possible noiseless sequences, and a decision is made
`in favor of the sequence that is closest in Euclidean distance to the input. With FDTS, this
`distance measurement is made by computing the squared distance of a single input from the
`noiseless symbols and adding this branch metric to a path metric accumulator. In the case of
`signal space detection, filters are used to form boundaries between regions corresponding to
`conflicting symbols. The location of the input symbol in relation to these boundaries is then used
`to make a decision. The output of the detector is then used to cancel ISI at the input, due to these
`
`B. Brickner, J. Moon
`
`University of Minnesota
`
`September 26, 1995
`
`
`Page 14 of 19
`
`

`

`I
`
`Seagate Annual Report
`
`15
`
`-b1
`+b1
`..___--- -~ o~----~
`
`Figure 15. Two-Dimensional Signal Space Detector
`
`past symbols. There is an important relationship between the ip.temal feedback used in the signal
`space detector and FDTS. The internal feedback cancels ISI due to symbols that have already
`been decided~ but in the detector delay line, rather than at its input. In FDTS, this action is
`accomplished by discarding half of the tree with every decision so that the !SI from the symbol
`that was decided is a constant offset in all of the path metrics.
`
`5.4 Signal Dependent Threshold
`Examination of Figure 14 shows that for any value of xk the boundary between the two
`regions intersects xk-I at a single point. Thus, a decision can be made by comparing xk-I with the
`boundary point, denoted O(xJ. Thus the decision rule is
`·
`
`(15)
`
`where SGN is the signum function which returns + 1 when the argument is greater than O and -1
`otherwise. As with the FIR formulation of signal space detection, an internal feedback loop is
`required. A block diagram for this digital implementation is shown in Figure 16, where the ROM
`serves as a lookup table for the functional mapping from xk to the bow1dary point.
`
`+b 1
`-b 1
`
`ROM
`Figure 16. Using a ROM to implement a signal dependent threshold
`
`8. Brickner, J. Moon
`
`University of Minnesota
`
`September 26, 1995
`
`
`Page 15 of 19
`
`

`

`Seagate Annual Report
`
`16
`
`6 Simulation Results
`The performance of the detectors and coding schemes discussed was investigated using Monte
`Carlo simulations. During the simulations, the equalizers were optimized at minimize the mean
`squared error (MSE) at the output, for each SNR point plotted. A minimum of 500 errors were
`counted at each point. During the simulations, the SNR was increased until the bit error rate
`(BER) fell below 1 error in 105 bits. All of the simulations were performed using the MR
`response, except for the signal space detector (SSD) simulations, which used a Lorentzi~ pulse.
`In all ·cases, the user density was Du=2.5.
`
`6.1 Detector Performance
`The performance of the FDTS/DF .detector with a d=O code is shown in Figure 17. As
`
`1E-01
`
`1E-02
`
`1 E-03
`
`1E-04
`
`Q)
`+-
`0 u::
`
`I..
`0
`I..
`I.. w
`+-co
`
`---DFE
`
`-+-
`r-=1
`~
`r=2
`-a-
`r=3
`~
`
`.r=4 --.-
`
`r=5
`
`1 E-0 5 +--t----+--+--
`5
`7
`6
`8
`
`--+--+--t----+--+---+--'--ffi-....u....:i
`9
`10
`11
`12 13 14 15
`16
`SNR (dB)
`
`Figure 17. Simulated performance of FDTS/DF at D.=2.5, with a d=-0 code
`
`predicted by the fimin curve, there is• a noticeable increase in detector performance from r=O to r= I
`and from r=2 to r=3, but increasing from r=3 to r-=4 yields a minimal gain. The performance of
`FDTS/DF for r=l and r=3 using the (0,4/4) code is compared against PRML, EPRML, and DFE
`in Figure 18. The curve Q(dm1j2a) gives the approximate l'vfLSD bound.
`
`B. Brickner, J. Moon
`
`University of Minnesota
`
`Se ptember 26, 1995
`
`
`Page 16 of 19
`
`

`

`Seagate Annual Report
`
`17
`
`1E-01
`
`1E- 02
`
`(I)
`+-
`0
`~
`
`L 1E-03
`0
`L
`L w
`+-
`CD
`
`1E-04
`
`---PRML
`
`--+-
`EPRML
`~
`DFE
`-s-
`r=l
`~
`r=3
`--A-
`Q(dmin/2a-)
`
`1 E -0 5 +--,---+-
`7
`5
`
`-+-----'T-----311E--'-+->--+-----,---i
`..---+-----.----+-~
`9
`1 7
`13
`15
`11
`19
`SNR (dB)
`
`Figure 18. Comparison of Several Detection Methods
`
`6.2 Coding Gain
`The use of a code which eliminates the data sequences most likely to cause errors has
`been proposed as a method for improving detector margin. To verify these claims, simulations
`were performed using a rate 4/5 and rate 16/19 MfR=2;k code with a FDTS/DF detector. The
`resulting error rate curves are shown in Figure 19 and Figure 20.
`A summary of the performance for the three codes is shown in Figure 21. This graph
`reveals several points of interest. As noted in the discussion of /3111111
`, the distance increase from
`one tree depth to the next is not a smooth function. However, the use of a MTR=2;k code
`smo