ON THE STRUCTURE AND DECODING OF CROSS PARITY CHECK CODES FOR MAGNETIC TAP

We describe and analyze a class of convolutional codes called cross parity check (CPC) codes, useful for protection of data stored on magnetic tape.;Cross parity check codes are first explained geometrically; their construction is described in terms of constraining data written onto a tape in such a way that, when lines of varying slope are drawn across the tape, the bits falling on those lines sum to zero modulo two. We then formalize this geometric interpretation by constructing canonical parity check matrices and systematic generator matrices for CPC codes and by computing the constraint lengths of a sub-class of CPC codes. The distance properties of CPC codes are analyzed and it is shown that these codes are maximum distance separable (MDS) convolutional codes.;Next, we show how CPC codes can be altered so as to make them more suitable for implementation without destroying either their geometric regularity or their MDS property; specifically, it is shown how the decoding delay of CPC codes can be reduced. This is done using the technique of parity check matrix reduction; each term of the parity check matrix is divided by some polynomial and only the remainder is retained. A class of polynomials that are particularly attractive for this purpose is identified.;Finally, we give examples of both error and erasure decoding algorithms that take advantage of the geometric regularity of CPC codes.