Since a storage medium is subject to various types of noise, distortion and interference, various errors can occur at the output of the storage medium. The massive amount of digital data stored in an optical disk storage increases the probability of the errors. To correct the errors, error control coding is used to transform an original information sequence into code words, which contain original data bytes and redundant bytes appended to the end. The redundant bytes of the code words written on the storage medium are used to recover the original data information which has been corrupted.
In optical disk applications, the code words are formed based on an International Standard Organization (ISO) Standard that requires Cyclic Redundancy Check (CRC) encoding and incorporates a Reed-Solomon (RS) code over some Galois fields.
The Galois field is a finite field, the elements of which may be represented as polynomials with a particular primitive element as variables. The RS code represents a block sequence of symbols over a Galois field GF(2.sup.m) of 2.sup.m binary symbols, where m is the number of bits per symbol. Constructing the Galois field GF(2.sup.m) requires a generator polynomial p(x) of degree m and a primitive element .beta., which is a root of p(x). The powers of .beta. generate all nonzero elements of GF(2.sup.m).
The RS (n,k) code is a cyclic symbol error-correcting code where k symbols of an original data are encoded. The result, which is an (n-k)-symbol redundancy block, is appended to the data.
For error correction circuitry capable of correcting a maximum of 8 errors for every 120-byte code word (up to 10 words) used in an optical disk storage, a shortened RS (120,104) code over the Galois field GF(2.sup.8) is required. In order to generate GF(2.sup.8), a generator polynomial p(x) of degree 8 (e.g. p(x)=1+x.sup.2 +x.sup.3 +x.sup.5 +x.sup.8) and a primitive element .beta..sup.j are required. The primitive element .beta..sup.j can be used to generate another field by the same polynomial. The j represents a number coprime to 2.sup.m -1 for GF(2.sup.m), i.e. a number which is not divisible by 2.sup.m -1 or any of its factors. For GF(2.sup.8), there are 128 different primitive elements .beta..sup.j, which can be used to generate various fields from each particular generator polynomial. This field consists of 256 vectors which represent every number between and including 0 to 255. The nonzero vectors are referenced using a specific element .alpha..sup.i, where i=0, 1, . . . , 254.
The cyclic redundancy check (CRC) is a cumulative parity check, which can be performed by a linear feedback shift register (LFSR) structure. In accordance with the ISO requirements, the LFSR should process each of the ten 104-byte words of the original data to generate in 104 steps four CRC data bytes appended as the last bytes to last four words.
To correct up to 8 errors per word for up to 10 words, an RS encoder uses a similar LFSR structure as in the CRC, which processes each of 104-byte words of the original data to form 16 redundant bytes in 104 steps. These redundant bytes are appended to each original word to make a 120-byte RS code word to be written into a codeword memory.
Reference is now made to FIG. 1 of the drawings showing interaction between RS and CRC encoders during encoding procedure. Words 0-9 of the original data stored in a codeword memory 22 are supplied to a CRC encoder 24, which processes the 104-byte words to generate four CRC bytes. The CRC bytes are sent back to the codeword memory 22 to replace the last byte in each of the last four words stored in the memory. The content of the codeword memory 22 is shown in FIG. 2, wherein the original data are represented as a 10 by 104 matrix. The 10 columns of the matrix correspond to the words 0 to 9 of the original data, and 104 rows of the matrix correspond to the bytes 0 to 103 of each word. The four CRC bytes generated by the CRC encoder 24 are represented in the matrix as C1, C2, C3 and C4 in bytes 103 of words 6, 7, 8 and 9.
After the CRC encoder 24 has saved the CRC bytes in the codeword memory 22, an RS encoder 26 reads the words 0-9 having the CRC bytes in the words 6-9 from the codeword memory 22 to generate 16 RS redundant bytes for each of the 10 words. The RS redundant bytes are sent back to the codeword memory 22 to be appended to each of the 10 words. In the memory matrix in FIG. 2, the RS redundant bytes are represented as 16 additional rows corresponding to bytes 104 to 119 of words 0 to 9.
Thus, the RS and CRC encoders sequentially process the original data during the encoding procedure. The sequential method is simple but takes a long time. To process 10 words, each of which includes 104 bytes, and to extract 4 CRC bytes per word, the CRC encoder requires 1080 total steps. The RS encoder processes the same number of 104-byte words, but outputs 16 RS bytes per word. Accordingly, the RS encoding requires 1200 steps. Thus, the sequential method of encoding requires 2280 steps. Reduction of the encoding time would allow the error correction circuit to increase the processing speed.
In view of the above, it would be desirable to provide a method of data encoding, wherein RS encoding and CRC encoding are provided in parallel to reduce the total time of encoding.