Browse Prior Art Database

Recomputing Cyclic Redundancy Code Check Bits

IP.com Disclosure Number: IPCOM000060427D
Original Publication Date: 1986-Apr-01
Included in the Prior Art Database: 2005-Mar-08
Document File: 3 page(s) / 50K

Publishing Venue

IBM

Related People

Desai, R: AUTHOR [+2]

Abstract

In some computer subsystem architectures, all or part of the data from a direct-access storage device is temporarily stored before being transmitted to the system. To assure data integrity, Cyclic Redundancy Code (CRC) check bits are typically appended at the end of the data field by the transmitting end, and stored at the receiving end. If errors are detected, an attempt is made to correct them before sending them to the channel. However, once any part of the field is changed because of correction or updating, the CRC bits are no longer valid, and have to be updated to reflect the changed data. In the past, CRC bytes have been regenerated for a given data field by clocking the entire data field through CRC hardware.

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 52% of the total text.

Page 1 of 3

Recomputing Cyclic Redundancy Code Check Bits

In some computer subsystem architectures, all or part of the data from a direct- access storage device is temporarily stored before being transmitted to the system. To assure data integrity, Cyclic Redundancy Code (CRC) check bits are typically appended at the end of the data field by the transmitting end, and stored at the receiving end. If errors are detected, an attempt is made to correct them before sending them to the channel. However, once any part of the field is changed because of correction or updating, the CRC bits are no longer valid, and have to be updated to reflect the changed data. In the past, CRC bytes have been regenerated for a given data field by clocking the entire data field through CRC hardware. In some cases, the data field clocked through the CRC hardware comprised the first changed byte through the last byte of that field, where a byte is a unit of data without specific bit length. The amount of time required to recompute the CRC was directly proportional to the physical position of the data bytes changed within the field. Thus, it takes more time to recompute the CRC if the changed bytes are at the beginning of the data field than if the changed bytes are near the end of the field. In accordance with the new method described here, CRC check bits for data which have been updated are themselves updated without having to clock the data through a CRC generator. As the length of the data field becomes relatively large, improvement in execution time becomes more significant. Procedurally, the original and updated data fields are added (modulo 2). The resulting data field has three parts: an initial part containing zero bytes, a middle part with nonzero bytes (where the field has been updated), and a tail end of zero bytes. Next, the (partial) CRC of the second part (the nonzero bytes) is generated. Using Galois Field multiplication, the partial CRC is multiplied by (T**n), where T is the generator polynomial in the form of a square matrix (as discussed below), and 'n' is the number of zero bytes in the tail end. Finally, the result is added to the original CRC to produce the check bits of the updated data field. The process of multiplying the partial CRC by (T**n) replaces the need for streaming the data through the generator. By breaking 'n' down into components which are stored, the task is now reduced to multiplying the partial CRC by the various factors of (T**n), which makes the implementation fairly straightforward. The CRC generator is the hardware implementation of a set of equations represented in the form of a square matrix. If CRC of the second part be C(r), the remainder, after passing the first zero byte through the generator, is C(r+1). Th...