1344
`
`Abstract - This paper provides a tutorial introduction to
`E E 6 i i i g codes for magnetic disk storage devices and a review
`of progress in code construction algorithms. Topics covered
`include: a
`brief description of typical magnetic recording
`channels; motivation for use of recording codes; methods of
`selecting codes to maximize data density and reliability; and
`techniques for code design and implementation.
`1. INTRODUCTIQN
`Recording codes have been uscd with great success in
`magnetic disk storage to increase linear density and improve
`performance. This paper attempts to provide, in a limited space,
`a tutorial introduction to these codes.
`Section 2 briefly reviews the basic principles of recording
`in a typical magnetic storage channel,
`as well as
`and detection
`the motivation for the use of codes.
`Section 3 focuses on recording codes for magnetic disk
`storage. The recording
`codes in most widespread use fall into
`the class of run-length-limited (RLL) or (d,k) constrained codes.
`Two major problems arise
`in the context of general RLL
`(d,k! codes. First, one must choose the parameters (d,k) which
`In Section 4, we address
`maximize data density and reliability.
`this issue
`of
`recording code performance evaluation and
`parameter selection.
`The second major problem is the design and
`implementation of (d,k) codes. Section 5 is devoted to a review
`of code construction techniques, with
`an emphasis on recent
`advances in the development
`of general algorithms for the
`construction of sliding block RLL codes.
`
`2. THE DIGITAL MAGNETIC RECORDING CHANNEL
`in use today employ
`Most magnetic disk storage devices
`saturation recording to place the data
`on the disk, followed by
`peak detection during the readback step to recover the
`1 illustrates schematically the essential
`information. Figure
`elements of the process. The data are recorded on the magnetic
`medium by orienting magnets along a concentric track, as shown
`at the top left of the figure. The magnets are oriented either
`in
`the direction of motion of the head around the t r y k , o r in the
`opposite direction (at least in conventional horizontal"
`recording). The remaining portions
`of the figure show the
`relationship of the pattern of magnetization to the recorded bits,
`as dictated by the modulation scheme (known as NRZI
`a 2-level write
`precoding) which converts the bit stream to
`symbols "I" in the
`current signal for the recordiy
`head. The
`transitions" or changes in the
`bit stream are recorded
`as
`polarity of the magnets along the track. During the readback
`process, the inductive read head transforms the sequence
`transitions into a stream of pulses of alternating polarity. The
`clocking circuit (VPO, or variable-frequency oscillator) uses
`these pulses to maintain
`a synchronized timing window for the
`detector, which locates the pulse peaks in time. The information
`can then be reconstructed by placing a recovered bit "1" in any
`window in which a peak was detected, and a bit "0" otherwise.
`
`of
`
`The recording channel has imperfections,
`however.
`Thermal noise generated by the electronic circuits and noise
`arising from magnetic properties of the disk medium can corrupt
`the readback signal, leading to spurious peaks as well as shifted
`positions of the genuine peaks. To compensate for these effects,
`t o peak detection, such as the
`at least in part, enhancements
`addition of a threshold (clip level) and the tracking
`of peak
`polarities, have been introduced. Another major problem is the
`intersymbol interference
`(ISI) of neighboring pulses, illustrated
`in the figure. Magnetic transitions, or recorded symbols "1,"
`which arc written too close to one another have an interfering
`effect during readback that can both reduce the amplitude of the
`pulse as well as shift the peak position. On the other hand,
`if
`the transitions are written too far apart, the clock recovery
`circuit will not be receiving adequate information
`t o maintain
`synchronization with the recorded bits.
`These detection error mechanisms are combatted by the
`use of data coding techniques. Two distinct
`kinds of codes are
`typically used. A recording code is
`used to guarantee that the
`recorded bit sequence does not suffer from
`$e problems
`symbols
`of
`described above, namely runs
`0" between
`consecutive symbols "1" which are either too short or too long.
`Recording codes are also referred to as modulation codes. Even
`errors may still
`with an appropriate recording code, detection
`occur as a result of channel noise, producing an unacceptable
`error rate at the desired data density. The
`second kind of code,
`an error-correcting (also called error-control) code (ECC), uses
`redundant bits which have been added t o the original user data
`to detect, locate, and correct all remaining errors with very high
`probability of success.
`The configuration of these codes in the magnetic recording
`channel is shown in Figure 2. In typical high end applications,
`the recording code reduces the bit error rate (BER) to
`approximately 1 detection error in 10 billion bits. In addition,
`practical recording codes limit error propagation in the decoding
`process. This
`is crucial, because the ECC typically used has the
`capability of correcting only a small number of multi-bit bursts
`of errors per track.
`
`Fig. 2. Configuration of codes
`For the remainder of this paper, we focus on the aspects of
`recording code selection and design.
`3. RUN-LENGTH-LIMITED (RLL) CODES
`FOR MAGNETIC STORAGE
`Many popular recording codes for peak detection channels fall
`into the class of run-length-limited (RLL) codes. These codes,
`in their general form, were pioneered by P. Franaszek [l] in the
`late 1960's. Since then, a considerable body of engineering and
`been written on the subject. RLL
`mathematical literature has
`(d,k), which
`codes are characterized by two parameters
`represent, respectively, the minimum and Caximum number
`of
`1" in the allowable
`symbols "0" between consecutive symbols
`d controls high frequency content
`code strings. The parameter
`in the associated write current signals, and so reduces the effects
`k controls low
`of intersymbol interference. The parameter
`frequency content, and ensures frequent information for the
`clock synchronization loop.
`rigid disk files, as
`For example, most flexible and low-end
`well as some high-end drives, today incorporate a code known as
`Modified Frequency Modulation (MFM). It also
`goes by other
`names, such as Delay Modulation or Miller code. MFM is an
`RLL code with (d,k)=(1,3).
`the coding theorist
`faced by
`is the
`The problem
`construction of. a simple, efficient correspondence, or code
`mapping, between the arbitrary binary strings that a
`user might
`want to store on a magnetic disk and the (d,k) constrained code
`strings which the peak detector
`ca,p more easily recover
`correctly. We now give the term efficient" quantitative
`meaning by introducing the third important code parameter, the
`code rate.
`'The conversion of arbitrary strings t o constrained (d,k)
`as follows. Pick a codeword
`strings could be accomplished
`0018-9464/85/0900-1344$01.0001985 IEEE
`
`* O
`
`Readback
`Vo!tage.
`
`.
`
`l
`
`.
`
`l
`
`. @ .
`
`
`
`Detected
`Data:
`
`.
`
`o
`
`.
`
`Magnetic
`Trzck:
`
`nata:
`
`write
`Current.
`
` 1
`
`.
`
`1
`
`.
`
`0
`
`
`
`Fig. 1. Digital magnetic recording channel
`
`Manuscript received:
`P. H. Siegel
`IBM Research Lab, K62/282
`5600 CottIe Road
`San Jose, CA 95193, U.S.A.
`
`UMN EXHIBIT 2026
`LSI Corp. et al. v. Regents of Univ. of Minn.
`IPR2017-01068
`
`
`Page 1 of 6
`
`

`

`length n. List all the strings of length n which satisfy the (d,k)
`constraint. If there are at least 2m such strings, assign a unique
`codeword to each of the 2m possible binary input words of
`length m. This kind of code mapping is commonly referred
`to
`to
`as a block code. The ratio, m/n,
`of input word length m
`codeword length n is called the code rate. Since there are only
`2" unconstrained binary strings
`of length n, there will be less
`than this number of constrained,codewords. Therefore, the
`rate must satisfy m/n<l. In fact, there is a maximum
`achievable rate, called the Shannon capacity C, which we now
`discuss.
`In 1948, Shannon proved that, as the codeword length
`2Cn
`grows, the number
`of constrained codewords approaches
`on the code
`from below, for some constant C which depends
`constraints. This result implies that the rate m/n
`of any code
`mapping for that constraint must satisfy m/n<C. Roughly
`speaking, a code is called efficient if the rate m/n is close to C.
`a' block code is possible at
`Shannon's proof also showed that
`any rate m/n<C, provided long enough codewords are used.
`We remark that practica1 applications usually require code
`mappings involving shorter codewords. Section
`5 discusses
`techniques which have been developed to construct practical
`code mappings, including codes with rate equal to the capacity
`C when C is a rational fraction.
`One can employ a finite-state transition diagram (FSTD)
`of binary
`in order to conveniently represent the infinitude
`strings satisfying the' (d,k) constraint. This graph
`representation for constrained channel strings dates back to
`Shannon's seminal paper [2], and it was exploited by Franaszek
`in his work on RLL codes. Figure 3 shows an FSTD for the
`(1,3) constraint. It consists of a graph with
`4 nodes, called
`states, and directed edges between them, called state
`transitions, represented by arrows.. The edges are labeled with
`channel bits. Paths through the graph correspond
`precisely to
`(1,3) constraint. A similar
`the binary strings satisfying the
`FSTD having k+l states can be used to describe any (d,k)
`constraint, as the reader can easily verify.
`
`(1)
`
`Rate
`1/2, 2/3
`1 /2
`213
`1 /2
`
`(d,k) Capacity Practical
`C
`(0,1) 0.6942
`(1,3) 0.5515
`(1,7) 0.679
`(2,7) 0.5172
`Fig. 3. (1,3) FSTD Fig.
`
`
`4. Code Capacities
`The capacity C of the RLL (d,k) constrained channel is
`directly related to the structure
`of the FSTD. We define the
`state-transition matrix T = (t.-) associated to the (d,k) FSTD
`with states 1, ..., k + l as followk!:
`t.. = x, if there are x edges from
`state i to state j .
`11
`otherwise .
`=0,
`For example, for the (d,k)=(1,3) case:
`0 1 0 0
`1 0 1 0
`T ' 1 0 0 1
`1 0 0 0
`The capacity C, in units of user bits per channel bit, was shown
`by Shannon to be:
`c = log, h
`where X is the largest positive eigenvalue of T , that is the largest
`of T. For the (d,k)
`root of. f(t), the characteristic polynomial
`constraint, the polynomial f(t)
`is f(t)=tk+l-tk-d-...-t-l. The
`roots can be easily found by computer calculation. In the (1,3)
`case, we find A=1.465.., so C=O.5515 ...
`In practice, one chooses for the rate a rational number
`m/n<C. To help keep the codeword length small, the integers m
`and n are often selected to be small. Thus, for the
`(1,3)
`constraint, it would be natural to
`look for a code mapping at
`rate 1/2, which uses codewords of length 2 bits. Figure 4 gives
`a list of some (d,k) constraints of historical and current interest,
`along with Shannon capacity C, and choices of practical code
`1/2 for (d,k)=(O,l) is
`rates. We note here that the rate
`included for historical reasons which will be clarified in section
`possibIe
`5. For now, it serves to emphasize that the rates of
`code mappings must only satisfy m/n<C.
`
`1345
`
`For a given user bit frequency, or data rate, the choice of
`(d,k) constraint and code rate determines the code bit
`frequency and the power spectrum of the write current signals
`produced by the code. Figure
`5 shows the power spectra of
`write current signals that would be obtained from a (d,k) code
`that is 100% efficient, for the (d,k) parameters in Figure 4.
`
`0
`
`5 -
`-
`ti -lo
`B
`
`-15
`
`-20
`0
`
`02
`
`08
`
`1 0
`
`O B
`0.4
`Fleg"e"CY
`ldala bll trequancy = ?,
`Fig. 5 . RLL code spectra
`4. CODE PERFORMANCE EVALUATION AND SELECTION
`We are now in a position to evaluate, to some extent, the
`relative abilities of RLL (d,k) codes to prevent detection errors
`in peak detection channels.
`as to the best (d,k) code to use at a
`One can get a clue
`specified data rate with a particular head and dizk combination
`by seeing which code spectrum in Figure
`5 matches" the
`head/disk transfer function best. This comparison can be
`strengthened by taking a closer look a t code patterns and their
`impact on the peak detection process. To start,
`we do a
`comparison which will explain the prevalence of MFM today.
`When peak detection was introduced along with a
`variable-frequency oscillator (VFO) clocking circuit, a coding
`technique was needed to give very frequent clock recovery
`information to the VFO. It is known as Frequency Modulation
`related to Phase Encoding
`(FM), or Double Frequency, and is
`and Manchester code. The code was at rate 1/2, and the code
`To encode, write 2 bits for each
`mapping rules were simple.
`data bit, the first always being "1," the second being the data
`bit. Decoding involves simply grouping the detected bits into
`pairs, and dropping the first bit of each pair. Using RLL code
`nomenclature, FM is a rate 1/2 (0,l) RLL code. This is the
`reason that rate 1/2 for (d,k)=CO,l) was included in Figure 4.
`It should be mentioned that FM is also a
`DC-balanced
`code, meaning that the associated write signals have zero
`average power at DC. In fact, at any point in time, the number
`signal is positive
`of preceding clock
`intervals in which the
`in which it is negative by a t most 1.
`differs from the number
`With this additional constraint, the FM code is 100% efficient.
`This DC-balanced property
`is not required, however, for most
`magnetic disk storage applications.
`In FM, the k=l parameter made accurate clock
`6 shows uncoded data and
`synchronization possible. Figure
`rate 1/2 (0,l) bit patterns which correspond to the same linear
`user bit density. The minimum allowable magnetic transition
`spacing is indicated by the solid bar at left above each pattern.
`in which the peak must be sensed is
`The detection window
`indicated by the dotted bar at right above each pattern. We
`see that the FM code cuts the size of the detection window in
`reduces the minimum transition
`half, and simultaneously
`spacing
`by a factor
`two. The drastic increase in
`of
`intersymbol interference certainly negated
`t o some extent the
`potential benefits obtained by the introduction of peak sensing
`and the VFO.
`
`-
` -
`' -
`
`+-----I
`
`1
`.
`1
`.
`+--i
`H
`. 1 . 1 . 1 . 1 . 0 . 1 . 1 . 1 .
`
`k---i
`H
`. 1 . 0 . 1 . 0 . 0 . 0 . 1 . 0 .
`
`.
`
`k---i
`
`.
`
`1
`
`.
`
`0
`
`Data:
`
`FM'
`
`MFM:
`
`1/2(2,7):
`
`. 1 . 0 . 0 . 1 . 0 . 0 . 0 . 0 .
`p---,
`. 0 . 0 . 0 .
`. 1 . 0 . 1
`2/3(1,7):
`Fig. 6 . RLL code patterns
`Modified Frequency Modulation (MFM) was developed,
`as the name suggests, to improve upon the FM recording code.
`The observation was made that not all
`of the redundant bits
`need to be "1". Inserting a "1" in the first.position of each
`code bit pair only when the current data bit and previous data
`bit are "0," and inserting "0" otherwise, produced a rate
`1/2
`(1,3) code. The k=3 parameter turned out to be still adequate
`
`
`Page 2 of 6
`
`

`

`1346
`
`I
`
`20
`
`d = l represented a doubling of the
`for clock recovery, and the
`6 shows
`minimum transition spacing compared to FM. Figure
`1/2 (0,l)
`and rate 1/2
`the comparison of "worst case" rate
`user bit density, one
`(1,3) bit patterns. At a specified linear
`would anticipate considerable improvement in detector
`performance from MFM. MFM became an industry standard in
`flexible and "Winchester"-technology drives.
`More recently, other RLL (d,k) constraints have been
`1 / 2 ( 2 , l l ) code
`introduced. For example, ISS used a rate
`called 3PM [3] in its 8434 disk drive and a rate 2/3 (1,7) code
`in its 8470 drive [4]. Also, IBM utilized a rate 1/2 (2,7) code
`[SI in its 3370-3380 family of high-end drives.
`Figure 6 gives heuristic Justification of the use of these
`codes instead of MFM. In comparing
`1/2 (2,7)
`to MFM, at
`fixed linear density, we see that the ' worst case" intersymbol
`(2,7) code gives a minimum transition
`interference for the
`spacing which is 50% larger than that of MFM. The detection
`window size remains unchanged. Provided that the VFO can
`handle a k=7 parameter, we conclude that use of the (2,7) code
`leads t o a considerable improvement in detector performance.
`2/3 (1,7) code to MFM, we find
`Similarly, in comparing the
`that the (1,7) has 33% larger minimum transition spacing, as
`well as a
`33% larger detection window. Again, we can
`of (1,7)
`conclude that the error rate can be reduced by use
`instead of MFM.
`The code comparison method breaks down when we try to
`1/2 (2,7)
`and the 2/3 (1,7)
`codes. The
`choose between the
`2/3(1,7) code has a 33% larger detection window than the
`1/2(2,7), but the minimum transition spacing is llo/o.less. The
`on the specific signal and noise
`optimal choice depends
`characteristics of the head-disk combination and other channel
`components, as well as additional signal processing options
`such as readback equalization and write precompensation.
`More sophisticated performance evaluation tools are required,
`been devoted to the development of
`and several studies have
`such tools and their application to code selection. See, for
`example, Huber
`[6]. Using the peak detection channel model
`[7], error-rate curves were computed for FM,
`reported in
`B
`MFM, and (2,7) codes to illustrate the progress achieved via
`improved coding. These calculations assumed conventional
`thin-film head, particulate medium with no significant disk
`defects, low-pass filtering, and no write precompensation. The
`results are shown
`in Figure 7. In addition, Figure 7 shows a
`projected range of improved performance that can be achieved
`of (2,7) or (1,7) codes in conjunction with write
`by use
`precompensation and readback equalization. These projections
`are consistent with simulated and experimental results given in
`several published studies. For example, Jacoby and Kost
`[4]
`reported that a data rate increase
`of 10% was achieved in an
`equalized channel by use of a rate 2/3 (1,7) code in place of a
`rate 1/2 (2,7) code.
`.- + x
`0
`
`- .-
`Q
`m
`Q
`2
`a -10
`2
`w"
`a
`0
`-I -20
`4
`
`a
`16
`12
`Linear Density (KBPI)
`Fig. 7. RLL code performance calculation
`These calculations indicate that recording code progress
`since 1966 has increased linear density by a factor
`approximately 2.5. This represents a significant contribution
`to the overall factor
`of increase due to improvements in
`storage technology, for example, as reported for IBM disk
`drives in [SI.
`5. RECORDING CODE CONSTRUCTION
`AND IMPLEMENTATION
`on
`Once the optimal code parameters'are selected, based
`modeling or experimentation, it is necessary t o devise encoding
`and decoding rules for an efficient code which can be
`implemented in simple logic circuits or look-up tables. This
`section addresses the problem
`of code construction and
`implementation.
`To illustrate some of the techniques and algorithms that
`have evolved in the construction
`of practical, efficient
`recording codes, we develop a sequence of examples. We first
`of MFM
`will describe practical code properties in the context
`
`
`
`A
`
`of
`
`code. Then, we will examine some of the methods developed to
`design (d,k) codes, emphasizing
`(2,7) and (1,7) codes. The
`of Franaszek [l] and the
`sequence state coding methods
`look-ahead techniques of Patel [9], Jacoby [3], Franaszek [lo],
`[ll], Jacoby and Kost
`Cohn and Jacoby
`[4], and Lempel and
`Cohn [12] will be discussed.
`on the recent sliding block code
`Finally, ,we focus
`construction algorithm of Adler, Coppersmith, Hassner [13],
`based on work of Marcus [14]. This technique, derived from
`the branch
`of mathematics known as symbolic dynamics,
`represents a theoretical breakthrough in code construction,
`with significant practical implications. For the first time, the
`algorithm provides an explicit recipe, justified by mathematical
`proofs, for construction
`of simple, efficient RLL codes with
`limited error propagation. The method incorporates many
`of
`the key ideas which appear in the work
`of Franaszek, Patel,
`Jacoby, Cohn and Lempel, generalizing them and making
`precise the construction steps and the scope
`of
`their
`applicability.
`- ------ -
`_-- _-
`Properties of Practical Code Mappings
`We now discuss some properties that practical code
`possess, using MFM to illustrate them. The essential
`properties are:
`1) high efficiency,
`2) simple encoder and decoder implementations, and
`3) limited error propagation.
`The MFM code, as defined earlier, is a rate 1/2 (1,3)
`code. It has high efficiency, 0.5/0.5515, or approximately 91%.
`The encoder is characterized by two encoding rules. The first
`rule, which we call rul: A, is used to encode a data bit
`if the
`,yy 0". The second rule B, is used if
`the
`previous data bit
`of a block
`1 , Both rules take the form
`previous bit was
`code, mapping 1 bit to 2 bits. The MFM encoder can be
`represented in table form, as shown in Figure 8.
`State
`
`
`Code Data
`Data
`0
`1
`
`mappings
`
`0
`
`OO/A
`
`10/A
`NO
`1
`
`N1
`
`
`01/B 01/B
`Fig. 8. Encoder and decoder tables for MFM
`The columns labeled A and B describe the block codes for the
`two rules. Each entry
`in these columns also indicates the next
`i s t o be used t o encode
`encoder state, that is, the rule which
`the next bit.
`The MFM encoder is an example
`of a finite-state machine
`(FSM), with fixed length inputs and outputs. A FSM is simply
`a set of encoding rules which indicate how t o map input words
`to output words, and also define which
`encoding rule to use
`after each encoding operation. A
`FSM also has a graphical
`an important role
`in the later
`representation which will play
`discussion of code construction techniques. The nodes (states)
`in the graph correspond to columns
`in the encoder table, and
`the graph edges have labels "x/y" where x
`is an input word,
`1s the corresponding codeword. The labeled edges
`and y
`emanating from a state define the
`encoding rule, and the state
`in which an edge terminates indicates the state, or encoding
`rule, to use next. The FSM graph for MFM is shown in
`Figure 9.
`is particularly convenient
`The FSM encoder structure
`because it is quite easily implemented as a sequential logic
`network or ROM-based look-up table. Each encoder cycle
`encodes a single data bit into 2 code bits, which are a function
`of the data bit and the contents
`of a 1-bit state indicator
`register, and then updates the state indicator.
`Decoding is accomplished by grouping the code string into
`2-bit blocks and dropping the redundant first bit in each block.
`The decoding :able is shown in Figure 8 also. The symbol "N"
`represents a not care" bit position in which the a5tual bit
`Zalue does not affect
`decoding. For example, both
`10" and
`00" decode to "0". This block decoder ensures that error
`propagation is no more than 1 user bit.
`The MFM decoder is an example of a sliding blo;k decode:[
`which decodes a codeword by looking at a window
`containing the codeword and a finite number of preceeding and
`following codewords in the string. In the MFM case, the
`window only contains the codeword
`being decoded. One can
`think of such a decoder in terms of a sliding window that shifts
`d o n g the codestring one codeword a t a time, producing at each
`on the window
`shift a decoded data word, depending only
`contents. This structure ensures finite error propagation, since an
`erroneous codeword can only affect the decoding decisions
`while it is contained in the sliding
`window. A sliding block
`decoder is also conveniently implemented
`in a logic network,
`with the sliding block embodied in a shift register. Each MFM
`
`
`Page 3 of 6
`
`

`

`decoding cycle shifts 2 code bits into the register and generates
`a decoded data bit.
`
`01
`
`00
`
`Fig. 9. MFM encoder Fig. 10. G2 for (1,3) Fig. 11. Subgraph H
`
`-- Secpence ----- State C o d a
`Franaszek [l] introduced sequence state methods into the
`investigation of efficient constrained code construction. The
`t o build a FSM encoder in which the states
`essential idea is
`(encoding rules) correspond to the states in a FSTD
`by
`representation of the constraints. The codewords produced
`a particular encoding rule
`in the FSM must
`be generated by
`following paths through the FSTD which start at the
`corresponding state.
`We illustrate the sequence state methods by rederiving
`the FSM encoder for the MFM code. We begin with the FSTD
`for the (1,3) constraint, shown in Figure 3. Denote this graph
`by G. We want the FSM encoding rules t o map 1 bit to 2 bits,
`so an edge in the FSM graph should have a codeword label
`which is 2 bits long. Therefore, an edge in the FSM graph
`must correspond to a sequence of 2 edges in the FSTD, each of
`which had a 1 bit codeword label. With this in mind, we now
`G J , as a candidate for the underlying graph
`de ine the graph called the square of the FSTD G, and denoted
`of the FSM
`encoder. This is the FSTD which has the same states as G, but
`in which, each edge corresponds t o a consecutive pair of edges
`in G, and the edge label is the corresponding sequence of 2 edge
`is shown in Figure
`labels from G. The FSTD G2 for thi case
`G 1 had at least
`10. Note that
`if each state in
`2 edges
`emanating from it, we could construct an FSM encoder by
`simply assigning the input words "0" and "1" to two distinct
`edges from each state, discarding any excess edges.
`Here, though, G2 does not have this property. This can
`be seen f om Figure 10. It can also be seen by noting that the
`matrix TI, the matrix square
`of the state-transition matrix T
`for FSTD G, is the state-transition matrix for the FSTD
`G2.
`This matrix is:
`
`1 0 1 0
`1 1 0 1
`2
`T =
`1 1 0 0
`0 1 0 0
`
`j) can be seen to count the total
`The entry in (row i, column
`number of edges from state i to state j in G2. The row sum for
`each row must be a t least 2 if each state has at least 2 outgoing
`edges. Clearly the row sum for row 4 is only 1.
`H of
`However, we can observe that there is a subgraph
`G2 which does have the desired number of outgoing edges from
`each state. Namely, we eliminate state 4 and all
`edges which
`it Alternatively, we note that the submatrix
`enter or leave
`obtained from Ti by eliminating the last row and column has
`row sums exactly
`2. Input labels can now
`be assigned to the
`edges in the subgraph H to yield a FSM encoder structure,
`shown in Figure
`11. States 2 and 3 have the property that
`their outgoing edges are identical in terms of output labels and
`next states. In other words, they describe the same encoding
`rule. Tpey may
`be merged, therefore, into a single aggregate
`state, 2 . The outgoing edges from 2' are those common
`t o
`states 2 and 3, while the incoming edges are simply redirected
`to 2' from states 2 and 3. If we relabel state 1 as state B and
`state 2' as state A, the resulting FSM is exactly the FSM
`shown in Figure 9.
`is
`For the RLL (2,7) constraint, the Shannon capacity
`given by C=0.5172 ... If we try to construct a FSM encoder
`which encodes 1 bit into 2 bits, as we did with MFM above, we
`of the square of the standard
`find that there is no subgraph
`(2,7) FSTD with at least 2 outgoing edges from each state. We
`know from Shannon's result that a code is possible at rate 1 2,
`SO one strategy is to take higher powers of the graph, say G4m,
`and try to derive from it a FSM encoder in which one encodes
`A computer
`m input bits at a time into
`2m code bits.
`calculation of powers of the matrix T shows that the smallest
`value of m for which this is possible is m=17
`In the resulting
`FSM encoder, each state would require 2 l 7 outgoing edges.
`The table form
`of t e encoder would require a table
`of
`encoding rules, each 2 19 x34 bits in size!
`
`1347
`
`Code
`
`A 000100
`
`100100
`001000
`00100100
`00001 000
`
`D a t i
`
`001 0
`001 1
`
`Fig. 12. 'Variable-length (2.7) code
`
`In general, this
`used to construct
`techni ue can be
`efficient (d,k) codes, with h i t e error propagation. The
`drawback, as seen in the (2,7) example, is that the encoder and
`decoder implementations can still be very complex, involving
`long codewords and otentially large error propagation.
`Franaszek [5] round a considerably simpler code mapping
`by utilizing FSM structures with variable-length input words
`a detailed
`and codewords. Space limitations preclude
`discussion of the technique, but we will describe the 1/2 (2,7)
`code he constructed, as well as properties of the variable-length
`FSM codes generated by the method.
`The variable-length FSM encoder for the
`1/2 (2.7) code
`reduces t o a single state, yielding a variable-length block code
`as shown in Fi ure
`12. The codewords form a
`prefix-free list,
`that is, no wor8 is a prefix of another. This ensures that any
`concatenation of codewords has a unique decomposition into a
`string of codewords. In additign, Franaszek selected the
`codewords so that the patterns
`1000" and "0100" delimit
`
`
`
`
`
`codeword boundaries. These two properties ensure
`decodability with finite error propagation. The corresponding
`data word list is also prefix-free, and additionally has the
`fuU. This means that every semi-infinite
`property of being
`binary data string has a unique decomposition into input
`of data. It is interesting to
`words, guaranteeing encodability
`of a (2,7) encoder based
`note that the actual implementation
`on this variable-length code involved the translation of this
`code description into an equivalent fixed-length FSM encoder
`mapping 1 data bit to
`2 code bits during each encoding
`operation. The number
`of states used required a 4-bit state
`indicator memory. The decoder implementation took the form
`of a sliding block decoder, decoding 2 code bits into 1 data bit
`during each decoding operation. The sliding window was a
`of 8 code bits. The error propagation was
`shift register
`therefore no more than 4 data bits. [15].
`In general,' the variable-length
`sequence state coding
`with