Method for constructing RLL codes of arbitrary rate
View Patent ↗The claimed embodiments provide methods, apparatuses and systems directed to run-length limited (RLL) coding of data. In one implementation, concatenatable RLL codes with run lengths of zeroes not exceeding k are constructed for any rate N/(N+1) where N≦2 k−2 +k−1. As code rates increase, the value of k departs from the minimum possible value more slowly than that of many other codes. Further, occurrences of k-bit run lengths occur only at the juncture of two codewords. Due to this, the codes are mostly k−1. This quality makes the codes ideal for parity bit insertion applications such as LDPC channels. The method, in one implementation, places the bit addresses of violating sequences in a table at the beginning of the codeword, and the user data, occupying the locations where the table entries are placed, are moved into the locations of the violating sequences. This is done iteratively and in a way which provides for cases in which the violating sequence is inside the address table itself.
1. In a media device operable to encode and decode codewords of data, a method for encoding codewords of data to be written to a medium, the method comprising:
receiving a word comprising N bits of data;
pre-pending an additional bit to the word to form a codeword, wherein each bit has a corresponding bit address;
locating a violating sequence in the codeword, wherein locating the violating sequence comprises:
pointing an address table pointer to a bit address adjacent to the pre-pended additional bit;
scanning the codeword for the violating sequence, wherein the violating sequence comprises a contiguous sequence of bits that violate a run-length limited coding constraint k, wherein N≦2 k−2 +k−1; and
locating a starting bit address of the violating sequence;
inserting, responsive to locating a violating sequence, an indicator into the codeword, wherein inserting the indicator comprises:
replacing k bits of the violating sequence with k bits of the codeword starting from the bit address of address table pointer;
constructing the indicator to include the starting bit address of the violating sequence; and
inserting the indicator starting at the bit address of the address table pointer; and
advancing the address table pointer, by k, to point to a new bit address of the code word.
2. The method as recited in claim 1 wherein the violating sequence is a contiguous sequence of bits having predetermined values.
3. The method as recited in claim 2 wherein the violating sequence is a contiguous sequence of zeroes.
4. The method as recited in claim 1 wherein a value of the pre-pended bit is changed when the violating sequence is located.
5. The method as recited in claim 1 wherein the indicator comprises a guard bit, an address field and an end flag.
6. The method as recited in claim 5 wherein the address field is k−2 bits long.
7. The method as recited in claim 5 wherein the address field identifies a first bit address of the violating sequence.
8. The method as recited in claim 5 wherein the guard bit has a value of 1 and the end flag initially has a value of 0 and wherein the end flag is changed to a 1 if an additional violating sequence is detected.
9. The method as recited in claim 1 wherein if a bit address of a first bit of the violating sequence is equal to a corresponding address table pointer then the bits of the violating sequence are replaced with the indicator.
10. The method as recited in claim 1 wherein if
a) a bit address of a first bit of the violating sequence is not equal to a corresponding address table pointer; and
b) if the bit address is less than the corresponding address table pointer; and
c) if the bit address is greater than the corresponding address table pointer minus k then:
replacing bits of the violating sequence with bits starting from the address table pointer down to, but not including, the bit address of the first bit of the violating sequence wherein the replaced bits of the violating sequence are replaced starting at one bit address adjacent to the address table pointer+k.
11. The method as recited in claim 1 wherein bit addresses of the code word range from a most significant bit address of N−1 to a least significant bit address of 0, and wherein if N>2 k−2 then the bit addresses are offset to range from the most significant bit address of N−(k+1) to a bit address of 0 where the k−1 least significant bits have no bit address.
12. In a media device operable to encode and decode codewords of data, a method for decoding codewords of data to be written to a medium, the method comprising:
receiving a codeword comprising N bits of data, wherein N≦2 k−2 +k−1, where k is a run-length limited coding constraint;
identifying a last indicator sequence in the codeword wherein the indicator sequence comprises a bit address of a violating sequence;
responsive to identifying the last indicator sequence, setting an address table pointer to a first bit address of the indicator sequence;
extracting the bit address of the violating sequence from the indicator sequence;
wherein if: a) the extracted bit address is not equal to the address table pointer; and b) if the extracted bit address is less than the corresponding address table pointer; and c) if the bit address is greater than the corresponding address table pointer minus k, then: replacing bits of the indicator sequence with bits of the violator sequence from a right-most violating sequence up to an end of the indicator sequence;
wherein if the extracted bit address of the violating sequence equals the address table pointer, then replacing the indicator sequence with the violating sequence;
else,
replacing the indicator sequence with the first k bits of the code word starting at the extracted bit address;
inserting the violating sequence into the codeword at the extracted bit address.
13. The method as recited in claim 12 wherein the violating sequence is k zeroes.
14. The method as recited in claim 12 wherein the codeword further comprises a pre-pended bit and wherein a value of the pre-pended bit is utilized to determine if the codeword includes an indicator sequence and requires decoding.
15. The method as recited in claim 14 wherein determining if the word requires decoding comprises:
examining the pre-pended bit; and
decoding the codeword if the pre-pended bit equals 0.
16. The method as recited in claim 12 where the indicator sequence further comprises a guard bit and an end flag.
17. The method as recited in claim 16 wherein the indicator sequence is a lastly encoded indicator sequence which is located in the codeword by a value of an end flag in the lastly-encoded indicator sequence.
18. The method as recited in claim 17 wherein the value of the end flag in the lastly encoded indicator sequence is 1.
19. The method as recited in claim 12 wherein if N>2 k−2 then the extracted bit address is increased by N−2 k− .