Browse Prior Art Database

Cyclical Redundancy Check with a Nonself Reciprocal Polynomial

IP.com Disclosure Number: IPCOM000081085D
Original Publication Date: 1974-Apr-01
Included in the Prior Art Database: 2005-Feb-27
Document File: 3 page(s) / 50K

Publishing Venue

IBM

Related People

Oldham, DM: AUTHOR [+2]

Abstract

A nonself-reciprocal polynomial can be used for a cyclical redundancy check (CRC) of tape and still allow a read backward operation.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 57% of the total text.

Page 1 of 3

Cyclical Redundancy Check with a Nonself Reciprocal Polynomial

A nonself-reciprocal polynomial can be used for a cyclical redundancy check (CRC) of tape and still allow a read backward operation.

A conventional CRC for tapes uses a self-reciprocal polynomial such as: g(X) = X /9/+X/6/+X/5/+X/4/+X/3/+1 = (X+1) (X/8/+X/7/+X/6/X+/4/X+/2/x+1. This polynomial has a cycle length 17. Thus, two errors spaced exactly 17 bytes apart along any track of the tape are undetectable. In its place a nonself-reciprocal polynomial with a cycle length 255 can be employed such as G = X/9/+X/6/X+/2/+1 = (X+1) X/8/+X/7/+X/6/+X+1).

Inasmuch as this is not a symmetrical polynomial, several changes must be made in the implementation.

In order to save an extra shift when writing out the final CRC character on tape, the data connections are shifted down one register position (premultiply by X). After the last data byte is shifted in the cyclical redundancy code register (CRCR), the CRC character is ready in the linear feedback shift register (LFSR). The polynomial: G(2) = X/8/ X/7/ X/6/ X 1 is added to the CRC. This accomplished with the inversion blocks on the output of the CRCR. (See Fig. 1).

When reading in a forward direction, the data bits are shifted in the CRCR, Fig. 2, in a normal fashion followed by the CRC character. The inversion blocks on the output add X/5/X/4/ +X/3/ +X/2/ to the error free pattern

G = X/8/ X/7/ X/6/ X 1 to give an all 1's,

G = X/8/ X/7/ X/6/ X/5/ X/4/ X/3/ X/2...