US 5,412,667 A · Decoder for cross interleaved error correcting encoded data

Abstract

An improved method for processing a sector of data read from a CD-ROM which has been encoded using a cross-interleaved Reed Solomon (CIRS) code is time linear in the number of errors in the sector. The improved method iteratively processes the data values from the sector, which appear in each of the sets of cross-interleaved sequences, through an error detection/correction algorithm. In the first pass, a syndrome is generated for each sequence in each set. If the syndrome indicates that the sequence either contains no errors or an undetectable number of errors, the sequence is marked as being error-free. If a sequence contains a correctable error, the error is corrected and the sequence is marked as being error-free. If the syndrome indicates that the sequence contains a number of errors which may be detected but not corrected the sequence is marked as containing errors. After the first pass the improved method only calculates an error syndrome for the sequences which are marked as containing errors. The sequences in this subset are those which are determined by the method to possibly contain an error. If an error is corrected in a sequence from one of the sets during any of the passes, the sequence from the cross-interleaved set which includes the error-corrected value is marked as containing errors to ensure that its syndrome is recalculated during the next pass.

Claims7

Dependent claims

the method comprising the steps of:
a) processing each sequence in the first set of sequences to correct any errors in members of a sequence which can be corrected by decoding the error correction encoded data;
and
b) only for each member of a sequence of the first set that has been corrected:
determining which sequence in the second set of sequences includes the member containing the corrected error;
and
marking the determined sequence in the second set for evaluation during subsequent error correction processing of the second set.

4 more elements

A method for efficiently decoding data which has been encoded in a first set of sequences and a second set of sequences according to an error correction encoding technique, each of the sequences in said first set and said second set having common members with sequences in said second set and said first set, respectively, wherein the error correction encoding technique applied to each of the sequences is able to correct errors in N-bits or less in the sequence and to detect but not correct errors in N+1 to M bits, and is not able to detect errors in more than M-bits in the sequence, where N and M are integers and M is greater than N, the method comprising the steps of:

a) processing each sequence in the first set of sequences to correct any errors in members of a sequence which can be corrected by decoding the error correction encoded data including
generating a respective syndrome value for each sequence in the first set of sequences, the syndrome having a value of zero for sequences which have no errors and for at least one sequence which has errors in more than M bits and having a non-zero value for sequences which have errors in 1 to M bits;
marking all sequences having zero-valued syndrome values to be skipped during subsequent error correction processing of the sequences of the first set;
using said respective syndrome values to correct errors in sequences having errors in between 1 and N bits and marking the sequences containing the corrected errors to be skipped during subsequent error correction processing of the sequences of the first set;
and
using said respective syndrome values to mark sequences containing errors in between N+1 and M bits for evaluation during the subsequent error correction processing of the sequences of the first set;
and
b) for each member of a sequence of the first set that has been corrected:
determining which sequence in the second set of sequences includes the member containing the corrected error;
marking the determined sequence in the second set for evaluation during subsequent error correction processing of the second set.

7 more elements

An apparatus for efficiently decoding data which has been encoded in a first set of sequences and a second set of sequences according to an error correction encoding technique, each of the sequences in said first set and said second set having common members with sequences in said second set and said first set, respectively, wherein the error correction means is able to correct errors in N-bits or less in the sequence and to detect but not correct errors in N+1 to M bits, and is not able to detect errors in more than M-bits in the sequence, where N and M are integers and M is greater than N, the apparatus comprising:

error correction means for processing one of the sequences in the first set of sequences to correct an error in one of the members of the sequence according to the error correction encoding technique including:
means for generating a syndrome value for each sequence in the first set of sequences, the syndrome having a value of zero for sequences which have no errors and for at least one sequence which has errors in more than M bits and having a non-zero value for sequences which have errors in 1 to M bits;
means for marking all sequences having zero-valued syndromes to be skipped during subsequent error correction processing of the sequences of the first set;
means, responsive to the generated syndrome values, for correcting errors in sequences having errors in between 1 and N bits and for marking the sequences containing the corrected errors to be skipped during subsequent error correction processing of the sequences of the first set;
and
means, responsive to the generated syndrome values, for marking sequences containing errors in between N+1 and M bits for evaluation during the subsequent error correction processing of the sequences of the first set;
means for determining which sequence in the second set of sequences includes the one member containing the corrected error;
and
means for marking the determined sequence in the second set for evaluation during subsequent error correction processing of the second set.

6 more elements

Dependencies are inferred from the claim text.

Decoder for cross interleaved error correcting encoded data

Life of this patent

Decoder for cross interleaved error correcting encoded data

Life of this patent

Abstract

Claims7