Browse Prior Art Database

Method for High Speed CRC Computation

IP.com Disclosure Number: IPCOM000044240D
Original Publication Date: 1984-Nov-01
Included in the Prior Art Database: 2005-Feb-05
Document File: 3 page(s) / 50K

Publishing Venue

IBM

Related People

Nielson, MC: AUTHOR

Abstract

This article describes a parallel implementation equivalent to a serial cyclic redundancy check (CRC) circuit and the procedure for designing it. CRC techniques are employed, especially in serially accessed mass storage devices, for detecting and sometimes for correcting data errors. The bit stream to be stored is divided modulo-2 by a binary polynomial, usually 16 bits wide, during the storage process to form a 16-bit remainder which is stored as the last two bytes in the data stream. When the data is read, the incoming bit stream (including the stored remainder) is divided by the same polynomial. If the new remainder is not equal to zero, then it is known that an error occurred in the reading of the data, presuming that the write function was verified, e.g., using a read-after-write scheme. Fig.

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

Page 1 of 3

Method for High Speed CRC Computation

This article describes a parallel implementation equivalent to a serial cyclic redundancy check (CRC) circuit and the procedure for designing it. CRC techniques are employed, especially in serially accessed mass storage devices, for detecting and sometimes for correcting data errors. The bit stream to be stored is divided modulo-2 by a binary polynomial, usually 16 bits wide, during the storage process to form a 16-bit remainder which is stored as the last two bytes in the data stream. When the data is read, the incoming bit stream (including the stored remainder) is divided by the same polynomial. If the new remainder is not equal to zero, then it is known that an error occurred in the reading of the data, presuming that the write function was verified, e.g., using a read-after-write scheme. Fig. 1 shows a well-known prior-art shift register CRC implementation of the divide modulo-2 process using the CRC polynomial D16 + D12 + D5 + 1. The input string, U, is serialized, either by the reading process or by a suitable parallel-to-serial converter. The remainder is accumulated in a 16-bit shift register which is used during the divide process in conjunction with three exclusive-OR gates to perform the division.

The circuit of Fig. 1 can be represented as a linear system over the finite field, GF(2), which has only two elements, 0 and 1, and all arithmetic is performed modulo-2. The signal flow graph of Fig. 2 is a convenient way of representing the system and was derived from the circuit of Fig. 1. The 1/D terms are sequence operators similar to the Z-transform for discrete time systems. Standard signal flow reduction techniques show that the transfer function for the linear system of Fig. 2 is:

(Image Omitted)

A parallel method for calculating the CRC can be derived by writing a set of state-space equations for Fig. 2. The state assignments are taken as the nodes of the signal flow graph. The state-space matrix and input vector derived from the signal flow graph of Fig. 2 are:

(Image Omitted)

The state-space equation is: DX(D) = A X(D) + b U(D) where X(D) is the 16 x 1 CRC vector, A is a 16 x 16 matrix, b is a 16 x 1 vector, and U(D) is the single bit input. (The matrix A turns out to be the transpose of the companion matr...