Enhanced decoding of interleaved error correcting codes

Claim 1

A method of enhancing the capability of a decoder to correct multiple burst errors in codewords comprising encoded symbols interleaved with an ECC code, comprising the steps of: encoding codewords, each n symbols in length, in successive rows to create a series of rectangular blocks, each having λ rows of codewords, n and λ being integers and having values which are relatively prime, and the corresponding symbols of adjacent codewords in the respective rows of each block being aligned columnwise; and interleaving the symbols of successive codewords by reading them in one continuous diagonal sequence one block at a time to form an array with a toroidal topology in which the symbol at the trailing end of each block is followed by the symbol at the beginning of the succeeding block, so that all burst errors will be continuous from codeword to codeword and block to block, irrespective of where they occur in the array; decoding all codewords, correcting all correctable errors in all correctable codewords, and flagging only those codewords in which the error correction capability of the code is exceeded; examining at lest one codeword adjacent in time to each flagged codeword to identify the locations in error therein that have been corrected and successfully decoded; separating the identified locations in error into sets according to a preselected protocol; tentatively declaring, as erasures, errors in the flagged codeword at specific locations which are diagonally adjacent in time to different respective sets of said locations in error; and repeating the decoding step in an attempt to now correct and decode the flagged codeword.

Claim 2

A method of enhancing the capability of a decoder to correct multiple burst errors in codewords comprising encoded symbols interleaved with an ECC code, comprising the steps of: encoding codewords, each n symbols in length, in successive rows to create a series of rectangular blocks, each having λ rows of codewords, n and λ being integers and having values which are relatively prime, and the corresponding symbols of adjacent codewords in the respective rows of each block being aligned columnwise; and interleaving the symbols of successive codewords by reading them in one continuous diagonal sequence one block at a time to form an array with a toroidal topology in which the symbol at the trailing end of each block is followed by the symbol at the beginning of the succeeding block, so that all burst errors will be continuous from codeword to codeword and block to block, irrespective of where they occur in the array; decoding all codewords, correcting all correctable errors in all correctable codewords, and flagging only those codewords in which the error correction capability of the code is exceeded; examining at lest one codeword adjacent in time to each flagged codeword to identify the locations in error therein that have been corrected and successfully decoded; separating the identified locations in error into sets according to a preselected protocol; tentatively declaring, as erasures, errors in the flagged codeword at specific locations which are diagonally adjacent in time to different respective sets of said locations in error; and repeating the decoding step in an attempt to now correct and decode the flagged codeword.

Claim 6

A method of enhancing the capability of a decoder to correct multiple burst errors in codewords comprising encoded symbols interleaved with an ECC code, comprising the steps of: decoding all codewords, correcting all correctable errors in all correctable codewords, and flagging only those codewords in which the error correction capability of the code is exceeded; examining at least one codeword adjacent to each flagged codeword to identify the locations in error therein that have been corrected and successfully decoded; separating the identified locations in error into sets according to a preselected protocol; tentatively declaring, as erasures, specific locations in the flagged codeword which are diagonally adjacent in time to different respective sets of corrected locations in error; and repeating the decoding step in an attempt to now correct and decode the flagged codeword.

Claim 7

A method of enhancing the capability of a decoder to correct multiple burst errors in codewords comprising encoded symbols interleaved with an ECC code, comprising the steps of: decoding all codewords, correcting all correctable errors in all correctable codewords, and flagging only those codewords in which the error correction capability of the code is exceeded; examining at least one codeword adjacent to each flagged codeword to identify the locations in error therein that have been corrected and successfully decoded; separating the identified locations in error into sets according to a preselected protocol; tentatively declaring, as erasures, specific locations in the flagged codeword which are diagonally adjacent in time to different respective sets of corrected locations in error; and repeating the decoding step in an attempt to now correct and decode the flagged codeword.

Claim 8

An apparatus for encoding and decoding digital data transmitted over a communications channel and capable of decoding and correcting a plurality of burst errors, comprising: encoder means for encoding a digital data input into a stream of symbols forming codewords, each n symbols in length, in successive rows to create a series of rectangular blocks, each having λ rows of codewords, the values of λ and n being relatively prime and the corresponding symbol positions of codewords in the respective rows of each block being aligned columnwise; interleaver means for resequencing the encoded codewords into an interleaved symbol stream in which successive codewords are read as one continuous sequence to form an array with a toroidal topology in which the symbol at the trailing end of each block is followed by the symbol at the beginning of the succeeding block; modulator means for converting the interleaved symbol stream into a code transmitted to the channel; demodulator means for processing the code and reproducing the stream of symbols, degraded by any noise on the channel; deinterleaver means for generating a resequenced interleaved symbol stream by performing an operation inverse to that of said interleaver means; and a decoder for generating an estimate of said digital data input by (i) decoding the resequenced interleaved symbol stream, (ii) flagging only those codewords which were not decodable, (iii) declaring, as erasures, locations in a flagged codeword that are diagonally adjacent in time to corrected locations in error, the corrected locations in error being separated into sets according to a preselected protocol and the erasures being declared adjacent to different respective sets of these corrected locations in error, and (iv) again decoding in an attempt to now correct and decode the flagged codeword.

Claim 9

An apparatus for encoding and decoding digital data transmitted over a communications channel and capable of decoding and correcting a plurality of burst errors, comprising: encoder means for encoding a digital data input into a stream of symbols forming codewords, each n symbols in length, in successive rows to create a series of rectangular blocks, each having λ rows of codewords, the values of λ and n being relatively prime and the corresponding symbol positions of codewords in the respective rows of each block being aligned columnwise; interleaver means for resequencing the encoded codewords into an interleaved symbol stream in which successive codewords are read as one continuous sequence to form an array with a toroidal topology in which the symbol at the trailing end of each block is followed by the symbol at the beginning of the succeeding block; modulator means for converting the interleaved symbol stream into a code transmitted to the channel; demodulator means for processing the code and reproducing the stream of symbols, degraded by any noise on the channel; deinterleaver means for generating a resequenced interleaved symbol stream by performing an operation inverse to that of said interleaver means; and a decoder for generating an estimate of said digital data input by (i) decoding the resequenced interleaved symbol stream, (ii) flagging only those codewords which were not decodable, (iii) declaring, as erasures, locations in a flagged codeword that are diagonally adjacent in time to corrected locations in error, the corrected locations in error being separated into sets according to a preselected protocol and the erasures being declared adjacent to different respective sets of these corrected locations in error, and (iv) again decoding in an attempt to now correct and decode the flagged codeword.