Methods and apparatus for implementing run-length limited and maximum transition run codes

Data words are converted to codewords in accordance with a run-length limited (RLL) or maximum transition run (MTR) code in which the codewords are subject to one or more constraints on the number of consecutive like symbols. The data words and codewords are each partitioned into a number of disjoint subsets. Associated with each of the disjoint subsets of data words is a distinct mapping. A given data word is converted to a codeword by applying to the given data word the mapping associated with the subset containing that data word. The mappings are configured to utilize symmetry whenever possible. For example, if Y=.psi.(X) represents the mapping of a given data word X onto a corresponding codeword Y. then it is preferred that X' and Y' representing the words X and Y in reversed order, satisfy the relation Y'=.psi.(X'). An example of an efficient high-rate, multi-purpose code in accordance with the invention is a rate 16/17 code satisfying (0,15,9,9) RLL and (0,3,2,2) MTR constraints. This exemplary code can be further processed using interleaving techniques to generate other higher rate codes.

FIELD OF THE INVENTION
 The present invention relates generally to coding techniques, and more
 particularly to run-length limited (RLL) and maximum transition run (MTR)
 coding techniques for use in high density recording channels and other
 applications.
 BACKGROUND OF THE INVENTION
 A variety of block codes that fulfil certain channel input constraints have
 been developed for recording channels during the last several decades. One
 important category is the class of run-length limited (RLL) codes. The
 codewords of an RLL code are run-length limited binary sequences of a
 fixed length n, also known as (d,k) sequences, and are characterized by
 the parameters d and k, which indicate the minimum and maximum number of
 "zeros" between consecutive "ones" in the binary sequence, respectively.
 In magnetic recording applications, the binary sequence is mapped to a
 magnetization pattern along a track where every cell is fully magnetized
 in one of two possible directions, or equivalently, to a two-level
 sequence. One convention, commonly referred to as
 non-return-to-zero-inverse (NRZI) modulation, is to have a "one"
 correspond to a reversal of the direction of magnetization, i.e., a
 transition in magnetization between two bit cells, and to represent a
 "zero" as a non-reversal in magnetization, i.e., the absence of a
 transition. As a consequence, the parameter d controls the intersymbol
 interference (ISI) whenever peak detection is used to determine the
 transitions, since d defines the minimum distance between consecutive
 transitions. The parameter k defines the maximum distance between
 transitions and therefore determines the self-clocking properties of the
 sequence.
 Current high-density recording systems generally use a detection technique
 that comprises partial response equalization with maximum-likelihood
 sequence detection, often referred to as PRML. By reconstructing the
 recorded sequence from sample values of a suitably equalized readback
 channel, ISI can be handled. In the current systems a partial-response
 channel model with transfer function h(D)=(1-D)(1+D)N is generally used.
 The channel models with N.gtoreq.2 are usually referred to as E.sup.N-1
 PR4 channels.
 For high density magnetic recording channels having high ISI, sequence
 detection can be enhanced by reducing the set of possible recording
 sequences in order to increase the minimum distance between those that
 remain. Often, to achieve this goal, a large fraction of the set of
 possible sequences has to be eliminated, which adversely affects the
 maximum achievable code rate. Pairs of sequences with minimum distance
 have been identified for important classes of partial-response channels
 and codes based on constrained systems have been proposed to increase the
 minimum distance between recorded sequences. See, e.g., E. Soljanin and A.
 J. van Wijngaarden, "On the Capacity of Distance Enhancing Constraints for
 High Density Magnetic Recording Channels," Proc. Workshop on Coding and
 Cryptography WCC'99, pp. 203-212, Paris, France, January 1999, which is
 incorporated by reference herein.
 For the E.sup.2 PR4 channel, which is an appropriate model for the current
 generation of high density recording systems, the constraints that have
 been specified can be realized by restricting the maximum run-length of
 consecutive "ones." The corresponding codes, known as maximum transition
 run (MTR) codes, are equivalent to (0,k) RLL codes with interchanged
 "ones" and "zeros." By observing the constraints it becomes clear that a
 (0,2) MTR code will in any case be sufficient to increase the minimum
 distance. However, the capacity of a (0,2) code is only 0.8791. Higher
 rates can be achieved by specifying constraints that do not remove all
 undesired pairs but instead significantly reduce the number of undesired
 pairs of sequences with minimum distance. In this way, a trade-off is made
 between code rate, code complexity and detection performance.
 In the construction of maximum (0,k) RLL codes, long sequences that fulfil
 the (0,k) constraints are typically constructed by concatenating the
 codewords of a (0,k,k.sub.l,k.sub.r) RLL constrained block code of length
 n, where k.sub.l and k.sub.r denote the maximum number of leading and
 trailing zeros of every codeword. By choosing k.sub.l +k.sub.r.ltoreq.k,
 the codewords can be concatenated without violating the global k
 constraint. In accordance with the above definition of MTR codes,
 (0,k,k.sub.l,k.sub.r) MTR codes are (0,k,k.sub.l,k.sub.r) RLL codes with
 interchanged "ones" and "zeros."
 RLL codes are typically implemented with the use of look-up tables or with
 simple combinatorial circuitry. This imposes limitations on the block
 length n and consequently puts restrictions on the achievable efficiency
 of the codes for the given set of constraints. The majority of codes have
 a block length n.ltoreq.9. Only recently have codes with longer block
 lengths been developed, often by interleaving an existing rate 8/9 code
 with uncoded bits, as described in, e.g., A. J. van Wijngaarden and K. A.
 S. Immink, "Combinatorial Construction of High Rate Runlength-limited
 Codes," IEEE Global Telecommun. Conf. Globecom'96, pp. 343-347, 1996. This
 has the advantage that the rate is increased without increasing error
 propagation. However, the constraints of the resulting code are in these
 cases loose and certainly not the best possible for the given rate.
 Several new coding algorithms have been proposed to efficiently convert
 data words serially into codewords of high-rate constrained block codes.
 These algorithms are simple and have a linear complexity with word length
 n. It is therefore feasible to construct (0,k) codes with a code rate of
 99% or more of the achievable capacity by using long codewords of several
 hundreds of bits. However, the practical application of these codes in
 recording systems is still limited, because most such systems have a
 separate device for modulation and error control. This configuration makes
 longer codes more vulnerable for error propagation. Other important
 concerns are delay and computational and hardware complexity.
 There is currently a specific interest in high-rate constrained codes,
 e.g., rate 16/17, 24/25 and 32/33 constrained codes, with tight
 (0,k,k.sub.l,k.sub.r) constraints. However, it is generally not feasible
 to implement these high-rate codes as a look-up table, and integrating the
 code into a device usually requires a highly parallelized architecture
 with small delay and high throughput. Conventional codes and code
 generation techniques have not adequately addressed these and other
 problems associated with high-rate codes.
 SUMMARY OF THE INVENTION
 The present invention provides improved constraints and techniques for the
 construction of efficient, high-rate, multi-purpose run-length limited
 (RLL) and maximum transition run (MTR) block codes.
 In accordance with a first aspect of the invention, a number of new
 constraints for use in generating RLL and MTR codes are provided. These
 constraints include, e.g., an F={1111, 11100} NRZI strong constraint, an
 F={1111, 00111} NRZI strong constraint, an F={1111, 11100.sub.odd,
 00111.sub.odd } NRZI strong constraint, an F={1111} NRZI weak constraint,
 an F={11111} NRZI weak constraint, and an F={1010} NRZ weak constraint,
 where F denotes a list of forbidden strings, and NRZI or NRZ specifies the
 modulation format.
 In accordance with another aspect of the invention, high-rate codes are
 generated which satisfy one or more of the above-noted constraints. The
 code generation process first partitions each of a set of data words and a
 set of codewords into a number of disjoint subsets. A distinct mapping is
 then generated between a given subset of the data words and a
 corresponding subset of the codewords. A given data word is converted to a
 codeword by applying to the given data word the mapping associated with
 the subset containing that data word. The mappings are configured to
 utilize symmetry whenever possible. For example, if Y=.psi.(X) represents
 the mapping of a given data word X onto a corresponding codeword Y. then
 it is preferred that X' and Y representing the words X and Yin reversed
 order, satisfy the relation Y'=.psi.(X'). An example of an efficient,
 high-rate, multi-purpose code in accordance with the invention is a rate
 16/17 code satisfying (0,15,9,9) RLL and (0,3,2,2) MTR constraints. This
 exemplary code can be further processed using interleaving techniques to
 generate other higher rate codes, e.g., a rate 48/49, (0,11,6,6) code can
 be generated by interleaving symbols of the above-noted rate 16/17,
 (0,3,2,2) code with uncoded bits of a data word, and a rate 32/33,
 (0,7,4,4) code can be generated by interleaving symbols of the rate 16/17,
 (0,3,2,2) code with uncoded bits of a data word.
 Advantageously, the invention provides techniques for generating high-rate,
 multi-purpose distance-enhancing codes with improved timing and gain
 control. Codes generated using these techniques exhibit improved
 performance, improved immunity to noise and ISI, and a more efficient
 encoder and decoder architecture than conventional codes. The codes and
 code generation techniques of the invention can be used in a wide variety
 of systems, e.g., high-density magnetic and optical recording systems,
 data transmission systems, etc.

DETAILED DESCRIPTION OF THE INVENTION
 FIG. 1 shows a coding system 10 in which the coding techniques of the
 invention may be implemented. The coding system 10 includes a data source
 12, an encoder 14, a channel 16, a decoder 18 and an output device 20.
 Binary information from the data source 12 is supplied to the encoder 14
 and block encoded using an RLL or MTR code in accordance with the
 invention. The codes and coding techniques of the invention will be
 described in greater detail below. The encoded sequences at the output of
 encoder 14 are supplied to channel 16, e.g., for recording on a magnetic,
 optical, electronic or other type of recording medium, for transmission
 through a communication medium, or for further processing, e.g.,
 modulation into NRZI format or other desired format, prior to recording,
 transmission, or other operations. The channel 16 may thus represent a
 recording medium, a communication medium, additional processing circuitry,
 as well as combinations of these and other types of elements. Encoded
 sequences received from the channel 16 are applied to the decoder 18, and
 decoded to recover the original binary information. This information may
 then be supplied to an output device for further processing as required in
 a given application.
 The system 10 may be implemented at least in part as a processor-based
 system such as a personal, micro or mainframe computer, a workstation, a
 microprocessor, a central processing unit, an application-specific
 integrated circuit (ASIC) or other digital data processor, as well as
 various portions or combinations thereof. In such a system, a processor
 may interact with one or more memory elements to execute stored software
 programs to carry out the various system functions. For example, the
 operations of the encoder 14 and the decoder 18 may be implemented in
 software executed by a processor associated with the system 10. Such a
 processor may also be used to implement one or more processing functions
 associated with the channel 16. For example, in an embodiment in which the
 channel 16 includes a communication medium, the processor may provide,
 e.g., modulation, framing, packetization or other similar operations for
 formatting the encoded sequences for transmission over a local area
 network, a wide area network, a global data communications network such as
 the Internet, a private "intranet" network or any other suitable data
 communication medium.
 A first aspect of the invention provides improved distance-enhancing
 constraints particularly well suited for use in generating high-rate RLL
 or MTR codes for high density recording channels. This aspect of the
 invention identifies constraints which recorded sequences have to satisfy
 to guarantee that the minimum distance between them is larger than for a
 corresponding uncoded system. This aspect of the invention also identifies
 constraints for which the minimum distance between sequences may be the
 same as for the uncoded system but the number of pairs of sequences at the
 minimum distance is smaller.
 Constrained codes are most often derived based on constrained systems of
 finite type (FT). An FT system X over alphabet A can always be
 characterized by a finite list of forbidden strings F={w.sub.1, . . . ,
 w.sub.N } of symbols in A. Such an FT system will be denoted
 X.sub.F.sup.A. A set of constraints for a binary channel can be written in
 the form of a directed graph with a finite number of states and edges, and
 edge labels drawn from the binary alphabet. The set of corresponding
 constrained sequences is obtained by reading the labels of paths through
 the graph. A constrained code C, C.OR right. X.sub.F.sup.{0,1} can be
 constructed based on a graph representation of X.sub.F.sup.{0,1} using the
 well-known state splitting algorithm, as described in, e.g., R. Adler, D.
 Coppersmith and M. Hassner, "Algorithms for sliding-block codes," IEEE
 Trans. Inform. Theory, Vol. 29, No. 1, pp. 5-22, January 1983.
 Translation of constrained sequences into channel sequences depends on the
 modulation method. For magnetic recording channels, the
 previously-described NRZI modulation records a "one" as a transition in
 cell magnetization, and a "zero" as the absence of a transition, while in
 NRZ modulation a "one" is a given direction of magnetization, and "zero"
 is the opposite magnetization direction. A channel constraint which
 forbids transitions in two neighboring bit cells for the case of NRZI
 modulation can be written as F={11} NRZI.
 The maximum rate of a code in a constrained system is determined by its
 Shannon capacity. The Shannon capacity C of a constrained system is
 defined as
 ##EQU1##
 where N(n) is the number of sequences of length n. The capacity of an FT
 constrained system represented by a graph G can be easily computed from an
 adjacency matrix, i.e., state transition matrix, of G. The adjacency
 matrix A of graph G with r states and a.sub.ij edges from state i to state
 j, where 1.ltoreq.i and j.ltoreq.r, is the r.times.r matrix
 A=A(G)={a.sub.ij }.sub.r.times.r. The Shannon capacity of G is given by
EQU C=log.sub.2 .lambda.(A),
 where .lambda.(A) is the largest real eigenvalue of A.
 Constrained codes can be used to provide coding gain on channels with high
 ISI, as will now be described in greater detail. The minimum distance of
 the uncoded binary channel with transfer function h(D) is defined by
 ##EQU2##
 where
 ##EQU3##
 and .epsilon..sub.i .di-elect cons.{-1, 0, 1}, .epsilon..sub.0 =1,
 .epsilon..sub.l-1.noteq.0, is the polynomial corresponding to a normalized
 input error sequence
 ##EQU4##
 of length l, and the squared norm of a polynomial is defined as the sum of
 its squared coefficients. The minimum distance is bounded from above by
 .vertline..vertline.h(D).vertline..vertline..sup.2, denoted by
 ##EQU5##
 This bound is known as the matched-filter bound (MFB), and is achieved when
 the error sequence of length l=1, i.e., .epsilon.(D)=1, is in the set
 ##EQU6##
 For channels that fail to achieve the MFB, i.e., for which
 ##EQU7##
 error sequences .epsilon.(D) for which
 ##EQU8##
 are of length l.gtoreq.2 and may belong to a constrained system
 X.sub.L.sup.{-1,0,1}, where L is an appropriately chosen finite list of
 forbidden strings.
 For code C, the set of all admissible non-zero error sequences are defined
 as
EQU E(C)={.epsilon.={e.sub.i }.vertline.e.sub.i.di-elect cons.{-1,0,1}, e.sub.0
 =1, .epsilon.=a-b, a,b.di-elect cons.C}.
 Given the condition E(C).OR right.X.sub.L.sup.{-1,0,1}, the objective is to
 identify the least restrictive finite list F of blocks over the alphabet
 {0,1} so that
EQU C.OR right.X.sub.F.sup.{0,1} {character pullout}E(C).OR
 right.X.sub.L.sup.{-1,0,1}. (4)
 A constrained code is defined by specifying F, the list of forbidden
 strings for code sequences. Prior to that one needs to first characterize
 error sequences that satisfy (3) and then specify L, the list of forbidden
 strings for error sequences. Error event characterization can be done by
 using known methods, and specification of L is usually straightforward.
 One possible way to construct the list F based on the list L is as
 follows. From the above definition of error sequences .epsilon.={e.sub.i }
 it can be seen that see that e.sub.i =1 requires a.sub.i =1 and e.sub.i
 =-1 requires a.sub.i =0, i.e., a.sub.i =(1+e.sub.i)/2. For each block
 w.sub.e.di-elect cons. L, construct a list F.sub.w, of blocks of the same
 length l according to the rule:
EQU F.sub.w ={w.sub.C.di-elect cons.{-1, 1}.sup.l.vertline.w.sub.C.sup.i
 =(1+w.sub.C.sup.i)/2 for all i for which w.sub.C.sup.i.noteq.0}.
 Then the list F obtained as
 ##EQU9##
 satisfies equation (4). However, the constrained system X.sub.F.sup.{0,1}
 obtained this way may not be the most efficient.
 A number of constraints in accordance with the invention will now be
 presented in conjunction with FIGS. 2 through 7. These constraints are
 illustrated for the above-noted E.sup.2 PR4 channel, for which the
 transfer function is h(D)=(1-D)(1+D).sup.3, and its MFB, determined by
 .epsilon.(D)=1, is
 .vertline..vertline.(1-D)(1+D).sup.3.multidot.1.vertline..vertline.=10.
 The list L of forbidden error strings is given by L={+-+00,+-+-}, where +
 denotes 1 and - denotes -1. In each case, the constraints are obtained as
 follows. For each of the error strings in list L, all pairs of channel
 strings whose difference is the error string are determined. The list F is
 then determined by searching for the longest string(s) appearing in at
 least one of the strings in each channel pair. The list F specifies the
 necessary conditions that have to be satisfied in order to achieve the
 matched filter bound for the E.sup.2 PR4 channel.
 FIGS. 2A-2C, 3A-3C, 4A-4D, 5A-5C, 6A-6C and 7A-7C illustrate the
 constraints in greater detail. These six sets of figures correspond to an
 F={1111, 11100} NRZI strong constraint, an F={1111, 00111} NRZI strong
 constraint, an F={1111, 11100.sub.odd, 00111.sub.odd } NRZI strong
 constraint, an F={1111} NRZI weak constraint, an F={11111} NRZI weak
 constraint, and an F={1010} NRZ weak constraint, respectively. The strong
 constraints remove all channel pairs involved in forming the above-noted
 error event +-+00, while the weak constraints do not remove all channel
 pairs involved in forming the error event +-+00. Each of the six sets of
 figures shows the strings eliminated by the constraint for channel pairs a
 and b (FIGS. 2A, 3A, 4A, 5A, 6A and 7A), a graph representation of the
 constraint (FIGS. 2B, 3B, 4B, 5B, 6B and 7B), and the adjacency matrix A
 and corresponding capacity C associated with the constraint (FIGS. 2C, 3C,
 4D, 5C, 6C and 7C). FIG. 4C shows a graph representation with the minimal
 number of states for the F={1111, 11100.sub.odd, 00111.sub.odd } NRZI
 strong constraint.
 The above-described constraints can be used to design efficient high-rate
 RLL and MTR codes in accordance with the invention. By way of example, it
 will be described in detail below the manner in which rate 16/17,
 (0,3,2,2) MTR codes that also fulfil (0,15,9,9) RLL constraints can be
 generated from the F={1111} NRZI and F={11111} NRZI weak constraints
 illustrated in conjunction with FIGS. 5A-5C and 6A-6C. In order to
 generate the rate 16/17 block codes satisfying the F={1111} NRZI and
 F={11111} NRZI weak constraints, the codewords are permitted to have
 strings 11 at the beginning and the end of the codewords. Therefore, the
 resulting codes permit the string 1111 at transitions between codewords.
 It will be apparent to those skilled in the art that the other constraints
 described herein can be similarly processed to generate other codes.
 As noted above, in the construction of maximum (0,k) RLL codes, long
 sequences that fulfil the (0,k) constraints are typically constructed by
 concatenating the codewords of a (0,k,k.sub.l,k.sub.r) RLL constrained
 block code of length n, where k.sub.l and k.sub.r denote the maximum
 number of leading and trailing zeros of every codeword. By choosing
 k.sub.l +k.sub.r &lt;k, the codewords can be concatenated without violating
 the global k constraint. Also as previously noted, (0,k,k.sub.l,k.sub.r)
 MTR codes correspond to (0,k,k.sub.l,k.sub.r) RLL codes with interchanged
 "ones" and "zeros."
 The set of binary sequences of a fixed length that fulfil given
 (0,k,k.sub.l,k.sub.r) constraints can be determined recursively. Before
 the recursive relations are described, the following notation is
 introduced. Let A.sup.m denote the set of binary sequences of length m. A
 run of s consecutive symbols a is written as a.sup.s. The character * is
 used to denote an arbitrary symbol of A. The sequence (*).sup.s represents
 an arbitrary element of A.sup.s. A sequence X .di-elect cons. A.sup.m will
 be often represented as a string of binary symbols x.sub.1 x.sub.2 . . .
 x.sub.m. Define H.sup.(m) .OR right.A.sup.m to be a set of sequences of
 length m. The concatenation of two sequences X and Y is denoted by XY, and
 PH.sup.(m) denotes a set of sequences of length p+m with prefix P
 .di-elect cons. A.sup.P and suffix Y, where Y .di-elect cons. H.sup.(m),
 in short, PH.sup.(m) ={PY.vertline.Y .di-elect cons. H.sup.(m) }.
 Similarly, H.sup.(m) S={YS.vertline.Y .di-elect cons. H.sup.(m) }. The null
 string, denoted by .LAMBDA., is introduced to represent a string of length
 0, for which the equation .LAMBDA.X=X.LAMBDA.=X holds.
 Let
 ##EQU10##
 denote the set of sequences of length n that satisfy the
 (0,k,k.sub.l,k.sub.r) constraints on the runs of consecutive zeros, where
 k.sub.l.ltoreq.k and k.sub.r &lt;k. The number of elements of
 ##EQU11##
 denoted by
 ##EQU12##
 can be determined recursively. For n.ltoreq.min(k.sub.l,k.sub.r),
 ##EQU13##
 and
 ##EQU14##
 For n&gt;k.sub.l, the set
 ##EQU15##
 satisfies the recursion relation
 ##EQU16##
 The set
 ##EQU17##
 where, as indicated, k.sub.l =k, can be determined using the same recursion
 relation for any value of t.gtoreq.k+2. For t.ltoreq.k.sub.r,
 ##EQU18##
 and for t=k.sub.r +1,
 ##EQU19##
 For k.sub.r +2.ltoreq.t.ltoreq.k+1, it can be shown that
 ##EQU20##
 For t.ltoreq.k+1, the value of
 ##EQU21##
 is given by
 ##EQU22##
 For n.gtoreq.k+2, since the union of the sets in (5) is disjoint, the
 recursion relation is given by
 ##EQU23##
 In a similar fashion,
 ##EQU24##
 is defined as the set of sequences of length n that satisfy the
 (0,k,k.sub.l,k.sub.r) constraints on the runs of consecutive zeros, and
 denote
 ##EQU25##
 as the size of
 ##EQU26##
 Reversing
 the zeros and the ones in the above derivation yields expressions for
 ##EQU27##
 and
 ##EQU28##
 that are identical to those given previously for
 ##EQU29##
 As will be illustrated below, these expressions can be used to determine
 the number of subsequences of a given length that satisfy given
 (0,k,k.sub.l,k.sub.r) constraints.
 An efficient methodology for the construction of (0,k,k.sub.l,k.sub.r)
 codes in accordance with the invention involves mapping (n-1)-bit data
 words onto n-bit codewords of a (0,k,k.sub.l,k.sub.r) code. If the number
 of sequences of length n that satisfy the (0,k,k.sub.l,k.sub.r)
 constraints exceeds 2.sup.n-1, it is always possible to perform this
 mapping, although the complexity may be high. For several codeword lengths
 it is possible to realize this mapping procedure using a small digital
 combinatorial circuit. The codes to be described below in conjunction with
 an illustrative embodiment of the invention are characterized by a set of
 data-dependent mapping rules. The encoder first checks whether the data
 word would be a valid codeword. If this is the case, the encoder copies
 the data word and inserts one extra bit that indicates that the other bits
 of the codeword are a copy of the data word. Otherwise, the extra bit
 indicates that a mapping rule had to be applied to transform the data word
 into an (n-1)-bit coded sequence that satisfies the imposed
 (0,k,k.sub.l,k.sub.r) constraints. The coded sequence, which uniquely
 represents the data word, comprises bits which identify the mapping used,
 and rearranged data bits. The mapping structure is preferably symmetric to
 simplify the design process and the structure of the digital combinatorial
 circuitry.
 The above-described code construction methodology of the present invention
 has the following characteristics:
 1. A mapping is defined for a set of data words rather than for one word.
 Based on the specific constraints, the set of data words and the set of
 codewords are partitioned into disjoint subsets. For every set a mapping
 is specified. The words belonging to the same subset are transformed in
 the same fashion.
 2. Symmetry is used whenever possible, i.e., if Y=.psi.(X) represents the
 mapping of X onto Y. then X' and Y', representing the words X and Y in
 reversed order, satisfy whenever possible the relation Y'=.psi.(X'). This
 significantly simplifies the design.
 3. The relative position of the information bits is changed only if
 necessary. Whenever changes are necessary to fulfil the constraints, the
 data symbols are permuted instead of transformed.
 4. The translation of (n-1) information bits into n-bit codewords and vice
 versa is done in parallel.
 5. The combinatorial circuitry that results from the methodology classifies
 the incoming data word, and rearranges the data bits based on the
 classification in order to satisfy the constraints.
 The methodology given above is particularly well suited for the
 construction of tightly constrained codes with a short and medium
 wordlength, e.g., a wordlength of 4 to 32 bits, and possibly up to 64 bits
 with slightly looser constraints. The constructed codes can also be used
 as a basic code to obtain longer and higher rate codes with less tight
 constraints by using interleaving with uncoded data symbols.
 The design of a rate 16/17, (0,3,2,2) MTR, (0,15,9,9) RLL code in
 accordance with the invention will now be described in detail. The
 objective is to construct a code C that is a subset of
 ##EQU30##
 and has a cardinality 2.sup.16. Since
 ##EQU31##
 there is a surplus of 217 codewords. The surplus codewords allow one to
 simultaneously fulfil (0,15,9,9) RLL constraints by excluding 199 words to
 obtain a code
 ##EQU32##
 with a surplus of 18 candidate words.
 An illustrative technique of mapping source words onto codewords that
 fulfil both the (0,3,2,2) MTR constraints and the (0,15,9,9) RLL
 constraints will now be described. As will be appreciated by those skilled
 in the art, this technique inherently specifies the structure of the
 encoder and decoder that map 16-bit data words in parallel onto 17-bit
 codewords and vice versa.
 In the mapping technique, the symmetry relative to the central position of
 the codeword plays an important role. Let Y=y.sub.1 y.sub.2 . . . y.sub.17
 be an arbitrary element of A.sup.17 and denote Y'=y.sub.17 . . . y.sub.2
 y.sub.1 to be the sequence Y in reversed order. The set
 ##EQU33##
 has the property that
 ##EQU34##
 if and only if
 ##EQU35##
 Let Y=.psi.(X) denote the mapping of a 16-bit data word onto a 17-bit
 codeword. Whenever possible, Y ' will be the codeword associated with X',
 i.e., Y'=.psi.(X'). This will help to reduce the complexity of the
 analysis and the design.
 Let X .di-elect cons. A.sup.16 denote the 16-bit source word. The
 above-noted symmetry is taken into account by decomposing X into two
 sequences X.sup.l =x.sub.1.sup.l x.sub.1.sup.l . . . x.sub.8.sup.l and
 X.sup.r =x.sub.1.sup.r x.sub.2.sup.r . . . x.sub.8.sup.r, where X.sup.l
 .di-elect cons. A.sup.8 and X.sup.r .di-elect cons. A.sup.8. Let X.sup.r'
 be the sequence X.sub.r in reversed order, i.e., X.sup.r' =x.sub.8.sup.r
 x.sub.7.sup.r . . . x.sub.1.sup.r. The source word X is given by
EQU X=X.sup.l X.sup.r' =x.sub.1.sup.l x.sub.2.sup.l x.sub.3.sup.l x.sub.4.sup.l
 x.sub.5.sup.l x.sub.6.sup.l x.sub.7.sup.l x.sub.8.sup.l x.sub.8.sup.r
 x.sub.7.sup.r x.sub.6.sup.r x.sub.5.sup.r x.sub.4.sup.r x.sub.3.sup.r
 x.sub.2.sup.r x.sub.1.sup.r
 Let Y denote the codeword, where the symbols are indexed as follows
EQU Y=y.sub.1.sup.l y.sub.2.sup.l y.sub.3.sup.l y.sub.4.sup.l y.sub.5.sup.l
 y.sub.6.sup.l y.sub.7.sup.l y.sub.8.sup.l y.sub.c y.sub.8.sup.r
 y.sub.7.sup.r y.sub.6.sup.r y.sub.5.sup.r y.sub.4.sup.r y.sub.3.sup.r
 y.sub.2.sup.r y.sub.1.sup.r
 where y.sub.c denotes the central position of the 17-bit codeword. The
 indices reflect the symmetry relative to the central position of the
 codeword.
 Consider the 17-bit word Y=X.sup.l 0X.sup.r', i.e., y.sub.i.sup.l
 =x.sub.i.sup.l, y.sub.i.sup.r =x.sub.i.sup.r for 1.ltoreq.i.ltoreq.8, and
 y.sub.c =0. It can be verified that
 ##EQU36##
 if and only if
 ##EQU37##
 and
 ##EQU38##
 i.e.,
 ##EQU39##
 Let
 ##EQU40##
 denote the set of words of length 8 that fulfil the (0,3,2,3) MTR
 constraints. The set A.sup.8.backslash.V.sub.0 is partitioned into five
 disjoint subsets V.sub.1, . . . , V.sub.5, which are specified in the
 table of FIG. 8. Every set V.sub.i, 1.ltoreq.i.ltoreq.5, consists of words
 that have a substring that violates the imposed (0,3,2,3) MTR constraints
 in common. Define V.sub.i to be the size of the set V.sub.i. The values of
 V.sub.1 through V.sub.5 are specified in the last column of the table in
 FIG. 8. The size of V.sub.0 is given by
 ##EQU41##
 Since the six sets V.sub.0, V.sub.1, . . . , V.sub.5 are disjoint and their
 union equals A.sup.8, every data word X .di-elect cons. A.sup.16 can be
 represented by X=X.sup.l X.sup.r', where X.sup.l .di-elect cons. V.sub.i
 and X.sup.r .di-elect cons. V.sub.j. The sets W.sub.i,j
 =V.sub.i.times.V.sub.j are disjoint and therefore the set of data words
 A.sup.16 is uniquely partitioned. This implies that there are 36 different
 sets W.sub.i,j that have to be considered. Define W.sub.i,j to be the
 number of elements in the set W.sub.i,j. FIG. 9 shows a table listing the
 values of W.sub.i,j =V.sub.i V.sub.j for each of the 36 sets W.sub.i,j. It
 can be verified that, as expected, the sum of the values W.sub.i,j that
 are given in the table of FIG. 9 is equal to 65536, i.e., 2.sup.16.
 To determine to which set V.sub.i a word X .di-elect cons. A.sup.8 belongs
 to, one can evaluate the following set of equations, which are obtained
 from the table in FIG. 8:
 ##EQU42##
 where x.sub.i denotes the inverse of the binary value x.sub.i and the
 ".multidot." operator denotes the binary AND operation.
 Exactly one out of the six binary values v.sub.0, . . . , v.sub.5 will be
 non-zero. In order to determine the particular set W.sub.i,j that a given
 data word X belongs to, this set of equations is evaluated for X.sup.l and
 X.sup.r. It is often necessary to further partition the sets W.sub.i,j
 into P.sub.i,j disjoint subsets, denoted by W.sub.i,j.sup.[p], where
 1.ltoreq.p.ltoreq.P.sub.i,j. These partitions have the property that
 ##EQU43##
 and
 ##EQU44##
 The set
 ##EQU45##
 will be partitioned into eight disjoint subsets M.sub.0, . . . , M.sub.7
 which are specified in the table of FIG. 10. The dots in this table are
 placeholders for binary symbols of elements of the set specified in the
 third column of the table. It can be seen that all the possible
 combinations of the central positions are specified. The rightmost column
 gives the number of codewords of M.sub.i. The sum of the last column
 equals
 ##EQU46##
 Because of the symmetry of the central positions,
 .vertline.M.sub.2m-1.vertline.=.vertline.M.sub.2m.vertline. for
 1.ltoreq.m.ltoreq.3. The sets M.sub.i, where 1.ltoreq.i.ltoreq.7,
 automatically fulfil the (0,15,9,9) RLL constraints in addition to the
 (0,3,2,2) MTR constraints.
 Having completed partitioning the set of data words and the set of
 candidate codewords, the next step is to specify the assignment of
 codewords to data words in a compact format by mappings which inherently
 define the encoder and the decoder.
 The mapping of a set of data words X .di-elect cons. W.sub.i,j.sup.[p] onto
 a set of codewords Y .di-elect cons. M is specified by the templates
 X.sub.i,j[p] and Y.sub.i,j[p]. The first string, X.sub.i,j[p], specifies
 the set W.sub.i,j.sup.[p] by indicating the relative positions of zeros,
 ones and data symbols. The second string, Y.sub.i,j[p], specifies the
 subset of M.sub.s onto which the elements of X .di-elect cons.
 W.sub.i,j.sup.[p] are mapped.
 In the illustrative embodiment, central positions of which the rightmost
 position is a zero and the leftmost position a one indicate a violation at
 the lefthand side. This makes it straightforward to use the symmetry and
 the central positions in reversed order to handle the violations at the
 righthand side. It will be shown that it is possible to specify one
 mapping for several sets W.sub.i,j. The elements X of the sets W.sub.i,0,
 where 1.ltoreq.i.ltoreq.5, will be mapped onto elements of the sets
 M.sub.1, M.sub.3 and M5.
 The mapping of an element X .di-elect cons. W.sub.i,j.sup.[p] onto an
 element Y .di-elect cons. M.sub.2m-1 where 1.ltoreq.m.ltoreq.3 almost
 always implies that the element X' .di-elect cons. W.sub.i,j.sup.[p] will
 be mapped onto the element Y' .di-elect cons. M.sub.2m. Whenever this is
 the case, the mapping will be marked with an S.
 Consider first the mapping of elements X .di-elect cons. W.sub.0,0 which is
 specified in a compact format in the table of FIG. 11. The elements X
 .di-elect cons. W.sub.0,0 are mapped onto the elements of M.sub.0, unless
 the (0,15,9,9) RLL constraints are violated. The table of FIG. 11
 specifies the subsets W.sub.0,0.sup.[1] up to W.sub.0,0.sup.[4] for which
 the (0,15,9,9) RLL constraints would be violated. The subsequences that
 violate the constraints are shown in bold-face type in the table to
 emphasize the kind of violation that is under consideration. The
 underlined zeros and ones in the template Y indicate which positions
 uniquely specify the mapping. The decoder checks these positions, and if
 there is a match, the mapping will be reversed to reconstruct the data
 word.
 The mapping of the elements X .di-elect cons. W.sub.0,0.sup.[1] will now be
 considered in more detail. The template X specifies the additional
 constraints that are imposed. Since X.sup.l .di-elect cons. V.sub.0, the
 data sequence
 ##EQU47##
 In other words, X specifies
 ##EQU48##
 48 different data words. The template Y specifies the corresponding
 codewords. Since sequence
 ##EQU49##
 the subsequence
 ##EQU50##
 and the subsequence
 ##EQU51##
 This guarantees that the words corresponding to template Y satisfy the
 imposed constraints.
 The five mappings in the table of FIG. 11 specify the transformation of
 W.sub.0,0 =37249 data words into codewords. All the elements of M.sub.0
 are paired with data words. Let
 ##EQU52##
 and
 ##EQU53##
 To determine to which set W.sub.0,0.sup.[i] a word X .di-elect cons.
 W.sub.0,0 belongs to, one can evaluate the following set of equations,
 which are directly obtained from the table in FIG. 11:
 ##EQU54##
 It can be verified that exactly one out of the five binary values
 w.sub.0,0[1], . . . , w.sub.0,0[5] will be non-zero.
 The mapping for the data words X .di-elect cons. W.sub.i,{0, . . . }, where
 1.ltoreq.i.ltoreq.5, is specified in the table of FIG. 12. The character S
 in the rightmost column of this table marks the sets W.sub.i,j.sup.[p]
 that have the property that by reversing the order of X and Y the mapping
 of the set W.sub.j,i.sup.[p] specified. Sets having the same property with
 the exception that the central indicator 00100 is replaced by 01110 and
 vice versa, are marked by S' in the table.
 Observe that in several cases the indicator in the middle ofthe codeword
 causes the righthand side of the codeword to satisfy the constraints.
 There are in fact 12 out of the 25 subsets W.sub.i,j, with
 1.ltoreq.i,j.ltoreq.5, which no longer have to be considered. The mapping
 for the other sets will be specified separately in subsequent tables.
 Consider first the situation for the sets W.sub.i,j where
 1.ltoreq.i.ltoreq.3 and 1.ltoreq.j.ltoreq.3. The mapping, specified in the
 table of FIG. 13, is of the form Y=.psi.(X)=.psi..sub.l (X.sup.l) 1
 .psi..sub.r (X.sup.r) .psi. M.sub.7, i.e., the left part of the codeword Y
 is specified by a mapping .psi..sub.l (X.sup.l) which depends on X.sup.l
 only. The same holds for the right part of the codeword, which is given by
 .psi..sub.r (X.sup.r), depending on X.sup.r only.
 As an example, consider the data word X=X.sup.l X.sup.r' =11101001
 11111110. It can be shown that X.sup.1 .di-elect cons. V.sub.1.sup.[2] and
 X.sup.r .di-elect cons. V.sub.2.sup.[1]. The table of FIG. 13 indicates
 that in this situation X.sup.l is mapped onto Y.sup.l =10001010 and
 X.sup.r is mapped onto Y.sup.r =10111010. The resulting codeword Y=Y.sup.l
 Y.sup.r' =10001010 1 01011101.
 It can be verified that .vertline.V.sub.1.sup.[1].vertline.=4,
 .vertline.V.sub.1.sup.[2].vertline.=28,
 .vertline.V.sub.2.sup.[1].vertline.=2,
 .vertline.V.sub.2.sup.[2].vertline.=6 and .vertline.V.sub.3.vertline.=8.
 Since the above-described mapping applies to both the lefthand side and
 the righthand side of an element X .di-elect cons. W.sub.i,j, where
 1.ltoreq.i.ltoreq.3 and 1.ltoreq.j.ltoreq.3, there are in total
 48.times.48=2304 data words that fall into this category and that are
 transformed in accordance with these rules. Note that the set M.sub.7 with
 central indicator 10101 is used exclusively to identify this category.
 The mapping of the words X .di-elect cons. W.sub.4,1 is specified in the
 table of FIG. 14.
 The sets W.sub.4,4 and W.sub.5,5 are the only sets for which the mapping
 has not yet been specified. As there are only very few candidate words
 remaining, the sets have to be further partitioned in the manner
 previously described in order to be able to map all their elements. The
 resulting mapping is specified in the table of FIG. 15.
 At this stage the specification of the mapping from the data words to the
 codewords is completed. The table in FIG. 16 gives an overview of the
 number of sequences of the sets M.sub.0 through M.sub.7 that are part of
 the code set.
 FIG. 17 shows a table listing the 18 surplus candidate words in this
 illustrative embodiment. One or more of these words may be used to replace
 codewords or as special recognition sequences for frame synchronization.
 FIG. 18 shows a table listing the partitions of the sets M.sub.1, M.sub.3
 and M.sub.5. The dots are placeholders for the data values. It can be seen
 that the patterns of underlined zeros and ones in this table uniquely
 identify the corresponding sets of data words W.sub.i,j.sup.[p]. By
 reversing the mapping that has been specified for this particular set, the
 data words can be reconstructed. The partitions of the sets M.sub.2,
 M.sub.4 and M.sub.6 are, because of the symmetry, very similar.
 It is important to restrict the number of consecutive zeros in the sequence
 of concatenated codewords in order to have a sufficient number of
 transitions in the NRZI modulated signal over a designated period of time,
 for purposes of clock recovery. The constructed 16/17, (0,3,2,2) MTR code
 described above fulfils the (0,15,9,9) RLL constraints. Let
 k.sub.l.sup.(0) and k.sub.r.sup.(0) denote the number of leading and
 trailing zeros of a particular codeword, and let k.sup.(0) denote the
 maximum run of zeros in the codeword. To estimate the likelihood that
 sequences with long runs of consecutive zeros occur, one can determine the
 number of codewords for which k.sup.(0) =i. The table in FIG. 19 gives the
 distribution of k.sup.(0), where 0.ltoreq.i.ltoreq.17, for the 2.sup.16
 codewords. The number of codewords for which k.sub.l.sup.(0) =i,
 0.ltoreq.i.ltoreq.17, and the number of codewords for which
 k.sub.r.sup.(0) =i, 0.ltoreq.i.ltoreq.17, is also specified in the FIG. 19
 table.
 It can be seen that, in compliance with the illustrative code design
 constraints, max (k.sub.l.sup.(0))=9, max (k.sub.r.sup.(0) =9, and max
 (k.sup.(0))=15. Since there is a surplus of 18 words in this design, it is
 possible to obtain a 16/17, (0,3,2,2) MTR code that fulfils (0,12,9,9) RLL
 constraints by removing the 15 words that exceed these constraints.
 However, it is not possible to further restrict the number of leading and
 trailing zeros, as this would require a surplus of at least 93 words.
 Since k.sub.l.sup.(0) +k.sub.r.sup.(0) is at most 18, a reduction of the
 k.sup.(0) constraint from 15 to 12 is not expected to give a significant
 improvement in performance.
 The above-described illustrative MTR-RLL code can be expanded into other
 useful codes, as will be described below in conjunction with FIGS. 20
 through 25.
 The rate 16/17, (0,3,2,2) MTR code, being equivalent to a (0,3,2,2) RLL
 code, could be used as a basic code for the construction of higher rate
 codes using interleaving. For example, interleaving the (0,3,2,2) RLL code
 in the manner illustrated in FIG. 20 results in a rate 48/49, (0,11,6,6)
 code. In FIGS. 20 through 25, a box containing an "x" is a placeholder for
 a symbol of the basic (0,3,2,2) RLL code, and an open box is a placeholder
 for interleaved uncoded information bits.
 In order to suppress error propagation, one can use a strategy where the
 data symbols remain unchanged unless the (0,12,6,6) constraints are
 violated. Consider the codeword profile shown in FIG. 21, where the 16
 positions denoted by a box containing a ".multidot." represent the input
 data of the (0,3,2,2) RLL code. The middle position is set to 1 as shown.
 If this string of length 49 already fulfils the (0,12,6,6) constraints,
 there is no need to transform the input. However, if the (0,12,6,6)
 constraints are violated, the (0,3,2,2) RLL code can be used to fulfil the
 constraints. Since the input data will be transformed in this situation,
 the middle position will be equal to zero, as illustrated in FIG. 22. At
 the decoder side, the middle position of the code indicates whether or not
 the input data was encoded.
 The probability that the data input of the 48/49 (0,12,6,6) code will need
 to be transformed to satisfy the constraints is very low. There are
 ##EQU55##
 words of length 24 that satisfy the (0,12,6,12) constraints. Since the
 default value of the middle position is 1, thereby separating the code in
 two independent blocks of 24 bits, the number of words that do not have to
 be converted is equal to (16634912).sup.2. This means that the probability
 that the input of the rate 16/17, (0,3,2,2) code has to be transformed to
 satisfy the constraints of the 48/49 (0,12,6,6) code is equal to
 ##EQU56##
 i.e., the input will have to be transformed in about 1.69 percent of the
 cases. Since the idea behind the 16/17 (0,3,2,2) code was to change only a
 limited number of bits to satisfy the constraints, it is expected that the
 48/49 code will be very close to the uncoded situation, in which case
 there will be a very limited probability of error propagation if detection
 errors occur.
 An alternative interleaving technique for obtaining a 48/49, (0,11,6,6)
 code using the basic 16/17, (0,3,2,2) code is illustrated in FIG. 23. This
 arrangement has the advantage that every codeword starts and ends with
 unconstrained positions, which means that burst errors at the boundaries
 do not cause any error propagation. In addition, the spacing between coded
 bits is either 4 or 8 unconstrained bits, i.e., it is byte-level oriented.
 As the single bytes are separated, short bursts are more likely to destroy
 one uncoded byte only.
 In a similar fashion as for the above-described rate 48/49 code, it is
 possible to obtain a 32/33, (0,7,4,4) code from the basic 16/17, (0,3,2,2)
 code by interleaving the codewords with uncoded bits according to one of
 the profiles shown in FIG. 24. Since there are
 ##EQU57##
 words of length 16 that fulfil the (0,8,4,8) constraints, the probability
 that a data word needs to be converted is 0.0746. If one would like to
 have run-length constraints that are less tight than (0,8,4,4), one could
 for example use a rate 8/9 code that was designed to minimize the
 run-length constraints when the code is interleaved.
 By interleaving the rate 8/9, (0,3,2,2) code specified in K. A.
 Schouhamer-Immink and A. Wijngaarden, "Simple high-rate constrained
 codes," Electronics Letters, Vol. 32, No. 20, p. 1877, 1996, which is
 incorporated by reference herein, a rate 32/33, (0,11,6,6) code can be
 constructed. The resulting codeword profile is shown in FIG. 25. In this
 case there are exactly 8 bits between the blocks of codeword symbols. If
 this code is used to obtain a rate 32/33, (0,12,6,6) code, there will be
 ##EQU58##
 sequences of length 16 that satisfy the (0,12,6,12) constraints and
 therefore the probability that a data word needs to be converted is
 ##EQU59##
 It should be emphasized that the exemplary codes and coding techniques
 described herein are intended to illustrate the operation of the
 invention, and therefore should not be construed as limiting the invention
 to any particular embodiment or group of embodiments. These and numerous
 other alternative embodiments within the scope of the following claims
 will therefore be apparent to those skilled in the art.