Patent ID: 6275965
Filing Date: 2001-08-14
Classification: G11B,H03M

Abstract:
A method for detecting and correcting multibyte errors in long byte strings either derived from a communications system or recorded on a moving storage medium of a storage device in blocks, each block comprising a plurality of codewords and a plurality of block-level check bytes derived from the codewords, each codeword including data bytes and codeword check bytes mapped from a plurality of extrinsic data byte vectors according to a linear error correction code, comprising the steps of:(a) generating and either transmitting on the system or recording on the storage medium at least one block formed from N codewords by(1) creating a set of N data byte vectors m' as an interleave of elements of N extrinsically supplied data byte vectors m by matrix multiplication using a nonsingular invertible integration matrix with nonzero minors with order up to B;(2) mapping said set of N data byte vectors m' into a counterpart set of N codewords c' including 2t.sub.1 check bytes per codeword and B*(2t2) block-level check bytes;(3) creating a set of N modified codewords c from said set of N codewords c' by matrix multiplication of the N codewords c' by the inverse of the integration matrix; and(b) accessing each block either from the system or from the storage medium and processing the accessed block to detect and correct incipient bytes in error including the substeps of:(1) deriving syndromes from the check bytes therein, and identifying any nonzero syndromes; and(2) processing any identified nonzero syndromes over the codewords to correct any bytes in error using the 2t.sub.1 check bytes per codeword, and processing any block-level nonzero syndromes either to locate and correct (t.sub.1 +t2) bytes in error in up to B bursty single codewords exceeding the correction capability of the respective codeword but within the capability of the block, or to indicate that the bytes in error exceed the correction capability of both the codeword and block levels.