United States Patent [191
`Shimoda et a1.
`
`USOO5341386A
`Patent Number:
`[11]
`[45] Date of Patent:
`
`5,341,386
`Aug. 23, 1994
`
`[54] VITERBI EQUALIZER AND
`RECORDING/REPRODUCING DEVICE
`USING THE SAME
`[75] Inventors:
`Kaneyasu Shimoda; Hideto
`Furukawa, both of Kawasaki, Japan
`Assignee:
`[73]
`Fujitsu Limited, Kawasaki, Japan
`[21]
`Appl. No.: 705,065
`[22] Filed:
`May 23, 1991
`[30]
`Foreign Application Priority Data
`May 25, 1990 [JP]
`Japan ................................ .. 2-136226
`
`[51] Int. (:1.5 ............................................ .. G06F 11/10
`[52] US. 01.
`371/43
`[58] Field of Search ............... .. 371/43, 44, 37.1, 37.2,
`371/37.3, 37.4, 37.6, 37.7, 37.8, 37.9, 43, 44
`References Cited
`U.S. PATENT DOCUMENTS
`
`[56]
`
`4,763,328 0/1988 Shirnoda et al. ...................... .. 371/3
`4,823,346 4/1989 Kobayashi et a1.
`371/43
`4,870,414 9/1989 Karabed et al.
`341/57
`4,945,538 7/1990 Patel ................ ..
`371/43
`5,042,036 .8/1991 Fettweis .............................. .. 371/43
`5,136,593 8/1992 Moon et a1. ..................... .. 371/43
`5,257,272 10/1993 Fredrickson ........................ .. 371/43
`
`OTHER PUBLICATIONS
`Shung et al “Area-Efficient Architectures for the
`Viterbi Algorithm” IEEE 1990 pp. 1787-1793.
`Fredrickson et al “Error Detecting Multiple Block (d,k) 9
`Codes” IEEE Trans. on Magnetics vol. 25 No. 5 Sep.
`1989.
`French et a], “Performance Comparison of Combined
`ECC/RLL Codes” IEEE 1990 pp. 1717-1722.
`Mouldin et al, “A New Path Metric for Survivable
`Circuit Switched Routing” IEEE 1989 pp. 0688-0692.
`French “Distance Preserving Run-lengthy Limited
`
`Codes” IEEE Transactions on Magnetics, vol. 25 No. 5
`Sep. 1989.
`Lin et al “Combined ECC/RLL Codes” IEEE Trans
`actions or Magnetics vol. 24, No. 6, Nov. 1988.
`Francis R. Magree, Jr. et al., “Adaptive Max
`imum-Likelihood Sequence Estimation for Digital Sig
`naling in the Presence of Intersymbol Interference”,
`IEEE Transaction of Information Theory, Jan. 1973,
`pp. 120-124.
`W. Toms et a1., “Maximum-Likelihood Sequence Esti
`mation of Diginal Sequences in the Presence of Inter
`symbol Interfernce”, IEEE Transactions of Informa
`tion Theory, Jan. 1972, pp. 363-378.
`
`Primary Examiner-Robert W. Beausoliel, Jr.
`Assistant Examiner-Joseph E. Palys
`Attorney, Agent, or 'Firmé-staas & Halsey
`
`ABSTRACT
`[57]
`A viterbi equalizer includes a distributor for receiving a
`run length limited code and for calculating branch met
`rics responsive to the [run length limited code. The
`branch metrics are related to only nodes and branches
`in a trellis state transition diagram based on a viterbi
`decoding algorithm de?ned for the run length limited
`code. The viterbi equalizer also includes a path metric
`calculating circuit, operatively coupled to the distribu
`tor, for generating path metrics on the basis of the
`branch metrics and for generating path select signals
`indicative of surviving paths coupling the nodes and
`. branches. Further, the viterbi equalizer includes a path
`memory, operatively coupled to the path metric calcu
`lating circuit, for determining a maximum likelihood
`. path on the basis of the path select signals output by the
`path metric calculating circuit.
`
`10 Claims, 12 Drawing Sheets
`
`ACS CIRCUIT 1 2 O
`
`LSI Corp. Exhibit 1008
`Page 1
`
`

`

`U.S. Patent
`
`Aug. 23, 1994
`
`Sheet 1 of 12
`
`5,341,386
`
`UZHDMODBN
`
`azmmmpo
`
`ozHomoomm
`
`ezammso
`
`kt.‘moim\GI
`
`NMV\k
`
`meBwe
`
`.23.most.NGI
`
`mm
`
`\®
`
`czaomooam
`
`.ezmmm:o
`
`ZOHBODDOEQHZ
`
`ezmmmou
`
`zOHB<OHJmHBJDENU<D0
`MBZEHOHERHOU
`xzqmLmu<x<mqa
`
`U<&<EJ
`
`xoaa
`
`LS|ComxExmbH1008
`Pagez
`
`LSI Corp. Exhibit 1008
`Page 2
`
`
`
`

`

`US. Patent
`
`Aug. 23, 1994
`
`Sheet 2 of 12
`
`5,341,386
`
`FIG
`. 3 PRIOR ART
`
`//7
`
`
`
` a <B<Q UZHDMOOHM
`
`UZHEODQOQQHG
`
`\UZHQGODHG
`
`, EHBMMM
`
`a
`
`REPRODUCTION
`DATA
`
`—>
`
`CLOCK
`EXTRACTER
`
`/5
`/
`
`FIG|4 PRIOR ART
`
`LSI Corp. Exhibit 1008
`Page 3
`
`

`

`U.S. Patent
`
`Aug. 23, 1994
`
`Sheet 3 of 12
`
`5,341,386
`
`F/G.5 PRIOR ART
`
`-II‘-H
`I,
`}
`ADD
`52 L __________ .___! P5-2
`
`I
`:
`I
`
`DITTO
`
`.
`
`I
`:
`I
`
`9
`
`DITTO
`
`L —————————— ——3 PS-3
`53» —————————— “-1
`g
`1
`'
`.
`;
`I
`I
`._ _________ ____J Ps-4
`54-‘sf ‘ * - — — ‘ - — * — "-1
`/
`I
`I
`:
`I
`I
`L _________ ____§
`
`DITTO
`
`'
`
`>4
`
`§
`cg
`5
`<
`W
`
`g_____v__:__J
`ACS CIRCUIT 5
`
`5
`
`LS|ComxExmbH1008
`Page4
`
`LSI Corp. Exhibit 1008
`Page 4
`
`

`

`U.S. Patent
`
`Aug. 23, 1994
`
`Sheet 4 of 12
`
`5,341,386
`
`VEVG NOILOflGOHdEH
`
`dd
`
`TBS
`
`TBS
`
`dd
`
`WES
`
`dd
`
`13$
`
`.53.moim©.®\.l
`
`
`--S-_.mj~sdS\mamamo
`an:III:1I—Mnml
`
`udddEI—__d__mII
`.I__._..l_L._\dS
`
`SSS\
`
`\-mm
`
`NIWQ
`
`LSI Corp. Exhibit 1008
`Page 5
`
`LSI Corp. Exhibit 1008
`Page 5
`
`

`

`U.S. Patent
`
`Aug. 23, 1994
`
`Sheet 5 of 12
`
`5,341,386
`
`VLVG
`NOILOflGOHdEH
`
`DECODER
`
`VITERBIEQUALIZER
`
`DZI
`
`-I
`
`FlG.7
`
`BD:
`
`3D
`
`E
`OE!
`0:54
`D..U.2
`13>!
`RICO
`
`RECORDING/
`
`
`
`RLLCOfJE
`
`ENCODER
`
`VLVG SNIQHOOEH
`
`.LS| Corp. Exhibit 1008
`Page 6
`
`LSI Corp. Exhibit 1008
`Page 6
`
`

`

`U.S. Patent
`
`Aug. 23, 1994
`
`Sheet 6 of 12
`
`5,341,386
`
`ZOH BD:
`
`3DOn
`
`:<
`0.9
`tr: <
`(IO
`
`
`
`2%
`c:
`o
`
`0c
`
`aD
`
`In
`‘*3
`3.53
`fig
`E4
`I489
`>13]
`
`
`
`V1“
`O
`\
`
`Yr
`I
`
`(I:
`E
`D
`<(11
`B
`"‘
`Ea
`
`U
`
`3DO.
`
`
`
` WECLSXS
`Dl\II.I.0flClOEcI{HH
`/DNICIHOOEIH
`
`ENCODER
`
`LSI Corp. Exhibit 1008
`Page 7
`
`D2F
`
`!
`C3
`[11
`O<'.
`DE-*
`Efl<
`(IQ
`
`21
`
`N)
`O
`\
`
`FIG.8
`
`LSI Corp. Exhibit 1008
`Page 7
`
`

`

`US. Patent
`
`Aug. 23, 1994
`
`Sheet 7 of 12
`
`5,341,386
`
`RLLH, 7), 3 TAPS
`
`LSI Corp. Exhibit 1008
`Page 8
`
`

`

`US. Patent
`
`Aug. 23, 1994
`
`Sheet 8 of 12
`
`5,341,386
`
`FIGJO
`
`F l I I » l I]
`
`m R R :R' R .IRI + On
`Q P.0d PM,‘ a‘ Q Am]
`
`w m M .0 .0 w m % % my I0 w mu k1
`
`+ + _ + .I .I
`
`&2
`31 >
`
`D D D D A A
`
`3 \
`
`M C 4
`v2 P
`
`P LM 0
`
`\Llp /
`
`_
`
`_ w \ ,
`
`wmozmzma‘qm (w
`
`v
`
`ACS CIRCUIT 1 2 0
`
`LSI Corp. Exhibit 1008
`Page 9
`
`

`

`U.S. Patent
`
`Aug. 23, 1994
`
`Sheet 9 of 12
`
`5,341,386
`
`I;I1d.I:I1O
`GEZITVHUEE
`
`:.eI
`
`LS|ComxExmbH1008
`Page10
`
`LSI Corp. Exhibit 1008
`Page 10
`
`

`

`US. Patent
`
`Aug. 23, 1994
`
`Sheet 10 of 12
`
`5,341,386
`
`RLL(2,7), 4 TAPS
`
`LSI Corp. Exhibit 1008
`Page 11
`
`

`

`U.S. Patent
`
`Aug. 23, 1994
`
`Sheet 11 of 12
`
`5,341,386
`
`Lfld&HO
`GEOOOEG
`
`dVlHW3W0HX
`
`BHDUSHOmo<
`
`LS|ComxExmbH1008
`Page12
`
`LSI Corp. Exhibit 1008
`Page 12
`
`

`

`US. Patent
`
`Aug. 23, 1994
`
`Sheet 12 of 12
`
`5,341,386
`
`hrm
`
`4mm A
`
`p ». » »
`
`E 15w E I Jam E 1 £5 E Sm o G
`
`> v » TIA
`
`2 L
`
`a .E _ E _ E \ w mm
`
`.5 T’ E E \ V mm
`
`E _ E _ E o W wm
`
`5 4mm 5 I 15w 1 E 1 4mm E Jam TM #8
`
`mm E E o w mm
`
`LSI Corp. Exhibit 1008
`Page 13
`
`

`

`1
`
`VITERBI EQUALIZER AND
`RECORDING/REPRODUCING DEVICE USING
`THE SAME
`
`20
`
`5,341,386
`2
`and branches of the trellis state transition diagram of
`FIG. 4 based on the viterbi decode algorithm.
`FIG. 5 shows the entire structure of such a conven
`tional decision circuit. The reproduction current output
`from the read head 72 (FIG. 1) of the recording/repro
`ducing system 12 (FIG. 3) passes through the A/D
`converter 13, and is then input, as a reproduction signal
`R, to a distributor 4 of the viterbi equalizer 17. The
`distributor 4 calculates a branch metric BM related to
`each node with respect to the digital reproduction sig
`nal R obtained at the present time. In the distributor 4
`shown in FIG. 5, the branch metric BM is de?ned by
`calculating the Euclidean distance. Instead of the Eu
`clidean distance, it is possible to use an alternative code
`distance, such as the Hamming distance. The branch
`metrics BM calculated by the distributor 4 are input to
`an ACS (Adder, Comparator and Selector) circuit 5.
`The ACS circuit 5 is comprised of four ACS units
`51-54 respectively corresponding to the four nodes.
`The ACS units 51-54 each include adders (ADD), a
`comparator (COMP) and a selector (SEL), and are
`connected so that the trellis state transition diagram of
`FIG. 4 can be formed. Each of the ACS units 51-54
`adds the current branch metric BM calculated by the
`distributor 4 and a path metric which is related to the
`immediately previous timing (via the feedback path)
`and which is calculated by the ACS circuit 5, and calcu
`lates two current path metrics PM of the two paths on
`the input side of the corresponding node. The compara
`tor COMP of each of the ACS units 51-54 compares the
`two path metrics with each other, and instructs the
`selector SEL to select, as a surviving path, one of the
`two paths which has a path metric smaller than that of
`the other path. The path metric related to the selected
`surviving path is fed back to the input side of each of the
`ACS units 51-54. Path select signals PS-l, PS-2, PS-3
`and PS4 used for respectively selecting the surviving
`paths in the ACS units 51-54 are input to a path mem
`ory 6. The path memory 6 convolutionally generates
`and records the locus of a maximum likelihood path
`based on the path select signals PS-l through PS-4.
`FIG. 6 is a block diagram of the path memory 6
`shown in FIG. 5. The path memory 6 has a plurality of
`unit circuits, each having a selector SEL and a ?ip-?op
`FF, the latter serving as a latch circuit. The unit circuits
`are arranged so that the trellis state transition diagram
`of FIG. 4 is formed. Each selector SEL is controlled by
`one of the path select signals PS-l through PS-4.
`In conventional viterbi equalizers as mentioned
`above, it is necessary to use a long constraint length in
`order to precisely perform the equalization. As the
`constraint length increases, the number of internal
`states, that is, the number of nodes increases exponen
`tially, and thus the hardware scale increases exponen
`tially. If the precise equalization is implemented by
`software, the number of steps of the maximum likeli
`hood path determination program increases exponen
`tially as the constraint length increases.
`
`45
`
`BACKGROUND OF THE INVENTION
`The present invention generally relates to a viterbi
`equalizer which eliminates intersymbol interference
`which may take place in a data reproduction system of
`a recording/ reproducing device, such as a magnetic
`disk device. Further, the present invention is concerned
`with a recording/reproducing device using such a
`viterbi equalizer.
`Recently, there has been considerable activity in the
`development of small-size, large capacity magnetic disk
`devices. It is known that, as the storage density on a
`magnetic disk increases, the distance between two adja
`cent recorded bits decreases. More speci?cally, as
`shown in FIG. 1, recorded bits b1 and b2 are adjacent to
`each other in the radial direction of the magnetic disk,
`and recorded bits b1 and b3 are adjacent to each other
`in the same direction. A read head 72 is positioned im
`mediately above the bit b1. In this state, the read head
`72 receives leakage ?uxes resulting from the bits b2 and
`25
`b3. Thus, a reproduction (read) current output by the
`read head 72 is affected by intersymbol interference.
`FIG. 2 is an equivalent circuit of the transfer function
`of a recording/reproducing model of the above-men
`tioned high recording density magnetic disk device. A
`recording current (write data) input to a write head 71
`shown in FIG. 1 is sequentially applied to delay ele
`ments 81 and 82 connected in series. Multipliers 83, 84
`and 85 multiply the recording currents of different tim
`ings by multiplication coef?cients G0, G1 and G2, re
`spectively. An adder 86 adds output signals of the multi
`pliers 83, 84 and 85, and outputs the reproduction cur
`rent (read data).
`It will be noted that the recording/reproducing
`model shown in FIG. 2 is a convolutional encoder.
`Thus, it is possible to decode the reproduction current
`output by the recording/reproducing model by means
`of a viterbi decoder, so that the intersymbol interfer
`ence can be eliminated using an error correction func
`tion of the viterbi decoder (see US. Pat. No. 4,763,328,
`the disclosure of which is hereby incorporated by refer
`ence).
`FIG. 3 shows a magnetic disk device using a conven
`tional viterbi equalizer. Recording (write) data is writ
`ten into a recording/ reproducing system 12, which
`outputs a reproduction (read) current. This reproduc
`tion current is converted into a digital signal by an
`analog-to-digital (A/D) converter 13. The digital signal
`is input to a viterbi equalizer 17, which eliminates an
`intersymbol interference and outputs reproduction data.
`A clock extracter 15 extracts a timing clock from the
`recording/reproducing system 12. The extracted timing
`signal is applied to the A/D converter 13 and the viterbi
`equalizer 17.
`FIG. 4 is a trellis state transition diagram of a viterbi
`equalizer con?gured with the constraint length equal to
`3. It will be noted that 0 and l of the internal state of
`each node correspond to —1 and +1 of the reproduc
`tion current, respectively, and there are four states (-1,
`-l), (— 1, +1), (+1, -l) and (+1, +1). A decision
`circuit in the viterbi equalizer which selects a maximum
`likelihood path is con?gured so that it forms the nodes
`
`SUMMARY OF THE INVENTION
`It is a general object of the present invention to pro
`vide an improved viterbi equalizer in which the above
`mentioned disadvantages are eliminated.
`A more speci?c object of the present invention is to
`provide a compact, less expensive viterbi equalizer.
`The above-mentioned objects of the present inven
`tion are achieved by a viterbi equalizer comprising:
`distributor means for receiving a run length limited
`
`65
`
`LSI Corp. Exhibit 1008
`Page 14
`
`

`

`5,341,386
`3
`4
`code and for calculating branch metrics responsive to
`FIG. 12 is a trellis state transition diagram of the
`the run length limited code, the branch metrics being
`viterbi equalizer in which the constraint length is 4 and
`related to only nodes and branches in a trellis state
`an RLL (2, 7) code is used;
`transition diagram based on a viterbi decoding algo
`FIG. 13 is a block diagram of the viterbi equalizer in
`rithm de?ned for the run length limited code; path
`which the constraint length is 4 and the RLL (2, 7) code
`metric calculating means, operatively coupled to the
`is used; and
`distributor means, for generating path metrics on the
`FIG. 14 is a block diagram of a path memory in
`basis of the branch metrics and for generating path
`which the constraint length is 4 and the RLL (2, 7) code
`select signals indicative of surviving paths coupling the
`is used.
`nodes and branches; and path memory means, opera
`tively coupled to the path metric calculating means, for
`determining a maximum likelihood path on the basis of
`the path select signals output by the path metric calcu
`lating means.
`Another object of the present invention is to provide
`a recording/reproducing device having the above-men
`tioned viterbi equalizer.
`,This object of the present invention is achieved by
`the recording/reproducing device comprising: encoder
`20
`means for encoding recording data into a run length
`limited code; recording/reproducing means, opera
`tively coupled to the encoder means, for recording the
`run length limited code on a recording medium and for
`reproducing the run length limited code from the re
`cording medium; viterbi equalizing means, operatively
`coupled to the recording/ reproducing means, for equal
`izing the run length limited code reproduced by the
`recording/reproducing means and for generating an
`equalized run length limited code; and decoder means,
`operatively coupled to the viterbi equalizing means, for
`decoding the equalized run length limited code in order
`to generate reproduced data. The viterbi equalizer is
`con?gured as mentioned above.
`
`30
`
`15
`
`25
`
`DESCRIPTION OF THE PREFERRED
`EMBODIMENTS
`Referring to FIG. 7, a recording/reproducing device
`according to the present invention includes an encoder
`101, a recording/ reproducing system 102, a viterbi
`equalizer 103 and a decoder 104. The encoder 101 en
`codes recording data into run length limited code data
`(hereafter simply referred to as RLL code data). The
`recording/reproducing system 102 records the RLL
`code data on a recording medium, such as a magnetic
`disk, and reproduces the RLL code data from the re
`cording medium. The viterbi equalizer 103 equalizes the
`RLL code data read out from the recording medium.
`The decoder 104 decodes the equalized RLL code data
`output by the viterbi equalizer 103, and generates repro
`duction data.
`The viterbi equalizer 104 has the functions of elimi
`nating the intersymbol interference which takes place in
`the recording/reproducing system 102. It should be
`noted that the viterbi equalizer 103 equalizes the RLL
`code. A viterbi decoding algorithm de?ned for use with
`an RLL code does not particular have state transitions
`inherent in the RLL code. In other words, there are
`state transitions which do not take place due to the rule
`of the RLL code. With the above in mind, a maximum
`likelihood path determination circuit provided in the
`viterbi equalizer 104 does not have any structural ele
`ments related to the state transitions which do not take
`place due to the rule of the RLL code.
`FIG. 8 shows a magnetic disk device which has a
`viterbi equalizer according to a preferred embodiment
`of the present invention. In FIG. 8, those parts which
`are the same as those shown in FIG. 7 are given the
`same reference numerals. The viterbi equalizer 103 is
`composed of an A/D converter 113, a viterbi equalizer
`114 and a clock extracter 115. The recording data is
`encoded into a magnetic recording code (RLL code) by
`the encoder 101, and recorded on a magnetic disk of the
`recording/reproducing system 102. A reproduction
`current read out from the recording/reproducing sys
`tem 102 is equalized in order to eliminate the intersym
`bol interference from the reproduction current. An
`equalized reproduction current (equalized reproduced
`RLL code) is input to the decoder 104, which generates
`reproduced recording data.
`More speci?cally, the RLL code data read out from
`the recording/reproducing system 102 is converted into
`digitized RLL code data by the A/D converter 113.
`The viterbi equalizer 114 equalizes the digital RLL
`code data in synchronism with a clock signal extracted
`from the readout RLL code data by the clock extracter
`115.
`It will be noted that there are various formats of the
`RLL code. Now, an RLL (1, 7) code will be consid
`ered. The RLL (1, 7) code is generated in accordance
`with the following generation rule.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`Other objects, features and advantages of the present
`invention will become more apparent from the follow
`ing detailed description when read in conjunction with
`the accompanying drawings, in which:
`FIG. 1 is a diagram showing a recording/reproduc
`ing mechanism of a conventional magnetic disk device;
`FIG. 2 is a diagram showing a recording/reproduc
`ing model of the magnetic disk device shown in FIG. 1;
`FIG. 3 is a block diagram of a conventional magnetic
`disk device;
`FIG. 4 is a state transition diagram of a conventional
`viterbi equalizer;
`FIG. 5 is a block diagram of a conventional viterbi
`equalizer;
`FIG. 6 is block diagram of a path memory used in the
`conventional viterbi equalizer shown in FIG. 5;
`FIG. 7 is a block diagram showing an outline of a
`recording/reproducing device according to the present
`invention;
`FIG. 8 is a magnetic disk device having a viterbi
`equalizer according to a preferred embodiment of the
`present invention;
`FIG. 9 is a trellis state transition diagram of the
`viterbi equalizer in which the constraint length is 3 and
`a run length limited (RLL) (1,7) code is used;
`FIG. 10 is a block diagram of the viterbi equalizer in
`which the constraint length is 3 and the RLL (1, 7) code
`is used;
`FIG. 11 is a block diagram of a path memory in
`which the constraint length is 3 and the RLL (1, 7) code
`is used;
`
`35
`
`45
`
`50
`
`55
`
`65
`
`LSI Corp. Exhibit 1008
`Page 15
`
`

`

`5
`
`w
`DATA
`CODE WORD
`
`00
`01
`10
`11
`
`101
`100
`001
`010
`w
`CODE WORD BASED ON CORRECTED
`BASIC TRANSFORM
`CODE WORD
`
`101101
`101100
`001101
`001100
`
`101000
`100000
`001000
`010000
`
`15
`
`DATA
`
`0000
`0001
`1000
`1001
`
`25
`
`35
`
`It is now assumed that the number of bits convoluted
`by the recording/reproducing system 102 is 3 as in the
`case of the recording/reproducing model shown in
`FIG.2. By using the RLL (1, 7) code and the convolu
`tional code in the recording/reproducing system 12 as a
`chain code, the trellis state transition diagram of the
`viterbi equalizer 114 is obtained as shown in FIG. 9.
`In FIG. 9, it is assumed that the directions of the
`write current (recording data) are de?ned as +1 and
`— 1. In this case, a time series of the write current en
`coded into the (1, 7) code does not have two transitions
`(+ 1, —l, +1) and (—1, +1, —l). Thus, state transi
`tions indicated by broken lines shown in FIG. 9 do not
`take place in the viterbi equalizer 114 which uses the
`RLL (1, 7) code.
`FIG. 10 is a block diagram of the viterbi equalizer 114
`using the RLL (1, 7) code formed in accordance with
`the trellis state transition diagram of FIG. 9. It should
`be noted the viterbi equalizer 114 does not have any
`structural elements related to the state transitions indi
`cated by the broken lines shown in FIG. 9. The viterbi
`equalizer 114 shown in FIG. 10 includes a distributor
`110, an ACS circuit 120 and a path memory 130. G0, G1
`and G2 are multiplication coef?cients as shown in
`40
`FIG.2, and R is the digital RLL code.
`i
`More speci?cally, the distributor 110 calculates the
`two branch metrics related to two inputs paths with
`respect to each of the internal states (— 1, — l) and (+ 1,
`+1). However, there is only one input path with re
`spect to each of the internal states (— 1, +1) and (+ 1,
`- 1). Thus, the distributor 110 calculates the path met
`ric of only one path with respect to each of the internal
`states (— 1, +1) and (+ 1, - l).
`The ACS circuit 120 has ACS units 21 and 24 pro
`vided for the internal states (— l, —l) and (+1, +1),
`respectively in the same way as the ACS circuit 5
`shown in FIG. 5. That is, each of the ACS units 21 and
`24 is made up of two adders ADD, one comparator
`COMP and one selector SEL. On the other hand, there
`is only one path on the input side of each of the internal
`states (— 1, +1) and (+1, —1). Thus, it is enough to
`calculate the path metric of only the above single path
`on the input side of each of the internal states (—1 +1)
`and (+1, —l). In other words, it is not necessary to
`carry out the comparing and selecting operation with
`respect to the internal states (—1 +1) and (+ 1, —l)
`With the above in mind, the ACS unit 120 has two
`adders 22 and 23 related to the internal states (- 1, +1)
`and (+1, -— 1), respectively. The adders 22 and 23 re
`65
`spectively add the corresponding branch metrics output
`by the distributor 110 and the previous path metrics
`output by the ACS units 21 and 24.
`
`5,341,386
`6
`The comparators of the ACS units 21 and 24 respec
`tively output path select signals PS-l and PS4 to the
`path memory 130. The viterbi equalizer 114 has a selec
`tor 20, which receives path metrics PM-l and PM-4
`respectively selected in the ACS units 21 and 24. Then,
`the selector 20 compares the path metrics PM-l and
`PM-4 with each other and provides the path memory
`130 with a path select signal PS-0 which instructs the
`selector 20 to select one of the path metrics PM-l and
`PM-4 which is smaller than the other one. The path
`memory 130 determines the maximum likelihood path
`in accordance with the path select signals PS-0, PS-1
`and PS-2.
`FIG. 11 is a block diagram of the path memory 130.
`As shown, the path memory 130 is formed in accor
`dance with the trellis state transition diagram of FIG. 9.
`It is not necessary for the path memory 130 to have
`selectors in circuits related to the internal states (—l,
`+1) and (+ 1, —— 1), since there is only single path on the
`input side of each of the internal states (- 1, +1) and
`(+1, — 1). Such circuits have only cascaded ?ip-?ops.
`More speci?cally, the path memory 130 has four
`likelihood determination circuit blocks 31, 32, 33 and 34
`related to the ?rst rows to fourth rows having the inter
`nal states (— 1, — 1), (- 1, + 1), (+ 1, — 1) and (+ 1, +1),
`respectively. Each of the circuit blocks 31 and 34 has a
`plurality of unit circuits cascaded. Each unit circuit
`includes a selector SEL and a ?ip-?op FF. The selec
`tors SEL of the circuit block 31 operate in accordance
`with the path select signal PS-l output by the ACS unit
`21. Similarly, the selectors SEL of the circuit block 34
`operate in accordance with the path select signal PS-4
`output by the ACS unit 24.
`On the other hand, each of the circuit blocks 32 and
`33 respectively related to the internal states (— 1, +1)
`and (+1, — 1) has only ?ip-?ops FF cascaded without
`any selectors. The unit circuits and the ?ip-?ops FF are
`connected in accordance with the trellis state transition
`diagram of FIG. 9. Output signals of the ?ip-?ops FF of
`the ?nal stages of the circuit blocks 31 and 34 are output
`to a selector 35 of the path memory 130. The selector 35
`selects one of the outputs of the above-mentioned ?ip
`?ops of the ?nal stages of the circuit blocks 31 and 34 in
`accordance with the path select signal PS-O, so that the
`maximum likelihood path is selected.
`The present invention is not limited to the above
`mentioned constraint length equal to 3 and the RLL (1,
`7) code. A description will now be given of a second
`embodiment of the present invention. The second em
`bodiment is concerned with a case where the constraint
`length is 4 and an RLL (2, 7) code is used.
`FIG. 12 is a trellis state transition diagram of the
`viterbi equalizer 114 in which the RLL (2, 7) code is
`used and the number of bits convoluted in the recor
`ding/reproducing system 102 (FIG. 8) is four. The
`RLL (2, 7) code, which is one of the formats of the
`RLL code, is generated in accordance with the follow
`ing rule of generation.
`
`45
`
`50
`
`55
`
`DATA
`
`CODE WORD
`
`10
`11
`000
`010
`011
`0010
`0011
`
`0100
`1000
`000100
`100100
`001000
`00100100
`00001000
`
`LSI Corp. Exhibit 1008
`Page 16
`
`

`

`15
`
`30
`
`35
`
`5,341,386
`7
`A time series of write data (current) based on the
`RLL (2, 7) code does not have state transitions of (+1,
`"'1:
`+1,
`2
`—1, —1,
`and (‘—1,
`+ 1, +1, — 1). Thus, there are not state transitions indi
`cated by broken lines shown in FIG. 12, and it is not
`necessary for the viterbi equalizer 114 to have circuits
`related to such state transitions which do not take place
`at all.
`FIG. 13 is a block diagram of the viterbi equalizer 114
`which uses the RLL (2, 7) code. As shown, the viterbi
`equalizer 114 is composed of a distributor 210, an ACS
`circuit 220 and a path memory 230. The distributor 210
`calculates the path metrics of the two input paths with
`respect to each of the internal states (— l, — 1, — 1) and
`(+1, +1, +1) On the other hand, the distributor 210
`calculates the path metric of only a single input path
`with respect to each of the internal states (— l, —1,
`+1)1(_1, +1’
`"'1:
`and
`+1, _1)'
`Further, the distributor 210 does not calculate any path
`metric with respect to each of the internal states (—1
`+1, — l) and (+1 — 1, +1) G3 is a multiplication coef
`?cient similar to, G0, G1 and G2.
`The ACS circuit 220 has two ACS units 51 and 56,
`adders 52-55, and a comparator 50 Each of the ACS
`units 51 and 56, which are respectively provided for the
`25
`internal states (—1, —1, —1) and (+1, +1, +1), has
`two adders ADD, one comparator COMP and one
`selector SEL in the same way as the aforementioned
`ACS units 21 and 24. The adders 52, 53, 54 and 55 are
`provided for the internal states (—1, —1, +1), (—1,
`+1, +1), (+1, — 1, —1) and (+1, +1, —1), respec
`tively. There are no structural elements for the internal
`states (— 1, +1, —l) and (+1, — 1, +1). The compara
`tor 50 compares the path metrics PM-1 and PM-4 and
`selects one of them which is smaller than the other one.
`FIG. 14 is a block diagram of the path memory 230
`shown in FIG. 13. As shown, the path memory 230 is
`composed of six circuit blocks 61-66. Each of the cir
`cuit blocks 61 and 66, which are respectively related to
`the internal states (—1, —l, -l) and (+1, +1, +1)
`includes a plurality of cascaded unit circuits, each hav
`ing one selector SEL and one ?ip-?op FF. Each of the
`circuit blocks 62—65 has only ?ip-?ops FF which are
`cascaded. There are not blocks with respect to the inter
`nal states (—1, +1, -1) and (+1, —1, +1). The unit
`circuits and the ?ip-?ops FF are connected so that the
`trellis state transition diagram of FIG. 12 is formed.
`It is possible to realize the above-mentioned hard
`ware structure by software since it is not necessary to
`carry out the judgment procedures related to the state
`transitions indicated by the broken lines shown in
`FIGS. 9 and 12.
`The present invention is not limited to magnetic disk
`devices, but includes recording/reproducing devices in
`which an interference may occur, such as optical disk
`devices.
`The present invention is not limited to the speci?cally
`disclosed embodiments, and variations and modi?ca
`tions may be made without departing from the scope of
`the present invention.
`60
`What is claimed is:
`1. A viterbi equalizer, comprising:
`distributor means for receiving a run length limited
`code and for calculating branch metrics responsive
`to said run length limited code, said branch metrics
`being related to only nodes and branches in a trellis
`state transition diagram based on a viterbi decoding
`algorithm de?ned for the run length limited code,
`
`8
`wherein said run length limited code has a con
`straint length of 3 and is de?ned by a (1, 7) code;
`path metric calculating means, operatively coupled to
`said distributor means, for generating path metrics
`on the basis of said branch metrics and generating
`path select signals indicative of surviving paths
`coupling said nodes and said branches, said path
`metric calculating means comprising:
`?rst means for generating two path metrics related
`to each ofinternal states (— l, —l) and (+1, +1)
`where —l and +1 are possible internal states,
`respectively; and
`second means for generating only one path metric
`related to each of internal states (— 1, +1) and
`(+1, —1); and
`path memory means, operatively coupled to said path
`metric calculating means, for determining a maxi
`mum likelihood path on the basis of said path select
`signals output by said path metric calculating
`means.
`2. A viterbi equalizer as claimed in claim 1, wherein
`said path metric calculating means further comprises:
`?rst comparing means for selecting one of said two
`path metrics related to each of said internal states
`(—1, —1) and (+1, +1) and generating ?rst and
`second path select signals indicative of said surviv
`ing paths; and
`second comparing means for comparing a ?rst se
`lected path metric related to the internal state (- 1,
`— l) and a second selected path metric related to
`the internal +1, +1) and generating a third path
`select signal indicative of which one of the said ?rst
`and second selected path metrics is smaller.
`3. A viterbi equalizer as claimed in claim 2, wherein
`said second means for generating comprises:
`?rst means for adding said ?rst selected path metric
`and the one of said branch metrics related to the
`internal state (— 1, +1) to generate the only one
`path metric related to the internal state (- 1, +1);
`and
`second means for adding said second selected path
`metric and the one of said branch metrics related to
`the internal state (+1, —I) to generate the only
`one path metric related to the internal state (+1,
`— 1).
`4. A viterbi equalizer as claimed in claim 1, wherein
`said path memory means comprises:
`a ?rst circuit block related to the internal state (— l,
`- l) and having unit circuits connectedly arranged
`on the basis of said trellis state transition diagram
`based on the viterbi decoding algorithm de?ned for
`the run length limited code, each of said unit cir
`cuits of said ?rst circuit block including a selector
`and a flip-?op;
`second circuit block related to the internal state
`(— 1, +1) and having ?ip-?ops connectedly ar
`ranged on the basis of said trellis state transition
`diagram;
`a third circuit block related to the internal state (+1,
`— l) and having ?ip-?ops connectedly arranged on
`the basis of said trellis state transition diagram; and
`a fourth circuit block related to the internal state (+ 1,
`+ l) and having unit circuits connectedly arranged
`on the basis of said trellis state transition diagram,
`each of said unit circuits of said fourth circuit block
`including a selector and a ?ip-?op, and
`
`45
`
`50
`
`55
`
`65
`
`LSI Corp. Exhibit 1008
`Page 17
`
`

`

`5,341,386
`9
`wherein said ?rst, second, third and fourth circuit
`blocks are coupled in accordance with said trellis
`state transition