Technique to construct 32/33 and other RLL codes

Details Technique to construct 32/33 and other RLL codes Technique to construct 32/33 and other RLL codes

2000-06-30

2002-09-24

Tokar, Michael (Department: 2819)

Coded data generation or conversion

Digital code to digital code converters

To or from run length limited codes

C341S081000

Reexamination Certificate

active

06456208

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of Invention
This invention relates to encoding a digital word and more specifically to a run length limited encoding of a digital word.
2. Description of Related Art
In current digital data communication and digital data storage systems the processes of encoding and decoding are frequently utilized. During the encoding process the input stream of 0's and 1's is convert into another stream of 0's and 1's. The encoded stream usually contains more bits than the original uncoded stream. For example, encoding process could have data divided into words of 32 bits which are then converted into coded words, each 33 bits long. Such an encoding process is referred to as a rate of 32/33.
In U.S. Pat. No. 5,781,130 (McLaughlin et al.)( a system for encoding a digital word with an M-ary(d,k) code is disclosed. The multilevel coded data for M>2 is a result of an M-ary encoder that produces a run length limited code for multilevel data storage and/or data communications. In U.S. Pat. No. 5,748,119 (Ko) channel encoding and decoding methods are described which use an EFM code with a reduced number of merging bits. An m-bit input word is encoded to an (n−d+1) bit channel word by an encoding table. One or more merge bits are added encoded channel word to form a n-bit channel word. In U.S. Pat. No. 5,604,497 (Sonntag) a method and apparatus is disclosed for increasing the density of run length limited block codes without increasing error propagation. This is accomplished by inserting “M” uncoded bytes between each coded byte which increases the coding density.
The goal of encoding is to produce a stream of bits better suited for digital transmission or digital recording. One common objective is to guarantee that the encoded stream can not have more than a predetermined number “n” of consecutive zeros. This coding requirement is referred to as (0,n) Run Length Limited (RLL) constraint. During the digital transmission or digital recording, logical 1's are often modulated as a pulse and logical 0's are modulated as no pulse. The long runs of consecutive zeros result in long periods with no pulses which make it difficult to perform timing and gain recovery of the transmitted or stored signal. There is another important type of constraint which is commonly referred to as (0,G/I) constraint. Here the encoded stream can not have more than “G” consecutive zeros and after the encoded sequence of bits is divided into the odd-number and even-numbered sub sequences then neither of these sub sequences can have more than “I” consecutive zeros. The need for utilizing the (0,G/I) constraint streams from the use of Viterbi detection. Therefore, it is desirable to design an encoder which has a high rate, e.g. 32/33 or 64/65, has low implementation complexity and which satisifies a (0,G/I) RLL constraints with small values of G and I.
SUMMARY OF THE INVENTION
In the present invention a method for encoding an input digital word is shown that results in an output digital word that is one bit longer than the input digital word before parity bit is added. The output digital word satisifies a run length limited (RLL) (0,11/11) constraint and a Hamming weight of nine. Having a Hamming weight of “9” means that the number of logical ones in a word is at least nine.
As an example, a thirty two bit word can be encoded into a thirty three bit word plus a parity bit. The thirty two bit input word can be defined as IN={in(
1
), in(
2
), . . . in(
32
)} and the thirty three bit output word can be defined as OUT={out(
1
), out(
2
), . . . out(
33
)}. If the input word, IN, satisfies the coding constraints of (0,11/11) and a Hamming weight of at least nine, the input word split in half can be directly transferred to the output word as OUT={IN(LH), out(
17
), IN(RH)}, where IN(LH)={in(
1
), in (
2
), . . . in(
16
)} is the left half of the input code word, out(
17
) is the seventeenth bit position of the output code word, and IN(RH)={in(
16
), in (
17
), . . . in(
32
)} is the right half of the input code word. For convenience of demonstration and consistency with programs such as MATLAB the notation in(
16
:
32
) will be used instead of {in(
16
), in(
17
), . . . in(
32
)}. The left half of the input word maps directly into the same numbered bit positions in the left half of the output code word, and the right half of input word maps into a numbered bit position one bit higher in order to accommodate out(
17
) which is set to a logical one to indicate that there was no violations of the coding constraints in the input word.
In order to analyze the thirty two bit input word and insure that the even and odd interleaves satisfy the coding constraints, the input word needs to be further subdivided into IN={intLO, intLE, intRO, intRE} where intLO={in(
1
), in(
3
), in(
5
), . . . in(
15
)}, intLE={in(
2
), in(
4
), in(
6
), . . . in(
16
)}, intRO={in(
17
), in(
19
), in(
21
), . . . in(
31
)}, and intRE={in(
18
), in(
20
), in(
22
), . . . in(
32
)}. Each of these interleaves is eight bits long. A table of “bad” eight bit words, such as Table A in
FIG. 2
, is established to compare against the eight bit interleaves. The eight bit words in Table A are sometimes called “violations”, and Table A was established to facilitate analysis, minimize global constraints, minimize interleave constraints and eliminate low Hamming weights. Table A is used as a pointer to a four bit replacement, shown in Table B in
FIG. 2
, for the interleave that is in violation of the coding constraints.
When either right interleave, intRO and intRE, is found to be identical to one of the eight bit words in Table A, the corresponding four bit word in Table B is selected, reversed and substituted for the interleave in violation. For instance, if the violation is 10000011, the last one in Table B, the replacement code is 1101 which is the reverse of the last code in Table B. If the violation is in intLO or intLE, then intLO or intLE are reversed, compared to Table A to select the replacement four bit code. For example, if intLO=11000001, the reverse is 10000011 which selects 1011 from Table B.
The coded output word from the encoder can be represented as OUT={out(
1
), out(
2
), out(
3
), . . . out(
32
), out(
33
), out(
34
)}, where out(
34
) is the added parity bit after coding is finisher. Once a violation is detected the middle bit position in the coded output word is set to out(
17
)=0 which becomes the overall violation indicator. If the left half of the input word IN has a violation, out(
16
)=1, and for a right half violation, out(
18
)=1. If there is an odd interleave violation, out(
14
)=1, for the left half of the input word, and out(
20
)=1 for a violation for the right half of the input word. When there is an even interleave that is in violation, out(
12
)=1 for a violation in the left half and out(
22
)=1 for a violation in the right half. Each of the flag bits out(
12
), out(
14
), out(
16
), out(
18
), and out(
20
) are a logical “0” if there is not a violation. If only on interleave in the left half is in violation, the selected four bit code word from Table B is inserted into outLE(
2
,
4
,
6
,
8
) and the valid interleave, either intLE or intLO, is copied from the input word to OUT{LHO}=out(
1
), out(
3
), . . . out(
15
), where OUT{LHO} is the odd interleave in the left half of the output word. When the left half violation flags are both set to out(
14
)=1 and out(
12
)=1, both interleaves are replaced by a four bit violation code from Table B in the first four positions in both interleaves, leaving out(
9
), out(
11
), out(
13
) and out(
15
) unused and each filled with a logical one. When there is no violation, out(
17
)=1, out(
18
)=in(
17
), but when a vi

Affiliated with

Also associated with

Rating

Technique to construct 32/33 and other RLL codes does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Technique to construct 32/33 and other RLL codes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Technique to construct 32/33 and other RLL codes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2840511