Abstract:
Improved design, computation and implementation of pairs of error detection check bytes, where such bytes are appended to the end of a variable length record for data integrity check of the entire record after ECC correction, is provided. The error detection check bytes are each computed using different powers of the same companion T matrix of a degree-eight primitive polynomial used for computing associated ECC check bytes. Use of the same T matrix provides the computational convenience of a reasonable size Galois field of GF(2 8 ), while providing long cycle length through a recurring offset within the data sequences corresponding to two members of each pair.

Description:
CROSS-REFERENCE TO RELATED APPLICATION 
     The present invention is related to the invention described in the U.S. patent application entitled, &#34;Method and Apparatus for Correcting Multibyte Errors Having Improved Two-Level Code Structure&#34;, Ser. No. 781,499, filed Sept. 27, 1985 by the inventor hereof, and is incorporated by reference as if fully set forth herein. 
     BACKGROUND OF THE INVENTION 
     The cyclic redundancy check (CRC) is extremely efficient and well suited for error detection in transmission, retrieval or storage of variable length records of binary data. CRC is capable of detecting nearly all patterns of error with almost negligent amount of redundancy. 
     CRC is also very well known. See, for example, &#34;Cyclic Codes for Error Detection&#34;, W. W. Peterson and D. T. Brown, Proceedings of the IRE, pages 228 to 235, January, 1961, and &#34;A Multi-channel CRC Register&#34;, Arvind M. Patel, Spring Joint Computer Conference, 1971. 
     A linear feedback register is essentially the only hardware needed for encoding and decoding variable length binary data for error detection by means of a CRC byte. The CRC byte is generated using a GF(2) polynomial divider circuit. In such a circuit, the binary information is serially shifted into a feedback shift register as the information is transmitted. The CRC byte is transmitted at the end of the binary data and received in sequence at the receiver. The generated CRC byte is then compared with the received CRC byte for detection of any errors in the received message which is processed in the same manner by a feedback shift register. The number of digits in the CRC byte determines the checking capability of the code and, in general, equals the number of stages of the encoding and decoding shift register. 
     SUMMARY OF THE INVENTION 
     This invention relates to improved design, computation and implementation of error detection check bytes, in particular CRC bytes, appended to the end of variable length records of binary data. These CRC bytes according to the present invention are created in pairs and each computed using different powers of a T matrix, the companion matrix of an irreducible polynomial, G(x), which is the same as that used for computing other associated ECC check bytes for the record. In many practical applications G(x) is a degree-eight primitive polynomial. 
     Use of the same T matrix provides computational convenience not found in conventional CRC implementations which typically employ a high degree (e.g. degree 16) polynomial divider to obtain long cycle length. The longer the cycle length, the less chance two errors in the same record will cancel; therefore, cycle length must be longer than the record. The present invention obtains long cycle lengths while operating in a reasonable size Galois field, such as GF(2 8 ) instead of a larger field GF(2 16 ) in a conventional CRC. 
     The present invention is also useful in two-level error correction code configurations such as that used in the related invention referenced above. In that invention, the variable length record is divided into subblocks, each of which having 2×2 check bytes of the two-way interleaved cyclic codeword for single error correction, and 1×2 extension check bytes for double error detection. At the second level, correction of a double burst error in one subblock is provided by reprocessing the subblock check bytes with additional 1×2 extension check bytes at the end of the block. Four additional check bytes at the end of the block are CRC check bytes which provide substantially strong data integrity check after ECC correction and may be generated in accordance with the present invention. 
     When used in the two-level ECC scheme described above, use of the same T matrix provides computational convenience when second level error correction requires recomputation of CRC bytes. 
    
    
     DESCRIPTION OF THE DRAWING 
     FIG. 1 is a block diagram of the logic for an encoding feedback shift register configured according to the principles of the present invention. 
     FIG. 2 is a block diagram of the logic for a feedback shift register for simultaneous decoding of data and error patterns configured according to the principles of the present invention. 
     FIG. 3 is a diagrammatic illustration showing the format of data bytes and subblock and block check bytes at the end of a two-level encoded record configured for a disk memory track constructed according to the principles of the present invention. 
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENT 
     The four check bytes, CRC1, CRC2, CRC3, CRC4, are given by ##EQU1## 
     The matrix T is a companion matrix of a degree-eight primitive polynomial, G(x). The polynomial is given by 
     
         G(x)=g.sub.0 ⊕g.sub.1 x⊕g.sub.2 x.sup.2 ⊕. . . ⊕g.sub.7 x.sup.7 ⊕x.sup.8,                                     (5) 
    
     where ⊕ signifies modulo-2 sum. 
     Different powers of the same primitive element T are used to create all CRC as well as ECC functions. The matrix T of the polynomial G(x) is given by the following non-singular matrix ##EQU2## 
     Referring to Equations (1)-(4), the byte sequence [D i  ] consists of all data bytes in a record and all first-level check bytes and excludes second-level check bytes. The byte sequence [Z i  ] consists of the same bytes but further excludes two check bytes corresponding to the last two byte positions of each subblock (except the last subblock) to create a recurring, two-byte offset between sequences [D i  ] and [Z i  ]. The two bytes are excluded by inhibiting the clock signal which controls the shift register processing [Z i  ] for two cycles. 
     The first-level check bytes in these sequences (and the corresponding error patterns) may be replaced by null bytes (i.e. all zeroes) in CRC calculatins. Such use of null bytes will eliminate the need for correcting errors, if any, in the ECC check bytes. 
     The sequence [Z i  ] is offset from the sequence [D i  ] by two bytes at the end of each subblock. When G(x) is a degree-8 primitive polynomial, the exponent for matrices T -1  and T -2  is 255. If a typical subblock is 102 bytes long, the recurring offset arrangement of the present invention provides combined effective cycle lengths of two CRC checks for sequences [D i  ] and [Z i  ] as given below: 
     
         255×102=26,010 bytes for [D.sub.i ], and 
    
     
         255×100=25,500 bytes for [Z.sub.i ]. 
    
     Thus, two identical detectable error patterns will not cancel each other simultaneously in both types of CRC checks for any record comprising up to 255 subblocks of data. 
     All four check bytes, CRC1, CRC2, CRC3 and CRC4, are computed by means of four 8-bit shift registers with premultipliers T -1 , T -2 , T -3  and T -4 , respectively. The sequence [D i  ] is entered into shift registers 1 and 3 with premultipliers T -1  and T -3 , respectively. Similarly, the sequence [Z i  ] is entered into shift registers 2 and 4 with premultipliers T -2  and T -4 , respectively. Note that subscript &#34;i&#34; counts from high to low and the last byte are identified by D 1  and Z 1  in their respective sequences. 
     By way of example for computing all CRC bytes according to the present invention, a typical encoder configuration for implementing Equation (3) is shown in FIG. 1. When the last bytes are entered, the contents of the four shift registers are shifted through 0, 1, 2 and 3 additional cycles, respectively, with null (all zeroes) input. The final contents of the shift registers comprise the four check bytes. 
     During the read process, CRC syndromes may be generated on-the-fly along with the ECC syndromes as the data are received. Of course, the CRC syndromes also must be adjusted for first- and second-level error correction. The equations for the four CRC cyndromes, S -1 , S -2 , S -3  and S -4  are given by ##EQU3## The symbol  indicates readback bytes, E 1  (D i ) and E 1  (Z i ) represent the first-level-error-correction patterns and E 2  (D i ) and E 2  (Z i ) represent the second-level-error-correction patterns corresponding to the recorded bytes D i  and Z i , respectively. The error patterns corresponding to the check bytes are replaced by null bytes. 
     The data sequence [D i  ] and the corresponding sequence of error-correction patterns [E 1  (D i )] appear at the input and output of the first-level decoder, respectively. If second-level error correction is required, then the error patterns [E 2  (Z i )] will be available for decoding at the second level. 
     If the first-level decoder includes a subblock buffer and on-the-fly error correction, then first-level CRC syndromes can be computed from the corrected data which is the combined sequence [D i  ⊕E 1  (D i )]. However, if the first-level error correction is deferred, then the subblock buffer and corrected data sequence may not be readily available. In that case, the CRC syndromes may be computed by combining partial computations. Syndrome S -3  is used to illustrate the process which is applicable to all CRC syndromes. The partial computations of Equation (9) are defined as ##EQU4## where S -3  (0), S -3  (1) and S -3  (2) denote the values for S -3  with no error correction, first-level error correction and second-level error correction, respectively. Corresponding equations for partial computations of Equations (7), (8) and (10) are given in Appendix A to this specification. 
     Equations (11) and (12) can be implemented using two shift registers (each similar to the one shown in FIG. 1) for processing the uncorrected sequence [D i  ] and the first-level-error-pattern sequence [E 1  (D i )] separately. Each shift register will use the multiplier T -3 . The first shift register provides a sufficient CRC check if no errors were corrected. This check is available immediately at the end of the record. When first-level error correction is required, the second shift register provides the CRC check with one-subblock delay from the end of record. 
     Preferably, however, the two sequences [D i  ] and [E 1  (D i )] can be processed in one shift register. Note that the one-subblock delay between these two sequences creates a delay of exactly 102 byte positions between them. If a count-down clock j, synchronized to the output of the first-level decoder, is used, then E.sub. (D j ) appears at the output in synchronism with D j-102  at the input. We can combine Equations (11) and (12) and rewrite in terms of j as ##EQU5## where L is the length of sequence [D j  ]. Note that E 1  (D j ) for j&gt;L and D j-102  for j≦102 do not exist, (are null bytes). 
     Equation (14) may be implemented with a shift register shown in FIG. 2 in which the sequence [D j  ] enters through a premultiplier T 3 ×102 and added to the sequence [E 1  (D j )] at the input as the clock parameter j counts down from L+102 to 1. The sequence [D j  ] starts at j=L+102 and ends at j=103. The sequence E 1  (D j ) starts at j=L and continues after j=102 to the end j=1. The final content of the shift register, when combined with CRC3, yields S -3  (1). 
     Referring to FIG. 3, all four readback CRC bytes at the end of the record also may be processed through a corresponding shift register along with the data during the readback process. Just as null bytes are entered for subblock check bytes during encoding, null bytes are also entered for the CRC positions at the end of the record. Similarly, null bytes are entered again for syndrome generation during the readback process. For example, byte CRC3 is physically offset two byte positions away from the last byte, D 1 , of sequence [D i  ] as shown in FIG. 3. Thus, two additional null bytes are entered into the shift register for CRC3 after byte D 1  during encoding as well as syndrome generation. 
     Readback byte CRC3 is processed through premultiplier 21 in shift register 20 after byte D 1  and two null bytes. At the end of entering sequence [E 1  (D i )] two null bytes need not be entered. The final contents of shift register 20 therefore is syndrome S -3  (1). The contents of shift register 20 upon entering the last readback byte CRC3 provides sufficient CRC check if no errors were corrected. In particular the content at j=102 is 0, if and only if, syndrome S -2  (1) is 0. Thus, if all ECC syndromes are 0, the immediate contents of the CRC registers at the end of the record provide a complete CRC check without requiring the final 100 shifting operations. Since most data records are error-free, this feature of the present invention provides substantialy performance advantage. 
     The other CRC syndromes are computed in like manner. Syndrome S -1 , given by Equation (7), merely requires different multiplier circuits, namely, T -1  and T 102  in place of those shown in FIG. 2. Syndromes S -2  and S -4  require processing of sequences [Z i  ] and [E 1  (Z i )], in which one subblock delay equals 100 byte positions between them. Thus, the corresponding multiplier circuits for S -2  are T -2  and T 2 ×100, and for S -4  are T -4  and T 4 ×100. 
     As in CRC3, any CRC byte may be processed along with the data through its shift register by allowing appropriate number of cycles with null byte input during encoding or syndrome-generation operations. In particular, CRC1, CRC2, CRC3 and CRC4 require 0, 1, 2 and 3 additional cycles, respectively, with null byte input at the end of their sequences [D i  ] and [D i  ] or [Z i  ] and [Z i  ]. 
     If no errors are present, all CRC syndromes will be 0. If second-level error correction is required, one of the subblocks with up to four byte-error corrections will be involved. Byte count &#34;i&#34; in sequence [D i  ] for each of the four error bytes will be determined from the error location numbers generated by the second-lvel ECC decoders of the referenced invention. Thereafter, for Equation (13), the term &#34;T -3i  E 2  (D i )&#34; for each i can be computed using the same log and antilog tables as those used by the ECC decoder employing the relation 
     
         T.sup.-3i E.sub.2 (D.sub.1)=log.sup.-1 {[log E.sub.2 (D.sub.i)-3i]modulo 255}.                                                     (15) 
    
     When added to the previously computed S -3  (1), the final CRC check of Equation (9) corresponding to the CRC syndrome S -3  is now complete. 
     Similarly, the byte count i in sequence [Z i  ] for each of the four errors will also be determined. Computations for syndromes S -1 , S -2 , S -3  and S -4  will be done in like manner. These final values of CRC syndromes must be all zero if all errors are corrected properly and no errors are present. 
     Errors in CRC bytes will tend to create unnecessary reread operations with undue performance penalty. In order to avoid such performance penalty, operational rules which balance adequate error correction and detection capability against unnecessary reread operations may be adopted. 
     Rule 1: All CRC bytes may be ignored if subblock level and block level ECC syndromes are zero. 
     Rule 2: One non-zero CRC check on [D i  ] sequence and one such CRC check on [Z i  ] sequence may be ignored if second-level correction is not required. 
     Rule 3: Block level ECC check may be ignored if all CRC checks are zero and second-level correction is not required. 
     Rule 2 allows errors in up to two CRC bytes, one each in sequences [D i  ] and [Z i  ], thereby retaining the benefit of the offset between such sequences. In order to balance the errors in the odd and even phases, odd phase CRCs, namely CRC1 and CRC3 are generated from the [D i  ] sequence and the even phase CRCs, namely CRC2 and CRC4 are generated from the [Z i  ] sequence. 
     According to the present invention, four separate CRC check bytes derived from the primitive field element in GF(2 8 ) provide not only computational convenience but also a better check. The recurring offset of the sequences [D i  ] and [Z i  ] provide desired long cycle length without using degree-16 polynomials.