Coded data generation or conversion – Digital code to digital code converters – To or from minimum d.c. level codes
Reexamination Certificate
1999-06-18
2001-06-05
Tokar, Michael (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
To or from minimum d.c. level codes
C341S058000, C341S059000, C341S068000, C341S069000, C341S106000
Reexamination Certificate
active
06241778
ABSTRACT:
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≧2 are usually referred to as E
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
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
l
,k
r
) RLL constrained block code of length n, where k
l
and k
r
denote the maximum number of leading and trailing zeros of every codeword. By choosing k
l
+k
r
≦k, the codewords can be concatenated without violating the global k constraint. In accordance with the above definition of MTR codes, (0,k,k
l
,k
r
) MTR codes are (0,k,k
l
,k
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≦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
l
,k
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
odd
, 00111
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=&psgr;(X) represents the mapping of
de Lind van Wijngaarden Adriaan J.
Soljanin Emina
Lucent Technologies - Inc.
Ryan & Mason & Lewis, LLP
Tan Vibol
Tokar Michael
LandOfFree
Methods and apparatus for implementing run-length limited... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and apparatus for implementing run-length limited..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for implementing run-length limited... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2453186