Browse Prior Art Database

Cyclic Redundancy Check System

IP.com Disclosure Number: IPCOM000087618D
Original Publication Date: 1977-Feb-01
Included in the Prior Art Database: 2005-Mar-03
Document File: 4 page(s) / 116K

Publishing Venue

IBM

Related People

Nicholson, JO: AUTHOR

Abstract

This system provides a fast computation of a V41 code (using the polynomial 1 + X/5/ + X/12/ + X/16/) cyclic redundancy check (CRC), computing on an 8-bit basis, and it is particularly amenable to implementation using programming or microprogramming techniques.

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

Page 1 of 4

Cyclic Redundancy Check System

This system provides a fast computation of a V41 code (using the polynomial 1 + X/5/ + X/12/ + X/16/) cyclic redundancy check (CRC), computing on an 8-bit basis, and it is particularly amenable to implementation using programming or microprogramming techniques.

A byte of ingoing or outgoing data that is to be checked by the system may flow with the 0 bit first and the 7 bit last (sequentially, bits 0, 1, 2, 3, 4, 5, 6 and
7), or the data may flow in the opposite direction with the 7 bit first and the 0 bit last (sequentially, bits 7, 6, 5, 4, 3, 2, 1 and 0).

With the data flow being in the first mode mentioned, with the 0 bit first and the 7 bit last, Fig. 1 illustrates the algorithm of the system. The register 10 holds the 8 bits of data that are to be checked, and the register 12 holds the 16 bits of a current CRC number. As indicated in Fig. 1, the bits 0, 1, 2 and 3 of the data are exclusively ORed by exclusive OR 14 with bits 15, 14, 13, and 12 of the current CRC number. This comparison is on a bit-by-bit basis (as are all of the other exclusive OR or comparison operations described herein). Thus, bit 0 of the data is compared with bit 15 of the current CRC number; data bit 1 is compared with CRC bit 14; data bit 2 is compared with CRC bit 13; and data bit 3 is compared with CRC bit 12. The output of the exclusive OR 14 is 4 bits, which is indicated by the designation S1. At the same time as the exclusive OR 14 is operated, an exclusive OR 16 is operated to compare data bits 4, 5, 6, and 7 with current CRC bits 11, 10, 9, and 8, respectively. The output of exclusive OR 16 is applied to an exclusive OR 18 and compared with the previous result generated from exclusive OR 14 to give a 4-bit output indicated as S2. Bits 7, 6, 5, 4, 3, 2, 1 and 0 of the current CRC number are indicated as CRC[7..0].

The 4 bits of the quantity S2 and the 4 bits of the quantity S1 are applied through the following algorithm to arrive at a new CRC number 20. The 4 bits of the quantity S2 makes up the rightmost 4 bits of the new CRC number 20, as shown. Bits 4, 5, 6 and 7 of the new CRC number 20 are obtained by exclusively ORing the quantity S1 with the shifted rightmost 3 bits of the quantity S2, as shown. Bit #8 of the new CRC number 20 is obtained by exclusively ORing the leftmost bit of the quantity S2 with the rightmost bit of the quantity CRC[7..0]. Bits 9, 10 and 11 of the new CRC number 20 are obtained by exclusively ORing the shifted rightmost 3 bits of the quantity S1 with bits 1, 2 and 3 of the quantity CRC[7..0]. Bit 12 of the new CRC number is obtained by exclusively ORing the rightmost bit of the quantity S2 with the leftmost bit of the quantity S1 and then exclusively ORing this result with bit 4 of the quantity CRC[7..0]. Bits 13, 14 and 15 of the new CRC number 20 are obtained by exclusively ORing the leftmost 3 bits of the quantity S2 with the leftmost 3 bits of the quantity CRC[7..0].

With the data fl...