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.