Latency reduced error correction scheme with error indication function for burst error correction codes
The present discloses provides a decoding method, decoding apparatus and decoder for correcting burst errors. In particular, the decoding method for correcting burst errors comprises: computing an initial syndrome of a received data frame, wherein the data frame is encoded according to cyclic codes for correcting burst errors; determining error correctability of burst error contained in the data frame based on the computed initial syndrome; and processing the burst error in the data frame and outputting the processed data frame based on the determined error correctability. With the decoding method, decoding apparatus, and decoder of the present invention, error correctability of burst errors contained in a data frame can be determined before the data is send out, while having smaller decoding latency through determining the error correctability and error pattern of the burst errors contained in the data frame using initial syndrome of the data frame.
1. A decoding method for correcting burst errors comprising:
computing an initial syndrome of a received data frame, wherein the data frame is encoded according to cyclic codes for correcting burst errors;
determining error correctability of a burst error contained in the data frame based on the computed initial syndrome;
processing the burst error in the data frame and outputting the processed data frame based on the determined error correctability;
computing a first syndrome by dividing the computed initial syndrome by an error pattern polynomial and determining a remaining polynomial associated with the first syndrome; and
computing a second syndrome by dividing the computed initial syndrome by an error location polynomial, and determining a remaining polynomial associated with the second syndrome,
wherein determining the error correctability of the burst error contained in the data frame comprises:
computing the first syndrome with the error pattern polynomial based on the computed initial syndrome;
computing the second syndrome with the error location polynomial, based on the computed initial syndrome, wherein the error pattern polynomial and the error location polynomial are associated with a generation polynomial of the cyclic codes; and determining the error correctability of the burst error contained in the data frame with a predetermined rule based on the computed first and second syndromes, and
wherein the cyclic codes are shorten cyclic codes, and the determined error correctability determined with the predetermined rule is defined as a first error correctability, and determining the error correctability based on the computed initial syndrome further comprises:
judging whether the burst error occurs at a boundary of a shorten frame of the shorten cyclic codes based on a location of the burst error in the data frame;
in response to judging that the burst error occurs at the boundary of the shorten frame of the shorten cyclic codes, determining a second error correctability; and
determining the error correctability of the burst error contained in the data frame based on the determined first and second error correctability.
2. The decoding method according to claim 1 , wherein dividing the computed initial syndrome by the error pattern polynomial comprises:
performing a shift operation on terms in the initial syndrome with orders higher than the highest order in the error pattern polynomial; and
performing a subtract operation on results of the shift operation and terms in the initial syndrome with orders not higher than the highest order of the error pattern polynomial.
3. The decoding method according to claim 1 , wherein dividing the computed initial syndrome by the error location polynomial comprises:
performing a shift operation on terms in the initial syndrome with orders higher than the highest order in the error location polynomial; and
performing a subtract operation on results of the shift operation and items in the initial syndrome with orders not higher than the highest order of the error location polynomial.
4. The decoding method according to claim 1 , further comprising:
determining an error pattern of the burst error contained in the data frame based on the computed initial syndrome, and wherein processing the burst error in the data frame comprises processing the burst error in the data frame based on the determined error correctability and the error pattern.
5. A decoder for correcting burst errors comprising:
a data buffer configured for storing a received data frame, wherein the data frame is encoded according to cyclic codes for correcting burst errors;
an initial syndrome computing circuit configured for reading out the data frame from the data buffer and computing an initial syndrome of the data frame;
an error correctability determining circuit, comprising a plurality of multiplexers and an XOR gate, and configured for determining error correctability of the burst error contained in the data frame based on the computed initial syndrome;
an error processing circuit configured for processing the burst error in the data frame and outputting the processed data frame based on the determined error correctability;
a first syndrome computing circuit which computes a first syndrome by dividing the computed initial syndrome by an error pattern polynomial, and determining the remaining polynomial as the first syndrome; and
a second syndrome computing circuit which computes a second syndrome by dividing the computed initial syndrome by an error location polynomial, and determining the remaining polynomial as the second syndrome,
wherein the cyclic codes are Fire Codes with a generation polynomial g(x)=(x 2L−1 +1) p(x), wherein p(x) is a primitive polynomial and Galois field arithmetic is performed in GF(2 m ), wherein m is an order of p(x), and wherein L is a positive integer less than or equal to m, and wherein 2L−1 is not divisible by a period of p(x); and wherein (x 2L−1 +1) is an error pattern polynomial, and p(x) is an error location polynomial.
6. The decoder according to claim 5 , wherein the error correctability determining circuit comprises:
the first syndrome computing circuit-which comprises a multiplexer and an XOR gate, and configured for computing the first syndrome with the error pattern polynomial based on the initial syndrome computed by the initial syndrome computing circuit;
the second syndrome computing circuit which comprises a multiplexer and an XOR gate, and configured for computing the second syndrome with the error location polynomial based on the initial syndrome computed by the initial syndrome computing circuit; and
a zero detect circuit, configured for determining the error correctability of the burst error contained in the data frame with a predetermined rule based on the first and second syndromes computed by the first and second syndrome computing circuits respectively.
7. The decoder according to claim 6 , wherein the first syndrome computing circuit is further configured for dividing the initial syndrome computed by the initial syndrome computing circuit by the error pattern polynomial using the multiplexer and XOR gate of the first syndrome computing circuit, and determining the remaining polynomial as the first syndrome.
8. The decoder according to claim 7 , wherein dividing the computed initial syndrome by the error pattern polynomial comprises:
performing a shift operation on terms in the initial syndrome computed by the initial syndrome computing circuit with orders higher than a highest order in the error pattern polynomial using the multiplexer of the first syndrome computing circuit; and
performing a subtract operation on results of the shift operation and terms in the initial syndrome with orders not higher than the highest order of the error pattern polynomial by using the XOR gate of the first syndrome computing circuit.