United States Patent [19J
`Moon et al.
`
`111111
`
`1111111111111111111111111111111111111111111111111111111111111
`US005859601A
`[11] Patent Number:
`[45] Date of Patent:
`
`5,859,601
`Jan. 12, 1999
`
`[54] METHOD AND APPARATUS FOR
`IMPLEMENTING MAXIMUM TRANSITION
`RUN CODES
`
`[75]
`
`Inventors: Jaekyun Moon, Plymouth; Barrett J.
`Brickner, Minneapolis, both of Minn.
`
`[73] Assignee: Regents of the University of
`Minnesota, Minneapolis, Minn.
`
`[21]
`
`Appl. No.: 730,716
`
`[22]
`
`Filed:
`
`Oct. 15, 1996
`
`[60]
`
`[51]
`[52]
`[58]
`
`[56]
`
`Related U.S. Application Data
`
`Provisional application No. 60/014,954 Apr. 5, 1996.
`
`Int. Cl.6
`...................................................... H03M 7/00
`U.S. Cl. ................................................. 341/59; 341/94
`Field of Search .................................. 341!58, 59, 61,
`341!94
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`4,775,985
`4,779,072
`5,341,134
`5,450,443
`5,608,397
`
`10/1988 Busby ....................................... 375!25
`10/1988 Van Gestel ................................ 341!59
`8/1994 Benjauhrit ................................. 341!58
`9/1995 Siegel et a!. ............................ 375/286
`3/1997 Soljanin .................................... 341!58
`
`Primary Examiner-Jeffrey A Gaffin
`Assistant Examiner-Jason L. W. Kost
`Attorney, Agent, or Firm-Patterson & Keough
`
`[57]
`
`ABSTRACT
`
`Apparatus and method for coding to improve the minimum
`distance properties of sequence detectors operating at high
`densities in storage systems is presented. The coding scheme
`of the present invention is referred to as maximum transition
`run (MTR) code and eliminates data patterns producing long
`runs of consecutive transitions while imposing the usual k
`constraint necessary for timing recovery. The code has a
`distance gaining property similar to an existing (l,k)
`runlength-limited (RLL) code, but can be implemented with
`considerably higher code rates. When the MTR code is used
`with fixed delay tree search (FDTS) or high order partial
`response maximum likelihood (PRML) detectors, the bit
`error rate performance improves significantly over existing
`combinations of codes and detectors.
`
`4,760,378
`
`7/1988 Iketani eta!. .................... 340/347 DD
`
`21 Claims, 14 Drawing Sheets
`
`"Pk+l
`
`Ttl=(-1,-1,-1,-1)
`
`(1)
`'l'k =(-1,-1,-1,+1)
`(2)
`1lfk =(-1,-1,+1,-1)
`
`(3)
`1lfk =(-1,-1,+1,+1)
`
`(4)
`'l'k =(-1,+1,-1,-1)
`
`(6)
`1lfk =(-1,+1,+1,-1)
`
`(7)
`1lfk =(-1,+1,+1,+1)
`(8)
`1lfk =( + 1 '-1 '-1 '-1)
`
`(9)
`1lfk =(+1,-1,-1,+1)
`
`(II)
`)
`1lfk =(+1,-1,+1,+1
`
`(12)
`1lfk =(+1,+1,-1,-1)
`
`( 13)
`1lfk =(+1,+1,-1,+1)
`
`(14)
`'l'k =(+1,+1,+1,-1)
`
`( 15)
`1lfk =(+1,+1,+1,+1)
`
`LSI Corp. Exhibit 1001
`Page 1
`
`

`

`U.S. Patent
`
`Jan. 12,1999
`
`Sheet 1 of 14
`
`5,859,601
`
`LSI Corp. Exhibit 1001
`Page 2
`
`LSI Corp. Exhibit 1001
`Page 2
`
`

`

`U.S. Patent
`
`Jan. 12,1999
`
`Sheet 2 of 14
`
`5,859,601
`
`
`
`Fig. 4
`
`RLL k Constraint
`
`Capacity with MTR j = 2
`
`9 8 7 6 5 4 3 L
`
`oo
`
`10
`
`SI Corp. Exhibit 1001
`Page 3
`
`LSI Corp. Exhibit 1001
`Page 3
`
`

`

`U.S. Patent
`
`Jan. 12,1999
`
`Sheet 3 of 14
`
`5,859,601
`
`Fig. 5
`
`Fig. 6
`
`Fig. 11
`
`DfiVRAVVCNC)° CCNDEVVCNRD
`
`0000- 10000
`
`0001' 00001
`
`0010' 00010
`
`0011- 10001
`0100- 00100
`
`0101- 00101
`
`0110' 00110
`
`0111- 10110
`
`1000- 01000
`
`1001' 01001
`
`1010' 01010
`
`1011' 10010
`
`11000 01100
`
`1101- 01101
`
`1110* 10100
`
`1111- 10101
`
`LSI Corp. Exhibit 1001
`Page 4
`
`LSI Corp. Exhibit 1001
`Page 4
`
`

`

`U.S. Patent
`
`Jan. 12,1999
`
`Sheet 4 of 14
`
`5,859,601
`
`Fig. 5A
`
`m
`
`rate
`
`efficiency available
`
`required
`
`———— codewords ————
`
`2
`2
`3
`
`3
`3
`3
`3
`4
`
`4
`4
`4
`4
`4
`4
`4
`
`5
`5
`5
`5
`5
`5
`5
`
`6
`6
`6
`6
`6
`6
`6
`
`6
`7
`7
`7
`7
`7
`7
`
`7
`7
`8
`8
`8
`8
`8
`
`0.5000
`0.5000
`0.7500
`
`0 6000
`0 6000
`0 6000
`0 6000
`0 8000
`
`0 6667
`0 6667
`0 6667
`0 6667
`0 6667
`0 6667
`0 6667
`
`0 7143
`0 7143
`0 7143
`0 7143
`0 7143
`0 7143
`0 7143
`
`0 7500
`0 7500
`0 7500
`0 7500
`0 7500
`0 7500
`0 7500
`
`0 6667
`0 7778
`0 7778
`0 7778
`0 7778
`0 7778
`0 7778
`
`0 7000
`0 7000
`0 8000
`0 8000
`0 8000
`0 8000
`0 8000
`
`0.5969
`0.5828
`0.8640
`
`0.7163
`0.6994
`0.6912
`0.6871
`0.9133
`
`0.7959
`0.7771
`0.7680
`0.7634
`0.7611
`0.7598
`0.7591
`
`0.8527
`0.8326
`0.8229
`0.8180
`0.8154
`0.8141
`0.8133
`
`0.8954
`0.8742
`0.8640
`0.8589
`0.8562
`0.8548
`0.8540
`
`0.7959
`0.9066
`0.8960
`0.8907
`0.8879
`0.8864
`0.8856
`
`0.8357
`0.8159
`0.9216
`0.9161
`0.9133
`0.9117
`0.9109
`
`6
`7
`8
`
`12
`13
`14
`15
`16
`
`20
`23
`26
`27
`28
`29
`30
`
`36
`41
`46
`49
`52
`53
`54
`
`66
`75
`84
`89
`94
`97
`100
`
`116
`137
`154
`163
`172
`177
`182
`
`208
`247
`282
`299
`316
`325
`334
`
`4
`4
`8
`
`8
`8
`8
`8
`16
`
`16
`16
`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
`256
`256
`256
`256
`
`n
`
`4
`4
`4
`
`5
`5
`5
`5
`5
`
`k
`
`4
`5
`6
`
`4
`5
`6
`7
`8
`
`4
`6
`5
`6
`6
`6
`7
`6
`8
`6
`9
`6
`6 10
`
`4
`7
`5
`7
`6
`7
`7
`7
`8
`7
`9
`7
`7 10
`
`4
`8
`5
`8
`6
`8
`7
`8
`8
`8
`9
`8
`8 10
`
`4
`9
`5
`9
`6
`9
`7
`9
`8
`9
`9
`9
`9 10
`
`4
`10
`5
`10
`6
`10
`7
`10
`8
`10
`9
`10
`10 10
`
`LSI Corp. Exhibit 1001
`Page 5
`
`LSI Corp. Exhibit 1001
`Page 5
`
`

`

`U.S. Patent
`
`Jan. 12, 1999
`
`Sheet 5 of 14
`
`5,859,601
`
`Fig. 5B
`
`.7273
`.7273
`.8182
`.8182
`.8182
`.8182
`.8182
`
`.7500
`.7500
`.7500
`.7500
`.8333
`.8333
`.8333
`
`.7692
`.7692
`.7692
`.7692
`.7692
`.7692
`.8462
`
`.7857
`.7857
`.7857
`.7857
`.7857
`.7857
`.7857
`
`.7333
`.8000
`.8000
`.8000
`.8000
`.8000
`.8000
`
`.7500
`.8125
`.8125
`.8125
`.8125
`.8125
`.8125
`
`.7647
`.7647
`.8235
`
`
`
`
`
`COOOCDOCDCDOOOOCJOCJOCDOOOCDCDOCDCDOCDOOCDOOOCDOCDOCDCIOOOOOO
`
`
`
`
`
`
`
`
`
`
`
`
`
`O\U'|J>-©\O03\]C7\U‘l»£>C)kOCD\lO\U'|u’>©K.OO3\lO‘\U‘-15©\.OCTO\1O\U1I1>©LOG)\1O\U'1»5>C)kOCO\lG\U"J>
`
`
`
`
`
`
`
`
`
`
`
`
`
`OCCDOCJOOOQOOCDOCDOCDOOOCDCDOOOOCDCDOOOC)CDCDOOCDOCDCICDCJOOOCD
`
`
`
`
`
`
`
`.8682
`.8477
`.9426
`.9370
`.9340
`.9325
`.9316
`
`.8954
`.8742
`.8640
`.8589
`.9513
`.9497
`.9489
`
`.9183
`.8966
`.8862
`.8809
`.8781
`.8767
`.9635
`
`.9380
`.9159
`.9052
`.8998
`.8970
`.8955
`.8947
`
`.8755
`.9325
`.9216
`.9161
`.9133
`.9117
`.9109
`
`.8954
`.9471
`.9360
`.9305
`.9275
`.9260
`.9252
`
`.9129
`.8914
`.9487
`
`372
`448
`514
`549
`580
`597
`614
`
`664
`812
`938
`1005
`1066
`1097
`1128
`
`1188
`1471
`1712
`1841
`1956
`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
`
`256
`256
`512
`512
`512
`512
`512
`
`512
`512
`512
`512
`1024
`1024
`1024
`
`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
`
`LSI Corp. Exhibit 1001
`Page 6
`
`LSI Corp. Exhibit 1001
`Page 6
`
`

`

`U.S. Patent
`
`Jan. 12, 1999
`
`Sheet 6 of 14
`
`5,859,601
`
`Fig. 5C
`
`17
`17
`17
`17
`
`18
`18
`18
`18
`18
`18
`18
`
`19
`19
`19
`19
`19
`19
`19
`
`20
`20
`20
`20
`20
`20
`20
`
`21
`21
`21
`21
`21
`21
`21
`
`22
`22
`22
`22
`22
`22
`22
`
`23
`23
`23
`23
`23
`23
`23
`
`
`
`
`
`
`
`C)KO®\)C7\U‘Is£>-©\OCO\1G\U'IsI>©KDCD\10\U1ub©kOCI)\10\U'1»l>-©\DG)\1OW(J'!»l>©\DCD\10\U'1n.D-©kO®\1
`
`
`
`
`
`
`
`
`
`
`
`
`
`QCDCJOCDCDCDOCDCDCDOOOOOCDCDOOOOOOCDOCDOOOOOCDCDOOOCDCDOOOOOCDQ
`
`
`
`
`
`
`
`.8235
`.8235
`.8235
`.8235
`
`.7778
`.7778
`.8333
`.8333
`.8333
`.8333
`.8333
`
`.7895
`.7895
`.7895
`.8421
`.8421
`.8421
`.8421
`
`.8000
`.8000
`.8000
`.8000
`.8500
`.8500
`.8500
`
`.7619
`.8095
`.8095
`.8095
`.8095
`.8095
`.8571
`
`.7727
`.8182
`.8182
`.8182
`.8182
`.8182
`.8182
`
`.7826
`.8261
`.8261
`.8261
`.8261
`.8261
`.8261
`
`
`
`
`
`
`
`OOOOOOCDCDCDCDCDCDOOQOOOOCDCDOOGOCDOOCCDOOCDCDOCJOOCJCJOCC)©©®
`
`
`
`
`
`
`
`.9431
`.9401
`.9386
`.9377
`
`.9285
`.9066
`.9600
`.9543
`.9513
`.9497
`.9489
`
`.9425
`.9202
`.9095
`.9644
`.9613
`.9597
`.9589
`
`.9551
`.9325
`.9216
`.9161
`.9703
`.9687
`.9679
`
`.9096
`.9436
`.9326
`.9270
`.9241
`.9226
`.9760
`
`.9225
`.9537
`.9426
`.9370
`.9340
`.9325
`.9316
`
`.9343
`.9629
`.9517
`.9460
`.9431
`.9415
`.9406
`
`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
`
`123548
`171314
`210790
`233309
`251708
`261658
`270370
`
`220794
`310489
`384724
`427366
`461946
`480694
`496970
`
`394584
`562732
`702180
`782831
`847784
`883087
`913484
`
`16384
`16384
`16384
`16384
`
`16384
`16384
`32768
`32768
`32768
`32768
`32768
`
`32768
`32768
`32768
`65536
`65536
`65536
`65536
`
`65536
`65536
`
`65536
`65536
`131072
`131072
`131072
`
`65536
`131072
`131072
`131072
`131072
`131072
`262144
`
`131072
`262144
`262144
`262144
`262144
`262144
`262144
`
`262144
`524288
`524288
`524288
`524288
`524288
`524288
`
`LS|Cmp.ExmbH1001
`Page?
`
`LSI Corp. Exhibit 1001
`Page 7
`
`

`

`U.S. Patent
`
`Jan. 12,1999
`
`Sheet 7 of 14
`
`5,859,601
`
`4 19
`24
`5 19
`24
`6 20
`24
`7 20
`24
`8 20
`24
`9 20
`24
`24 10 20
`
`4 20
`25
`5 20
`25
`6 21
`25
`7 21
`25
`8 21
`25
`9 21
`25
`25 10 21
`
`4 21
`26
`5 21
`26
`6 22
`26
`7 22
`26
`8 22
`26
`9 22
`26
`26 10 22
`
`4 21
`27
`5 22
`27
`6 22
`27
`7 23
`27
`8 23
`27
`9 23
`27
`27 10 23
`
`4 22
`28
`5 23
`28
`6 23
`28
`7 23
`28
`8 24
`28
`9 24
`28
`28 10 24
`
`0.7917
`0.7917
`0.8333
`0.8333
`0.8333
`0.8333
`0.8333
`
`0.8000
`0.8000
`0.8400
`0.8400
`0.8400
`0.8400
`0.8400
`
`0.8077
`0.8077
`0.8462
`0.8462
`0.8462
`0.8462
`0.8462
`
`0.7778
`0.8148
`0.8148
`0.8519
`0.8519
`0.8519
`0.8519
`
`0.7857
`0.8214
`0.8214
`0.8214
`0.8571
`0.8571
`0.8571
`
`Fig. 51)
`
`0.9451
`0.9228
`0.9600
`0.9543
`0.9513
`0.9497
`0.9489
`
`0.9551
`0.9325
`0.9677
`0.9619
`0.9589
`0.9573
`0.9565
`
`0.9643
`0.9415
`0.9748
`0.9690
`0.9660
`0.9643
`0.9635
`
`0.9285
`0.9498
`0.9387
`0.9755
`0.9725
`0.9708
`0.9700
`
`0.9380
`0.9575
`0.9463
`0.9407
`0.9785
`0.9769
`0.9760
`
`705168
`1019898
`1281584
`1433958
`1555892
`1622325
`1679082
`
`1260216
`1848466
`2339084
`2626666
`2855444
`2980384
`3086334
`
`2252152
`3350167
`4269182
`4811419
`5240442
`5475284
`5673012
`
`4024856
`6071855
`7791902
`8813360
`9617500
`10058681
`10427604
`
`7192882
`11004651
`14221398
`16143951
`17650478
`18478872
`19167054
`
`524288
`524288
`1048576
`1048576
`1048576
`1048576
`1048576
`
`1048576
`1048576
`2097152
`2097152
`2097152
`2097152
`2097152
`
`2097152
`2097152
`4194304
`4194304
`4194304
`4194304
`4194304
`
`2097152
`4194304
`4194304
`8388608
`8388608
`8388608
`8388608
`
`4194304
`8388608
`8388608
`8388608
`16777216
`16777216
`16777216
`
`LSI Corp. Exhibit 1001
`Page 8
`
`LSI Corp. Exhibit 1001
`Page 8
`
`

`

`U.S. Patent
`
`Jan. 12,1999
`
`Sheet 8 of 14
`
`5,859,601
`
`Fig. 7
`
`¥,:‘1£(+1,—1,+1,+1) Q /
`<12>_
`’
`wk
`-(+1,+1,—1,—1) . 0
`\1I,:‘3’:(+1,+1,—1,+1) .’I\
`‘P,:M)=(+1,+1,+1,-1) Q,
`‘P,:15):(+1,+1,+1,+1)‘
`
`0
`Q
`
`LSI Corp. Exhibit 1001
`Page 9
`
`LSI Corp. Exhibit 1001
`Page 9
`
`

`

`U.S. Patent
`
`Jan. 12,1999
`
`Sheet 9 of 14
`
`5,859,601
`
`+1
`
`_']
`
`=='
`
`“-
`
`Fig. 8
`
`+1
`
`_1
`
`+1
`
`_']
`
`+1
`
`_1
`
`+1
`
`+1 """"
`":.:§,:i='
`_1
`.=;:'
`
`-..l
`
`4
`
`+1
`
`_’I
`
`+1
`
`+1
`_
`
`1
`
`-1
`+1
`-1
`+1
`
`-1
`
`_:II
`+1
`+1
`-1
`
`LSI Corp. Exhibit 1001
`Page 10
`
`LSI Corp. Exhibit 1001
`Page 10
`
`

`

`U.S. Patent
`
`Jan. 12,1999
`
`Sheet 10 of 14
`
`5,859,601
`
`Fzg. I0
`
`C=2
`
`998
`1004
`1009
`3127
`3131
`3134
`3175
`3182
`3187
`3190
`3193
`3196
`3227
`
`3230
`3271
`3278
`3289
`3292
`3299
`3302
`
`3308
`3313
`3320
`3463
`3470
`3475
`3481
`3484
`3505
`3512
`3523
`3526
`3529
`3532
`3544
`
`3553
`3556
`3611
`3614
`3623
`3635
`3638
`3641
`3644
`3655
`3662
`3683
`3686
`
`3692
`3697
`3704
`3779
`3782
`3785
`3788
`
`3800
`3809
`3812
`3847
`3854
`3859
`3865
`3868
`3875
`3878
`3889
`3896
`3937
`3940
`
`247
`251
`439
`443
`446
`475
`478
`487
`494
`499
`502
`505
`631
`
`635
`638
`823
`827
`830
`871
`878
`
`883
`886
`889
`892
`923
`926
`947
`950
`953
`956
`967
`974
`985
`988
`995
`
`C=4
`
`C=6
`
`503
`507
`887
`891
`894
`951
`955
`958
`987
`990
`999
`1006
`1011
`
`1014
`3191
`3195
`3198
`3291
`3294
`3303
`
`3310
`3315
`3318
`3321
`3324
`3483
`3486
`3507
`3510
`3513
`3516
`3527
`3534
`3545
`3548
`
`3555
`3558
`3564
`3569
`3576
`3639
`3643
`3646
`3687
`3694
`3699
`3702
`3705
`
`3708
`3783
`3790
`3801
`3804
`3811
`3814
`
`3820
`3825
`3832
`3867
`3870
`3879
`3891
`3894
`3897
`3900
`3939
`3942
`3948
`3953
`3960
`
`1015
`3319
`3323
`3511
`3515
`3518
`3547
`3550
`3559
`3566
`3571
`3574
`3577
`
`3703
`3707
`3710
`3803
`3806
`3815
`3822
`
`3827
`3830
`3833
`3836
`3895
`3899
`3902
`3943
`3950
`3955
`3958
`3961
`3964
`
`3651
`3654
`3657
`3660
`3681
`3684
`3777
`3780
`3784
`3843
`3846
`3849
`3852
`
`3857
`3864
`3873
`3876
`
`C=0
`
`795
`798
`807
`819
`822
`825
`828
`867
`870
`876
`881
`888
`903
`
`910
`915
`921
`924
`945
`952
`963
`
`966
`969
`972
`984
`993
`996
`3099
`3102
`3111
`3123
`3126
`3129
`3132
`3143
`3150
`
`3171
`3174
`3180
`3185
`3192
`3207
`3214
`3219
`3225
`3228
`3267
`3270
`3273
`
`3276
`3288
`3297
`3300
`3459
`3462
`3465
`
`3468
`3473
`3480
`3521
`3524
`3528
`3591
`3598
`3603
`3609
`3612
`3619
`3622
`3633
`3640
`
`219
`222
`231
`238
`243
`246
`249
`252
`311
`315
`318
`411
`414
`
`435
`438
`441
`444
`455
`462
`473
`
`476
`483
`486
`492
`497
`504
`567
`571
`574
`615
`622
`627
`630
`633
`636
`
`LSI Corp. Exhibit 1001
`Page 11
`
`LSI Corp. Exhibit 1001
`Page 11
`
`

`

`U.S. Patent
`
`Jan. 12,1999
`
`Sheet 11 of 14
`
`5,859,601
`
`Fig. 11A
`
`n
`
`k
`
`m
`
`rate Max C
`
`available
`
`required
`
`———- codewords —---
`
`6
`
`7
`7
`
`8
`8
`8
`
`9
`9
`9
`9
`
`10
`10
`10
`10
`10
`
`11
`11
`11
`11
`11
`11
`
`4
`
`4
`5
`
`4
`5
`6
`
`4
`5
`6
`7
`
`4
`5
`6
`7
`8
`
`4
`5
`6
`7
`8
`9
`
`4
`12
`5
`12
`6
`12
`7
`12
`8
`12
`9
`12
`12 10
`
`4
`13
`5
`13
`6
`13
`7
`13
`8
`13
`9
`13
`13 10
`
`2
`
`3
`3
`
`4
`4
`5
`
`4
`5
`5
`5
`
`5
`6
`6
`6
`6
`
`6
`6
`7
`7
`7
`7
`
`7
`8
`8
`8
`8
`8
`8
`
`7
`8
`8
`9
`9
`9
`9
`
`14
`14
`14
`14
`14
`
`9
`4
`9
`5
`6 10
`7 10
`8 10
`
`0.3333
`
`0.4286
`0.4286
`
`0.5000
`0.5000
`0.6250
`
`0.4444
`0.5556
`0.5556
`0.5556
`
`0.5000
`0.6000
`0.6000
`0.6000
`0.6000
`
`0.5455
`0.5455
`0.6364
`0.6364
`0.6364
`0.6364
`
`0.5833
`0.6667
`0.6667
`0.6667
`0.6667
`0.6667
`0.6667
`
`0.5385
`0.6154
`0.6154
`0.6923
`0.6923
`0.6923
`0.6923
`
`0.6429
`0.6429
`0.7143
`0.7143
`0.7143
`
`2
`
`3
`3
`
`2
`2
`6
`
`3
`3
`3
`3
`
`2
`4
`2
`2
`2
`
`3
`3
`5
`3
`3
`3
`
`2
`6
`4
`4
`2
`2
`2
`
`3
`3
`3
`5
`5
`5
`5
`
`6
`2
`6
`4
`4
`
`5
`
`9
`10
`
`19
`24
`32
`
`24
`33
`39
`42
`
`47
`79
`75
`82
`84
`
`70
`97
`144
`129
`137
`142
`
`135
`263
`296
`328
`264
`274
`277
`
`200
`296
`364
`514
`556
`583
`601
`
`524
`562
`1046
`1038
`1114
`
`4
`
`8
`8
`
`16
`16
`32
`
`16
`32
`32
`32
`
`32
`64
`64
`64
`64
`
`64
`64
`128
`128
`128
`128
`
`128
`256
`256
`256
`256
`256
`256
`
`128
`256
`256
`512
`512
`512
`512
`
`512
`512
`1024
`1024
`1024
`
`LSI Corp. Exhibit 1001
`Page 12
`
`LSI Corp. Exhibit 1001
`Page 12
`
`

`

`U.S. Patent
`
`Jan. 12,1999
`
`Sheet 12 of 14
`
`5,859,601
`
`Fig. 113
`
`9 10
`14
`14 10 10
`
`0.7143
`0.7143
`
`9
`4
`15
`5 10
`15
`6 10
`15
`7 10
`15
`8 11
`15
`9 11
`15
`15 10 11
`
`4 10
`16
`5 11
`16
`6 11
`16
`7 12
`16
`8 12
`16
`9 12
`16
`16 10 12
`
`4 11
`17
`5 11
`17
`6 12
`17
`7 12
`17
`8 12
`17
`9 12
`17
`17 10 12
`
`4 12
`18
`5 13
`18
`6 13
`18
`7 13
`18
`8 13
`18
`9 13
`18
`18 10 14
`
`4 12
`19
`5 13
`19
`6 14
`19
`7 14
`19
`8 14
`19
`9 14
`19
`19 10 14
`
`4 13
`20
`5 14
`20
`6 15
`20
`7 15
`20
`8 15
`20
`9 15
`20
`20 10 15
`
`0.6000
`0.6667
`0.6667
`0.6667
`0.7333
`0.7333
`0.7333
`
`0.6250
`0.6875
`0.6875
`0.7500
`0.7500
`0.7500
`0.7500
`
`0.6471
`0.6471
`0.7059
`0.7059
`0.7059
`0.7059
`0.7059
`
`0.6667
`0.7222
`0.7222
`0.7222
`0.7222
`0.7222
`0.7778
`
`0.6316
`0.6842
`0.7368
`0.7368
`0.7368
`0.7368
`0.7368
`
`0.6500
`0.7000
`0.7500
`0.7500
`0.7500
`0.7500
`0.7500
`
`21
`
`4 14
`
`0.6667
`
`4
`4
`
`3
`5
`3
`3
`9
`7
`7
`
`2
`4
`2
`10
`6
`6
`6
`
`5
`3
`5
`5
`3
`3
`3
`
`6
`8
`4
`4
`2
`2
`10
`
`3
`3
`7
`5
`5
`5
`5
`
`2
`4
`6
`4
`4
`4
`4
`
`5
`
`1163
`1195
`
`578
`1119
`1130
`1274
`2108
`2136
`2221
`
`1086
`2258
`2153
`4113
`4164
`4378
`4531
`
`2060
`2737
`4607
`5312
`4372
`4575
`4712
`
`4545
`8255
`9135
`10489
`8272
`8644
`16747
`
`4836
`8379
`16626
`17111
`18821
`19849
`20579
`
`8985
`21308
`33829
`33557
`36775
`38703
`40032
`
`1024
`1024
`
`512
`1024
`1024
`1024
`2048
`2048
`2048
`
`1024
`2048
`2048
`4096
`4096
`4096
`4096
`
`2048
`2048
`4096
`4096
`4096
`4096
`4096
`
`4096
`8192
`8192
`8192
`8192
`8192
`16384
`
`4096
`8192
`16384
`16384
`16384
`16384
`16384
`
`8192
`16384
`32768
`32768
`32768
`32768
`32768
`
`17857
`
`16384
`
`LSI Corp. Exhibit 1001
`Page 13
`
`LSI Corp. Exhibit 1001
`Page 13
`
`

`

`U.S. Patent
`
`Jan. 12, 1999
`
`Sheet 13 of 14
`
`5,859,601
`
`Fig. IIC
`
`21
`21
`21
`21
`21
`21
`
`22
`22
`22
`22
`22
`22
`22
`
`23
`23
`23
`23
`23
`23
`23
`
`24
`24
`24
`24
`24
`24
`24
`
`25
`25
`25
`25
`25
`25
`25
`
`26
`26
`26
`26
`26
`26
`26
`
`27
`27
`27
`27
`27
`
`15
`15
`16
`16
`16
`16
`
`15
`16
`16
`17
`17
`17
`17
`
`15
`16
`17
`17
`18
`18
`18
`
`16
`18
`18
`18
`19
`19
`19
`
`17
`18
`19
`19
`19
`19
`19
`
`18
`19
`20
`20
`20
`20
`21
`
`19
`20
`20
`21
`21
`
`
`
`
`
`
`
`m~qg\u1¢c)m<m~4o\m.uouoanqcnuwac3u>m-qoxm-AOkOd)<(fiU1bC)©(D\JmLDbC>u>m—4o\w
`
`
`
`
`
`
`
`
`
`
`
`
`
`OOOOCDOOOCDCDCDOCDOCDCJCDCDOOOOOOOCDOCDOOCDOOOCDOOCCDOOOCDCDCDG
`
`
`
`
`
`
`
`.7143
`.7143
`.7619
`.7619
`.7619
`.7619
`
`.6818
`.7273
`.7273
`.7727
`.7727
`.7727
`.7727
`
`.6522
`.6957
`.7391
`.7391
`.7826
`.7826
`.7826
`
`.6667
`.7500
`.7500
`.7500
`.7917
`.7917
`.7917
`
`.6800
`.7200
`.7600
`.7600
`.7600
`.7600
`.7600
`
`.6923
`.7308
`.7692
`.7692
`.7692
`.7692
`.8077
`
`.7037
`.7407
`.7407
`.7778
`.7778
`
`33597
`35236
`68427
`71495
`76019
`67153
`
`34683
`65732
`66307
`140771
`143015
`151640
`157756
`
`40949
`79430
`149570
`131932
`264682
`273403
`286841
`
`75344
`263893
`290571
`346562
`546228
`553812
`579307
`
`154995
`326028
`558253
`578589
`648508
`690244
`719462
`
`32768
`32768
`65536
`65536
`65536
`65536
`
`32768
`65536
`65536
`131072
`131072
`131072
`131072
`
`32768
`65536
`131072
`131072
`262144
`262144
`262144
`
`65536
`262144
`262144
`262144
`524288
`524288
`524288
`
`131072
`262144
`524288
`524288
`524288
`524288
`524288
`
`296598
`629996
`1110146
`1117761
`1250283
`1328833
`2110651
`
`540881
`1175593
`1127331
`2229237
`2117392
`
`262144
`524288
`1048576
`1048576
`1048576
`1048576
`2097152
`
`524288
`1048576
`1048576
`2097152
`2097152
`
`
`
`o\o\(5\col\)a:..;>01\1\]Lo0JU'I
`
`
`
`l\)u-|>-n.l>-J:-O'\».bubU'|U‘|U'!U'|\lU'|U'|
`
`U‘|\J(,«)\1kO
`
`}—‘
`
`LS|Cmp.ExmbH1001
`Page14
`
`LSI Corp. Exhibit 1001
`Page 14
`
`

`

`U.S. Patent
`
`Jan. 12,1999
`
`Sheet 14 of 14
`
`5,859,601
`
`Fig. 11D
`
`9 21
`27
`27 10 21
`
`0.7778
`0.7778
`
`4 20
`28
`5 21
`28
`6 22
`28
`7 22
`28
`8 22
`28
`9 22
`28
`28 10 22
`
`0.7143
`0.7500
`0.7857
`0.7857
`0.7857
`0.7857
`0.7857
`
`5
`5
`
`8
`6
`12
`6
`6
`4
`4
`
`2260957
`2361027
`
`2097152
`2097152
`
`1085033
`2327099
`4234345
`4398507
`4985834
`4339268
`4525346
`
`1048576
`2097152
`4194304
`4194304
`4194304
`4194304
`4194304
`
`LSI Corp. Exhibit 1001
`Page 15
`
`LSI Corp. Exhibit 1001
`Page 15
`
`

`

`5,859,601
`
`1
`METHOD AND APPARATUS FOR
`IMPLEMENTING MAXIMUM TRANSITION
`RUN CODES
`
`This application claims the benefit of U.S. provisional 5
`application No. 60/014,954, filed Apr. 5, 1996.
`
`FIELD OF THE INVENTION
`
`The present invention relates in general to digital storage
`systems. More specifically, the invention pertains to an
`improved coding technique involving data recovery chan(cid:173)
`nels utilizing sequence detection methods.
`
`BACKGROUND OF THE INVENTION
`
`10
`
`2
`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 (O,G/I) coding offers a much higher rate, but
`does not provide any coding gain. Also, (O,G/1) 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)
`systems.
`Sequence detectors are data recovery devices that exam(cid:173)
`ine 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
`15 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 mostly from difficulty in distin-
`20 guishing minimum distance patterns. For a sequence detec(cid:173)
`tor that uses M samples to make a decision, all possible
`noiseless sample 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
`25 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 mini(cid:173)
`mum 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.
`
`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
`codes impose a ( d,k) constraint on the recorded data
`sequence. With the Non-Return-to-Zero (NRZ) recording
`format, where the binary "1" represents a positive level in
`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, 30
`where a magnetic transition is represented by 1 and no
`transition by 0, d and k are the minimum and maximum
`number of consecutive O's between any two 1's, respec(cid:173)
`tively as described in P. H. Siegel, "Recording codes for
`digital magnetic storage," IEEE Transactions on Magnetics, 35
`vol. MAG-21, no. 5, pp. 1344-1349, September 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 40
`loop to the data. A (1,7) code is a common example of an
`RLL code; see U.S. Pat. No. 4,337,458. 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 U.S. Pat. No. 4,707,681. Additional 45
`constraints, such as a limitation on the total number of NRZI
`1's in a codeword for the purpose of improving timing and
`gain control can be applied to these codes; see U.S. Pat. No.
`5,196,849. A DC-free constraint as described in U.S. Pat.
`No. 4,499,454 can be used to reduce the low frequency 50
`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 55
`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 Transactions 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 recording," International Con- 65
`ference on Communications, June 1989. While RLL (1,k)
`coding has many useful properties, the required code rate,
`
`SUMMARY OF THE INVENTION
`The present invention relates to a channel coding tech(cid:173)
`nique 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 cer(cid:173)
`tain 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 repro(cid:173)
`duced. This improvement in the bit error rate can be traded
`for an increase in storage density if the error rate perfor(cid:173)
`mance is already satisfactory. See B. Brickner and J. Moon,
`"Coding for increased distance with a d=O FDTS/DF
`detector," Seagate Internal Report, May 1995; also pre(cid:173)
`sented at the Annual Meeting of the National Storage
`Industry Consortium, Monterey, Calif., 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 limit on the
`60 maximum number of consecutive transitions that can occur
`in the written magnetization 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 number of consecutive
`transitions is limited to two. The MTR code with a constraint
`length of j=2 will allow "dibit" transitions in the magneti(cid:173)
`zation pattern, but will not permit "tribit" or longer runs of
`
`LSI Corp. Exhibit 1001
`Page 16
`
`

`

`5,859,601
`
`3
`consecutive transitions. Unless indicated otherwise, our dis(cid:173)
`cussion 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 (O,G/I) code/partial response maximum likelihood
`(PRML) and (1,7) RLL code/peak detector combinations.
`Computer implemented simulations show a large perfor(cid:173)
`mance 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 NRZI format, the
`MTR code constraint is equivalent to limiting the maximum
`runlength of 1 's. To facilitate timing recovery, the usual
`maximum runlength constraint is also imposed on O's.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 shows pairs of write patterns causing most errors
`in sequence detection at high user densities.
`FIG. 2 is the state diagram for the MTR code with j=2.
`FIG. 3 is the state diagram for an MTR (2;6) code.
`FIG. 4 gives the capacities for the MTR j=2 codes with
`different RLL k constraints.
`FIG. 5 is a table showing the code parameters for MTR
`j=2 block codes with different RLL k constraints and dif(cid:173)
`ferent block sizes.
`FIG. 6 shows a mapping of datawords to codewords for
`the rate 4/5 MTR (2;8) code.
`FIG. 7 is the E2 PR4-VA trellis modified for use with an
`MTR j=2 code.
`FIG. 8 illustrates a FDTS 1:=3 detector modified for use 35
`with an MTR j=2 code.
`FIG. 9 illustrates a FDTS 1:=2 detector modified for use
`with an MTR j=2 code.
`FIG. 10 lists a decimal representation of the valid code(cid:173)
`words corresponding to different values of C for the 8/12
`DC-free MTR j=2 code.
`FIG. lllists code parameters for DC-free MTR j=2 block
`codes with different RLL k constraints and different block
`SIZeS.
`
`45
`
`5
`
`4
`removing the paths that allow the ±{2-2 2} 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 E2 PR4ML. Low order PRML sys-
`terns are not dominated by these errors because they force
`the channel to respond like a low density system where the
`minimum distance error event is different.
`To obtain a coding gain (improvement in minimum dis(cid:173)
`tance due to coding), the minimum distance pairs shown in
`10 FIG. 1 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
`15 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
`20 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
`25 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
`30 the typical (1,k) RLL code.
`Referring now to FIG. 2, the MTR j=2 code based on the
`NRZI recording convention, where 1 and 0 represent the
`presence and absence, respectively, of a magnetic transition
`is shown. Specifically, FIG. 2 depicts a state diagram defin(cid:173)
`ing 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
`40 eigenvalue of the adjacency matrix A, which describes the
`transitions between states for the given state diagram and
`computing:
`
`(1)
`
`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 oper(cid:173)
`ating at high data densities is the detector's inability in the
`presence of noise to distinguish the minimum distance
`patterns. FIG. 1 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
`difference) pattern of ek=±{2-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 dis(cid:173)
`tance between two diverging look ahead tree paths after
`
`To more compactly describe the code constraints, the MTR
`parameters are written as Q;k) where j is the MTR constraint
`and k is the usual RLL constraint. For practical codes, the
`RLLk-constraint must be included for timing recovery. This
`50 constraint can be incorporated into the state diagram as in
`the case of the MTRQ;k)=(2;6) code shown in FIG. 3. The
`capacities for MTR(2;k) codes for different k constraints are
`given in FIG. 4. The capacity is the upper bound on the code
`rate for the given set of parameters. Most codes will have a
`55 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/8 is possible for k~8;
`however, it is likely to be extremely complex. Lower rates
`such as 4/5, 5!6 and 6/7 will require less complexity, while
`60 still improving on the 2/3 rate of RLL(1,7) codes.
`While state-dependent encoders and sliding block decod(cid:173)
`ers can be designed for the MTR constraint, simple fixed(cid:173)
`length block codes can be realized with good rates and
`reasonable k values. A computer search is utilized to find the
`65 2m n-bit codewords required to implement a rate m/n block
`code. First, all binary words that contain the NRZI string of
`"111" or more than k consecutive NRZI O's are removed
`
`LSI Corp. Exhibit 1001
`Page 17
`
`

`

`5,859,601
`
`5
`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" string are removed. Also, the k
`constraint is satisfied at the boundary by removing the words
`with k 1 + 1 leading O's or k 2 + 1 trailing O's where k1 +k2 =k. 5
`FIG. 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, m/n, to the capacity computed for the given value of k
`and the MTR constraint. Thus, the efficiency is a measure of 10
`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 FIG. 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 optimal in terms of mini(cid:173)
`mizing the logic implementation. Note that the k=8 con(cid:173)
`straint comes into effect when the codewords 10000 00001
`occur in sequence. If the user data and codeword pairs are 20
`represented by
`
`6
`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
`"11", 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 and ending
`with 0 are joined. By replacing the codewords with a long
`run of NRZI O's with a codeword beginning with "11" when
`the previous bit is a 0, the k constraint can be reduced. To
`illustrate this, consider the rate 4/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 000