System and method for producing data and ECC code words using a high rate restricted-symbol code

Abstract

An encoding system manipulates L m-bit data symbols or sequences in accordance with a “restricted-symbol” code to produce code words that include error correction code (ECC) redundancy information and also meet modulation requirements, such as run length. The system combines the data and associated redundancy information of a code word D of the underlying code and one or more predetermined symbols or sequences that are appended to the data code word with the corresponding symbols or bit sequences of a selected code word F, to produce a transmission code word C that consists of symbols or sequences that meet the modulation requirements. Thereafter, the system corrects any errors in the retrieved or received code word C using the included redundancy information and the L m-bit data symbols or sequences are then recovered by removing therefrom the contributions of the code word F. The system may instead use the restricted-symbol code strictly as a data code, by combining the respective m-bit data symbols or sequences and one or more predetermined symbols with one or more selected m-bit symbols or sequences, to produce L+1 m-bit symbols or sequences that meet the modulation requirements. The predetermined symbols or sequences are appended to the data to aid in decoding, with the corresponding symbols in the encoded code word or data symbols or sequences indicating to a decoder which selected code word, symbols or sequences have been combined with the data.

1. A method of encoding data including the steps of:
 A. manipulating the data to include one or more additional predetermined m-tuples; 
 B. determining a set of one or more prohibited m-tuples that combine with respective m-tuples of the data and the predetermined m-tuples to produce m-tuples that do not meet modulation requirements; and 
 C. selecting one or more m-tuples that are not prohibited m-tuples and combining the selected one or more m-tuples with the data and the predetermined m-tuples to produce a sequence of m-tuples that meet the modulation requirements. 
 
     
     
       2. The method of  claim 1  wherein the step of selecting includes selecting m-tuples that combine with one or more fixed sequences of m-tuples to produce selected m-tuples that combine with the data and predetermined m-tuples. 
     
     
       3. The method of  claim 2  wherein
 the step of manipulating the data includes manipulating the data in accordance with a shortened distance d (n,k) Reed Solomon code to produce a data code word that includes n-k=r m-bit redundancy symbols and appending to the data code word the one or more predetermined m-tuples, 
 the step of determining includes
 determining one or more fixed-symbol code words F i  with selected non-zero symbols, and 
 
 the step of selecting includes selecting for each fixed-symbol code word a corresponding m-tuple α pi  such that the fixed symbols are multiplied by the corresponding α pi , and the results are combined with the data code word and the appended predetermined m-tuples to produce a corresponding transmission code word in which the respective symbols meet the modulation requirements. 
 
     
     
       4. The method of  claim 3  wherein
 the determining step further includes determining the number of fixed-symbol code words based on the code length and the modulation requirements, and 
 the manipulation step further includes appending to the data code word a number of predetermined m-tuples that corresponds to the number of fixed-symbol code words. 
 
     
     
       5. The method of  claim 4  wherein the predetermined m-tuples are all set to the value α 0  and the corresponding symbols in the transmission code word have values that correspond to the selected α pi . 
     
     
       6. The method of  claim 4  wherein the step of determining includes determining fixed-symbol code words in which the fixed symbols are combinations of corresponding rows in m×m sub-matrices of the k×n code generator matrix G. 
     
     
       7. The method of  claim 6  wherein the step of determining further includes for a non-systematic code manipulating the code generator matrix G by permuting rows with a row permutation matrix P and permuting columns with a column permutation matrix Q to produce a generator matrix G* for an associated systematic code as PGQ and determining the fixed symbols of the fixed-symbol code words as combinations of corresponding rows in m×m sub-matrices of the matrix G*Q −1 . 
     
     
       8. A method of encoding data symbols including the steps of
 A. manipulating the data symbols in accordance with a shortened distance d (n,k) Reed Solomon code to produce r redundancy symbols and including the data symbols, the redundancy symbols and one or more predetermined appended symbols in a data code word D; 
 B. selecting one or more symbols α pi  to combine with one or more fixed-symbol code words F i  to produce a code word F=α pm F m +α pm-1 F m-1 + . . . +α p0 F 0  that when combined with the data code word produces a transmission code word that includes respective symbols that meet modulation requirements; and 
 C. combining the data code word D and the selected code word F to produce a transmission code word C with respective symbols that meet the modulation requirements. 
 
     
     
       9. The method of  claim 8  wherein the step of selecting includes
 determining a number of fixed-symbol code words required based on the code length and the number of symbols prohibited by the modulation requirements, 
 for all but one of the respective fixed-symbol code words setting to α 0  L information symbols that combine with L corresponding symbols of the data and setting the remaining information symbols that correspond to the data to all zeros and for the one code word setting to α 0  L-r information symbols that combine with L-r corresponding symbols of the data and a first redundancy symbol, and setting the remaining information symbols that correspond to the data to all zeros, and 
 selecting for each fixed-symbol code word F i  a symbol α pi  such that the non-zero symbols of the respective code words combine with the corresponding symbols of the data code word to produce corresponding symbols of the transmission code word. 
 
     
     
       10. A method of encoding data symbols including the steps of
 A. appending a predetermined m-tuple to L m-tuples of data; 
 B. determining a set of one or more prohibited m-tuples that combine with respective m-tuples of the data and the predetermined m-tuple to produce m-tuples that do not meet modulation requirements; and 
 C. selecting one or more m-tuples that are not prohibited m-tuples and combining the selected one or more m-tuples with the L data m-tuples and the predetermined m-tuple to produce L+1 m-tuples that meet the modulation requirements. 
 
     
     
       11. The method of  claim 10  wherein the step of selecting includes selecting a single m-tuple that combines with respective data m-tuples and the predetermined m-tuple. 
     
     
       12. The method of  claim 10  wherein the step of selecting includes selecting an m-tuple that combines with a sequence of L+1 fixed m-tuples to produce L+1 selected m-tuples that combine with the data and predetermined m-tuple.