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, including erasure of written data. The massive amount of digital data stored in an optical disk storage increases the probability of the errors and erasures. To correct the errors and erasures, error control coding is used. Reference is now made to FIG. 1, wherein an error correction system comprises an encoder 22, which transforms an input information sequence entered on the optical disk storage into code words.
In optical disk applications the code words are encoded based on International Standard Organization (ISO) Standard that requires Cyclic Redundancy Check (CRC) encoding and incorporates a Reed-Solomon (RS) code over some Galois fields. 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. 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 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). Encoding and decoding circuitry is therefore required which has a capability of performing Galois field arithmetic.
The encoder 22 generates, in k steps, (n-k) redundancy bytes, which are appended to the original code data to make a n-byte code word. A writing unit 24 records the coded data on an optical disk 26.
A reading unit 28 unloads data from the optical disk 26 and transfers them to a decoding section 30. The decoding section 30 comprises a syndrome generator 32, which detects errors and generates syndrome bytes S(x) for each word received from the optical disk. The syndrome (n-k) bytes are supplied to an Euclidean operation circuit 34, which finds an error location polynomial .sigma.(x) and error value polynomial .eta.(x) using an extended Euclidean algorithm. The Euclidean operation circuit 34 is connected to an error locating circuit 36, which uses the Chien Search process to find actual error locations based on the error location polynomial .sigma.(x). The error locations together with the error value polynomial .sigma.(x) and error location polynomial .eta.(x) are used by an error value calculator 38 to determine error value at each error location found by the Chien Search process. An error correcting circuit 40 uses known error locations and values to correct the errors.
Inasmuch as in RS code decoding procedure codewords and the intermediate data bytes are regarded as polynomials with coefficients over some finite fields, polynomial arithmetic operations are usually performed during the decoding procedure. These operations fall into the following categories:
1) recursive division and multiplication used in the Extended Euclidean algorithm; PA1 2) polynomial expansion to find erasure polynomial based on the known erasure locations; PA1 3) modulo polynomial multiplication to calculate modified syndrome polynomial; and PA1 4) regular polynomial multiplication to obtain erasure/error location polynomial. PA1 storing polynomial data indicating occurrence of the errors and erasures in the read data, PA1 performing recursive division and multiplication of the polynomial data in a first mode of operation, PA1 performing polynomial expansion of the polynomial data in a second mode of operation, PA1 performing modulo polynomial multiplication of the polynomial data in a third mode of operation, PA1 performing regular polynomial multiplication of the polynomial data in a fourth mode of operation, and PA1 switching between the first, second, third and fourth modes of operation to generate signals indicating values and locations of said errors and erasures.
Detailed description of these functions is stated as follows.
Recursive multiplication and division
In Reed-solomon code decoding, Extended Euclidean algorithm is often used to calculate error location polynomial .sigma.(z) and error value polynomial .eta.(z). This algorithm is actually used to perform recursive division of two polynomials r.sub.0 (z) and r.sub.1 (z) to find the polynomial .eta.(z) (i.e. r.sub.i (z)), and to perform recursive multiplication and accumulation to the intermediate quotients to find the polynomial .sigma.(z) (i.e. yt(z)). The operation sequences are presented as the following equation sequences.
__________________________________________________________________________ Iteration Division Multiplication __________________________________________________________________________ 0 r.sub.0 (z)=p.sub.0 (z)*r.sub.1 (z)+r.sub.2 (z) y.sub.2 (z)=q.sub.0 (z)*y.sub.1 (z)+y.sub.0 (z), 1 r.sub.1 (z)=q.sub.1 (z)*r.sub.2 (z)+r.sub.3 (z) y.sub.3 (z)=q.sub.1 (z)*y.sub.2 (z)+y.sub.1 (z), . . . i-2 r.sub.i-2 (z)=q.sub.i-2 (z)*r.sub.i-1 (z)+r.sub.i (z), y.sub.i (z)=q.sub.i-2 (z)*y.sub.i-1 (z)+y.sub.i-2 (z), (1) __________________________________________________________________________
These iterations stop when the degree of the remainder deg[r.sub.i (z)] is less than some predetermined number u, where u=.left brkt-bot.(d-1+.epsilon.)/2.right brkt-bot., .epsilon. is the number of erasures and d is a minimum distance. Error value polynomial .eta.(z) is the remainder r.sub.i (z) and error location polynomial .sigma.(z) is y.sub.i (z).
2) Polynomial expansion
For a set of known erasure locations .alpha..sub.0, .alpha..sub.1, . . . , .alpha..sub.i, where i .ltoreq.d-2. The corresponding erasure polynomial .sigma..sub.z (z) becomes EQU .sigma..sub.s (z)=(z-.alpha..sub.1) . . . (z-.alpha..sub.i)=z.sup.i+1 +a.sub.i z.sup.i + . . . +a.sub.2 z.sup.2 +a.sub.1 z+a.sub.0( 2)
3) Regular polynomial multiplication For two polynomials p.sub.1 (z) and p.sub.2 (z) with degrees n and m respectively. The product of the multiplication is EQU p.sub.1 (z)*p.sub.2 (z)=b.sub.n+m z.sup.n+m +b.sub.n+m-1 z.sup.n+m-1 + . . . +b.sub.1 z+b.sub.0 ( 3)
4) Modulo polynomial multiplication
For two polynomials r.sub.1 (z) and r.sub.2 (z) with degrees n and m respectively. The result of the (modulo z.sup.k)--multiplication, where k .gtoreq.n+m, is ##EQU1##
The operation complexity shown in Equations (1) to (4) is proportional to the degree of the initial polynomials. For codes having high correction capability, the data generated during decoding process represent polynomials with high degree. Consequently, the decoding procedure becomes a time-consuming task for a conventional processor to handle.
To perform each of the above-described operations, a decoder equipped with separate modules for each of the operations is required. It results in logic redundancy.
Further, lengthy calculations to perform each of the above-described polynomial operations separately drastically degrade the overall performance of the error correction system.
In view of the above, it would be desirable to provide a single polynomial processing module with flexible control modes that can perform various polynomial operations.
USPTO Backgrounds
USPTO Backgrounds