Coded data generation or conversion – Digital code to digital code converters – To or from run length limited codes
Reexamination Certificate
1999-09-17
2002-06-04
Tokar, Michael (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
To or from run length limited codes
C341S050000, C341S058000, C341S063000, C341S067000, C341S068000, C341S071000, C341S072000, C360S040000, C375S260000, C375S261000, C375S265000, C375S251000
Reexamination Certificate
active
06400288
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to encoding data for transmission through a channel and for decoding such encoded data after its transmission through a channel. In particular, the present invention relates to encoders and decoders in communication systems for information storage and retrieval.
Information that is transmitted from a source to a destination can be considered generically to pass through a channel. In some communication systems, the channel comprises electromagnetic radiation passing through the atmosphere. In other communication systems, the channel comprises a long conductor between the source and destination. Still other communication systems comprise a magnetic disk, where information from the source is stored on the disk and later retrieved from the disk for delivery to the destination.
In early storage systems, an analog read signal was generated from the disk and converted into digital data by assuming that a current digital value was unaffected by its predecessor values in the read signal. Later systems recognized that the writing and reading operations could be modeled as a communication channel and that this communication channel exhibited certain partial response characteristics in which neighboring values in the channel affected each other.
Using this channel model, many current systems utilize a Partial Response Maximum Likelihood (PRML) approach when attempting to detect and decode data read from a storage medium. Under PRML, a read signal is generated from the medium and sampled to produce a sequence of samples. These samples are then passed through a filter to fit the samples to a desired channel response. A detector then determines the most likely data sequence given the sequence of samples.
Before storing the data on the medium, most systems encode the data to improve certain performance characteristics. In particular, most codes attempt to limit the number of consecutive same symbols in the data. This is especially important in storage systems that detect physical transitions along the medium in order to read back data. In such systems, a binary “1” is typically written as a transition on the medium and a binary “0” is typically written as no transition. If there are too many consecutive 1's in the data, the transitions on the medium can interfere with each other. If there are too many consecutive 0's, the system is not able to generate an accurate read clock from the data.
Recently, some codes have been devised that limit the number of consecutive 1's to less than four. In such codes, it has been found that detection errors can occur when three consecutive 1's in a code word are mistakenly detected as beginning one code bit earlier or one code bit later than where they actually begin. This type of error has come to be known as a shifted tribit error.
To reduce the likelihood of a shifted tribit error, codes have been developed that limit the starting positions of tribits in the code word. (See W. Bliss, “An 8/9 rate time-varying trellis code for high density recording,” Intermag 97; and P. Siegel et al.,” An 8/9 rate trellis code for E
2
PR4,” presented UCSD CMRR, May 1997.) Under these codes, tribits are allowed to begin at either even code bit positions or odd code bit positions but not both. In a detector for such a code, detection paths that include tribits beginning outside of an allowed bit position are removed from consideration. Thus, a shifted tribit error cannot occur because a recovered word with a shifted tribit is not recognized as a valid code word.
Although such codes reduce tribit errors, they also reduce the number of available code words that can be used during encoding. In some cases, the reduction means that a particular code rate cannot be achieved because there are not enough code words. For example, a rate 9/10 code (9 data bits converted into 10 code bits), that prevents tribit shifting as discussed above would not have enough code words to support each of the possible data words. In other cases, the reduction in code words requires that code words with undesirably long sequences of consecutive 0's must be used. Thus, a code is needed that reasonably protects against tribit shift errors while providing more code words than current techniques.
SUMMARY OF THE INVENTION
An encoder is provided that converts data words into code words. The code words, when concatenated together, are such that sub-strings of consecutive first symbols in the code words have no more symbols than a maximum number; sub-strings having the maximum number of consecutive first symbols and beginning at selected locations within the code words appear without restriction, and sub-strings having the maximum number of consecutive first symbols and beginning at locations other than the selected locations appear only where the substring is concatenated with an acceptable secondary sub-string.
A method is also provided for generating a set of code words for an encoder. The method includes eliminating code words that have strings of consecutive first symbols that are longer than a maximum length and retaining some code words that have a string of consecutive first symbols that is as long as the maximum length if the string begins at a selected location. The method further includes retaining some code words that have a string of consecutive first symbols that is as long as the maximum length and that begins at a location other than a selected location if the string is concatenated with an acceptable sub-string. If the string of consecutive symbols is not concatenated with an acceptable sub-string, the code word is eliminated.
REFERENCES:
patent: 5257272 (1993-10-01), Frederickson
patent: 5280489 (1994-01-01), Frederickson et al.
patent: 5933103 (1999-08-01), Kim
patent: 6175318 (2000-01-01), Kahhman et al.
patent: 6046691 (2000-04-01), Aziz et al.
patent: 6229459 (2001-05-01), Noda
“Analysis of Error Sequence for PRML and EPRML Signaling Performed Over Lorentzian Channel”, R. Karabed et al., Globecom 96, (IEEE Global Telecommunications Conference 96) pp. 368-373.
“Maximum Transition Run Codes for Data Storage Systems”, J. Moon et al., IEEE Trans. Mag., vol. 32, No. 5, pp. 3992-3994 (Sep. 1996).
“An 8/9 Rate Time-Varying Trellis Code for High Density Recording”, W. Bliss, IEEE Magnetics Conference, International (InterMag) 97.
“Experimental Performance Comparison of FTDS/DFE Detectors: 8/9 (0,k) vs. 4/5 MTR Codes”, Z. Keirn, IEEE Magnetics Conference, International (InterMag) 97.
“Distances Spectra for PRML Channels”, S. Altekar et al., IEEE Magnetics Conference, International (InterMag) 97.
Fredrickson Lisa
Sukhija Anuradha
Magee Theodore M.
Mai Lam T.
Seagate Technology LLC
Tokar Michael
Westman Champlin & Kelly P.A.
LandOfFree
Method and apparatus for generating code words with shifted... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for generating code words with shifted..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for generating code words with shifted... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2920044