United States Patent [19]
`Tsang
`
`IIIII
`
`111111 11111111111111111111111111111 1111111111111111
`US005731768A
`[11] Patent Number:
`[45] Date of Patent:
`
`5,731,768
`Mar. 24, 1998
`
`[54] METHOD AND APPARATUS FOR
`IMPLEMENTING CODES WITH MAXIMUM
`TRANSITION RUN LENGTH
`
`[75]
`
`Inventor: Kinhing P. Tsang, Plymouth, Minn.
`
`[73] Assignee: Seagate Technology, Inc., Scotts
`Valley, Calif.
`
`[21] Appl. No.: 594,987
`
`[22] Filed:
`
`Jan. 31, 1996
`
`Int. Cl. 6
`[51]
`•••...•.•••••••••••••.•..•...•••..••••••••••••••••.••• H03M 7/46
`[52] U.S. CL ................................................................ 341/59
`[58] Field of Search .................................. 341/59, 58, 50,
`341/93, 94, 82
`
`[56]
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`9/1992 McMahon ................................. 341158
`5,144,304
`Primary EXaminer-Brian K. Young
`Attorney, Agent, or Firm-Kinney & Lange, P.A.
`[57]
`ABSTRACT
`
`Encoding and decoding systems for data blocks based on
`forming corresponding code blocks having a maximum
`number of successive repetitions of a first symbol and a
`maximum number of successive repetitions of a second
`symbol, and having code blocks which can represent plural
`different ones of said data blocks unambiguously by having
`further code blocks aid in distinguishing data block is being
`represented.
`
`19 Claims, 15 Drawing Sheets
`
`40
`/-
`
`VALIDITY
`DETERMINER
`
`/371\
`\
`39 -v
`---v
`
`1\
`
`(
`
`J4 Js.JJ_
`~ /
`r-v HOLDING
`\ >
`36
`
`4~1\. /"50
`51--/ DECODER
`~
`
`,J2
`/31
`
`I'>
`A
`-v
`
`I
`
`/30
`
`INPUT
`
`1--
`
`}J
`
`~
`
`/42
`
`STATE
`
`I DETERMINER
`
`l17 /45
`13
`44
`
`t>
`
`46
`DELAY ~
`
`LSI Corp. Exhibit 1009
`Page 1
`
`

`

`U.S. Patent
`U.S. Patent
`
`Mar. 24, 1998
`Mar. 24, 1998
`
`Sheet 1 of 15
`Sheet 1 of 15
`
`5,731,768
`5,731,768
`
`LSI Corp. Exhibit 1009
`Page 2
`
`LSI Corp. Exhibit 1009
`Page 2
`
`

`

`Group A
`
`Group B
`
`Group C
`
`Group D
`
`Binary HEX
`21
`100001
`23
`100011
`25
`100101
`29
`101001
`2B
`101011
`2D
`101101
`31
`110001
`33
`110011
`35
`110101
`
`Binary HEX
`20
`100000
`100010
`22
`24
`100100
`100110
`26
`28
`101000
`2A
`101010
`101100
`2C
`110000
`30
`32
`110010
`110100
`34
`36
`110110
`
`Binary HEX
`01
`000001
`11
`010001
`09
`001001
`19
`011001
`05
`000101
`15
`010101
`OD
`001101
`03
`000011
`13
`010011
`OB
`001011
`1B
`011011
`
`Binary HEX
`02
`000010
`04
`000100
`06
`000110
`08
`001000
`OA
`001010
`oc
`001100
`10
`010000
`12
`010010
`14
`010100
`16
`010110
`18
`011000
`1A
`011010
`
`FIG. 2
`
`~ • 00
`•
`~
`~
`
`a:
`~ :;
`N
`... .:.
`.....
`1.0
`1.0
`OCl
`
`~ a
`N
`s,
`.....
`!.II
`
`01
`~ '-1 w
`~
`~ '-1
`0\
`00
`
`LSI Corp. Exhibit 1009
`Page 3
`
`

`

`State 0 (S 0)
`
`State 1 (S 1)
`
`Data (HEX)
`
`Codeword (HEX)
`
`00000 (00)
`00001 (01)
`00010 (02)
`00011 (03)
`00100 (04)
`00101 (05)
`00110 (06)
`00111 (07)
`01000 (08)
`01001 (09)
`01010 (OA)
`01011 (OB)
`01100 (OC)
`01101 (OD)
`
`100000 (20)
`100010 (22)
`100100 (24)
`100110 (26)
`101000 (28)
`101010 (2A)
`101100 (2C)
`110110 (36)
`110000 (30)
`110010(32)
`110100 (34)
`100001 (21)
`100011 (23)
`100101 (25)
`
`Next
`State
`So
`So
`So
`So
`So
`So
`So
`So
`So
`So
`So
`sl
`s I
`sl
`
`Codeword (HEX)
`
`011000 ( 18)
`000010 (02)
`000100 (04)
`000110 (06)
`001000 (08)
`001010 (OA)
`001100 (OC)
`010110 (16)
`010000 (10)
`010010 (12)
`010100 (14)
`010001 (11)
`010011 ( 13)
`010101 (15)
`
`Next
`State
`So
`So
`So
`So
`So
`So
`So
`s 0
`So
`So
`So
`sl
`sl
`sl
`
`~ •
`00
`•
`
`~ t""t'-a
`
`N
`_,.,f;..
`
`~ ~
`....
`~ QC)
`
`~ I'D a
`w
`~ ....
`
`til
`
`til
`'!..:~
`FIG. 3A ~
`~
`"' ......:.
`0\
`00
`
`LSI Corp. Exhibit 1009
`Page 4
`
`

`

`01110 (OE)
`01111 (OF)
`10000 (10)
`10001 (11)
`10010 (12)
`10011 (13)
`10100 (14)
`10101 (15)
`10110 (16)
`10111 (17)
`11000 ( 18)
`11001 (19)
`11010 (lA)
`11011 (lB)
`11100 ( 1 C)
`11101 (10)
`11110 (1 E)
`1 1 I II (I F)
`
`101 001 (29)
`101011 (2B)
`100000 (20)
`100010 (22)
`100100 (24)
`100110 (26)
`101000 (28)
`101010 (2A)
`101100 (2C)
`110110 (36)
`110000 (30)
`110010 (32)
`110100 (34)
`101101 (20)
`110011 (33)
`110101 (35)
`110001 (31)
`01 1 010 (1 A)
`
`s,
`s,
`s,
`s,
`sl
`s,
`s,
`s,
`sl
`s,
`s,
`s,
`s,
`s,
`sl
`s,
`s,
`sl
`
`011001 (19)
`011011 (IB)
`011000 (18)
`000010 (02)
`000100 (04)
`000110 (06)
`001000 (08)
`001010 (OA)
`001100 (OC)
`010110 (16)
`010000 (10)
`010010 (12)
`010100 (14)
`001101 (00)
`000011 (03)
`000101 (05)
`001001 (09)
`001011 (OB)
`
`s,
`s,
`s,
`s,
`s,
`s,
`s,
`s I
`s,
`s,
`s,
`s,
`s,
`s,
`s,
`s I
`SJ
`sf
`
`d •
`00
`•
`
`~ a
`
`~
`~
`~
`,..s;;..
`
`1-"
`\C
`~
`
`~
`!
`.s;;..
`~
`1-"
`!.II
`
`01
`
`~
`
`FIG. 38 ~ ~
`~ .....:1
`=" 00
`
`LSI Corp. Exhibit 1009
`Page 5
`
`

`

`U.S. Patent
`
`Mar. 24, 1998
`
`Sheet 5 of 15
`
`5,731,768
`
`0:: w
`0
`0
`0 z
`w
`
`~
`
`~
`~
`
`I-
`=>
`0... z
`
`~ ~
`
`~
`~
`
`' ~
`" ~
`tf1
`
`LSI Corp. Exhibit 1009
`Page 6
`
`

`

`U.S. Patent
`
`Mar. 24, 1998
`
`Sheet 6 of 15
`
`5,731,768
`
`0:::
`w
`0
`0
`u
`w
`0
`
`0:::
`>-w
`~--~
`-:::2
`Qo::: _jw
`<(1->w
`0
`
`>-
`:5 w
`
`0
`
`0::: w
`wz
`t-z
`<Co::::
`1-w
`([)1-
`w
`0
`
`~
`\
`
`I(cid:173)
`
`~ n... z
`
`I\
`
`LSI Corp. Exhibit 1009
`Page 7
`
`

`

`U.S. Patent
`
`Mar. 24, 1998
`
`Sheet 7 of 15
`
`5,731,768
`5,731,768
`
`\Ni
`
`4.4.4.35.,»°\now/03”
`\\/\\//éo ae
`ow?aovo
`4v\\
`4999,0
`
`LSI Corp. Exhibit 1009
`Page 8
`
`

`

`U.S. Patent
`
`Mar. 24, 1998
`
`Sheet 8 of 15
`
`5,731,768
`
`Group A
`
`Group B
`
`Group C
`
`Group D
`
`Binary HEX
`Binary HEX
`1000001
`41
`1000000
`40
`1000011
`43
`1000010
`42
`1000101
`45
`1000100
`44
`1001001
`49
`1000110
`46
`1001011
`1001000
`4B
`48
`1001101
`4D
`1001010
`4A
`1010001
`51
`1001100
`4C
`1010011
`1010000
`50
`53
`1010101
`55
`1010010
`52
`1011001
`59
`1010100
`54
`1011011
`5B
`1010110
`56
`61 . 1011000
`1100001
`58
`1100011
`63
`1011010
`SA
`1100101
`65
`1100000
`60
`1101001
`69
`1100010
`62
`1101011
`6B
`1100100
`64
`1101101
`6D
`1100110
`66
`1101000
`68
`1101010
`6A
`1101100
`6C
`
`Binary HEX
`0000001
`01
`0100001
`21
`0010001
`11
`0110001
`31
`0001001
`09
`0101001
`29
`0011001
`19
`0000101
`05
`0100101
`25
`0010101
`15
`0110101
`35
`OD
`0001010
`0101101
`2D
`0000011
`03
`0100011
`23
`0010011
`13
`0110011
`33
`0001011
`OB
`0101011
`2B
`0011011
`lB
`
`Binary HEX
`0000010
`02
`0000100
`04
`0000110
`06
`0001000
`08
`0001010
`OA
`oc
`0001100
`0010000
`10
`0010010
`12
`0010100
`14
`0010110
`16
`0011000
`18
`0011010
`1A
`0100000
`20
`0100010
`22
`0100100
`24
`0100110
`26
`0101000
`28
`0101010
`2A
`0101100
`2C
`0110000
`30
`0110010
`32
`0110100
`34
`0110110
`36
`
`FIG. 6
`
`LSI Corp. Exhibit 1009
`Page 9
`
`

`

`U.S. Patent
`
`Mar. 24, 1998
`
`Sheet 9 of 15
`
`5,731,768
`
`Group A
`
`Group B
`
`Group C
`
`Group D
`
`Binary
`Group AA
`1100011
`1101011
`
`Group AB
`1100001
`1100101
`1101001
`1101101
`
`Group AC
`1000011
`1001011
`1010011
`1011011
`
`Group AD
`1000001
`1000101
`1001001
`1001101
`1010001
`1010101
`1011001
`
`Binary
`Group BD
`1000000
`1000010
`1000100
`1000110
`1001000
`1001010
`1001100
`1010000
`1010010
`1010100
`1010110
`1011000
`1011010
`
`Group BB
`1100000
`1100010
`1100100
`1100110
`1101000
`1101010
`1101100
`
`HEX
`
`63
`6B
`
`61
`65
`69
`60
`
`43
`4B
`53
`SB
`
`41
`45
`49
`40
`51
`55
`59
`
`HEX
`
`40
`42
`44
`46
`48
`4A
`4C
`50
`52
`54
`56
`58
`SA
`
`60
`62
`64
`66
`68
`6A
`6C
`
`Binary
`Group CD
`0000001
`0100001
`0010001
`0110001
`0001001
`0101001
`0011001
`0000101
`0100101
`0010101
`0110101
`0001010
`0101101
`
`Group CC
`0000011
`0100011
`0010011
`0110011
`0001011
`0101011
`0011011
`
`FIG. 7
`
`HEX
`
`01
`21
`11
`31
`09
`29
`19
`05
`25
`15
`35
`OD
`2D
`
`Binary
`Group Dl
`0000100
`0000110
`0001000
`0001010
`0010000
`0010010
`0010100
`0010110
`0100100
`0100110
`0101000
`0101010
`0110000
`0110010
`0110100
`0110110
`
`03
`23
`13 Group 02
`33
`0000010
`OB
`0001 100
`0011000
`2B
`1B
`0011010
`0100000
`0100010
`0101100
`
`HEX
`
`04
`06
`08
`OA
`10
`12
`14
`16
`24
`26
`28
`2A
`30
`32
`34
`36
`
`02
`oc
`18
`lA
`20
`22
`2C
`
`LSI Corp. Exhibit 1009
`Page 10
`
`

`

`State 0 (S0)
`
`State 1 (S 1)
`
`State 2 (S2)
`
`State 3 (S 3)
`
`Data (HEX) Codeword
`(HEX)
`000000 (00) 1100001 (61)
`000001 (01) 1100101 (65)
`000010 (02) 1101001 (69)
`000011 (03) 1101101 (6D)
`000100 (04) 1100001 (61)
`000101 (05) 1100101 (65)
`000110 (06) 1101001 (69)
`000111 (07) 1101101 (6D)
`001000 (08) 1100000 ( 60)
`001001 (09) 1100010 (62)
`001010 (OA) 1100100 (64)
`001011 (OB) 11 00 11 0 ( 66)
`001100 (OC) 1101000 (68)
`001101 (OD) 1101010 (6A)
`001110 (OE) 11 0 11 00 ( 6C)
`001111 (OF) 1000011 (43)
`
`Next
`State
`Sz
`Sz
`Sz
`Sz
`s3
`s3
`s3
`s3
`So
`So
`So
`So
`So
`So
`So
`Sz
`
`Codeword
`(HEX)
`1001101 (4D)
`1000010 (42)
`1000100 (44)
`1000110 (46)
`1001000 (48)
`1001010 (4A)
`1001100 (4C)
`1001101 (4D)
`1010000 (50)
`1010010 (52)
`1010100 (54)
`1010110 (56)
`1011000 (58)
`1011010 (SA)
`1010001 (51)
`1010001 (51)
`
`Next
`State
`Sz
`So
`So
`So
`So
`So
`So
`s3
`So
`So
`So
`So
`So
`So
`s2
`s3
`
`Codeword
`(HEX)
`0000010 (02)
`0011000 (18)
`0011010 (lA)
`0011000 ( 18)
`00 1 1 0 1 0 ( 1 A)
`01 00000 (20)
`0000011 (03)
`0001100 (OC)
`0000011 (03)
`00 11 000 (18)
`0011010 (1A)
`0011000 (18)
`0011010 (1A)
`0100000 (20)
`0100010 (22)
`0101100(2C)
`
`Next
`State
`So
`So
`So
`sl
`sl
`sl
`s3
`So
`sz
`Sz
`sz
`s3
`s3
`So
`So
`So
`
`Codeword
`(HEX)
`0000100 (04)
`000011 0 (06)
`0001000 (08)
`0001010 (OA)
`0010000 (10)
`0010010 (12)
`0010100 (14)
`00 1 0 11 0 ( 16)
`0100100 (24)
`01 00 11 0 (26)
`0101000 (28)
`0101010 (2A)
`0110000 (30)
`0110010(32)
`0110100 (34)
`0110110 (36)
`FIG. 8A1
`
`Next
`State
`So
`So
`So
`So
`So
`So
`So
`So
`So
`So
`So
`So
`So
`So
`So
`So
`
`Lj
`•
`00.
`•
`
`~ e. a
`
`a:
`~
`N
`'"~
`~
`
`~
`
`~
`~
`
`~
`0
`~
`
`~
`~
`
`Ot
`
`'!..l w
`
`~ ._,.
`'I
`~
`00
`
`LSI Corp. Exhibit 1009
`Page 11
`
`

`

`010000 (10) 1100001 (61)
`010001 (11) 1100101 (65)
`010010 (12) 1101001 (69)
`010011 (13) 1101101 (6D)
`010100 (14) 1001011 (4B)
`010101 (15) 1011011 (5B)
`010110 (16) 1 00 1 0 11 ( 4 B)
`010111 (17) 1011011 (5B)
`011000 (18) 1100000 ( 60)
`011001 (19) 1100010 (62)
`011010 (1A) 1100100 (64)
`011011 (lB) 1100110 (66)
`011100 (lC) 1101000 (68)
`011101 (1D) 1101010 (6A)
`011110 (IE) 11 0 11 00 ( 6C)
`011111 (IF) 1000011 (43)
`
`sl
`sl
`sl
`sl
`Sz
`Sz
`s3
`s3
`sl
`sl
`sl
`sl
`sl
`sl
`sl
`s3
`
`1000101 (45)
`I 0000 1 0 ( 4 2)
`1000100 (44)
`1000110 (46)
`1001000 (48)
`10010,10 (4A)
`1001100 (4C)
`1001001 (49)
`1010000 (50)
`1010010 (52)
`1010100 (54)
`1010110 (56)
`1011000 (58)
`1011010 (5A)
`1010101 (55)
`1011001 (59)
`
`sl
`sl
`sl
`sl
`s· I
`s,
`sl
`sl
`sl
`sl
`sl
`sl
`sl
`sl
`sl
`sl
`
`0000010 (02)
`0 1 0000 1 (21)
`0010001 (11)
`0110001 (31)
`0001001 (09)
`0101001 (29)
`0011001 (19)
`0001100 (OC)
`0000101 (05)
`0100101 (25)
`0010101 (15)
`0110101 (35)
`0001101 (OD)
`0101101 (2D)
`0100010 (22)
`0101100 (2C)
`
`sl
`sl
`sl
`sl
`sl
`sl
`sl
`sl
`sl
`sl
`sl
`s,
`sl
`sl
`sl
`sl
`
`0000100 (04)
`0000110 (06)
`0001 000 (08)
`0001010 (OA)
`0010000 (1 0)
`0010010 (12)
`0010100 (14)
`0010110 (16)
`0100100 (24)
`0 1 00 11 0 (26)
`0101000 (28)
`0101010 (2A)
`011 0000 (30)
`0110010 (32)
`0110100 (34)
`0110100 (34)
`
`sl
`sl
`sl
`sl
`sl
`s,
`sl
`s,
`sl
`sl
`sl
`sl
`sl
`sl
`sl
`sl
`
`FIG. 8A2
`
`~ •
`7J1 •
`~
`~ a
`
`~
`
`~
`--~
`"""""
`\C
`~
`
`~
`m.
`"""""
`""""" s,
`"""""
`!JI
`
`til
`.,.
`;;!
`~ .,.
`.....:t
`=" 00
`
`LSI Corp. Exhibit 1009
`Page 12
`
`

`

`State 0 (S 0)
`
`State 1 (S 1)
`
`State 2 (S2)
`
`State 3 (S3)
`
`Data (HEX) Codeword
`(HEX)
`100000 (20) 1100011 (63)
`100001 (21) 0100011 (23)
`100010 (22) 0010011 (13)
`100011 (23) 0110011 (33)
`100100 (24) 0001011 (OB)
`100101 (25) 0101011 (2B)
`100110 (26) 0011011 (lB)
`100111 (27) 1101011 (6B)
`101000 (28) 1000001 (41)
`101001 (29) 1100010 (62)
`101010 (2A) 1100100 (64)
`101011 (2B) 11 00 11 0 ( 66)
`101100 (2C) 1101000 (68)
`101101 (2D) 1101010 (6A)
`101110 (2E) 11 0 1 1 00 ( 6C)
`101111 (2F) 1 0 1 00 11 (53)
`
`~-
`
`Next
`State
`s2
`s2
`s2
`s2
`s2
`s2
`s2
`s2
`s2
`s2
`s2
`s2
`s2
`s2
`s2
`s2
`
`Codeword
`(HEX)
`1000101 (45)
`1000010 (42)
`1000100 ( 44)
`I000110 (46)
`1001000 (48)
`1001010 (4A)
`1001100 (4C)
`1001001 (49)
`1010000 (50)
`1010010 (52)
`1010100 (54)
`1010110 (56)
`1011000 (58)
`1011010 (SA)
`1010101 (55)
`1011001 (59)
`
`Next
`State
`s2
`s2
`s2
`s2
`s2
`s2
`s2
`s2
`s2
`s2
`s2
`s2
`s2
`s2
`s2
`s2
`
`Codeword
`(HEX)
`0000010 (02)
`0100001 (21)
`0010001 (11)
`0 II 0001 (31)
`0001001 (09)
`0101001 (29)
`0011001 (19)
`0001100 (OC)
`0000101 (05)
`0100101 (25)
`0010101 (15)
`0110101 (35)
`0001101 (OD)
`0101101 (2D)
`0100010 (22)
`0101100 (2C)
`
`Next
`State
`s2
`s2
`s2
`s2
`s2
`s2
`s2
`s2
`s2
`s2
`s2
`s2
`s2
`s2
`s2
`s2
`
`Codeword
`(HEX)
`0000100 (04)
`0000110 (06)
`0001000 (08)
`0001010 (OA)
`0010000 (1 0)
`0010010 (12)
`0010100 (14)
`0010110 (16)
`0100100 (24)
`0100110 (26)
`0101000 (28)
`0101010 (2A)
`0110000 (30)
`0110010 (32)
`0110100 (34)
`0 11 0 11 0 (3 6)
`
`Next
`State
`s2
`s2
`s2
`s2
`s2
`s2
`s2
`s2
`s2
`s2
`s2
`82
`82
`s2
`s2
`s2
`
`FIG. 8B1
`
`•
`
`c • 00.
`~ = ~ a
`
`a=
`~
`N
`~.(;;;..
`
`1--"
`
`~
`
`~ a
`
`1--"
`N
`~
`1--"
`!.11
`
`Ot
`~ tj
`~
`~ 'I
`0\ oe
`
`LSI Corp. Exhibit 1009
`Page 13
`
`

`

`110000 (30) 1100011 (63)
`110001 (31) 0100011 (23)
`110010 (32) 0010011 (13)
`110011 (33) 0 11 00 11 ( 3 3)
`110100 (34) 0001011 (OB)
`110101 (35) 0101011 (2B)
`110110 (36) 0011011 (1 B)
`110111 (37) 1101011 (6B)
`111000 (38) 1000001 (41)
`111001 (39) 1100010 (62)
`111010 (3A) 11 00 1 00 ( 64)
`111011 (3B) 11 00 11 0 ( 66)
`111100 (3C) 1101000 (68)
`111101 (3D) 1101010 (6A)
`111110 (3E) 11 0 11 00 ( 6C)
`111111 (3F) 1 0 1 00 11 (53)
`
`s3
`s3
`s3
`s3
`s3
`s3
`s3
`s3
`s3
`s3
`s3
`s3
`s3
`s3
`s3
`s3
`
`1000101 (45)
`1000010 (42)
`1000100 (44)
`1000110 (46)
`1001000 ( 48)
`1001010 (4A)
`1001100 (4C)
`1001001 (49)
`1010000 (50)
`1010010 (52)
`1010100 (54)
`1010110 (56)
`1011000 (58)
`1011010 (SA)
`1010101 (55)
`1011001 (59)
`
`s3
`s3
`s3
`s3
`s3
`s3
`s3
`s3
`s3
`s3
`s3
`s3
`s3
`s3
`s3
`s3
`
`0000010 (02)
`0100001 (21)
`0010001 (11)
`0110001 (31)
`0001001 (09)
`0101001 (29)
`0011001 (19)
`0001100 (OC)
`0000101 (05)
`0100101 (25)
`0010101 (15)
`0110101 (35)
`0001101 (OD)
`0101101 (2D)
`0100010 (22)
`0101100 (2C)
`
`s3
`s3
`s3
`s3
`s3
`s3
`s3
`s3
`s3
`s3
`s3
`s3
`s3
`s3
`s3
`s3
`
`0000100 (04)
`000011 0 (06)
`0001000 (08)
`0001010 (OA)
`0010000 (10)
`0010010 (12)
`0010100 (14)
`0010110 (16)
`0100100 (24)
`0100110 (26)
`0101000 (28)
`0101010 (2A)
`0110000 (30)
`0110010 (32)
`0110100 (34)
`0110110 (36)
`
`s3
`s3
`s3
`s3
`s3
`s3
`s3
`s3
`s3
`s3
`s3
`s3
`s3
`s3
`s3
`s3
`
`FIG. 8B2
`
`Cj
`• 00
`•
`~
`[
`
`3:
`~
`'"t
`
`1-"
`\C)
`~
`
`g:
`~ a
`1-" w
`s,
`
`1-"
`Ul
`
`Ot
`
`'!..:~ w
`~ ._.
`....;J
`=" oc
`
`LSI Corp. Exhibit 1009
`Page 14
`
`

`

`U.S. Patent
`
`Mar. 24, 1998
`
`Sheet 14 of 15
`
`5,731,768
`
`0:::
`w
`0
`0
`0 z
`w
`
`~
`
`~
`~
`
`" ~
`~ tfl
`
`•
`
`~
`~
`
`I-
`::J
`
`0... z -
`
`LSI Corp. Exhibit 1009
`Page 15
`
`

`

`U.S. Patent
`
`Mar. 24, 1998
`
`Sheet 15 of 15
`
`5,731,768
`
`n:::
`w
`0
`0
`0 w
`ro
`~ ~ .. ,. 1't 9'
`
`o
`(
`~L-----------~
`~ ~----------~
`~ ....
`~
`
`~-
`
`~ ~ ;::...o--..-<' "r
`'-
`I
`~.._
`
`L------~
`
`n:::
`w
`w~
`~~
`1-n:::
`cnW 1-w
`
`0
`
`LSI Corp. Exhibit 1009
`Page 16
`
`

`

`5,731,768
`
`1
`METHOD AND APPARATUS FOR
`IMPLEMENTING CODES WITH MAXIMUM
`TRANSITION RUN LENGTH
`
`BACKGROUND OF THE INVENTION
`
`The present invention relates in general to information
`storage systems and, more particularly, to a method and
`apparatus for implementing maximum transition run (MTR)
`codes in a digital data magnetic recording system. In digital
`data magnetic recording systems, digital data is recorded in
`a moving magnetic media layer by a storage, or ''write"
`electrical current-to-magnetic field transducer, or ''head",
`positioned immediately adjacent thereto. The data is stored
`or written to the magnetic media by switching the direction
`of flow of a substantially constant magnitude write current
`which flows through windings in the write transducer. Each
`write current direction transition results in a reversal of the
`magnetization direction in that portion of the magnetic
`media just passing by the transducer during current flow in
`the new direction, with respect to the magnetization direc(cid:173)
`tion in the media induced by the previous current flow in the
`opposite direction. In one scheme (NRZI), a magnetization
`direction reversal over a portion of the media moving past
`the transducer represents a binary digit "1", and the lack of
`any reversal in that portion represents a binary digit "0".
`When such recorded data is to be recovered, a retrieval, or
`''read" magnetic field-to-voltage transducer, (which may be
`the same as the write transducer if both are inductive) is
`positioned to have the magnetic media, containing previ- 30
`ously stored data, pass thereby such that flux reversal
`regions in that media either induce, or change a circuit
`parameter to provide, a voltage pulse to form an output read
`signal for that transducer. Such a read signal has an analog
`character in the recording retrieval process. In the scheme 35
`described above, each such voltage pulse due to the mag(cid:173)
`netizations in corresponding media portions is taken to
`represent a binary digit "1" and the absence of a pulse in
`correspondence with such portions because of no magneti(cid:173)
`zation reversals therein is taken to represent a binary digit 40
`"0''~
`In digital magnetic recording systems, the times between
`voltage pulses are used to reconstruct the timing information
`concerning the time base used in recording the data previ(cid:173)
`ously stored in the magnetic media to define the path 45
`portions described above. More specifically, the output of
`the read signal information detector is used as an input signal
`to a phase-locked loop forming a controlled oscillator, or
`phase-lock oscillator (PLO), or synchronizer, which pro(cid:173)
`duces an output clock signal from the positions of the so
`detected peaks of the read signal. In other words, the PLO
`locks the phase of the timing clock signal to the phase of the
`signal resulting from peak detection of the read signal
`voltage pulses. Absolute time is not used in operating the
`data retrieval system portion since the rotational speed of the 55
`motor which drives the magnetic media varies over time
`both during recording and retrieval which results in nonuni(cid:173)
`form time intervals between read signal voltage pulses.
`A data encoding scheme known as run-length-limited
`(RLL) coding is commonly used to improve the PLO's 60
`reconstructed clock signal accuracy based on avoiding drift
`in the frequency thereof because of too much time occurring
`between successive voltage read signal pulses. When RLL
`code is employed, the time durations between read signal
`voltage pulse transitions is bounded, that is, effectively, the 65
`number of binary digits of value "0" that can separate binary
`digits of value "1" in the read signal is limited. This
`
`15
`
`10
`
`2
`constraint is known overall as a ( d,k) constraint where the
`individual constraint "d" represents the minimum run length
`of zeros, or the number thereof between ones, while the
`individual constraint "k" represents the maximum run length
`5 of zeros permitted. The "d" portion of the constraint can be
`chosen so as to avoid crowding of voltage pulses in the read
`signals which can reduce intersymbol interference problems
`in which portions of read signal voltage pulses overlap. By
`limiting the number of consecutive zeros, the "k" constraint
`maintains the reliability of the PLO in providing an accurate
`clock signal for the retrieval system. An automatic gain
`control (AGC) system is usually used to maintain signal
`amplitude in the retrieval signal processing channel, and the
`"k" restraint also maintains the reliability of the AGC.
`As the recording densities become greater, the result is
`that transitions representing binary "1's" become recorded
`very close to each other in the magnetic media such that
`severe intersymbol-interference results. At densities consid(cid:173)
`erably greater than those in currently commercially available
`20 products, the most likely error sequence has been demon(cid:173)
`strated to consist of write patterns that contain three or more
`unspaced consecutive transitions. A class of block codes that
`limits the number of consecutive symbol transitions, typi(cid:173)
`cally representing binary "l's", are known as maximum
`25 transition run (MTR) codes. To avoid three or more con(cid:173)
`secutive transitions, codes with MTR values (no more than
`two successive binary "1 's" in the coding result) equal to
`two are desirable.
`When data is encoded into codewords that satisfy certain
`constraints, data words (blocks of successive coding sym(cid:173)
`bols typically binary "1 's" and ''O's'') having ''rn" successive
`bits are translated into code words (blocks of successive
`coding symbols again typically binary "1's" and "O's")
`having "n" bits where "n" is greater than ''rn". The ratio
`"m/n" of the data word symbol length to the codeword
`symbol length is known as the code rate, "r". The upper
`bound of the MTR=2 code rate in which k=oo has been found
`to be 0.8791 as indicated in the Seagate Annual Report. This
`upper bound is also known as the capacity of the code. This
`means there exists MTR codes with MTR=2 that map m data
`bits into n code bits as long as the ratio of m to n is smaller
`than 0.8791. For practical implementation, m and n are
`usually chosen to be small integers and the ratio m/n is as
`close to the code capacity as possible.
`To design a MTR code with MTR=2 having a rate of m/n
`and using one-to-one block mapping in which the "m" data
`symbols, or binary data bits, in a block are mapped into the
`"n" code symbols, or binary data bits, in a block, an
`exhaustive search of the possible n bit blocks is used to find
`2m different n-bit words which satisfy the MTR=2 con(cid:173)
`straint. In addition, in order for these words to satisfy the
`MTR=2 constraint when concatenated as code words, the bit
`patterns therein must begin and end with '00', '01' or '10'.
`That is, bit patterns can be considered in these words found
`in the exhaustive search which start or end with '11' and
`those words can be invalidated insofar as being used as code
`words. For instance, if n=5 and if one removes all the 5-bit
`words having three or more consecutive "1's", having bit
`patterns that start or end with '11', and the all zero bit pattern
`word, there are exactly 2 4 or 16 words which remain. This
`is just enough to form a 4/5 rate MTR code with MTR=2
`using one-to-one mapping between the data words and the
`code words.
`However, when attempting to extend this method to a 5/6
`rate MTR code with MTR=2, there are only thirty words
`with valid bit patterns available, two short of the 25 or 32
`words required. Although one may achieve the same code
`
`LSI Corp. Exhibit 1009
`Page 17
`
`

`

`5,731,768
`
`4
`DETAilED DESCRIPTION OF THE
`PREFERRED EMBODIMENTS
`
`3
`rate by mapping 10-bit data words to 12-bit data words, the
`210 or 1024 code words will significantly complicate the
`encoder and decoder which use Boolean logic to implement
`the bit pattern mapping. Thus, in the context of the above
`example, there is a desire to provide an encoding algorithm 5
`which satisfies the MTR=2 constraint that is easy to imple(cid:173)
`ment using Boolean logic and is not limited by invalid
`patterns beginning or ending with '11 '. Of course, the
`present invention is not limited to such codes which satisfy
`the MTR=2 constraint. but rather is applicable to any such 10
`code regardless of the coding constraints chosen.
`
`20
`
`SUMMARY OF THE INVENTION
`The present invention provides a system for encoding
`selected data blocks having selected ordered symbols therein
`into corresponding code blocks having selected ordered
`symbols therein numbering more than the symbols in the
`data blocks with the data blocks received at a receiver in the
`system. An encoder provides a corresponding said code
`block for each of the data block. such that each of the code
`blocks, and any concatenations thereof, are without more
`than a preselected number of successive repetitions of a first
`symbol throughout. and without more than a preselected
`number of successive repetitions of a second symbol
`throughout. In addition, any of said code blocks that can be
`provided for more than one of different ones of the data
`blocks, in coming to the receiver to represent a data block.
`comes in a concatenation of code blocks such that such that
`a code block that can represent more than one different data
`block comes to the receiver together with at least one other
`code block in the concatenation so that they are together
`sufficient to determine which of the different ones of the data
`blocks that could be represented is being represented. The
`symbols in the blocks can be from the binary number
`system.
`
`To achieve a m/n rate equal to 5/6 in an MTR code with
`MTR=2 using code words of 6 bits in length (n=6), an initial
`list is provided of all such 6 bit words including those that
`begin or end with bit patterns '11'. According to the present
`invention, these 6-bit words are assigned to branchings to
`the next state during a state transition from a selected
`corresponding state in a finite state machine represented by
`a two-state trellis diagram in such a manner that invalid
`patterns (three or more consecutive 1's) do not occur when
`these code words are concatenated. Referring to FIG. 1, the
`two states in the trellis diagram are indicated there as state
`S0 and state S1 which have been found to be sufficient in
`15 number for this code. Two branches are shown leading into
`and out of each of the states S0 and S1 if viewed across the
`entire diagram, but with each of the branches shown in fact
`representing several branches in parallel.
`As shown in FIG. 2, an exhaustive search of this initial list
`is made to find all of the 6-bit words in the list having bit
`patterns therein which satisfy the MTR=2 constraint results
`in the listing shown there after being divided into four
`selected groups of words based on selected bit patterns in
`25 those words:
`Group A: '1XXXX1' (9 different words),
`Group B: '1XXXXO' (11 different words),
`Group C: 'OXXXX1' (11 different words),
`Group D: 'OXXXXO' (12 different words),
`30 where X represents either a "1" or an "0". This grouping is,
`as indicated, based on the bit patterns of the two end bits in
`each of these words.
`In order to limit the resulting code to having the MTR
`value therefor equal to two in concatenations of the code
`35 words resulting from successive transmissions thereof, con(cid:173)
`straints are imposed on the transition branches in the trellis
`BRIEF DESCRIPTION OF THE DRAWINGS
`diagram so that the branches may only be associated with
`=a. 1 t"s a two-state trellis diagram for associating
`certain code words having suitable bit patterns to avoid the
`r..
`occurrence of three or more successive "1 • s". If all code
`concatenated code word bit patterns with each other accord-
`ing to the present invention;
`40 words arising upon state transitions leaving states along
`branches leading to a state S
`in the diagram have bit
`F1G. 2 is a table illustrating all of the 6obit binary patterns
`0
`patterns that are restricted to those that end with '0', code
`which satisfy the MTR=2 constraint according to the present
`words arising upon a subsequent state transition along
`invention;
`branches leaving that S0 state can be from any group. If all
`F1G. 3 is a code word assignment and next state table of
`a 5/6 rate MTR=2. k=9 code according to the present 45 code words arising upon state transitions along branches
`leaving a state sl in the diagram have bit patterns that are
`invention;
`F1G. 4A is a block diagram of an encoder for the 5/6 rate
`restricted to those that begin with '0', code words arising in
`code of F1G. 3;
`an immediately preceding state transition along branches
`F1G. 4B is a block diagram of a decoder for the 5/6 rate
`leading to that state S1 can be from any group. As a result
`50 of following these constraints, the above code word groups
`code of F1G. 3;
`are acceptable to arise along each branch as listed below:
`FIG. 5 is a four-state trellis diagram for associating
`S0 to S0 Branch: Groups B and D (end with ''0"),
`concatenated code word bit patterns with each other accord-
`ing to another embodiment of the present invention;
`S0 to S 1 Branch: Groups A, B and D (all but these chosen
`FIG. 6 is a table illustrating all of the 7-bit binary patterns 55
`to allow a unique state assignment as set out below)
`S1 to S0 Branch: Groups D (begin and end with "0"),
`which satisfy the MTR=2 constraint according to the present
`invention;
`S1 to S 1 Branch: Groups C and D (begin with "0").
`FIG. 7 is a table of sub-groups of the 7 -bit patterns which
`In order to make the code words uniquely decodable and
`satisfy the MTR=2 constraint according to the present
`limit the error propagation, code words arising upon leaving
`invention;
`60 each state in a state transition must be unique. That means
`FIGS. SA and 8B are a code word assignment and next
`each code word cannot be used upon transitions from more
`state table of a 6n rate MTR=2, k=9 code according to the
`than one state. Groups A and B are assigned so that code
`present invention;
`words arise therefrom upon state transitions along branches
`F1G. 9A is a block diagram of an encoder for the 6/7 rate
`leaving just state S0 in view of their association with
`code of F1G. 8; and
`65 branches leaving that state as shown above, and Groups C
`F1G. 9B is a block diagram of a decoder for the 6n rate
`and Dare assigned so that code words arise therefrom upon
`code of F1G. 8.
`state transitions along branches leaving state S1 for that
`
`LSI Corp. Exhibit 1009
`Page 18
`
`

`

`5,731,768
`
`10
`
`15
`
`[Eq. 1]
`
`Since data words in this first group for state transitions
`from either state S0 or state S1 have the next state as S0 , and
`the data words from the second group do not, negating KK
`and placing it in an OR relationship with the fourth data
`word digit A4 allows the next state to be expressed by the
`equation
`
`[Eq. 2]
`
`for use in encoder 15. Ns=O represents state S0 as the next
`state, and Ns=l represents state S1 as the next state.
`The bits of the code words arising on branchings from
`state S0 during state transitions as set out in the table of FIG.
`3 can be expressed as follows for use in encoder 15:
`
`6
`well known manners based on forming a finite state machine
`therewith. Alternatively, such encoders and decoders can be
`similarly implemented in a microprocessor, or
`microprocessors, in well known manners.
`In the encoder system shown in block diagram form in
`FIG. 4A, each input data word of five bits A4 , A3 , A2, A1 and
`Aa is successively supplied to a clocked five bit input
`register, 10, as the data word receiver at a system input, 11,
`during a corresponding period of the system clocking signal
`supplied at a clock signal input, 12. Each such input data
`word stored in input register 10 is transferred during the next
`clock period from an output, 13, of that register into an input,
`14, of an encoder, 15, comprising a finite state machine
`based on the table in FIG. 3 to be encoded into a code word
`of six bits C5 , C4 • C3 , C2 , C1 and C0 provided at a code word
`output, 16, of that encoder. From the table of FIG. 3, we can
`see the input data words are divided into two groups. The
`first group of data words extends '00' to 'OA' (hex) and, for
`state transitions from either state S0 or state S 1, has state S0
`as its next state. The second group of data words extends
`from 'OB' to '1F' (hex) and, for state transitions from either
`state S0 or state S1 , has state S1 as its next state. Data words
`can be identified as being from two sublists in the data word
`listing, data words in the listing from '00' (hex) to 'OA' (hex)
`and from '10' (hex) to '1A' (hex), by the following expres(cid:173)
`sion taking a Boolean value of 1:
`
`5
`same reason. However, since this is a 5/6 rate code, 25 or 32
`different code words are necessary for transitions from each
`state so that a data word can be represented by each such
`transition, but code words assigned for branchings from a
`selected state can be repeated for branchings from that state 5
`to each of the different next states branched to therefrom
`since they will still be uniquely decodable because of their
`differing next state characteristics. The use of the fewest
`states possible, of course, tends to reduce complexity and
`cost.
`One code word '011010' from Group D is therefore
`moved to arise on transitions from state S0 (which group is
`also associated with branches leaving that state in the second
`listing above) to thereby provide 32 code words available to
`arise on transitions from that state. As a result, that moved
`code word now forms Group D" leaving the rest of former
`Group D to now form Group D'. The code words are, as a
`result, distributed to the branches as follows:
`From S0 to S0 : B (