Coded data generation or conversion – Digital code to digital code converters – To or from run length limited codes
Reexamination Certificate
1998-07-13
2001-02-27
Young, Brian (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
To or from run length limited codes
C341S058000, C341S061000
Reexamination Certificate
active
06195025
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to anomalous decoding of sequences of binary values such as may be found in magnetic storage recording channels or in optical communications subsystems where the errors, erasures, or faults involve binary subsequences exhibiting high-duty-cycle patterns or selected pattern repetitions. More particularly, the invention relates to methods and means for either preventing indefinite repetition of the patterns or excluding them.
DESCRIPTION OF RELATED ART
It is well known that a binary-valued sequence, such as 1000011011, may be adversely interpreted by decoding devices due to unintended patterns or attributes present in such sequences. For example, a sequence such as 1010101010 . . . exhibits a very high duty cycle. Electronically, a high duty cycle is synonymous with electrical or mechanical elements being repeatedly stressed. This frequently results in attendant thermal and noise increases in component environments resulting in higher error rates, failure rates, and shortened component lives.
The term “duty cycle” for purposes of this specification means the number of binary 1's occurring in a pattern or repetitive subsequence interval. In the 101010 example, the duty cycle is 50 percent since the “1” occurs in every two-bit interval. If the repetitive pattern was of the form of two binary 4-bit words such as 1001, 1000, the duty cycle would be ⅜=37.5 percent.
In magnetic recording channels and optical communications there arises the phenomenon of pulse smearing or broadening. For instance, two binary 4-bit words 0001, 0010 might, as a result of “smearing”, appear at the input of the decoder as 0001, 1010. In this case, the binary 1 in the 4
th
-bit position of the first word is electrically or optically “stretched” to appear as if it were two consecutive binary 1's. Such studies or smearing is especially egregious in pulse position modulation (PM) communications systems or the like. This devolves from the fact that PPM systems are notoriously bandwidth inefficient.
It is known from Adler et al., U.S. Pat. No. 4,413,251, “Method and Apparatus for Generating a Noiseless Sliding Block Code for a (1,7) Channel with Rate ⅔”, issued Nov. 1, 1983, that a finite state machine (FSM) can convert unconstrained binary-valued sequences into a constrained binary-valued sequence in an invertible manner. Furthermore, Adler teaches that a finite lookahead state-independent machine could perform the decoding. The lookahead capability permits a decoder to resolve n<m bits of a current RLL codeword into m bits of the unconstrained sequence by taking into account a predetermined number of subsequent RLL codewords. Nevertheless, this decoder lookahead feature increases the adverse effect of error or erasure in the RLL codeword.
According to Adler et al., for a given code rate R=m
of mapping m bits of unconstrained binary sequence into n bits of constrained sequence, the requirement is partially satisfied by deriving an FSM encoder with 2
m
branches per state in which the (d, k) constraints are manifested by splitting and merging some of the FSM states in order to obtain a new FSM. The (d, k) constraint means that at least d “0's” and no more than k “0's” are to be inserted between any pair of consecutive binary “1's”. For d<k, d determines the frequency of transitions and whence the intersymbol interference (ISI). In the case of k, it is used for clock resynchronization.
SUMMARY OF THE INVENTION
It is accordingly an object of this invention to devise an invertible method and apparatus for converting unconstrained sequences of binary values into a fixed-rate RLL-coded sequence either inhibiting indefinite repetition of or excluding RLL subsequences exhibiting high-duty-cycle patterns.
It is yet another object of this invention that such invertible method and apparatus generate RLL-coded sequences with good bandwidth efficiency, minimal ISI, low complexity, and exhibit sufficient timing information for clock recovery.
The foregoing objects are satisfied by an FSM for converting an unconstrained sequence of binary values into a constrained sequence selected from one of a set of fixed-rate ⅔ (d, k) RLL codes consisting of (1,9) and (1,13) RLL codes in which predetermined RLL-coded sequences are inhibited from indefinite recurrence, as in the case of (1,9) and (1,10) RLL codes, or excluded from appearing, as in the case of the (1,13) RLL code. Furthermore, a lookahead nonstate-dependent decoder provides for the necessary invertability when the RLL-coded sequences are read from a storage subsystem or an optical communications path or the like.
More particularly, the foregoing objects are believed satisfied by a processor implementable method or a hard-wired combinatorial logic equivalent for invertibly mapping binary sequences into rate ⅔ (1, k) run-length-limited coded (RLL) sequences with maximum transition density constraints. The method involves two steps, namely, defining and storing a finite state machine operative as an encoder and then executing the mapping over the binary sequences.
The first step involves defining and storing in a processor a state transition table of ordered pairs including a next state (n
1
n
2
n
3
) and a current RLL-coded tri-bit symbol (c
1
c
2
c
3
). Each ordered pair in said table is indexed in a first tabular dimension according to its present state, and in a second tabular dimension according to a vector (b
1
b
2
b
3
b
4
) of a present (b
1
b
2
) and a predetermined number of lookahead (b
3
b
4
) bit-pairs from the binary sequence. Each present bit-pair is a cognizable binary value (00,01,10,11). Also, each of the predetermined numbers of bit-pairs is selected from a set consisting of a cognizable binary value and a “don't care” (xx) value. Significantly, the state-to-state transitions are constrained such that any counterpart long-run sequence of RLL-coded tri-bits manifests a duty cycle less than 50 percent. The second step involves causing the processor to access the table responsive to a succession of vectors of bit-pairs and extending therefrom a succession of RLL-coded tri-bits. The logical relations defining the binary-to-RLL codeword mappings and their inverses are elaborated in the figures and in the description of the preferred embodiment.
In order to use a (1, k) rate ⅔ RLL encoding to reduce the duty cycle of a stream of binary values, it was necessary to appreciate the effect it would have when selected unconstrained binary-coded patterns were applied to a standard (1,7) or (1,9) rate ⅔ RLL encoder. Indeed, these selected patterns produced constrained binary-coded patterns with very high duty cycles. These are exemplified in Table 1 below:
TABLE 1
Unconstrained
Binary-coded
Duty
Patterns
Cycle
(1,7) Rate 2/3 RLL Code
00 11 00
010 101 010
4/9
00 11 01
010 101 001
419
(1,7), (1,9) Rate 2/3 RLL Codes
10 11 00
100 101 010
4/9
10 11 01
100 101 001
419
(1,7), (1,9) Rate 2/3 RLL Codes
00 11 10 11
010 101 000 101
5/12
10 11 10 11
100 101 000 101
5/12
However, it was further observed that (1,9) and (1,13) rate ⅔ RLL encoders of the type disclosed in the Adler '413 patent could be heuristically modified to either (a) inhibit indefinite high-duty-cycle RLL encoding repetitions of these predetermined unconstrained patterns, or (b) effectively inhibit them such as is shown in Table 2 below:
TABLE 2
Unconstrained
Binary-coded
Patterns
(1,9) Rate 2/3 RLL with
Modified Encoder/Decoder
00 11 00
010 000 000
00 11 01
001 000 000
(1,13) Rate 2/3 RLL with
Modified Encoder/Decoder
10 11 00
100 000 000
10 11 01
101 000 000
00 11 10 11
010 000 000 000
10 11 10 11
100 000 000 000
REFERENCES:
patent: 4413251 (1983-11-01), Adler et al.
patent: 4675650 (1987-06-01), Coppersmith et al.
patent: 5175545 (1992-12-01), Uchiyama et al.
patent: 5604497 (1997-02-01), Sonntag
patent: 5731768 (1998-03-01), Tsang
patent: 5742243 (1998-04-01), Moriyama et al.
patent: 5774078 (1998-06-01), Tanaka et al.
patent: 5859601 (1999-01-01),
Hassner Martin Aureliano
Heise Nyles
Hirt Walter
Trager Barry Marshall
Brodie R. Bruce
International Business Machines - Corporation
Kost Jason L. W.
McSwain Marc D.
Young Brian
LandOfFree
Method and means for invertibly mapping binary sequences... 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 means for invertibly mapping binary sequences..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and means for invertibly mapping binary sequences... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2591911